系統設計

1const CACHE_MS = 1;
2 
3// One hot key. fillAt is when the reload in flight, if any, completes.
4class HotKeyCache {
5  expiresAt: number;
6  fillAt = Infinity;
7  dbCalls = 0;
8 
9  constructor(public mode: string, public ttl: number, public loadMs: number, now = 0) {
10    this.expiresAt = now + ttl;
11  }
12 
13  settle(now: number): void {
14    if (this.fillAt <= now) {
15      this.expiresAt = this.fillAt + this.ttl;
16      this.fillAt = Infinity;
17    }
18  }
19 
20  load(now: number): void {
21    this.dbCalls++;
22    this.fillAt = Math.min(this.fillAt, now + this.loadMs);
23  }
24 
25  // random is a draw in [0, 1), used only by early refresh. Returns the latency.
26  get(now: number, random: number): number {
27    this.settle(now);
28    const fresh = now < this.expiresAt;
29    if (this.mode === "early" && fresh && this.fillAt === Infinity) {
30      // XFetch: refresh early with a probability that rises near expiry.
31      if (now - this.loadMs * Math.log(1 - random) >= this.expiresAt) this.load(now);
32      return CACHE_MS;
33    }
34    if (fresh) return CACHE_MS;
35    if (this.mode === "plain") {
36      this.load(now);
37      return this.loadMs;
38    }
39    if (this.mode === "stale") {
40      if (this.fillAt === Infinity) this.load(now);
41      return CACHE_MS;
42    }
43    if (this.fillAt === Infinity) {
44      this.load(now);
45      return this.loadMs;
46    }
47    return this.fillAt - now + CACHE_MS;
48  }
49}
50 
51// Stands between a lookup for a key the database lacks and the database.
52class PenetrationGuard {
53  negative = new Map<string, number>();
54 
55  constructor(public fix: string, public mightExist: (key: string) => boolean, public negativeTtl: number) {}
56 
57  lookupMissing(key: string, now: number): string {
58    if (this.fix === "bloom" && !this.mightExist(key)) return "rejected";
59    if (this.fix === "negative") {
60      const until = this.negative.get(key);
61      if (until !== undefined && now < until) return "negative-hit";
62      this.negative.set(key, now + this.negativeTtl);
63    }
64    return "db";
65  }
66}
67 
68// TTL with +/- jitter, so keys cached together do not expire together.
69function jitteredTtl(base: number, jitter: number, random: number): number {
70  return Math.round(base * (1 + jitter * (2 * random - 1)));
71}
72 
73// An app server's own copy of a hot key: at most one shard call per TTL.
74class LocalCache {
75  expiresAt = -Infinity;
76  shardCalls = 0;
77 
78  constructor(public ttl: number) {}
79 
80  get(now: number): string {
81    if (now < this.expiresAt) return "local";
82    this.shardCalls++;
83    this.expiresAt = now + this.ttl;
84    return "shard";
85  }
86}