Latency percentile tracker (p50/p99)

Q: Why not average p99s across servers?

Percentiles do not compose: the average of each server's p99 is not the fleet's p99, and can be far off when one server is slow. To aggregate you need the underlying distribution, which is why systems ship histograms (fixed latency buckets with counts) that can be added together, and compute percentiles from the merged buckets.

Q: How would this look in Go, and in production?

In Go the direct translation is a ring buffer of samples plus a sorted []int maintained with sort.SearchInts and copy for the shift, behind a mutex. Production systems rarely keep raw samples. Prometheus histograms count samples per fixed bucket, and HDR histograms or t-digest/DDSketch give percentiles with bounded relative error in constant memory. They trade exactness for memory that does not grow with traffic, and they can be merged across instances.

Q: Why do SRE interviews ask this?

Percentiles are the language of SLOs and alerting, and the question tests whether you know the definition precisely (nearest rank, off-by-one), why averages mislead, and the real cost of computing them over a moving window.

mediumMetrics and health Must-do

Averages hide the slow requests that users actually notice, which is why SLOs are written in percentiles: "p99 latency under 300 ms". Build a tracker that reports percentiles over the most recent window_size latency samples.

API (Java: record(int), Integer percentile(double p) returning null when empty)

◈ DIAGRAM

PercentileTracker(window_size: int)
record(value: int) -> None       # e.g. a latency in ms
percentile(p: float) -> int or None
count() -> int                   # samples currently in the window

Rules

Only the last window_size recorded values count. Recording one more drops the oldest.
Use the nearest-rank definition: sort the n samples ascending, compute rank = ceil(p * n / 100) (at least 1), and return the sample at that 1-based rank. The answer is always a value that was actually recorded, never an interpolation.
p must satisfy 0 < p <= 100, otherwise raise ValueError. An empty tracker returns None.
Duplicate values are allowed and each counts separately.
percentile will be called far more often than a full sort per call can afford, for example on every dashboard refresh across many endpoints. It must not sort the window.

Outputs are the return values of the calls, in order.

Examples

Example 1

Input: t = PercentileTracker(5) record 120, 80, 300, 95, 110 t.percentile(50) t.percentile(99) t.record(90) t.percentile(50) t.percentile(20) t.count()

Output: 110 300 95 80 5

Explanation: Sorted window [80, 95, 110, 120, 300]: p50 has rank ceil(2.5) = 3, and p99 has rank ceil(4.95) = 5. Recording 90 evicts 120, giving [80, 90, 95, 110, 300].

Example 2

Input: t = PercentileTracker(100) t.percentile(50) t.record(7) t.percentile(1) t.percentile(100) t.percentile(0)

Output: null 7 7 error: p must be in (0, 100]

Explanation: With one sample every valid percentile is that sample. p = 0 has no nearest rank, so it is rejected.

Hints

Approach

Maintain two views of the same window:

arrival: a deque in arrival order, so you know which sample to evict.
ordered: a list kept sorted at all times.

record(v): if the window is full, pop the oldest value from arrival, find one copy of it in ordered by binary search, and delete it. Then append v to arrival and insert it into ordered at its binary-search position.
percentile(p): validate p, compute the nearest rank, and index into ordered. O(1).

Binary search makes finding the position O(log n). Inserting into or deleting from the middle of an array still shifts elements, O(n), but that is a fast memory move, and it moves the cost to record and away from queries. A balanced tree or order-statistics structure would make both sides O(log n) if the window were very large.

ComplexityTime O(n) record (O(log n) search + shift), O(1) percentileSpace O(n)

Python

import bisect
import math
from collections import deque
 
 
class PercentileTracker:
    def __init__(self, window_size):
        if window_size < 1:
            raise ValueError("window_size must be at least 1")
        self.window_size = window_size
        self.arrival = deque()      # samples in arrival order, for eviction
        self.ordered = []           # the same samples, kept sorted
 
    def record(self, value):
        if len(self.arrival) == self.window_size:
            old = self.arrival.popleft()
            del self.ordered[bisect.bisect_left(self.ordered, old)]   # remove one copy
        self.arrival.append(value)
        bisect.insort(self.ordered, value)
 
    def percentile(self, p):
        if not 0 < p <= 100:
            raise ValueError("p must be in (0, 100]")
        n = len(self.ordered)
        if n == 0:
            return None
        rank = max(1, math.ceil(p * n / 100))    # nearest-rank method
        return self.ordered[rank - 1]
 
    def count(self):
        return len(self.arrival)

Follow-up questions

Make the window time-based (the last 60 seconds) instead of the last N samples.
Latencies are integers from 0 to 10,000 ms. Can you make record O(1) with a counting array?
Merge trackers from 50 servers into one fleet-wide p99.

Frequently asked questions

Percentiles do not compose: the average of each server's p99 is not the fleet's p99, and can be far off when one server is slow. To aggregate you need the underlying distribution, which is why systems ship histograms (fixed latency buckets with counts) that can be added together, and compute percentiles from the merged buckets.

In Go the direct translation is a ring buffer of samples plus a sorted []int maintained with sort.SearchInts and copy for the shift, behind a mutex. Production systems rarely keep raw samples. Prometheus histograms count samples per fixed bucket, and HDR histograms or t-digest/DDSketch give percentiles with bounded relative error in constant memory. They trade exactness for memory that does not grow with traffic, and they can be merged across instances.

Percentiles are the language of SLOs and alerting, and the question tests whether you know the definition precisely (nearest rank, off-by-one), why averages mislead, and the real cost of computing them over a moving window.

Problem statement