Concepts and theorems · Intermediate

Consistent hashing: limit placement changes as membership changes

Compute ownership on a hash ring and separate virtual nodes, imbalance, migration and consistency.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Membership changes alter placement
  2. Work through a ring insertion
  3. Virtual nodes improve distribution, conditionally
  4. Migration needs a data protocol
  5. Ask Logeia about this articleCheck your understanding

Membership changes alter placement

A placement rule based on hash(key) modulo N can move many keys when the node count changes. Consistent hashing aims to limit how placement changes as members join or leave. This article uses a ring where both keys and nodes have positions, and a key belongs to the next node clockwise. Other consistent-placement schemes need not use exactly this representation. The central idea is placement stability under membership changes, which is separate from equal utilization, replication correctness or the consistency semantics of operations performed on the placed data.

Work through a ring insertion

On an illustrative ring from zero to less than one hundred, place A at twenty, B at sixty and C at ninety. Keys at ten, forty-five, seventy-five and ninety-five belong to A, B, C and A respectively. Add D at forty. The interval greater than twenty and up to forty moves from B to D. A key at thirty moves; a key at forty-five remains at B. This is a placement calculation rather than a measured workload. Avoid saying the new owner takes data from the preceding node: under this successor rule the displaced owner is the next old node clockwise.

Virtual nodes improve distribution, conditionally

Representing each physical node by one point can produce uneven interval sizes. Multiple virtual nodes distribute one machine’s ownership across several intervals and can support capacity weighting. They do not guarantee balanced request load. A popular key can dominate traffic even when key counts and hash-space lengths are balanced, and assigning more tokens does not split that one key’s operations automatically. Observe item counts, bytes, request frequency and write cost separately. Replication, caching or a redesigned hot-key representation may be needed. The relevant balance measure must match the resource that is actually exhausted.

Migration needs a data protocol

During migration, clients may temporarily use different membership maps. Define where new writes go, whether they are copied to multiple owners, and when old data may be deleted. Correct hash arithmetic cannot prevent loss if that transition protocol is incomplete. A design choosing consecutive replica positions must also avoid accidentally selecting the same physical machine or failure domain several times. The word consistent here describes placement behaviour, not a latest-value read guarantee. Membership, routing, migration and version handling need their own contracts before the entire storage system has a defensible correctness claim.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 18

Choose a learning path