📘

Aggregate Latency Histogram Buckets to a Quantile

MediumSystems & Infrastructure 📚 ML Systems & Infrastructure 1

Problem Statement

Prometheus-style latency histograms store cumulative counts per bucket boundary. Estimate a quantile by linear interpolation within the bucket where the quantile rank falls.

Background

Buckets are given as ascending (upper_bound, cumulative_count) pairs (cumulative = number of samples <= upper_bound). The last bucket's count is the total. For quantile q, the target rank is q * total. Find the first bucket whose cumulative count >= rank; linearly interpolate between the previous bucket's upper bound (or 0) and this bucket's upper bound based on where rank falls within [prev_count, this_count].

Your Task

def histogram_quantile(buckets, q):

Return the estimated quantile value (float), rounded to 4 decimals.

Input Format

buckets (list of (upper_bound, cumulative_count), ascending), q (float in [0,1]).

Output Format

A float rounded to 4 decimals.

Sample

print(histogram_quantile([(1.0, 10), (2.0, 20), (5.0, 30)], 0.5))

Output:

1.5

Example:

Input:

print(histogram_quantile([(1.0, 10), (2.0, 20), (5.0, 30)], 0.5))

Output:

1.5

Reasoning:

Determine the total number of samples from the last bucket's cumulative count: $total = 30$ .
Calculate the target rank for the 50th percentile ( $q = 0.5$ ): $rank = 0.5 \times 30 = 15$ .
Identify the bucket containing the rank by finding the first cumulative count $\ge 15$ : the first bucket has count $10$ (too low), and the second has count $20$ (sufficient), so the relevant interval is between bounds $1.0$ and $2.0$ .
Compute the linear interpolation fraction within this bucket, using the previous cumulative count ( $10$ ) and the current span ( $20 - 10 = 10$ ): $frac = \frac{15 - 10}{10} = 0.5$ .
Apply the fraction to the bucket width to estimate the value: $1.0 + 0.5 \times (2.0 - 1.0) = 1.5$ .
The final output is 1.5

Constraints:

rank = q * total (total = last cumulative count).
Interpolate in the bucket where cumulative first reaches rank, between prev bound (or 0) and this bound over [prev_count, this_count].
Round to 4 decimals; buckets non-empty and ascending.

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost DecisionMedium Minimum-Cost Job Scheduling Across Priced WindowsHard Deduplicate Retried Pipeline Runs by Idempotency KeyMedium Retry with Capped Exponential Backoff and Jitter CapMedium Critical Path Length of a Pipeline DAGMedium

1. Background Knowledge

In observability systems like Prometheus, latency is not stored as raw values but as histograms. A histogram divides the value range into buckets defined by upper bounds. Each bucket stores a cumulative count: the total number of observations that are less than or equal to that bucket's upper bound. This structure is memory-efficient and allows for fast aggregation across many time series, but it loses the exact distribution of values within a bucket.

To estimate a specific value, such as the 99th percentile (p99), from this aggregated data, we use quantile estimation. The core idea is to find the bucket that contains the target rank and then assume a uniform distribution of samples within that bucket. This allows us to perform linear interpolation to estimate the value more precisely than just returning the bucket boundary. This technique is fundamental to calculating Service Level Objectives (SLOs), where you might need to guarantee that 99% of requests complete within a certain time.

The mathematical foundation relies on the relationship between the cumulative distribution function (CDF) and the quantile function. If $F(x)$ is the CDF, the quantile $Q(q)$ is the inverse. In a discrete histogram, $F(x)$ is a step function. Linear interpolation smooths these steps, creating a piecewise linear approximation of the inverse CDF. This is the standard method used by Prometheus's histogram_quantile function.

2. Algorithm Approach

The problem is a search and interpolation task.

Compute Target Rank: Calculate the absolute number of samples corresponding to the quantile $q$ . Let $N$ be the total count (the cumulative count of the last bucket). The target rank is $R = q \times N$ .
Locate Bucket: Iterate through the buckets to find the first bucket where the cumulative count is greater than or equal to $R$ . Let this be bucket $i$ with upper bound $u_i$ and count $c_i$ .
Identify Previous Bucket: Determine the previous bucket $i-1$ with upper bound $u_{i-1}$ and count $c_{i-1}$ . If $i$ is the first bucket, treat $u_{i-1} = 0$ and $c_{i-1} = 0$ .
Linear Interpolation: Calculate the position of $R$ within the interval $[c_{i-1}, c_i]$ . Use this relative position to interpolate between $u_{i-1}$ and $u_i$ .

The interpolation formula is:

\text{value} = u_{i-1} + \frac{R - c_{i-1}}{c_i - c_{i-1}} \times (u_i - u_{i-1})

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.