The whole course ▾

System Design · Mock interview 3 of 20

Design a key-value store like DynamoDB

Updated 22 Oct 2026 · By Akshay, software engineer, India · 9 min read

Design a key-value store like DynamoDB.

Try it first

Before you read the interview, answer the question yourself. Give yourself 10 minutes: say your design out loud, or sketch it on paper. What would you ask? Which numbers matter? Which boxes, and what's the hard part? Then read on, and score yourself with the feedback at the end.

Got a doubt? Ask in the comments under the video.Subscribe

Requirements

Requirements
Clarifying questions
->
Operations? -> get, put, delete by key
->
Values? -> Small, under 1 MB
->
Scale? -> 100 TB, 1M requests/s
->
Consistency? -> Tunable; available first
Functional requirements
put(key, value)
get(key) -> value
delete(key)
Consistency chosen per request
Non-functional requirements
->
100 TB, and growing
->
1M requests a second at peak
->
Single-digit milliseconds
->
Always writable: no single point of failure
->
Survives machines and racks failing
Out of scope
Queries by value, or scans
Transactions across keys
Secondary indexes
interviewer
Hello again. Ready to start?
candidate
Ready. I'll think out loud and draw as I go.
interviewer
Today I'd like you to design a distributed key-value store. Something like DynamoDB.
candidate
Okay. A key goes in, a value comes out. That sounds small, so I'm guessing the hard parts are scale, and machines failing. Let me ask a few questions first.
interviewer
Go ahead.
candidate
Which operations do we need?
interviewer
Get, put and delete, by key.
candidate
How big are the values?
interviewer
Small. Under a megabyte.
candidate
And the scale?
interviewer
About a hundred terabytes, and up to a million requests a second at peak.
candidate
What about consistency?
interviewer
Tunable per request. But by default it must stay available, even if a read is sometimes a moment old.
candidate
Okay. Availability first. That's going to decide a lot.
candidate
So what it does is short. Put a key and a value. Get the value back by key. Delete a key. And a consistency level chosen per request, from fast and maybe stale, to slower and always the latest.
interviewer
Any limit on the key size?
candidate
I'll assume keys are short, a few hundred bytes at most.
candidate
How well it does it is the real problem. A hundred terabytes, and growing. A million requests a second at peak. Answers in single-digit milliseconds. Always writable, so no single machine whose death stops writes. And it has to survive machines, and whole racks of machines, failing.
candidate
I'll leave out queries by value, and scans across keys. Transactions across several keys. And secondary indexes. Does that match what you had in mind?
interviewer
Yes. And one more thing: assume machines fail every single day.
candidate
Got it.

Estimation

Estimation
Back of the envelope
100 TB × 3 copies = 300 TB
÷ 2 TB usable per node ~ 150 nodes
1M requests/s ÷ 150 ~ 7,000/s each
100 TB ÷ 1 KB average ~ 100 billion keys
WHAT THE NUMBERS DECIDE
150machines:thedata
mustbepartitioned,and
atthatsizesomethingis
alwaysfailing.
candidate
Let me size it.
interviewer
Roughly how many machines is this?
candidate
I'll start from the data, because copies multiply it.
candidate
A hundred terabytes, kept as three copies for safety, is three hundred terabytes. At about two usable terabytes a machine, that's around a hundred and fifty nodes. A million requests a second across a hundred and fifty nodes is about seven thousand each, which one machine handles comfortably. And with values around a kilobyte, that's about a hundred billion keys.
interviewer
Fine. What does that tell you?
candidate
Two things. A hundred and fifty machines means the data must be partitioned, so I need a way to find a key's machine. And at that size, failure isn't an exception. It's daily. So the design has to keep working with machines down.
interviewer
Agreed. Those are the two things I want to see.

API and data

API and data
Commit log
every write, appended
Memtable
recent writes,
sorted
SSTables
sorted files on disk
then
1
flush when
full
2
Endpoints
1
PUT /kv/{key} -> stored
2
GET /kv/{key} -> value + version
3
DELETE /kv/{key} -> a tombstone
4
Header: consistency = one or quorum
READS STAY FAST
Memtablefirst,thenthe
newestfiles;aBloom
filterskipsfilesthat
can'tholdthekey.
candidate
Next, the API, and what one machine stores.
interviewer
What does the API look like?
candidate
As small as the requirements.
candidate
PUT slash kv slash the key stores a value. GET returns the value, plus a small version tag that comes back with the next put. I'll need that later. DELETE doesn't erase anything straight away. It writes a tombstone, a marker that says deleted, so every copy learns about it. And a header picks the consistency level per request: one copy, or a quorum.
interviewer
Why the tombstone?
candidate
If I just erased it, a copy that missed the delete could bring the old value back.
candidate
Inside one machine, it's a sorted map from key to value and version. It takes heavy writes, so I'd use an LSM tree. Every write is first appended to a commit log, so a crash loses nothing. Then it goes into the memtable, a sorted map in memory. When that fills up, it's written to disk in one go as SSTables, sorted files that never change, merged in the background.
interviewer
Why not a B-tree, like most databases?
candidate
A B-tree updates pages in place, which means random writes. An LSM tree turns every write into an append, which disks handle much faster.
interviewer
And reads?
candidate
Reads check the memtable first, then the newest files. A small Bloom filter per file says definitely not here for most of them, so a typical read touches one or two files.
interviewer
Okay.

