Improve Summary quantiles with DataSketches

[DCjanus]

Summary.observe() can become expensive when quantiles are recorded at high frequency. This can make the current quantile path visible on hot request paths.

We saw this in ZooKeeper's Prometheus metrics path. In an internal ZooKeeper 3.9.2 fork, a version inspired by ZooKeeper's unmerged DataSketches Summary PR improved peak throughput by about 2x.

DataSketches KLL may be a useful way to improve this in client_java. The goal would be to reduce the cost of the observe path while keeping the external Summary behavior as close as practical.

This would not have to replace the current CKMS-based Summary immediately. DataSketches KLL has a different accuracy model, memory cost, and quantile visibility behavior, so an explicit opt-in path may be a better first step.

Initial questions:

• Does using DataSketches for Summary quantiles sound like a direction worth exploring?
• If so, would a separate opt-in artifact be a reasonable way to introduce it?
• What behavior details and benchmark data would be most useful before going further?

[DCjanus]

Here are some rough notes from early experiments with a DataSketches-backed Summary.

I am not an expert in quantile sketch algorithms, so this is not a final proposal. I hope it can still be useful as a starting point.

The prototype I tested keeps the Prometheus Summary shape, but changes how quantile values are stored internally:

• Observations are first written into a small set of write-side KLL sketches.
• On collect, those write-side sketches are merged into a sliding time window.
• The time window uses multiple age buckets, similar to the current Summary window.
• The exported metric would still look like a Summary.

The main knobs in this prototype are:

• k: KLL sketch size. Higher k lowers rank error and increases memory.
• stripes: number of write-side sketches per label set. More stripes may reduce write contention and increase memory / merge work.
• age buckets: number of sketches used for the sliding time window.

Benchmark run: https://github.com/DCjanus/client_java/actions/runs/25210855857

The benchmark used the same mixed workload for the current CKMS Summary and the DataSketches prototype. The table omits JMH error and measured rank error. The rank error column is the configured KLL normalized rank error for each k. The memory column is a rough idle lower bound per label set before Java object headers and other metric metadata.

K	Stripes	Age buckets	KLL normalized rank error	Rough idle memory / label set	DataSketches throughput	vs CKMS in same runner
64	32	60	4.03%	520 B * 93 ~= 47 KiB	31.49M ops/s	16.9x
64	64	60	4.03%	520 B * 125 ~= 64 KiB	30.15M ops/s	16.1x
64	128	60	4.03%	520 B * 189 ~= 96 KiB	28.70M ops/s	11.9x
128	32	60	2.05%	1 KiB * 93 = 93 KiB	31.60M ops/s	17.2x
128	64	60	2.05%	1 KiB * 125 = 125 KiB	35.53M ops/s	14.5x
128	128	60	2.05%	1 KiB * 189 = 189 KiB	27.93M ops/s	14.9x
256	32	60	1.05%	2 KiB * 93 = 186 KiB	24.94M ops/s	13.4x
256	64	60	1.05%	2 KiB * 125 = 250 KiB	19.56M ops/s	14.9x
256	128	60	1.05%	2 KiB * 189 = 378 KiB	29.23M ops/s	15.7x
512	32	60	0.53%	4 KiB * 93 = 372 KiB	28.33M ops/s	15.1x
512	64	60	0.53%	4 KiB * 125 = 500 KiB	25.13M ops/s	13.5x
512	128	60	0.53%	4 KiB * 189 = 756 KiB	23.82M ops/s	13.1x

The bold row is the possible default I would start with. It keeps k close to the current default p50 / p90 Summary error order, uses bounded write-side state, keeps the current 5-minute window, and gives roughly 5s quantile visibility.

This is mostly a judgment call based on the production environments I usually work with: observe-path cost matters a lot, a few seconds of quantile visibility delay is acceptable, and per-label-set memory growth needs to stay bounded.

This may not match other workloads or operating constraints. In particular, k, stripe count, and bucket count are the parts I would expect to tune further.

[DCjanus]

One implementation detail I am still unsure about is how to structure the write side.

In our internal ZooKeeper fork, I used a per-thread local KLL sketch design. Each thread had its own local sketch, and a background task periodically drained those sketches into the global time-window buckets. This worked well for our ZooKeeper use case.

After looking again at ZooKeeper 3.9.2, I think that trade-off was easier to accept there because the relevant observe path is usually bounded by fixed-size worker pools:

• The Prometheus metrics provider reports Summary observations through a fixed-size worker pool by default.
• NIO request handling uses fixed selector and worker thread counts.
• CommitProcessor also uses a bounded worker pool.

I am less sure this is a good fit for client_java as a general-purpose library. Applications may call Summary.observe() from request executors, short-lived threads, executor churn, or virtual threads. A per-thread local sketch design keeps the hot path cheap, but it can make memory usage and drain/merge cost grow with the historical number of threads that touched a metric.

The striped prototype avoids that unbounded per-thread state by using a fixed number of write-side sketches per label set. That gives a clearer upper bound, but it is also not obviously the best answer. It still adds per-label-set memory, and the right trade-off between write contention, memory, collect cost, and API complexity is not obvious to me.

I am sharing this mainly to explain the path I tried and where I am uncertain. There may be a better design than either per-thread local sketches or fixed stripes.

[ADITYA-CODE-SOURCE]

Hi @DCjanus, I’d like to work on this.

The DataSketches KLL approach looks promising, especially as an opt-in path for improving Summary.observe() performance while keeping external Summary behavior as close as practical.

Before I start, I wanted to confirm the preferred direction:

1. Should this be introduced as a separate opt-in module/artifact?
2. Do you currently prefer the striped write-side design over per-thread local sketches?
3. Would you like the first PR to focus on API/design or on a benchmarked prototype?