算法与数据结构 / 概率型 sketch · 用固定内存换有界误差 / t-digest：按分位密度自适应分桶 待审核 5 / 7
scale function · rank 误差 · 尾部更细

t-digest：按分位密度自适应分桶

基数与频次都是可加的量：两个分片各数一遍，合起来就是全局答案。分位数不是。分片 A 的 p99 是 800、分片 B 的 p99 是 900，全局 p99 既不是 850 也不是 900——它取决于两边的整条分布，而 p99 这一个数字里没有这个信息。

这一条决定了分位数结构的形态：它必须留下分布的形状，不能只留一个数。t-digest 留的是一串 centroid，每个记一对 (mean,weight)(\text{mean}, \text{weight})。

1 · 分位数的不可加性

三个问题的可加性各不相同：

问题 需要留下什么 合并算子
有多少个不同的 key 每桶的最长前导零串 逐桶取 max
这个 key 出现几次 每格的频次之和 逐格相加
p99 是多少 分布的形状 无逐位算子

前两个的状态里，每一位都是一个可以独立合并的量。分位数没有这个性质：任何固定的「第 ii 个位置」在两个分片里对应的不是同一段数据，逐位合并无从谈起。

一个直接的办法是等宽直方图：把值域切成固定的若干段，各记落进去的个数。它可加，但要求预先知道值域，而延迟分布的右尾能拉到 median 的几十倍，切法一旦定死就再也调不了。t-digest 换成按分位而非按值切，切点随数据自己浮动。

2 · scale function 与自适应分桶

压缩规则是：把全部点按值排序，从左往右扫，能并进当前 centroid 就并，并不下就另起一个。判据由一个 scale function 给出，它把累积分位 qq 映到一个 kk 空间，并要求单个 centroid 在 kk 空间里的跨度不超过 1：

k1(q)=delta2πarcsin⁡(2q−1)k_1(q) = \frac{\text{delta}}{2\pi} \arcsin(2q - 1)

arcsin⁡\arcsin 在 q→0q \to 0 与 q→1q \to 1 处导数发散。同样是 kk 空间里宽度为 1 的一段，折回 qq 空间时：q=0.5q = 0.5 附近对应 0.0314，q=0.9q = 0.9 附近 0.0189，q=0.99q = 0.99 附近 0.0063，q=0.999q = 0.999 附近 0.0020。中间宽、两端窄的分桶就是这么来的，不需要任何额外机制。

k1k_1 的值域宽度是 delta/2\text{delta}/2，故 centroid 个数约为 delta/2\text{delta}/2。delta=100\text{delta} = 100 时实测 55 到 58 个，每个 centroid 两个 double 共 16 字节，合计不到 1KB——而它摘要的是 20 万个样本。

图 2-1 · 3 万个 lognormal 样本压成的 centroid 分位带与权重曲线。可在 k1 与 k0 之间切换 scale function，可调 delta，可选关注的分位观察该处的桶宽与误差。

3 · 等权分桶的对照

「自适应分桶买到了什么」这个问题可以在同一个引擎上问：把 scale function 换成线性的 k0(q)=delta⋅q/2k_0(q) = \text{delta} \cdot q / 2，值域宽度不变，centroid 预算不变，只是每个 centroid 的权重变成近似相等。

delta=100\text{delta} = 100、N=20N = 20 万的实测，两边都是 55 个 centroid：

k1k_1 权重 k0k_0 权重
覆盖 q=0.5q = 0.5 的那个 5922 3819
覆盖 q=0.99q = 0.99 的那个 888 3303
覆盖 q=0.999q = 0.999 的那个 417 1417
最大与最小之比 44 2.8

k1k_1 把尾部的桶做细了三到四倍，代价是中间的桶粗了五成。这笔交易在 p50 上是亏的：k0k_0 在 q=0.5q = 0.5 的 rank 误差 2.61×10−42.61 \times 10^{-4}，比 k1k_1 的 4.00×10−44.00 \times 10^{-4} 还小一点。在 p99 上则完全反过来，k0k_0 是 3.22×10−33.22 \times 10^{-3}，比 k1k_1 的 3.43×10−43.43 \times 10^{-4} 差了 9.4 倍。

4 · rank 误差与值误差的分歧

