Design: a key-value store

get(key)                    → { values: [value, …], context }    one value normally, several on conflict
put(key, value, context?)   → ok                                 context: the version the writer read

type Versioned = { value: string; version: number };
const hash32 = (s: string) => createHash("md5").update(s).digest().readUInt32BE(0);

export class KvCluster {
  private ring: [number, string][] = []; // (position, physical node), sorted
  data = new Map<string, Map<string, Versioned>>();
  hints = new Map<string, { owner: string; key: string; v: Versioned }[]>();
  down = new Set<string>();

  constructor(nodes: string[], readonly n = 3, readonly w = 2, readonly r = 2, vnodes = 64) {
    for (const node of nodes) {
      this.data.set(node, new Map());
      for (let i = 0; i < vnodes; i++) this.ring.push([hash32(`${node}#${i}`), node]);
    }
    this.ring.sort((a, b) => a[0] - b[0]);
  }

  /** Walk clockwise from the key, collecting distinct physical nodes. */
  walk(key: string): string[] {
    const h = hash32(key);
    let i = this.ring.findIndex(([p]) => p >= h);
    if (i < 0) i = 0;
    const out: string[] = [];
    for (let k = 0; out.length < this.data.size && k < this.ring.length; k++) {
      const node = this.ring[(i + k) % this.ring.length][1];
      if (!out.includes(node)) out.push(node);
    }
    return out;
  }

  put(key: string, value: string, version: number) {
    const all = this.walk(key);
    const spares = all.slice(this.n).filter((s) => !this.down.has(s));
    let acks = 0;
    for (const owner of all.slice(0, this.n)) {
      const v = { value, version };
      if (!this.down.has(owner)) {
        this.store(owner, key, v);
        acks++;
      } else if (spares.length) {
        const holder = spares.shift()!; // sloppy quorum: a healthy stand-in keeps it, with a hint
        this.store(holder, key, v);
        this.hints.set(holder, [...(this.hints.get(holder) ?? []), { owner, key, v }]);
        acks++;
      }
    }
    if (acks < this.w) throw new Error(`only ${acks} of ${this.w} writes acknowledged`);
  }

  get(key: string) {
    const replies = this.walk(key).filter((node) => !this.down.has(node)).slice(0, this.n)
      .map((node) => this.data.get(node)!.get(key));
    if (replies.length < this.r) throw new Error("not enough replicas");
    return replies.filter(Boolean).sort((a, b) => b!.version - a!.version)[0];
  }

  /** When a node comes back, every stand-in hands its hints over. */
  recover(node: string) {
    this.down.delete(node);
    for (const [holder, list] of this.hints) {
      this.hints.set(holder, list.filter((h) => (h.owner === node ? (this.store(node, h.key, h.v), false) : true)));
    }
  }

  private store(node: string, key: string, v: Versioned) {
    const cur = this.data.get(node)!.get(key);
    if (!cur || cur.version < v.version) this.data.get(node)!.set(key, v);
  }
}