Consistent hashing

01Stabilize placement when membership changes

A cache stores each object on one machine. To choose a machine, it runs a repeatable calculation on the object key, called a hash. A simple rule divides the result by three and uses the remainder to select one of three machines: hash(key) mod 3.

Adding a fourth machine changes the divisor to four. Many keys now choose a different machine. That causes cold misses in a cache and requires actual record movement in retained storage. Consistent hashing aims to keep most assignments stable when machines join or leave.

Build a small ring calculation:

1. Use positions 0 through 99 arranged in a circle.
2. Assign machine A position 20, B position 50, and C position 80. These assigned positions are tokens; abbreviate them as A20, B50, and C80.
3. Hash a data key into the same position range.
4. Move clockwise from the key’s position to the first machine token. That machine owns the key.
5. If no token remains before 99, wrap around to the start. A key exactly on a token belongs to that token in this example.

Apply the rule:

• Key 12 reaches A20 first, so A owns it.
• Key 44 reaches B50 first, so B owns it.
• Key 90 wraps around and reaches A20 first.

The ring describes a placement calculation. It is not physical network wiring and does not make machines send requests clockwise.

02Add a node and identify the exact movement

Now assign a new machine D position 35. Work from the key to its old and new destination:

1. Before D joins, key 28 reaches B50 first.
2. After D joins, key 28 reaches D35 before B50.
3. Every key greater than 20 and up to 35 changes in the same way. Write this interval as (20,35]: exclude 20, include 35.
4. B previously held those records, so B must transfer them to D. A’s token at 20 marks the lower boundary; it does not mean A stored the transferred interval.

Only the newly assigned interval changes in this simplified update. Its size depends on the actual token positions; there is no fixed movement percentage for every deployment. Removing a token transfers its interval to the next eligible owner.

One token per physical machine can create uneven intervals by chance. Give a machine several positions and it owns several smaller intervals instead. These additional positions are called virtual nodes or virtual tokens.

• More positions provide flexibility for dividing and moving ownership.
• A larger-capacity machine can receive a tested larger share of positions.
• More positions add mapping information and movement work.
• One popular key still chooses one owner under this rule. Extra positions do not automatically spread that key’s requests.

03Separate placement, copies, and commitment

Calculating B-to-D placement does not copy any bytes. A retained store needs a separate transition:

1. Copy the affected records from B to D.
2. Capture and apply writes that arrive while copying proceeds.
3. Pause new writes for the moving interval, finish writes already accepted by B, then verify D has copied those records and applied every accepted change.
4. In this illustrative handoff, save D as the new owner and have B forward requests from clients with the old machine list. B must not keep accepting independent writes for the transferred interval; resume writes for the transferred interval at D.
5. Retain the saved owner and move progress across a crash. Retire B’s old copy only after D’s records and required replicas are verified. Use the store’s supported movement protocol to enforce this handoff.

Copy placement is another separate decision:

• If several successive tokens belong to the same physical machine, they do not provide independent replicas.
• Choose distinct physical owners and the required zones for retained copies.
• Define when a write succeeds and which reads may use a lagging copy. Knowing its destination does not prove that copies agree on accepted changes.

Rendezvous hashing offers another stable-placement method without a ring:

1. Calculate a repeatable score for each pair of data key and eligible machine.
2. Choose the machine with the highest score.
3. When D joins, a key moves only if its score with D beats its previous winning score.

The score still does not transfer data, establish independent copies, or settle concurrent writes. In an interview, work an addition and a removal with actual numbered keys, then explain movement, uneven demand, and the failure locations of copies.