Design a Key-Value Store

Problem statement

The prompt is short and exact: design a key-value store. A key-value store is a store built around one promise, that a value saved under a key comes back when that key is presented. A key is the short name a value is saved under and asked for by, and a value is the data saved under a key, such as a name, a cart or a session. Three operations carry the whole service: put saves a value under a key, get returns the value saved under a key, and delete removes the value saved under a key.

store = {}
store["user:1:name"] = "Ana"
store["user:1:city"] = "Oslo"
store["cart:9:items"] = "books"

print("get user:1:name ->", store.get("user:1:name"))
print("get user:1:city ->", store.get("user:1:city"))
print("keys stored:", len(store))

Three puts store three values, and two gets return exactly the values those keys hold. The third line of the output counts the stored keys, which shows that each distinct key occupies its own entry in the store. Nothing in the exchange depends on the order of the puts, and nothing depends on the values resembling each other in any way.

store = {"user:1:name": "Ana"}
store["user:1:name"] = "Ana Lee"

print("after overwrite:", store.get("user:1:name"))
print("missing key:", store.get("user:2:name"))
print("keys stored:", len(store))

A second put under the same key replaces the first value, so the latest put is the value a later get returns. A get for a key that was never saved finds nothing, and the store reports that absence plainly instead of guessing or returning a neighbour. Overwrite and absence are both ordinary outcomes of the contract, not errors, and clients build on both behaviours every day.

store = {"user:1:name": "Ana", "user:1:city": "Oslo", "user:2:name": "Ben"}

print("exact key:", store.get("user:1:name"))
print("part of a key:", store.get("user:1"))
print("keys stored:", len(store))

The store answers only the exact key presented, and a shorter part of a key is simply a different key that finds nothing. There is no prefix search, no pattern matching and no way to ask for every key that begins alike. That narrowness is the source of the speed: one exact key maps to one exact answer, with no scanning of other entries on the way.

store = {}
store["session:a"] = "Ana"
store["session:b"] = "Ben"
store["session:c"] = "Cid"
store["session:b"] = "Ben Fox"
del store["session:a"]

print("session:b ->", store.get("session:b"))
print("session:c ->", store.get("session:c"))
print("session:a ->", store.get("session:a"))
print("entries left:", len(store))

Puts, an overwrite and a delete run against one store in the closing model, and two entries are left at the end. A get for the deleted key finds nothing, while the surviving keys still return their latest values. The model is tiny, but every behaviour the larger design must preserve is already visible: exact lookup, latest value wins, and deletion that truly removes.

The stated scale is the load named in the ask: the store must serve 50,000 gets and puts per second, combined across all clients. That rate is far beyond one comfortable machine once durability and copies are priced in, and it is the number that forces the store across many servers. The shape is the NoSQL shape built for one-key lookups, and it is deliberately not built for joins across keys or questions that range over every key.

In scope

• Put, get and delete for one exact key, with the latest put winning
• Serving 50,000 gets and puts per second across many servers
• Surviving the failure of a single server without losing finished writes
• A per-request choice between a fast read and a read that is sure to be newest

Out of scope

• Joins across keys and questions that scan or range over many keys
• Transactions that span several keys at once
• Secondary indexes that find keys by their values
• Consensus protocols and leader election in depth

Requirements

The requirements turn the bare prompt into a contract that later choices can be judged against. Each functional item names a behaviour together with the consequence that makes the behaviour matter. Each non-functional item names a bar, and the bars around durability, failure and read freshness are the ones that shape the architecture most strongly.

Functional requirements

• Put a value under a key: the value is stored, and a later get for that exact key returns it, so a client can rely on what it saved being what it reads back
• Get a value by its exact key: the answer is the latest finished value for that key, or a plain absence when the key was never saved or was deleted, so clients never receive a value belonging to another key
• Overwrite a key: a second put under the same key replaces the earlier value everywhere the design promises freshness, so stale copies cannot quietly become the answer
• Delete a key: the value is removed, and later gets find nothing, so deletion is a real operation rather than a hint the store may ignore
• Choose freshness per request: a caller can ask for a fast read or a sure read on the same key, so one store serves both latency-sensitive and correctness-sensitive traffic

Non-functional requirements

• Throughput at the stated scale: the store sustains 50,000 gets and puts per second, so no single server sits on the path of every request
• Durability of finished writes: a write that counts as done survives the failure of the server that received it, because copies live on other servers
• Availability through one failure: with copies on separate servers, one failed server leaves its ranges served by the copies that remain, so reads and writes continue at reduced strength
• Honest freshness: a read labelled strong returns the latest finished write, while a read labelled eventual may return an older value for a short time, and the two are never confused
• Even load: keys spread across servers so that no server holds a wildly larger share than the others, because the slowest server sets the pace for its ranges

Two tensions run through the whole design and never fully disappear. More copies make finished writes safer and reads more available, yet every added copy costs storage and makes each write slower to confirm. Asking more copies on a read makes the answer surer, yet every added copy makes the read slower and heavier. The mechanisms in the deep dives exist to place those tensions under explicit numbers instead of leaving them as slogans.

Scale estimates

The estimates begin from the one stated load figure and derive everything else in the open. The stated figure is 50,000 gets and puts per second, and one day holds 86,400 seconds. Replication is stated separately: each range of keys is kept in 3 copies, so the fleet stores three entries for every logical key before any other overhead is counted.

The scale of the problem

The decisive multiplication is the daily volume: 50,000 operations per second × 86,400 seconds = 4,320,000,000 operations a day. A single machine can hold a key-value store comfortably at small scale, and the one-machine design remains the right starting point for correctness. The daily volume is what breaks the single machine as a final answer, because every one of those operations must also be made durable and, for most keys, copied. Partitioning spreads the operations across servers, and replication multiplies the storage and the write work on each range.

The quorum arithmetic is the second decisive sum, and it is small enough to hold in one line: W + R = 2 + 2 = 4, and 4 is more than N at 3, so a read always meets the latest finished write on at least one copy. That overlap is bought with the storage multiplier of 3 copies and with writes that wait for 2 confirmations before counting as done. The demo ring places 100 virtual nodes per server, stated as a demo value, so that each server owns many small slices of the ring rather than one large arc.

API design

The API is deliberately tiny, because the promise is tiny: one key in, one value out. Three operations cover the contract, and each one names the copies it must reach before it may report success. The quorum numbers travel with the operations rather than hiding inside the servers, so a caller choosing a strong read knows exactly what extra work that choice buys.

Core operations

All three operations are synchronous from the caller's point of view: the caller waits, and the answer means the promised quorum was reached. Nothing in the core contract needs a queue, because there is no spreading work behind a put or a get in the way a feed or a notification fans out. Background work still exists inside the store — log compaction, copy repair and the movement of ranges when servers join or leave — and that work runs off the request path so a busy repair never blocks a waiting client.

Failure answers are part of the shapes rather than surprises. A put that reaches fewer than W copies does not count as done, even if one copy holds it, and the caller is told the write failed so the value is never half-promised. A get for a missing key returns a plain absence, which is a successful answer about the key rather than an error about the request. Keeping those two cases distinct lets clients retry failed writes safely while treating absence as final information.

Data model

The data model has one entity that matters to clients and two structures that matter to the server holding it. The entity is the key-value pair itself, addressed by the exact key and carrying a version that rises with every write. Inside one server, durability comes from a write-ahead log, and speed comes from an index that remembers where each key's latest entry sits in that log.

Core entities and structures

log = []
index = {}

def put(key, value):
    log.append((key, value))
    index[key] = len(log) - 1

put("name", "Ana")
put("city", "Oslo")
put("name", "Ana Lee")

print("log entries:", len(log))
for key in sorted(index):
    print(key, "at position", index[key])
print("get name ->", log[index["name"]][1])

A put appends its entry to the log first and then records the entry position in the index, and a get follows the index straight to the latest entry. Writing the log before touching the index is the whole durability trick: if the machine stops between the two steps, the log entry survives and the index can be rebuilt to include it. The order of the two steps is therefore a correctness rule, not a performance preference.

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee")]
index = {}

for position, (key, value) in enumerate(log):
    index[key] = position

for key in sorted(index):
    print(key, "at position", index[key])
print("get name ->", log[index["name"]][1])
print("get city ->", log[index["city"]][1])

The log survives a restart while the in-memory index is lost, and reading the log in order rebuilds the same index. Each later entry for a key replaces the earlier position during the rebuild, so the rebuilt index points at the latest value for every key. Restart cost grows with log length, which is the pressure that makes compaction necessary rather than optional.

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee"), ("job", "cook"), ("city", "Bergen"), ("name", "Ana Lee Fox")]
latest = {}

