How to use the consistent hash ring simulator
- List the nodes, one per line, such as cache servers. At least 2 and at most 50.
- Set the points each node places on the ring (more points spread the keys more evenly) and the number of keys to test.
- Choose whether to add or remove a node and type its name.
- Read the share of keys that moved on the ring, the share that would move with modulo hashing, and the keys per node before and after.
Formula
point = hash("name#i") for i from 0 to points - 1
owner of a key = the first point at or after hash(key), wrapping around
modulo hashing: node number = hash(key) mod number of nodes
The hash is FNV-1a over the UTF-8 bytes followed by the MurmurHash3 finalizer, giving a number from 0 to 4,294,967,295. Keys are named key-1, key-2 and so on.
Adding a fourth node
With cache-a, cache-b and cache-c, 100 points each and 10,000 keys, adding cache-d moves 2,354 keys on the ring, which is 23.54%, close to the fair share of 25.00% (one in four). The new node ends up with 2,354 keys, so every moved key went to it.
With modulo hashing the same change moves 7,476 keys, or 74.76%, since a key keeps its node only when hash mod 3 equals hash mod 4. The ring keeps the other three quarters of the keys where they were.
Why systems use a ring
Distributed caches and stores must decide which node holds each key. If the choice depends on the number of nodes, every resize reshuffles almost everything, and caches lose their contents. On a ring, a node owns only the stretches just before its own points, so a change moves only about 1 / (nodes) of the keys. The best known use is spreading cache keys over servers, and the same idea guides some databases and load balancers.
With few points per node the ring is lumpy and some nodes get far more keys than others; many points even out the load. Try the preset with 3 points to see the effect. For what happens inside a node, see the Cache Replacement Policy Simulator, and for hashing itself the Hash Generator.
What the page leaves out
Replication, weights for bigger servers, failure detection and the time it takes to move data are not modeled. The counts are exact for the hash and names used, and a different hash function gives somewhat different numbers.
Assumptions and limits
- Every node uses the same number of points, from 1 to 500.
- Up to 100,000 keys are tested and node names must be different.
- Removing a node needs at least 3 nodes in the list so 2 remain.
- Modulo hashing numbers the nodes in the order listed, with a new node added last.
- A key moves if its owner changes; keys of a removed node necessarily move.
Frequently asked questions
Why is the ring result not exactly 25%?
Points are placed pseudo randomly, so the new node's share of the ring is close to, but not exactly, one quarter. More points per node narrow the gap.
Why do the keys move to only one node when I add one?
A new node only takes over ranges just before its own points. Nothing else changes ownership, so every moved key goes to the new node.
What happens when I remove a node?
Only its keys move, to the next points on the ring, which spreads them over the remaining nodes.
Does the choice of hash function matter?
Yes. A weak hash clusters points and keys. The page mixes FNV-1a with a finalizer so that similar names spread out.