系統設計

1type Clock = Record<string, number>;
2type Version = { value: string; clock: Clock };
3 
4function position(name: string): number {
5  let h = 0x811c9dc5;
6  for (const b of new TextEncoder().encode(name)) h = Math.imul(h ^ b, 0x01000193);
7  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b);
8  h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
9  return (h ^ (h >>> 16)) >>> 0;
10}
11 
12function descends(a: Clock, b: Clock): boolean {
13  return Object.keys(b).every((n) => (a[n] ?? 0) >= b[n]);
14}
15 
16function addVersion(list: Version[], v: Version): Version[] {
17  if (list.some((x) => descends(x.clock, v.clock))) return list;
18  return [...list.filter((x) => !descends(v.clock, x.clock)), v];
19}
20 
21class KvStore {
22  ring: string[];
23  alive: Set<string>;
24  data = new Map<string, Map<string, Version[]>>();
25  hints = new Map<string, Array<[string, string, Version]>>(); // holder -> [target, key, version]
26  counters = new Map<string, Map<string, number>>(); // key -> coordinator -> last count
27 
28  constructor(nodes: string[], private n: number, private w: number, private r: number, private sloppy: boolean) {
29    this.ring = [...nodes].sort((a, b) => position(a) - position(b) || (a < b ? -1 : 1));
30    this.alive = new Set(nodes);
31    for (const node of nodes) { this.data.set(node, new Map()); this.hints.set(node, []); }
32  }
33 
34  walk(key: string): string[] {
35    const h = position(key);
36    let start = this.ring.findIndex((node) => position(node) >= h);
37    if (start === -1) start = 0;
38    return this.ring.map((_, i) => this.ring[(start + i) % this.ring.length]);
39  }
40 
41  store(node: string, key: string, v: Version): void {
42    const table = this.data.get(node)!;
43    table.set(key, addVersion(table.get(key) ?? [], v));
44  }
45 
46  put(key: string, value: string, context: Clock = {}, via?: string): boolean {
47    const order = this.walk(key);
48    const targets: Array<[string, string | null]> = [];               // [node, hint for]
49    const standIns = order.slice(this.n).filter((x) => this.alive.has(x));
50    for (const node of order.slice(0, this.n)) {
51      if (this.alive.has(node)) targets.push([node, null]);
52      else if (this.sloppy && standIns.length) targets.push([standIns.shift()!, node]);
53    }
54    if (targets.length < this.w) return false;
55    const coord = via && targets.some((t) => t[0] === via) ? via : targets[0][0];
56    const counters = this.counters.get(key) ?? new Map<string, number>();
57    const observed = Math.max(0, ...(this.data.get(coord)!.get(key) ?? []).map(v => v.clock[coord] ?? 0));
58    const count = Math.max(context[coord] ?? 0, counters.get(coord) ?? 0, observed) + 1;
59    counters.set(coord, count); this.counters.set(key, counters);
60    const clock = { ...context, [coord]: count };
61    for (const [node, hintFor] of targets) {
62      this.store(node, key, { value, clock });
63      if (hintFor) this.hints.get(node)!.push([hintFor, key, { value, clock }]);
64    }
65    return true;
66  }
67 
68  get(key: string, order: string[]): Version[] | null {
69    const up = this.walk(key).filter((x) => this.alive.has(x));
70    const asked = this.sloppy ? up.slice(0, this.n)
71      : this.walk(key).slice(0, this.n).filter((x) => this.alive.has(x));
72    asked.sort((a, b) => order.indexOf(a) - order.indexOf(b));
73    const answered = asked.slice(0, this.r);
74    if (answered.length < this.r) return null;
75    let versions: Version[] = [];
76    for (const node of answered)
77      for (const v of this.data.get(node)!.get(key) ?? []) versions = addVersion(versions, v);
78    for (const node of answered)
79      for (const v of versions) this.store(node, key, v);
80    return versions;
81  }
82 
83  handoff(target: string): number {
84    if (!this.alive.has(target)) return 0;
85    let delivered = 0;
86    for (const [holder, list] of this.hints) {
87      if (!this.alive.has(holder)) continue;
88      const keep = list.filter(([t, key, v]) => {
89        if (t !== target) return true;
90        this.store(target, key, v);
91        delivered += 1;
92        return false;
93      });
94      this.hints.set(holder, keep);
95    }
96    return delivered;
97  }
98}