AI-narrated article. Prose is preserved with pronunciation adjustments; code and image cues refer to the written article.
Consistent Hashing for Cache Fleets: Make Membership Changes Recoverable
This is the AI-narrated article. The prose follows the written post; pronunciation is adjusted, and code and images are announced separately.
Keep cache routing stable through membership changes, then define the epoch, freshness and source-budget controls needed to recover safely from cold owners.
TL;DR: Consistent hashing limits ownership changes when cache membership changes, but it does not warm new nodes or synchronize client views. This article builds an immutable Python routing snapshot with canonical node IDs, domain-separated SHA-256, virtual nodes and explicit wraparound. Deterministic checks verify addition, removal and stable routing across process hash seeds. A safely reproduced membership disagreement shows why a cache miss cannot prove source absence. Production recovery needs validated membership epochs, bounded source fallback and controlled cold starts. Virtual nodes distribute ownership; they do not solve hot keys, replication, durability or authorization.
Membership changes turn routing into a reliability problem
A cache fleet grows during a traffic spike. The new capacity is empty, clients learn membership at different times, and source reads surge just when the origin is busiest. Consistent hashing reduces unnecessary reassignment, but it does not warm new caches or make clients agree about ownership.
The practical objective is a stable routing contract plus a bounded recovery path. Separate those responsibilities: use the ring to choose an owner, version membership explicitly, and protect the authoritative source during misses. A cache-routing function is not a distributed storage protocol.
The original consistent-hashing paper studies assignment under changing and inconsistent cache views. Its motivation remains useful: changing the available buckets should not require rebuilding every assignment. The operational controls below are a concrete application design, rather than guarantees inherited from that paper.
Preserve existing tokens when membership changes
Hash node tokens and keys into the same ordered space. Route a key to the first token at or after its position, wrapping to the smallest token when necessary. An inserted token owns the interval after its predecessor through its own position; other intervals retain their owners.
Image. Adding one token changes ownership of its preceding interval while other ring arcs remain unchanged
This diagram inserts one illustrative token D between A and B. Key X moves from B to D. A physical node normally contributes several virtual tokens, so adding it changes several arcs. The schematic is not a diagram of the example's actual SHA-256 positions.
Virtual nodes spread a physical node across the ring rather than letting one randomly placed token determine its share. They can improve distribution of key-space ownership, but neither equal key counts nor a larger ring guarantees equal request traffic. One popular key still has one primary owner in this design. The Dynamo paper describes virtual nodes and additional replication and membership mechanisms; the ring alone supplies none of those mechanisms.
Keep the virtual-node count and existing node IDs fixed across an add/remove operation. Changing either regenerates tokens and invalidates the limited-movement contract. Capacity weighting is omitted here deliberately: every member contributes the same configured number of tokens.
Define the bytes before writing the router
Python's built-in hash is unsuitable for this wire-level contract. The Python data model documents randomized string and byte hashes across processes. Persisted ownership must not depend on a process's random hash seed.
Our version-one contract uses SHA-256, an unsigned big-endian digest integer, and distinct domain prefixes for tokens and keys. A token hashes the ASCII node ID, a zero delimiter and a four-byte unsigned big-endian virtual-node index. Node IDs contain only the permitted lowercase ASCII characters; no delimiter can occur inside them.
The key API accepts bytes, so callers own canonical identity encoding. Agree on tenant, object identifier and revision framing across languages. Do not let one client hash a display label while another hashes a URL-normalized identifier. Domain separation prevents accidental token/key preimage overlap; it does not authorize tenants or hide keys.
The epoch labels a snapshot. It is intentionally excluded from token and key hashing: changing only the epoch must not remap the fleet.
Complete immutable routing snapshot
Prerequisites are Python 3.11 and a disposable local directory. Save this standard-library-only example as consistent_ring_22.py. It performs no network requests, stores no cache values and changes no running service. Construct snapshots with Ring.build; do not populate the dataclass directly.
Code example. Refer to the written article for the complete code.
Run without -O, which disables assertions:
Code example. Refer to the written article for the complete code.
The hashlib documentation defines the byte-oriented digest API. bisect_left finds the first token greater than or equal to the key's position; modulo handles the wrap.
Snapshots contain tuples and frozen fields. Build the next snapshot separately and install it through the application's chosen synchronization mechanism; frozen routing data does not supply a thread-safe rollout protocol. Accepted snapshots have bounded membership and token counts, but these are example admission limits rather than sizing recommendations. Validate manifest size before construction; do not pass unbounded iterables to the builder.
With P tokens, construction sorts P entries; selection uses binary search over them after hashing the key. There is no health checking, network retry, replication or storage migration in either operation. Cleanup only requires deleting the local example and its generated __pycache__ inside the disposable directory.
Reproduce disagreement without a cache deployment
The main block searches a bounded set of illustrative keys for one whose new owner is the added node. It then prints old and new ownership. The executed example found tenant-a/artifact-8@v1: epoch 1 selects cache-b, while epoch 2 selects cache-c.
That is a real execution of the routing function, not an observed distributed-cache outage. It safely exposes the failure's prerequisite: two valid snapshots can choose different owners for the same bytes. If only the old owner holds a value, a new client can miss even while the old client hits. Treating that miss as an authoritative “object absent” result would be a separate application error.
Diagnose the disagreement by recording the membership epoch, algorithm version, virtual-node count, canonical member IDs and selected owner. Associate each epoch with an immutable manifest digest, and reject a different manifest presented under an already known epoch. An epoch integer by itself does not prove two clients built the same ring.
Roll out ownership with a bounded cold path
Publish a validated next manifest, let clients build it before activation, and monitor adoption. Retain a known previous snapshot for a bounded transition if the read protocol permits an old-owner lookup. Make the epoch part of diagnostic context and, where implemented, request validation. A server can reject an unsupported epoch rather than silently applying a different mapping.
For a read-through cache, a miss should reach the authoritative source under an explicit timeout and concurrency budget. Coalesce concurrent fills for the same key, limit prewarming work, and ramp activation so newly owned arcs do not cause an unbounded origin surge. If the source budget is exhausted, use the service's defined unavailable or stale-data policy; do not manufacture absence.
Old-owner fallback is optional and must respect value freshness, authorization and tenant scope. A versioned immutable artifact is easier to reuse than mutable session state. Do not keep probing arbitrary nodes after a miss. For a removed or failed cache, plan recovery separately: surviving ownership stays stable, but values formerly held only by the unavailable node still need a source or valid replica.
Verify movement separately from traffic balance
The accompanying correctness checks compare 5,000 deterministic key routes before addition and removal. They found zero moves from an existing owner to another existing owner during addition, zero ownership changes outside the removed node's keys, and zero mismatches against a linear successor lookup. All 192 new-ring token boundaries and wraparound checks passed.
Two child processes with different Python hash seeds produced identical routes for 100 keys. Tests also rejected duplicate IDs, invalid input and an injected token collision. These observations check implementation behavior; sampled identifiers do not establish production request balance, latency or memory consumption. No distribution benchmark is claimed.
Observe request rate, miss/fill rate and source pressure by physical node, together with epoch adoption and routing disagreement. Key-space ownership and request load are separate signals. More virtual nodes cannot split one hot key; that needs a deliberate caching or replication strategy with its own consistency rules.
Keep proxy routing and cache ownership aligned
Envoy's versioned ring-hash documentation describes request hashing and endpoint hash identities, including stable metadata keys. A protocol hash policy is required; selecting ring hash without a meaningful request hash does not establish object affinity.
Its ring-hash API exposes ring-size and hash-function configuration. This Python SHA-256 ring is not compatible with Envoy's token construction. Choose one authoritative routing layer or explicitly specify and test interoperability. “Both use consistent hashing” is insufficient evidence that they choose the same cache.
Frequently asked questions
Does adding one node move every key? With unchanged existing tokens, only keys acquired by the new node change owner in this implementation.
Do virtual nodes eliminate hot keys? No. They distribute ring ownership; they do not divide one key's request stream.
Is choosing several owners equivalent to replication? No. Replication also needs writes, freshness, failure handling and a recovery protocol.
Can every client independently remove an unhealthy node? That changes its effective membership view. Define how the cache read protocol handles disagreement rather than assuming all clients still agree.