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

[olegkovalenko]

Version

io.prometheus:prometheus-metrics-core:1.8.0 (the affected code in CKMSQuantiles is
unchanged since at least 1.3.x and is still present on main).

Reproducer

import io.prometheus.metrics.core.metrics.Summary;
import io.prometheus.metrics.model.registry.PrometheusRegistry;
import io.prometheus.metrics.model.snapshots.Quantile;
import io.prometheus.metrics.model.snapshots.SummarySnapshot;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SummaryQuantileBugRepro {

  public static void main(String[] args) {
    Summary summary =
        Summary.builder()
            .name("request_latency")
            .help("reproducer")
            .quantile(0.9, 0.05)
            .quantile(0.99, 0.005)
            .register(new PrometheusRegistry());

    // observe the values 1..100_000 shuffled, so the true p90 is 90_000 and p99 is 99_000
    List<Integer> values = new ArrayList<>();
    for (int i = 1; i <= 100_000; i++) {
      values.add(i);
    }
    Collections.shuffle(values, new Random(42));
    for (int v : values) {
      summary.observe(v);
    }

    SummarySnapshot.SummaryDataPointSnapshot dataPoint = summary.collect().getDataPoints().get(0);
    for (Quantile q : dataPoint.getQuantiles()) {
      System.out.printf(
          "quantile %.2f: reported = %10.1f, expected ~ %10.1f%n",
          q.getQuantile(), q.getValue(), q.getQuantile() * 100_000);
    }
  }
}

Output with 1.8.0:

quantile 0.90: reported =        1.0, expected ~    90000.0
quantile 0.99: reported =        1.0, expected ~    99000.0

Both quantiles report the minimum of all 100,000 observations. The result does not
depend on the input distribution or the shuffle seed. A single targeted quantile
quantile(0.99, 0.005) reproduces it too.

How we found it

In our application we had

.quantile(0.9, 0.05)
.quantile(0.99, 0.005)

on a latency Summary. It reported p90 == p99 == 0.6ms while a
classic Histogram fed by the same observations (cross-checked against an in-process
exact-percentile counter) showed p90 = 2ms, p99 = 44ms. The reported value was below the
true median. Adding a .quantile(0.5, 0.05) softens the failure but doesn't fix it: get(0.99)
then returns a value from around the 85th percentile.

Observations

CKMSQuantiles:

1. compress() destroys the sketch. The error function from the CKMS paper
   (definition 5) allows a sample below a target (q, ε) at rank r to have width
   2ε(n−r)/(1−q). When 2ε ≥ 1−q — which holds with equality for both (0.9, 0.05) and
   (0.99, 0.005) — this is ≥ n−r: one sample may span every rank from r to n.
   compress() then merges away everything between the middle of the distribution and the
   maximum; the sample list collapses to just a few samples no matter how many values are inserted.

2. get() stops at the first wide sample. The scan stops at the first sample with
   r + g + delta > desiredRank + f(desiredRank)/2 and returns the previous sample's value.
   That rule is only correct when g + delta is small for all samples up to the target
   rank. Below a targeted quantile, deltas may legally be of order n — and freshly
   inserted samples get delta = f(r) − 1 while get() flushes the insert buffer right
   before scanning, so maximally-wide fresh samples are always present at query time. The
   scan therefore stops far before the target rank.

Tightening error/epsilon avoids the issue

The tight-epsilon (0.01 for p90, 0.001 for p99) Summary agrees with the histogram-derived p99,
while the identically-fed boundary-epsilon (0.05 for p90, 0.005 for p99) Summaries report p90 == p99 from
the very same measurements. So the failure is fully determined by the quantile
configuration, not by the data.

Side note

I have a fix with reproducer tests ready and happy to open a PR:
it bounds merges in compress() so a sample can never span across the accuracy window of a target quantile,
and changes get() to select the sample whose rank interval is centered closest to the desired rank.
With the reproducer config, get(0.99) goes from returning the minimum observation to a rank-accurate value.
The full existing test suite passes.