系統設計

1type Entry = { key: string; count: number };
2 
3function fnv1a(key: string): number {
4  let h = 0x811c9dc5;
5  for (const byte of new TextEncoder().encode(key)) h = Math.imul(h ^ byte, 0x01000193);
6  return h >>> 0;
7}
8 
9// Murmur3's finalizer: every input bit reaches every output bit.
10function mix(h: number): number {
11  h ^= h >>> 16;
12  h = Math.imul(h, 0x85ebca6b);
13  h ^= h >>> 13;
14  h = Math.imul(h, 0xc2b2ae35);
15  return (h ^ (h >>> 16)) >>> 0;
16}
17 
18class CountMinSketch {
19  counts: number[];
20  constructor(public width: number, public depth: number) {
21    this.counts = new Array(width * depth).fill(0);
22  }
23 
24  // Row i uses column (h1 + i * h2) mod width.
25  cells(key: string): number[] {
26    const h1 = mix(fnv1a(key));
27    const h2 = (mix(h1 ^ 0x9e3779b9) | 1) >>> 0;
28    return Array.from({ length: this.depth }, (_, row) =>
29      row * this.width + ((h1 + Math.imul(row, h2)) >>> 0) % this.width);
30  }
31 
32  add(key: string, count = 1): void {
33    for (const cell of this.cells(key)) this.counts[cell] += count;
34  }
35 
36  estimate(key: string): number {
37    return Math.min(...this.cells(key).map((cell) => this.counts[cell]));
38  }
39 
40  merge(other: CountMinSketch, sign: 1 | -1): void {
41    other.counts.forEach((c, i) => (this.counts[i] += sign * c));
42  }
43}
44 
45// Lower rank: fewer counts, or the same count and a later key.
46const below = (count: number, key: string, than: Entry) =>
47  count < than.count || (count === than.count && key > than.key);
48 
49class TopK {
50  heap: Entry[] = [];                 // min-heap: the weakest of the k at heap[0]
51  where = new Map<string, number>();  // key -> index in heap
52  constructor(public k: number) {}
53 
54  update(key: string, count: number): void {
55    const at = this.where.get(key);
56    if (at !== undefined) {
57      this.heap[at].count = count;
58      this.down(at);
59    } else if (this.heap.length < this.k) {
60      this.heap.push({ key, count });
61      this.where.set(key, this.heap.length - 1);
62      this.up(this.heap.length - 1);
63    } else if (!below(count, key, this.heap[0])) {
64      this.where.delete(this.heap[0].key);
65      this.heap[0] = { key, count };
66      this.where.set(key, 0);
67      this.down(0);
68    }
69  }
70 
71  top(): Entry[] {
72    return this.heap.map((e) => ({ ...e }))
73      .sort((a, b) => b.count - a.count || (a.key < b.key ? -1 : 1));
74  }
75 
76  swap(i: number, j: number): void {
77    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
78    this.where.set(this.heap[i].key, i);
79    this.where.set(this.heap[j].key, j);
80  }
81 
82  up(i: number): void {
83    while (i > 0) {
84      const parent = (i - 1) >> 1;
85      if (!below(this.heap[i].count, this.heap[i].key, this.heap[parent])) break;
86      this.swap(i, parent);
87      i = parent;
88    }
89  }
90 
91  down(i: number): void {
92    for (;;) {
93      let low = i;
94      for (const c of [2 * i + 1, 2 * i + 2]) {
95        if (c < this.heap.length && below(this.heap[c].count, this.heap[c].key, this.heap[low])) low = c;
96      }
97      if (low === i) return;
98      this.swap(i, low);
99      i = low;
100    }
101  }
102}
103 
104// One minute of events: count each in the sketch, keep the heaviest.
105function countMinute(events: string[], width: number, depth: number, k: number) {
106  const sketch = new CountMinSketch(width, depth);
107  const heap = new TopK(k);
108  for (const key of events) {
109    sketch.add(key);
110    heap.update(key, sketch.estimate(key));
111  }
112  return { sketch, heap };
113}
114 
115// Slide the window: add the newest minute, subtract the one that left.
116function slide(window: CountMinSketch, newest: CountMinSketch, oldest?: CountMinSketch): void {
117  window.merge(newest, 1);
118  if (oldest) window.merge(oldest, -1);
119}