Chapter 8: Consistent Hashing — Scaling Without the Avalanche

Curriculum: Distributed Systems from First Principles Chapter: 8 of 24 Part: 3 — Partitioning Prerequisites: Chapter 7 (sharding, hash partitioning, rebalancing problem) Estimated reading time: 75–85 minutes

Opening

Chapter 7 ended with a cliff-hanger. You want to add a shard to your cluster. With naive hash partitioning — shard = hash(key) % N — adding one shard changes the mapping for roughly half of all keys. For a 4 TB dataset, that means moving ~2 TB of data across the network before the new shard can serve any traffic. During the migration, the routing layer must track which data has moved and which hasn't, creating a dual-state nightmare that lasts hours or days. In practice, teams avoid resharding because it's so painful. The system runs hot on the existing shards. Performance degrades. Engineering time gets spent managing a migration rather than building features. This is the price of hash(key) % N.

The insight that breaks the problem: the % N operation is what causes mass movement. When N changes, it changes the output of % N for almost every key. What if instead of mapping keys to shard slots using % N, you mapped both keys and shards to positions on a fixed-size ring — and assigned each key to the nearest shard clockwise? When a shard is added, it only takes keys from its immediate clockwise neighbour. When a shard is removed, its keys migrate to its immediate clockwise successor. The total data movement is roughly total_data / new_shard_count — the theoretical minimum. This is consistent hashing, and it's why DynamoDB, Cassandra, Riak, and virtually every serious distributed cache use it.

Part 1: The Problem With hash(key) % N — Stated Precisely

Let's make the rebalancing problem concrete with numbers before we solve it.

You have a cache cluster with 4 nodes (N=4). You have 1,000,000 cached keys. Each node holds roughly 250,000 keys.

A key maps to a node via: node = hash(key) % 4

You add a 5th node. Now: node = hash(key) % 5

For a given key, the old mapping was hash(key) % 4. The new mapping is hash(key) % 5. These are the same only when hash(key) % 4 == hash(key) % 5, which for a uniformly distributed hash function is true only when hash(key) is divisible by lcm(4,5) = 20. That's roughly 1 in 20 keys, or about 5% of keys. The other 95% of keys now map to different nodes.

N=4: hash(key) % 4 outcomes: {0,1,2,3}
N=5: hash(key) % 5 outcomes: {0,1,2,3,4}

For key with hash value 12:
  Old: 12 % 4 = 0  → Node 0
  New: 12 % 5 = 2  → Node 2  ← MOVED

For key with hash value 17:
  Old: 17 % 4 = 1  → Node 1
  New: 17 % 5 = 2  → Node 2  ← MOVED

For key with hash value 20:
  Old: 20 % 4 = 0  → Node 0
  New: 20 % 5 = 0  → Node 0  ← STAYS (hash divisible by lcm(4,5)=20)

For a cache, this means ~95% of cache keys are suddenly invalid on the nodes they were on. Every request hits a cache miss and falls through to the database. If your cache was absorbing 90% of database read load, you've just sent 10× the normal load to your database — at the moment you were trying to add capacity. Many systems have been brought down by exactly this: scaling the cache cluster caused a cache stampede that took out the database.

For a database, the story is even worse — you can't just declare the data "invalid." It physically needs to be on the correct node. So every key that changed mapping needs to physically move, which takes hours for terabytes of data.

The ideal algorithm would move only the keys that need to move — the ones being reassigned to the new node. All other keys should stay put. For adding one node to an N-node cluster, the minimum data to move is total_data / (N+1) — the new node's fair share. Consistent hashing achieves this minimum.

Part 2: The Ring — A New Way to Think About Hash Space

The key insight of consistent hashing is to treat the hash space as a ring (circular space) rather than a linear array.

Take your hash function. It produces a 32-bit integer: values from 0 to 2^32 - 1 (about 4.3 billion). Instead of treating these as a line from 0 to 4.3 billion, wrap them into a circle: 0 is at 12 o'clock, 2^31 is at 6 o'clock, and 2^32 - 1 wraps back around to just before 0.

         0 (2^32)
           │
    3B ────┼──── 1B
           │
         2B
        
        (Ring: hash values 0 to 2^32-1 arranged clockwise)

