How to design photo storage with dedup
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
The problem
A photo backup service takes uploads from phones and computers, keeps one copy of any photo whose bytes it has already seen, and lets each owner browse, view and delete their own library. Ownership and bytes are separate records: a photo row belongs to a user, a content row is keyed by the SHA-256 of the bytes, and many photo rows can point at one content row. The answer turns on keeping those two records honest at the two moments they can disagree: when two uploads of the same new bytes arrive together, and when one owner deletes a photo whose bytes someone else still needs.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
What counts as a duplicate: identical bytes, or the same picture at another size or compression? | A byte-identical match is a hash lookup. A near-duplicate match is a perceptual-hash or vision problem, a different system with different failure modes. | Byte-identical, matched by the |
Do we deduplicate across users, or within one user's library? | Cross-user sharing saves the most storage, but a skipped upload then confirms to the uploader that the file is already held by somebody, and it makes deletion a shared decision. | Across users. That is what makes deletion interesting, and you should raise the privacy cost yourself. |
How many uploads a second, and how many photos are stored? | The rate sizes the hot path through the content table; the stored count sizes the hash index and decides whether one database can hold it. | Over 4 trillion photos stored, 28 billion new photos and videos a week, about 46,000 a second on average. |
Can the hash from the client be trusted? | A client that can claim any hash can attach itself to bytes it has not held, or make the service store bytes under the wrong name. The answer decides whether the server must read the bytes itself before linking. | No. The server checks the bytes before it links them to anything. |
When a user deletes a photo, how fast must it disappear, and must the bytes go too? | The owner's view and the shared bytes are different promises. The first is a row delete; the second depends on who else holds the same bytes. | The owner stops seeing it at once. Bytes go once no photo record points to them, and not while one does. |
Do uploads need to resume after a dropped connection? | Phones upload on flaky networks. Resumable uploads change the shape of the pending area and of the complete call. | Nice to have. Design the pending area so a resumable upload could use it, but do not spend the round on chunking. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
Content is never deleted while any photo record still points to it | Ownership and bytes live in separate rows, and a photo row's link to its content row is the fact that protects the bytes. Any change to who points at a blob happens in a transaction with the photo change, and bytes are removed by a later job that re-checks the row, not by the delete request itself. |
A matching hash is verified on the server, never trusted from the client | Uploaded bytes land in a pending area, not in the content store, and a server-side step hashes them before any photo row links to them. The client's hash is a lookup key for skipping work, not evidence. |
Two identical uploads at the same moment store the bytes once | The content table has a unique key on the hash, and linking a photo is an insert-or-find against that key inside one transaction. The loser of the race finds the row the winner made and discards its own pending copy. |
A deleted photo stops being viewable by its owner at once | The delete request removes or marks the photo row synchronously and the library reads from that table, so the owner's next page omits it. Signed URLs already handed out are short-lived, so a cached link stops working soon after. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Upload rate | 28 billion a week ÷ 604,800 seconds a week ≈ 46,300 | About 46,000 photos and videos a second on average | The write rate through the content table and the pending area; peaks will be higher, so the design is judged against this as a floor. |
Uploads a day | 28 billion ÷ 7 days = 4 billion | About 4 billion new photo rows a day | How fast the photo table grows, and how much a daily cleanup of abandoned uploads has to look at. |
Size of the hash index if nothing deduplicates | 4 trillion content rows × 32 bytes per | About 128 TB for the hash column by itself, before storage keys, counts or index overhead | Why the content table is sharded by hash prefix from the start: a hash column that large, taking tens of thousands of writes a second, is split across nodes for write throughput and operations rather than kept on one, even in the best case where dedup shrinks it. |
Writes per content shard | 46,000 a second ÷ 256 shards ≈ 180 | About 180 inserts or count updates a second per shard with 256 shards | How many shards make the per-shard write rate ordinary. Hashes are uniformly spread, so the first byte of the hash is a fair shard key. |
Storage that cross-user dedup saves (example assumptions) | Assume 10% of uploads are byte-identical to content already stored and 3 MB per item: 10% × 28 billion = 2.8 billion skipped a week; 2.8 billion × 3 MB = 8.4 PB | About 8.4 PB a week not written under those assumptions | What is at stake in the cross-user versus within-user choice. The percentage is an assumption to state out loud, not a measured figure. |
Time for a full mark-and-sweep scan | 4 trillion photo rows ÷ an assumed 10 million rows a second = 400,000 seconds | About 4.6 days per full pass | Why a scan is an audit that runs now and then, and reference counts carry the live deletion path. |
Abandoned uploads in the pending area (example assumptions) | Assume 1% of uploads fail to complete: 46,000 × 1% = 460 a second; 460 × 3 MB ≈ 1.4 GB a second; × 86,400 seconds ≈ 120 TB a day | On the order of 120 TB a day of pending bytes to expire | The cleanup job on the pending area, which deletes sessions and objects older than a cutoff. |
Core entities
| Entity | What it holds |
|---|---|
Content blob | One row per distinct set of bytes, keyed by its hash. Owns the storage key and knows how many photos point at it. |
Photo | One row per upload a user keeps: who owns it and which content blob it shows. |
Rendition | A thumbnail or resized copy, made once per content blob and shared by all the photos that point at it. |
Upload session | A pending upload: what the client claimed, where the bytes are landing, and how far it got. |
The API
| Endpoint | Notes |
|---|---|
| The client hashes the file locally and asks first. On a hit the service may link a photo row at once and return photo_id with no bytes moved; on a miss it creates an upload session and returns a short-lived signed URL into the pending area. Whether a hit should skip the upload across users is the privacy trade-off in the first deep dive. |
| The server hashes the pending object, compares it with the claimed hash and size, then runs one transaction: insert-or-find the content row by hash, adjust its count, insert the photo row. A mismatch returns HTTP 422 and the pending object is deleted. Calling complete twice returns the same photo_id because the session records the result. |
| Pages the owner's photo rows by (owner_id, taken_at, id). Each item carries the photo id and thumbnail URL; rows with deleted_at set are skipped. |
| Checks the caller owns the photo, then signs a short-lived CDN URL for the rendition's storage key. The URL names the blob, so two users with the same photo get URLs to the same object. |
| Owner-scoped. Removes or marks the photo row and lowers the content count in one transaction. Bytes are not touched here; the sweeper decides later. |
The high-level design
Step 1 of 4
Two tables and a pending area
Start with the separation the whole question rests on. A photo table holds one row per upload a user keeps, with an owner and a pointer to content. A content table holds one row per distinct set of bytes, keyed by SHA-256, with a reference count. The client hashes its file and calls POST /uploads with the hash; the API looks the hash up. On a hit it adds a photo row and returns a photo id. On a miss it hands back a signed URL into a pending area, the client puts the bytes there, and on complete the API moves them into the content store under a key derived from the hash and adds both rows. Deleting a photo removes the photo row and lowers the count. The weakness is that the API believes the client: the hash it looked up and the key it files the bytes under both come from the phone.
What breaks first
The deep dives
Uploading with dedup. Two phones upload the same new photo within the same second, and neither copy is stored yet. Walk one upload through the service: where the hash is computed, where the bytes land, when the photo appears, and what makes the second phone's copy go away.
Deleting safely. Alice deletes a photo whose bytes other users also hold, and at that moment Bob is finishing an upload of the same photo. What is removed, what is kept, and how does the service know the difference?
A concept that helps here: Reference counting and mark-and-sweep
A concept that helps here: Transactions and isolation levelsA concept that helps here: Job scheduling and delayed workConcepts this guide uses
- Content addressing and deduplication
- Blob storage and presigned uploads
- Transactions and isolation levels
- Reference counting and mark-and-sweep
- Job scheduling and delayed work
Sources
- Google: Updating Google Photos' storage policy to build for the future
- Dropbox: Inside the Magic Pocket
- Amazon S3 documentation: Uploading objects with presigned URLs
- Amazon S3 documentation: Checking object integrity for data uploads
- PostgreSQL documentation: INSERT
- IBM Research: Side channels in cloud services: Deduplication in cloud storage (Harnik, Pinkas, Shulman-Peleg, IEEE Security and Privacy)
- Wikipedia: Garbage collection (computer science)
- Wikipedia: Reference counting
- Wikipedia: Tracing garbage collection
- Encryption Consulting: What is SHA-256?
- Wikipedia: Crypto-shredding
- GDPR: Right to erasure (right to be forgotten)