High-level design

High-level design
Client
Request
router
Coordinator
first node
clockwise
Second
copy
next
clockwise
Third copy
one more
put(k, v)
1
hash(k)
2
copy
3
copy
3
Hash ring, virtual nodes
Reading a key
1
Hash the key: same three nodes
2
Ask R = 2 of the 3 copies
3
Return the newest version
4
Fix a stale copy on the way
TWO RISKS
Nosinglemachinecan
stopwrites.Butcopies
candisagree.
candidate
Now the overall design.
interviewer
Walk me through a put, and a get.
candidate
First, where a key lives, because everything follows from that. And there's no master: any node can coordinate its own keys.
candidate
I'd spread the keys with a hash ring and virtual nodes. A client sends a put to a request router, which hashes the key and finds the first node clockwise. That node is the key's coordinator. It stores the value, then sends it to the next two nodes clockwise, the second copy and the third copy. So N is three. As soon as two of the three confirm, the coordinator answers: done. W is two.
interviewer
Why virtual nodes?
candidate
Each machine owns many small slices of the ring. When one joins or leaves, its load spreads across everyone, instead of landing on one neighbour.
candidate
A get finds the same three nodes the same way. The coordinator asks two of the three copies, so R is two. Two plus two is more than three, so at least one answer has the latest write, and the coordinator returns the newest version. If a copy answered with an older version, the coordinator fixes it on the way out. That's read repair.
interviewer
And when the caller only wants speed?
candidate
Then the header says one copy. Faster, but maybe stale.
interviewer
Is there any single machine whose death stops writes?
candidate
No. Any node can coordinate, and every key has three homes. The real risk is different: because I chose availability, copies will sometimes disagree.
interviewer
Then let's go there.

Deep dive: conflicting writes

Deep dive: conflicting writes
Last write wins
Each write carries a timestamp
The highest timestamp wins
Clock drift loses writes silently
Versions: keep both
A version counter per node
Spots truly concurrent writes
The reader merges them
THE CHOICE
Lastwritewinsby
default;versionswherea
lostwritecostsmoney,
likeacart.
High-level design
Client
Request
router
Coordinator
first node
clockwise
Second
copy
next
clockwise
Third copy
one more
put(k, v)
1
hash(k)
2
copy
3
copy
3
Hash ring, virtual nodes
2 versions
merges, then puts
Reading a key
1
Hash the key: same three nodes
2
Ask R = 2 of the 3 copies
3
Return the newest version
4
Fix a stale copy on the way
TWO RISKS
Nosinglemachinecan
stopwrites.Butcopies
candisagree.
interviewer
Let's start with that risk.
interviewer
Two clients write the same key at the same moment, and the copies get the writes in different orders. Which value wins?
candidate
I need a rule to settle it. Let me weigh two options.
candidate
Option one: last write wins. Every write carries a timestamp, and each copy keeps the highest. Simple, and Cassandra does this. But clocks drift, so a write can lose to an older one stamped by a faster clock, and nobody is told. Option two: versions. Each value carries a small counter per node, a vector clock, which can tell this came after that, from these happened at the same time. When two writes truly conflict, the store keeps both, and the next reader merges them.
candidate
I'd choose per table. Last write wins for most data: it's simple, and losing an update to a profile photo is acceptable. Versions where a lost write costs money, like a shopping cart. Both carts are kept, and the merge is the union of the two. At worst, a deleted item comes back, which is better than losing one.
interviewer
Show me how a client sees that.
candidate
A get now returns both versions, each with its version tag. The client merges them and puts the result back with both tags attached. That tells the store the new value replaces both, and the conflict is gone. That's what the version tag in the GET response was for.
interviewer
What if the client never merges?
candidate
Then both versions stay, and the next reader sees them again. Nothing is lost. It just isn't tidy yet.
interviewer
Why not just synchronise the clocks?
candidate
You can get them close, within milliseconds, but never exact, and two writes a millisecond apart still need a rule. Google's Spanner bounds clock error with GPS and atomic clocks, and waits out the uncertainty on every commit. That's a different, and much more expensive, design. For us, versions catch what clocks can't.
interviewer
Fair.

Deep dive: failures