for key, value in log:
    latest[key] = value

compacted = list(latest.items())
print("log entries before:", len(log))
print("log entries after:", len(compacted))
print("compacted log:", compacted)

Repeated puts under one key leave older entries behind in the log, and log compaction is the rewrite of the log that keeps only the latest entry for each key. The model log shrinks from six entries to three, one per surviving key, and every get returns the same answer before and after the rewrite. Compaction spends work rewriting the log in exchange for a shorter log, faster restarts and less disk held by values nobody can still read.

log = [("name", "Ana"), ("city", "Oslo"), ("name", "Ana Lee"), ("job", "cook"), ("city", "Bergen"), ("name", "Ana Lee Fox"), ("job", "baker"), ("city", "Oslo")]
index = {}

for position, (key, value) in enumerate(log):
    index[key] = position

print("entries in the log:", len(log))
print("get name after restart ->", log[index["name"]][1])

latest = {}
for key, value in log:
    latest[key] = value

print("entries after compaction:", len(latest))
for key in sorted(latest):
    print(key, "->", latest[key])

The closing model runs a longer log through both steps in sequence: a rebuild after a restart, then a compaction. Eight entries rebuild into an index that still answers every key with its latest value, and compaction then reduces the log to three entries without changing any answer. The pair of steps is the complete one-machine story — append for durability, index for speed, compact to stay short — and the multi-server design keeps that story inside each server while adding placement and copies around it.

High-level architecture

A client request first meets a coordinator, the component that works out which range a key belongs to and which servers hold copies of that range. The coordinator consults the ring, the shared map of which server owns which slice of the key space, and then talks to the copy servers for that range. Each copy server runs the one-machine store internally, with its own write-ahead log and index, so durability on one server and durability across servers are separate mechanisms that compose.

┌──────────┐   put / get / delete   ┌───────────────┐
│  Client  │ ─────────────────────▶ │  Coordinator  │
└──────────┘ ◀───────────────────── └───────────────┘
     value or absence          ring lookup │
                                           ▼
                                  ┌───────────────┐
                                  │     Ring      │
                                  │ key -> owners │
                                  └───────────────┘
                                           │
              ┌────────────────────────────┼────────────┐
              ▼                            ▼            ▼
       ┌────────────┐              ┌────────────┐ ┌────────────┐
       │ Server A   │              │ Server B   │ │ Server C   │
       │ log+index  │              │ log+index  │ │ log+index  │
       │ copy of    │              │ copy of    │ │ copy of    │
       │ the range  │              │ the range  │ │ the range  │
       └────────────┘              └────────────┘ └────────────┘

The write flow

1. The client sends a put with the key and the value to a coordinator
2. The coordinator reads the ring and finds the servers holding copies of the key's range
3. Each reachable copy server appends the entry to its write-ahead log, updates its index and raises the version
4. Once W = 2 copies have confirmed, the write counts as done and the coordinator answers the client
5. A copy that was down receives the missed write later, during repair, and holds a stale version until then

The read flow

1. The client sends a get with the exact key and the freshness it needs
2. The coordinator finds the copy servers for the key's range from the ring
3. A strong read asks R = 2 copies and returns the value carrying the highest version
4. An eventual read takes the first copy that answers and returns its value, which may be older
5. A key held by no copy returns a plain absence to the client

Every functional requirement lands on a component in the diagram. Put, get and delete land on the coordinator and the copy servers, durability lands on the write-ahead log inside each server, freshness choice lands on how many copies the coordinator asks, and survival of one failure lands on copies held by separate servers. No requirement depends on a component the diagram leaves out, and the ring is the single shared fact every coordinator must agree on for routing to stay consistent.

Deep dive: splitting the store with consistent hashing

One machine cannot carry 50,000 operations per second with copies and durability priced in, so the key space must split across servers. The placement rule decides which server owns which keys, and a bad rule punishes the store twice: uneven shares overload some servers, and clumsy re-placement moves enormous numbers of keys whenever a server joins or leaves. Consistent hashing is the placing of keys and servers on one ring, where a key belongs to the next server clockwise.

Three ways to place keys

