Consistent hashing and a membership change

With simple hash-modulo-node-count placement, changing the divisor changes assignments for many keys. A consistent scheme instead tries to preserve assignments among unaffected owners, assigning a joining node a share without arbitrarily reshuffling every existing key. The original ring approach places node positions and key hashes on an ordered space; ownership follows a defined successor rule. Other placement algorithms offer related properties, so specify the actual mapping rather than assuming all distributed key stores use the same ring.

Membership views must also converge. Clients using different node sets can reach different owners even when each computes its mapping correctly. Decide whether requests dual-read, migrate, redirect, or accept temporary misses, and how the transition handles writes. A cache miss after remapping is not necessarily data loss at the authoritative origin, but the refill traffic can still overwhelm it. Separate disposable cached replicas from any state whose relocation requires durable handoff.

A single random ring position can own a surprisingly large interval. Multiple virtual positions per physical node can reduce ownership imbalance, but the degree depends on count, weighting, hash quality, and the workload. Equal numbers of keys still need not mean equal memory if object sizes differ, or equal request rate if one key is very hot. A single hot object cannot be split just by adding virtual nodes unless the application's replication or partitioning protocol changes.

Replication and failover introduce additional owners and movement rules. Distinct virtual positions do not imply distinct physical failure domains. During a join, controlled warming or migration may preserve useful residency but consumes network and memory capacity. Pace that work and measure the actual moved bytes, origin requests, and overloaded owners. A theoretical expected fraction can look small while a skewed group of moved keys causes a large traffic spike.

Before adding capacity, record the current mapping, residency, owner load, and origin headroom. Compare expected movement with actual keys and bytes remapped in a staging trace or controlled rollout. Include retries and negative entries in the workload. Test a node failure separately from a planned join: absent old data and abrupt membership changes can create a different refill shape. A successful normal join does not establish correct degraded reads under inconsistent client views.

The probability lab represents a deliberately balanced fixed new-node share, not a hash-ring implementation. Reset and set both p=0.2, n=20, predict four sampled keys assigned to a new one-fifth share on average, then inspect. The trials assume independent uniform keys given that fixed share. A random single-position ring can have a variable share and correlated unconditional assignments, so its distribution need not be this binomial. Play highlights outcomes rather than moving actual keys; use the distinction to state the missing placement assumptions.