Membership, Gossip and Hashing

// consistent hashing with virtual nodes
import { createHash } from 'node:crypto';
const h = (s: string) => createHash('md5').update(s).digest().readUInt32BE(0);

class Ring {
  private points: { at: number; node: string }[] = [];
  add(node: string, vnodes = 128) {
    for (let v = 0; v < vnodes; v++) this.points.push({ at: h(`${node}#${v}`), node });
    this.points.sort((a, b) => a.at - b.at);
  }
  remove(node: string) { this.points = this.points.filter(p => p.node !== node); }
  get(key: string): string {
    const k = h(key); let lo = 0, hi = this.points.length;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (this.points[mid].at < k) lo = mid + 1; else hi = mid; }
    return this.points[lo % this.points.length].node;     // next point clockwise, wrapping
  }
}
// adding a fourth node to three moves about a quarter of keys; mod N would move about three quarters