Skip to content

fix: prevent Summary quantiles from collapsing to the minimum observation - #2316

Closed
manduinca wants to merge 1 commit into
prometheus:mainfrom
manduinca:fix/2292-ckms-boundary-epsilon
Closed

fix: prevent Summary quantiles from collapsing to the minimum observation#2316
manduinca wants to merge 1 commit into
prometheus:mainfrom
manduinca:fix/2292-ckms-boundary-epsilon

Conversation

@manduinca

@manduinca manduinca commented Jul 19, 2026

Copy link
Copy Markdown

Fixes #2292

When a targeted quantile has 2*epsilon >= 1 - quantile, all reported quantiles could collapse to the minimum observation. The query scan stopped too early: a freshly inserted low-rank sample can carry a delta on the order of n, so the running rank + g + delta exceeded the target far sooner than it should and returned a value near the minimum.

The fix has two parts, matching the diagnosis in the issue. compress() now keeps a merged sample from spanning a quantile's target rank, and the query uses the minimum of the error function over a sample's rank interval [lo, hi] rather than at a single point. To support that I split the single-argument f(r) into f(lo, hi) (the plain error function is f(r, r)), which is numerically identical for the existing call sites.

Added a regression test that reproduces the collapse and asserts distinct quantiles. CKMSQuantilesTest passes (18 tests).

@manduinca
fix: prevent Summary quantiles from collapsing to the minimum observa…
eace47f 
…tion

CKMSQuantiles returned the minimum observation for every targeted quantile
whenever 2*epsilon >= 1-quantile (e.g. quantile(0.9, 0.05) or
quantile(0.99, 0.005)). At the boundary the error function permits a sample's
uncertainty (delta) to reach the order of n at low ranks, which broke both the
query and compression:

- get() stopped at the first sample whose maximum rank exceeded
  desiredRank + f(desiredRank)/2 and returned the preceding sample. A freshly
  inserted low-rank sample (delta = f(r) - 1) then made the scan stop almost
  immediately, returning a value near the minimum. get() now returns the sample
  whose possible-rank interval is centered closest to the desired rank.
- compress() bounded merges by the error function at the left edge only, where
  f is huge for low ranks, so it merged away all resolution between the median
  and the maximum. Merges are now bounded by the error function over the whole
  rank interval the merged sample would span, via a new f(lo, hi) overload
  (f(r) delegates to f(r, r), so single-rank behavior is unchanged).

Adds regression tests for the boundary configuration.

Fixes prometheus#2292

Signed-off-by: Jean Pierre Mandujano G. <jeanpierre.mandujano@gmail.com>
zeitlinger
zeitlinger requested changes Jul 22, 2026
View reviewed changes

@zeitlinger zeitlinger left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the focused reproducer. I found a correctness issue in the new rank-selection heuristic, plus a couple of changes that would make the fix easier to review:

  1. get() currently chooses the sample whose possible-rank interval has the nearest center. That does not preserve the advertised rank bound. With values 1..10_000 shuffled using new Random(2), a single (q=0.99, epsilon=0.005) configuration returns 9784; the allowed range under the test's 2 * epsilon bound is [9800, 10000]. The sample centered nearest to rank 9900 is therefore not a sufficient selection criterion. Please rework the selection against the CKMS error bounds and add this smaller deterministic regression case.

  2. Please rename f. It is now overloaded for both a point rank and an interval, but the name gives no indication of either the mathematical meaning or the interval semantics. Descriptive names such as errorBoundAtRank and minErrorBoundInRange would make the compression logic much easier to audit. Please update the associated Javadocs and test references too.

  3. The new tests only use n=100_000, and their broad 2 * epsilon assertions do not verify the comment's claim that the quantiles remain distinct or exercise the 2 * epsilon > 1 - quantile case. Please add direct rank-bound coverage for the failing smaller case and a strict-above-boundary case.

The two new boundary tests pass, but the additional deterministic case above fails on the current head.

This was referenced Aug 19, 2026
Closed
Merged
olegkovalenko added a commit to olegkovalenko/client_java that referenced this pull request Aug 19, 2026
@olegkovalenko
fix: Summary quantiles collapsing for targeted quantiles with 2*epsil…
2e86dac 
…on >= 1-quantile

