Chunks, hashes and two stores

Part of the free System Design course on LogicWiz, in the chapter: Design file storage and sync (Dropbox, Google Drive). The interactive whiteboard exercises and simulations run in the app.

Week 18, Day 2: Two stores, one file

"I fixed one typo in a 200 MB slide deck. The app uploaded all 200 MB again, and my phone data ran out."

Meera, on her hotspot

The simplest version, and what breaks

Start with the smallest design that works. The client sends the whole file to one file server. The server writes it to disk and saves the file name in a database. Download is the reverse.

Now count what breaks at our numbers:

  • A 2 GB upload needs one unbroken connection for minutes. A drop at 97 percent means a restart.
  • A small edit resends the whole file. Most of the 20 TB a day would be bytes we already hold.
  • 5 PB does not fit on one disk, and a dead disk loses files.
  • The server keeps no list of changes, so it cannot tell a second laptop what is new.

Each box below answers one of these.

Cut every file into chunks

A chunk is a fixed-size piece of a file. Use 4 MB. A 2 GB file becomes 2,048 / 4 = 512 chunks, numbered 0 to 511. The client sends each chunk as a separate small request. Three gains follow:

  • Resume. If the connection drops after 358 chunks (70 percent), the client asks which chunks the server holds and sends the other 154, not all 512.
  • Parallel transfer. Send four chunks at once, and one slow connection stops being the limit.
  • Send only what changed. A 200 MB deck is 200 / 4 = 50 chunks. Fix one slide and, if the editor changes the bytes in place, one or two chunks change. The client sends 4 to 8 MB, not 200 MB.

Why a fixed size? It is simple: chunk n starts at byte n x 4 MB, so no scanning is needed. The trade-off is that inserting bytes near the start of a file shifts every later chunk, so all of them change. Edits in place and appends keep most chunks stable. Some formats, such as zipped office files, may rewrite much of the file on save, and then many chunks change. Cutting at content-defined points (where the bytes themselves decide the boundary) avoids the shift from inserts, and it is a good follow-up to mention.

Why 4 MB and not 4 KB? A 2 GB file would become 524,288 chunks, each a request and a metadata row. Why not 400 MB? One changed byte resends 400 MB. A few MB is a common balance.

Meera objected: "Our average file is 1 MB, so chunking is pointless." The average hides the tail. A few huge files hold most of the bytes. A file under 4 MB is one chunk and costs nothing extra, so one rule fits every file.

Fingerprint every chunk

A hash is a short fixed-size fingerprint computed from bytes. SHA-256 gives 32 bytes. The same bytes always give the same hash, and two different chunks will not share one in practice. Name each chunk by its hash. This is content addressing: the name says what is inside.

Upload now starts with a question. The client hashes every chunk and sends the list. The server answers "missing: chunks 3, 4 and 9". The client sends only those. Resume, delta upload and de-duplication all come from this one step.

De-duplication means storing identical content once. Picture 1,000 SwiftKart store managers saving the same 3 MB price-list template. The server keeps one copy with a reference count of 1,000, the number of files that use it. Without dedup that is 3 GB. When a file is deleted, the count drops by one. At zero, the chunk can go.

Dedup is about bytes, not names. A file copied into another folder, or renamed, uploads zero bytes.

⚠️ Warning: Asking "does this hash exist?" across all users can reveal that someone else holds a file. Think about whether dedup should work inside one account or across all.

Two stores: bytes and descriptions

Chunks go into object storage. It is cheap per GB and keeps several copies. It has no folders and does not edit a blob in place, which suits chunks that never change. Everything else goes to a metadata service backed by a SQL database:

  • the file tree: folders, names and moves
  • versions: each one is an ordered list of chunk hashes
  • sharing and permissions
  • the change log

Why SQL? A folder rename or move must be atomic. A commit must write the new version, update the current version and add a change-log row in one transaction. Shard by user id, so one user's whole tree sits on one shard and a folder listing touches one shard. From lesson 1: 1.5 TB of files plus a chunk index of roughly 0.5 TB (billions of unique chunks at about 100 bytes a row, plus indexes) is 2 TB. Over 8 shards, that is 250 GB each.

Someone always says: "Put the bytes in the database too, to keep one place." At 5 PB that costs far more per GB, fills the database with data it never queries, and slows the queries it does serve.

One rule protects readers: a new version appears only after all its chunks are stored. The client calls commit last. The metadata service checks that every hash exists, then writes the version. If the laptop dies at chunk 40 of 50, other devices still see the old version. Stray chunks are cleaned up later.

One upload and one download, walked through

sequenceDiagram
  participant C as Client
  participant M as Metadata service
  participant U as Upload service
  participant O as Object storage
  C->>M: new version, chunk hashes
  M-->>C: missing chunks 3, 4, 9
  C->>U: send missing chunks
  U->>O: store each by hash
  C->>M: commit, base version 7
  M-->>C: version 8 saved

To download, the client asks the metadata service for the version. The service checks permission and returns the chunk list with short-lived download links. The client fetches chunks in parallel, checks each hash, and joins them into the file. A hash mismatch means a damaged chunk, so the client fetches it again.

Draw it yourself. Add object storage for the bytes, a queue for change events and a notification service for other devices, and remove the single database.

Telling the other devices

The bytes are safe, but the phone still does not know. The metadata service writes every commit to the change log: one row per change, numbered 1841, 1842 and so on. Each device remembers its cursor, the number of the last change it applied.

After a commit, the service puts an event on a queue. A notification service, which keeps one open connection per online device, sends a small ping: "something new". The phone calls GET /changes?cursor=1840, receives entries 1841 to 1843, downloads only the chunks it lacks, and moves its cursor to 1843. The next lesson shows why this beats polling.

📌 Summary: Cut files into 4 MB chunks named by their hash, so uploads resume, send only changes and store identical chunks once. Keep bytes in object storage and descriptions in a metadata database.

What Meera learns next

The hardest part is left. Two devices edit one file while offline. How do you sync without losing anyone's work, and who may open what? Next: sync in depth, conflicts, sharing links, trash and the bill.

Check your understanding

  1. Meera uploads a 2 GB file in 4 MB chunks (512 chunks). The connection drops after 358 chunks. What should the app do after reconnecting?
  2. Two different users upload the same 4 MB chunk. What should the storage layer hold?
  3. A 200 MB deck has one slide corrected, and the editor changes the bytes in place. With 4 MB fixed chunks, about how much does the client upload?
  4. A laptop uploaded 40 of 50 chunks of a new version, then lost power before commit. What do the user's other devices see?
  5. A teammate says: "Keep the chunk bytes in the same SQL database as the file tree, so we have one place to look." What is the best reply?