「t-digest 在 p99 比 p50 更准」这句常见说法需要限定，否则它是错的。实测把两个口径分开看：

qq rank 误差 值相对误差
0.5 4.00×10−44.00 \times 10^{-4} 0.092%
0.9 5.21×10−45.21 \times 10^{-4} 0.280%
0.99 3.43×10−43.43 \times 10^{-4} 1.230%
0.999 2.42×10−42.42 \times 10^{-4} 7.914%

rank 误差（估计值在样本里的真实分位与目标分位之差）确实在尾部更小，从 4.00×10−44.00 \times 10^{-4} 降到 2.42×10−42.42 \times 10^{-4}。值相对误差则反过来，从 0.092% 涨到 7.914%，差了近两个量级。

两者不矛盾。lognormal 的右尾很平，同样万分之几的 rank 偏移，在 median 附近对应零点几个百分点的值，在 p99.9 附近就对应百分之几。t-digest 的保证写在 rank 上，值误差随分布形状走。

图 4-1 · 各分位上的 rank 误差与值相对误差，k1 与 k0 两条曲线并列。可切换误差口径，观察两个口径的走势相反。

写这一页时的原稿按常见说法写成了「p99 的相对误差比 p50 小」，实测直接推翻了它。改法是把「相对误差」这个含糊的词拆成两个口径分别给数——而不是把数字改成符合原稿的那一组。

警示 · 极端尾部还有一处更硬的限制。delta=100\text{delta} = 100 时 p99.99 的值相对误差实测 116%：最后一个 centroid 之外没有任何信息，估计只能在它的均值与全局 max 之间线性插值。delta\text{delta} 加到 200 后降到 4.55%。要报 p99.99 就得把 delta 提上去，或者改用把极值单独留下的实现（Dunning 的参考实现对两端的 singleton centroid 有专门处理，本页的简化引擎没有）。

5 · 合并

合并只是把两串 centroid 拼起来重跑一次压缩。centroid 是 (mean,weight)(\text{mean}, \text{weight}) 这样一个可加的摘要，不记它来自哪条流，压缩过程也不关心输入是原始点还是已经合过的 centroid。

合并后的 centroid 数仍被 delta\text{delta} 卡住，不随分片数增长。十份 20 万样本的分片各建一份再依次合并，实测各分位的 rank 误差仍在 3×10−33 \times 10^{-3} 以内（core/tdigest.test.ts 里就是这么断言的）。

图 5-1 · 分片各建一份再合并，与对全量直接建一份的逐分位对照。可调分片数观察 centroid 数与传输量的变化。

与 HyperLogLog 的合并有一处本质差别：那边的合并结果与直接建的一份逐桶相等，这边不是。每次压缩都把已经合过的 centroid 当作一个整体，信息一旦并进去就取不回来，分片切法不同最终的 centroid 边界也就不同。t-digest 是 mergeable 的，但不是「合并等于重算」那一档。

6 · KLL 这条路线

t-digest 的误差界是经验性的，Dunning 与 Ertl 给出的是大量实测而非形式化证明。要一个带证明的界，另一条路是 KLL sketch：它用分层的随机采样，在 O(ε−1log⁡log⁡δ−1)O(\varepsilon^{-1} \log\log \delta^{-1}) 空间内给出 ε\varepsilon 的 rank 误差保证，且这个空间是最优的。

两者的取舍很清楚。KLL 的界是全分位一致的 ε\varepsilon，t-digest 的 rank 误差随 q(1−q)q(1-q) 收窄，在尾部实际更准但没有证明。Apache DataSketches 选 KLL，Elasticsearch 与 Druid 用 t-digest，分歧点正在「要不要一个可证的界」。

7 · 参考文献

  1. Dunning, T., & Ertl, O. (2019). Computing extremely accurate quantiles using t-digests. arXiv:1902.04023.
  2. Karnin, Z., Lang, K., & Liberty, E. (2016). Optimal quantile approximation in streams. FOCS 2016, 71–78.
  3. Greenwald, M., & Khanna, S. (2001). Space-efficient online computation of quantile summaries. SIGMOD 2001, 58–66.
  4. Agarwal, P. K., Cormode, G., Huang, Z., Phillips, J. M., Wei, Z., & Yi, K. (2013). Mergeable summaries. ACM Transactions on Database Systems, 38(4), 26.