系統設計

1type Policy = "write-through" | "write-around" | "write-back";
2 
3class CachedStore {
4  cache = new Map<number, number>();   // LRU order: oldest first
5  dirty = new Map<number, number>();   // written to cache, not yet to db
6  db = new Map<number, number>();
7  dbWrites = 0;
8 
9  constructor(private capacity: number, private policy: Policy) {}
10 
11  read(key: number): number {
12    const cached = this.cache.get(key);
13    if (cached !== undefined) {
14      this.cache.delete(key);
15      this.cache.set(key, cached);
16      return cached;
17    }
18    const value = this.db.get(key) ?? 0;
19    this.fill(key, value);
20    return value;
21  }
22 
23  write(key: number, value: number): void {
24    if (this.policy === "write-through") {
25      this.db.set(key, value);
26      this.dbWrites++;
27      this.fill(key, value);
28    } else if (this.policy === "write-around") {
29      this.db.set(key, value);
30      this.dbWrites++;
31      this.cache.delete(key);
32    } else {
33      this.fill(key, value);
34      this.dirty.set(key, value);
35    }
36  }
37 
38  private fill(key: number, value: number): void {
39    this.cache.delete(key);
40    this.cache.set(key, value);
41    if (this.cache.size <= this.capacity) return;
42    const oldest = this.cache.keys().next().value!;
43    this.cache.delete(oldest);
44    if (this.dirty.has(oldest)) {
45      this.db.set(oldest, this.dirty.get(oldest)!);
46      this.dirty.delete(oldest);
47      this.dbWrites++;
48    }
49  }
50 
51  flush(): void {
52    for (const [key, value] of this.dirty) {
53      this.db.set(key, value);
54      this.dbWrites++;
55    }
56    this.dirty.clear();
57  }
58}