Consistent Hashing

Fractional CTO · Founder of Injuria.ai
Consistent hashing[1] is a distributed systems algorithm that maps data keys to a dynamic set of storage nodes or servers.[27] Unlike traditional hash tables[2] where a change in the number of array slots requires remapping nearly all keys, consistent hashing ensures that when a node is added or removed, only a mathematically minimal fraction of keys must be reassigned.[28] This property allows large scale networks, databases, and caches to scale horizontally without incurring massive data migration penalties or system-wide cache invalidation.
The algorithm operates by mapping both the incoming keys and the available servers into the same mathematical space, typically represented as a circular ring.[29] By establishing a deterministic routing rule, such as assigning a key to the first server that appears clockwise on the ring, the system decouples the hashing function from the exact number of active servers. This decoupling provides the foundation for decentralized routing and elastic scaling, eliminating the need for a centralized directory to track data placement.
Originally formalized to address traffic bottlenecks on the early World Wide Web, consistent hashing has become a foundational concept in modern computer science. As software architectures transitioned from monolithic mainframes to distributed microservices and cloud infrastructure, the need for stateless, decentralized routing became absolute. Today, consistent hashing forms the underlying data partitioning mechanism for distributed hash tables, NoSQL databases, content delivery networks, and software defined load balancers.
The Problem of Dynamic Scaling
In a standard hash table, a hash function converts a key into an integer, which is then mapped to a specific array index using the modulo operator.[30] For a system with $N$ servers, the routing logic is typically expressed as server_index = hash(key) modulo N. This approach distributes data evenly across the available servers as long as $N$ remains strictly constant.
However, distributed systems are inherently dynamic. Hardware failures, network partitions, and maintenance operations cause servers to drop out of the cluster.[31] Conversely, surges in traffic require administrators to provision additional servers. When $N$ changes to $N+1$ or $N-1$, the modulo operation yields a different result for nearly every key in the system. Statistically, a change in the server count forces $K(N-1)/N$ keys to be reassigned, where $K$ is the total number of keys. If a cluster scales from 10 to 11 servers, approximately 90 percent of the data must move to a new location.
In a caching architecture, this massive reassignment invalidates 90 percent of the cache, forcing the system to fetch the data from the slower primary database. This sudden spike in database queries is known as a thundering herd or cache stampede, which can easily overwhelm the backend and cause a complete system outage. The severity of this problem was documented in the 2013 USENIX NSDI paper "Scaling Memcache at Facebook"[3], which detailed how the social network managed billions of requests per second across trillions of items. In environments of that magnitude, a single node failure under a modulo-based hashing scheme would trigger a catastrophic flood of queries to the underlying MySQL databases. In a persistent storage architecture, moving 90 percent of the stored data across the network saturates bandwidth and degrades read and write latencies. Consistent hashing was developed specifically to solve this exact problem by guaranteeing that only $K/N$ keys move when the cluster size changes. This represents the theoretical minimum amount of data movement required to restore an even distribution.
Mechanism and Architecture
Consistent hashing replaces the modulo arithmetic with a unified mathematical space known as a hash ring. A cryptographic or non-cryptographic hash function, such as MD5, SHA-1, or MurmurHash3[4], is selected to generate uniformly distributed integers. These hash functions are chosen for their avalanche effect, a property where a minor change in the input string produces a completely different output hash, ensuring that lexically similar keys are scattered randomly across the space. If the hash function outputs a 160-bit integer, the hash space ranges from 0 to $2^{160}-1$. The maximum value wraps around to zero, forming a logical circle.
Both the servers and the data keys are hashed into this identical space.[32] A server is assigned a position on the ring by hashing its unique identifier, such as its IP address or hostname. A data key is assigned a position by hashing its string or binary value. To locate the server responsible for a specific key, the algorithm finds the key's position on the ring and moves clockwise until it encounters the first server. That server becomes the designated storage node for the key.
When a new server is added to the ring, it occupies a specific position and takes over a portion of the arc previously managed by its immediate clockwise neighbor. Only the keys located in that specific arc are reassigned to the new server. All other keys in the system remain completely unaffected. Similarly, when a server is removed, its keys are simply inherited by its immediate clockwise neighbor.[32]
Virtual Nodes
A mathematical vulnerability of mapping physical servers directly to the ring is that a random distribution of a small number of nodes will result in highly uneven arc lengths. One server might control 30 percent of the ring, while another controls only 1 percent. This high variance leads to severe load imbalances. To achieve a uniform distribution, consistent hashing implementations use virtual nodes, commonly referred to as vnodes.
Instead of hashing each physical server once, the system hashes each server multiple times using deterministic suffixes (for example, serverA_01 to serverA_256). This places hundreds of virtual nodes on the ring for every physical machine, interleaving them with the virtual nodes of other servers. The use of virtual nodes ensures that the load is distributed evenly, reducing the peak-to-average load ratio to a mathematically acceptable margin.
Virtual nodes also enable weighted routing. In a heterogeneous cluster, physical machines often have different compute and storage capacities. A high-capacity server can be assigned 500 virtual nodes, while a legacy server is assigned only 100. This configuration naturally directs more traffic to the more capable hardware without requiring complex routing logic at the application layer.
Replication and High Availability
In distributed databases, data must survive the failure of a physical machine. Consistent hashing facilitates this through ring-based replication. A system configured with a replication factor of $R$ will store a key on its primary node and replicate it to the next $R-1$ distinct physical nodes encountered while continuing clockwise around the ring.
Because virtual nodes belonging to the same physical server may appear consecutively on the ring, the replication logic must inspect the physical identity of each vnode and skip duplicates to ensure replicas are stored on isolated hardware. Advanced implementations extend this concept to achieve rack and data center awareness. For example, Apache Cassandra[5] utilizes a NetworkTopologyStrategy that walks the ring to place replicas on nodes located in entirely different physical racks or geographic data centers. This ensures that a localized failure, such as a top-of-rack switch losing power or a network partition isolating a single data center, does not result in permanent data loss or total unavailability for any specific key.
Complexity and Implementation Data Structures
The time and space complexity of consistent hashing depends heavily on the number of virtual nodes, denoted as $V$. Storing the ring requires $O(V)$ space. The choice of underlying data structure dictates the performance characteristics of the system.
The most common implementation uses a sorted array of node positions. Looking up a key requires computing its hash in $O(1)$ time, followed by a binary search over the sorted array to find the next node. This results in a lookup time complexity of $O(\log V)$. Adding or removing a node requires inserting or deleting its virtual nodes in the array, which takes $O(V \log V)$ time to resort, or $O(V)$ time if shifting elements in place. Following the topology change, the network transfer of the $O(K/N)$ affected keys occurs.
Alternatively, the ring can be implemented using a balanced binary search tree, such as a Red-Black tree. This structure maintains the $O(\log V)$ lookup time but reduces the insertion and deletion time to $O(\log V)$, making it highly efficient for volatile environments where nodes join and leave frequently. However, tree structures incur higher memory overhead due to pointer storage and suffer from reduced CPU cache locality compared to contiguous arrays.
def get_node(key, ring_array):
if not ring_array:
return None
hash_val = hash_function(key)
left, right = 0, len(ring_array) - 1
# Binary search for the first node position >= hash_val
while left <= right:
mid = (left + right) // 2
if ring_array[mid].position < hash_val:
left = mid + 1
else:
right = mid - 1
# Wrap around to the first node if the key is past the last node
if left == len(ring_array):
return ring_array[0].node_name
return ring_array[left].node_name
Discovery and History
The formalization of consistent hashing occurred in the late 1990s as the World Wide Web experienced exponential growth, leading to severe network congestion and server overloads.
In 1997, a team of researchers at the Massachusetts Institute of Technology published the seminal paper [6] at the ACM Symposium on Theory of Computing.[33] The authors included David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. The research was prompted by a challenge from World Wide Web inventor Tim Berners-Lee, who visited MIT and urged colleagues to invent a better way to distribute web content. Karger and Lewin developed the mathematical proofs, utilizing Chernoff bounds to demonstrate that consistent hashing could restrict the number of keys mapped to any single cache to $O((K/N) \log N)$ with high probability. This academic breakthrough directly led Leighton and Lewin to found Akamai Technologies in 1998, commercializing the algorithm to build one of the first and largest content delivery networks.
Independent Co-discovery
The core concept of decoupling the hash space from the server count was discovered independently by multiple groups during the same period. In 1996, David Thaler and Chinya V. Ravishankar at the University of Michigan developed a related algorithm called Highest Random Weight hashing[7], also known as Rendezvous hashing. They published their findings in the IEEE/ACM Transactions on Networking in 1998 under the title "Using Name-Based Mappings to Increase Hit Rates".
Simultaneously, in 1997, Vinod Valloppillil of Microsoft and Keith W. Ross of the University of Pennsylvania authored an Internet Engineering Task Force draft titled "Cache Array Routing Protocol v1.0"[8] (CARP). CARP utilized a hash-based routing mechanism to distribute URLs among proxy servers, aiming to replace the broadcast-heavy Internet Cache Protocol[9].
In 2007, Richard Jones at Last.fm developed Ketama[10], an open-source C library that brought consistent hashing to Memcached clients. Ketama utilized the MD5 algorithm to generate 160 virtual nodes per physical server, establishing a standard implementation that prevented cache stampedes during Memcached cluster resizing and became widely adopted across the industry.
Key Refinements and Important Variants
The original algorithm underwent significant evolution as it was adapted for different domains. In 2001, Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan published the design of Chord[11], a distributed peer-to-peer lookup service. Chord applied consistent hashing to overlay networks, introducing finger tables that allowed nodes to route requests across the ring in $O(\log N)$ network hops without requiring a central directory.
In 2007, Amazon engineers Giuseppe DeCandia, Werner Vogels, and others published the Dynamo[12] paper at the ACM Symposium on Operating Systems Principles. The Dynamo architecture adapted consistent hashing for persistent enterprise databases, popularizing the use of virtual nodes and establishing the pattern of replicating data to the next $R-1$ distinct physical nodes on the ring.
The standard ring-based implementation is highly versatile, but specific engineering constraints have driven the development of several distinct variants.
Rendezvous Hashing
Rendezvous hashing achieves the same minimal disruption property as ring-based consistent hashing but uses a different mechanism. Instead of placing nodes on a ring, the algorithm computes a combined hash of the key and the node identifier for every available node, expressed as $score = hash(key, node_id)$. The node that produces the highest score is selected. While this requires $O(N)$ time to compute the hashes for all nodes, it naturally results in an extremely even distribution of keys without the need for virtual nodes.
Jump Consistent Hash
In 2014, John Lamping and Eric Veach at Google introduced Jump Consistent Hash[13], a highly optimized algorithm designed for data storage applications where memory and execution speed are critical. It operates without a ring. Instead, it evaluates a key against a number of buckets sequentially. For a given key, it seeds a linear congruential generator. When the system scales from $j$ to $j+1$ buckets, the ideal probability that a key moves to the new bucket is exactly $1/(j+1)$. The algorithm generates a pseudorandom float between 0 and 1. If the float is less than $1/(j+1)$, the key jumps to bucket $j$. This process repeats up to the total number of buckets $N$. The algorithm requires $O(1)$ space and executes in $O(\log N)$ time. Its primary limitation is that the buckets must be numbered sequentially from 0 to $N-1$. If a node is removed from the middle of the sequence, all subsequent nodes must be renumbered, making it unsuitable for highly volatile environments.
Multi-probe Consistent Hashing
In 2015, Ben Appleton and Michael O'Reilly published "Multi-probe consistent hashing"[14], outlining a method to achieve uniform load distribution without the $O(V)$ memory overhead of virtual nodes. Instead of hashing each physical node multiple times to create vnodes, the algorithm hashes the incoming key multiple times to generate several candidate positions on the ring. The key is then assigned to the closest node among these candidate positions. This approach requires only $O(N)$ space to store the physical nodes while achieving a peak-to-average load ratio of $1 + \epsilon$.
Maglev Hashing
In 2016, Danielle Eisenbud and colleagues published the Maglev[15] paper at NSDI, detailing a precomputed consistent hashing variant optimized for high-speed network load balancing. Maglev hashing bypasses the $O(\log V)$ binary search overhead of ring-based hashing, achieving $O(1)$ lookup times for network packet routing. It uses a precomputed lookup table of a fixed prime size, typically 65537. During initialization, every node uses a hash function to generate a deterministic sequence of preferences for all 65537 indices. The algorithm populates the table in rounds, with each node attempting to claim the next index in its preference list until the table is full. When a packet arrives, the load balancer hashes the packet's 5-tuple (source IP, destination IP, source port, destination port, protocol) to an index in the table and routes the packet to the node listed at that index.
Bounded-Load Consistent Hashing
Standard consistent hashing guarantees that the keyspace is partitioned evenly, but it assumes that all keys receive an equal volume of requests. In reality, internet traffic follows a Zipfian distribution, where a small number of keys generate the vast majority of traffic. In 2017, Vahab Mirrokni and Morteza Zadimoghaddam of Google, and Mikkel Thorup of the University of Copenhagen formalized Bounded-Load Consistent Hashing[16] to solve this access skew, presenting their findings at SODA 2018[17]. The algorithm introduces a capacity parameter, $c$, defined as a multiplier of the average cluster load (for example, $c = 1.25$). When a request arrives, the key is hashed to its primary node on the ring. If routing the request to that node would cause its load to exceed the capacity limit, the algorithm forwards the request to the next node clockwise on the ring. By enforcing a strict upper bound, the algorithm prevents cascading failures where a single hot key causes a server to crash.
Real-World Applications
Consistent hashing is the primary data partitioning strategy for a vast array of modern infrastructure systems.
Distributed Databases
Apache Cassandra[5] relies entirely on a consistent hash ring to distribute data across clusters. Each node is assigned a set of tokens that dictate its position on the ring, utilizing virtual nodes to balance the storage load. Amazon DynamoDB[18] uses a proprietary implementation of the Dynamo architecture, employing consistent hashing to partition customer tables across thousands of storage nodes while maintaining high availability through ring-based replication. Other NoSQL databases, including Riak[19], use similar ring topologies to manage data placement and cluster elasticity, while Couchbase[20] uses a fixed-partition vBucket architecture (similar to Redis hash slots), not a ring topology.
Caching Systems
Distributed memory caches heavily utilize consistent hashing to prevent cache stampedes during scaling events. The Memcached ecosystem relies on client-side libraries, such as libmemcached, which implement the Ketama algorithm. Redis Cluster[21] uses a hybrid approach called hash slots. Instead of a continuous ring, Redis divides the hash space into exactly 16,384 fixed slots. Keys are mapped to slots using the CRC16 algorithm, and the slots are distributed among the active Redis nodes. When a node is added or removed, specific slots are migrated between nodes, providing administrators with explicit control over data movement.
Content Delivery and Load Balancing
Content Delivery Networks like Akamai use consistent hashing to map user requests to specific edge servers, as detailed in "Algorithmic Nuggets in Content Delivery"[22]. By ensuring that requests for the same image or video file consistently route to the same edge server, the CDN maximizes its cache hit rate and shields the origin server from redundant requests. In the load balancing sector, Google Cloud Load Balancing[23] uses Maglev hashing to distribute incoming network traffic across frontend servers. The open-source load balancer HAProxy[24] implemented Bounded-Load Consistent Hashing in 2016 based on the 2016 arXiv paper (the Google Research Blog post was published later in 2017 about his contribution)[25][26], to distribute video streaming traffic without overloading individual cache servers.
Significance and Tradeoffs
Consistent hashing is a fundamental enabler of horizontal scalability. By eliminating the need for a central routing directory, it removes a single point of failure and allows distributed systems to operate in a completely decentralized manner. Nodes can join or leave the cluster independently, and the system mathematically guarantees that data migration is kept to the absolute minimum.
Despite its advantages, the algorithm requires careful engineering to mitigate specific tradeoffs. The most prominent issue is the distinction between data skew and access skew. While virtual nodes effectively solve data skew by ensuring an even distribution of the keyspace, they offer no protection against access skew. A single highly popular key will always hash to the same node, potentially overwhelming its CPU or network interface. Systems must implement secondary mechanisms, such as bounded loads or application-level caching, to handle these hot keys.
Another tradeoff is the loss of strict data ordering. Because keys are hashed into a pseudorandom space, sequential data (such as time-series logs) is scattered randomly across the cluster. This makes range queries highly inefficient, as the system must query every node in the cluster to retrieve a sequential list of records. For applications that require frequent range scans, databases like Google Spanner or CockroachDB abandon consistent hashing entirely in favor of range partitioning, where data is sorted and split into contiguous chunks.
Finally, the memory and network overhead of virtual nodes can become significant in massive clusters. Storing 256 virtual nodes for a cluster of 10,000 servers requires maintaining and propagating a routing table with 2.5 million entries. If a network partition occurs, the constant recalculation of the ring topology via gossip protocols can consume excessive CPU resources. To address this, modern systems often reduce the number of virtual nodes or adopt fixed-partition architectures, balancing the theoretical elegance of the hash ring with the practical constraints of network overhead.
Sources (33)
- Wikipedia: Consistent hashing
- Wikipedia: traditional hash tables
- "Scaling Memcache at Facebook"
- MurmurHash3
- Apache Cassandra
- ACM Digital Library
- IEEE
- IETF
- IETF
- Ketama
- ACM Digital Library
- ACM Digital Library
- Jump Consistent Hash
- "Multi-probe consistent hashing"
- Maglev
- Bounded-Load Consistent Hashing
- ACM Digital Library
- Amazon DynamoDB
- Riak
- Couchbase
- Redis Cluster
- ACM Digital Library
- Google Cloud Load Balancing
- HAProxy
- contribution by Andrew Rodland at Vimeo
- Google Research Blog
- Geoffrey M. Voelker, Scott Shenker, Peer-to-Peer Systems III (Springer, 2005)
- Samrat Ganguly, Sudeept Bhatnagar, VoIP (John Wiley & Sons, 2008)
- Xiaofei He, Xinbo Gao, Yanning Zhang, Intelligence Science and Big Data Engineering. Big Data and Machine Learning Techniques (Springer, 2015)
- Wilfried Lemahieu, Seppe vanden Broucke, Bart Baesens, Principles of Database Management (Cambridge University Press, 2018)
- Marcos K. Aguilera, Distributed Computing (Springer, 2012)
- Shashank Tiwari, Professional NoSQL (John Wiley & Sons, 2011)
- Guy Lebanon, Mohamed El-Geish, Computing with Data (Springer, 2018)