servers = [(10, "server A"), (40, "server B"), (70, "server C")]
keys = [("key-1", 5), ("key-2", 15), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 85)]

def owner(position):
    for server_position, name in servers:
        if position <= server_position:
            return name
    return servers[0][1]

counts = {}
for key, position in keys:
    name = owner(position)
    counts[name] = counts.get(name, 0) + 1
    print(key, "at", position, "->", name)

for name in sorted(counts):
    print(name, "owns", counts[name], "keys")

Servers and keys sit at fixed positions on the ring, and each key belongs to the first server met clockwise from its position, wrapping to the start after the last server. That first server is the owner of the key, the server responsible for holding the key's range before copies are considered. The small ring spreads its keys evenly by construction of the positions, and the ownership rule needs nothing beyond the ordered positions to answer any key.

servers = [(10, "server A"), (40, "server B"), (70, "server C")]
keys = [("key-1", 5), ("key-2", 15), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 85)]

def owner(position, ring):
    for server_position, name in ring:
        if position <= server_position:
            return name
    return ring[0][1]

before = {key: owner(position, servers) for key, position in keys}
remaining = [entry for entry in servers if entry[1] != "server C"]
moved = []
stayed = []

for key, position in keys:
    if owner(position, remaining) != before[key]:
        moved.append(key)
    else:
        stayed.append(key)

print("moved keys:", moved)
print("moved:", len(moved))
print("stayed:", len(stayed))

When one server leaves the ring, only that server's keys pass to the next server clockwise, and every other key keeps the same owner. The model shows two keys moving and four keys staying when the third server leaves. That locality is the property the whole design is bought for: a fleet change touches one share of the keys instead of reshuffling the entire store, so growth and failure recovery stay proportional to one server's load.

ring = [(5, "server A"), (20, "server B"), (35, "server C"), (50, "server A"), (65, "server B"), (80, "server C"), (88, "server A"), (93, "server B"), (98, "server C")]
keys = [("key-1", 3), ("key-2", 18), ("key-3", 33), ("key-4", 48), ("key-5", 63), ("key-6", 78)]

def owner(position):
    for node_position, name in ring:
        if position <= node_position:
            return name
    return ring[0][1]

counts = {}
for key, position in keys:
    name = owner(position)
    counts[name] = counts.get(name, 0) + 1
    print(key, "at", position, "->", name)

for name in sorted(counts):
    print(name, "owns", counts[name], "keys")

A single position per server leaves balance to luck, because one large gap between neighbouring positions hands one server a large arc of the ring. A virtual node is one of many positions a single server places on the ring, so its keys spread around the circle in many small slices instead of one arc. The small model uses three virtual nodes per server and says so, and the design demo ring uses 100 virtual nodes per server, stated as a demo value, which smooths the shares far more finely.

ring = [(10, "server A"), (25, "server B"), (40, "server C"), (55, "server A"), (70, "server B"), (85, "server C"), (100, "server A"), (115, "server B"), (125, "server C")]
keys = [("key-1", 5), ("key-2", 20), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 80), ("key-7", 95), ("key-8", 110), ("key-9", 120)]

def owner(position, nodes):
    for node_position, name in nodes:
        if position <= node_position:
            return name
    return nodes[0][1]

before = {key: owner(position, ring) for key, position in keys}
remaining = [entry for entry in ring if entry[1] != "server B"]
moved = []
stayed = []

for key, position in keys:
    if owner(position, remaining) != before[key]:
        moved.append(key)
    else:
        stayed.append(key)

print("moved keys:", moved)
print("moved:", len(moved))
print("stayed:", len(stayed))

The closing model places virtual nodes for three servers around a larger ring and then removes one server entirely. Only the removed server's keys move to a new owner, and the remaining keys stay with the server that already held them. Virtual nodes change the balance of the shares without changing the movement rule, which is why the two ideas pair so often: the ring limits movement, and the many positions even out the load.

The verdict is consistent hashing with virtual nodes. Modulo placement is rejected because a single fleet change would move almost every key, turning routine growth into a store-wide migration. Fixed ranges are rejected because popular key prefixes concentrate load in a way the operator must repair by hand. The cost of the verdict is the ring itself: every coordinator must hold the same ring, hash values in the demos are written as plain data rather than worked out inside the programs, and a stale ring routes requests to the wrong owner until it refreshes.

Deep dive: copies and quorums

