Hide outline
Feedback
Guide
Was this lesson helpful?
Dive Deeper
Generate a follow-up sub-lesson on any aspect of this topic
Guide complete
Consistent Hashing for Moving Node Sets
Generate a follow-up sub-lesson on any aspect of this topic
Consistent Hashing for Moving Node Sets
TLDR;
- Adding one cache node can turn most requests into misses if routing uses
hash(key) % N.- A ring-based mapping limits a membership change to a narrow, predictable blast radius of keys.
- Virtual nodes let the same three machines share load evenly and fail over in smaller pieces.
A cache cluster is easiest to reason about when we start with what it is doing for the application. Suppose an app serving 1M daily users stores session tokens in a cache so API servers can validate requests without hitting the database on every call. With one Redis server, every session token lookup goes to the same place, which is simple but becomes a bottleneck and a single point of failure as traffic grows. The moment we add cache nodes, we need a routing rule that tells any API server which cache node should hold a given session:{token} key. Here is the baseline next to a naive multi node approach:
In the single node baseline, there is one mapping from key to cache server, so a session token miss is just a normal cold cache event. In the three node naive setup, clients often pick a node with hash(key) % N, which seems stable until changes. When a node is added during a scale out, the mapping changes for most keys, so the new cluster looks empty even though it was warm seconds earlier.
The core failure in hash(key) % N routing is that the modulo boundary moves almost every key when changes. When goes from 3 to 4, the computed remainder for a given hash value typically changes, so the key that used to be routed to node 1 now routes to some other node. That is not a gradual rebalance, it is a near full reshuffle, which means a near full cache miss storm right after scaling. Those misses fall through to the backing database, and the database load spikes at the same time the cache tier is already under stress from reconnects and warmup.
A quick way to see the size of the blast radius is to look at what fraction of keys keep the same destination as we vary . The exact percentage depends on the hash distribution, but under a uniform hash it is close to the fraction of hashes whose remainder happens to match under both moduli, which is small for adjacent . Let’s visualize the remap rate as changes in this session token keyspace:
After the widget, the pattern to notice is that changing by 1 is not a small perturbation, it is effectively a new partitioning scheme. The database sees a thundering herd because many independent API servers all miss on different keys at once, and the cache provides little protection during that transition window.
Design rule
Prefer routing functions where a membership change moves a bounded slice of keys.
The design idea behind consistent hashing is to map both keys and cache nodes into the same large hash space, then assign each key to the next node clockwise. Concretely, pick a hash function that outputs bits, interpret hashes as points on , and place each cache node at the position hash(node_id). A session key like session:{token} is placed at hash(key). The owner is the first node encountered when walking clockwise from the key’s position. The segment of the ring a node is responsible for is its ownership interval, the arc from the previous node position (exclusive) to its own position (inclusive). Here is that mapping with three cache nodes and a few example session keys:
In the ring diagram, each node owns a contiguous clockwise interval, and every key falls into exactly one interval. That contiguity is what makes rebalancing local. When membership changes, only the intervals adjacent to the changed node positions are affected, instead of every key’s arithmetic changing at once.
Consistent hashing limits movement because adding or removing a node only changes who owns the keys in the intervals that touch that node’s position. When a new node joins at some point on the ring, it splits exactly one existing interval into two. Only the keys in that carved out slice move from the old owner to the new node. Under the simplifying assumption that node positions are uniform and independent, the expected slice size is about of the ring for nodes, so a single join moves about of keys instead of most keys. This is a heuristic expectation, not a guarantee, because real placements and key popularity can be skewed.
The same intuition lets us compare against mod N routing with the same and see how replication changes movement. If each key is stored on distinct successors on the ring, then a node addition still only changes which nodes appear in the first successors for keys in a limited set of intervals. Let’s estimate key movement under both approaches as we vary and :
After the widget, the important output is the order of magnitude difference. mod N behaves like a reshuffle, while ring based routing behaves like a splice. Replication increases the number of placements per key, so more cache entries are copied or fetched during rebalance, but the affected keys still come from a bounded region around the join or leave points.
A practical problem with placing one point per physical cache server is that random gaps can be uneven, so one server might own a huge interval and become hot. Virtual nodes fix this by giving each physical machine many independent positions on the ring, such as hash(node_id#vnode_index) for indices 0 through 99. Each vnode owns a small interval, and the physical machine owns the union of its vnodes’ intervals. With enough vnodes, the law of large numbers smooths out gap sizes, and the load per machine becomes more even. Vnodes also enable weighting, because a bigger machine can be assigned more vnodes and therefore more ring share.
Vnodes change failure and rebalance behavior from moving one big interval to moving many small ones. When one physical node fails, its vnodes are interleaved around the ring, so the lost intervals are spread across the remaining nodes, avoiding a single neighbor absorbing the whole load spike. Compare one vnode per node versus 100 vnodes per node for three physical nodes:
After the widget, the key components to notice are interval sizes and skew. With one vnode, ownership depends on three random gaps, so one node can accidentally own a large fraction of the ring. With 100 vnodes, each physical node owns many small intervals, so the total share is closer to one third, and the pieces that move on a failure are smaller and distributed.
Rule of thumb
Use enough vnodes that no single interval is operationally scary to move.
A cache cluster still needs a plan for when a node is down or a client is briefly out of date about membership. On a ring, replication is often defined as storing each key on the next distinct successors clockwise, so a read can fall back to the next replica if the first choice is unavailable. Replication improves availability but increases memory usage and makes writes more expensive, even in a cache, because multiple nodes must be updated to avoid serving stale session validation results. In practice, teams decide whether session validation can tolerate brief inconsistency, which is a cache flavored version of the CAP tradeoff between consistency and availability under network partitions.
The specific behaviors change a lot between and , so it helps to look at read path, write path, and failure impact side by side:
After the widget, the main numbers are the replica count and its cost. With , a node outage immediately causes misses for its share of keys. With or , many reads can succeed during a single node failure by walking to the next successor, but memory cost scales roughly linearly with , and write fanout increases.
Consistent hashing makes membership changes survivable, but it does not make the cache automatically stable. Hotspots still happen when key popularity is skewed, because even perfectly balanced ring intervals do not help if one session token is hammered by retries or a misbehaving client. Membership churn can also create repeated partial warmups, where the cluster is always moving of keys and never fully stabilizes. Client side routing introduces a staleness problem because each API server must learn node joins and leaves, and during propagation some clients will send traffic to dead nodes or to nodes that no longer own the key.
A few non obvious failure modes show up specifically in the session token cache scenario, and they often drive a move away from pure client side rings toward a directory service or proxy layer that centralizes membership and routing decisions. Here are the ones to watch for:
After the widget, the pattern is that the ring is a routing function, not a control plane. Something still has to distribute membership changes reliably, rate limit cold starts, and handle overloaded keys. When those concerns dominate, the extra hop through a smart proxy can be worth it because it turns many clients into one place to update.
Back in the 1M daily user session token cache, the point of the ring is not theoretical elegance, it is reducing the number of simultaneous cache misses when the node set changes. A defensible baseline is consistent hashing with a vnode count that keeps any single interval small, plus a replication factor that matches how much session validation unavailability the product can tolerate. If session tokens must be strongly consistent for logout or revocation semantics, replication also needs an update strategy that prevents stale reads, which can pull the design toward a leader based cache, short TTLs, or pushing validation to an authoritative store.
The choice among mod N, consistent hashing with vnodes, and a centralized directory is mostly about which failure mode you want to make rare. A decision matrix makes that trade visible for this scenario, and the constraint that usually forces a redesign is rapid autoscaling or frequent node churn, because it turns membership propagation and warmup into the dominant problem rather than steady state routing. Here is that comparison in one view:
After the widget, the useful outcome is a crisp reason for the routing choice. If the main risk is cache miss storms on resize, a ring with vnodes contains the blast radius. If the main risk is client staleness and fast churn, a directory or proxy can be the simpler operational boundary. When the constraint changes from stable membership to constantly shifting membership, the right design is the one whose control plane you can keep correct under that churn.