背景

首先说下，分位数(quantile)的概念，也就是我们监控中常见的p99， 这里举一个例子

排序为rank=⌊ϕN⌋的元素，其中N为序列中元素的个数。考虑以下例子数据：

11 , 21 , 24 , 61 , 81 , 39 , 89 , 56 , 12 , 51

查询ϕ−quantile分位点所在数据前，需要对无序数据进行排序：

input:  11   21   24   61   81   39   89   56   12   51
sort:   11   12   21   24   39   51   56   61   81   89
rank:   1    2    3    4    5    6    7    8    9    10

排序后，我想查这批数据的中位数 也就是：0.5−quantile 对应 rank=5，值为39

现实场景下，我们一般用这个来统计比如一段时间的调用延迟的p99，而上述操作无论在时间还是空间上成本比较高，实际场景中肯定不是这么实现的。

后文将阐述近年来实际工业中使用的各种分位数算法.

随机算法

实现案例:
dropwizard 的 metrics 库有提供随机算法(见ref)

原理解释:

维护一个固定长度的sample buffer数组，写sample时，随机确定是否插入到当前sample buffer 数组。

当需要查询quantile时，则进行传统的排序，计算quantile

时间复杂度

空间占用

固定大小，gc影响为0

缺点：数据失真严重

确定性算法

静态分桶

HdrHistogram

源码地址:
https://github.com/HdrHistogram/HdrHistogram

思路还是分桶，只不过不是一个数字一个桶，而是一个区间一个桶。

该区间的范围可以是线性增长，可指数增长。

通过牺牲一小部分精度，从而达到减小空间占用，并且数据大致准确的结果。

下图中，采样范围在 [1-15]的有991个，在 [16-31]的有2个...

空间占用
根据采样点的范围以及精度分桶，大小固定。gc影响为0

缺点

1. 统计范围有限，需要预先确定

q-digest

本质上还是静态分桶，只是用完全二叉树存储数据。

他的使用场景为为大数据分块计算 histogram 后，可对多个histogram 快速归并

数据格式如下图所示

上图中，这颗树总共能统计 1-8，8个数字。其中，有4个3，6个4，2个5-6, 2个 7-8 , 1个 1-8

它将数据压缩的的目标就是将 σ 个采样点 变成 k 组数据输出。下面是将简述压缩树的过程

是否可以进行压缩，以2个约束条件作为宗旨

1. count(v) <= n/k

2. count(v) + count(vp1) + count(vp2) > n/k

vp1 vp2 就是下图框起来的3个点

如何计算Quantile?

用图1做例子

首先，我们把树上每个节点根据其数进行bfs，并进行编号，并根据其编号的值的个数做成一个二维组 （编号，count）

可得到

{〈1,1〉,〈6,2〉,〈7,2〉,〈10,4〉,〈11,6〉}

每个节点可表达的数据不同，比如 c可表达[5, 6], g 可表达[1,8]

然后再根据每个二维组，可表达的最大范围进行正序排序

{〈10,4〉 [3],〈11,6〉 [4],〈6,2〉 [5-6],〈7,2〉 [7-8], 〈1,1〉 [1-8]}

最后就是 count x 请求的分位数，确定index的套路。

对于 p50 = 0.5*15 = 7.5

4 + 6 > 7.5

所以p50 是 <11.6> 也就是4

时间复杂度

优点：树的特点决定了，对相同规格的树，merge操作成本很低，适合大数据map reduce 场景下的多颗树的合并作业

缺点：

1. 需要预分桶

2. 空间占用较多

动态分桶

GK 算法

思路，还是分桶，只不过这个桶的大小是变化的，论文的话是根据一个区间段来划分的，这里简化下，本质还是根据现存的相邻sample之间的距离确定下个sample是不是放在一个新的独立的桶，具体如下图

优点：

1. 不需要预设定统计范围

2. 根据sample的量的范围，大部分情况下较静态分桶节省空间

缺点：

1. 写成本比静态分桶高，比起静态分桶是一个确定的空间，他的空间会不定期扩大。

2. 精度不可控。

1. 假设 sample数据很均匀的平铺在总的数据范围内，则会导致采样的节点数过多，甚至不如静态分桶。

2. 假设 部分节点的距离较大，则会导致精度降低。

时间复杂度

