Design a Distributed Key-Value Store (Dynamo)

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Clients (or a thin smart-client library) send requests to any node. Every node knows the full ring via gossip, so a node receiving a request either coordinates it directly or forwards it to a natural coordinator. There is no master, no config service on the hot path, and therefore no single point of failure.

Placement uses consistent hashing: keys hash onto a ring of tokens, each physical node owns many virtual-node tokens, and a key's preference list is the next N distinct physical nodes clockwise from its hash. Virtual nodes make load and rebalancing granular; when a node joins it takes small slices from everyone rather than half of one neighbor's range.

A write goes to the coordinator, which stamps the vector clock, sends it to all N preference-list replicas, and acks the client after W responses. A read fans out to the preference list and returns after R responses; if the responses disagree, the coordinator returns the causally latest version, or all concurrent siblings, and performs read repair by writing the winner back to stale replicas.

Each replica persists writes to a local LSM-tree storage engine: append to a commit log, apply to an in-memory memtable, flush to immutable SSTables, and compact in the background. This makes the per-node write path sequential I/O, which is what sustains high write throughput on commodity disks.

Failures are handled in layers: sloppy quorum with hinted handoff keeps writes flowing when a replica is briefly down; anti-entropy with merkle trees repairs longer divergence; and gossip-based membership with failure detection tells everyone which layer applies. Together these implement 'always writable' without a coordinator database.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Write the consistent-hash Ring class with ~100 vnodes per node; unit test that removing a node remaps only about 1/N of 10K sample keys.
2. 02Build a FastAPI node exposing internal GET/PUT /local/{key} backed by a SQLite table (key, value, version).
3. 03Add coordinator logic: any node computes the preference list for a key and fans the PUT to N=3 replicas, acking the client after W=2 responses.
4. 04Implement quorum GET: read from R=2 replicas, return the highest version, and write it back to any stale replica (read repair).
5. 05Bring up 3 nodes with docker-compose, kill one, and verify reads and writes still succeed at R=W=2.
6. 06Add hinted handoff: when a replica is down, write to the next healthy ring node with a hint row, and replay hints on a background timer.
7. 07Add GET /admin/ring showing token ownership and a smoke script that writes 10K keys and checks the distribution is roughly even.

import hashlib
from bisect import bisect_right

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.tokens = []  # sorted (hash, node) pairs
        for node in nodes:
            for i in range(vnodes):
                self.tokens.append((self._hash(node + ":" + str(i)), node))
        self.tokens.sort()

    @staticmethod
    def _hash(s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def preference_list(self, key, n=3):
        idx = bisect_right(self.tokens, (self._hash(key), chr(0)))
        picked = []
        for i in range(len(self.tokens)):
            node = self.tokens[(idx + i) % len(self.tokens)][1]
            if node not in picked:  # skip vnodes of already-chosen hosts
                picked.append(node)
            if len(picked) == n:
                break
        return picked

async def quorum_get(ring, key, r=2, n=3):
    replies = []
    for node in ring.preference_list(key, n):
        try:
            # each reply: {"value": ..., "version": int}
            replies.append((node, await http_get(node, key)))
        except Exception:
            continue  # dead replica, try the next one
        if len(replies) >= r:
            break
    if len(replies) < r:
        raise QuorumError("read quorum failed: " + str(len(replies)))
    newest = max(replies, key=lambda p: p[1]["version"])[1]
    for node, reply in replies:
        if reply["version"] < newest["version"]:
            # read repair: push the winner back to stale replicas
            await http_put(node, key, newest)
    return newest

async def quorum_put(ring, key, value, version, w=2, n=3):
    item = {"value": value, "version": version + 1}
    acks = 0
    for node in ring.preference_list(key, n):
        try:
            await http_put(node, key, item)
            acks += 1
        except Exception:
            continue
    if acks < w:
        raise QuorumError("write quorum failed")
    return item