Design Consistent Hashing

Hash Ring System Design

Overview

You have a cluster of cache servers — or database shards, or message-queue partitions — and you need to decide which server owns which key. The obvious rule is hash(key) % N, where N is the node count. It works fine until N changes. Remove a crashed node or add a new one, and almost every key remaps: hash(key) % 3 produces a completely different distribution from hash(key) % 4. For a cache cluster, that means a near-total cache miss storm the moment you scale. For a database cluster, it means a massive data migration that can take hours.

Consistent hashing fixes this. Both keys and nodes are mapped onto the same ring (a circular space, say 0 to 2³²−1). A key is owned by the first node clockwise from its position on the ring. When you add a node, it takes over the arc just behind it — only those keys move; every other key is unaffected. When you remove a node, its arc is absorbed by the next node clockwise. In either case, only ~1/N of the total keys change hands.

This is labeled "Easy" because the core idea is compact, and the question tests whether you can explain why the naïve approach is broken, articulate the ring construction precisely, and then reason about the practical fixes (virtual nodes, replication). It comes up in almost every distributed-cache or partitioning design — the distributed-cache breakdown, the Dynamo/Cassandra data model, and the message-queue partitioning design all build on it directly.

Out of scope: the full distributed-cache system (read/write paths, eviction, TTL — covered in the distributed-cache guide), database replication lag, and the client-side load-balancing library that hosts the ring. This guide covers the ring algorithm and its operational properties.

Functional requirements

• Key → node lookup. Given a key, return the node responsible for it. This must be fast — O(log V), where V is the total ring positions, or better.
• Add a node. When a new node joins the cluster, redistribute the minimum number of keys needed to incorporate it. Existing keys that do not land in the new node's arc must not move.
• Remove a node. When a node leaves (planned or crashed), hand its keys to the next node clockwise. No other keys should move.
• Replication. Optionally store each key on R distinct physical nodes for fault tolerance.

Out of scope: the transport layer (how keys actually move between nodes), node health-checking beyond "present or absent," and the consensus protocol that decides the ring membership. We own only the mapping algorithm.

Non-functional requirements

• Minimal disruption. Adding or removing a node should move roughly 1/N of all keys — not a fraction proportional to total data size in the worst case (the naïve modulo failure mode).
• Even load distribution. Each node should own approximately the same fraction of the keyspace. Without virtual nodes, a node's share is determined by where it landed on the ring, which is essentially random and highly uneven in small clusters.
• Lookup performance. The ring state is read on every key access. O(log V) lookup over V ring positions is needed, not O(V) linear scan.
• Heterogeneous node support. A larger or newer node should be able to claim a proportionally larger share of the ring — i.e. receive more virtual nodes.

Estimations

The math here is lightweight — what matters is justifying the virtual-node count and understanding how numbers affect the design.

Rounded assumptions

• Physical nodes N: 10–100 (typical cache cluster or DB shard group).
• Virtual nodes per physical node V_per: 100–200 positions per physical node.
• Total ring positions V: N × V_per → 1,000–20,000 entries in the sorted ring structure.
• Lookup cost: binary search over V entries → O(log V) ≈ 10–15 comparisons — negligible.

How the numbers affect the design

Core entities / data model

The ring state is maintained in every node (or in a central coordinator) and has three building blocks.

The ring is a sorted collection of RingEntry records, keyed by their position in [0, 2³²). Adding a physical node inserts weight new entries (one per vnode); removing it deletes them. The sorted structure supports O(log V) successor lookup: "find the smallest position ≥ hash(key)."

Positions are derived, not random. Each vnode's position is computed deterministically: hash(node_id + ":" + vnode_index). This means any node that knows the cluster membership can reconstruct the full ring locally without a broadcast — membership is the only shared state.

ReplicaSet is not stored — it is computed on every lookup by walking the ring clockwise from hash(key) and collecting the first R distinct physical nodes (skipping duplicate vnodes of a node you have already included). The replication walk is a design decision expanded in deep dive 2.

API design

Three operations carry the system: lookup, add, and remove. These are the interfaces a library or service exposes to the application.

Get the node(s) responsible for a key

getNode(key: string) → NodeAddress
getNodes(key: string, replicationFactor: int) → List<NodeAddress>

getNode returns the primary owner. getNodes returns an ordered preference list of R distinct physical nodes for replication. Both are pure in-memory reads: hash the key, binary-search the sorted ring, walk clockwise for R. No network call.

Add a node

