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 ]   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%
   

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 {return 0;}} else {return 0;}
}

到此，类似于计数排序的方式，通过范围hash桶动态维护了一个个元素所处的bucket_ size，而非整个元素。
hash桶 以map方式实现，本事有序，key-value代表范围，保证相邻的桶的耗时区间不会重叠，从而达到统计的过程中在范围之间是有序的。

这个时候很多同学会有疑惑，返回之间有序，当分位数的某一个指标比如p20落在了一个拥有数万个元素的范围之间。按照当前的计算方式，其实已经无法精确计算p20这样的指标了。之前也说了，rocksdb实现的是工业级的分位数计算，也就是我们通过p99即更高的分位数指标作为系统可用性的评判标准，那当前的分桶算法实现的分位数计算也就能够理解了。

正如我们打印的分桶过程：

[       0,       1 ]     9230   3.422%   3.422% #
(       1,       2 ]   174704  64.771%  68.193% #############
(       2,       3 ]    50114  18.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 ]     1893   0.702%  99.032%
(      15,      22 ]      969   0.359%  99.391%
(      22,      34 ]      708   0.262%  99.653%
(      34,      51 ]      571   0.212%  99.865%
(      51,      76 ]      324   0.120%  99.985%
(      76,     110 ]       35   0.013%  99.998%
(     110,     170 ]        3   0.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 bucketuint64_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%，也是一个概率性的数值。

一些总结 和 相关论文

工业界的实现总是在成本和收益之间进行取舍，最低的成本换来最大的收益。分位数的价值是说能够用最低的计算和存储成本换来系统可用性的评判，从而更有针对性的进行系统优化，从而产生更大的价值。

分位数的工业界算法实现有很多篇可以参考的论文：
1. 随机算法- Random Sampling with a Reservoir
2.静态分桶算法 - HdrHistogram
3.二叉树实现的静态分桶算法 - Medians and Beyond: New Aggregation Techniques
for Sensor Networks
4. 动态分桶 GK算法

欢迎感兴趣的同学一起讨论～