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

1. Client calculates digest of chunk
2. Client sends digest to server
3. Server replies with exists or doesn't exist
4. If digest exists then the client moves on to next chunk
5. 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?

1. Negotiate session with epitomed server
2. Create metadata header
3. Read files and chunk them with the negotiated block size
4. Call write_exists to save chunk if it doesn't exist
5. Save chunk metadata
6. Repeat until all files are processed
7. Write metadata trailer
8. Send metadata to epitomed server
9. 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!