File sync & deduplication

A 30-person architecture firm keeps its project folders in a sync service. Noor, an architect in the office, saves a 40 MB drawing about 20 times a day, usually after changing a few lines. Tariq is at a building site with a laptop and no signal. Every new project starts by copying the firm's 2 GB library of standard details.

Sending whole files would upload 20 × 40 MB = 800 MB a day for Noor's one drawing, then download it again on every device that holds the folder, and it would store each project's copy of the library separately. A sync design has to do better on each of these:

The core idea is to describe a file by its content. Dropbox splits every file into 4 MB blocks, hashes each block with SHA-256, and records the file's contents as its blocklist, the ordered list of those hashes. Noor's 40 MB drawing is a list of 10 hashes. The service keeps two kinds of server: a metadata server that knows users, folders and blocklists, and block servers that only map a hash to the stored bytes.

Saving a new version is a negotiation. The client first tries to commit the new blocklist; the metadata server answers with the blocks it doesn't have, the client uploads only those, and commits again:

The hashes double as a check. Dropbox's API exposes a content hash per file: the SHA-256 of the concatenated block hashes. A client can compare its local file with the server's copy without downloading anything, and verify an upload arrived intact (Resumable & chunked uploads).

Because a block's name is its hash, two identical blocks are the same block. When Noor copies the 2 GB library into a new project, the commits list hundreds of hashes the server already has, and nothing is uploaded. Downloads benefit too: before fetching a block, the Dropbox client checks whether it already has it locally, inside existing files or a cache of deleted ones. Storing each unique block once is deduplication.

Two questions follow. Can two different blocks share a hash? Systems built this way assume not: with a strong hash such as SHA-256, an accidental collision is far less likely than a hardware bit error. Older hashes such as SHA-1 can now be collided on purpose, so they're unsafe as names in a store shared across users. And can anyone who knows a hash claim the block? No: the metadata server accepts a blocklist without uploads only if the account has access to those blocks, and the block server checks access before serving them.

Deduplication across users also leaks information. If a file uploads instantly, it already existed somewhere in the service. An attacker who can guess most of a document can test every variant: a standard contract with a salary that is a multiple of $500 between $50,000 and $200,000 has only 301 versions, and the one that "uploads" instantly is the real one. The defenses trade away some savings:

Fixed blocks have a weakness. If Noor's drawing program inserts 1 KB near the start of the file, every byte after it moves, every later block boundary cuts in a different place, and every later block gets a new hash. One inserted byte at the start of a large file is enough to make the whole file look new.

Content-defined chunking places boundaries by looking at the data instead of counting bytes. A hash is computed over a small sliding window, 48 bytes in one early system and 64 bytes in the backup tool restic, and wherever the hash matches a chosen pattern, a chunk ends. An insertion changes only the chunks around it, because the boundaries after it are found again where the same content reappears. Minimum and maximum chunk sizes keep chunks in a useful range; restic cuts chunks of 512 KiB to 8 MiB.

A different fix sends a delta instead of blocks. The rsync algorithm has the receiver send a checksum for each fixed block of its old copy; the sender slides over the new file with a cheap rolling checksum, finds those blocks at any offset, and sends only the bytes in between. Dropbox uses rsync together with compression to shrink block transfers.

Once Noor's commit succeeds, the other devices in the firm need to find out. Dropbox records every file version as a row in an append-only journal: the shared folder, the path, the blocklist, and a journal id that only grows within that folder. Each device keeps a cursor, the last journal id it has seen, for every folder it syncs. An idle device holds a long poll open to a notification server that answers when something changes (WebSockets & long polling):

Google Drive's API has the same shape. A client gets a start page token for the current state, lists changes from that token, and saves the new token returned with the last page for its next check. The pattern is the same as in Chat delivery & sync: devices never ask "what's new?", they ask "what came after this point?", so a laptop that was off for a week gets exactly the changes it missed.

Large files add one more optimization. If other devices wait for the whole upload to finish before downloading, a large file takes nearly twice as long to arrive when upload and download speeds are similar. Dropbox lets other devices prefetch blocks of a file still being uploaded. The gain approaches 2× for large files at equal speeds; in a test with a slower upload than download, a 500 MB file synced in 293 s instead of 383 s.

Tariq edits the drawing offline at the site while Noor edits it in the office. When the laptop reconnects, the sync engine sees that its copy and the server's copy differ, but which one changed? Comparing the two can't tell a remote addition from a local deletion. Dropbox's rewritten sync engine keeps three trees: the remote tree (the server now), the local tree (the disk now) and the synced tree, the last state both agreed on. The synced tree is a merge base, as in version control:

The last row is Tariq's case. Whole files like drawings can't be merged automatically, so sync services keep both and leave the merge to people. Dropbox creates a conflicted copy with the editor's name, "conflicted copy" and the date in the file name; OneDrive keeps the online version under the original name and adds the device name to the local copy. Neither silently discards a version. Real-time co-editing avoids the problem for documents that support it (Collaborative editing).

Files also need a stable identity. Dropbox's original engine represented a move as a delete plus an add, so a network failure between the two could make a moved file vanish from other devices. Its replacement gives files and folders ids that survive moves, and moves are atomic regardless of folder size. Concurrent moves can still combine into a cycle in which each folder ends up inside another. Dropbox's original engine resolved this by duplicating folders; its replacement keeps the original folders, and the final arrangement depends on which move reaches the server first.

Each choice below answers one of the needs from the start of the page. Together they let Noor save twenty times a day for the cost of a few blocks, keep one copy of the firm's library, and bring Tariq's laptop back in without losing either drawing: