CodeWalk

TDigest算法与百分位数计算

作者：我还是少年 · 2026-05-30 12:55

什么是TDigest算法？在大数据场景中如何高效计算百分位数（P50/P95/P99）？请说明TDigest的数据结构、数据合并（Cluster）策略，以及与常规排序法相比的内存和计算优势。在StarRocks/ClickHouse中如何使用TDigest？

回答

我还是少年

1. TDigest原理

TDigest是一种在线分位数估计算法，通过维护一组质心（Centroid）来近似数据分布：

数据结构：
Centroid = (mean, weight)  # 均值和权重

TDigest = 有序的Centroid列表
         [c1(1.2, 10), c2(3.5, 50), c3(7.8, 30), ...]

合并策略：

  • 新数据点找到最近的Centroid合并
  • 如果权重和超过阈值，则分裂
  • 保证Centroid在分位数轴上的分布密度与数据密度成正比

关键参数：

compression（压缩因子）：
- 值越大精度越高，占用内存更多
- 默认100，P99误差<0.5%
- 200-500用于高精度场景

2. 与排序法对比

维度全量排序法TDigest
内存全部数据固定大小（≈4KB*compression）
时间复杂度O(nlogn)O(n)
精度精确近似（可配置）
支持并行否是（可合并）
支持流式否是

3. 在StarRocks中使用

-- 聚合模型中使用
CREATE TABLE latency_metrics (
  api STRING,
  ts DATE,
  p50_latency PERCENTILE_UNION,
  p99_latency PERCENTILE_UNION
) AGGREGATE KEY(api, ts);

-- 导入
INSERT INTO latency_metrics VALUES
  ('/api/v1', '2024-01-01', 
   percentile_hash(150.0),  -- 构建TDigest
   percentile_hash(150.0));

-- 查询
SELECT 
  percentile_approx(p50_latency, 0.5),
  percentile_approx(p99_latency, 0.99)
FROM latency_metrics;

4. 在ClickHouse中使用

SELECT
  quantile(0.50)(latency) AS p50,
  quantile(0.99)(latency) AS p99,
  quantiles(0.50, 0.90, 0.99)(latency) AS percentiles
FROM metrics
WHERE ts > now() - INTERVAL 1 DAY;

-- TDigest版本（精度更高）
SELECT quantileTDigest(0.99)(latency) FROM metrics;

5. 适用场景

  • 在线服务延迟监控
  • 实时流量分析
  • 大规模日志分位数查询
  • 流式计算中的百分位统计