Design deduplicated multi-tenant file storage

01The design, in the six-step framework

1. Requirements

Functional

• Tenants (companies) upload files on behalf of their users; each tenant's data is private to it.
• Identical bytes uploaded by different tenants or users are stored once; uploads of known content complete without sending the bytes.
• Download, list and delete with per-file access control; a deleted file is reclaimed only when no one references it.
• Out of scope: editing, sharing between tenants, sync clients.

Non-functional

• 10 million tenants, 10 billion files, 50 PB logical; dedup expected to cut physical storage by at least 40 percent.
• No tenant can learn anything about another's data, including whether a given file exists elsewhere (the dedup side channel).
• Durability eleven nines; download first byte under 100 ms; upload acknowledgement under 500 ms for already-known content.
• Encryption at rest with keys the provider's staff cannot casually use.

2. Core entities

• Tenant: id, key-encryption key id, quota.
• File: tenant, path, size, ordered chunk list (hashes), owner user, ACL, created-at, deleted flag.
• Chunk: content hash, size, blob location, reference count, encryption metadata.
• Reference: (chunk hash, file id) kept as a ledger so counts can be rebuilt.

3. API

• POST /tenants/{t}/files body: path, size, chunk hashes → response: which chunks to upload (as presigned URLs) and an upload id.
• PUT /chunks/{hash} → chunk bytes, verified against the hash on arrival.
• POST /uploads/{id}/commit → file becomes visible; references are recorded.
• GET /tenants/{t}/files/{id} → chunk download URLs in order; DELETE → marks deleted.

4. High-level design

Uploading a 100 MB installer that 2,000 other tenants already hold:

1. The client cuts the file into content-defined chunks and sends 25 hashes. The file service asks the chunk index which exist: all 25 do.
2. No bytes are uploaded. commit writes the file record on the tenant's shard and 25 reference rows; the chunks' reference counts go up.
3. For a genuinely new chunk, the chunk service verifies the hash of the bytes it receives, encrypts the chunk with a key derived from its content, writes it to object storage, and inserts the index row.
4. A download reads the file record, checks the ACL, and returns per-chunk download URLs the client fetches in parallel.

5. Deep dives

The side channel: how does dedup not leak that someone else has the file?

Naive client-side dedup answers "already have it, skip the upload" in 5 ms and "please upload" in 2 s, so a malicious tenant can test whether a secret document exists anywhere by hashing it. Three defences, used together. First, the API never reveals existence to the client: the response always lists every chunk as uploadable with a presigned URL, and the chunk service accepts the bytes and discards them if the hash is known, so timing and bandwidth look the same. Second, hashes are keyed: the client computes an HMAC with a per-tenant or per-provider secret rather than a bare SHA-256, so an outsider cannot even compute the identifier for a known file. Third, rate limits and anomaly detection on hash-check volume catch brute-force probing. The cost is bandwidth: the "skip the upload" saving is lost for cross-tenant dedup, kept for same-tenant dedup where the side channel does not apply. Say which trade you make: most providers keep client-side dedup within a tenant and server-side dedup across tenants.

Encryption versus deduplication: can both hold?

If each tenant encrypts with its own key, identical plaintext becomes different ciphertext and dedup is dead. Convergent encryption resolves it: the chunk key is derived from the chunk's content hash, so equal content gives equal ciphertext and dedups, while a tenant without the content cannot derive the key. Each tenant's file record stores the chunk keys wrapped with the tenant's own key from the key service, so revoking a tenant's key makes its files unreadable without touching shared chunks. The honest weakness: convergent encryption lets an attacker who can guess a plaintext confirm it (the same side channel in cryptographic form), which is why low-entropy data (a form letter with one name changed) is sometimes excluded from cross-tenant dedup or salted per tenant.

Reference counting at 10 billion files: how do deletes stay correct?

Incrementing a counter in the chunk index on every commit and decrementing on every delete looks simple and goes wrong under retries and partial failures: a retried commit double-counts, a crashed delete leaks. Keep the references as rows, (chunk, file), written in the same transaction as the file record, so they are exactly as correct as the file itself. The count is a derived value. A background garbage collector scans for chunks whose reference rows are gone, waits a grace period (24 hours, to survive a file that is deleted and re-committed), then deletes the blob. Deleting a file is therefore cheap (mark deleted, drop references) and reclaiming space is eventual, which is the right trade.

Isolation: the tenant boundary in every layer

The gateway resolves the tenant from the credential, and every file-service query carries the tenant id as the first key component, so a bug cannot read across tenants by forgetting a filter. The chunk layer is shared by design, which is what makes dedup possible, so its API accepts only hashes that the file service has authorised for that request (a short-lived signed token per chunk), never arbitrary hashes from the client. Authorization for downloads is checked on the file, and the chunk URLs are signed with a 5-minute expiry bound to that file id.

Chunk boundaries: fixed or content-defined, and what size?

Fixed 4 MB chunks are simple and dedup whole-file duplicates perfectly, but a one-byte insert near the start of a file shifts every later boundary and defeats dedup for edited documents. Content-defined chunking cuts where a rolling hash over a sliding window hits a chosen pattern, so boundaries move with the content and an edit changes only the chunk it touched. Smaller chunks dedup better but inflate the index: halving the chunk size doubles the 480 GB index and doubles the per-file reference rows. A 4 MB average with 1 MB minimum and 16 MB maximum is a defensible middle; say that the number is a tuning decision backed by measuring the dedup ratio on real tenant data.

6. What a strong answer sounds like

• Name the dedup side channel before the interviewer does, and give a concrete mitigation with its bandwidth cost.
• Explain convergent encryption in two sentences and its limit on low-entropy data.
• Replace counters with reference rows plus a grace-period collector; say why counters fail under retries.
• Give the arithmetic: 30 PB physical, 7.5 billion chunks, a 480 GB index.
• Expect follow-ups on quota accounting under dedup (charge logical bytes), on a tenant leaving (crypto-shred by deleting their wrapping key), and on hot chunks.
• Common mistake: dedup by bare SHA-256 with an early-return "already exists" response.

02Where this question was reported

• PracHub · Hard