addNode(nodeId: string, address: string, weight: int) → RingDiff

Inserts weight new vnode entries for nodeId. Returns a RingDiff describing which key ranges move (from the successor of each new entry to the new entry itself). The caller uses this diff to migrate only those keys. Returns immediately; data migration is the caller's responsibility.

Remove a node

removeNode(nodeId: string) → RingDiff

Deletes all vnode entries for nodeId. Returns a RingDiff of the affected arc (from each removed entry's predecessor to its successor). Keys in that arc now map to the successor node. Again, data migration is the caller's responsibility.

Membership sync

In practice, ring state is gossiped across nodes (Dynamo/Cassandra use a gossip protocol) or stored in a coordination service (ZooKeeper, etcd). The API above is the logical interface; the transport is out of scope here.

High-level architecture

The ring is consulted on every key access, so it lives in-process (or in a sidecar) on every application node — not in a remote service. The architecture has three layers: the ring data structure, the membership plane that propagates changes, and the data plane where actual keys are stored.

1. The ring data structure

flowchart LR
    Key["hash(key)\n= position P"] -->|"binary search\nsorted ring"| Ring["Sorted Ring\n[pos → node]"]
    Ring -->|"first entry ≥ P\n(clockwise)"| Owner["Primary node"]
    Ring -->|"next R−1\ndistinct physical nodes"| Replicas["Replica nodes\n(R−1 more)"]

1. Hash the key to a position P in [0, 2³²).
2. Binary-search the sorted ring for the first entry with position ≥ P (wrap around to position 0 if P is past the last entry).
3. That entry's node_id is the primary owner.
4. Walk clockwise, skipping entries that belong to a physical node already in the set, until you have R distinct physical nodes — that is the preference list.

2. Adding a node — only one arc moves

flowchart LR
    subgraph Before["Before: nodes A, B, C"]
        direction LR
        A1["A\n(pos 100)"] --> B1["B\n(pos 200)"] --> C1["C\n(pos 300)"] --> A1
    end
    subgraph After["After: node D added at pos 250"]
        direction LR
        A2["A\n(pos 100)"] --> B2["B\n(pos 200)"] --> D2["D\n(pos 250)"] --> C2["C\n(pos 300)"] --> A2
    end
    Before -->|"keys in arc (200, 250]\nmove C → D"| After

Before D joins, keys in arc (200, 300] all belong to C. After D joins at position 250, keys in (200, 250] belong to D — those migrate from C. Keys in (250, 300] still belong to C. Everything else is untouched. Only the arc (200, 250] moves: roughly 1/N of the total if positions were evenly spaced.

3. Combined architecture (with virtual nodes)

Real rings use many vnodes per physical node. The picture below shows a 3-node cluster with 3 vnodes each — enough to illustrate that each physical node's load is spread across many arcs rather than one.

flowchart LR
    subgraph Ring["Hash Ring (0 → 2³²) — C-3 wraps back to A-1"]
        direction LR
        A1["A-1\n(pos 40)"] --> B1["B-1\n(pos 80)"] --> C1["C-1\n(pos 120)"]
        C1 --> A2["A-2\n(pos 160)"] --> B2["B-2\n(pos 220)"] --> C2["C-2\n(pos 270)"]
        C2 --> A3["A-3\n(pos 310)"] --> B3["B-3\n(pos 350)"] --> C3["C-3\n(pos 390)"]
        C3 -->|"wraps to start"| A1
    end

The chain above renders left-to-right for readability; in the actual ring the last node (C-3) wraps clockwise back to the first (A-1), closing the circle.

flowchart TD
    K1["key 'user:42'\nhash → 195"] -->|"binary-search ring"| S1["successor = B-2\n(pos 220)"]
    S1 --> N1["route to Node B"]
    K2["key 'order:99'\nhash → 330"] -->|"binary-search ring"| S2["successor = B-3\n(pos 350)"]
    S2 --> N2["route to Node B"]

Node B owns arcs ending at B-1, B-2, and B-3 — three spread-out slices, not one contiguous block. Adding or removing B affects three small arcs instead of one potentially large one.

Deep dives

1. The ring and virtual nodes — why one position per node is not enough

The fundamental problem with a single ring position per physical node is load variance. With N nodes and each at a random position, the arc lengths follow an exponential distribution. In expectation, each node owns 1/N of the ring — but the variance is high:

N = 10, one position per node:
  min arc length observed in practice: ~2% of ring
  max arc length observed in practice: ~30% of ring
  → one node can hold 3× the load of another

N = 10, 150 vnodes per node:
  positions per node = 150, total ring entries = 1,500
  load std-dev ≈ 1/√150 ≈ 8%  → within 10% of target for almost all nodes

Node at 90:   owns arc (350, 90] = 140 units  (35% of ring)
Node at 100:  owns arc (90, 100]  =  10 units  ( 2.5%)
Node at 200:  owns arc (100, 200] = 100 units  (25%)
Node at 350:  owns arc (200, 350] = 150 units  (37.5%)

flowchart LR
    subgraph Physical["Physical nodes"]
        A["Node A\n(weight=1)"]
        B["Node B\n(weight=2)"]
    end
    subgraph Ring["Ring entries"]
        A --> VA1["A-0\nA-1\n… A-149\n(150 positions)"]
        B --> VB1["B-0\nB-1\n… B-299\n(300 positions)"]
    end
    Ring -->|"total 450 entries\nB owns ~66%"| Total["Key distribution\nA ≈ 33%\nB ≈ 67%"]

The lookup structure. The ring is stored as a sorted array (or a language-native TreeMap/SortedMap) of (position, node_id) pairs. Lookup is a binary search: lowerBound(hash(key)), wrapping to index 0 if past the last entry. This is O(log V) and typically 10–15 comparisons — fast enough for in-process use with no caching needed.

2. Replication and fault tolerance — the preference list

Consistent hashing tells you which single node owns a key. Replication requires storing the key on R distinct physical nodes so it survives individual node failures. The standard approach is to walk the ring clockwise from hash(key) and collect the first R distinct physical nodes — the preference list.

Why "distinct physical" matters. Without this rule, a key whose primary is node A might have its second replica at A-3 (another vnode of A) — providing no fault tolerance at all. The walk must skip any ring position belonging to a physical node already in the preference list.

What happens when a node fails?

flowchart LR
    subgraph Normal["Normal: A, B, C all up; R=2"]
        K1["key → pos 150"] -->|"primary"| B_n["B (pos 200)"]
        K1 -->|"replica"| C_n["C (pos 300)"]
    end
    subgraph Failure["Node B fails; hinted handoff"]
        K2["key → pos 150"] -->|"primary arc\nnow goes to C"| C_f["C (new primary)"]
        K2 -->|"hinted handoff\n(temp replica)"| D_f["D (next available)"]
        C_f -.->|"B rejoins →\nhand back B's arc"| B_f["B"]
    end
    Normal --> Failure

When B fails, C absorbs B's arc (B's vnodes disappear from the ring, so keys route to the next available node clockwise). To maintain R replicas, the system uses hinted handoff — a substitute node D holds the key with a metadata note ("this belongs to B"). When B recovers and re-enters the ring, D forwards the data back. This ensures availability during transient failures without a permanent change to the ring.

