Key value store system design: object, blob and file storage

In this article

1. Before you start
2. Why interviewers ask this
3. Key-value blob storage from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

A storage design question shows whether you can turn "store a lot of data safely" into a short list of decisions with numbers on each. The usual prompt gives a size range, such as keys up to about 1 KB and values up to about 300 KB, and asks how the design changes as volume grows from millions of records to billions.

A weak answer draws a load balancer and a database box. A strong answer says how a key finds its machine, how the machine finds the bytes, how many copies exist and what a failed disk costs to repair. It then does the arithmetic out loud. This question is reported in interviews at AI labs and large technology companies, often with an artifact or checkpoint store in mind.

Key-value blob storage from first principles

Blob

A blob is a large, opaque chunk of bytes, such as an image, a model checkpoint or a build artifact, that a store keeps and returns whole under a key without looking inside it.

Erasure coding

Erasure coding is a way of protecting data by splitting it into data pieces and adding a few computed parity pieces, so that the original can be rebuilt from any large enough subset of the pieces.

Quorum

A quorum is the minimum number of replicas that must answer a read or acknowledge a write, chosen so that every read set overlaps every write set and the reader sees the latest acknowledged value.

In plain words

A blob store is like a warehouse with a card catalog. The catalog is small. It says which shelf holds each box. The boxes are big and live on the shelves. To find a box, you check the catalog, then walk to one shelf. To survive a fire, you keep copies in other buildings. The analogy breaks in one place.

A real warehouse has one catalog and one manager, while a blob store has to spread both across many machines, and any of them can fail. In one precise sentence, a blob store maps a key to a partition by hashing, maps the key to a disk location through a compact in-memory index, stores the value on several machines as copies or as erasure-coded pieces, and answers reads and writes through a quorum.

Step 1: Split the keys across machines by hash

The first step gives every key one owner by hashing it. If you hash a key and take it modulo the number of machines, adding one machine changes the answer for almost every key. A hash ring avoids that. Machines and keys are both placed on a circle, and a key belongs to the next machine clockwise. Dynamo gives each machine several positions on the ring, which it calls virtual nodes or tokens, so that load spreads evenly and a failed machine's load is dispersed across the rest (DeCandia et al., 2007, section 4.2). The ring is the same idea as consistent hashing in a distributed cache.

When an 11th machine joins 10, modulo hashing moves 91.0% of the keys. A ring moves about 1 in 11 either way: averaged over 200 random placements, a ring with one position per machine moves 8.3% and a ring with 128 positions moves 9.1%, against an ideal of 9.1%.¹ The positions keep the average and make the move predictable: one position per machine ranged from 0.6% to 21.5% (5th to 95th percentile) with every key from one neighbour, while 128 positions ranged from 8.0% to 10.6% with keys from all 10 old machines.¹ What you now know: a key finds its machine by hash, the ring keeps growth cheap, and many positions make the cost steady and shared.

Step 2: Keep the metadata small and apart from the bytes

The second step separates what is looked up from what is stored. A key and a pointer are tiny, and the value may be 300 KB, so the index can live in memory while the bytes live on disk. The Haystack paper describes why this matters. Its earlier design needed several disk operations to read a single photo, because the file system had to find the file's metadata on disk first, and Facebook then built a store that keeps all metadata in main memory and needs at most one disk operation per read (Beaver et al., 2010).

For large files the same split appears as chunks. The Google File System uses 64 MB chunks and a single master that keeps less than 64 bytes of metadata per chunk in memory (Ghemawat et al., 2003). For a petabyte of files that is 16,777,216 chunks and about 1 GiB of index.¹ What you now know: the small index is the part that must be fast, and the big bytes only need to be cheap.

Step 3: Copy or erasure-code the bytes

The third step decides how data survives a disk or machine failure, and it is where the opening number gets its meaning. A replica is one full copy of the data on one machine, and three replicas are the simple choice: with the three replicas of the Google File System, reads can use any copy and a repair is a straight copy.

The Hadoop documentation says the default replication scheme has 200% overhead in storage space, and that a Reed-Solomon (RS) code with 6 data blocks and 3 parity blocks, written RS(6,3), stores a 6-block file in 9 blocks, an overhead of no more than 50% (Apache Hadoop, read 2026-10-24). The price is the repair. To rebuild one lost block, the code reads 6 surviving blocks, so losing a 16 TB node means reading 96 TB over the network to restore 16 TB, six times the traffic of copying.¹ What you now know: erasure coding saves disk and spends network and processor time, and the repair is where the bill arrives.

