Skip to content

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
Asked at
Practice this question

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

AskWhy it mattersA 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 SHA-256 of the file. Resized or recompressed copies are different photos here.

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.

The requirements menu

RequirementScopeWhy

Upload photos from phones and computers

Core

The write path, and the one where dedup happens. The client sends a hash first and bytes second, so the service can skip bytes it already holds.

Browse a library and view photos at different sizes

Core

The read path. Thumbnails and full-size renditions are made once per content blob and served through a CDN with signed URLs.

Delete photos

Core

Deleting a photo removes one owner's record. Whether the bytes go is a second decision that depends on who else points at them.

Store byte-identical uploads only once, matched by SHA-256

Core

The dedup rule. It makes the content table keyed by hash the center of the design, and it forces the race between two identical uploads to be settled somewhere.

Resume an interrupted upload

Optional

Worth a sentence: the pending area and the complete call already separate receiving bytes from linking them, so a resumable or chunked upload fits without a new path. Leave the chunk protocol out unless asked.

Keep deleted photos in a trash for a while before they go

Optional

A real product feature, and cheap here: a deleted_at on the photo row delays the count change instead of the record delete. Take it if the interviewer asks what an accidental delete does.

Dedup within one user's library instead of across users

Optional

The privacy-safe setting. It gives up most of the savings but means a skipped upload reveals nothing about other users and erasure is simple. Name it as the fallback when cross-user sharing is challenged.

Verify stored bytes still match their hash

Optional

A background scrubber re-hashes stored content and flags corruption. It belongs in the deletion deep dive as the audit that backs the counts, so bring it up there rather than as a separate requirement.

Video uploads

Optional

The scale figures count photos and videos together, so videos are in the traffic. The dedup and deletion logic is identical; the renditions differ. Say that and keep the round on photos.

Near-duplicate detection of resized or recompressed copies

Out of scope

A hash match means the bytes are the same; a resized or recompressed copy has different bytes and a different hash. Finding visually similar photos is a separate system with fuzzy matches and false positives.

Albums and sharing

Out of scope

Grouping and access control over photo records, which sits above the storage layer. Keep an owner id on the photo row and stop.

Editing photos

Out of scope

An edit produces new bytes with a new hash, so it is an upload. Nothing in the storage design changes.

Client-side encryption of photos

Out of scope

Encrypting with a per-user key makes identical photos produce different bytes, which defeats cross-user dedup. Mention the conflict and move on.

Non-functional requirements

RequirementWhat 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

QuantityWorkingResultWhat 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 SHA-256 = 1.28 × 10^14 bytes

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

EntityWhat 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

EndpointNotes

POST /uploads { sha256, size } → { upload_id, upload_url } or { photo_id } when the content exists

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.

POST /uploads/{id}/complete → { photo_id }

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.

GET /photos?cursor={c} → { photos, next_cursor }

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.

GET /photos/{id}?size={thumb|full} → signed URL

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.

DELETE /photos/{id}

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

hash firstbyteslookup, linkmove bytesClientPhoto APIPending uploadsContent and phototablesContent store byhash

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.

hash firstbyteslookup, linkcompletereadmove oncenew blobwrite sizessigned URLzero, ageddelete bytesrecountre-hashexpireClientPhoto APIPending uploadsContent and phototablesHash verifierContent store byhashRendition workerCDNSweeperMark and sweepauditPending cleanup
The whole design

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.

A concept that helps here: Content addressing and deduplicationA concept that helps here: Blob storage and presigned uploadsA concept that helps here: Transactions and isolation levels

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: Transactions and isolation levelsA concept that helps here: Job scheduling and delayed work

Concepts this guide uses

Sources

  1. Google: Updating Google Photos' storage policy to build for the future
  2. Dropbox: Inside the Magic Pocket
  3. Amazon S3 documentation: Uploading objects with presigned URLs
  4. Amazon S3 documentation: Checking object integrity for data uploads
  5. PostgreSQL documentation: INSERT
  6. IBM Research: Side channels in cloud services: Deduplication in cloud storage (Harnik, Pinkas, Shulman-Peleg, IEEE Security and Privacy)
  7. Wikipedia: Garbage collection (computer science)
  8. Wikipedia: Reference counting
  9. Wikipedia: Tracing garbage collection
  10. Encryption Consulting: What is SHA-256?
  11. Wikipedia: Crypto-shredding
  12. GDPR: Right to erasure (right to be forgotten)
Sign in to report a mistake