Node joins — minimal movement.

When a new node X joins, it inserts its vnodes into the ring. For each new vnode at position P, the arc (P's predecessor, P] now belongs to X — those keys must migrate from X's successor (who previously owned that arc) to X. No other keys move. The total migration is:

keys migrated ≈ (total keys) × (V_per / V_total) = (total keys) / N_after

(assuming equal weights; for heterogeneous weights the moved fraction is W/(T+W), where W is the new node's weight and T the existing total weight)

With 10 nodes and one node joining, roughly 1/11 of all keys migrate — exactly the theoretical minimum. With naive hash % N, roughly (N−1)/N of all keys would move.

Rebalancing after join. The preferred approach is for the joining node to pull data for each of its new arcs from the current owners, not for the old owners to push. This keeps the migration load on the new node (which has spare capacity) rather than on established nodes serving live traffic.

3. Load balancing, hot spots, and weighted nodes

Even with virtual nodes, certain workloads can create hot spots — not because the ring is unbalanced in its key allocation, but because certain keys are simply accessed far more often than others.

Symmetric vs. asymmetric access patterns. Consistent hashing guarantees balanced storage distribution across nodes. It does not guarantee balanced request distribution if access is skewed. A viral cache key or a celebrity user's ID may receive 10,000× the requests of the average key — it still maps to one node, which becomes the bottleneck regardless of virtual-node count.

flowchart LR
    Key["hash(key) → pos P"] --> Primary["Primary node\n(clockwise successor)"]
    Primary -->|"capacity check:\nload < threshold?"| Accept["Accept key\n(normal path)"]
    Primary -->|"overloaded"| Next["Walk to next\navailable node"]
    Next --> Accept

The minimal-movement property holds regardless of weighting — a new node of weight W joining total weight T claims exactly W/(T+W) of the keyspace (≈ 1/(N+1) for an average-weight node). The keys it claims come from their former owners' arcs. No node that did not neighbor one of the new node's vnodes loses any keys.

Tradeoffs & bottlenecks

• Minimal movement vs. absolute uniformity. Consistent hashing minimizes key movement on topology changes but cannot guarantee perfect uniformity — especially with few nodes. Virtual nodes improve uniformity at the cost of more ring entries and more migration arcs per topology change.
• Virtual node count. Too few (< 50) → high variance; too many (> 500) → ring gossip overhead, finer migration granularity without much benefit. The sweet spot of 100–200 is well-validated in production Dynamo/Cassandra deployments.
• Replication walk skips physical node duplicates. Correctly implementing the preference list (skipping same physical node's vnodes) is easy to get wrong: a naive "next R ring positions" walk can put two replicas on the same physical node.
• Ring state consistency across nodes. All nodes must agree on ring membership or they will route to different owners. Gossip protocols (Cassandra, Dynamo) converge in seconds; during convergence, briefly inconsistent routing is possible. This is why the system is eventually consistent at the routing layer.
• Hinted handoff correctness. A hint that is never delivered (the original node never recovers) can leave data stranded on the substitute. Dynamo/Cassandra run anti-entropy reconciliation (Merkle-tree-based repair) to catch and fix this.
• Hot spots from access skew. As noted in deep dive 3, consistent hashing addresses storage distribution, not request-rate distribution. Hot keys need separate mitigation.

Extensions if asked

If the interviewer wants to push beyond the core ring algorithm, add only the extension that changes the design discussion:

• Jump consistent hash. A mathematical function (no ring data structure) that maps a key to one of N buckets in O(1) time and O(1) space, with minimal remapping when N changes. The tradeoff: no virtual-node weighting; and critically, only the highest-numbered bucket can ever be removed — because bucket assignment is derived from the bucket count itself (not from ring positions), removing a middle bucket would renumber all higher buckets and remap their keys, breaking the minimal-movement guarantee. Excellent for stateless worker pools where nodes fail by being decommissioned in order; unsuitable for heterogeneous or failure-prone clusters where arbitrary removal is needed.
• Rendezvous (HRW) hashing. For each key, score all N nodes as hash(key, node_id) and pick the highest-scoring node. Same minimal-movement property as consistent hashing; O(N) lookup (hash all nodes) instead of O(log V). Simpler to implement but slower at scale. Good for small N where simplicity wins.
• Bounded-load consistent hashing. Adds a per-node load cap (covered in deep dive 3). Useful when access skew is predictable and you want the routing layer itself to handle hot spots.

What interviewers look for & common mistakes

What interviewers usually reward:

• Motivating the problem clearly — showing that hash(key) % N remaps ~(N−1)/N keys on a topology change, and explaining why that is catastrophic for a cache cluster (miss storm) or a database cluster (mass migration).
• Explaining the ring precisely — hashing both keys and nodes onto the same space, clockwise successor lookup, and the O(log V) sorted-structure implementation.
• Reaching for virtual nodes unprompted — explaining that one position per node creates severe load imbalance, and that V_per ≈ 150 vnodes per node smooths the distribution by √V_per.
• Correctly walking the preference list — when describing replication, specifying that the walk skips same-physical-node vnodes so R replicas land on R distinct machines.
• Connecting to real systems — noting that Dynamo (Amazon), Cassandra, and most distributed caches use consistent hashing with vnodes, and cross-referencing it to the distributed-cache or Cassandra design questions.
• Distinguishing distribution from access skew — knowing that consistent hashing solves the former, not the latter, and naming the hot-key fix separately.

Before you finish, do a quick mistake check:

• Did you motivate consistent hashing with the hash % N failure mode — not just say "it's better"?
• Did you describe the ring as mapping both keys and nodes to the same hash space?
• Did you specify that lookup is the clockwise successor, not nearest neighbor?
• Did you name virtual nodes as essential (not optional), and explain why they reduce variance?
• Did you walk the preference list correctly — R distinct physical nodes, skipping vnode duplicates?
• Did you separate the ring's load-distribution guarantee from the application-layer hot-key problem?
• Did you mention that Dynamo/Cassandra use this, connecting to the broader distributed-systems design context?