Design a distributed object store

01Separate an object’s name from its bytes

An object store accepts a named sequence of bytes and later returns those bytes. Unlike a filesystem, it does not need to support in-place edits to arbitrary byte offsets. Our product stores tenant-owned videos, exports and backups. Clients create or replace a whole object, read a range, list names and delete a name. Every successful replacement creates an immutable version.

Ask whether clients replace whole objects or need filesystem-style edits, whether reads must immediately see a completed replacement, and which failure must an acknowledged upload survive. This walkthrough chooses whole immutable versions, authoritative current-key reads and one storage-node failure within a region.

Use tenant T7 uploading a 2 GiB video as the running example. Its logical key is videos/launch.mp4; version V5 identifies one exact byte sequence under that key. Keeping those identities separate lets a download finish on V4 while a new upload prepares V5. A key is an address, while a version is a particular saved object.

The complete flow is authorize upload → store temporary bytes → verify them → publish a version → authorize download → read that version. Publication means making a completed object visible under its logical name. Upload progress alone does not make an object readable. This distinction is the basis of retries, concurrent replacements and cleanup throughout the design.

02Functional requirements

Agree on what the service must do before choosing its components.

1. Create and replace objects. Support PUT of tenant-owned bytes under a logical key, creating a new immutable version on each successful replacement.
2. Read object data and metadata. Support GET, HEAD and ranged GET, plus reads naming an exact version. An existing version-specific reader may finish on the version it selected.
3. Resume large uploads. Support multipart sessions, part inspection/retry, explicit completion and abort. Partial bytes must remain invisible as a completed object.
4. List and delete names. Support DELETE and paginated key listing with a stable ordering and cursor. Listing is not a snapshot across concurrent changes unless an additional snapshot feature is requested. Filesystem-style in-place edits and cross-region disaster recovery are outside the initial scope.

03Non-functional requirements

Use these hypothetical requirements for the worked interview. Confirm the assumptions with the interviewer; the numerical targets require testing and are not measured results. For latency, p95 and p99 mean that 95% and 99% of measured delays, respectively, are no greater than the reported value.

1. Workload. Assume ten million new objects/day averaging 10 MB and one billion reads/day averaging 4 MB returned. The sizing exercise retains thirty days; versions, temporary uploads and peaks require extra capacity.
2. Visibility and integrity. After completion succeeds, a new lookup of the logical key must return the new version. Each download returns one complete immutable version with verified length/checksum, never a mixture of versions. Concurrent conditional replacements must detect a conflict.
3. Regional durability. An acknowledged upload must survive one storage-node failure, and acknowledged metadata must survive one metadata-node failure. Required durable copies must exist before success; background replication alone does not establish this promise. Region loss needs a separately designed recovery point, recovery time and cost.
4. Latency and transfer rate. Target metadata-read p95 below 100 ms and read time-to-first-byte p95 below 250 ms on regional test paths. For large transfers, target at least 50 MiB/s per transfer when the client and network can sustain it. Test under admitted load; a 2 GiB video cannot share a tiny-object completion-latency target.
5. Bounded uploads and quotas. For this exercise, accept objects up to 64 GiB and expire incomplete uploads after 24 hours. Start with a default 1 TiB logical-byte quota, including temporary and retained versions, and ten active upload sessions per tenant; larger tiers require explicit configuration. With 64 MiB parts the largest object uses 1,024 parts. Reclaim only unreferenced expired parts.
6. Tenant access. Authorize metadata lookup, upload capabilities and byte delivery. A tenant prefix only names data; it does not authorize access. Short-lived download URLs are bearer grants until expiry, so immediate revocation would require an online enforcement path.

04Make one server publish only complete objects

Start with an API, a metadata database and a filesystem on one storage server. A client requests an upload session U31 for T7’s key. The API checks permission and returns an upload identifier. The server writes incoming bytes to a temporary file named by that session, computes a checksum and verifies the declared length. A checksum detects accidental corruption; it does not establish who is allowed to upload.

After the file is complete and durably flushed, establish its immutable version name durably as well; a filesystem rename may require flushing the containing directory before publication. In a metadata transaction, create V5 and change the key’s current-version pointer to V5. Only then return success. A reader first authorizes access, resolves the current version and reads that exact file. It never streams a partially written temporary file.

