系統設計

1type Span = { traceId: string; spanId: number; parentId: number | null; name: string; start: number; end: number };
2 
3class Tracer {
4  spans: Span[] = [];
5  logs: string[] = [];
6  private nextId = 1;
7  constructor(private traceId: string) {}
8 
9  start(name: string, parent: Span | null, now: number): Span {
10    const span = { traceId: this.traceId, spanId: this.nextId++, parentId: parent ? parent.spanId : null,
11                   name, start: now, end: now };
12    this.spans.push(span);
13    return span;
14  }
15 
16  finish(span: Span, now: number): void {
17    span.end = now;
18  }
19 
20  // One JSON object per line, carrying the trace ID so logs join up with traces.
21  log(span: Span, level: string, msg: string, now: number): void {
22    this.logs.push(JSON.stringify({ t: now, trace_id: span.traceId, span_id: span.spanId, level, msg }));
23  }
24}
25 
26// Walk back from the end: the child that finished last before the cursor
27// is what the parent was waiting on; before it started, the next one was.
28function criticalPath(spans: Span[]): string[] {
29  const children = new Map<number, Span[]>();
30  for (const span of spans) {
31    if (span.parentId === null) continue;
32    if (!children.has(span.parentId)) children.set(span.parentId, []);
33    children.get(span.parentId)!.push(span);
34  }
35  const path: string[] = [];
36  const walk = (span: Span) => {
37    path.push(span.name);
38    let cursor = span.end;
39    const kids = (children.get(span.spanId) ?? []).slice().sort((a, b) => b.end - a.end);
40    for (const child of kids) {
41      if (child.end <= cursor) {
42        walk(child);
43        cursor = child.start;
44      }
45    }
46  };
47  walk(spans.find((span) => span.parentId === null)!);
48  return path;
49}
50 
51// Count a value into the first bucket whose upper bound holds it; the
52// last count is for everything above the largest bound.
53function observe(bounds: number[], counts: number[], value: number): void {
54  let i = 0;
55  while (i < bounds.length && value > bounds[i]) i++;
56  counts[i]++;
57}
58 
59// The q-quantile from bucket counts alone, interpolating inside the bucket.
60function histogramQuantile(bounds: number[], counts: number[], q: number): number {
61  const rank = q * counts.reduce((a, b) => a + b, 0);
62  let cumulative = 0;
63  for (let i = 0; i < counts.length; i++) {
64    if (counts[i] > 0 && cumulative + counts[i] >= rank) {
65      if (i === bounds.length) return bounds[bounds.length - 1];
66      const lower = i === 0 ? 0 : bounds[i - 1];
67      return lower + ((bounds[i] - lower) * (rank - cumulative)) / counts[i];
68    }
69    cumulative += counts[i];
70  }
71  return bounds[bounds.length - 1];
72}
73 
74// An incident of `minutes` at a steady error rate, against an SLO over a window.
75function errorBudget(slo: number, windowDays: number, errorRate: number, minutes: number) {
76  const budget = 1 - slo;
77  const windowMinutes = windowDays * 24 * 60;
78  const consumed = (errorRate * minutes) / (budget * windowMinutes);
79  const burnRate = errorRate / budget;
80  const over = (window: number) => (burnRate * Math.min(minutes, window)) / window;
81  const page = over(60) >= 14.4 && over(5) >= 14.4;
82  const ticket = over(360) >= 6 && over(30) >= 6;
83  return { consumed, burnRate, page, ticket };
84}