1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
use core::cell::UnsafeCell;
const FACTOR: f64 = 1.5;
#[derive(Debug)]
pub struct PerCpuLogHistogram {
buckets: Vec<UnsafeCell<u64>>,
}
impl PerCpuLogHistogram {
pub fn buckets(&self) -> &[UnsafeCell<u64>] {
&self.buckets
}
#[inline]
pub fn record(&self, us: u64) {
let idx = (us as f64).log(FACTOR) as usize;
let idx = idx.min(self.buckets.len() - 1);
unsafe { *self.buckets[idx].get() += 1 };
}
}
impl Default for PerCpuLogHistogram {
fn default() -> Self {
let mut buckets = Vec::new();
let max = 60000000.0; // 60s
let mut curr = 1.0;
loop {
if curr >= max {
break;
}
buckets.push(UnsafeCell::new(0));
curr *= FACTOR;
}
Self { buckets }
}
}
#[derive(Debug)]
pub struct LogHistogram {
snapshot: Vec<u64>,
}
impl LogHistogram {
#[inline]
pub const fn new(snapshot: Vec<u64>) -> Self {
Self { snapshot }
}
/// Calculates the quantile.
///
/// Suppose we have the following histogram, in linear coordinates:
/// +---+------+--------+----------------+-----------+
/// | i | b[i] | sum[i] | Duration range | Histogram |
/// +---+------+--------+----------------+-----------+
/// | 0 | 2 | 2 | [0; f^0) | ** |
/// | 1 | 1 | 3 | [f^0; f^1) | * |
/// | 2 | 9 | 12 | [f^1; f^2) | ********* |
/// | 3 | 4 | 16 | [f^2; f^3) | **** |
/// | 4 | 3 | 19 | [f^3; f^4) | *** |
/// | 5 | 0 | 19 | [f^4; f^5) | |
/// | 6 | 1 | 20 | [f^5; f^6) | * |
/// | . | .... | ...... | .......... | |
/// | N | 4 | 1000 | [f^(N-1); Inf | **** |
/// +---+------+--------+----------------+-----------+
///
/// For given quantile "q" have to find the first index "i",
/// where sum[i] + b[i] >= q * sum[N].
/// Thus, we can guarantee that sum[i] requests are under the given
/// quantile.
/// So we can return the corresponding duration range upper
/// bound: "f^i".
/// But we can go further and improve our result by performing linear
/// interpolation in logarithmic coordinates by base "f":
///
/// | o sum[i+1]
/// | /|
/// | / |
/// | x |
/// | /^--|-- q * sum[N]
/// | / | |
/// | / | |
/// | / | |
/// |/ | |
/// o sum[i] |
/// | | |
/// i x i+1
///
/// Let's build two linear equations with known boundary conditions:
///
/// sum[i] = k * i + c
/// sum[i+1] = k * (i+1) + c
///
/// Solve them, find "k" and "c":
///
/// c = sum[i] - k * i
/// sum[i+1] = k * (i+1) + (sum[i] - k * i)
/// k = (sum[i+1] - sum[i]) / ((i+1)-i)
/// k = (sum[i+1] - sum[i])
/// k = (sum[i] + b[i] - sum[i])
/// k = b[i]
///
/// Then, find the desired pseudo-index "x":
///
/// q * sum[N] = b[i] * x + (sum[i] - b[i] * i)
/// x = (q * sum[N] - (sum[i] - b[i] * i)) / b[i]
///
/// The result will be "f^x", because we need to return from logarithmic
/// coordinates to normal.
pub fn quantile(&self, q: f64) -> u64 {
assert!((0.0..=1.0).contains(&q));
let size: u64 = self.snapshot.iter().sum();
let mut sum = 0;
for (idx, &b) in self.snapshot.iter().enumerate() {
if ((sum + b) as f64) >= q * (size as f64) {
// Found upper bound, let's interpolate now.
let idx = idx as f64;
let b = b as f64;
let sum = sum as f64;
let size = size as f64;
let c_inv = |q: f64| FACTOR.powf((q * size - sum) / b + idx);
return c_inv(q) as u64;
}
sum += b;
}
u64::MAX
}
}