1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #include "monitoring/histogram.h"
11
12 #include <stdio.h>
13 #include <cassert>
14 #include <cinttypes>
15 #include <cmath>
16
17 #include "port/port.h"
18 #include "util/cast_util.h"
19
20 namespace ROCKSDB_NAMESPACE {
21
HistogramBucketMapper()22 HistogramBucketMapper::HistogramBucketMapper() {
23 // If you change this, you also need to change
24 // size of array buckets_ in HistogramImpl
25 bucketValues_ = {1, 2};
26 valueIndexMap_ = {{1, 0}, {2, 1}};
27 double bucket_val = static_cast<double>(bucketValues_.back());
28 while ((bucket_val = 1.5 * bucket_val) <= static_cast<double>(port::kMaxUint64)) {
29 bucketValues_.push_back(static_cast<uint64_t>(bucket_val));
30 // Extracts two most significant digits to make histogram buckets more
31 // human-readable. E.g., 172 becomes 170.
32 uint64_t pow_of_ten = 1;
33 while (bucketValues_.back() / 10 > 10) {
34 bucketValues_.back() /= 10;
35 pow_of_ten *= 10;
36 }
37 bucketValues_.back() *= pow_of_ten;
38 valueIndexMap_[bucketValues_.back()] = bucketValues_.size() - 1;
39 }
40 maxBucketValue_ = bucketValues_.back();
41 minBucketValue_ = bucketValues_.front();
42 }
43
IndexForValue(const uint64_t value) const44 size_t HistogramBucketMapper::IndexForValue(const uint64_t value) const {
45 if (value >= maxBucketValue_) {
46 return bucketValues_.size() - 1;
47 } else if ( value >= minBucketValue_ ) {
48 std::map<uint64_t, uint64_t>::const_iterator lowerBound =
49 valueIndexMap_.lower_bound(value);
50 if (lowerBound != valueIndexMap_.end()) {
51 return static_cast<size_t>(lowerBound->second);
52 } else {
53 return 0;
54 }
55 } else {
56 return 0;
57 }
58 }
59
60 namespace {
61 const HistogramBucketMapper bucketMapper;
62 }
63
HistogramStat()64 HistogramStat::HistogramStat()
65 : num_buckets_(bucketMapper.BucketCount()) {
66 assert(num_buckets_ == sizeof(buckets_) / sizeof(*buckets_));
67 Clear();
68 }
69
Clear()70 void HistogramStat::Clear() {
71 min_.store(bucketMapper.LastValue(), std::memory_order_relaxed);
72 max_.store(0, std::memory_order_relaxed);
73 num_.store(0, std::memory_order_relaxed);
74 sum_.store(0, std::memory_order_relaxed);
75 sum_squares_.store(0, std::memory_order_relaxed);
76 for (unsigned int b = 0; b < num_buckets_; b++) {
77 buckets_[b].store(0, std::memory_order_relaxed);
78 }
79 };
80
Empty() const81 bool HistogramStat::Empty() const { return num() == 0; }
82
Add(uint64_t value)83 void HistogramStat::Add(uint64_t value) {
84 // This function is designed to be lock free, as it's in the critical path
85 // of any operation. Each individual value is atomic and the order of updates
86 // by concurrent threads is tolerable.
87 const size_t index = bucketMapper.IndexForValue(value);
88 assert(index < num_buckets_);
89 buckets_[index].store(buckets_[index].load(std::memory_order_relaxed) + 1,
90 std::memory_order_relaxed);
91
92 uint64_t old_min = min();
93 if (value < old_min) {
94 min_.store(value, std::memory_order_relaxed);
95 }
96
97 uint64_t old_max = max();
98 if (value > old_max) {
99 max_.store(value, std::memory_order_relaxed);
100 }
101
102 num_.store(num_.load(std::memory_order_relaxed) + 1,
103 std::memory_order_relaxed);
104 sum_.store(sum_.load(std::memory_order_relaxed) + value,
105 std::memory_order_relaxed);
106 sum_squares_.store(
107 sum_squares_.load(std::memory_order_relaxed) + value * value,
108 std::memory_order_relaxed);
109 }
110
Merge(const HistogramStat & other)111 void HistogramStat::Merge(const HistogramStat& other) {
112 // This function needs to be performned with the outer lock acquired
113 // However, atomic operation on every member is still need, since Add()
114 // requires no lock and value update can still happen concurrently
115 uint64_t old_min = min();
116 uint64_t other_min = other.min();
117 while (other_min < old_min &&
118 !min_.compare_exchange_weak(old_min, other_min)) {}
119
120 uint64_t old_max = max();
121 uint64_t other_max = other.max();
122 while (other_max > old_max &&
123 !max_.compare_exchange_weak(old_max, other_max)) {}
124
125 num_.fetch_add(other.num(), std::memory_order_relaxed);
126 sum_.fetch_add(other.sum(), std::memory_order_relaxed);
127 sum_squares_.fetch_add(other.sum_squares(), std::memory_order_relaxed);
128 for (unsigned int b = 0; b < num_buckets_; b++) {
129 buckets_[b].fetch_add(other.bucket_at(b), std::memory_order_relaxed);
130 }
131 }
132
Median() const133 double HistogramStat::Median() const {
134 return Percentile(50.0);
135 }
136
Percentile(double p) const137 double HistogramStat::Percentile(double p) const {
138 double threshold = num() * (p / 100.0);
139 uint64_t cumulative_sum = 0;
140 for (unsigned int b = 0; b < num_buckets_; b++) {
141 uint64_t bucket_value = bucket_at(b);
142 cumulative_sum += bucket_value;
143 if (cumulative_sum >= threshold) {
144 // Scale linearly within this bucket
145 uint64_t left_point = (b == 0) ? 0 : bucketMapper.BucketLimit(b-1);
146 uint64_t right_point = bucketMapper.BucketLimit(b);
147 uint64_t left_sum = cumulative_sum - bucket_value;
148 uint64_t right_sum = cumulative_sum;
149 double pos = 0;
150 uint64_t right_left_diff = right_sum - left_sum;
151 if (right_left_diff != 0) {
152 pos = (threshold - left_sum) / right_left_diff;
153 }
154 double r = left_point + (right_point - left_point) * pos;
155 uint64_t cur_min = min();
156 uint64_t cur_max = max();
157 if (r < cur_min) r = static_cast<double>(cur_min);
158 if (r > cur_max) r = static_cast<double>(cur_max);
159 return r;
160 }
161 }
162 return static_cast<double>(max());
163 }
164
Average() const165 double HistogramStat::Average() const {
166 uint64_t cur_num = num();
167 uint64_t cur_sum = sum();
168 if (cur_num == 0) return 0;
169 return static_cast<double>(cur_sum) / static_cast<double>(cur_num);
170 }
171
StandardDeviation() const172 double HistogramStat::StandardDeviation() const {
173 uint64_t cur_num = num();
174 uint64_t cur_sum = sum();
175 uint64_t cur_sum_squares = sum_squares();
176 if (cur_num == 0) return 0;
177 double variance =
178 static_cast<double>(cur_sum_squares * cur_num - cur_sum * cur_sum) /
179 static_cast<double>(cur_num * cur_num);
180 return std::sqrt(variance);
181 }
ToString() const182 std::string HistogramStat::ToString() const {
183 uint64_t cur_num = num();
184 std::string r;
185 char buf[1650];
186 snprintf(buf, sizeof(buf),
187 "Count: %" PRIu64 " Average: %.4f StdDev: %.2f\n",
188 cur_num, Average(), StandardDeviation());
189 r.append(buf);
190 snprintf(buf, sizeof(buf),
191 "Min: %" PRIu64 " Median: %.4f Max: %" PRIu64 "\n",
192 (cur_num == 0 ? 0 : min()), Median(), (cur_num == 0 ? 0 : max()));
193 r.append(buf);
194 snprintf(buf, sizeof(buf),
195 "Percentiles: "
196 "P50: %.2f P75: %.2f P99: %.2f P99.9: %.2f P99.99: %.2f\n",
197 Percentile(50), Percentile(75), Percentile(99), Percentile(99.9),
198 Percentile(99.99));
199 r.append(buf);
200 r.append("------------------------------------------------------\n");
201 if (cur_num == 0) return r; // all buckets are empty
202 const double mult = 100.0 / cur_num;
203 uint64_t cumulative_sum = 0;
204 for (unsigned int b = 0; b < num_buckets_; b++) {
205 uint64_t bucket_value = bucket_at(b);
206 if (bucket_value <= 0.0) continue;
207 cumulative_sum += bucket_value;
208 snprintf(buf, sizeof(buf),
209 "%c %7" PRIu64 ", %7" PRIu64 " ] %8" PRIu64 " %7.3f%% %7.3f%% ",
210 (b == 0) ? '[' : '(',
211 (b == 0) ? 0 : bucketMapper.BucketLimit(b-1), // left
212 bucketMapper.BucketLimit(b), // right
213 bucket_value, // count
214 (mult * bucket_value), // percentage
215 (mult * cumulative_sum)); // cumulative percentage
216 r.append(buf);
217
218 // Add hash marks based on percentage; 20 marks for 100%.
219 size_t marks = static_cast<size_t>(mult * bucket_value / 5 + 0.5);
220 r.append(marks, '#');
221 r.push_back('\n');
222 }
223 return r;
224 }
225
Data(HistogramData * const data) const226 void HistogramStat::Data(HistogramData * const data) const {
227 assert(data);
228 data->median = Median();
229 data->percentile95 = Percentile(95);
230 data->percentile99 = Percentile(99);
231 data->max = static_cast<double>(max());
232 data->average = Average();
233 data->standard_deviation = StandardDeviation();
234 data->count = num();
235 data->sum = sum();
236 data->min = static_cast<double>(min());
237 }
238
Clear()239 void HistogramImpl::Clear() {
240 std::lock_guard<std::mutex> lock(mutex_);
241 stats_.Clear();
242 }
243
Empty() const244 bool HistogramImpl::Empty() const {
245 return stats_.Empty();
246 }
247
Add(uint64_t value)248 void HistogramImpl::Add(uint64_t value) {
249 stats_.Add(value);
250 }
251
Merge(const Histogram & other)252 void HistogramImpl::Merge(const Histogram& other) {
253 if (strcmp(Name(), other.Name()) == 0) {
254 Merge(
255 *static_cast_with_check<const HistogramImpl, const Histogram>(&other));
256 }
257 }
258
Merge(const HistogramImpl & other)259 void HistogramImpl::Merge(const HistogramImpl& other) {
260 std::lock_guard<std::mutex> lock(mutex_);
261 stats_.Merge(other.stats_);
262 }
263
Median() const264 double HistogramImpl::Median() const {
265 return stats_.Median();
266 }
267
Percentile(double p) const268 double HistogramImpl::Percentile(double p) const {
269 return stats_.Percentile(p);
270 }
271
Average() const272 double HistogramImpl::Average() const {
273 return stats_.Average();
274 }
275
StandardDeviation() const276 double HistogramImpl::StandardDeviation() const {
277 return stats_.StandardDeviation();
278 }
279
ToString() const280 std::string HistogramImpl::ToString() const {
281 return stats_.ToString();
282 }
283
Data(HistogramData * const data) const284 void HistogramImpl::Data(HistogramData * const data) const {
285 stats_.Data(data);
286 }
287
288 } // namespace ROCKSDB_NAMESPACE
289