| 1 | /** |
| 2 | * Durations kept as counts in fixed buckets, so a minute's latency (or |
| 3 | * CPU) is a short list of numbers that adds to any other minute's, and |
| 4 | * percentiles over any period come from the sum. Each bucket is read back |
| 5 | * as a point between its bounds, which keeps a percentile within the |
| 6 | * bucket's width of the true one: a few percent here, as bounds go up in |
| 7 | * steps of about 1.5×. |
| 8 | */ |
| 9 | import type { Percentiles } from "@g1t/contracts/telemetry"; |
| 10 | |
| 11 | /** Upper bounds, in milliseconds; the last bucket holds everything above the last bound. */ |
| 12 | export const BOUNDS_MS = [1, 2, 3, 5, 7, 10, 15, 20, 30, 50, 75, 100, 150, 200, 300, 500, 750, 1000, 1500, 2000, 3000, 5000, 7500, 10000, 15000, 30000, 60000]; |
| 13 | |
| 14 | export const BUCKETS = BOUNDS_MS.length + 1; |
| 15 | |
| 16 | export function bucketOf(ms: number): number { |
| 17 | let i = 0; |
| 18 | while (i < BOUNDS_MS.length && ms > BOUNDS_MS[i]) i++; |
| 19 | return i; |
| 20 | } |
| 21 | |
| 22 | export function emptyHistogram(): number[] { |
| 23 | return new Array(BUCKETS).fill(0); |
| 24 | } |
| 25 | |
| 26 | export function addInto(into: number[], from: readonly number[]): number[] { |
| 27 | for (let i = 0; i < BUCKETS; i++) into[i] = (into[i] ?? 0) + (from[i] ?? 0); |
| 28 | return into; |
| 29 | } |
| 30 | |
| 31 | /** A histogram as stored: counts joined by commas, trailing zeros dropped. */ |
| 32 | export function encode(counts: readonly number[]): string { |
| 33 | let end = counts.length; |
| 34 | while (end > 0 && !counts[end - 1]) end--; |
| 35 | return counts.slice(0, end).join(","); |
| 36 | } |
| 37 | |
| 38 | export function decode(text: string | null | undefined): number[] { |
| 39 | const out = emptyHistogram(); |
| 40 | if (!text) return out; |
| 41 | text.split(",").forEach((n, i) => { |
| 42 | if (i < BUCKETS) out[i] = Number(n) || 0; |
| 43 | }); |
| 44 | return out; |
| 45 | } |
| 46 | |
| 47 | /** The value at quantile `q` (0–1), interpolated within its bucket. */ |
| 48 | export function quantile(counts: readonly number[], q: number): number | null { |
| 49 | const total = counts.reduce((a, b) => a + b, 0); |
| 50 | if (!total) return null; |
| 51 | const rank = q * total; |
| 52 | let seen = 0; |
| 53 | for (let i = 0; i < BUCKETS; i++) { |
| 54 | const n = counts[i] ?? 0; |
| 55 | if (!n) continue; |
| 56 | if (seen + n >= rank) { |
| 57 | const low = i === 0 ? 0 : BOUNDS_MS[i - 1]; |
| 58 | const high = i < BOUNDS_MS.length ? BOUNDS_MS[i] : BOUNDS_MS[BOUNDS_MS.length - 1] * 2; |
| 59 | const within = n === 0 ? 0 : (rank - seen) / n; |
| 60 | return Math.round((low + (high - low) * within) * 100) / 100; |
| 61 | } |
| 62 | seen += n; |
| 63 | } |
| 64 | return BOUNDS_MS[BOUNDS_MS.length - 1]; |
| 65 | } |
| 66 | |
| 67 | export function percentiles(counts: readonly number[]): Percentiles { |
| 68 | return { p50: quantile(counts, 0.5), p75: quantile(counts, 0.75), p95: quantile(counts, 0.95), p99: quantile(counts, 0.99) }; |
| 69 | } |