阅读中文版本

Build a Heap Metrics Aggregator

A streaming metrics aggregator that maintains a per-percentile sketch on a heap, answering quantile queries in O(1) without storing every sample.

heap-metrics-aggregator/
├── src/sketch.ts
├── src/aggregator.ts
├── src/window.ts
├── tests/sketch.test.ts
└── package.json

sketch.add(value); if (sketch.size > TARGET) sketch.compact();

return sketch.quantile(0.99);

aggregator.insert(label, value); // routes to sketches.get(label)

if (now > bucket.end) rotateBucket(); buckets[bucket].insert(value);

Project overview

A metrics aggregator that stores every sample answers quantile queries exactly, but it grows without bound and the query is O(n log n) to sort. A sketch stores a bounded sample set and answers approximately, with an error that is small enough for a dashboard and a memory that is small enough for a process. The trade-off is accuracy for cost, and for operational metrics the trade is almost always worth it.

The sketch is a sorted set of samples with a compaction rule. Insert adds a sample; when the set exceeds a target size, compaction merges samples that are close, keeping the set small. The compaction is what bounds the memory, because the set never exceeds the target by much, and the merging is what bounds the error, because the merged samples are within a known distance.

The quantile query returns the sample at the requested rank. The 99th percentile is the sample at rank 0.99 times the count, and the sketch returns the sample at that rank in the sorted set. The error is the distance between the returned sample and the true 99th percentile, which is bounded by the compaction rule.

The per-label routing lets the aggregator handle multiple metrics independently. A latency metric with a label for endpoint is a separate sketch per endpoint, so the 99th percentile of one endpoint is not mixed with another. The label is a name plus tag pairs, so the same metric with different tags is a separate sketch.

The value of this project is the bounded error, not the sorting. Sorting samples is trivial; merging them so the quantile error is bounded and the memory is bounded is the part worth learning, because that is what lets a process aggregate a million samples without a million-entry array.

What you will build

The project delivers five capabilities, each driven by a test:

• Streaming quantile sketch
• O(1) quantile query
• Bounded memory
• Per-label aggregation
• Time-window rotation

A sketch per label maintains a sorted sample set with a bounded error. Insert adds a sample and compacts; quantile returns the sample at the requested rank. A time-window rotator keeps sketches per bucket and ages out old buckets. The aggregator holds a map of label to sketch and routes inserts by label.

Architecture and data model

The sketch is a sorted array of samples with a target size and an error bound. Insert adds a sample in sorted order, which is O(n) for the insert but O(1) amortized if the samples are roughly uniform. When the size exceeds the target, compaction finds the pair of adjacent samples with the smallest difference and merges them, removing one. This keeps the size at the target and the error at the merge distance.

The quantile query computes the rank as the quantile times the count, and returns the sample at that rank in the sorted array. The query is O(1) in the sketch size, which is the target size, a constant. The error is the maximum merge distance, which is the error bound, a constant.

The per-label routing is a map from label to sketch. The label is a string, typically a metric name plus tag key-value pairs, and the map holds a sketch per label. Insert routes by label, and a query specifies the label and the quantile. The map grows with the number of labels, which is bounded by the metric cardinality.

The time-window rotation keeps a ring of sketches per time bucket. Each bucket covers a fixed interval, and a tick advances the current bucket. When the current bucket ends, a new bucket starts and the oldest is dropped. The aggregator queries the current bucket for the sliding-window view, or merges buckets for a longer view. The merge is a union of the sample sets, which is approximate but cheap.

The compaction rule is the key to the error bound. A rule that merges the closest pair keeps the maximum merge distance small, which keeps the quantile error small. A rule that merges randomly is simpler but has a larger error. The closest-pair rule is O(n) per compaction, which is acceptable because compaction is infrequent.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A stream of metric samples with labels

The dependencies cover the core needs:

• node:perf_hooks (built-in) — High-resolution timestamps

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

heap-metrics-aggregator/ is organized so each concern is testable in isolation:

heap-metrics-aggregator/
├── src/sketch.ts
├── src/aggregator.ts
├── src/window.ts
├── tests/sketch.test.ts
└── package.json

Phase 1: Insert and compact

Add a sample to the sketch and compact when the sample count exceeds the target, merging close samples.

sketch.add(value); if (sketch.size > TARGET) sketch.compact();

Compaction merges samples within the error bound, keeping the sketch small.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Quantile query

Return the sample at the requested rank, interpolating between samples if needed.

return sketch.quantile(0.99);

The query is O(1) in the sketch size, which is bounded by the error target.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Per-label routing

