系統設計

1type Version = { value: number; createdBy: number; deletedBy: number | null };
2type Snapshot = { xmax: number; active: number[] };
3 
4class MvccDb {
5  rows = new Map<string, Version[]>();
6  status = new Map<number, string>([[0, "committed"]]);
7  snapshots = new Map<number, Snapshot>();
8  locks = new Map<string, number>();
9  waitsFor = new Map<number, number>();
10  nextTx = 1;
11 
12  constructor(initial: Record<string, number>) {
13    for (const [row, value] of Object.entries(initial)) this.rows.set(row, [{ value, createdBy: 0, deletedBy: null }]);
14  }
15 
16  begin(): number {
17    const tx = this.nextTx++;
18    const active = [...this.status].filter(([, s]) => s === "active").map(([id]) => id);
19    this.status.set(tx, "active");
20    this.snapshots.set(tx, { xmax: tx, active });
21    return tx;
22  }
23 
24  // Does tx see what "other" did? Its own work, or a commit before its snapshot.
25  sees(tx: number, other: number | null): boolean {
26    if (other === null) return false;
27    if (other === tx) return true;
28    const snap = this.snapshots.get(tx)!;
29    return this.status.get(other) === "committed" && other < snap.xmax && !snap.active.includes(other);
30  }
31 
32  read(tx: number, row: string): number | null {
33    const versions = this.rows.get(row) ?? [];
34    for (let i = versions.length - 1; i >= 0; i--) {
35      const v = versions[i];
36      if (this.sees(tx, v.createdBy) && !this.sees(tx, v.deletedBy)) return v.value;
37    }
38    return null;
39  }
40 
41  write(tx: number, row: string, value: number): string {
42    const holder = this.locks.get(row);
43    if (holder !== undefined && holder !== tx) {
44      for (let at: number | undefined = holder; at !== undefined; at = this.waitsFor.get(at)) {
45        if (at === tx) return "deadlock";
46      }
47      this.waitsFor.set(tx, holder);
48      return "wait";
49    }
50    this.waitsFor.delete(tx);
51    const versions = this.rows.get(row)!;
52    let live = versions.length - 1;
53    while (live >= 0 && this.status.get(versions[live].createdBy) === "aborted") live--;
54    const current = versions[live];
55    if (current.createdBy === tx) {
56      current.value = value;
57      return "ok";
58    }
59    if (!this.sees(tx, current.createdBy)) return "conflict";
60    this.locks.set(row, tx);
61    current.deletedBy = tx;
62    versions.push({ value, createdBy: tx, deletedBy: null });
63    return "ok";
64  }
65 
66  finish(tx: number, status: string): number[] {
67    if (status === "aborted") {
68      for (const versions of this.rows.values())
69        for (const v of versions) if (v.deletedBy === tx) v.deletedBy = null;
70    }
71    this.status.set(tx, status);
72    const waiters = [...this.waitsFor].filter(([, h]) => h === tx).map(([w]) => w);
73    for (const [row, h] of [...this.locks]) if (h === tx) this.locks.delete(row);
74    this.waitsFor.delete(tx);
75    for (const w of waiters) this.waitsFor.delete(w);
76    return waiters;
77  }
78 
79  vacuum(): number {
80    const active = [...this.status].filter(([, s]) => s === "active").map(([id]) => id);
81    let removed = 0;
82    for (const [row, versions] of this.rows) {
83      const kept = versions.filter((v) => {
84        if (this.status.get(v.createdBy) === "aborted") return false;
85        const d = v.deletedBy;
86        const dead = d !== null && this.status.get(d) === "committed" && active.every((t) => this.sees(t, d));
87        return !dead;
88      });
89      removed += versions.length - kept.length;
90      this.rows.set(row, kept);
91    }
92    return removed;
93  }
94}