Consistent Hashing

1// ============================================
2// Consistent Hashing — Implementation
3// ============================================
4
5class ConsistentHash {
6  constructor(virtualNodes = 150) {
7    this.virtualNodes = virtualNodes;
8    this.ring = new Map();       // hash position → node
9    this.sortedKeys = [];        // sorted hash positions
10    this.nodes = new Set();
11  }
12
13  addNode(node) {
14    this.nodes.add(node);
15    for (let i = 0; i < this.virtualNodes; i++) {
16      const hash = this.hash(`\${node}:vn\${i}`);
17      this.ring.set(hash, node);
18      this.sortedKeys.push(hash);
19    }
20    this.sortedKeys.sort((a, b) => a - b);
21  }
22
23  removeNode(node) {
24    this.nodes.delete(node);
25    for (let i = 0; i < this.virtualNodes; i++) {
26      const hash = this.hash(`\${node}:vn\${i}`);
27      this.ring.delete(hash);
28      this.sortedKeys = this.sortedKeys.filter(k => k !== hash);
29    }
30  }
31
32  getNode(key) {
33    if (this.sortedKeys.length === 0) return null;
34    const hash = this.hash(key);
35    // Find first position on ring >= hash (clockwise)
36    for (const pos of this.sortedKeys) {
37      if (pos >= hash) return this.ring.get(pos);
38    }
39    return this.ring.get(this.sortedKeys[0]); // Wrap around
40  }
41
42  hash(key) {
43    let hash = 0;
44    for (let i = 0; i < key.length; i++) {
45      hash = ((hash << 5) - hash + key.charCodeAt(i)) >>> 0;
46    }
47    return hash;
48  }
49}
50
51// Demo: Add/remove node only affects ~1/N keys
52const ch = new ConsistentHash(100);
53ch.addNode('server-1');
54ch.addNode('server-2');
55ch.addNode('server-3');
56
57const keys = Array.from({length: 100}, (_, i) => `key_\${i}`);
58const before = keys.map(k => ({ key: k, node: ch.getNode(k) }));
59
60ch.addNode('server-4');
61const after = keys.map(k => ({ key: k, node: ch.getNode(k) }));
62
63const moved = keys.filter((k, i) => before[i].node !== after[i].node);
64console.log(`Keys moved after adding server-4: \${moved.length}/\${keys.length}`);
65// ~25% moved (1/4), not 75% like with mod hashing!