Fixes prometheus#2292.

CKMSQuantiles returned values from far below the requested quantile for
quantile configurations such as (0.9, 0.05) or (0.99, 0.005) - often the
minimum of all observations, regardless of the input data.

Interacting root causes, all stemming from the error function f() being
of order n-r below a target quantile when 2*epsilon >= 1-quantile:

1. compress(): a single sample was allowed to span all ranks from r to
   n, so compress() merged away the samples that hold the information
   needed to answer the quantile query. With quantiles
   {(0.9, 0.05), (0.99, 0.005)} the sample list collapsed to 3 samples.

2. insertBefore(): freshly inserted samples get delta = f(r) - 1, so
   below a target their possible-rank intervals are centered near rank
   n regardless of the sample's actual position, making them
   indistinguishable from genuine samples near the target.

3. get(): the scan stopped at the first sample with
   r + g + delta > desiredRank + f(desiredRank)/2 and returned the value
   of the sample before it; a single wide sample (see 2., and get()
   flushes the buffer right before scanning, so such samples are always
   present) made the scan stop far before the target rank.

The fix bounds sample widths by maxWidthNotCrossingTargets(r) in
addition to f(r) at both places where widths are created - merging in
compress() and delta assignment in insertBefore() - so that every
target quantile keeps enough resolution around its accuracy window
[quantile*n - epsilon*n, quantile*n + epsilon*n]. The bound is anchored
at the window's start with a floor of 2*epsilon*n so that it does not
degenerate for targets with quantile + epsilon >= 1 (window end == n),
e.g. (0.99, 0.01) or (0.95, 0.05). get() returns the value of the
sample whose possible rank interval is centered closest to the desired
rank, which cannot be derailed by a single wide sample.

Verified against exact percentiles on 3720 test cases (31 quantiles
across 13 configurations x 6 distributions x 2 sizes x 10 seeds):
worst rank error 1.75 * epsilon, no case above 2 * epsilon. Before the
fix the worst rank error was 330 * epsilon.

Also includes the deterministic regression case from the review of
PR prometheus#2316 (values 1..10,000 shuffled with seed 2, single quantile
(0.99, 0.005)), which this fix passes, plus regression tests for the
quantile + epsilon >= 1 family and for descending input order.

Signed-off-by: Oleg Kovalenko <okovalenko@evolution.com>
@olegkovalenko

olegkovalenko commented Aug 19, 2026

Copy link
Copy Markdown
Contributor

Heads-up: I've opened #2396 for the same issue (#2292). It shares the two-part diagnosis from this PR — the compress() merge bound and the early-stopping scan in get() — but bounds sample widths differently (window-anchored cap, applied at both merge and insert time) and keeps f() unchanged.

The deterministic case from the review here (values 1..10,000, Random(2), single (0.99, 0.005)) is included #2396 as a regression test and passes (returns 9940, within [9800, 10000]), along with the strict-above-boundary coverage the review asked for. Details and the comparison harness are linked in the PR description. Happy to have either PR land — flagging it mainly so the two efforts don't diverge silently.

