Netflix 并发 Latency Tracker：时间窗口与 P90/P99 查询

题目重点：围绕 Netflix 并发编程面经中的延迟上报和窗口分位数查询，明确一致快照、nearest-rank、乱序时间戳及精确与近似的成本取舍。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练版查询显式传 now，把窗口设为闭区间 [now-window, now]；题目仅写 time window，没有声明左右开闭或时钟来源。
使用 nearest-rank 精确分位数：升序第 ceil(pN/100) 个，p∈(0,100]；空窗口返回 None。题目没指定插值还是 nearest-rank。
允许乱序和未来 timestamp；查询只看窗口内样本，report 不自动永久删除旧样本。latency 非负，读写在一个进程的线程间并发。

解题路线

以 mutex 保护共享样本容器；写入短临界区追加一条 (timestamp,latency)。查询在锁内复制快照后释放锁，再过滤窗口并排序，确保本次查询基于某个一致时点，不阻塞写入直到排序完成。
按已约定 percentile 取 nearest-rank 下标；对端点重复值和空窗口单独测试。
若生产数据长时间运行，当前列表会无限增长。可按 event time 分桶并结合 watermark 淘汰；乱序最大迟到需要边界，否则无法安全地无损清理。若窗口查询很多，按时间索引窗口，再用 order-statistics tree、分桶直方图或 sketch 估算分位数；近似方案要写误差目标。

手动走一遍

训练例 report (t=8,10ms)、(t=10,20ms)、(t=10,100ms)；query(now=10,window=2,p=90) 读到三个值，nearest-rank 第 3 个为 100ms。query(now=10,window=1,p=50) 只读两条 t=10，结果第 1 个 20ms。若查询与上报同时发生，本次快照可包含或不包含新上报，但不能只读到半条记录。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from math import ceil
from threading import Lock


class LatencyTracker:
    """Exact nearest-rank percentile; queries include timestamps in [now-window, now]."""

    def __init__(self):
        self._samples = []
        self._lock = Lock()

    def report(self, timestamp, latency_ms):
        if latency_ms < 0:
            raise ValueError("latency must be nonnegative")
        with self._lock:
            self._samples.append((timestamp, latency_ms))

    def percentile(self, now, window, percent):
        if window < 0 or not 0 < percent <= 100:
            raise ValueError("invalid window or percentile")
        with self._lock:
            snapshot = tuple(self._samples)
        values = sorted(latency for timestamp, latency in snapshot if now - window <= timestamp <= now)
        if not values:
            return None
        return values[ceil(percent * len(values) / 100) - 1]

复杂度

训练实现 report O(1) 均摊；每次查询复制和过滤 N 条 O(N)，对窗口内 M 条排序 O(M log M)，空间 O(N+M)，存储随所有历史上报 O(N) 增长。锁保护只覆盖复制和追加；真正的高吞吐方案须用有界保留策略与按时间分片。

易错点与追问

容易失分的边界

不明确窗口边界与 percent 的定义，却在 P99 上比较不同算法结果。
只在 append 加锁，在遍历底层可变容器时不取快照。
单纯把所有历史样本排序做全局 P99，忘记时间窗口。
按当前时钟删除旧数据却声称仍可回答任意过去窗口或乱序迟到上报。
把 Python GIL 当作跨语言或复合读写的完整并发契约。

继续深挖

高写入量下如何避免一次全量复制？
若 query 必须严格线性化，快照时点怎样定义？
近似 P99 可接受 1% rank 误差时，直方图与 t-digest 如何选？
多用户上报是合并总体还是每用户分位数？