A distributed data structure is a classic structure made robust to partial failure and evolution: every node holds a partial view, every operation must produce a consistent answer despite some nodes being unreachable, and the structure holds across reconfigurations. Consensus protocols (Paxos, Raft) answer agreement. The structures in this topic answer placement, parity, and parity verification — the everyday machinery behind Dynamo, Cassandra, Riak, and any ring- or hash-partitioned store.

Consistent Hashing

A normal hash map says: slot = hash(key) % N. The moment N changes — adding a node, losing a node — slot moves for every key. At scale, re-shuffling every key is catastrophe.

Consistent hashing distributes keys such that adding or removing one node moves only K/N keys — the average fair share — instead of all of them. The structure: imagine a ring from 0 to 2^k - 1. Each node takes a position on the ring (hash(node_id)). The node owning a key is the next node clockwise from hash(key).

   hash(nodeA)   hash(nodeB)   hash(nodeC)        hash(nodeD)
        |             |             |                   |
   ─────●─────────────●─────────────●───────────────────●───────→
        key1 → nodeA (clockwise from hash(key1) lands at A)
   key2 → nodeB

• Adding nodeE between A and B moves only the keys between A and E (a sliver) — nowhere else.
• Removing nodeB moves only B’s keys to C (its clockwise neighbour).

Virtual Nodes

Real hardware is uneven. If each physical node gets one ring position, a powerful 64-core node and a tired 2-core node each get the same key share. Virtual nodes fix this: each physical node claims many (typically 100–200) ring positions, distributing the workload roughly fairly via the law of large numbers.

The trade off: more virtual nodes means larger routing tables and slower membership changes, but smaller per-rebalance movements.

Rendezvous Hashing (HRW)

Rendezvous hashing (Highest Random Weight) is the alternative to consistent hashing when you don’t want to maintain a ring. Each key is assigned to the node that maximises hash(key, node) over all nodes.

• No ring to maintain; adding or removing a node is O(1) datastructure change.
• Lookup is O(N) per key — heavier than a ring’s O(log N).
• Used where the number of replicas is small and the routing is client-side (CDN cache selection, sharded JDBC proxies).

Merkle Trees for Anti-Entropy

Two replicas that should hold the same data will drift — disk flak, network hiccups, dropped writes. Merkle trees let two nodes compare terabytes of data in seconds.

The structure is a hash tree: leaves are hashes of data records (or record ranges); internal nodes are hashes of their children. Comparing two replicas is comparing the root hash — O(1). Where roots differ, walk down only the divergent subtrees, exchanging O(log n) hashes to localise the difference.

            root = h(h_AB + h_CD)
          /                      \
     h_AB = h(h_A + h_B)     h_CD = h(h_C + h_D)
    /            \              /            \
  h_A          h_B            h_C          h_D
   ↑            ↑              ↑            ↑
blk_A        blk_B          blk_C        blk_D

In Dynamo-family systems, each token range is the root of a Merkle tree; two replicas exchange range roots and re-fetch only the ranges whose roots differ. Without this, anti-entropy would be full-table scans at every reconciliation — infeasible past gigabytes.

Gossip and SWIM

Membership — who is alive? — is the simplest-sounding distributed problem, and the hardest. Centralised heartbeats are a single point of failure; broadcasting keeps every node pinging every other, which doesn’t scale past ~50 nodes. Gossip solves it: each node periodically tells a few random peers its current view of the world; views spread exponentially like an epidemic.

• Gossip heartbeat — each node increments a counter; views propagate node → counter pairs. Members are declared suspect when their counter stalls, then dead after a grace period.
• SWIM — a refinement: instead of full view spread, each round a node pings one random member; if it fails, it asks k others to ping it indirectly. The result of the indirect ping is gossiped rather than the raw view. SWIM reduces bandwidth and false positives.

Failure detectors using either scheme obey the same truth: a “dead” verdict is probabilistic, not certain. The system must tolerate the case where a node returns after being declared dead — typically via incarnation numbers (a counter that lets the returned node prove it is it, not a stale rumour).

Vector Clocks for Causality

Two writes to the same key, on two nodes, in a partition — when the partition heals, which wins? “Last write wins” by wall clock is a lie: clocks drift millisecond to second; ordering on them is wrong.

A vector clock is a per-key map {node → counter}; each write increments the writer’s counter. The rules:

• A → B (A causally precedes B) iff for every node, A[node] ≤ B[node] and at least one is A[node] < B[node].
• Two writes are concurrent if neither causally precedes the other; both must be reconciled (an application-defined merge, or a syntactic conflict resolver).

key=cart   N1=2     N2=1
write W1 on N1:     {N1: 2, N2: 1}
write W2 on N2:     {N1: 2, N2: 2}     ← causally after W1 (both counters ≥)
write W3 on N1:     {N1: 3, N2: 1}     ← concurrent with W2 (N1 higher, N2 lower)

Vector clocks are the mechanism Dynamo-class stores use to expose concurrency to the application rather than silently pick a winner. The cost: clock size grows with the number of writes (typically trimmed to a fixed window of recent coordinators).

Version Vectors

The cousin of vector clocks — used when the unit is versions of an object rather than events. Same shape; different framing. A version vector {replica → counter} says “the highest version this replica has seen of each object version”. Conflict resolution is the same: concurrent versions need a merge.

Practice Trajectory

1. Implement consistent hashing with virtual nodes (one ring, 5 physical nodes, 100 virtual positions each). Add a 6th physical node and verify only K/N keys move.
2. Replace it with rendezvous hashing; measure the lookup cost difference at N = 50.
3. Build a Merkle tree over 10,000 leaf records; corrupt one record; locate it in O(log n) hash comparisons.
4. Run a SWIM simulation: take 100 nodes, kill 10 randomly, observe detection time and false positives as a function of probe interval.
5. Take three concurrent writes to the same key with a vector clock; design an application merge rule (e.g., union of cart items) and verify all replicas converge to the merged value.

When It’s the Right Tool