Consistent hashing primer

1.The ring abstraction

Imagine a circular keyspace from 0 to 2^32 - 1. Each node is hashed to a point on the ring, and each key is hashed to its own point. A key is owned by the first node found clockwise from its position. When a node leaves, only its successor inherits the keys.

2.Virtual nodes for balance

A single point per node leaves load imbalanced. Each physical node registers V virtual replicas (typically 100 to 200) at independent ring positions. The variance of keys per node falls as 1 / sqrt(V), which converges fast.

3.A minimal implementation

The reference implementation below uses a sorted ring of (position, node) pairs and a binary search to locate the owner for any key.

import { createHash } from 'crypto';

export class Ring {
  private points: Array<[number, string]> = [];

  add(node: string, vnodes = 128) {
    for (let i = 0; i < vnodes; i++) {
      const h = this.hash(`${node}#${i}`);
      this.points.push([h, node]);
    }
    this.points.sort((a, b) => a[0] - b[0]);
  }

  owner(key: string): string {
    const h = this.hash(key);
    for (const [p, n] of this.points) {
      if (p >= h) return n;
    }
    return this.points[0][1];
  }

  private hash(s: string): number {
    const d = createHash('md5').update(s).digest();
    return d.readUInt32BE(0);
  }
}