Design a Key-Value Store

// A strict quorum fails the write when W of the N owners are unreachable.
// A sloppy quorum writes to the next healthy nodes on the ring instead, tagging
// each write with a hint naming the node it really belongs to. The stand-in
// keeps hinted writes in a separate area and replays them when the owner
// returns, then deletes its copy.
export async function putSloppy(ring, key, value, clock) {
  const owners = await Promise.all(
    preferenceList(ring, key).map(async (n) => ({ node: n, up: await n.isHealthy() })),
  );

  const targets = [];
  const hintedFor = new Map();   // stand-in id -> owner id

  for (const { node, up } of owners) {
    if (up) { targets.push(node); continue; }
    const standIn = nextHealthyAfter(ring, node, [...owners.map((o) => o.node), ...targets]);
    if (!standIn) continue;      // nothing left to take it; W may not be reached
    hintedFor.set(standIn.id, node.id);
    targets.push(standIn);
  }

  return quorum(
    targets.map((n) => n.write(key, value, clock, { hintedFor: hintedFor.get(n.id) ?? null })),
    W,
  );
}

// Durability survives; the quorum guarantee does not. A read that asks only
// the N nodes in the preference list can miss a write that only stand-ins
// acknowledged, so a client can read its own write as absent. Anti-entropy
// (Dynamo compared Merkle trees of key ranges between replicas) eventually
// closes the gap, but "eventually" is the whole point of the word.

// Two writes whose clocks neither dominates the other are genuinely concurrent.
// The store cannot order them. The application can merge them.
function dominates(a, b) {
  // `a` dominates `b` if a >= b at every node and strictly greater somewhere.
  let strictly = false;
  for (const node of new Set([...Object.keys(a), ...Object.keys(b)])) {
    const x = a[node] ?? 0;
    const y = b[node] ?? 0;
    if (x < y) return false;
    if (x > y) strictly = true;
  }
  return strictly;
}

export function reconcile(versions) {
  // Discard any version that some other version descends from.
  const siblings = versions.filter(
    (v) => !versions.some((other) => dominates(other.clock, v.clock)),
  );
  if (siblings.length === 1) return { value: siblings[0].value, context: { clock: siblings[0].clock } };

  // Cart merge, the example the Dynamo paper uses. Union the additions, then
  // apply the removals: union alone makes deleted items reappear, which is the
  // behaviour the paper reports as visible to customers.
  const lines = new Map();
  for (const s of siblings) {
    for (const line of s.value.items) {
      lines.set(line.sku, Math.max(lines.get(line.sku) ?? 0, line.qty));
    }
  }
  for (const s of siblings) for (const sku of s.value.removed ?? []) lines.delete(sku);

  // The merged context descends from all siblings, so writing it back collapses
  // them into one version.
  const clock = {};
  for (const s of siblings) {
    for (const [node, n] of Object.entries(s.clock)) clock[node] = Math.max(clock[node] ?? 0, n);
  }
  return { value: { items: [...lines].map(([sku, qty]) => ({ sku, qty })) }, context: { clock } };
}

// LSM tree, which is what the node under the quorum usually is (Bigtable,
// Cassandra, RocksDB all take this shape).
export class LsmNode {
  constructor({ memtableBytes = 64 * 1024 * 1024 } = {}) {
    this.limit = memtableBytes;
    this.memtable = new Map();   // in a real engine: a skip list, kept sorted
    this.bytes = 0;
    this.tables = [];            // newest SSTable first
  }

  async write(key, value, clock) {
    // 1. Append to the write-ahead log. This is the only durability point; the
    //    memtable is lost on a crash and rebuilt by replaying the log.
    await this.wal.append({ key, value, clock });
    // 2. Insert in memory. Both steps are sequential writes: no page to find,
    //    no page to rewrite. That is why LSM write throughput is high.
    this.memtable.set(key, { value, clock });
    this.bytes += key.length + value.length;
    if (this.bytes > this.limit) await this.flush();   // freeze, write an SSTable
  }

  async read(key) {
    const hot = this.memtable.get(key);
    if (hot) return hot;                 // the newest version is in memory

    // Newest SSTable first, stop at the first hit - an older file may hold a
    // superseded version. The Bloom filter answers "definitely not in this
    // file" without touching disk; a false positive costs one wasted read, and
    // a false negative cannot happen.
    for (const table of this.tables) {
      if (!table.bloom.mightContain(key)) continue;
      const found = await table.lookup(key);
      if (found) return found.tombstone ? null : found;
    }
    return null;
  }
}

// A delete writes a tombstone rather than removing anything: the key may exist
// in several older files, and only compaction can drop them all. Until then,
// deleted keys still cost reads - and a tombstone deleted too early lets an
// old value come back from a replica that never saw the delete.