Design a Key-Value Store: A Dynamo-Style Guide

It runs out of write capacity. Carts are written on every click, and one database server can only take so many writes a second.

Picture a common setup. An online marketplace hosts thousands of small vendors' shops, and it keeps every buyer's cart and login session in one PostgreSQL database. A normal evening brings about 3,000 cart writes a second. The setup is made up, but the problem is real.

Then a festival sale arrives and traffic jumps to 18,000 cart writes a second. The single database falls behind. For 40 minutes, buyers cannot add anything to a cart.

Carts and sessions rarely need joins or reports. They need fast reads and writes by one id, on many machines, with no single server whose crash stops everything. Key-value store design is the work of building a store for exactly that.

This guide designs one in the style of Dynamo, the store Amazon described in a 2007 paper. Amazon's shopping cart service was one of the services built on it.

A key-value store is a database that saves each value under a unique key and gives it back when you ask with that key. A plain one, like the store this guide designs, does not look inside the value.

Think of the shoe stand outside a busy temple. You hand over your chappals and get a numbered token. Later you show the token and get the same chappals back. The attendant never asks what brand they are.

Key. The key is the name you store data under, like the token number. In the marketplace a cart key looks like cart:v42:b9001, which means vendor 42 and buyer 9001.

Value. The value is the data itself, kept as plain bytes. A cart value is a small JSON document listing items and quantities, about 2 KB.

The whole interface is just three calls:

• put(key, value) saves a value, replacing any old one.
• get(key) returns the value, or nothing if the key is unknown.
• delete(key) removes the key and its value.

Many stores also support a time to live, or TTL: an expiry time after which a key disappears on its own. The marketplace gives every session a TTL of 7 days, so old logins clean themselves up.

Where the picture breaks: the shoe stand keeps one pair in one place. A real store keeps several copies of each value on different machines, and those copies can briefly disagree.

You fix the requirements first. Then you answer four questions in order: where each key lives, how many copies exist, how copies agree, and how the store heals.

The requirements fit on one page. Most are non-functional requirements, the qualities a system must have besides its features.

• Always writable: a buyer can add to a cart even while a server is down.
• Fast: 99 out of 100 requests finish within 20 milliseconds.
• Grows by adding servers, without moving most of the data around.
• No single boss server whose crash stops everything.
• Values are small, under 10 KB, and are always read by key.

For a real yardstick, the Dynamo paper says a typical target for services using it was 99.9 percent of reads and writes within 300 milliseconds.

Next comes back-of-the-envelope maths, quick sums that size the system. Say the marketplace holds 3 crore (30 million) carts and sessions at 2 KB each. That is 60 GB of data. With 3 copies of everything, the cluster stores 180 GB.

Storage is the easy part. At a peak of 18,000 writes a second, with 3 copies each, the cluster handles 54,000 replica writes a second. Spread over 6 servers to start, that is about 9,000 writes a second per server.

In this overview, notice that the shop app can reach any node, but the request ends up with one of the key's owners.

A coordinator is the node that runs one request from start to finish. In Dynamo it is usually the first owner of the key. Every node runs the same code, so there is no special leader to lose.

It uses consistent hashing: each key is hashed to a point on a ring of numbers, and the first servers found going clockwise from that point own the key.

A hash function turns any text into a big number that looks random. The same key always gives the same number. Now bend the range of numbers into a circle, so the largest wraps back to zero.

The naive first try is simpler, and it is wrong for this job: hash the key and take the remainder after dividing by the server count. In our run on 100,000 keys, going from 5 to 6 servers that way moved 83.1 percent of them.

On a ring, each server also gets a spot. To find a key's owner, hash the key and walk clockwise to the next server. Adding a server only takes keys from its neighbours. In the same run, the sixth server became first owner of 16.4 percent of keys and one of the three owners of 45.6 percent. Every copy that moved went to the new server.

One spot per server spreads data unevenly, because the gaps between spots differ. So each physical server takes many spots, called virtual nodes. In Dynamo, they spread a failed node's load over the others, and a bigger server can take more spots.

Here is a tiny version to test the idea. position() hashes text to a number, build_ring() gives each server eight spots, and replicas() walks clockwise to collect three different owners.

import bisect, hashlib

def position(text):
    return int(hashlib.md5(text.encode()).hexdigest(), 16) % 2**32