If the server crashes before metadata publication, an unreferenced file may remain for later cleanup. If it crashes afterward but before replying, retrying completion for U31 returns the recorded V5 result. This ordering avoids a published pointer to bytes that were never durably stored. The baseline is complete but has one storage failure domain and limited disk/network capacity.

05Size stored bytes separately from requests

Assume ten million new objects per day with an average size of 10 MB. That is approximately 100 TB of new logical data per day. Retaining thirty days gives 3 PB before versions, temporary uploads and overhead. Three complete replicas require about 9 PB. Use consistent decimal units for this estimate; the running 2 GiB multipart example uses binary units deliberately.

One billion reads per day at an average returned range of 4 MB gives 4 PB/day of output, about 46.3 GB/s on average. Peak demand and popular-object skew require additional capacity. Caching immutable versions can save origin traffic, but an average cache hit rate can hide a single very large hot download.

For the example video, 64 MiB parts produce 32 parts. Four parallel transfers can improve throughput until the client, gateway or storage network saturates. More parallelism then adds connections and retry pressure without speeding the disk.

Metadata entries are much smaller than payloads and follow different access patterns. Scale the metadata database for key lookups and publication transactions; scale storage nodes for bytes, capacity and repair bandwidth. Do not route all large payloads through a single database or control server.

06Give upload sessions and versions different APIs

Create the upload session

POST /uploads

Example request body for the 2 GiB video

{
  "tenant": "T7",
  "key": "videos/launch.mp4",
  "expectedCurrentVersion": "V4",
  "totalSizeBytes": 2147483648
}

The request may also include a content checksum. The API validates the 64 GiB size ceiling, reserves the declared logical bytes against the tenant quota, checks the ten-active-upload limit and creates U31 with a 24-hour expiry. Account for concurrent reservations atomically so several uploads cannot each spend the same free quota.

Continue or read an upload

Metadata records

The manifest lists the parts and their order so a reader can reconstruct the video without storing another complete copy.

Use conditional replacement when the caller wants to avoid overwriting another edit. If U31 expects V4 but another upload already published V6, reject U31’s completion with a conflict. An unconditional replacement may instead use an explicit last-committed-writer policy.

Returned object metadata

Do not teach clients that an ETag must equal the whole object’s MD5 checksum, especially for multipart objects.

07Make completion a small metadata operation

Each part is stored under an immutable identity. A retry of the same part can reuse verified identical bytes; a replacement creates another part generation instead of silently overwriting bytes that a manifest may already reference. The upload record names the exact part generation that completion may include. Before accepting an additional replacement generation, atomically reserve its extra bytes against the same tenant quota; the original declared-size reservation does not cover unlimited superseded parts. Reusing the same verified immutable bytes needs no additional charge. Keep superseded generations charged until safe cleanup reclaims them.

Complete U31 in this order

1. Validate the session. Check ownership, expiry, ordered part numbers, lengths and checksums against the reserved total size.
2. Freeze exact part identities. Select the generations that the published object will reference.
3. Verify durable bytes. Check that those parts meet the required durability policy.
4. Publish atomically. In one metadata transaction, mark the upload completed, create V5’s immutable manifest, conditionally change the key pointer and save the completion result.
5. Return the saved result. Retrying completion returns V5.

If part 7 is still missing, completion fails while U31 remains recoverable. The client can inspect uploaded parts and send the missing one. If another completion already succeeded, the response identifies that success rather than creating a second version accidentally.

This mechanism avoids copying 2 GiB inside the publication transaction. The transaction changes a small manifest and pointer while the large bytes already exist. It also explains why upload completion is an explicit operation: the service cannot infer that an interrupted connection meant the client intended a complete video.

08Replicate bytes and keep metadata authoritative

Replace the one disk with storage nodes across independent failure domains. Choose three copies across independent storage failure domains and require all three to be durable before publication. If one required write is unavailable, wait or fail that completion without publishing it. Existing reads can use surviving copies. Three processes on the same disk do not provide this separation.

Use a synchronously replicated metadata authority whose acknowledged commits survive one metadata-node loss. Its conditional transactions prevent two concurrent replacements from both winning an expected-version check. Large transfers can go directly to selected storage endpoints using scoped capabilities. The control service still authorizes sessions and publication; it need not proxy every byte.

