Marco Peereboom

Epitome2

Dedup for the masses

Agenda

Overview of data deduplication and its associated technologies
Outline of Epitome2 architecture
In-depth look at Epitome2

What is dedup?

Deduplication, or dedup for short, is act of eliminating redundant data from a dataset.
The easiest way to explain that definition is with an example:
- Someone sends an email with a picture attachment of their adorable baby to 20 others in their office.
- That results in 21 copies of the baby picture on the mail server.
- Since the picture is identical the smart mail server only saves 1 copy.

Better example

The OpenBSD CVS src repository, not the tree, holds ~93900 files that add up to ~1.6GB
Of those files about 50 change per day
At an average of 18K that is <1MB in actual changes.

Better example continued

Assume a traditional towers of Hanoi backup with a weekly full at 50% compression
- Bandwidth cost per week: tar 0.8GB, epitome 0.8GB
- Bandwidth per month: tar 3.21GB, epitome 3.71MB
- Bandwidth per year: 38.48GB, epitome 0.89GB
Over the course of a year Epitome uses 44x less bandwidth and disk space!

Cool savings

Disk space
Network bandwidth
Systems Administrators hair!

Deduplication types

Source
- Heavy lifting done at the client
Target
- Heavy lifting done at the server
Post-process
- Data is spooled first and dedup happens in a lazy fashion afterwards
In-line
- Dedup happens in-line as it streams over the network

Why do we want dedup?

Minimize storage usage in backup scenarios
- No discernible seek time
- Shorter backup window
- Disk is generally faster than tape
- Disks are cheap
Minimize network resource consumption
- Sizes of backups disproportionate with available bandwidth
Get rid of tape and proprietary backup software
- Tape is going away (really!)
- Tapes are unreliable

Why don't we want dedup?

Primary storage
- Usually too slow
- Brittle due to ever changing I/O patterns
File system storage
- Resource hungry
- Cumbersome and requires special handling
End-all, be-all
- There are serious cost trade offs between storage and processing resources

Industry state

Patents, Patents, Patents!
Buzzword heavy
Expensive
Silly solutions marketed as dedup
Poor resource balance
Implicit vendor lock-in
Questionable sales tactics
No open source alternatives

What is Epitome?

Epitome is an open source deduplication engine
- Not encumbered by patents
- No license deception
- Free
Encrypted network protocol designed to reduce bandwidth usage
Backend and frontend tools

Pieces and tools

epitomed
- Server side daemon that handles deduplication sessions
epitomize
- Client side backup tool (tar-like)
eprepare
- Server side tool to prepare the backend storage (format)
libepitome
- Library for client and server tools that provides all dedup primitives

Architectural Overview

Why wire protocol?

Bandwidth minimization
- Spooling and other transparent deduplication techniques only save disk space at the cost of processing power
Patent avoidance
- Simple protocol with primitives that are covered by prior art
Spread of resource utilization
- Everyone shares in processing load

Dedup algorithm

Client calculates digest of chunk
Client sends digest to server
Server replies with exists or doesn't exist
If digest exists then the client moves on to next chunk
If the digest does not exist then the chunk is compressed and the smallest result is sent to the server

Dedup algorithm details

SHA-1 (160 bit) fingerprints
- Simple, fast and not too big
- Hash collisions probability exists
zlib compression
- Fast, portable and reasonably simple API
Mandatory SSL encryption
- Using ASSL to abstract OpenSSL
Why so simple?
- Patents, Patents, Patents!

Hash collisions

The probability* of a hash collision (n is number of hashes, b is bits in the hash) is

Example: 80M hashes @ 16KB (12.2TB of data) has a smaller than 2.18e-31 probability of a hash collision
No excuse for not detecting collisions though!

* See section 3.1 of http://doc.cat-v.org/plan_9/4th_edition/papers/venti/

Future hash considerations

Currently Epitome does not detect collisions, bad author!
In the future Epitome will use the OpenBSD ports methodology
- A number of different hashes
- Chunk size considered a hash too

epitomed

Server side daemon that forks individual connections into sessions
Negotiates sessions parameters with client
Verifies chunks going in and out based on settings
Maildir-like backend that uses eXternal Data Representation (XDR)
Driver-like implementation that makes adding a different backend relatively simple

epitomize

Client side backup tool
Tar-like which makes it familiar
Initiates connections to epitomed server
Results in a backup token or local metadata
- Token is SHA1 of metadata

eprepare

Generic tool to prepare backend
- Initialize databases
- Initialize other backend pieces
Calls the prepare function in the backend driver
Currently only maildir like backend supported
- Create maildir-like directory structure for epitomed

Protocol basics

Client initiates commands and server replies to said commands
Protocol is versioned and does not allow version mixing
Each protocol primitive, request and reply, is 32 bytes
Primitives optionally have a payload
SCSI-like quality
Each command has a uniquely identifying tag

Protocol primitives

NEG(2), NEG_REPLY(3)
NOP(10), NOP_REPLY(11)
EXISTS(12), EXISTS_REPLY(13)
READ(14), READ_REPLY(15)
WRITE(16), WRITE_REPLY(17)
WRITE_MD(18), WRITE_MD_REPLY(19)
READ_MD(20), READ_MD_REPLY(21)

NEG

Negotiate parameters between client and server
Client requests certain parameters and the server dictates the results
The client shall obey the server parameters

NOP

Send No Operation request to the server
Used to determine if a server is alive or other round-trip requirements
The NOP contains a NOP_ID and that NOP_ID is incremented by 1 when completed by the server

EXISTS

Ask server if a digest exists
May contain a verify chunk flag
Server replies exists or doesn't exist and if requested the result of the verify operation

READ

Read chunk from server
If the digest exists it is sent from the server to the client
The server sends the chunk either compressed or uncompressed based on settings and optimal bandwidth usage
Optionally the chunk is verified if requested by the client

WRITE

Write chunk to server
If the chunk doesn't exists then it is written to the backend
Optionally the chunk is verified if requested by the client
Client should always send an EXISTS before it sends the WRITE to minimize network traffic
- This is a single API call

WRITE_MD

Write metadata to the backend
Medatata is validated before continuing and finishing operation
Server returns backup token to the client

READ_MD

Read metadata from backend
Medatata is validated before continuing and finishing operation
Server returns metadata to the client

How does epitomize work?

Negotiate session with epitomed server
Create metadata header
Read files and chunk them with the negotiated block size
Call write_exists to save chunk if it doesn't exist
Save chunk metadata
Repeat until all files are processed
Write metadata trailer
Send metadata to epitomed server
Display backup token

Future development

Finish the code!
Protocol enhancements
Content Addressable Storage
- Natural progression
- Stink on filesystems
HTTP version of the Epitome protocol
- Industry standard, currency of the Internet
- Slightly heavier on the wire but enables bypassing silly corporate firewalls
Buzzword compliance
- Continuous Data Protection (CDP)
- Virtual Tape Library (VTL)
- Dedup File System (DFS)

Conclusion

Simple
The price is right
Cross platform and architecture neutral
No patents
No license deception

Thanks!

Asiabsdcon for inviting me.
Mark T. Uemura for his help getting me here!
The friendly folks at the OpenBSD project for letting me play
My lovely wife for putting up with all this!

Questions?

Shoot!