注：实现时，需要维护一个buffer，当buffer满时需要做排序，所以写的成本按照最慢的来算，就是nlogn

空间占用

空间不固定，并且由于有merge，会有一定的gc成本

CKMS算法

GK算法的升级版本，prometheus 的 summary 就用的该算法实现

它引入了一个可配置的错误率的概念，从而解决了GK 精度不可控问题。

GK 的桶的大小是根据 sample之间的距离delta 决定的，而 CKMS 在抉择是否开辟新桶，则是根据用户设置的错误率。

delta = 错误率 x 总体sample个数，并以此决定分桶的大小。

下图是一个数据合并的例子

可见，当错误率为0.1时，当size > 10 时，会对range <=1 的进行合并

优点：

1. 不需要预设定统计范围

2. 根据sample的量的范围，大部分情况下较静态分桶节省空间

3. 空间上 完全靠用户参数 错误率 决定，更可控。

缺点：

1. 写成本比静态分桶高

时间复杂度

注：同上，需要维护一个buffer，写时，大部分情况下都是O(1), 触发merge 时由于需要做排序，所以O(nlogn)

空间占用

空间不固定，并且由于有merge，会有一定的gc成本

素描法 (sketch)

t-digest

源码地址:
https://github.com/tdunning/t-digest

t-digest算法，比动态分桶算法更准，但是资源又可控

这是作者自己写的简介
https://mapr.com/blog/some-important-streaming-algorithms-you-should-know-about/

简单描述:

1. 本质上，还是动态分桶，但有以下几个特点

1. 桶的总量在一开始就固定，ckms 并不固定，这样实现可以直接用定长数组，这对gc友好

2. 桶划分函数也更适合于计算分位数场景，众所周知我们更关心 p9999, p999 的精度，对p90, p50 的精度并不太在意。
   所以在划分桶的函数上对2边分桶分的更细，对中间划分的更粗
   
   

3. 

4. 桶的大小随着采样个数的增加而增加。（不这样也就没法保证空间固定了）
   桶大小 = f(n) x 当前采样个数

时间复杂度:

注：写时，大部分情况下都是O(1), 触发merge 时排序，导致 O(nlogn)

空间复杂度:

总空间占用固定，对gc影响较小。

压测

最终我们基于以下3种较为可靠的算法做压测，做一个横向比较。

我们的场景，一般用于统计接口的 p99 的耗时。允许几十ms的误差。一般统计的范围为 0 - 6000

由于 CKMS 和 t-digest 的实现并非线程安全，所以对其读写操作时都加了把锁。测试代码在此

这里直接给结果:

从上述结果可见，tdigest 的读写性能相对来说是最好的，但是他的空间占用却很厉害。hdrhistogram 反倒是出乎意料的写性能比tdigest略逊一筹。

仔细看源码会发现tdigest 为了减少gc影响，内部使用了多个固定长度的double数组来实现，

也就是说，假如采样的范围足够大时，tdigest 才能凸显出优势，不然，内存占用有点多。

所以，最终，在我们的场景下，还是选择 hdrhistogram

Reference

随机算法论文
http://www.cs.umd.edu/~samir/498/vitter.pdf

dropwizard 的 metrics 库实现的随机算法
https://github.com/dropwizard/metrics/blob/release/4.1.x/metrics-core/src/main/java/com/codahale/metrics/UniformReservoir.java

GK算法教学
http://www.mathcs.emory.edu/~cheung/Courses/584/Syllabus/08-Quantile/Greenwald.html

https://blog.csdn.net/matrix_zzl/article/details/78641264

GK算法论文
https://www.cis.upenn.edu/~sanjeev/papers/sigmod01_quantiles.pdf

Q-digest算法论文
https://graphics.stanford.edu/courses/cs468-05-winter/Papers/Information_Aggregation/Suri_sensys04.pdf

addthis stream-lib 的 Qdigest算法实现
https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/quantile/QDigest.java

CKMS算法论文
http://dimacs.rutgers.edu/~graham/pubs/papers/bquant-icde.pdf

prometheus client lib内使用的CMKS Quantiles
https://github.com/prometheus/client_java/blob/master/simpleclient/src/main/java/io/prometheus/client/CKMSQuantiles.java

t-digest
https://blog.bcmeng.com/post/tdigest.html

t-digest 论文
https://arxiv.org/pdf/1902.04023