zeitlinger pushed a commit that referenced this pull request Aug 25, 2026
@olegkovalenko
fix: Summary quantiles collapsing for targeted quantiles with 2*epsil…
9c7479f 
…on >= 1-quantile (#2396)

Fixes #2292. Alternative to #2316, addressing the issues raised in its
review.

## Problem

For targeted quantile configurations with `2*epsilon >= 1 - quantile` —
e.g. `(0.9, 0.05)` or `(0.99, 0.005)`, both taken from real-world
configurations — `Summary` reported values from far below the requested
quantile, often the minimum of all observations, regardless of the input
data.

The root causes all stem from the same property: below a target
quantile, the CKMS error function `f(r) = 2*epsilon*(n-r)/(1-q)` is of
order `n-r` when `2*epsilon >= 1-q`. Three things break:

1. **`compress()` destroys the sketch.** A single sample may span all
ranks from `r` to `n`, so `compress()` merges away the samples that hold
the information needed to answer the quantile query. With `{(0.9, 0.05),
(0.99, 0.005)}` the sample list collapsed to 3 samples no matter how
many values were inserted.

2. **`insertBefore()` assigns misleading deltas.** Freshly inserted
samples get `delta = f(r) - 1`, so below a target their possible-rank
intervals are centered near rank `n` regardless of the sample's actual
position — indistinguishable from genuine samples near the target.

3. **`get()` stops too early.** The scan stopped at the first sample
with `r + g + delta > desiredRank + f(desiredRank)/2` and returned the
value of the sample before it; a single wide fresh sample (always
present, since `get()` flushes the buffer right before scanning) tripped
it far before the target rank.

## Fix

1. Sample widths are additionally bounded by
`maxWidthNotCrossingTargets(r)` at **both places where widths are
created** — merging in `compress()` and delta assignment in
`insertBefore()`, via a shared `effectiveMaxWidth(r)` — so every target
quantile keeps enough resolution around its accuracy window `[q*n -
eps*n, q*n + eps*n]`: below a window a sample may extend at most
`max(windowStart - r, 2*eps*n)` — it can intrude into the window but
never reach the window's end — and any sample overlapping a window has
width at most the window's size `2*eps*n`. So no single sample can span
a whole window, and the center of a sample's possible-rank interval is
within `eps*n` of any rank the sample covers inside the window. The
bound is anchored at the window's *start* so it does not degenerate for
targets with `quantile + epsilon >= 1` (e.g. `(0.99, 0.01)`, `(0.95,
0.05)`), where the window's end is rank `n` and an end-anchored bound
would be no constraint at all. For configurations with `2*epsilon <
1-quantile` the bound is larger than `f()` near the target, so behavior
there is mostly unchanged.

2. `get()` returns the value of the sample that minimizes the
**worst-case rank error**: the true rank of a sample is somewhere in
`[r+g, r+g+delta]`, so picking it the rank error can be as large as
`max(|r+g - desiredRank|, |r+g+delta - desiredRank|)` — the distance of
the interval's center from the desired rank plus half the interval's
width. Minimizing this cannot be derailed by a single wide sample
(unlike the old stop rule), and penalizes wide samples whose interval
center happens to fall near the desired rank (which an earlier revision
of this PR, selecting by nearest center alone, did not — caught in
review by a deterministic counterexample, now a regression test).

## Relation to #2316 and its review

#2316 diagnoses the compress and get parts but bounds `compress()`
differently (minimum of the error function over the merged interval) and
leaves insert-time deltas unbounded. The review found a deterministic
counterexample: single quantile `(0.99, 0.005)`, values 1..10,000
shuffled with `Random(2)` — #2316 returns 9784, outside the allowed
`[9800, 10000]`.

This fix passes that case (returns 9940), and it is included as a
regression test (`testSingleTargetedQuantileSmallN`).

## Verification

The documented guarantee is `q ± epsilon`. Sweeping values `1..n` (true
rank = value) across 10 configurations × sizes {100, 257, 1k, 10k, 100k}
× 100 shuffled seeds plus ascending and descending order, with pass =
rank error `<= eps*n + 1 rank` (the `+1` absorbs integer-rank
quantization where `eps*n < 1`):

| Configuration | cases | `main` > 1ε | this PR > 1ε |
|---|---|---|---|
| `(0.5, 0.025)` (review counterexample config) | 510 | 9 | 2 |
| `(0.75, 0.02)` | 510 | 9 | 2 |
| `(0.99, 0.005)` | 510 | 299 | 2 |
| `(0.9, 0.05)` + `(0.99, 0.005)` | 1020 | 706 | 1 |
| `(0.5, 0.05)` + `(0.9, 0.01)` + `(0.99, 0.001)` | 1530 | 39 | 3 |
| `(0.9, 0.06)` (strictly above boundary) | 510 | 407 | 1 |
| `(0.99, 0.01)` (window end = n) | 510 | 404 | 0 |
| `(0.95, 0.05)` (window end = n) | 510 | 404 | 0 |
| `(0.5, 0.025)` + `(0.9, 0.05)` + `(0.99, 0.005)` | 1530 | 288 | 3 |
| `(0.5, 0.01)` + `(0.75, 0.01)` + `(0.95, 0.005)` + `(0.99, 0.002)` |
2040 | 22 | 1 |

Every remaining `> 1ε` case for this PR is **descending input order**
(worst 1.75ε, at `(0.99, 0.005)`, n=100k); on shuffled and ascending
input there are **no violations of the 1ε bound**. `main` fails every
one of those descending cases too — by up to 198ε on the collapsing
configurations, and by 1.1–1.25ε even on well-behaved ones — and
additionally fails dozens of *shuffled* cases (e.g. `(0.5, 0.025)` at
n=10,000 with seeds 47, 52, 77), because deltas are fixed at insert time
while `n` grows, so the paper's invariant erodes over the sketch's
lifetime. In other words: this PR meets 1ε on every case `main` meets
it, plus almost all the cases `main` fails. Closing the remaining
descending-input gap would require maintaining the width invariant at
query time, which is out of scope here; a test pins it at 2ε.

Additionally verified against exact percentiles on the evaluation grid
of 2,900 cases (29 quantiles across 11 configurations × 5 distributions
— uniform, heavy-tail from a production latency CDF, exponential,
lognormal, gaussian — × 2 sizes × 10 seeds): worst rank error `1.60 *
epsilon`, no case above `2 * epsilon`. Before the fix the worst rank
error was `~330 * epsilon`. The evaluation harness (including the
instrumented query-rule variants compared before settling on this fix —
the shipped rule is mode 6, `minimax`) is available at
https://gist.github.com/olegkovalenko/83c58835a1357d3450e6538f89e2cda7.

Memory impact of the width bound is a handful of extra samples on the
affected configurations (e.g. `(0.99, 0.005)`: 3–4 → 6–11 samples after
1M inserts); well-behaved configurations such as `(0.5, 0.05)(0.9,
0.01)(0.99, 0.001)` are unchanged (37–40 samples).

## Tests

- `testTargetedQuantilesDoNotCollapse` — the original reproducer from
#2292
- `testSingleTargetedQuantileDoesNotCollapse` — single targeted quantile
at the boundary
- `testTargetedQuantilesWithMedian` — collapse still occurred with a
well-behaved quantile added
- `testSingleTargetedQuantileSmallN` — the deterministic small-n case
from the #2316 review
- `testMedianSmallN` — the deterministic counterexample from this PR's
review: `(0.5, 0.025)`, values 1..257 shuffled with seed 5
(nearest-center selection returned 121, outside [122, 135]; the
worst-case-error selection returns 132)
- `testTargetedQuantileWindowReachingMaximum` — the degenerate `quantile
+ epsilon >= 1` family
- `testTargetedQuantilesDescendingInput` — descending input order, the
worst case for these configurations
- `testTargetedQuantilesAscendingInput` — ascending input order, the
counterpart of the descending test
- `testTargetedQuantilesDescendingInputLargeN` — pins the known
remaining descending-input gap at 2ε (with a comment explaining why the
1ε bound erodes there and that `main` fails the same cases by far more)

`validateResults` now asserts the documented `q ± epsilon` rank bound
(floor/ceil, since ranks are integers) — it previously allowed `q ±
2*epsilon` — and all tests above except
`testTargetedQuantilesDescendingInputLargeN` use it at 1ε, on values
`1..n` inserted in the respective order (value = true rank). All
existing `CKMSQuantilesTest` cases pass at the tightened bound (25
tests), as does the full `prometheus-metrics-core` suite (165 tests).

---------

Signed-off-by: Oleg Kovalenko <okovalenko@evolution.com>
@zeitlinger

zeitlinger commented Aug 25, 2026

Copy link
Copy Markdown
Member

closed in favor of #2396

@zeitlinger zeitlinger closed this Aug 25, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@zeitlinger zeitlinger zeitlinger requested changes
@fstab fstab Awaiting requested review from fstab fstab is a code owner
@dhoard dhoard Awaiting requested review from dhoard dhoard is a code owner
@jaydeluca jaydeluca Awaiting requested review from jaydeluca jaydeluca is a code owner

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Summary quantiles collapse to the minimum observation when 2·epsilon ≥ 1−quantile

3 participants

@manduinca @olegkovalenko @zeitlinger