系統設計

1function hash(key: string): number {
2  let h = 0x811c9dc5;
3  for (const byte of new TextEncoder().encode(key)) {
4    h = Math.imul(h ^ byte, 0x01000193);
5  }
6  h = Math.imul(h ^ (h >>> 16), 0x85ebca6b);
7  h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35);
8  return (h ^ (h >>> 16)) >>> 0;
9}
10 
11class HashRing {
12  private points: number[] = [];                   // sorted positions
13  private owner = new Map<number, string>();
14  constructor(private vnodes: number) {}
15 
16  addServer(name: string): void {
17    for (let r = 0; r < this.vnodes; r++) {
18      const p = hash(`${name}#${r}`);
19      this.points.splice(this.firstAtOrAfter(p), 0, p);
20      this.owner.set(p, name);
21    }
22  }
23 
24  removeServer(name: string): void {
25    this.points = this.points.filter((p) => this.owner.get(p) !== name);
26  }
27 
28  getServer(key: string): string {
29    const p = hash(key);
30    let i = this.firstAtOrAfter(p);
31    if (i === this.points.length) i = 0;
32    return this.owner.get(this.points[i])!;
33  }
34 
35  private firstAtOrAfter(p: number): number {
36    let lo = 0, hi = this.points.length;
37    while (lo < hi) {
38      const mid = (lo + hi) >> 1;
39      if (this.points[mid] < p) lo = mid + 1;
40      else hi = mid;
41    }
42    return lo;
43  }
44}