Consistent hashing simulator
Consistent hashing places servers and keys on the same circle, and gives each key to the next server clockwise. When a server joins or leaves, only the keys next to it change hands. Add and remove servers below and compare it with plain hash mod N, then follow the worked example and the Python implementation further down.
- On the ring
- n2
- With hash mod 3
- n3
The thin line marks an even split of 33.3% each. The largest share is 1.09 times that.
Add or remove a server to measure how many keys change owner.
How to use the simulator
The circle is the range of possible hash values, from 0 at the top to 232, increasing clockwise and bent round so that the two ends meet. Each coloured tick is one position of a server; the black dot is the key you typed. A key belongs to the first server position found by moving clockwise from it. The shaded arc is the stretch of the circle that this server position is responsible for, and the centre names the owner.
Try these:
- Press Add a server. The panel reports how many of 5,000 sample keys changed owner on the ring, and how many would have moved if keys were assigned with hash(key) mod N instead.
- Set Virtual nodes per server to 1. Each server then has a single position, and the shares in the bar chart become very uneven. Raise it to 100 or 200 and the shares move close to an even split.
- Type different keys to see which server owns each one, and compare the ring's answer with hash mod N.
The simulator hashes names with 32-bit FNV-1a followed by a mixing step (the MurmurHash3 finalizer), so that similar names such as n1:0 and n1:1 land far apart. It finds owners with a binary search over the sorted positions, which is how many real implementations work.
What is consistent hashing?
Consistent hashing is a way of assigning keys to servers so that adding or removing a server moves only a small share of the keys: about 1/N of them for N servers. Both the servers and the keys are hashed to positions on a circle, and each key is stored on the first server found by moving clockwise from the key's position.
It was introduced in 1997 by David Karger and colleagues at MIT as a way to spread web content across a changing set of caches. It is used today in distributed caches, in key-value databases such as Cassandra and Riak, and in load balancers that need to send the same client or key to the same backend.
The problem with hash mod N
The simplest way to spread keys over N servers is to hash each key and take the remainder after dividing by N: server = hash(key) mod N. Each server gets about the same number of keys, and finding a key needs no lookup table.
The trouble starts when N changes. A key whose hash is 10 goes to server 1 when there are three servers (10 mod 3 = 1), but to server 2 when there are four (10 mod 4 = 2), and most other keys change server in the same way. Going from N to N + 1 servers moves about N/(N + 1) of all keys: three quarters when going from three servers to four, and 99% when going from 100 to 101.
In a cache, every moved key is a miss, and all of those misses arrive at once. The database behind the cache can be overwhelmed by what should have been a routine change, such as adding capacity or replacing a failed machine.
How the hash ring works
Consistent hashing uses the same hash function for servers and keys. The output range of the hash, for example 0 to 232 − 1, is treated as a circle. Each server is placed on the circle at the hash of its name, and each key at the hash of the key. To find the server for a key, start at the key's position and move clockwise until you reach a server.
When a new server is added, it lands somewhere on the circle and takes over only the keys between its position and the previous server's position. Every other key still reaches the same server as before. When a server is removed, its keys move to the next server clockwise, and again nothing else changes.
In practice the server positions are kept in a sorted array or a balanced tree, and a lookup is a binary search, taking time proportional to the logarithm of the number of positions.
Consistent hashing example
Take a small ring numbered 0 to 99 instead of 0 to 232, with three servers at positions A = 10, B = 45 and C = 80, and five keys whose hashes are 5, 30, 50, 70 and 90. Each key goes to the first server at or after its position, wrapping round from 99 to 0. Then add a fourth server, D, at position 60.
| Key hash | Ring, 3 servers | Ring, after adding D at 60 | hash mod 3 | hash mod 4 |
|---|---|---|---|---|
| 5 | A | A | 2 | 1 (moved) |
| 30 | B | B | 0 | 2 (moved) |
| 50 | C | D (moved) | 2 | 2 |
| 70 | C | C | 1 | 2 (moved) |
| 90 | A (wraps round) | A | 0 | 2 (moved) |
On the ring only one key moves: 50 lies between B at 45 and the new server at 60, so it now belongs to D. Every other key keeps its server, and the key that moved went to the new server, not between old ones. With hash mod N, going from three servers to four moves four of the five keys.
Virtual nodes
With one position per server, the gaps between positions are uneven, because random points on a circle do not spread out evenly. Some servers end up owning much more of the circle than others, and the imbalance does not disappear as the cluster grows: with many servers, the largest share is typically several times the average.
The usual fix is to give each server many positions, called virtual nodes. A server named n1 is hashed as n1:0, n1:1, n1:2 and so on, and each hash adds a position on the circle. Each server then owns many small arcs, and their total is much closer to the average. Virtual nodes have a second benefit: when a server leaves, its keys are spread across many other servers instead of all going to one neighbour, and a new server takes a little from many servers.
The cost is a larger lookup table. Cassandra used 256 positions per node by default for many years; since version 4.0 the default is 16, combined with an algorithm that chooses the positions so they stay balanced.
How many keys move
If the hash spreads positions evenly, each of N servers owns about 1/N of the circle. A new server takes over part of the circle that is, on average, the same size as everyone else's share after the change, so about 1/(N + 1) of the keys move. Removing one of N servers moves the keys it held, about 1/N of the total. In both cases the moved keys go to or come from the changed server only.
| Change | Keys moved with hash mod N | Keys moved with consistent hashing |
|---|---|---|
| 3 servers to 4 | about 75% | about 25% |
| 10 servers to 11 | about 91% | about 9% |
| 100 servers to 101 | about 99% | about 1% |
These are averages. With few virtual nodes the actual number can differ quite a lot from the expected one, which the simulator shows when you set virtual nodes to 1.
Consistent hashing implementation in Python
A ring is a sorted list of positions. Adding a server inserts its virtual nodes; a lookup is a binary search for the first position at or after the key’s hash, wrapping round to the start of the list.
import bisect, hashlib
def h(s):
# 32-bit position on the ring; any well-mixed hash works
return int.from_bytes(hashlib.md5(s.encode()).digest()[:4], "big")
class Ring:
def __init__(self, nodes=(), vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted (position, node) pairs
for node in nodes:
self.add(node)
def add(self, node):
for i in range(self.vnodes):
bisect.insort(self.points, (h(f"{node}:{i}"), node))
def remove(self, node):
self.points = [p for p in self.points if p[1] != node]
def get(self, key):
i = bisect.bisect(self.points, (h(key),)) # first position at or after the key
return self.points[i % len(self.points)][1] # wrap round past the end
ring = Ring(["cache-a", "cache-b", "cache-c"])
ring.get("user:42") Run on 10,000 keys, adding a fourth server to this ring moved about 26% of them, close to the expected 25%, and every moved key went to the new server. In Java the same structure is usually a TreeMap, using ceilingEntry(hash) for the lookup and firstEntry() to wrap round.
Replication on the ring
Databases that use a ring usually store each key on more than one server. In the design described in Amazon's Dynamo paper, a key is stored on the first server clockwise from it and on the next N − 1 distinct servers after that, so that the data survives if one server fails. Cassandra and Riak work in a similar way. When a server leaves, each of the keys it held loses one copy, and the servers that take over its range copy those keys from the remaining replicas.
Variants
Several other schemes give the same "move only a few keys" property, with different trade-offs:
- Rendezvous hashing (highest random weight), described by David Thaler and Chinya Ravishankar in 1996. For each key, compute a score from the key and each server's name, and pick the server with the highest score. It needs no ring and no virtual nodes, and servers can be weighted easily, but each lookup checks every server.
- Jump consistent hash, published by John Lamping and Eric Veach of Google in 2014. A few lines of arithmetic map a key to one of N numbered buckets, with no table at all. Buckets can only be added or removed at the end of the numbering, so it suits data shards rather than servers that can fail individually.
- Maglev hashing, from Google's Maglev load balancer (Eisenbud and others, 2016). Each backend fills a large lookup table according to its own preference order, giving even load and lookups in constant time. When backends change, most entries stay the same, though a few more than the minimum may move.
- Consistent hashing with bounded loads, described by Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam in 2016. Each server has a capacity a little above the average load; when a server is full, the key goes to the next server clockwise. Vimeo used it in HAProxy, where it is available as the hash-balance-factor setting.
| Scheme | Lookup cost | Memory | Notes |
|---|---|---|---|
| Hash ring | Binary search | One entry per virtual node | Servers can join or leave anywhere |
| Rendezvous hashing | One score per server | None beyond the server list | Easy weighting; slower with many servers |
| Jump consistent hash | A few arithmetic steps | None | Buckets numbered 0 to N − 1; change only at the end |
| Maglev hashing | One table read | A fixed-size table | Very even load; slightly more movement |
| Bounded loads | Ring lookup, then a few steps | As for the ring | Caps each server at a set multiple of the average |
Where it is used
- Content delivery. Tom Leighton and Daniel Lewin, two of the paper's authors, co-founded Akamai in 1998, and consistent hashing was part of how it decided which of its servers should cache each piece of content.
- Key-value databases. Amazon's Dynamo paper (2007) used a ring with virtual nodes to place and replicate data. Cassandra and Riak followed the same approach.
- Distributed caches. Memcached servers do not talk to each other, so the client library chooses the server for each key. The ketama library, released by Last.fm in 2007, made consistent hashing the usual choice for memcached clients.
- Load balancers. Envoy offers ring hash and Maglev policies, HAProxy has hash-type consistent, and NGINX has hash … consistent. They are used to keep a given client or key on the same backend while the set of backends changes. Google's Maglev and the Cilium project's Kubernetes load balancing use Maglev hashing.
- Peer-to-peer systems. Distributed hash tables such as Chord (2001) place both nodes and data on a ring in the same way.
Consistent hashing in a system design interview
Consistent hashing comes up whenever a design spreads data or traffic over servers that come and go: a distributed cache, a key-value store, a sharded database, or a load balancer that should keep each user on the same backend. A good answer covers:
- Why not mod N. Adding one server to N moves almost all keys, which empties a cache all at once.
- The ring. Servers and keys hashed onto the same circle; a key belongs to the next server clockwise; a lookup is a binary search.
- Virtual nodes. Needed to balance the load and to spread a failed server’s keys over many others; servers with more capacity get more of them.
- Replication. Store each key on the next few distinct servers clockwise, as Dynamo and Cassandra do.
- Hot keys. Even placement does not mean even traffic; mention caching or splitting very popular keys.
- Alternatives. Fixed hash slots (Redis Cluster), rendezvous hashing, and range partitioning when the system needs range scans.
Limitations
Hot keys
Consistent hashing spreads keys evenly, not requests. If one key receives a large share of the traffic, the server that owns it receives that traffic too. Common remedies are a small cache in front of the servers, copying very popular keys to several servers, or splitting a hot key into several sub-keys.
No ordering
Hashing scatters neighbouring keys across servers, so a range query such as "all orders between 100 and 200" has to ask every server. Systems that need range scans, such as Spanner, CockroachDB and HBase, split data into ordered ranges instead.
No control over co-location
Keys that are used together, for example in one transaction, usually end up on different servers. Systems that need related keys together hash only part of the key, such as a customer ID, so that everything sharing that part lands in the same place.
Hash quality and hostile input
The scheme assumes a hash that spreads its output evenly. If keys come from untrusted users, an attacker who knows the hash function can choose keys that all land on one server. A keyed hash, such as SipHash with a secret key, prevents this.
Not everything that hashes is consistent
Some systems use plain hash mod N. Kafka's default partitioner, for example, assigns a key to a partition using a hash of the key modulo the number of partitions, which is why adding partitions to a topic changes where existing keys go.
History
Consistent hashing was introduced in the paper Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, presented at the ACM Symposium on Theory of Computing (STOC) in 1997 by David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin and Rina Panigrahy. Leighton and Lewin co-founded Akamai the following year.
The Chord distributed hash table (2001) used the same ring for peer-to-peer lookup, and Amazon's Dynamo paper (2007) brought it into wide use for databases. Rendezvous hashing, a related scheme, was published in 1996, and later variants include jump consistent hash (2014), Maglev hashing (2016) and consistent hashing with bounded loads (2016).
Consistent hashing questions and answers
What is consistent hashing?
Consistent hashing is a way of assigning keys to servers so that when a server is added or removed, only a small share of the keys move: about 1/N of them for N servers. Servers and keys are both hashed to positions on a circle, and each key belongs to the first server found by moving clockwise from it. It was introduced by David Karger and colleagues in 1997.
Why not just use hash mod N?
With hash(key) mod N, changing the number of servers changes the result for most keys. Going from N to N + 1 servers moves about N/(N + 1) of all keys, for example 75% when going from 3 to 4 servers. In a cache, every moved key becomes a miss at the same moment.
What are virtual nodes in consistent hashing?
With one position per server, the gaps between positions are uneven, so some servers own much more of the circle than others. Virtual nodes give each server many positions on the circle. Each server then owns many small arcs, which add up to a share much closer to the average, and a server that leaves hands its keys to many others instead of one neighbour.
How many virtual nodes should each server have?
Enough to even out the shares, usually somewhere between about 100 and a few hundred per server for a ring with random positions; the simulator shows the spread shrinking as you raise the number. More virtual nodes mean a larger table and slower rebuilds. Cassandra used 256 per node for years and since version 4.0 uses 16, with an algorithm that picks balanced positions instead of random ones.
What is the time complexity of consistent hashing?
A lookup is a binary search over the sorted ring positions, so it takes O(log(N × V)) time for N servers with V virtual nodes each. Adding or removing a server changes V positions, and moves about 1/N of the keys.
Does Redis Cluster use consistent hashing?
Not a hash ring. Redis Cluster divides the key space into 16,384 hash slots, puts each key in slot CRC16(key) mod 16384, and assigns slots to nodes. Adding a node means moving some slots to it, which gives a similar effect: only the keys in the moved slots change node.
What is the difference between consistent hashing and rendezvous hashing?
Rendezvous (highest random weight) hashing computes a score for every server from the key and the server name, and picks the server with the highest score. It needs no ring or virtual nodes and moves the same small share of keys when servers change, but each lookup costs time proportional to the number of servers, while a ring lookup is a binary search.
Where is consistent hashing used?
It was first used by Akamai for its content delivery network. It is used for data placement in Amazon’s Dynamo design and in Cassandra and Riak, in memcached client libraries such as ketama, and as a load-balancing policy in Envoy, HAProxy and NGINX. Google’s Maglev load balancer uses a related scheme.
Further reading
- Karger and others, 1997Consistent Hashing and Random TreesThe original paper, including the analysis of load balance.
- DeCandia and others, 2007Dynamo: Amazon's Highly Available Key-value StoreShows how a database uses the ring for placement and replication.
- Lamping and Veach, 2014A Fast, Minimal Memory, Consistent Hash AlgorithmJump consistent hash, with its short implementation.
- Eisenbud and others, 2016Maglev: A Fast and Reliable Software Network Load BalancerGoogle's load balancer and its lookup-table hashing scheme.
- Mirrokni, Thorup and Zadimoghaddam, 2016Consistent Hashing with Bounded LoadsHow to cap each server's load while keeping movement small.
- Stoica and others, 2001Chord: A Scalable Peer-to-peer Lookup Service for Internet ApplicationsA distributed hash table built on the same ring.
- SemicolonyHow load balancing worksWhere hashing fits among round robin, least connections and other policies.
- SemicolonyHow a CDN worksThe setting consistent hashing was invented for.