System Design (High-Level Design) Module 19 – Building blocks: traffic, storage and messaging
Design a distributed key-value store
Size a distributed key-value store, place one replica per zone, and follow the read and write paths of a leaderless design and a leader per shard.
What you will learn
- Estimate the data, replica traffic and node count of a key-value store from its requirements
- Design partitioning and zone-aware replica placement that survives the loss of a zone
- Compare a leaderless quorum design with a leader per shard along their write and read paths
- Diagnose failures such as expired hints, deleted keys that return and skewed clocks
- Plan the storage engine, membership changes and tests of the store at ten times the load
Before you start
What you’ll learn · Before you start
What you will learn
- Estimate the data, replica traffic and node count of a key-value store from its requirements
- Design partitioning and zone-aware replica placement that survives the loss of a zone
- Compare a leaderless quorum design with a leader per shard along their write and read paths
- Diagnose failures such as expired hints, deleted keys that return and skewed clocks
- Plan the storage engine, membership changes and tests of the store at ten times the load
Before you start
On this page
A shop keeps 5 billion carts, sessions and balances under keys and must answer 300,000 reads and 100,000 writes a second within 10 ms, while machines, and sometimes a whole zone, fail. A distributed key-value store meets that by making three decisions: partitioning decides which machines hold a key, replication keeps one copy in each zone, and agreement decides how the copies stay consistent.
Two designs for agreement have proved themselves. In a leaderless design, after Amazon’s Dynamo paper and Apache Cassandra, a coordinator sends each write to all three replicas and answers once two of them hold it. In a leader-per-shard design, as in Amazon DynamoDB, each range of keys is a consensus group whose leader orders every write. You will size the store, place its replicas, run both designs along their write and read paths, and choose one for each workload.
Requirements and estimate: 5.5 TB becomes 16.5 TB on 15 nodes
Ask what the store holds and how stale a read may be before drawing anything. This design takes these answers:
- Operations:
get,putanddelete, and a conditional put that succeeds only if the stored version is still the one the caller read. Keys up to 256 bytes, values up to 64 KB and 1 KB on average. - Scale and speed: 5 billion keys; 300,000 reads and 100,000 writes a second at peak; p99 under 10 ms inside one region.
- Failures: lose any node, or any one of three zones, without losing an acknowledged write.
- Consistency: a read after an acknowledged write returns it.
The estimate, row by row:
| Quantity | Working | Result |
|---|---|---|
| Data | 5 billion keys × 1.1 KB with key and version | 5.5 TB |
| Copies | 3 replicas, one in each zone | 16.5 TB |
| Nodes | 2 TB disks kept near 55 % full for compaction and spare room | 15 nodes, 1.1 TB each |
| Replica writes | 100,000 puts × 3 | 20,000 a second per node |
| Replica reads | 300,000 gets × 3 replicas asked | 60,000 a second per node |
Disk space sets the node count, and the headroom is deliberate: compaction needs room for its temporary files, and a failed node’s share lands on the others.
Checkpoint
Check: Sizing data, copies and nodes
The API: a conditional put, and deletes that leave tombstones
Three calls cover the operations; the version token protects a put from a writer that got there first:
| Call | What it does | Answers |
|---|---|---|
GET /v1/kv/{key} |
Returns the value and an opaque version token | 200, or 404 for a missing key |
PUT /v1/kv/{key} |
Stores a value; with If-Match: <version>, only while the key is still at that version |
200 with the new version, or 412 Precondition Failed |
DELETE /v1/kv/{key} |
Writes a tombstone: A marker an LSM-tree engine writes to delete a key, because its files are never changed. It hides the older values of the key until compaction drops them. More in “Storage engines: B-trees vs LSM-trees”, a marker that replicas keep for a grace period | 200 |
The conditional put works as HTTP’s conditional requests do (RFC 9110). Each replica stores the key, the value or tombstone, a version, the write’s timestamp and an optional expiry. The designs differ in the version: a leader gives every write a position in the shard’s log, so versions simply grow; a leaderless store needs a version vector: One counter per leader, kept with every version of an item; each leader raises its own counter when it writes. When each of two versions is ahead in some counter, their writes were concurrent. More in “Multi-leader replication and conflict resolution”, one counter per coordinator, to tell a newer write from a concurrent one.
Checkpoint
Check: Conditional puts and tombstones
One copy per zone: a key’s replicas come from the ring
The first complete design: one request, three replicas, one per zone
Text description of the diagram
Application servers hold a client library with the ring map, so they know the three replicas of every key. For a put or a get (1), the library sends the request to a coordinator. In the leaderless design the coordinator is the key's replica in the client's own zone; in the leader design it is the leader of the key's shard.
The coordinator (2) sends the request to all three replicas of the key, one each in zones a, b and c. Every replica keeps a commit log, an in-memory table and sorted files on disk.
The answer goes back to the client (3) once two replicas have replied: two acknowledgements for a write in the leaderless design, or the leader and one follower holding the log entry in the leader design.
Every node also runs background work: gossip about which nodes are up, failure detection, hints for replicas that were down, and repair that compares replicas.
Each node owns 256 tokens on a hash ring, and a key belongs to the tokens that follow its hash clockwise (consistent hashing). Its replicas are the first three nodes clockwise that sit in three different zones, its preference list. Cassandra places copies the same way across racks when a data centre has at least as many racks as copies (Cassandra). The model below builds the ring for 15 nodes, compares three placements of 30,000 keys and then traces one key through both designs:
# A key-value store of 15 nodes in three zones (a, b and c), placed on a consistent-hash ring, and the write and read
# paths of two designs traced on one fixed latency model: a leaderless store (N = 3, W = 2, R = 2) and a leader per
# shard (a consensus group of three replicas). Deterministic: ring positions come from SHA-256 and the latencies are
# fixed numbers, so every run prints the same.
import bisect
import hashlib
ZONES = "abc"
NODES = [f"{z}{i}" for z in ZONES for i in range(1, 6)] # a1 … a5, b1 … b5, c1 … c5
N = 3
def position(text):
"""A 64-bit ring position."""
return int.from_bytes(hashlib.sha256(text.encode()).digest()[:8], "big")
def build_ring(tokens_per_node):
ring = sorted((position(f"{node}#{i}"), node) for node in NODES for i in range(tokens_per_node))
return ring, [p for p, _ in ring]
def zone(node):
return node[0]
def preference_list(key, ring, zone_aware):
"""The first N nodes clockwise from the key; zone-aware skips a node whose zone already holds a copy."""
tokens, positions = ring
start = bisect.bisect_left(positions, position(key))
chosen = []
for step in range(len(tokens)):
node = tokens[(start + step) % len(tokens)][1]
if node in chosen or (zone_aware and any(zone(node) == zone(c) for c in chosen)):
continue
chosen.append(node)
if len(chosen) == N:
break
return chosen
# ---- 1. Placement: balance, and what a zone outage leaves behind ------------------------------------------------
KEYS = [f"user:{i}" for i in range(30_000)]
mean = len(KEYS) * N // len(NODES)
print(f"{len(NODES)} nodes in zones a, b and c; {len(KEYS):,} keys, {N} replicas each ({mean:,} replicas per node on average)\n")
print(f"{'placement':<33}{'replicas per node':<20}{'busiest':<10}keys without 2 replicas if zone c fails")
for tokens, aware, label in ((16, False, "distinct nodes, 16 tokens each"), (16, True, "one per zone, 16 tokens each"), (256, True, "one per zone, 256 tokens each")):
ring = build_ring(tokens)
load = {n: 0 for n in NODES}
lost = 0
for key in KEYS:
replicas = preference_list(key, ring, aware)
for r in replicas:
load[r] += 1
if sum(zone(r) != "c" for r in replicas) < 2:
lost += 1
spread = f"{min(load.values()):,} to {max(load.values()):,}"
busiest = f"+{max(load.values()) / mean - 1:.0%}"
print(f"{label:<33}{spread:<20}{busiest:<10}{lost:,} of {len(KEYS):,}")
# ---- 2. One key through both designs (zone-aware placement, 256 tokens per node) ---------------------------------
RING = build_ring(256)
APPEND = 0.1 # ms to append a record to a replica's commit log (with group commit)
READ = 0.05 # ms to read a key that is in memory
def rtt(x, y):
"""Round trip in ms between two places (the client counts as a place in its zone)."""
if x == y:
return 0.0
return 0.2 if zone(x) == zone(y) else 1.0
def show(step_times):
for t, text in step_times:
print(f" {t:5.2f} ms {text}")
key = "user:42"
replicas = preference_list(key, RING, True)
client = "a-client" # an application server in zone a
print(f"\n{key}: replicas {', '.join(replicas)} (the preference list; in the leader design the first one leads)")
# Leaderless put: a token-aware client sends to the key's replica in its own zone, which coordinates.
coord = next(r for r in replicas if zone(r) == zone(client))
hop = rtt(client, coord)
acks = sorted((rtt(coord, r) + APPEND, r) for r in replicas)
print("\nLeaderless put (N = 3, W = 2), client in zone a:")
show([(hop / 2, f"client reaches coordinator {coord}, which sends the write to all 3 replicas")]
+ [(hop / 2 + t, f"acknowledged by {r}") for t, r in acks]
+ [(hop + acks[1][0], "client has its answer: 2 replicas hold the write, the third catches up")])
reads = sorted((rtt(coord, r) + READ, r) for r in replicas)
print("Leaderless get (R = 2): the newest of the first 2 replies; a stale reply is repaired")
show([(hop + reads[1][0], f"answer from {reads[0][1]} and {reads[1][1]}")])
# Leader per shard: every write goes to the shard's leader, which commits once a majority (2 of 3) has the entry.
leader = replicas[0]
hop = rtt(client, leader)
first_follower = min(rtt(leader, r) + APPEND for r in replicas[1:])
commit = max(APPEND, first_follower) # the leader's own append and the first follower's
print(f"\nLeader per shard, leader {leader}, client in zone a:")
show([(hop / 2, f"client reaches leader {leader} in zone {zone(leader)}"),
(hop / 2 + commit, "a majority (the leader and one follower) has the log entry: committed"),
(hop + commit, "client has its answer")])
print("Leader read with a valid lease: the leader answers alone")
show([(hop + READ, f"answer from {leader}")])
# Over many keys the client meets a remote leader two times in three.
lat_leaderless, lat_leader, remote = [], [], 0
for key in KEYS:
reps = preference_list(key, RING, True)
coord = next(r for r in reps if zone(r) == "a")
lat_leaderless.append(rtt(client, coord) + sorted(rtt(coord, r) + APPEND for r in reps)[1])
leader = reps[0]
remote += zone(leader) != "a"
lat_leader.append(rtt(client, leader) + max(APPEND, min(rtt(leader, r) + APPEND for r in reps[1:])))
print(f"\nAll {len(KEYS):,} keys written from zone a, no failures:")
print(f" leaderless put {sum(lat_leaderless) / len(KEYS):.2f} ms on average")
print(f" leader-per-shard put {sum(lat_leader) / len(KEYS):.2f} ms on average ({remote:,} keys have their leader in another zone)")Output
15 nodes in zones a, b and c; 30,000 keys, 3 replicas each (6,000 replicas per node on average) placement replicas per node busiest keys without 2 replicas if zone c fails distinct nodes, 16 tokens each 4,376 to 7,555 +26% 8,790 of 30,000 one per zone, 16 tokens each 4,377 to 8,627 +44% 0 of 30,000 one per zone, 256 tokens each 5,320 to 6,435 +7% 0 of 30,000 user:42: replicas b5, c3, a2 (the preference list; in the leader design the first one leads) Leaderless put (N = 3, W = 2), client in zone a: 0.10 ms client reaches coordinator a2, which sends the write to all 3 replicas 0.20 ms acknowledged by a2 1.20 ms acknowledged by b5 1.20 ms acknowledged by c3 1.30 ms client has its answer: 2 replicas hold the write, the third catches up Leaderless get (R = 2): the newest of the first 2 replies; a stale reply is repaired 1.25 ms answer from a2 and b5 Leader per shard, leader b5, client in zone a: 0.50 ms client reaches leader b5 in zone b 1.60 ms a majority (the leader and one follower) has the log entry: committed 2.10 ms client has its answer Leader read with a valid lease: the leader answers alone 1.05 ms answer from b5 All 30,000 keys written from zone a, no failures: leaderless put 1.30 ms on average leader-per-shard put 1.83 ms on average (20,054 keys have their leader in another zone)
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 kv_paths.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Placing copies on distinct nodes alone left 8,790 of the 30,000 keys with two or more copies in zone c, so losing that zone would take their quorum. One copy per zone removed that risk, but with 16 tokens per node the busiest node held 44 % more than the average; 256 tokens brought that to 7 %. Size disks for the busiest node, not the average.
Checkpoint
Check: One replica per zone from the ring
Two ways to agree: any two replicas, or a leader’s log
In the leaderless design, the client library sends a put to the key’s replica in its own zone, which coordinates: it stamps a version, sends the write to all three replicas and answers
after W = 2 acknowledgements, a quorum (N, R and W): The number of a key's N replicas that must take part: W for a write to succeed, R for a read. When R + W is more than N, every set of replicas a read asks shares at least one replica with every set a write reached. More in “Leaderless replication and quorums: N, R and W”. A get asks all three replicas, returns the newest of
the first R = 2 replies and repairs a replica that answered with an older version. The Dynamo paper describes this
shape, and its common setting was N = 3, R = 2, W = 2
(Dynamo). Step through one put and one get
of user:42, timed by the model:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- The nearest replica coordinates. The client library knows the key's three replicas, b5, c3 and a2, and sends the put to a2, the one in its own zone. It arrives at 0.10 ms.
- Stamp a version, write to all 3. a2 stamps a version and sends the write to every replica, itself included. Its own append to the commit log is done at 0.20 ms.
- Two zones away, one round trip. b5 and c3 each append the write and acknowledge after one round trip across zones, at 1.20 ms.
- W = 2 is enough. a2 has two acknowledgements, its own and one from another zone, so it answers. The client has its answer at 1.30 ms; no single replica had to reply.
- A read asks all three. A get goes to a2 too, which asks all three replicas for the key and its version.
- Newest of the first two replies. With R = 2, a2 answers from the first two replies, its own and b5's, at 1.25 ms, and returns the newer version. A replica that answered with an older one is repaired.
With a leader per shard, the three replicas form a consensus group for each range of keys. A put goes to the group’s leader, which appends it to its log and commits once a majority, itself and one follower, holds it; a consistent get is answered by the leader alone, once it knows it still leads. In DynamoDB’s paper, the replicas of each partition form a Multi-Paxos group, only the leader serves writes and strongly consistent reads, and a write is acknowledged once a quorum of replicas has persisted its log record (USENIX ATC).
Not affiliated
Based on public information about Amazon Web Services. MySmartCoPilot is not affiliated with Amazon Web Services, and Amazon Web Services’s real systems may differ from what this lesson describes.
| Criterion | Leaderless, N = 3, R = 2, W = 2 | Leader per shard, groups of 3 |
|---|---|---|
| Who orders writes | Nobody: versions are compared afterwards | The shard's leader, through its log |
| A write waits for | Any 2 of the 3 replicas | The leader and 1 follower |
| A consistent read asks | All 3, answers after 2 | The leader alone |
| Two writes at once | Kept as siblings, or the newest timestamp wins | Ordered by the log |
| Conditional put | An extra consensus round per write | A check inside the leader |
| A replica fails | No pause | A pause until a new leader serves, if it led |
| When to choose | Writes that must always succeed: carts, sessions, counters | Conditional writes and current reads: balances, stock, locks |
Checkpoint
Check: Leaderless quorums and a leader per shard
Both paths on a model: a remote leader costs about half a millisecond
The traces in the model’s output put numbers on the comparison, with round trips of 0.2 ms inside a zone and 1.0 ms
across zones. The leaderless put answered in 1.30 ms, because its coordinator was in the client’s zone. The leader of
user:42 was in zone b, so the same put went there first:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- To the leader, wherever it is. Every write of the shard goes to its leader, b5, in zone b. The request arrives at 0.50 ms, half a cross-zone round trip.
- The leader's log. b5 appends the write to its log and sends the entry to both followers.
- A majority. The first follower's acknowledgement makes a majority with the leader's own copy, so the entry is committed at 1.60 ms.
- The answer comes back. The answer reaches the client at 2.10 ms, 0.80 ms later than the leaderless put, because the leader was in another zone.
- A read from the leader alone. With a valid lease, the leader answers a consistent get by itself, without asking the followers, at 1.05 ms.
- One copy answers. One replica's answer is cheaper than the leaderless read's two. Over all 30,000 keys, puts averaged 1.83 ms here and 1.30 ms leaderless, because two leaders in three were in another zone.
That put took 2.10 ms. Two leaders in three were in another zone, so across all 30,000 keys puts averaged 1.83 ms against 1.30 ms leaderless, about half a millisecond more. The lease read went the other way: one copy answered, in 1.05 ms against 1.25 ms for the quorum read, which waits for a second reply.
Checkpoint
Check: What each path costs on the model
Practise: choose a key’s replicas, one per zone
Write the zone-aware walk from the placement section, then test yourself on the first design:
Exercise · Medium · Python
Choose a key's replicas, one per zone
Write replicas(ring, key_position, n) in replicas.py. It returns the nodes that store a key, the key's preference list, so that losing one zone never takes more than one copy.
ring is a list of (position, node, zone) tuples sorted by position; a node appears once for each of its tokens. Start at the first token whose position is at or after key_position, going round past the last token to the first, and walk the ring once:
- take a node the first time you meet it, unless a node already taken is in the same zone;
- stop as soon as you have
nnodes.
If one walk finds fewer than n nodes, because the ring has fewer zones than n, walk once more from the same start and add the nodes not taken yet, in the order you meet them: two copies then share a zone, as few as possible. If the ring has fewer than n nodes, return all of them. An empty ring returns [].
On the ring [(10, "a1", "a"), (20, "a2", "a"), (30, "b1", "b"), (40, "a3", "a"), (50, "c1", "c"), (60, "b2", "b")], position 15 gives ["a2", "b1", "c1"] for three replicas: the walk takes a2 at 20 and b1 at 30, skips a3 at 40 because zone a already has a copy, and takes c1 at 50.
Starter code · replicas.py
import bisect
def replicas(ring, key_position, n):
"""The key's n replicas: clockwise from key_position, one node per zone while zones last."""
# Replace this line with your code.
return []The sample tests · test_replicas.py
from replicas import replicas
RING = [(10, "a1", "a"), (20, "a2", "a"), (30, "b1", "b"), (40, "a3", "a"), (50, "c1", "c"), (60, "b2", "b")]
def test_one_replica_per_zone():
"""a3 is skipped: zone a already holds a copy"""
assert replicas(RING, 15, 3) == ["a2", "b1", "c1"]
def test_starts_at_a_token_with_the_same_position():
"""a key at 30 starts at the token at 30"""
assert replicas(RING, 30, 3) == ["b1", "a3", "c1"]
def test_wraps_past_the_last_token():
"""after 60 the walk goes on at 10"""
assert replicas(RING, 55, 3) == ["b2", "a1", "c1"]
assert replicas(RING, 99, 2) == ["a1", "b1"]
def test_tokens_of_one_node_count_once():
"""a node with several tokens is one replica"""
ring = [(10, "a1", "a"), (20, "a1", "a"), (30, "b1", "b"), (40, "b1", "b"), (50, "c1", "c")]
assert replicas(ring, 5, 3) == ["a1", "b1", "c1"]
def test_fewer_zones_than_replicas():
"""two zones for three copies: the third copy goes to the next node not taken"""
ring = [(10, "a1", "a"), (20, "a2", "a"), (30, "b1", "b"), (40, "b2", "b")]
assert replicas(ring, 15, 3) == ["a2", "b1", "b2"]
def test_small_and_empty_rings():
"""never more nodes than the ring has, and nothing from an empty ring"""
assert replicas([(10, "a1", "a"), (20, "b1", "b")], 0, 3) == ["a1", "b1"]
assert replicas([], 42, 3) == []A hint
bisect.bisect_left([p for p, _, _ in ring], key_position) gives the index of the first token at or after the key; when it equals len(ring), the walk starts again at index 0, so use (start + step) % len(ring) for step 0, 1, …, len(ring) - 1. Keep the zones you have used in a set, and write the walk as a loop you can run twice: the first time it checks zones, the second time it only skips nodes already taken.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Practice that adapts to you
Practise this lesson
10 questions about 12 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
The deep dives this design must answer
The first design leaves the second half of a round: the failures it must survive, measured; what a leader costs; and the storage engine, membership and tests underneath both designs.
Failure drills on the leaderless design, measured Pro: opens with a Pro, Premium or Ultimate pass
A store earns its keep in the hours when replicas are missing. This part runs three failures through the leaderless design, counts what each one costs and turns the counts into operating rules.
In this part:
- A replica that stays down past the hint window
- Deleted keys that come back after a long outage
- Clocks against version vectors: lost updates, measured
- The failure drills at a glance
1 diagram · 1 runnable example (Python) · about 9 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
A leader per shard, priced: tails, failover and hot shards Pro: opens with a Pro, Premium or Ultimate pass
A leader per shard gives every write one order, at the price of an extra hop and of one replica that must not stall. This part measures both and covers the leases, splits and conditional writes that come with a leader.
In this part:
- What a leader costs: the extra hop, the single reader and the failover pause
- Splitting a hot shard, with numbers
- Conditional writes in each design
1 diagram · 1 runnable example (Python) · about 7 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Storage engine, membership, testing and the level rubric Pro: opens with a Pro, Premium or Ultimate pass
The last part sizes the work under the replication protocol, tests the store the way its users will rely on it and turns the design into an answer you can give in a round.
In this part:
- Sizing the storage engine on each node, with numbers
- Membership, failure detection and adding nodes, worked
- Testing it: histories that a checker accepts or rejects
- Bottlenecks at 10× and 100×
- What each level is expected to cover
- A sample answer in ten minutes
- A 45-minute self-mock
1 runnable example · about 12 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Interview questions
Start with the warm-up, then take the three design problems, each from its first step:
-
Fresher to mid · Warm-up
How does a leaderless key-value store accept a write, and how does a store with a leader per shard?
In a leaderless store, any replica of the key can coordinate a write: it sends the write to all N replicas and answers once W of them, say 2 of 3, have stored it. No replica is special, so a slow or failed one does not stop writes, but two writes to one key can reach the replicas in different orders, and the store needs a rule to settle them: the newest timestamp, or version vectors that keep both. With a leader per shard, each key range is a consensus group, such as Raft or Multi-Paxos. Every write goes to the group's leader, which appends it to its log and answers once a majority holds it. Writes to a key are ordered, which makes conditional writes and current reads cheap, at the price of an extra hop to the leader and a pause while a failed leader is replaced.
-
Mid to senior
Two teams want the same key-value store: one for shopping carts that must accept writes even while a zone is down, one for wallet balances that must never be debited twice. Do you give them one design or two? Choose the replication design and its settings for each, with numbers.
-
Senior to staff
Customers of a leaderless store with three replicas report that items they deleted from saved lists two weeks ago are back. The application did not change, but one replica spent 12 days in repair after a disk failure and was then restarted. Explain what happened, how you fix the data and how you prevent a repeat.
-
Senior to staff
A leaderless store of 15 nodes with 2 TB disks holds 22 TB including replicas, and its p99 reads rose from 6 ms to 25 ms during compactions. You must add capacity this week without breaking a 10 ms p99. How many nodes do you add, how much data moves, and how do you do it?
Key takeaways
- A key-value store is three decisions: partitioning, replica placement and how the copies agree.
- 5.5 TB of data becomes 16.5 TB of copies, and disk space sets the 15 nodes.
- A conditional put stores only while the key is at the version the caller read; a delete writes a tombstone.
- One copy per zone and 256 tokens per node keep a zone outage from taking a quorum and the busiest node near the average.
- Leaderless writes wait for any 2 of 3 replicas; a leader orders every write and answers once a majority has it.
- In the model, a leader in another zone two times in three raised the average put from 1.30 ms to 1.83 ms.
References
- Dynamo: Amazon's Highly Available Key-value Store (ACM SOSP (authors' copy))
- Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (USENIX ATC)
- In Search of an Understandable Consensus Algorithm (Raft, extended version) (Diego Ongaro and John Ousterhout)
- Apache Cassandra documentation: Dynamo (The Apache Software Foundation)
- Apache Cassandra documentation: Hints (The Apache Software Foundation)
- Apache Cassandra documentation: Repair (The Apache Software Foundation)
- Apache Cassandra documentation: Data manipulation (conditional statements) (The Apache Software Foundation)
- Best practices for designing and using partition keys effectively in DynamoDB (Amazon Web Services)
- RocksDB Overview (The RocksDB project (Meta))
- Linearizability (Jepsen consistency models) (Jepsen)
- RFC 9110: HTTP Semantics, section 13 (conditional requests) (IETF)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress