What is Consistent Hashing and Why Does It Matter?

Consistent hashing is a placement algorithm that maps both keys (like user IDs or cache keys) and nodes (like servers or storage instances) into the same hash space, typically visualized as a ring. When you hash a key, you find the first node clockwise from that position on the ring, and that node owns the key. The critical property: when you add or remove one node from an N node cluster, only roughly 1/N of keys move to new locations. With simple modulo hashing (key % N), adding or removing a node remaps almost all keys, causing massive data movement.

This matters enormously at scale. Consider Amazon Dynamo with 100 storage nodes holding 100 TB of data. Adding one node with consistent hashing moves approximately 1 TB (1% of data), which can be planned during off peak hours with controlled streaming. With modulo hashing, you would need to relocate nearly 99 TB, saturating networks and violating Service Level Objectives (SLOs) for hours or days.

The algorithm works by hashing node identifiers (like server IP addresses or unique node IDs) onto points on the ring using the same hash function used for keys. When a new node joins, it takes ownership of keys in its clockwise arc from the previous node. When a node leaves, its keys transfer to the next clockwise successor. This predictable, minimal disruption enables elastic scaling, where clusters grow and shrink without massive reshuffling.

Production systems across Amazon, Meta, and Microsoft rely on this property to maintain single digit millisecond latencies during topology changes. Without consistent hashing, every scaling operation would become a risky, manually coordinated data migration event rather than a routine automated action.

💡 Key Takeaways

•Minimal disruption: Adding or removing one node from N nodes moves only approximately 1/N of keys, versus nearly all keys with modulo hashing

•Amazon Dynamo pattern with 100 nodes and 100 TB: adding one node moves roughly 1 TB (1%) instead of 99 TB (99%), enabling planned off peak migrations

•Hash both keys and nodes into same space: Use identical hash function (often SHA-1 or non-cryptographic like MurmurHash) to map both into large identifier space

•Deterministic and distributed: Each client can independently compute key placement without central directory, reducing coordination overhead and single points of failure

•Real latency targets: Meta memcache clusters serve millions of requests per second with sub-millisecond median and low millisecond p99, maintained even during node additions

📌 Examples

Memcached at Meta (mcrouter): 200 node cache pool with 200M hot keys uses consistent hashing; adding one node remaps approximately 1M keys (0.5%), kept under background refill budgets to avoid cache miss storms

Amazon ElastiCache: Clients use Ketama style consistent hashing to select cache shards; rolling out one node in a 50 node cluster affects 2% of keys with no central coordinator

Cassandra token ring: 100 nodes with replication factor 3 across availability zones; removing one failed node transfers its 1% key range to immediate successors with controlled streaming

← Back to Consistent Hashing Overview