系統設計

1type Entry = [number, string | null];  // null is a tombstone
2 
3function fnv1a(s: string): number {
4  let h = 0x811c9dc5;
5  for (const byte of new TextEncoder().encode(s)) h = Math.imul(h ^ byte, 0x01000193);
6  return h >>> 0;
7}
8 
9class Bloom {
10  bits: Uint8Array;
11  constructor(keys: number[]) {
12    this.bits = new Uint8Array(Math.max(8, keys.length * 6));
13    for (const k of keys) for (const p of this.positions(k)) this.bits[p] = 1;
14  }
15  positions(key: number): number[] {
16    const h1 = fnv1a(String(key)), h2 = (fnv1a(key + "#") | 1) >>> 0;
17    return [h1 % this.bits.length, (h1 + h2) % this.bits.length];
18  }
19  mightContain(key: number): boolean {
20    return this.positions(key).every((p) => this.bits[p] === 1);
21  }
22}
23 
24class LSMTree {
25  memtable = new Map<number, string | null>();
26  levels: { entries: Entry[]; bloom: Bloom }[][] = []; // newest file first
27 
28  put(key: number, value: string | null): void {
29    this.memtable.set(key, value);
30    if (this.memtable.size >= 4) this.flush();
31  }
32 
33  flush(): void {
34    const entries = [...this.memtable].sort((a, b) => a[0] - b[0]);
35    this.memtable.clear();
36    this.addFile(0, entries);
37  }
38 
39  addFile(level: number, entries: Entry[]): void {
40    (this.levels[level] ??= []).unshift({ entries, bloom: new Bloom(entries.map((e) => e[0])) });
41    if (this.levels[level].length >= 3) {
42      const merged = mergeRuns(this.levels[level].map((f) => f.entries));
43      this.levels[level] = [];
44      this.addFile(level + 1, merged);
45    }
46  }
47 
48  get(key: number): string | null | undefined {
49    if (this.memtable.has(key)) return this.memtable.get(key);
50    for (const level of this.levels) {
51      for (const file of level) {
52        if (!file.bloom.mightContain(key)) continue;
53        const i = binarySearch(file.entries, key);
54        if (i >= 0) return file.entries[i][1];
55      }
56    }
57    return undefined;
58  }
59}
60 
61// Runs come newest first; for a key in several, the newest value wins.
62function mergeRuns(runs: Entry[][]): Entry[] {
63  const latest = new Map<number, string | null>();
64  for (let r = runs.length - 1; r >= 0; r--) {
65    for (const [k, v] of runs[r]) latest.set(k, v);
66  }
67  return [...latest].sort((a, b) => a[0] - b[0]);
68}
69 
70function binarySearch(entries: Entry[], key: number): number {
71  let lo = 0, hi = entries.length - 1;
72  while (lo <= hi) {
73    const mid = (lo + hi) >> 1;
74    if (entries[mid][0] === key) return mid;
75    if (entries[mid][0] < key) lo = mid + 1; else hi = mid - 1;
76  }
77  return -1;
78}