T-Digest：高精度估算 p99 与 p999 分位数
T-Digest 解决流式数据的分位数估算问题（p50/p99/p999），核心洞察是"越靠近边界的质心越精确"，使得极端分位数（如 p99.9）的精度远高于普通近似方法。Prometheus、Elasticsearch、InfluxDB 均内置 T-Digest。
目录
| 章节 | 说明 |
|---|---|
| 要解决的问题 | 为什么流式分位数难 |
| 核心原理 | 质心 + scale function |
| Java 实现 | 批量合并版完整代码 |
| 误差特性 | 边界精度高的数学原因 |
| 工程应用 | 监控系统中的实践 |
| DDSketch：确定性近似方案 | 对数分桶、均匀误差保证、与 T-Digest 对比 |
要解决的问题
场景：统计接口响应时间的 p50 / p99 / p999，数据是无限流式到来的。
精确方案：保存所有数据排序——内存 O(n)，对流式场景不可接受。
近似方案对比：
| 方案 | 内存 | p50 精度 | p99 精度 | p999 精度 |
|---|---|---|---|---|
| 等宽直方图 | O(b) | 中 | 差 | 很差 |
| 指数衰减采样 | O(k) | 中 | 中 | 差 |
| T-Digest | O(delta) | 好 | 很好 | 极好 |
T-Digest 的独特之处：极端分位数精度高于中间分位数（恰好与监控需求吻合——p99 比 p50 更重要）。
核心原理
质心（Centroid）
T-Digest 将数据压缩为一组质心 (mean, weight)，每个质心代表一批相近数据点的加权均值和总权重：
质心按均值升序排列，可以用累计权重来定位分位数。
Scale Function（合并约束）
直觉：不同位置的质心允许的最大 weight 不同——靠近边界（q≈0 或 q≈1）的质心必须小，靠近中间（q≈0.5）的质心可以大。
T-Digest k1 scale 函数将分位数位置 q 映射到"k 空间"：
$$k_1(q) = \frac{\delta}{2\pi} \cdot \arcsin(2q - 1)$$
- δ（delta）= compression 参数（用户设置，常用 100~300）
- q ∈ [0, 1] 是质心在累计权重中的位置
- arcsin(2q-1) 在 q=0.5 时为 0，在 q→0 或 q→1 时趋向 ±π/2
两个相邻质心可以合并，当且仅当：
$$k_1(q_{\text{right}}) - k_1(q_{\text{left}}) \leq 1$$
即合并后不超出 k 空间的一个单位区间。
为什么边界质心小？ 对 k₁(q) 求导：
$$\frac{dk_1}{dq} = \frac{\delta}{\pi \cdot \sqrt{q(1-q)}}$$
- q=0.5 时：dk/dq = δ/π，最小，说明 k 空间里单位区间对应的 q 范围最大，即一个质心可以覆盖更多数据 → 质心 weight 大
- q→0 或 q→1 时：dk/dq → ∞，说明 k 空间里单位区间对应的 q 范围极小，即一个质心只能覆盖极少数据 → 质心 weight 小
下图展示 k₁(q) 的形状——边界陡峭，中间平缓：
质心大小分布
scale function 的直接结果是：质心的 weight（大小）从边界到中间呈"两头小、中间大"的分布。
边界处质心极小（接近单个数据点），分位数查询等同于精确计算；中间质心大，精度相对较低。这正好契合监控场景——p99、p999 比 p50 更需要精确。
分位数查询
将质心列表视为累计权重的分段线性函数，对目标 q 做插值：
target = q × totalWeight
遍历质心，累加 weight，找到覆盖 target 的质心 i
在质心 i-1 和 i 之间做线性插值：
frac = (target - cumWeight_before_i) / centroid_i.weight
result = centroid_{i-1}.mean + frac × (centroid_i.mean - centroid_{i-1}.mean)
Java 实现
import java.util.*;
/**
* T-Digest（k1 scale，批量合并版）
*
* compression 参数：100~300 为常用范围
* - compression=100：质心约 62 个，p99 误差约 0.34%
* - compression=200：质心约 125 个，误差更小
*/
public class TDigest {
private final double compression;
private final List<double[]> centroids; // [mean, weight]，按 mean 升序
private final List<double[]> pending; // 待压缩缓冲区
private double totalWeight;
private static final int BUFFER_LIMIT = 512;
public TDigest(double compression) {
this.compression = compression;
this.centroids = new ArrayList<>();
this.pending = new ArrayList<>();
this.totalWeight = 0;
}
public void add(double x) {
pending.add(new double[]{x, 1.0});
totalWeight++;
if (pending.size() >= BUFFER_LIMIT) compress();
}
/** k1(q) = compression/(2π) × arcsin(2q-1) */
private double k1(double q) {
if (q <= 0) return -compression / 2.0;
if (q >= 1) return compression / 2.0;
return compression / (2 * Math.PI) * Math.asin(2 * q - 1);
}
/** 批量合并：将 pending + centroids 排序后贪心合并 */
private void compress() {
if (pending.isEmpty()) return;
List<double[]> all = new ArrayList<>(centroids.size() + pending.size());
all.addAll(centroids);
all.addAll(pending);
pending.clear();
all.sort(Comparator.comparingDouble(c -> c[0]));
centroids.clear();
if (all.isEmpty()) return;
double n = totalWeight;
double[] cur = new double[]{all.get(0)[0], all.get(0)[1]};
double cumLeft = 0.0; // 当前质心左边界的累计权重
for (int i = 1; i < all.size(); i++) {
double[] point = all.get(i);
double newWeight = cur[1] + point[1];
double qLeft = cumLeft / n;
double qRight = (cumLeft + newWeight) / n;
// 合并条件：k 区间跨度 ≤ 1
if (k1(qRight) - k1(qLeft) <= 1.0) {
cur[0] = (cur[0] * cur[1] + point[0] * point[1]) / newWeight;
cur[1] = newWeight;
} else {
centroids.add(cur);
cumLeft += cur[1];
cur = new double[]{point[0], point[1]};
}
}
centroids.add(cur);
}
public double quantile(double q) {
compress(); // flush 剩余 pending
if (centroids.isEmpty()) throw new IllegalStateException("空 T-Digest");
if (q <= 0) return centroids.get(0)[0];
if (q >= 1) return centroids.get(centroids.size() - 1)[0];
double target = q * totalWeight;
double cum = 0;
for (int i = 0; i < centroids.size(); i++) {
double[] c = centroids.get(i);
double lo = cum, hi = cum + c[1];
if (target <= hi) {
if (i == 0) return c[0];
double[] prev = centroids.get(i - 1);
double frac = c[1] > 0 ? (target - lo) / c[1] : 0;
return prev[0] + frac * (c[0] - prev[0]);
}
cum = hi;
}
return centroids.get(centroids.size() - 1)[0];
}
public int centroidCount() { compress(); return centroids.size(); }
}
使用示例：
TDigest td = new TDigest(100);
for (double latency : latencyStream) td.add(latency);
System.out.println("p50: " + td.quantile(0.50) + "ms");
System.out.println("p99: " + td.quantile(0.99) + "ms");
System.out.println("p999: " + td.quantile(0.999) + "ms");
验证结果（均匀分布 10 万个数据点，compression=100）：
| 分位数 | 真实值 | 估算值 | 误差 |
|---|---|---|---|
| p50 | 499.71 | 496.26 | 0.69% |
| p90 | 899.03 | 890.32 | 0.97% |
| p99 | 990.30 | 987.00 | 0.34% |
| 质心数 | — | 62 | 远小于 100000 |
误差特性
边界精度高的数学原因
arcsin 函数在 q=0 和 q=1 附近导数趋向无穷大：
| q | dk₁/dq | 含义 |
|---|---|---|
| 0.5 | δ/π（最小） | 质心可以很大，精度低 |
| 0.1 | δ/π × 3.3 | 质心较小 |
| 0.01 | δ/π × 10 | 质心很小 |
| 0.001 | δ/π × 32 | 质心极小，接近精确 |
dk₁/dq 越大，k 空间里同一个单位区间对应的 q 范围越窄，即该位置的质心必须越小。p99（q=0.99）和 p999（q=0.999）对应的质心都接近单个数据点，分位数查询几乎等同于精确计算。
compression 参数与精度
| compression | 质心数（n=10万） | p50 误差 | p99 误差 |
|---|---|---|---|
| 50 | ~32 | ~5% | ~0.7% |
| 100 | ~62 | ~2.7% | ~0.34% |
| 200 | ~125 | ~1.35% | ~0.09% |
规律：compression 翻倍，质心数翻倍，误差减半。
工程应用
分布式合并
多个节点各自维护一个 T-Digest，周期性将质心列表发送到聚合服务合并后查询：
合并算法：将多个质心列表拼接后排序，重新执行 compress()，结果等价于对所有原始数据做一次 T-Digest。总内存始终是 O(compression) 级别。
对比其他方案
| 方案 | p99 精度 | 内存 | 流式支持 | 可合并 |
|---|---|---|---|---|
| 精确排序 | 精确 | O(n) | 否 | 否 |
| HDR Histogram | 好（预设范围内） | O(范围/精度) | 是 | 是 |
| T-Digest | 极好（尤其极端值） | O(compression) | 是 | 是 |
| GK Summary | 好 | O(1/ε × log(εn)) | 是 | 否 |
选 T-Digest 的场景：
- 需要精确的 p99、p999（如 SLA 监控）
- 数据范围不确定（无法预设 HDR Histogram 的 max）
- 分布式部署需要合并多个节点的统计结果
DDSketch：确定性近似方案
DDSketch（2019，DataDog 提出）是 T-Digest 的主要竞争算法，核心差异是全范围误差均匀、结果确定性。
核心思路：对数分桶
DDSketch 不存质心，而是把值域划分为等比数列桶，每个桶只存计数：
桶边界：γ^0, γ^1, γ^2, ... γ = (1+α)/(1-α)，α 为相对误差参数
α=0.01 时，γ ≈ 1.0202：
桶0: [1.000, 1.020)
桶1: [1.020, 1.041)
桶2: [1.041, 1.062)
...
桶k: [γ^k, γ^(k+1))
写入一个值 x 时，只需计算桶编号并加 1：
桶编号 = ceil(log(x) / log(γ))
查询分位数时，按桶顺序累加计数，找到覆盖目标比例的桶，返回桶中间值。
误差保证
对任意分位数 q，相对误差 ≤ α（严格保证，不是概率意义）：
真实值 v，估算值 v̂：|v̂ - v| / v ≤ α
这与 T-Digest 的"边界精、中间粗"不同——DDSketch 全范围误差一致。
Java 实现
import java.util.*;
/**
* DDSketch：对数分桶近似分位数
* α = 相对误差上限（如 0.01 = 1%）
*/
public class DDSketch {
private final double alpha;
private final double gamma; // 桶比例因子 = (1+α)/(1-α)
private final double logGamma; // ln(γ)，预计算加速
private final Map<Integer, Long> buckets = new HashMap<>();
private long totalCount = 0;
public DDSketch(double alpha) {
this.alpha = alpha;
this.gamma = (1 + alpha) / (1 - alpha);
this.logGamma = Math.log(gamma);
}
/** 将值 x 映射到桶编号 */
private int bucketIndex(double x) {
return (int) Math.ceil(Math.log(x) / logGamma);
}
/** 写入一个值 */
public void add(double x) {
if (x <= 0) throw new IllegalArgumentException("DDSketch 只支持正数");
int idx = bucketIndex(x);
buckets.merge(idx, 1L, Long::sum);
totalCount++;
}
/** 查询分位数 q ∈ (0, 1] */
public double quantile(double q) {
if (buckets.isEmpty()) throw new IllegalStateException("空 DDSketch");
long target = (long) Math.ceil(q * totalCount);
long cum = 0;
// 按桶编号升序遍历
List<Integer> sortedKeys = new ArrayList<>(buckets.keySet());
Collections.sort(sortedKeys);
for (int idx : sortedKeys) {
cum += buckets.get(idx);
if (cum >= target) {
// 返回桶的几何中点：√(γ^idx × γ^(idx+1)) = γ^(idx+0.5)
return Math.pow(gamma, idx + 0.5);
}
}
int last = sortedKeys.get(sortedKeys.size() - 1);
return Math.pow(gamma, last + 0.5);
}
/** 合并另一个 DDSketch（α 必须相同） */
public void merge(DDSketch other) {
if (Double.compare(this.alpha, other.alpha) != 0) {
throw new IllegalArgumentException("alpha 不同，无法合并");
}
other.buckets.forEach((idx, cnt) ->
buckets.merge(idx, cnt, Long::sum));
totalCount += other.totalCount;
}
public int bucketCount() { return buckets.size(); }
}
使用示例：
DDSketch sketch = new DDSketch(0.01); // 1% 相对误差
for (double latency : latencyStream) sketch.add(latency);
System.out.println("p50: " + sketch.quantile(0.50) + "ms");
System.out.println("p99: " + sketch.quantile(0.99) + "ms");
System.out.println("p999: " + sketch.quantile(0.999) + "ms");
与 T-Digest 对比
| T-Digest | DDSketch | |
|---|---|---|
| 误差类型 | 确定性，但边界/中间不均匀 | 确定性，全范围 ≤ α |
| 插入顺序影响 | 有（合并顺序影响质心分布） | 无（相同数据结果完全一致） |
| 合并性 | 合并后误差略增 | 完全可合并，误差不增 |
| 内存 | O(compression)，质心数有界 | O(log(max/min)/log(γ))，桶数取决于值域范围 |
| 支持负数/零 | 支持 | 原版不支持（需 offset 扩展） |
| 实现复杂度 | 较高（k 空间、合并逻辑） | 较低（哈希表 + 对数计算） |
| 主要采用者 | Prometheus、ES、InfluxDB | DataDog、部分新系统 |
选 DDSketch 的场景：
- 需要严格的全范围误差保证（SLA 合规场景）
- 多节点合并后误差不能累积
- 数据范围已知且为正数
选 T-Digest 的场景：
- 对极端分位数（p99.9+）精度要求特别高
- 数据含负数或零
- 已有 Prometheus / ES 生态，直接复用内置实现
参考资料
- Computing Extremely Accurate Quantiles Using t-Digests (Ted Dunning & Otmar Ertl, 2019)
- t-digest GitHub (tdunning) — Java 参考实现
- DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees (DataDog, 2019)
评论 (0)