首先说下,分位数(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
时间复杂度
写 | O(1) |
读 | O(nlogn) |
空间占用
固定大小,gc影响为0
缺点:数据失真严重
源码地址:
https://github.com/HdrHistogram/HdrHistogram
思路还是分桶,只不过不是一个数字一个桶,而是一个区间一个桶。
该区间的范围可以是线性增长,可指数增长。
通过牺牲一小部分精度,从而达到减小空间占用,并且数据大致准确的结果。
下图中,采样范围在 [1-15]的有991个,在 [16-31]的有2个...
时间复杂度 | |
---|---|
写 | O(1) |
读 | O(n) |
空间占用
根据采样点的范围以及精度分桶,大小固定。gc影响为0
缺点
统计范围有限,需要预先确定
本质上还是静态分桶,只是用完全二叉树存储数据。
他的使用场景为为大数据分块计算 histogram 后,可对多个histogram 快速归并
数据格式如下图所示
上图中,这颗树总共能统计 1-8,8个数字。其中,有4个3,6个4,2个5-6, 2个 7-8 , 1个 1-8
它将数据压缩的的目标就是将 σ 个采样点 变成 k 组数据输出。下面是将简述压缩树的过程
是否可以进行压缩,以2个约束条件作为宗旨
count(v) <= n/k
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
时间复杂度
写 | O(1) |
读 | O(nlogn) |
优点:树的特点决定了,对相同规格的树,merge操作成本很低,适合大数据map reduce 场景下的多颗树的合并作业
缺点:
需要预分桶
空间占用较多
思路,还是分桶,只不过这个桶的大小是变化的,论文的话是根据一个区间段来划分的,这里简化下,本质还是根据现存的相邻sample之间的距离确定下个sample是不是放在一个新的独立的桶,具体如下图
优点:
不需要预设定统计范围
根据sample的量的范围,大部分情况下较静态分桶节省空间
缺点:
写成本比静态分桶高,比起静态分桶是一个确定的空间,他的空间会不定期扩大。
精度不可控。
假设 sample数据很均匀的平铺在总的数据范围内,则会导致采样的节点数过多,甚至不如静态分桶。
假设 部分节点的距离较大,则会导致精度降低。
时间复杂度
写 | O(nlogn) |
读 | O(n) |
注:实现时,需要维护一个buffer,当buffer满时需要做排序,所以写的成本按照最慢的来算,就是nlogn
空间占用
空间不固定,并且由于有merge,会有一定的gc成本
GK算法的升级版本,prometheus 的 summary 就用的该算法实现
它引入了一个可配置的错误率的概念,从而解决了GK 精度不可控问题。
GK 的桶的大小是根据 sample之间的距离delta 决定的,而 CKMS 在抉择是否开辟新桶,则是根据用户设置的错误率。
delta = 错误率 x 总体sample个数,并以此决定分桶的大小。
下图是一个数据合并的例子
可见,当错误率为0.1时,当size > 10 时,会对range <=1 的进行合并
优点:
不需要预设定统计范围
根据sample的量的范围,大部分情况下较静态分桶节省空间
空间上 完全靠用户参数 错误率 决定,更可控。
缺点:
写成本比静态分桶高
时间复杂度
写 | O(nlogn) |
读 | O(n) |
注:同上,需要维护一个buffer,写时,大部分情况下都是O(1), 触发merge 时由于需要做排序,所以O(nlogn)
空间占用
空间不固定,并且由于有merge,会有一定的gc成本
源码地址:
https://github.com/tdunning/t-digest
t-digest算法,比动态分桶算法更准,但是资源又可控
这是作者自己写的简介
https://mapr.com/blog/some-important-streaming-algorithms-you-should-know-about/
简单描述:
本质上,还是动态分桶,但有以下几个特点
桶的总量在一开始就固定,ckms 并不固定,这样实现可以直接用定长数组,这对gc友好
桶划分函数也更适合于计算分位数场景,众所周知我们更关心 p9999, p999 的精度,对p90, p50 的精度并不太在意。
所以在划分桶的函数上对2边分桶分的更细,对中间划分的更粗
桶的大小随着采样个数的增加而增加。(不这样也就没法保证空间固定了)
桶大小 = f(n) x 当前采样个数
时间复杂度:
写 | O(nlogn) |
读 | O(n) |
注:写时,大部分情况下都是O(1), 触发merge 时排序,导致 O(nlogn)
空间复杂度:
总空间占用固定,对gc影响较小。
最终我们基于以下3种较为可靠的算法做压测,做一个横向比较。
我们的场景,一般用于统计接口的 p99 的耗时。允许几十ms的误差。一般统计的范围为 0 - 6000
由于 CKMS 和 t-digest 的实现并非线程安全,所以对其读写操作时都加了把锁。测试代码在此
这里直接给结果:
w (ops/ms) | r (ops/ms) | gc(次数) | 空间(byte) | |
---|---|---|---|---|
ckms | 0.182 | 3670790 | 4 | 32440 |
hdrhistogram | 6.546 | 43 | 0 | 3352 |
tdigest | 8.733 | 177045 | 0 | 13600 |
从上述结果可见,tdigest 的读写性能相对来说是最好的,但是他的空间占用却很厉害。hdrhistogram 反倒是出乎意料的写性能比tdigest略逊一筹。
仔细看源码会发现tdigest 为了减少gc影响,内部使用了多个固定长度的double数组来实现,
也就是说,假如采样的范围足够大时,tdigest 才能凸显出优势,不然,内存占用有点多。
所以,最终,在我们的场景下,还是选择 hdrhistogram
随机算法论文
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