Partitioning decides where a key lives, and replication decides how many servers hold it. A copy is one stored replica of a range of keys, kept on its own server, so the copies of one range never share a single point of failure. The design keeps N = 3 copies for each range, and the quorum rule decides how many of those copies a write or a read must reach before it counts.

Three ways to keep data safe

copies = [{"value": None, "version": 0}, {"value": None, "version": 0}, {"value": None, "version": 0}]

def put(value):
    for copy in copies:
        copy["value"] = value
        copy["version"] += 1

put("Ana")
put("Ana Lee")

for i, copy in enumerate(copies):
    print("copy", i + 1, "holds", copy["value"], "at version", copy["version"])

Each put writes all reachable copies and raises the version counter, and a version is a plain counter on each value that rises with every write, so the newest copy can be told from a stale one. After two puts, every copy holds the same value at the same version, which is the calm case the quorum rules are designed around. Versions matter precisely because the calm case is not guaranteed, and the next models show the disturbed cases.

alive = [True, True, False]
copies = [{"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}]
confirmations = 0

for i in range(3):
    if alive[i]:
        copies[i]["value"] = "Ana Lee"
        copies[i]["version"] += 1
        confirmations += 1

print("confirmations:", confirmations)
print("write counts as done:", confirmations >= 2)
for i, copy in enumerate(copies):
    print("copy", i + 1, "holds", copy["value"], "at version", copy["version"])

One copy is down and never confirms the write, yet the write still counts as done because the other copies reach W = 2. The down copy keeps the older value at the older version, and that staleness is recorded honestly by the version numbers rather than hidden. A write that reaches fewer than W copies does not count as done, even if one copy holds it, so a single surviving copy can never promote a write on its own authority.

copies = [("copy A", "Ana Lee", 2), ("copy B", "Ana", 1), ("copy C", "Ana Lee", 2)]
asked = copies[:2]
best = asked[0]

for entry in asked:
    print(entry[0], "reports version", entry[2])
    if entry[2] > best[2]:
        best = entry

print("read returns:", best[1], "at version", best[2])

One copy is stale and still holds the older version, and the read asks two copies and takes the answer with the highest version. The overlap rule is what makes that safe: W + R is 4, and 4 is more than N at 3, so the copies the read asks must share at least one copy with the copies the finished write reached. That shared copy carries the newest version into the comparison, and the version comparison does the rest.

copies = [{"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}]
alive = [True, True, False]
confirmations = 0

for i in range(3):
    if alive[i]:
        copies[i]["value"] = "Ana Lee"
        copies[i]["version"] += 1
        confirmations += 1

print("write confirmations:", confirmations)
print("write counts as done:", confirmations >= 2)

asked = [copies[1], copies[2]]
best = asked[0]
for copy in asked:
    if copy["version"] > best["version"]:
        best = copy

print("read returns:", best["value"], "at version", best["version"])
print("W + R > N:", 2 + 2 > 3)

The closing model disturbs the write and the read at once: one copy is down during the write and stale during the read, yet the write still counts as done and the read still returns the newest value. The two copies the read asks overlap the copies the write reached, which is the overlap rule operating exactly as the arithmetic promised. Nothing in the outcome depends on luck or timing, because the guarantee is arithmetic rather than hopeful.

The verdict is N = 3 copies with W = 2 and R = 2. One copy per range is rejected because a single failure would silence whole ranges of keys. Every-copy writes are rejected because one down copy would block writes entirely, which wastes the very redundancy the copies were bought for. The cost of the verdict is real: storage triples for the same keys, writes wait for a second confirmation, and stale copies exist as a normal state that every read path must handle through versions.

Deep dive: choosing consistency per request

Copies create a question that one machine never faces: when copies disagree for a short time, which answer may a read return. Strong consistency means a read returns the latest finished write, even when the read must ask more copies to be sure. Eventual consistency means a read may return an older value for a short time, and the copies agree later. The design refuses to pick one answer for the whole store, and instead lets each request pick, so one key can serve both kinds of read.

Three consistency postures

copies = [("copy A", "red", 2), ("copy B", "blue", 3)]

print("eventual read asks copy A ->", copies[0][1])
best = copies[0]
for entry in copies:
    if entry[2] > best[2]:
        best = entry
print("strong read asks every copy ->", best[1])

An eventual read asks the first copy and may get the older value, while a strong read asks every copy and takes the newest version. The same key at the same moment returns two different answers to two different requests, and both answers are correct under the promise each request chose. The difference is not hidden inside the store, because the request itself carries the choice and the response honours exactly that choice.

arrivals = [(5, "red"), (9, "blue"), (7, "green")]
kept = arrivals[0]

for stamp, value in arrivals:
    print("arrived: time", stamp, "value", value)
    if stamp > kept[0]:
        kept = (stamp, value)

print("kept:", kept[1], "from time", kept[0])

Copies that were written at different moments need a rule for resolving two conflicting writes, and last-write-wins is a conflict rule that keeps the write with the later time stamp and drops the other. Several writes for one key arrive out of order in the model, and the kept value is the one with the highest time stamp rather than the one that arrived last. Arrival order is deliberately ignored, because arrivals reflect network timing rather than the order in which the writes were made.

arrivals = [(10, "old address"), (8, "new address")]
kept = arrivals[0]

for stamp, value in arrivals:
    print("arrived: time", stamp, "value", value)
    if stamp > kept[0]:
        kept = (stamp, value)

print("kept:", kept[1])
print("newer write kept:", kept[1] == "new address")

The honest weakness of the rule is clock risk: server clocks can run slightly fast or slow, so the later time stamp is not always the truly newer write. A newer write carries the smaller time stamp in the model because its server clock runs slow, and last-write-wins keeps the older write while the newer write is lost. No amount of care in applying the rule repairs a wrong time stamp, which is why the risk belongs in the open rather than in a footnote.

arrivals = [(12, "Ana"), (15, "Ana Lee"), (13, "A. Lee")]
kept = arrivals[0]

for stamp, value in arrivals:
    print("arrived: time", stamp, "value", value)
    if stamp > kept[0]:
        kept = (stamp, value)

print("kept:", kept[1], "from time", kept[0])

The closing model runs three writes for one profile name through the same rule, arriving out of order, and the write with the highest time stamp is kept. The kept write did not arrive last, and the rule does not care about arrival order at any point in the comparison. The example and the clock-risk model are the same mechanism seen from two sides: the rule is simple and predictable, and its single assumption is that time stamps deserve trust.

The verdict is a per-request choice with last-write-wins resolving conflicts. Strong everywhere is rejected because it taxes every read for a guarantee only some callers need, and eventual everywhere is rejected because it offers no path at all to a caller holding a correctness requirement. The costs are named plainly: callers carry the burden of choosing, and a slow clock can erase a newer write under the conflict rule. Vector clocks are a stronger tool for tracking which write came first, and a later course covers them.

Bottlenecks and failure modes

The first saturation point is not the fleet as a whole but a single hot range or a single hot key. Load spreads evenly only while requests spread evenly, and real traffic concentrates: one popular key can draw a large share of all requests while neighbouring keys sit idle. Storage growth is the slow pressure behind that sharp one, because the log on each server grows with every write and copies multiply whatever the fleet stores.

for alive in [3, 2, 1]:
    print("copies up:", alive, "write counts:", alive >= 2, "read counts:", alive >= 2)

The quorum tolerates exactly one failed copy in this design, and the model prints the boundary without decoration. With two copies up, writes and reads still count, and with only one copy up, neither counts. That boundary is a chosen property rather than an accident: raising the tolerance would mean more copies or lower quorums, and each of those moves costs storage or freshness somewhere else.

requests = ["key-7", "key-7", "key-1", "key-7", "key-2", "key-7", "key-7", "key-3", "key-7", "key-7"]
counts = {}

for key in requests:
    counts[key] = counts.get(key, 0) + 1

for key in sorted(counts):
    print(key, "asked", counts[key], "times")
print("total requests:", len(requests))

A hot key is a key asked for far more than the others, the familiar hot spot in a new shape. In the model run, most of the requests ask for one key, and that key's server takes most of the load while the other servers sit nearly idle. Consistent hashing cannot fix a hot key, because the key hashes to one place by design, and every request for it follows the same route to the same owner and its copies.

• One copy server fails: its ranges stay served by the remaining copies, writes and reads still count at quorum, and the failed server's copies are stale until repaired
• Two copy servers for one range fail: that range stops counting writes and reads, while every other range keeps working, so the failure stays local to the affected keys
• A coordinator holds a stale ring: requests route to a former owner, which forwards or refuses them until the ring refreshes, and no data is lost because the copies themselves are untouched
• The write-ahead log grows unchecked: restarts slow down and disk fills with superseded entries, until compaction rewrites the log and restores the short form
• A hot key saturates its owner: reads for that key queue behind each other while the rest of the fleet idles, and only spreading that key's reads relieves it

The degradation order is deliberate throughout. Freshness degrades before availability when a read falls back to a faster answer, and availability of one range degrades before the store as a whole notices anything. What must never degrade is the durability of a finished write: a write counted as done at W = 2 copies survives the loss of any one of them, and a write that cannot reach its quorum reports failure instead of quietly weakening the promise. How replicas agree on a leader is a deeper topic, covered in the Advanced course, and the failure behaviour described here assumes that machinery rather than replacing it.

Trade-offs

Every earlier choice bought something by giving something up, and the summary collects those exchanges in one place. The table carried over from the source design names the recurring four: copies, strong reads, eventual reads and compaction. The paragraphs after the table add the placement and conflict choices, so no verdict given in the deep dives is missing from the accounting.

Key-value store trade-offs

keys = ["name", "city", "job", "cart"]

for copies in [1, 3]:
    print("copies:", copies, "stored entries:", len(keys) * copies)

The storage cost of copies is arithmetic rather than opinion: the same keys stored with one copy occupy a quarter of the entries they occupy with three copies in the model, and the ratio holds at any scale. Survival and storage are the same dial turned in opposite directions, which is why N is a stated design choice rather than a default nobody chose. A store that cannot afford the tripled storage must say openly that it accepts weaker survival, instead of discovering the fact during an outage.

The decisions and their costs

requests = ["song-1", "song-1", "song-2", "song-1", "song-3", "song-1", "song-1", "song-1"]
counts = {}

for key in requests:
    counts[key] = counts.get(key, 0) + 1

for key in sorted(counts):
    print(key, "asked", counts[key], "times")

alive = 2
print("total requests:", len(requests))
print("copies up:", alive, "write counts:", alive >= 2, "read counts:", alive >= 2)

The closing model combines the two live pressures in one small run: most requests chase one hot key while one of the three copies is down. The store still counts its writes and reads, because two copies remain up and the quorum is still met. The hot key remains the load problem to fix, and the sound first move is to spread its reads across its copies and cache its value, so one server stops taking every request for it.

Taken together, the design spends storage and write confirmations to buy survival and honest freshness at 50,000 operations per second. Placement keeps fleet changes cheap, quorums keep one failure ordinary, and the per-request choice keeps fast reads fast without lying to careful ones. A smaller store with gentler load should give some of that back — fewer copies, simpler placement — because the right shape follows the stated load rather than habit.

Common questions

How does a key-value store find the right server for a key?

Placement runs through consistent hashing on a ring shared by the coordinators. The key and the servers sit at positions on the ring, and the key belongs to the first server met clockwise from its position, with virtual nodes spreading each server across many positions. The demo ring uses 100 virtual nodes per server, stated as a demo value, and only the keys of a joining or leaving server change owner.

Why do W and R add up to more than N?

The overlap is the guarantee, stated in one sum: with N = 3, W = 2 and R = 2, the value of W + R is 4, which is more than 3. Any group of 2 copies a write reached and any group of 2 copies a read asks must share at least one copy out of the 3. That shared copy carries the latest finished version into the read, and the read returns the highest version it is shown.

What is a write-ahead log for?

The write-ahead log is the durable record that makes one server trustworthy before copies across servers are considered. Each write is appended to the log first, in order, and only then does the in-memory index change to point at the new entry. A restart rebuilds the index by reading the log from start to end, and compaction rewrites the log keeping only the latest entry per key, so restarts stay fast and the log stays short.

What should be done about a hot key?

A hot key is relieved by spreading its reads rather than by moving the key, because its copies already sit on separate servers. Reads for the hot key are shared across its 3 copies and its value is cached, so no single server takes every request for it. The quorum settings stay untouched, since raising W would send even more traffic to the same copies instead of spreading the load.

Related designs: the URL shortener stores its codes in a store of this shape, the rate limiter keeps its counters in one, and the chat system, the news feed, the autocomplete service, the notification system and the social app each lean on key-value storage for their hottest lookups.

The estimate at a glance