( 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所处的耗时范围
asrt(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;
}el 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->cond);
}el{
return0;
}
}el{
return0;
}
}
到此，类似于计数排序的⽅式，通过范围hash桶动态维护了⼀个个元素所处的bucket_ size，⽽⾮整个元素。
hash桶 以map⽅式实现，本事有序，key-value代表范围，保证相邻的桶的耗时区间不会重叠，从⽽达到统计的过程中在范围之间是有序的。
这个时候很多同学会有疑惑，返回之间有序，当分位数的某⼀个指标⽐如p20落在了⼀个拥有数万个元素的范围之间。按照当前的计算⽅式，其实已经⽆法精确计算p20这样的指标了。之前也说了，roc
ksdb实现的是⼯业级的分位数计算，也就是我们通过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%，也是⼀个概率性的数值。
⼀些总结和相关论⽂