Deep dive: failures
Noticing: gossip
1
Every second, ping a few random nodes
2
Swap what each knows about everyone
3
News reaches all 150 in seconds
4
No central monitor to fail
THE TRADE-OFF
Hintedhandoffkeeps
writesalwayson;reads
canbestaleuntilthe
hintisdelivered.
High-level design
Client
Request
router
Coordinator
first node
clockwise
Second
copy
next
clockwise
Third copy
one more
put(k, v)
1
hash(k)
2
copy
3
copy
3
Hash ring, virtual nodes
2 versions
merges, then puts
Stand-in
node
keeps a hint
hinted
write
hand back
later
Reading a key
1
Hash the key: same three nodes
2
Ask R = 2 of the 3 copies
3
Return the newest version
4
Fix a stale copy on the way
TWO RISKS
Nosinglemachinecan
stopwrites.Butcopies
candisagree.
interviewer
Now, failures.
interviewer
A node dies. How does the cluster notice, and what happens to writes meant for it?
candidate
Two parts: noticing, then carrying on.
candidate
Noticing uses gossip, the way rumours spread. Every second, each node pings a few random others, and they swap what they know about everyone: who's alive, and who stopped answering. The news reaches all hundred and fifty nodes within a few seconds. And there's no central monitor that could fail itself.
interviewer
When is a node declared dead?
candidate
When enough nodes hear nothing from it for a while, it's marked down. Down, not removed. A node that's quiet for a minute is usually just rebooting.
candidate
Now carrying on. Say the third copy dies. A write for that key wants three copies, but only two of its homes are up. Instead of failing, the coordinator writes the third copy to the next healthy node on the ring, a stand-in node, with a hint: this belongs to the third copy. When the dead node comes back, the stand-in hands the data back. That's hinted handoff.
interviewer
What if the stand-in dies too?
candidate
Then that hint is lost. But two copies still have the write, and the background repair catches the third one up later.
interviewer
What does that cost you?
candidate
Writes stay always on, which is what we promised. But until the hint is delivered, a read might be stale. And for copies that drift apart over days, nodes compare their data in the background with Merkle trees, hashes of key ranges, and only exchange the ranges that differ.
interviewer
What if a whole rack loses power? Twenty machines at once.
candidate
If all three copies of a key were in that rack, the key would be gone until the power comes back. So placement has to be rack-aware: when I walk clockwise to pick a key's three homes, I skip nodes in a rack I've already used. Better still, spread them across three zones. Then no rack, and no zone, holds every copy of anything.
interviewer
Good.

Wrap-up

Wrap-up
Next steps
1
Hot keys: cache, or split the key
2
Many regions
3
Tune merging: disk versus read speed
4
Watch p99, hint backlog, disk
5
Backups: snapshot the SSTables
INTERVIEWER'S FEEDBACK
Strong:aringwithN,RandWsaid
outloud,aclearconflictrule,failure
treatedasnormal.Nexttime:raise
hotkeysearlier.Verdict:stronghire.
interviewer
We're close to time.
interviewer
What would you improve with more time?
candidate
Let me name the weak spots, each with a fix.
candidate
First, hot keys. One viral key can melt its three nodes, so I'd cache it in front, or split it into several keys. Second, many regions, for users around the world, and to survive a whole region going down. Third, tune the background merging of SSTables, which trades disk work against read speed. Fourth, I'd watch the ninety-ninth percentile latency, the backlog of undelivered hints, and disk space. And fifth, backups: SSTables never change once written, so a snapshot is just a list of files, copied to object storage.
interviewer
Which one worries you most?
candidate
Hot keys. They hurt users first, and fast.
interviewer
Okay, let's stop there. Really nice. You partitioned with a ring, you said N, R and W out loud with the reason behind them, you had a clear rule for conflicts, and you treated failure as a normal day. If I'm picky: hot keys only came up at the end, and they deserve a word earlier. I'd say a strong hire.
candidate
Thank you. I'll remember the hot keys.
Interviewer's feedback

Strong: a ring with N, R and W said out loud, a clear conflict rule, failure treated as normal. Next time: raise hot keys earlier. Verdict: strong hire.

Score yourself

Interviewers score these seven things. Give your own attempt a tick for each one you did.

  • Asks before drawing. Agrees what the system does, and how well: scale, speed, consistency.
  • Turns users into requests a second and bytes a day, and says what the numbers decide.
  • A small, clear contract, and a data model that fits how the data is read.
  • A working path end to end before any detail. Every box has a reason.
  • Picks the hard parts, compares two options, and chooses one with a trade-off said out loud.
  • What breaks, what happens then, and how users notice. Retries, duplicates, limits.
  • Thinks out loud, checks in with the interviewer, and takes a hint without losing the thread.

0 of 7

Your progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.