系統設計

1class SampledLru {
2  lastUsed = new Map<number, number>();
3  keys: number[] = [];
4  slot = new Map<number, number>();
5  pool: { key: number; idle: number }[] = [];
6  clock = 0;
7 
8  constructor(private capacity: number, private samples: number,
9              private usePool: boolean, private random: () => number) {}
10 
11  access(key: number): boolean {
12    this.clock++;
13    if (this.lastUsed.has(key)) {
14      this.lastUsed.set(key, this.clock);
15      return true;
16    }
17    if (this.keys.length >= this.capacity) this.remove(this.victim());
18    this.lastUsed.set(key, this.clock);
19    this.slot.set(key, this.keys.length);
20    this.keys.push(key);
21    return false;
22  }
23 
24  victim(): number {
25    const picked: number[] = [];
26    for (let i = 0; i < this.samples; i++) {
27      picked.push(this.keys[Math.floor(this.random() * this.keys.length)]);
28    }
29    if (!this.usePool) {
30      let best = picked[0];
31      for (const key of picked) {
32        if (this.lastUsed.get(key)! < this.lastUsed.get(best)!) best = key;
33      }
34      return best;
35    }
36    for (const key of picked) {
37      if (this.pool.some((e) => e.key === key)) continue;
38      this.pool.push({ key, idle: this.clock - this.lastUsed.get(key)! });
39    }
40    this.pool.sort((a, b) => b.idle - a.idle);
41    this.pool = this.pool.slice(0, 16);
42    while (this.pool.length) {
43      const { key } = this.pool.shift()!;
44      if (this.lastUsed.has(key)) return key;
45    }
46    return picked[0];
47  }
48 
49  remove(key: number): void {
50    const at = this.slot.get(key)!;
51    const last = this.keys.pop()!;
52    if (last !== key) {
53      this.keys[at] = last;
54      this.slot.set(last, at);
55    }
56    this.slot.delete(key);
57    this.lastUsed.delete(key);
58  }
59}
60 
61function crc16(bytes: Uint8Array): number {
62  let crc = 0;
63  for (const byte of bytes) {
64    crc ^= byte << 8;
65    for (let bit = 0; bit < 8; bit++) {
66      crc = crc & 0x8000 ? ((crc << 1) ^ 0x1021) & 0xffff : (crc << 1) & 0xffff;
67    }
68  }
69  return crc;
70}
71 
72function keySlot(key: string): number {
73  const open = key.indexOf("{");
74  const close = open === -1 ? -1 : key.indexOf("}", open + 1);
75  const hashed = close > open + 1 ? key.slice(open + 1, close) : key;
76  return crc16(new TextEncoder().encode(hashed)) % 16384;
77}
78 
79class SortedSet {
80  scores = new Map<string, number>();
81  order: [number, string][] = [];                                // ascending by score, then member
82 
83  position(score: number, member: string): number {
84    let lo = 0, hi = this.order.length;
85    while (lo < hi) {
86      const mid = (lo + hi) >> 1;
87      const [s, m] = this.order[mid];
88      if (s < score || (s === score && m < member)) lo = mid + 1;
89      else hi = mid;
90    }
91    return lo;
92  }
93 
94  add(member: string, score: number): void {
95    const old = this.scores.get(member);
96    if (old !== undefined) this.order.splice(this.position(old, member), 1);
97    this.scores.set(member, score);
98    this.order.splice(this.position(score, member), 0, [score, member]);
99  }
100 
101  incrBy(member: string, by: number): number {
102    const score = (this.scores.get(member) ?? 0) + by;
103    this.add(member, score);
104    return score;
105  }
106 
107  top(n: number): [string, number][] {
108    return this.order.slice(-n).reverse().map(([s, m]) => [m, s]);
109  }
110 
111  rank(member: string): number | null {
112    const score = this.scores.get(member);
113    if (score === undefined) return null;
114    return this.order.length - 1 - this.position(score, member);
115  }
116}
117 
118class AppendOnlyFile {
119  pending: string[] = [];   // written, not yet fsynced
120  onDisk: string[] = [];
121  lastSync = 0;
122 
123  constructor(private policy: "always" | "everysec") {}
124 
125  append(command: string, nowMs: number): void {
126    this.pending.push(command);
127    if (this.policy === "always") this.fsync(nowMs);
128  }
129 
130  tick(nowMs: number): void {
131    if (this.policy === "everysec" && nowMs - this.lastSync >= 1000) this.fsync(nowMs);
132  }
133 
134  fsync(nowMs: number): void {
135    this.onDisk.push(...this.pending);
136    this.pending = [];
137    this.lastSync = nowMs;
138  }
139}