系統設計

1type Entry = { state: "in-progress" | "done"; response?: string; expiresAt: number };
2 
3class IdempotencyStore {
4  private entries = new Map<string, Entry>();
5  private expiry: { key: string; entry: Entry }[] = []; // min-heap by expiresAt
6 
7  constructor(private ttlSec: number) {}
8 
9  get size(): number { return this.entries.size; }
10 
11  private put(key: string, entry: Entry): void {
12    this.entries.set(key, entry);
13    this.expiry.push({ key, entry });
14    for (let i = this.expiry.length - 1; i > 0;) {
15      const parent = (i - 1) >> 1;
16      if (this.expiry[parent].entry.expiresAt <= entry.expiresAt) break;
17      [this.expiry[i], this.expiry[parent]] = [this.expiry[parent], this.expiry[i]];
18      i = parent;
19    }
20  }
21 
22  // Run on arrivals and from a timer during idle periods, not only on key reuse.
23  expire(now: number): void {
24    while (this.expiry.length && this.expiry[0].entry.expiresAt <= now) {
25      const first = this.expiry[0], last = this.expiry.pop()!;
26      if (this.expiry.length) {
27        this.expiry[0] = last;
28        for (let i = 0;;) {
29          let child = 2 * i + 1;
30          if (child >= this.expiry.length) break;
31          if (child + 1 < this.expiry.length && this.expiry[child + 1].entry.expiresAt < this.expiry[child].entry.expiresAt) child++;
32          if (this.expiry[i].entry.expiresAt <= this.expiry[child].entry.expiresAt) break;
33          [this.expiry[i], this.expiry[child]] = [this.expiry[child], this.expiry[i]];
34          i = child;
35        }
36      }
37      if (this.entries.get(first.key) === first.entry) this.entries.delete(first.key);
38    }
39  }
40 
41  // In production this is one atomic insert-if-absent
42  // (Redis SET NX, or INSERT ... ON CONFLICT DO NOTHING).
43  begin(key: string, now: number): { kind: "new" | "busy" | "replay"; response?: string } {
44    this.expire(now);
45    const entry = this.entries.get(key);
46    if (entry && entry.expiresAt <= now) this.entries.delete(key);
47    else if (entry?.state === "done") return { kind: "replay", response: entry.response };
48    else if (entry) return { kind: "busy" };
49    this.put(key, { state: "in-progress", expiresAt: now + this.ttlSec });
50    return { kind: "new" };
51  }
52 
53  finish(key: string, response: string, now: number): void {
54    this.expire(now);
55    this.put(key, { state: "done", response, expiresAt: now + this.ttlSec });
56  }
57 
58  release(key: string): void {
59    this.entries.delete(key);
60  }
61}
62 
63function handlePayment(store: IdempotencyStore, key: string, now: number, charge: () => string) {
64  const claim = store.begin(key, now);
65  if (claim.kind === "replay") return { status: 200, body: claim.response };
66  if (claim.kind === "busy") return { status: 409, body: "in progress" };
67  try {
68    const body = charge();
69    store.finish(key, body, now);
70    return { status: 200, body };
71  } catch (error) {
72    store.release(key);
73    throw error;
74  }
75}
76 
77// One key per payment, reused by every retry of that payment.
78function pay(send: (key: string) => number, newKey: () => string, maxAttempts: number): boolean {
79  const key = newKey();
80  for (let attempt = 0; attempt < maxAttempts; attempt++) {
81    if (send(key) === 200) return true;
82  }
83  return false;
84}