Partitioning and replication

The diagram. The ring in the middle: the dots are the nodes' tokens at their true hash positions, each arc coloured by the node that owns it; the black dot is the focused key (cart:alice unless you pick another), with its preference list printed in the centre and its replicas outlined in the node’s colour. Around it, one card per node: its keys, the hinted writes it holds for others, and the focused key’s versions with their vector clocks (two side by side are siblings). Two clients at the top. Messages are labelled: put k=v, put k (hint N3), ack, read k, the versions a replica returns, repair k, handoff, Merkle root hash / level 2 exchanges and sync. Tap a node to crash or restart it, isolate it, send a request through it or run anti-entropy with a neighbour; tap a client to put or get.

Do something. Put and get as either client on any of six keys; set R and W; switch between sloppy and strict quorums; crash, restart, isolate, heal; drop the next write to a node; compare Merkle trees between any two nodes.

Replicas of each key: every key’s preference list and every node’s versions (green when the replicas agree). Merkle trees: both trees of the last anti-entropy exchange, with the hashes that differ in red and the ones never compared dashed. Requests: each request, its coordinator, the result and the latency.

Settings: nodes, tokens per node, N, R, W, latency, jitter, sloppy quorum, read repair, seed.

Consistent hashing (Karger et al. 1997): nodes and keys hashed onto a 32-bit circle (FNV-1a with the murmur3 finaliser); a key belongs to the first token clockwise; each node may have v tokens (virtual nodes). A node’s share is then a sum of v random arcs, so its coefficient of variation is about 1/√v.

Rendezvous hashing (Thaler & Ravishankar 1998): each node scores (node, key) with a hash and the highest score wins.

Jump consistent hash (Lamping & Veach 2014): the paper’s function exactly, with its 64-bit linear congruential generator (BigInt in the page), checked against published test vectors. Buckets are numbered, so only the last can be removed.

Maglev (Eisenbud et al., NSDI 2016): permutations from offset = h₁ mod M and skip = h₂ mod (M − 1) + 1, and the table filled by Pseudocode 1 (M = 65537 for the statistics, 13 for the drawing) — checked against the paper’s Table 1.

Dynamo (§4): the preference list is the next N distinct nodes clockwise (skipping further tokens of a chosen node). A client sends to the first healthy node of the key’s list, which coordinates: for a put it builds a new vector clock from the client’s context and its own counter, writes locally and sends to the others, answering after W acknowledgements; for a get it asks the N replicas, answers after R, and returns every version it cannot order (syntactic reconciliation — siblings are the client’s to merge). With a sloppy quorum, unreachable replicas are replaced by the next healthy nodes, which store the write with a hint and hand it off when the owner is reachable again (§4.6). Read repair: once every replica asked has answered, stale ones get the newest versions. Anti-entropy (§4.7): two replicas build Merkle trees (Merkle 1987) over the keys they share — leaves hash the (key, version) pairs in one slice of the hash space — compare them top down, and exchange only the keys under differing leaves. A read is flagged stale when none of its versions is the newest acknowledged write or concurrent with it.

Partial quorums (Bailis et al., Probabilistically Bounded Staleness, VLDB 2012): the WARS model by seeded Monte Carlo — per replica a write delay W, an acknowledgement A, a read request R and a response S, drawn from the chosen distribution with the given means; a write commits at the W-th fastest W + A; a read takes the R fastest R + S and is consistent if one came from a replica the write reached first.

Nodes join and leave only in the Placement tab; the Dynamo ring is fixed for a run (Dynamo’s partition-transfer on membership change is not simulated), and tokens are random (not Dynamo’s later equal-size partitions, §6.2).

Vector clocks are never truncated (§4.4 truncates them past 10 entries); there is no gossip-based membership or failure detection — a node is down or up, and the coordinator knows it instantly.

Anti-entropy compares the keys two nodes share in one tree (Dynamo keeps one tree per key range); trees are rebuilt for each exchange.

The latency explorer assumes independent, identically distributed legs per replica and a coordinator that sends to all N replicas — the model and assumptions of the PBS paper, not measurements of a real system.