Step 4: Read and write through a quorum

The fourth step makes the copies agree. With N replicas, a write waits for W acknowledgements and a read asks R replicas, and when R plus W exceeds N, every read set overlaps every write set. Dynamo calls this a quorum-like system and reports that its common (N, R, W) configuration is (3, 2, 2) (DeCandia et al., 2007, section 6). With (3, 2, 2) a read overlaps the last write and one node can be down for either operation.¹ The other end of the dial is consistency itself.

Eventual consistency means that after a write, readers may briefly see an older value, and all copies agree later. Strong read-after-write consistency means that once a write succeeds, every later read returns that new value. Dynamo targets objects usually smaller than 1 MB and accepts eventual consistency, while Amazon S3 announced on 1 December 2020 that it provides strong read-after-write consistency for all applications at no extra cost (Amazon Web Services, December 2020). What you now know: the quorum numbers are how you buy availability or consistency.

1 · Partition2 · Index3 · Protect4 · QuorumReplay

Step-by-step description

1. Hash each key to one owner.
2. Small index in memory, bytes on disk.
3. Copies or erasure-coded pieces.
4. Reads overlap the last write.

• A ring with 128 tokens per node moves a mean of 9.1% of keys when an 11th node joins.
• The index can live in memory while the bytes live on disk.
• RS(6,3) stores 150 TB where three copies store 300 TB.
• A quorum of three, two, two overlaps every read with the last write.

Worked example

One sizing exercise ties the four steps together. Every number below comes from assets/data/blob-store.py.¹ The inputs are illustrative, not a real system: one billion records, an average value of 100 KB (the question allows up to about 300 KB), a worst-case key of 1 KB, 64 bytes of location and version per key, and nodes with 16 TB of usable disk filled to 70%.

The values add up to 100 TB. The key index is separate: 1 billion keys of 1 KB each plus 64 bytes of pointer is about 1.064 TB of metadata, which is far too large for one machine's memory and is the reason the index is partitioned like the data.¹

Two readings matter. First, the capacity gain flattens: RS(6,3) saves 150 TB over three copies,¹ while moving to RS(10,4) saves only another 10 TB and raises the repair read from 96 TB to 160 TB. Second, the code choice sets how many failures a stripe survives (a stripe is one group of data and parity blocks, here 6 plus 3 or 10 plus 4, written across different machines): RS(6,3) tolerates 3 lost blocks and RS(10,4) tolerates 4 (the 3x scheme loses data only if all 3 copies go). Fewer nodes also means fewer racks to spread across, and the Hadoop page notes that RS(6,3) needs at least 9 nodes and 3 racks to keep rack-level tolerance.

Text description of the diagram

• 100 TB of values needs 300 TB with three copies, 150 TB with RS(6,3) and 140 TB with RS(10,4).
• RS(6,3) stores 100 TB of values in 150 TB, an overhead of 50%.

Trade-offs and edge cases

The design trades cost, repair load and speed against each other, and no single scheme wins everywhere. Copies are fast to read and cheap to repair but cost 3 times the data. Erasure codes cost 1.4 to 1.5 times the data (the RS(10,4) and RS(6,3) rows of the worked example),¹ but the Hadoop page says encoding and decoding use extra processor (CPU) time and that most reads and writes of striped files go off-rack (to a machine in a different rack, the shelf of servers that shares a network switch, which is slower than staying in the same rack), so network bandwidth matters.

Practice differs on where each is used: many stores keep recent and small objects as copies and move cold, large objects to a code, and the choice is a policy, not a law. File systems add a limit of their own. The single master of the Google File System keeps all metadata in memory, which is simple and fast, and it bounds the file count by the memory of one machine.

Text description of the diagram

• Modulo hashing moves 91.0% of keys when an 11th node joins; a ring moves a mean of 8.3% with one token per node and 9.1% with 128 tokens per node.
• In 90% of 200 placements, 128 tokens per node moved 8.0% to 10.6% from all 10 old nodes; one token moved 0.6% to 21.5% from one neighbour.

Three edge cases come up in practice. Large uploads must be split: Amazon S3 allows at most 10,000 parts per multipart upload, with parts from 5 MiB to 5 GiB and a maximum object size of 48.8 TiB (Amazon S3 documentation, read 2026-10-24), while a 300 KB value fits in one request.

Concurrent writers to one key need a rule: Dynamo keeps conflicting versions with vector clocks, small lists of (node, counter) pairs, and leaves reconciliation to the application, while a strongly consistent store serializes them. Hot keys defeat hashing, because one key always lands on one partition, so a very popular object is cached or copied more widely. See also concurrency interview questions for the races involved, and Kubernetes interview questions for the platform such a store often runs on.

How to answer it in an interview

Say it in this order: the partitioning, the index, the durability scheme with its cost, the quorum, then the sizing.

Common mistakes

"Hash the key modulo the number of servers."

(Wrong) "Server number is the hash of the key mod N." Adding the 11th server moved 91.0% of the keys in the worked example. (Right) "Use a ring with many tokens per node, which moves about one key in eleven."

"Erasure coding is just cheaper replication."

(Wrong) "RS(6,3) is the same as three copies but smaller." Repairing a 16 TB node reads 96 TB against 16 TB for copies. (Right) "It saves disk and spends repair traffic and processor time."

"Put the value in the same table as the metadata."

(Wrong) "Store the 300 KB value in the row with the key." The index no longer fits in memory and every lookup touches the big bytes. (Right) "Keep a compact index in memory and keep the bytes in a separate store."

"A quorum of two out of three is always strongly consistent."

(Wrong) "R plus W above N means strong consistency." It ensures an overlap, but sloppy quorums, hinted handoff and failed writes can still leave readers with stale or conflicting versions. A sloppy quorum counts the first N healthy machines instead of the N machines that own the key, and hinted handoff means a stand-in machine holds the write with a hint naming the real owner and passes it back when the owner returns (DeCandia et al., 2007, section 4.6); a read can miss the write held by a stand-in. (Right) "A quorum gives a read overlap, and Dynamo shows eventual consistency still needs conflict handling."

Follow-up questions

How do you add hosts without moving too much existing data?

Use a hash ring with many tokens per node. The new host takes small slices from many neighbours, so the 11th host takes close to its fair 1 in 11. Averaged over 200 random placements in the worked example it took 9.1% of the keys with 128 tokens per node, within 8.0% to 10.6% in 90% of placements (7.0% to 11.6% at the extremes) and from all 10 old hosts, while one token per node averaged 8.3% but swung from 0.6% to 21.5% in 90% of placements (0.06% to 36.0% at the extremes) and took everything from one neighbour.

How would you design the storage system as volume grows from millions of records to billions?

Partition the keys and the index together, and size nodes from the arithmetic. At a billion records, the key index alone is about 1.064 TB for 1 KB keys, so it must be partitioned.

How would you design a file storage system similar to S3?

Treat files as objects split into parts, keep object metadata in a partitioned index, and store the parts with copies or erasure codes. S3 documents up to 10,000 parts per upload and a 48.8 TiB maximum object size.

How do you handle two clients creating the same key at the same time?

Either serialize them with a strongly consistent write, or accept both and reconcile later. Dynamo keeps both versions with vector clocks and returns them to the application to merge.

Why not replicate everything three times?

Three copies cost 300 TB for 100 TB of data against 150 TB for RS(6,3). They are simple and cheap to repair, so many designs keep hot data replicated and code the cold data.

Sources

1. Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) — DeCandia et al., Amazon (year only; read 2026-10-24), 1 Jan 2007
2. The Google File System (SOSP 2003) — Ghemawat, Gobioff, Leung, Google (year only; read 2026-10-24), 1 Jan 2003
3. Finding a needle in Haystack: Facebook's photo storage (OSDI 2010) — Beaver et al., USENIX (year only; read 2026-10-24), 1 Jan 2010
4. Amazon S3 now delivers strong read-after-write consistency automatically for all applications — Amazon Web Services, 1 Dec 2020
5. Amazon S3 multipart upload limits — Amazon Web Services documentation (date = read date), 24 Oct 2026
6. HDFS Erasure Coding — Apache Hadoop documentation (date = read date), 24 Oct 2026