Consistent Hashing Ring with Virtual Nodes

Maps keys to nodes so that adding or removing a node moves only about 1/N of the keys, not nearly all of them.

const ring = new HashRing({ vnodesPerWeight: 128 });
ring.addNode('A').addNode('B').addNode('C', { weight: 2 });
ring.getNode('user:42');        // 'C'
ring.getNodes('user:42', 3);    // ['C', 'A', 'B'], a replica preference list of distinct nodes
ring.ownership();               // { A: 0.25.., B: 0.24.., C: 0.51.. }, exact share of the hash space

The problem and where it shows up

With node = hash(key) % N, changing N from 4 to 5 remaps about 1 - 1/5 = 80% of keys (the demo measures 79.7%). For a cache fleet that is a mass cold-miss event. For a datastore it is a mass data migration. Consistent hashing puts both keys and nodes on a circle, and a key belongs to the next node clockwise. A membership change only affects the arcs next to the changed node. It's used in:

• Amazon Dynamo / DynamoDB-lineage stores and Riak: partitioning and replica preference lists.
• Apache Cassandra: token ring. Each node owns num_tokens vnodes (the default dropped from 256 to 16 in 4.0, with a token-allocation algorithm to keep balance).
• Memcached clients (libketama, spymemcached): client-side key-to-server selection.
• Load balancers: Envoy RING_HASH and MAGLEV, NGINX hash ... consistent, HAProxy hash-type consistent, for session affinity and cache locality.
• Discord, Akamai and others: routing users or objects to shards and cache servers.

Design

0 / 2^32
         A#7 .   . B#2
     C#1 .           . A#3        key k: h = md5(k)[0..4] as uint32
        .      ring     .          owner = first vnode with point >= h (wrap to index 0)
     B#9 .           . C#4
          C#0 .   . A#1

• Hash space: uint32. The default hash is the first 4 bytes of MD5, as libketama does. Any (string) => uint32 can be injected; the tests use one that places points at chosen positions.
• Virtual nodes: node X of weight w gets round(vnodesPerWeight * w) points (at least 1), at hash("X#0") ... hash("X#k-1"). Many small arcs per node average out the randomness of arc lengths.
• Storage: two parallel sorted arrays, points[] and owners[]. Lookup is a lower-bound binary search, and a hash past the last point wraps to index 0. A point exactly equal to the key hash owns the key.
• Collisions: if two vnodes hash to the same point, the node with the smaller id wins. Ties are broken the same way everywhere, so every process builds a byte-identical ring (tested).
• Preference list (getNodes(key, n)): walk clockwise from the key's position and skip vnodes whose physical node was already chosen. This returns min(n, size) distinct nodes, which is the Dynamo "skip positions to ensure distinct physical nodes" rule.
• Ownership: the arc (points[i-1], points[i]] belongs to owners[i], and index 0 also owns the wrap arc. ownership() sums the arcs exactly, so it doesn't need sampling.
• Movement stats: assignments(keys) snapshots key→node. movementStats(before, after) returns the moved count, the fraction, and the from->to flow matrix.

Invariants (all tested)

1. Adding node X: every key that moves, moves to X.
2. Removing node X: every key that moves, moves from X. The number moved equals X's key count.
3. Reweighting X only moves keys to or from X, because X's vnode set grows or shrinks as a prefix X#0..k.
4. Preference lists contain distinct nodes, and element 0 is getNode(key).
5. Removing a replica keeps the other replicas in the same relative order. Only the tail changes.
6. Ownership shares sum to 1. Binary search agrees with a linear scan.

Complexity

V = total vnodes, N = physical nodes. The rebuild is deliberately simple. Membership changes are rare compared with lookups, and an incremental sorted merge would be O(V).

Balance vs vnodes (from demo.js, 4 nodes, 100k keys)

Imbalance falls roughly as 1/sqrt(vnodes). The cost is memory and a slightly longer binary search.

Failure modes and trade-offs

• Too few vnodes: hot nodes get 2x their share. Too many: memory, rebuild time, and (in Cassandra) repair and streaming overhead per token range. That is why Cassandra reduced its default.
• Hot keys are not fixed by hashing: a single viral key still lands on one node. Mitigate with key salting or splitting, replica reads, or a local cache in front.
• Membership disagreement: if clients hold different rings (for example, one hasn't seen a node leave), the same key routes to different nodes. Real systems spread ring state by gossip or a coordination service, and tolerate a convergence window (hinted handoff, read repair).
• Cascading failure: when a node dies, its whole load moves to its clockwise successors. With vnodes it is spread over many successors, which is one of the main reasons for vnodes.
• Replicas in the same failure domain: distinct nodes aren't distinct racks/AZs. Production preference lists also skip nodes in an already-used rack (Cassandra's NetworkTopologyStrategy).
• Weights are approximate: shares converge to the weight ratio only as vnodes grow (the demo's 2x node gets 52.2%, not 50%).

How production systems do it

• libketama (memcached): each server gets about 160 points weighted by memory. Each MD5 digest yields 4 32-bit points, so it runs 40 digests per server.
• Cassandra: Murmur3Partitioner with a signed 64-bit token space. Since 4.0, num_tokens: 16 plus allocate_tokens_for_local_replication_factor places tokens to minimize imbalance instead of choosing them at random.
• Dynamo (2007 paper): evolved from random tokens per node (strategy 1) to Q equal-sized fixed partitions with tokens assigned to nodes (strategy 3), which decouples partitioning from placement and makes bootstrap and recovery simpler. Preference lists skip positions so replicas land on distinct physical nodes.
• Envoy: RING_HASH (configurable minimum_ring_size, default 1024) or MAGLEV (a 65537-entry lookup table, O(1) lookup, near-perfect balance, slightly more disruption on change).
• Jump consistent hash (Google, 2014): no ring and no memory, O(log N), perfect balance, but only for numbered buckets that are added or removed at the end.
• Rendezvous (HRW) hashing: score every node with hash(key, node) and take the max. O(N) per lookup, no vnodes needed, and a natural top-k preference list.

Extension exercises

1. Rack-aware preference lists: give nodes a zone and make getNodes skip nodes whose zone is already used, falling back to reusing zones only when there are fewer zones than replicas.
2. Incremental add/remove: replace the full rebuild with an O(V) sorted merge or filter, and benchmark both at 10k vnodes.
3. Bounded loads (Google/Vimeo, 2017): cap each node at (1+ε) * average load and send overflow clockwise. Measure the max load under a Zipf workload.
4. Rendezvous vs ring: implement HRW, then compare movement, balance and lookup cost at N = 5, 50 and 500.
5. Ketama-compatible mode: 4 points per MD5 digest and weight-proportional point counts. Check your ring matches a known libketama server list.