Serve public immutable objects through a CDN. Private objects need a cache and delivery policy that preserves authorization; do not accidentally turn a private origin into an anonymously readable cache. Cache identity includes the immutable version and requested range where appropriate.

Background workers check replica health and repair missing copies. Reserve bandwidth for repair during a failure, when serving demand may also rise. Erasure coding is an optional later storage optimization: it uses data and parity fragments to lower storage overhead at the cost of more complex repair and small-read behavior. Replication remains the final interview design.

09Trace a download while a replacement commits

A reader asks for T7’s current video. The API authenticates the actor, checks read permission and resolves V4. It returns or internally retains V4’s immutable manifest. The storage path reads the requested byte range from its listed parts, using another verified replica if a copy is unavailable or corrupt.

Meanwhile U31 publishes V5. A new current-key lookup sees V5, but the existing reader continues with V4. Mixing the first half of V4 and the second half of V5 would produce an object that nobody uploaded. Binding the download to a version prevents that error without blocking replacement for the entire transfer.

A short-lived signed download URL is a bearer capability. Anyone who possesses it may use its allowed scope until expiry, so issue it only after authorization and keep its lifetime appropriate. Immediate revocation requires an authenticated serving gateway or another online enforcement path; a signature alone cannot retract bytes already delivered.

Record whether a failed read is missing metadata, unavailable replicas or corrupt bytes. Those outcomes lead to different recovery actions. A published version whose replicas are temporarily unreachable should not be silently reported as an object that never existed.

10Recover uploads and delete without damaging readers

An upload that never completes consumes temporary space. Expiry and an explicit abort operation let cleanup reclaim its unused parts. Before deleting a part, cleanup checks whether an upload or retained version still needs it. An old upload session does not make a completed version’s bytes disposable.

DELETE first changes the key’s visible metadata according to the retention policy. Version retention may preserve older bytes for recovery, legal policy or active downloads. Apply these cleanup and accounting rules:

Start with conservative retention and a grace period; an exact reference-management protocol is an advanced implementation topic.

After a lost completion response, U31’s durable status answers whether V5 was published. After a node failure, reads use another replica and repair recreates the missing copy. After a metadata outage, reject publication rather than acknowledging an update that cannot be recorded safely.

Keep checksums for corruption detection and independently verify restoration from backups. Replication copies accidental deletion and application mistakes as readily as legitimate updates; retention and backups address different failure modes. Test the complete metadata-plus-byte restore, because restoring only filenames does not reconstruct their contents.

11Observe the promises at their actual boundaries

Measure upload throughput, completion latency, metadata conflicts, time to first byte, range-read failures, replica health, repair backlog and temporary-storage age. Track storage growth by tenant and data class. A service can return fast metadata responses while repair falls behind and durability risk grows.

Enforce byte and request quotas, maximum part counts and concurrency limits. Upload capabilities should bind tenant, session, destination, expiry and permitted operation. Protect storage nodes from arbitrary paths supplied by callers. Verify content length and checksums rather than trusting client declarations as evidence that bytes arrived intact.

Exercise two completions expecting V4, a lost completion reply, a missing part, a corrupt replica, a read spanning a replacement and deletion during a long read. The expected outcomes should be explicit: one conditional winner, stable replay result, recoverable upload, replica fallback and one unchanged download version.

Close the design by identifying its limits. It provides whole-version publication and replicated regional durability, not cross-region survival, a POSIX filesystem or instantaneous revocation of bearer URLs. Add those features only after the interviewer changes the contract and you can explain the new cost.

12Check the design against its requirements

Before closing, check the final design against the agreed requirements. FR means functional requirement and NFR means non-functional requirement; the numbers refer to the lists above. These are proposed validation checks, not test results.

13Rapid revision

Rehearse the numbered functional requirements and non-functional targets first. Use this table to recall the mechanisms, then close with the requirements check above.

Remember: Durable bytes → atomic publication → saved reply.

A useful close is: “I keep names and immutable versions separate. Uploads prepare durable bytes before a small transaction publishes them, and readers bind to one version. Replication handles the selected node failure; conservative lifecycle cleanup and explicit access grants make the limits visible.”

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.