Route inserts by label to a per-label sketch, so each metric is aggregated independently.

aggregator.insert(label, value); // routes to sketches.get(label)

A label is a name plus tag pairs, so the same metric with different tags is separate.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Time-window rotation

Keep sketches per time bucket and age out old buckets so the aggregator covers a sliding window.

if (now > bucket.end) rotateBucket(); buckets[bucket].insert(value);

Rotation bounds the memory and gives a sliding-window view.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Insert a million samples from a known distribution and assert the 99th percentile is within the error bound; insert with two labels and assert each sketch is independent; advance the clock and assert old buckets are dropped.

The accuracy test inserts a million samples from a known distribution, such as a normal or a uniform, and asserts the 99th percentile from the sketch is within the error bound of the true 99th percentile. The true value is computed from the full sample set, which is kept for the test.

The memory test inserts a million samples and asserts the sketch size is at the target, not a million, proving the compaction bounds the memory. The per-label test inserts with two labels and asserts each sketch has only its own samples, proving the routing is independent.

The time-window test inserts into the current bucket, advances the clock past the bucket end, inserts into the new bucket, and asserts the old bucket is dropped. The merge test merges two sketches and asserts the quantile is approximately the quantile of the union.

The monotonicity test inserts samples in ascending order and asserts the quantile is monotonic, because a non-monotonic quantile would be a bug. The empty-sketch test queries a sketch with no samples and asserts a defined behavior, such as returning null, not throwing.

The compaction test inserts enough to trigger compaction and asserts the sketch size is at the target and the error is within the bound, proving the compaction rule works.

pnpm vitest run

Observability

Track the streaming quantile sketch rate, the metrics resource usage, and the error count as the three primary signals for the heap-metrics-aggregator system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the o(1) quantile query alongside the streaming quantile sketch so a correlation is visible at a glance, because a rising o(1) quantile query with a stable streaming quantile sketch means the system is doing more work per unit, not that it is failing.

Log every insert and compact transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the metrics identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the streaming quantile sketch error rate crossing a threshold, the metrics utilization exceeding a percentage, and the o(1) quantile query latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The heap-metrics-aggregator system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Run one aggregator per process, and expose the quantile queries via a metrics endpoint that dashboards scrape. The endpoint returns the 50th, 90th, and 99th percentiles for each label, which is the common dashboard query. The aggregator is in-process, so the endpoint is a local HTTP handler.

Choose the error target from the dashboard need. A one-percent error is fine for a latency dashboard; a 0.1-percent error is needed for an SLO dashboard. The error target sets the sketch size, which sets the memory, so the trade-off is accuracy for memory.

Set the time window from the retention need. A one-minute window is fine for a live dashboard; a one-hour window is needed for a trend. The window sets the number of buckets, which sets the memory, so the trade-off is retention for memory.

Monitor the sketch sizes and the label count. A growing sketch size means the compaction is not keeping up, which should not happen; a growing label count means the cardinality is high, which is a metric design problem, not an aggregator problem.

Do not use the sketch for exact queries. The sketch is approximate, and the error is bounded but not zero, so a query that needs the exact 99th percentile, such as an SLO breach, should use the full sample set, not the sketch.

Security considerations

Treat every input to the heap-metrics-aggregator system as untrusted, because the streaming quantile sketch path is the one place an external caller controls what the system processes. Validate the input shape before any metrics operation, and reject early with a clear error rather than letting a malformed input propagate into the insert and compact phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:perf_hooks credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured heap-metrics-aggregator fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the streaming quantile sketch endpoint per caller, because an unbounded metrics operation is a resource leak as much as a security problem. A caller that can trigger the quantile query path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the insert and compact logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The heap-metrics-aggregator system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the metrics structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• The sketch is approximate; it is not exact, and the error is bounded but not zero.
• No cross-aggregator merge; two aggregators cannot combine their sketches.
• The time window is fixed; a variable window is out of scope.

The sketch is approximate. The quantile error is bounded by the compaction rule, but it is not zero, so the sketch is wrong for a query that needs exactness. A dashboard that shows approximate percentiles is fine; an SLO calculation that breaches on a specific value is not.

There is no cross-aggregator merge. Two aggregators cannot combine their sketches, because the merge of two sketches is not the sketch of the union. A distributed aggregator that merges across processes needs a mergeable sketch, such as a t-digest, which is a different structure.

The time window is fixed. A one-minute window cannot answer a five-minute query without merging buckets, and the merge is approximate. A variable window that adjusts to the query is a real improvement but out of scope, because the window is a storage decision, not a query decision.