Rocksdb的优秀代码（⼀）--⼯业级分桶算法实现分位数p50,p99,p9999
⽂章⽬录
我们知道⼀个完整的监控系统必须存在p99/p999等分位数指标，作为系统可⽤性的评判标准之⼀。⽽像开源监控系统中做的很不错
的grafana和prometheus⼀定需要⼯业级的分位数算法。
本⽂中涉及到的rocksdb源代码都是基于rocksdb 6.4.6版本
基本概念
所谓分位数(quantile)，⽐如p99，表⽰percent of 99，即99% 的数据⼩于当前p99的指标。使⽤分位数来统计系统的长尾延时，也是系统可⽤性的⼀种衡量指标。
由分位数的基本描述中我们能够看到分位数的结果计算是需要有排序的过程，我们想要知道99%的指标⼩于某⼀个值，即需要针对当前数据集进⾏从⼩到⼤的排序，取到第99%的数据才能拿到p99的指标。
所谓⼯业级 ，由以上针对p99的计算过程我们知道这个过程需要排序，同时肯定也需要占⽤存储空间，当系统吞吐达到数⼗万级更⾼量级，分位数的精确度 和 其计算过程中的空间占⽤ trade off 也需要重点关注。那么⼀个⾼性能，节省空间，以及精确度较⾼的分位数实现算法就需要仔细揣摩。
普通的分位数计算
我们常见的分位数为p50,p99,p999,p9999 ，在计算不同分位数数值的过程⼀般分位三步：
将数据从⼩到⼤排列
确定p 分位数位置
确定p 分位数的具体数值
数据从⼩达到的排序就是我们正常的排序算法。
确定p分位数的位置，⽐如p99，则确定整个数组中99%的那个元素所处的位置，⼀般通过
pos =1+(n -1)* p
为了保证得到的是第99%个元素，将计算时的元素位置前移 并 在最后的结果+1。
确定分位数的具体数值则通过如下公式：
在数据已经完成从⼩到⼤的排列之后，通过如下公式完成计算。
p分位数位置的值 = 位于p分位数取整后位置的值 + （位于p分位数取整下⼀位位置的值 - 位于p分位数取整后位置的值）*（p分位数位置 -p分位数位置取整）
Rocksdb中的应⽤
作为⾼性能单机引擎，rocksdb内部有数量庞⼤的metrics，也有对应的分位数。在单机引擎数⼗万的qps下，针对请求耗时的分位数计算必须满⾜⼯业级需求。既需要较⾼的性能和精确度，⼜需要较少的空间占⽤。
如果按章上⽂普通⽅式的算法完成分位数的计算：
空间占⽤的消耗 ：需要保存所有的指标数据，假如每秒钟产⽣20w的qps，那么就需要保存20w对应的uint64_t 的指标数据。⽽且，rocksdb中指标数⼗甚⾄上百个，每个指标 每秒都需要保存20w的指标数据，这对内存是⼀个巨⼤的消耗。
计算资源的消耗： 因为分位数的获取是由⽤户来指定时间的，也就是在⽤户指定获取分位数之前所有
的指标都需要累加，如果这⼀段累计的时间较长，那么获取的时候进⾏数据全排的计算代价就⾮常⼤了。
接下来我们⼀起看看⼯业级的rocksdb是如何解决以上两⽅⾯的问题的。
rocksdb中的分桶算法结果展⽰
先简单展⽰⼀下rocksdb的⼀秒钟level0 读耗时的分位数统计结果指标：
** Level 0 read latency histogram (micros):
Count: 360578 Average: 2.8989  StdDev: 116.15
Min: 1  Median: 1.6243  Max: 38033
Percentiles: P50: 1.62 P75: 1.95 P99: 3.95 P99.9: 16.61 P99.99: 290.83
------------------------------------------------------
[      0,      1 ]    6994  1.940%  1.940%
(      1,      2 ]  277573  76.980%  78.920% >>>
(      2,      3 ]    70608  19.582%  98.502% ####
(      3,      4 ]    1884  0.522%  99.024%
(      4,      6 ]      454  0.126%  99.150%
(      6,      10 ]    2110  0.585%  99.735%
(      10,      15 ]      507  0.141%  99.876%
(      15,      22 ]      380  0.105%  99.981%
(      22,      34 ]      20  0.006%  99.987%
(      34,      51 ]        6  0.002%  99.988%
(    110,    170 ]        4  0.001%  99.989%
(    170,    250 ]        1  0.000%  99.990%
(    250,    380 ]        3  0.001%  99.991%
(    380,    580 ]        2  0.001%  99.991%
(    580,    870 ]        4  0.001%  99.992%
(    870,    1300 ]        5  0.001%  99.994%
(    1300,    1900 ]        4  0.001%  99.995%
(    1900,    2900 ]        6  0.002%  99.996%
(    2900,    4400 ]        5  0.001%  99.998%
(    9900,  14000 ]        3  0.001%  99.999%
(  14000,  22000 ]        3  0.001%  99.999%
(  22000,  33000 ]        1  0.000% 100.000%
(  33000,  50000 ]        2  0.001% 100.000%
⾮常清晰得看到 各个层级的分位数指标，包括p50,p75,p99,p99.9,p99.99
在Percentiles之下 总共有四列（这⾥将做括号和右⽅括号算作⼀列，是⼀个hash桶）
第⼀列 ： 看作⼀个hash桶，这个hash桶表⽰⼀个耗时区间，单位是us
第⼆列：⼀秒内产⽣的请求耗时命中当前耗时区间的有多少个
第三列：⼀秒内产⽣的请求耗时命中当前耗时区间的个数占总请求个数的百分⽐
第四列：累加之前所有请求的百分⽐
通过hash桶完整得展⽰了 耗时主体命中在了(1,2]us的耗时区间，占了整个耗时⽐例的78.9%。
以上仅仅是L0的⼀个分位数统计，rocksdb为每⼀层都维护了类似这样的耗时桶。同时实际测试过程中，累加每秒的耗时统计结果即上⾯的Count统计， 和实际的每秒的qps进⾏对⽐发现并没有太⼤的差异，也就是这⾥的耗时统计和实际的请求统计接近，且并没有太多的资源消耗。（打开opstions.statistics和关闭这个指标，系统CPU资源的消耗并没有太⼤的差异），也就是说单从rocksdb实现的分位数算法的计算资源消耗⾓度来看已经满⾜⼯业级的标准了。
rocksdb 分桶算法实现
按照我们之前描述的分位数计算的三步来看rocksdb的代码
将数据从⼩到达排列
确定p 分位数位置
计算p 分位数的值
第⼀步，数据从⼩到⼤进⾏排列。在rocksdb中，我们打开statistics选项之后相关的耗时指标会动态增加，也就是分位数计算的数据集是在不断增加且动态变化的。
rocksdb的数据集中元素的增加逻辑如下:
void HistogramStat::Add(uint64_t value){
// This function is designed to be lock free, as it's in the critical path
// of any operation. Each individual value is atomic and the order of updates
// by concurrent threads is tolerable.
const size_t index = bucketMapper.IndexForValue(value);// 通过hash桶计算value所处的耗时范围
assert(index < num_buckets_);
// index 所在的hash桶 bucket_[index]元素个数⾃增
buckets_[index].store(buckets_[index].load(std::memory_order_relaxed)+1,
std::memory_order_relaxed);
uint64_t old_min =min();
if(value < old_min){
min_.store(value, std::memory_order_relaxed);
}
uint64_t old_max =max();
if(value > old_max){
max_.store(value, std::memory_order_relaxed);
}
num_.store(num_.load(std::memory_order_relaxed)+1,
std::memory_order_relaxed);
sum_.store(sum_.load(std::memory_order_relaxed)+ value,
std::memory_order_relaxed);
sum_squares_.store(
sum_squares_.load(std::memory_order_relaxed)+ value * value,
std::memory_order_relaxed);
}
以上添加的过程整体的逻辑如下⼏步
1. 计算该value 代表的耗时 所处hash桶的范围。假如传⼊的是
2.5us, 则该耗时处于上⽂中打印出来的耗时范围(2,3]，返回该范围代表
的索引号
[0,1]6994  1.940%  1.940%
(1,2]27757376.980%78.920% >>>
(2,3]7060819.582%98.502% ####
(3,4]18840.522%99.024%
(4,6]4540.126%99.150%
2. 拿到索引号，更新该hash桶的元素个数。 即bucket_⾃增
3. 更新当前层的当前读耗时其他指标：最⼩值，最⼤值，值的总和，值平⽅的总和
也就是整个添加过程并不会将新的value数据保存下来，⽽是维护该value所处的bucket_⼤⼩，这个bucket_⼀个std::atomic_uint_fast64_t的数组，初始化整个hash桶的过程就已经完成了整个hash桶耗时范围的映射。
其中计算索引的逻辑如下：
主要是通过变量valueIndexMap_来查的，这个变量在HistogramBucketMapper构造函数中进⾏的初始化。是⼀个map类型，key-value代表的是⼀个个已经完成初始化的耗时区间。
在IndexForValue函数中拿着当前耗时数据value 在valueIndexMap_中查到第⼀个⼩于等于(lower_bound)当前指标的索引位置。
size_t HistogramBucketMapper::IndexForValue(const uint64_t value)const{
if(value >= maxBucketValue_){
return bucketValues_.size()-1;
}else if( value >= minBucketValue_ ){
std::map<uint64_t, uint64_t>::const_iterator lowerBound =
valueIndexMap_.lower_bound(value);
if(lowerBound != valueIndexMap_.end()){
return static_cast<size_t>(lowerBound->second);
}else{
return0;
}
}else{
return0;
}
}
到此，类似于计数排序的⽅式，通过范围hash桶动态维护了⼀个个元素所处的bucket_ size，⽽⾮整个元素。
hash桶 以map⽅式实现，本事有序，key-value代表范围，保证相邻的桶的耗时区间不会重叠，从⽽达到统计的过程中在范围之间是有序的。
这个时候很多同学会有疑惑，返回之间有序，当分位数的某⼀个指标⽐如p20落在了⼀个拥有数万个元
素的范围之间。按照当前的计算⽅式，其实已经⽆法精确计算p20这样的指标了。之前也说了，rocksdb实现的是⼯业级的分位数计算，也就是我们通过p99即更⾼的分位数指标作为系统可⽤性的评判标准，那当前的分桶算法实现的分位数计算也就能够理解了。
正如我们打印的分桶过程：
[0,1]9230  3.422%  3.422% #
(1,2]17470464.771%68.193% >>###
(2,3]5011418.580%86.773% ####
源代码大电影(3,4]13030  4.831%91.604% #
(4,6]8827  3.273%94.877% #
(6,10]9314  3.453%98.330% #
(10,15]18930.702%99.032%
(15,22]9690.359%99.391%
(22,34]7080.262%99.653%
(34,51]5710.212%99.865%
(51,76]3240.120%99.985%
(76,110]350.013%99.998%
(110,170]30.001%99.999%
可以看到在更⾼层分桶区间内，命中的指标越来越少，也就是像p999,p9999这样的⾼分位数的统计将更加精确。
当然，也可以有完全精确的计算统计⽅法，那就是需要通过空间以及计算资源来换取精确度了，这个代价并不是⼀个很好的trade off⽅式。rocksdb的分桶同样可以控制精确度，我们可以⼿动调整初始化桶的精度，来让精度区间更⼩。
接下来我们看看后⾯两步：
确定p 分位数的位置
计算p 分位数的值
这两步的实现主要在如下函数中:
通过传⼊分位数指标50, 99，99.9，99.99等来进⾏对应的计算。
double HistogramStat::Percentile(double p)const{
double threshold =num()*(p /100.0);// 分位数所在总请求的位置
uint64_t cumulative_sum =0;
for(unsigned int b =0; b < num_buckets_; b++){
uint64_t bucket_value =bucket_at(b);
cumulative_sum += bucket_value;
if(cumulative_sum >= threshold){// 持续累加bucket_请求数，直到达到分位数所在总请求个数的位置
// Scale linearly within this bucket
uint64_t left_point =(b ==0)?0: bucketMapper.BucketLimit(b-1);
uint64_t right_point = bucketMapper.BucketLimit(b);
uint64_t left_sum = cumulative_sum - bucket_value;
uint64_t right_sum = cumulative_sum;
double pos =0;
uint64_t right_left_diff = right_sum - left_sum;
if(right_left_diff !=0){
pos =(threshold - left_sum)/ right_left_diff;// 计算p 分位数的位置
}
double r = left_point +(right_point - left_point)* pos;// 计算分位数的值
uint64_t cur_min =min();
uint64_t cur_max =max();
if(r < cur_min) r = static_cast<double>(cur_min);
if(r > cur_max) r = static_cast<double>(cur_max);
return r;
}
}
return static_cast<double>(max());
}
以上函数关于分位数位置和值的计算基本和下⾯公式接近：
p分位数位置的值 = 位于p分位数取整后位置的值 + （位于p分位数取整下⼀位位置的值 - 位于p分位数取整后位置的值）*（p分位数位置 -p分位数位置取整）
rocksdb的计算⽅式是通过取分位数所处总请求的位置，该请求所在的hash桶范围内取第pos个位置的指标，作为当前分位数的值。
通过这样图就⽐较清晰的展⽰计算threshold的精确percentile的值了。
left_point hash桶区间左端点
right_point 代表右端点
threshold 代表分位数所处该区间的位置的⽐例（并不是⼀个精确的位置）
left_sum 达到左端点的之前所有hash桶请求总个数
right_sum 达到右端点的之前所有hash桶请求总个数
threshold所在的pos 计算如下：pos = (right_sum - threshold) / (right_sum - left sum)
整个pos代表的值的计算如下：r = left_point + pos * (right_point - left_point) ，即可得到当前hash桶所代表的耗时区间内分位数所处的精确位置，当前这⾥的精确肯定不是100%，也是⼀个概率性的数值。
⼀些总结和相关论⽂
教你如何用CC++做高大上的软件界面
« 上一篇
AutoJs4源代码分享---十大高收益合集
下一篇 »

发表评论