codejump
MediumPro challengePythonJavaScriptTypeScript

System Design — Rendezvous (HRW) Hashing

System DesignHashingDistributed Systems

consistent-hashing uses a ring. Rendezvous hashing (highest random weight) reaches the same
goal with no ring and no virtual nodes: for a key, score every node and pick the best.
Adding or removing a node only moves the keys that node wins or loses.

solve(args, ops) builds new Router(nodes) — args = [nodes], a list of node names — and
replays ops:

  • route(key) — return the node with the highest score for key, or null if there are no

nodes. The score of a node is hash(node + ":" + key). On equal scores the node name that
 sorts first (plain string order) wins.

  • add(node) / remove(node) — change the node set. Adding an existing node or removing an

unknown one changes nothing. Return nothing.

The hash is pinned so every language agrees (inputs are ASCII). Take the 32-bit FNV-1a
hash of the UTF-8 bytes (start at 2166136261; for each byte: h ^= byte; h = h * 16777619
modulo 2^32), then apply the murmur3 finalizer:

h ^= h >>> 16;  h = h * 0x85ebca6b (mod 2^32);  h ^= h >>> 13;  h = h * 0xc2b2ae35 (mod 2^32);  h ^= h >>> 16

The result is an unsigned 32-bit number. In JavaScript use Math.imul and >>> 0: a plain *
would lose precision above 2^53.

Sample tests

Test #1Keys spread over three nodes
Input: [[["cache-1","cache-2","cache-3"]],[["route","user:1"],["route","user:2"],["route","user:3"],["route","user:4"],["route","user:5"],["route","user:6"],["route","user:7"],["route","user:8"],["route","user:9"],["route","user:10"]]]
Output: ["cache-3","cache-3","cache-3","cache-2","cache-2","cache-2","cache-1","cache-1","cache-2","cache-1"]
Test #2Removing a node only moves the keys it owned
Input: [[["cache-1","cache-2","cache-3"]],[["remove","cache-2"],["route","user:1"],["route","user:2"],["route","user:3"],["route","user:4"],["route","user:5"],["route","user:6"],["route","user:7"],["route","user:8"],["route","user:9"],["route","user:10"]]]
Output: [null,"cache-3","cache-3","cache-3","cache-1","cache-1","cache-1","cache-1","cache-1","cache-1","cache-1"]
Test #3A new node only steals keys
Input: [[["cache-1","cache-2","cache-3"]],[["add","cache-4"],["route","user:1"],["route","user:2"],["route","user:3"],["route","user:4"],["route","user:5"],["route","user:6"],["route","user:7"],["route","user:8"],["route","user:9"],["route","user:10"]]]
Output: [null,"cache-3","cache-3","cache-3","cache-2","cache-2","cache-4","cache-1","cache-4","cache-2","cache-1"]
← All challenges