Now, place both nodes and keys on this ring using the hash function:

• Each node is placed on the ring at position hash(node_identifier), where node_identifier might be the node's IP address or hostname.
• Each key is placed on the ring at position hash(key).

The assignment rule: each key belongs to the first node encountered when walking clockwise from the key's position.

                    0
                    │
          Node A    │    Node B
           (3.8B)   │   (0.9B)
                 ╲  │  ╱
    3B ────────────Ring────────── 1B
                 ╱  │  ╲
          Node D    │    Node C
           (2.8B)   │   (1.9B)
                    │
                   2B

Key at position 1.2B: walk clockwise → first node hit is Node C (1.9B) → assigned to Node C
Key at position 2.0B: walk clockwise → first node hit is Node D (2.8B) → assigned to Node D
Key at position 3.9B: walk clockwise → first node hit is Node A (3.8B)... but 3.9 > 3.8, 
                       so we wrap around → first node clockwise is Node A at 3.8B? 
                       No — 3.9B going clockwise hits 0, then Node B at 0.9B → assigned to Node B

Each node "owns" the arc of the ring between itself and its counter-clockwise neighbour. All keys that fall in Node C's arc (1.9B back to Node B at 0.9B, i.e., the arc from 0.9B to 1.9B) are Node C's responsibility.

Before reading on, try it. Each tab asks you to predict first — the next two sections explain what you'll see.

Part 3: Adding a Node — Why Only 1/N Keys Move

Now watch what happens when you add Node E to the cluster.

BEFORE (4 nodes):
Node positions: A=3.8B, B=0.9B, C=1.9B, D=2.8B

Each node's arc (the keys it owns):
  B owns: 3.8B → 0.9B  (wrapping around 0)
  C owns: 0.9B → 1.9B
  D owns: 1.9B → 2.8B
  A owns: 2.8B → 3.8B

Add Node E at position 1.4B:

AFTER (5 nodes):
Node positions: A=3.8B, B=0.9B, C=1.9B, D=2.8B, E=1.4B

