Distributed Systems Reference/Optional Coding Practice

Placement & Consistent Hashing

Implement a hash ring in memory — the same primitive behind Dynamo, Cassandra, and cache clients.

3/5Overview: 15m

Why code a hash ring?

Partitioning theory (Topic 4) explains when to shard. Consistent hashing is how many systems place keys with minimal remapping when nodes join or leave. Interviewers often ask you to sketch or implement the ring — not deploy Cassandra.

This subtopic is in-memory only: one process, sorted map or array, deterministic hash. No sockets, no Docker, no cloud.

Mental model

  1. Hash every key and every virtual node to a 32-bit integer.
  2. Sort virtual-node positions on a circle.
  3. get_server(key) = first virtual node at or after H(key), wrapping to the smallest position if needed.
  4. Adding a server inserts its virtual nodes; removing deletes them. Only keys in the affected arcs move.

What interviewers probe

  • Why virtual nodes? (spread load evenly — without them, a physical node owning a large arc becomes hot.)
  • What happens on node add/remove? (~K/N keys move, not all K.)
  • How is this different from hash(key) % N? (modulo remaps everything when N changes.)

Practice order

  1. Play with the ring visualizer in Further Reading — build intuition before coding.
  2. Implement ConsistentHashRing per the task spec (unit tests are your grader).
  3. Optional: compare your implementation to Topic 4 partitioning strategies verbally — when would you still pick range partitioning over a ring?

Further Reading

Coding Exercises (Optional)

In-memory specs — implement locally with unit tests. No cluster, Docker, or cloud setup unless a task says otherwise.

  • Code: ConsistentHashRing with virtual nodes

    Implement a class in your language of choice (no network, no threads). API: `add_server(server_id)`, `remove_server(server_id)`, `get_server(key)` → server id or null if the ring is empty. Use 100 virtual nodes per physical server at positions `hash(server_id + "#" + i)` for i in 0..99. Use this deterministic 32-bit hash so results are reproducible: `H(s) = sum((index + 1) * ord(s[index])) mod 2^32`. Store virtual-node positions in a sorted structure; `get_server(key)` finds the first position ≥ H(key) clockwise (wrap to smallest if none). On hash collision, break ties by replica token `server_id#i`. Write unit tests: empty ring → null; single server; add second server only moves ~half of sample keys; remove server. Target ~45 minutes.

    45m