def build_ring(nodes, vnodes=8):
    return sorted((position(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))

def replicas(ring, key, n=3):
    start = bisect.bisect(ring, (position(key),))
    chosen = []
    for k in range(len(ring)):
        node = ring[(start + k) % len(ring)][1]
        if node not in chosen:
            chosen.append(node)
        if len(chosen) == n:
            break
    return chosen

ring = build_ring(["node-1", "node-2", "node-3", "node-4", "node-5"])
print(replicas(ring, "cart:v42:b9001"))

We ran it on Python 3.13. It prints ['node-4', 'node-3', 'node-1'], the same list every time, because MD5 gives the same number for the same key on every machine.

What just happened? The bisect call found the first spot clockwise from the key with one fast search of the sorted list. The check node not in chosen skipped extra spots of a server already picked, so three copies landed on three machines.

Dynamo calls this list of owners the preference list. It keeps the list longer than the number of copies, so spare servers are ready when an owner fails.

Dynamo itself applies MD5 to each key to get a 128-bit position. MD5 here only spreads keys and plays no security role. Cassandra 5.0.9 is the latest stable release as of 19 October 2026. The cassandra.yaml it ships with picks a different hash function, Murmur3, through its Murmur3Partitioner setting.

It writes every key to N servers, usually three, picked by walking clockwise on the ring. If one server dies, two copies are still there.

N is the replication factor, the number of copies of each key. Replication comes in two broad styles. In leader-based replication one server orders the writes; in leaderless replication several copies accept them.

Dynamo is leaderless for writes: any of a key's top N owners may coordinate one. That keeps writes flowing when servers fail. The cost is that two owners can accept different writes to the same key at once.

This is the availability side of the CAP theorem. CAP says that when messages between servers can be lost, no system can both answer every request and act like one up-to-date copy. Dynamo chose to answer.

N is the number of copies, W is how many copies must confirm a write, and R is how many must answer a read. If R plus W is more than N, every possible read group shares at least one server with every write group.

That overlap is the whole trick. With N of 3, W of 2 and R of 2, the 2 servers that answer a read always include one of the 2 that confirmed the write. You can check the rule by brute force instead of trusting it:

from itertools import combinations

def always_overlap(n, w, r):
    owners = range(n)
    return all(set(ws) & set(rs)
               for ws in combinations(owners, w)
               for rs in combinations(owners, r))

for w, r in [(3, 1), (2, 2), (1, 3), (1, 1), (2, 1)]:
    print(f"N=3 W={w} R={r}: always overlap = {always_overlap(3, w, r)}")

It prints True for W 3 R 1, W 2 R 2 and W 1 R 3, and False for W 1 R 1 and W 2 R 1. Those are exactly the rows where R plus W is more than 3. The same check matched the rule for every N up to 7.

The Dynamo paper says the common setting among its services was N 3, R 2 and W 2. Cassandra's consistency levels, its name for these R and W choices, are a version of the same idea. Its documentation says writes are always sent to all replicas, whatever the level, and the level only sets how many replies it waits for.

Follow one cart write with N of 3 and W of 2. At the question box, notice that the coordinator does not wait for the slowest copy.

R and W trade read speed, write speed and freshness against each other. The table shows the main choices when N is 3 and the owners stay fixed, which is called a strict quorum.

The marketplace picks W 2 and R 2 for carts, because a lost cart item means a lost sale. For sessions, a stale read only means one extra login, so W 1 and R 1 is enough there.

The store either keeps both versions or picks one by a fixed rule, and the copies agree later. Dynamo can keep both and let the application merge them, which is what its cart service did. Cassandra keeps the write with the newest timestamp.

In the marketplace, a buyer has the same shop open on a phone and a laptop. A brief network problem sends the two devices to different coordinators.

1. 1

   One cart, one version

   The cart holds 2 plates of poha. Its version stamp is A:1, meaning node A has handled one change.

2. 2

   The phone adds jalebi

   Node A coordinates this write and bumps its own counter. The stamp becomes A:2.

3. 3

   The laptop adds sev

   The laptop cannot reach node A, so node C coordinates. It starts from the A:1 version, and the stamp becomes A:1, C:1.

4. 4

   Both versions meet

   Neither stamp has seen every change in the other. The store keeps both, called siblings, and returns both on the next read.

5. 5

   The app merges

   The cart code takes every item from both: poha, jalebi and sev. It writes the merged cart back with a stamp that covers both versions.

That version stamp is a vector clock: a list of node and counter pairs, one pair for each node that changed the value. One version replaces another only if every counter in it is at least as high.

def descends(a, b):
    # True if clock a has seen every change that clock b has seen
    return all(a.get(node, 0) >= count for node, count in b.items())

def compare(a, b):
    if descends(a, b) and descends(b, a):
        return "same version"
    if descends(a, b):
        return "a is newer, drop b"
    if descends(b, a):
        return "b is newer, drop a"
    return "conflict, keep both as siblings"

phone = {"A": 2}
laptop = {"A": 1, "C": 1}
print(compare(phone, laptop))

It prints conflict, keep both as siblings. The descends function is the core rule, and a node missing from a clock counts as zero.

What just happened? The phone clock has no C, so it has not seen the laptop's change. The laptop clock has A at only 1, so it has not seen the phone's change either. A merged clock such as A:3, C:1 descends from both, so it replaces both.

Merging carts by taking every item has a known side effect. The Dynamo paper says an add to cart is never lost, but deleted items can resurface. A buyer may remove the sev and see it come back, so the marketplace shows the full cart before payment.

Last write wins, or LWW, is the simpler rule. Each write carries a timestamp, and the newest one survives. Some Dynamo services used it too. Cassandra works this way. Its documentation says its correctness depends on node clocks, so run a time sync service such as NTP.

The cost of LWW is silent loss. With the phone and laptop writes, one of the two changes would simply vanish. For sessions, that is acceptable. For carts, siblings are safer.

How often do conflicts happen? The Dynamo paper reports that over 24 hours, 99.94 percent of shopping cart requests saw exactly one version. Conflicts are rare, but your code must still handle every one of them.

It sends writes to the next healthy server with a note to hand them back later, and it repairs differences in the background. Dynamo calls these ideas sloppy quorum, hinted handoff and anti-entropy.

Hinted handoff for short failures

With a sloppy quorum, a write goes to the first N healthy servers in the preference list, not strictly the first N on the ring. If owner 3 is down, the next server takes the write along with a hint that names owner 3.

Back at the temple, picture the attendant for rack 7 away on a tea break. The rack 8 attendant keeps your chappals on a side rail with a slip saying rack 7. When the rack 7 attendant returns, the chappals go back where they belong.

The diagram follows one write while node 3 is down. Notice the path back to node 3 at the end.

Hints are a best effort, not a promise. Cassandra's documentation calls hinted handoff and read repair best effort too. If a server stays down too long, or the holder of the hints fails, copies stay different until a repair runs.

Cassandra 5.0.9's shipped config stops creating new hints for a node once it has been down for max_hint_window, 3 hours. After that, the missed writes come back only through read repair of keys that get read, or a full repair.

Read repair is the second safety net. During a read, if one copy answers with an older version, the coordinator writes the newer version back to it.

Merkle trees for long-term repair

Anti-entropy is a background job that compares two copies of the same key range and fixes any differences. Sending every key across the network would be far too slow, so servers compare Merkle trees instead.

A Merkle tree is a tree of hashes. In Dynamo each leaf is a hash of one key's value, and each parent is a hash of its children. If two roots match, the whole range matches and nothing moves.

If the roots differ, the servers follow only the branches that differ, down to the exact keys. Cassandra's repair also compares Merkle trees.

Gossip for knowing who is in the cluster

There is no central list of live servers. In Dynamo, each node contacts a random peer every second to swap what it knows about the cluster. Cassandra also gossips every second, and each node decides for itself whether a peer looks down.

It breaks whenever a read or a write does not reach the key's real owners. The R plus W rule assumes fixed owners, and failures move them.

Take a key owned by A, B and C, with W 2 and R 2. C is down, so a sloppy write lands on A and on a stand-in, D, which holds a hint for C.

Pause and predict: C comes back before the hint is delivered, and A becomes unreachable. A read waits for 2 replies, and B and C answer first. Will it see the write?

It will not. The write set is A and D, the read set is B and C, and they share nobody. The Dynamo paper says it does not enforce strict quorum membership, and calls the R plus W setting quorum-like.

Three more leaks matter in practice:

• A failed write is not rolled back. Cassandra sends every write to all replicas and only counts replies, so a write reported as failed may already sit on some copies.
• In Cassandra, the coordinator also stores a hint for a replica that timed out, so that failed write can still arrive there later.
• Under last write wins, a write stamped by a machine whose clock runs fast can beat writes made after it.

None of this makes the design wrong. It means a Dynamo-style store promises eventual agreement, and your app must tolerate a stale or surprising read.

Because random spots on a ring leave random gaps, and a handful of spots per server is too few to even them out. We measured how many of 100,000 keys the busiest and quietest of 5 servers own first, on one ring layout from the ring code above.

With 8 spots, one server held almost twice the keys of another. More spots help, but slowly: 16 spots did no better here, and 128 still left a gap of about 4 percentage points. Other server names give other layouts: with 8 spots, three more runs had busiest servers between 21.6 and 29.7 percent.

Dynamo's own paper reports this lesson. Both Dynamo and Cassandra call ring spots tokens. The paper compared three ways to place tokens and found the best balance came from splitting the ring into equal-sized partitions shared out among nodes.

Cassandra took a different path. Its docs say 2.x defaulted to 256 tokens per node, and 3.x added a token allocator that picks tokens deliberately. The cassandra.yaml shipped with 5.0.9 sets num_tokens: 16 with that allocator on.

So do not copy the 8 spots from a tutorial ring into production. Either use many spots, fixed equal partitions, or a store that places tokens for you.

Many stores in this family, Cassandra among them, append each change to a log on disk, keep recent data in memory, and later flush it to sorted files. Writes stay fast because the disk mostly appends instead of jumping around.

Dynamo itself made local storage pluggable. Its paper lists Berkeley DB, MySQL and an in-memory buffer with a persistent backing store. Cassandra uses a log-structured design with these parts:

• Commit log: every write is appended to a log file on disk, so it can be replayed after a crash.
• Memtable: the write also goes into a table in memory, kept in sorted order, which serves recent reads.
• SSTable: when a memtable reaches its size limit, it is flushed to a sorted file on disk that is never changed again.
• Compaction: a background job merges several SSTables into one and drops old overwritten values.
• Bloom filter: a small summary per SSTable that can say a key is definitely not there, so reads skip that file.

In this write path inside one node, notice that the node replies before any SSTable is written.

One detail surprises people. Cassandra 5.0.9 ships with commitlog_sync: periodic, which acknowledges writes at once and syncs the log every 10 seconds. The docs warn an unexpected shutdown can lose up to that window or more.

The other modes, batch and group, wait for the disk before replying. In periodic mode, writes from a node's last 10 seconds may be gone from that node after an unexpected shutdown, and the other copies are what keep them.

Tombstones and deletes

A store cannot simply erase a key from one copy, or an older copy would bring it back during repair. So a delete is written as a marker, called a tombstone, which is cleaned up much later.

In Cassandra, a tombstone can be dropped by compaction after gc_grace_seconds, 10 days by default. The repair docs say to repair every node at least once every 7 days, so deleted data cannot reappear.

Run the two small programs above, then ask a real Cassandra node the same questions. Each step names the output to expect.

1. 1

   Run the ring code

   Save the hash ring code and run it with Python 3. Expect ['node-4', 'node-3', 'node-1'] on every machine.

2. 2

   Run the overlap check

   Run the quorum code. Expect True for W 2 R 2 and False for W 1 R 1.

3. 3

   Ask Cassandra for a key's owners

   Run nodetool getendpoints KEYSPACE TABLE KEY. Expect one replica address per line, three lines when the replication factor is 3.

4. 4

   Read the shipped defaults

   Search conf/cassandra.yaml for num_tokens and commitlog_sync. On 5.0.9 expect num_tokens: 16 and commitlog_sync: periodic.

Explain it as a chain of choices, each backed by a requirement: where keys live, how many copies, how copies agree, and how the store heals.

1. 1

   Ask about the data

   Key size, value size, read and write rates, and whether a read may be a little stale.

2. 2

   Size it out loud

   Data size times copies, and peak writes times copies. These two sums set the first server count.

3. 3

   Partition with consistent hashing

   Draw the ring, add virtual nodes, and name the hot-key risk before the interviewer does.

4. 4

   Replicate and pick N, R and W

   Start with 3, 2 and 2, explain the overlap rule, and say which data could use weaker settings.

5. 5

   Handle conflicts

   Pick vector clocks with an app merge, or last write wins, and say what each one can lose.

6. 6

   Handle failures

   Hinted handoff for short outages, Merkle tree repair for long ones, and gossip for membership.

7. 7

   Describe one server

   Commit log, memtable and SSTables, plus tombstones for deletes.