New arcs:
  B owns: 3.8B → 0.9B  (UNCHANGED)
  E owns: 0.9B → 1.4B  (NEW — split from C's old arc)
  C owns: 1.4B → 1.9B  (REDUCED — lost 0.9B→1.4B to E)
  D owns: 1.9B → 2.8B  (UNCHANGED)
  A owns: 2.8B → 3.8B  (UNCHANGED)

Only the keys in the arc 0.9B–1.4B moved — from Node C to Node E. Every other key is completely unaffected. Nodes A, B, and D don't change at all. Node C loses only the portion of its arc that now falls before Node E.

Keys that moved:  those with hash(key) in [0.9B, 1.4B]
Keys that stayed: everything else

Fraction moved ≈ (1.4B - 0.9B) / 4.3B ≈ 0.5B / 4.3B ≈ 12%
                 (Node E got ~1/5 of the ring = ~1/5 of all keys)

In general, when adding the Nth node, it claims approximately 1/N of the total ring. So it receives 1/N of the total data from exactly one neighbour. Everything else stays put. This is the theoretical minimum data movement for adding a node — you can't do better, because the new node needs its fair share of data, and it can come from only one neighbour (since the new node's arc displaces exactly one existing node's arc).

The same logic applies to node removal: when Node C is removed, its arc merges into its clockwise successor's arc. Only Node C's data migrates. All other nodes are unaffected.

Part 4: The Non-Uniformity Problem and Virtual Nodes

The elegant ring model has a flaw in practice: with only a handful of physical nodes, their hash positions on the ring are not perfectly equally spaced. They're determined by hash(node_identifier), which is random. With 4 nodes, you might get something like:

Node A at 3.8B: owns arc from 2.8B to 3.8B → 1.0B of ring space → 23% of keys
Node B at 0.9B: owns arc from 3.8B to 0.9B → 1.4B of ring space → 33% of keys  ← HOT
Node C at 1.9B: owns arc from 0.9B to 1.9B → 1.0B of ring space → 23% of keys
Node D at 2.8B: owns arc from 1.9B to 2.8B → 0.9B of ring space → 21% of keys

Node B owns 33% of the ring while Node D owns only 21%. With 1 million keys, B holds 330,000 and D holds 210,000 — a 57% imbalance. If Node B fails and its data must be absorbed by its successor, that successor suddenly gets 33% more data in addition to its own. Uneven load distribution defeats much of the purpose of sharding.

The solution: virtual nodes (vnodes).

Instead of placing each physical node once on the ring, place it multiple times — say, 150 times — at different positions. Each physical node gets 150 virtual node identifiers (node_A_1, node_A_2, ..., node_A_150), each hashed to a different ring position. The ring now has 150 × N virtual nodes, and each virtual node's arc is much smaller.

Physical node A, represented by 150 virtual nodes:
  A_1 at  0.03B
  A_2 at  0.11B
  A_3 at  0.19B
  ... (147 more positions scattered around the ring)
  A_148 at 4.27B
  A_149 at 4.30B
  A_150 at 4.29B (wait, positions are sorted, not sequential)

With 150 virtual nodes per physical node and 4 physical nodes = 600 total positions on the ring, the arcs between adjacent positions are much smaller. By the law of large numbers, each physical node's total arc (the sum of its 150 small arcs) converges toward 25% of the ring. With 150 virtual nodes, the load imbalance is typically under 5% — far better than the raw 3-4 node case.

Ring with 4 nodes × 150 vnodes = 600 positions:

...─[A]─[C]─[B]─[D]─[A]─[B]─[C]─[A]─[D]─[B]─[C]─[D]─[A]─...
           ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
         Each gap is ~4.3B / 600 ≈ 7M hash units

Virtual nodes also make rebalancing more graceful. When a physical node is added, it claims virtual node positions scattered around the entire ring — taking a small amount of data from every existing node, rather than taking all its data from one neighbour. This spreads the migration load evenly across the cluster.

Part 5: Consistent Hashing in Real Systems

Amazon Dynamo (the paper, not DynamoDB the product)

The 2007 Amazon Dynamo paper described the original commercial consistent hashing implementation. Each node was responsible for a range of the hash ring, and the ring used MD5 to hash both node IDs and keys into a 128-bit space. Dynamo used 150–200 virtual nodes per physical node to ensure load balance.

One interesting design choice: Dynamo used preference lists. For each key, instead of assigning it to just one node, Dynamo assigned it to the first N healthy nodes clockwise on the ring (N was typically 3). This provided replication — the key was stored on N nodes — without a separate replication layer. The consistent hashing ring simultaneously handled both partitioning and replica placement.

Apache Cassandra

Cassandra's original architecture used the same consistent hashing ring. In recent versions, Cassandra introduced "virtual nodes" as a first-class feature (controlled by the num_tokens configuration, default 256 vnodes per node). Adding a new node to a Cassandra cluster automatically claims ~1/N of vnodes from existing nodes and triggers only the necessary data streaming. A 10-node cluster adding an 11th node streams ~9.1% of total data (1/11), vs. roughly 50% with naive hash partitioning.

Redis Cluster

Redis Cluster uses a different but related approach: hash slots rather than a pure ring. The entire key space is divided into 16,384 fixed slots. slot = CRC16(key) % 16384. Each Redis node is manually or automatically assigned a range of slots. Adding a node means reassigning some slots to the new node, which involves migrating only the keys in those slots.

This is consistent hashing with a fixed, coarse virtual node count (16,384 slots instead of continuous vnodes). The advantages: the slot mapping is deterministic and can be stored in a simple lookup table; all clients can know the full slot assignment map and route directly without a proxy. The disadvantage: you can't have more than 16,384 nodes (one slot per node minimum), and the minimum migration granularity is one slot's worth of keys.

Chord (the academic distributed hash table)

Chord is a theoretical distributed hash table protocol that formalises consistent hashing and adds a clever lookup mechanism. In Chord, nodes maintain a "finger table" of O(log N) other nodes' positions on the ring, enabling key lookups in O(log N) hops rather than O(N). Chord is more relevant as a foundation for understanding peer-to-peer systems (BitTorrent, Kademlia) than for production databases, but the finger table idea shows up in modified form in any distributed system that needs efficient routing through the ring without a central directory.

Part 6: The Routing Layer — Where Does the Ring Live?

Consistent hashing answers "which node owns this key?" But something must execute that computation and route the request. There are three architectural approaches:

Client-side routing

Every client knows the full node map (the ring topology). When a client wants to read or write a key, it computes target_node = consistent_hash(key, ring) locally and connects directly to the correct node.

Redis Cluster uses this model. Clients download the hash slot assignment table from any cluster node and cache it. A GET mykey request: client computes CRC16("mykey") % 16384 = slot 7638, looks up slot 7638 in its local table → Node 3, connects directly to Node 3. If the data has moved (resharding in progress), Node 3 returns a MOVED redirect, the client updates its table, and retries. No proxy, no extra hop.

Advantage: Zero extra latency — direct connection to the correct node. Disadvantage: Every client must track topology changes. With dozens of microservices, each with their own connection pool, distributing topology updates becomes a coordination problem.

Proxy routing

A central proxy (or pool of proxies) sits between clients and nodes. Clients connect to the proxy. The proxy knows the ring and forwards each request to the correct node.

Twemproxy (Twitter's Memcached proxy), Mcrouter (Facebook's Memcached router), and many database middleware solutions use this model. The client is dumb — it just sends requests to the proxy as if it were a single server.

Advantage: Clients are simple. Topology changes are handled by the proxy layer — update one place, all clients benefit immediately. Disadvantage: The proxy is now in the critical path of every request. It must be highly available. At extreme throughput, the proxy can become a bottleneck. Typically mitigated by running multiple proxy instances.

Coordinator node

Some distributed databases (Cassandra in some configurations) have clients connect to any node, and that node acts as coordinator — it computes the correct target node, forwards the request, and returns the result. This is essentially distributed proxy routing with the proxy role shared among all nodes.

Advantage: No single proxy bottleneck. Any node can coordinate. Disadvantage: Every hop now involves two network round trips (client→coordinator, coordinator→target). Adds latency.

The choice between these architectures involves trade-offs between operational simplicity, latency, and fault tolerance. Most production systems use proxy routing or client-side routing for performance-sensitive workloads, and coordinator-based routing for simpler operational requirements.

Part 7: Hotspots Still Happen — Consistent Hashing Doesn't Solve Access Skew

Here is an important limitation to be clear about: consistent hashing solves data distribution (roughly equal number of keys per node). It does not solve access skew (some keys being accessed far more frequently than others).

If a celebrity post receives 10 million reads per hour and an average post receives 100 reads per hour, consistent hashing will place the celebrity post on exactly one node — consistently. The consistent part means the routing is stable and predictable. But it also means that one node receives all 10 million reads. Consistent hashing doesn't know that this key is hotter than others. It just finds the right node. The right node is overwhelmed.

Consistent hashing distributes:
  Key count per node:     ✓ Roughly uniform (via vnodes)
  Access frequency per key: ✗ Not addressed — hot keys still hot

The solutions to access skew are orthogonal to consistent hashing:

Caching (Chapter 9): The hot key gets cached at a layer above the database. The cache absorbs most reads. The database node only receives cache-miss requests and initial populates.

Replication of hot keys: Some systems explicitly replicate hot keys to multiple nodes (Cassandra's "speculative reads" effectively do this). The key is stored on its consistent hash node plus additional nodes when flagged as hot. Reads go to any of the replicas.

Client-side local cache: The application tier caches the celebrity post in process memory. No database request at all for subsequent reads within the same process.

Consistent hashing is the right tool for data placement and rebalancing. Access skew needs its own tools. Don't expect consistent hashing to fix what it was never designed to fix.

Part 8: Consistent Hashing for Caches vs. Databases — Different Stakes

The algorithm is identical for caches and databases, but the failure consequences differ dramatically.

Cache clusters (Memcached, Redis)

If a cache node goes down and its keys become temporarily unreroutable, the keys are simply unavailable in the cache. Every cache miss falls through to the database. This is an availability problem (worse latency, higher database load) but not a data loss problem — the canonical data is in the database. The cache repopulates as requests come in.

This means cache clusters can tolerate imperfect consistency in the ring state. If two clients have slightly different views of which nodes are up (one thinks Node C is up, the other thinks Node C is down), they'll route some keys differently. Some will hit the cache, some will miss. The worst outcome is a cache miss and a database call — acceptable.

Database clusters (Cassandra, DynamoDB)

If a database node goes down, the data that was on that node is unavailable (or degraded, if replicated). The ring must correctly reflect which nodes are alive so that requests are routed only to nodes that can serve them. An inconsistent ring view means some requests are routed to a dead node — a hard error, not a performance degradation.

Database clusters typically maintain the ring state in a separate, highly-consistent coordination service (ZooKeeper, etcd) or via gossip protocol with explicit failure detection. Node failure is handled by promoting a replica or routing to one of the key's replica nodes. Rebalancing after a failure is a careful operation with explicit migration protocols, not just a routing update.

The takeaway: for caches, consistent hashing is a best-effort optimisation. For databases, it's a correctness-critical component of the storage system. Design your ring management accordingly.

Part 9: From Consistent Hashing to DynamoDB's Architecture

Amazon DynamoDB (the modern product, not the 2007 paper) uses a variant of consistent hashing internally, but exposes a higher-level abstraction to users: partition key + optional sort key.

The partition key is what DynamoDB hashes to determine the partition (shard). Internally, DynamoDB maintains a table of hash ranges (consistent hashing ranges) and the storage nodes responsible for each range. When you add provisioned capacity or a table autoscales, DynamoDB splits partitions — equivalent to adding a virtual node and rebalancing a portion of the ring.

The important abstraction DynamoDB provides: you never see the ring. You don't configure vnodes or migration. You choose a partition key, and DynamoDB handles all of the consistent hashing mechanics invisibly. The price: your partition key must be high-cardinality and uniformly accessed, or DynamoDB's auto-split logic can't help you (a single hot partition can't be split further without changing the partition key).

This is the production lesson: consistent hashing is increasingly invisible infrastructure, implemented inside managed databases and cache services. You'll rarely implement it directly. But understanding it is essential to:

1. Diagnose performance problems caused by hot partitions
2. Make good partition key choices (they directly determine which consistent hash bucket your data lands in)
3. Understand capacity planning (adding nodes, rebalancing, migration windows)
4. Build distributed systems from scratch when managed services don't fit

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

Your team runs a Memcached cluster with 6 nodes using hash(key) % 6 routing. You add a 7th node. Calculate precisely: what percentage of the 10 million cached keys are now assigned to a different node? Your database normally handles 2,000 queries per second, with the cache absorbing 85% of read traffic (cache hit rate = 85%). Estimate the query burst to the database immediately after adding the 7th node, assuming all displaced cache keys are simultaneously requested by clients. Would your database survive this? At what cache hit rate does the database become the bottleneck? Now redesign: if you had used consistent hashing with 150 vnodes per node, what percentage of keys would have moved, and what would the database query burst have been?

Problem 2 — Design from Scratch

Design the consistent hashing ring for a distributed rate limiter. The system limits API requests per user per minute (e.g., 1,000 requests/minute per user_id). The rate limiter must:

• Route all requests for a given user_id to the same node (so counts are local, not distributed)
• Handle node failure gracefully (a failed rate limiter node should fail open — allow traffic — rather than blocking all users on that node)
• Rebalance when a node is added without causing all users to be re-routed

Choose a ring design (number of vnodes, hash function), a routing architecture (client-side, proxy, or coordinator), and explain how you handle node failure. What happens to rate limit accuracy during the rebalancing window when a new node joins?

Problem 3 — Synthesis

Connect Chapter 7's shard key selection rules to consistent hashing.

In Chapter 7, you learned that a good shard key must have high cardinality and uniform distribution. Now apply this to consistent hashing: if your shard key has low cardinality (e.g., only 100 distinct values) and you're running a cluster with 150 vnodes per physical node across 10 machines = 1,500 vnode positions on the ring, what problem arises? Specifically: if only 100 distinct key values exist, how many vnodes can ever be "active" (actually receiving traffic)? What does this mean for the load distribution across the 10 physical nodes? How does this connect to Chapter 3's selectivity concept — high-cardinality columns for indexes, and now high-cardinality shard keys for consistent hashing? What is the structural similarity between these two requirements?

Problem 4 — Go Deeper

Consistent hashing with vnodes assumes that hash(key) produces a uniformly distributed output. Most hash functions (MurmurHash, CRC32, MD5) satisfy this for arbitrary inputs. But what happens when the input keys are not arbitrary — specifically, when keys are sequential integers (1, 2, 3, ..., 1,000,000)?

Work through this: does the ring distribution of sequential integer keys differ from the distribution of random string keys? Why or why not? (Hint: consider what a hash function does to sequential inputs.) Now consider the reverse: sequential node IDs hashed onto the ring. If your node identifiers are node_001, node_002, ..., node_010, do you expect uniform ring placement? What happens if you use node_1, node_2, ..., node_10 as identifiers? Test your reasoning: what property of the hash function determines whether sequential inputs produce uniform ring positions, and how would you verify this for a specific hash function?

Problem 5 — Connect to Previous Chapters

Connect consistent hashing to Chapter 6's consistency model and Chapter 4's failure taxonomy.

A Cassandra cluster uses consistent hashing with replication factor 3: each key is written to 3 consecutive nodes clockwise on the ring. A quorum write requires 2 of 3 replicas to acknowledge. A quorum read requires 2 of 3 replicas to respond.

Scenario: Node 2 experiences a network partition (Chapter 4's partial failure — it can talk to clients but not to the other cluster nodes). A client writes key K to the cluster. The write reaches Node 1 (primary) and Node 3 (second replica) but not Node 2. Both acknowledge — quorum achieved. The client receives a success response.

Now trace through Chapter 6's consistency vocabulary: does this write satisfy linearizability? Sequential consistency? Causal consistency? Eventual consistency? Which one does the quorum model actually provide, and under what specific conditions does it violate the stronger models? If Node 2 later rejoins and a client reads key K from Node 2 before the anti-entropy repair runs, what does the client see, and what consistency level has been violated?

What's Coming Next

Consistent hashing solves the "where does this data live?" problem with minimal reshuffling. But there's a layer above the database that you're missing: every time a client fetches data, they're reading from disk (or SSD) and the database's buffer pool. The fastest possible answer is one that never touches the database at all — one that lives in RAM, closer to the application. Chapter 9 covers caching: how application-tier caches like Memcached and Redis eliminate the majority of database reads, the cache invalidation strategies that keep them consistent with the database, and the failure modes (thundering herd, cache penetration, cache avalanche) that can bring a system down when caching is done wrong. The celebrity problem from Chapter 7 — where a single hot key overwhelms one shard — is finally fully solved in Chapter 9.

Chapter 8 complete. Problem 1 is essential: run the numbers on the cache stampede before moving on. The gap between 50% cache key displacement (naive hash%N) and 10% (consistent hashing with 7th node) is what determines whether adding a cache node kills your database. Problem 5 applies the hardest concept from Chapter 6 (quorum consistency level) to a concrete failure trace — it's exactly the kind of reasoning FAANG system design interviews test.