userver: userver/utils/statistics/percentile.hpp Source File
⚠️ This is the documentation for an old userver version. Click here to switch to the latest version.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
percentile.hpp
Go to the documentation of this file.
1#pragma once
2
3/// @file userver/utils/statistics/percentile.hpp
4/// @brief @copybrief utils::statistics::Percentile
5
6#include <array>
7#include <atomic>
8#include <chrono>
9#include <string>
10
11#include <userver/utils/statistics/writer.hpp>
12
13USERVER_NAMESPACE_BEGIN
14
15namespace utils::statistics {
16
17/** @brief Class allows easy calculation of percentiles.
18 *
19 * Stores `M + ExtraBuckets` buckets of type `Counter`.
20 *
21 * On `Account(x)` the bucket to increment is chosen depending on `x` value.
22 * If `x` belongs to:
23 *
24 * - `[0, M)`, then bucket from `M` buckets;
25 * - `[M, M + ExtraBuckets * ExtraBucketSize)`, then bucket from `ExtraBuckets`;
26 * - all the bigger values, then last bucket from `ExtraBuckets`.
27 *
28 * On `GetPercentile(percent)` class sums up the required amount of buckets,
29 * knowing the total count of `Account(x)` invocations.
30 *
31 * @tparam M buckets count for value step of `1`
32 * @tparam Counter type of all the buckets
33 * @tparam ExtraBuckets buckets for value step of `ExtraBucketSize`
34 * @tparam ExtraBucketSize `ExtraBuckets` store values with this precision
35 * @see GetPercentile
36 * @see Account
37 *
38 * @b Example:
39 * Precisely count for first 500 milliseconds of execution using `std::uint32_t`
40 * counters and leave 100 buckets for all the other values with precision
41 * of 9 milliseconds:
42 *
43 * @code
44 * using Percentile = utils::statistics::Percentile<500, std::uint32_t, 100, 9>;
45 * using Timings = utils::statistics::RecentPeriod<Percentile, Percentile>;
46 *
47 * void Account(Percentile& perc, std::chrono::milliseconds ms) {
48 * perc.Account(ms.count());
49 * }
50 *
51 * void ExtendStatistics(utils::statistics::Writer& writer, Timings& timings) {
52 * writer["timings"]["1min"] = timings;
53 * }
54 * @endcode
55 *
56 * Type is safe to read/write concurrently from different threads/coroutines.
57 *
58 * `Percentile` metrics are non-summable, e.g. given RPS counts and timing
59 * percentiles for multiple hosts or handlers, we cannot accurately compute the
60 * total timing percentiles.
61 *
62 * @see utils::statistics::Histogram for the summable equivalent
63 */
64template <std::size_t M, typename Counter = std::uint32_t,
65 std::size_t ExtraBuckets = 0, std::size_t ExtraBucketSize = 500>
66class Percentile final {
67 public:
68 Percentile() noexcept {
69 for (auto& value : values_) value.store(0, std::memory_order_relaxed);
70 for (auto& value : extra_values_) value.store(0, std::memory_order_relaxed);
71 count_.store(0, std::memory_order_release);
72 }
73
74 Percentile(const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>&
75 other) noexcept {
76 *this = other;
77 }
78
79 Percentile& operator=(const Percentile& rhs) noexcept {
80 if (this == &rhs) return *this;
81
82 std::size_t sum = 0;
83 for (std::size_t i = 0; i < values_.size(); i++) {
84 const auto value = rhs.values_[i].load(std::memory_order_relaxed);
85 values_[i].store(value, std::memory_order_relaxed);
86 sum += value;
87 }
88
89 for (std::size_t i = 0; i < extra_values_.size(); i++) {
90 const auto value = rhs.extra_values_[i].load(std::memory_order_relaxed);
91 extra_values_[i].store(value, std::memory_order_relaxed);
92 sum += value;
93 }
94
95 count_ = sum;
96 return *this;
97 }
98
99 /// @brief Account for another value.
100 ///
101 /// `1` is added to the bucket corresponding to `value`
102 void Account(std::size_t value) noexcept {
103 if (value < values_.size()) {
104 values_[value].fetch_add(1, std::memory_order_relaxed);
105 } else {
106 if (!extra_values_.empty()) {
107 std::size_t extra_bucket =
108 (value - values_.size() + ExtraBucketSize / 2) / ExtraBucketSize;
109 if (extra_bucket >= extra_values_.size()) {
110 extra_bucket = extra_values_.size() - 1;
111 }
112 extra_values_[extra_bucket].fetch_add(1, std::memory_order_relaxed);
113 } else {
114 values_.back().fetch_add(1, std::memory_order_relaxed);
115 }
116 }
117 count_.fetch_add(1, std::memory_order_release);
118 }
119
120 /// @brief Get X percentile - min value P so that total number
121 /// of elements in buckets is no less than X percent.
122 ///
123 /// @param percent - value in [0..100] - requested percentile.
124 /// If outside of 100, then returns last bucket that has any element in it.
125 std::size_t GetPercentile(double percent) const {
126 if (count_ == 0) return 0;
127
128 std::size_t sum = 0;
129 std::size_t want_sum = count_.load(std::memory_order_acquire) * percent;
130 std::size_t max_value = 0;
131 for (std::size_t i = 0; i < values_.size(); i++) {
132 const auto value = values_[i].load(std::memory_order_relaxed);
133 sum += value;
134 if (sum * 100 > want_sum) return i;
135
136 if (value) max_value = i;
137 }
138
139 for (size_t i = 0; i < extra_values_.size(); i++) {
140 const auto value = extra_values_[i].load(std::memory_order_relaxed);
141 sum += value;
142 if (sum * 100 > want_sum) return ExtraBucketToValue(i);
143
144 if (value) max_value = ExtraBucketToValue(i);
145 }
146
147 return max_value;
148 }
149
150 template <class Duration = std::chrono::seconds>
151 void Add(const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& other,
152 [[maybe_unused]] Duration this_epoch_duration = Duration(),
153 [[maybe_unused]] Duration before_this_epoch_duration = Duration()) {
154 size_t sum = 0;
155 for (size_t i = 0; i < values_.size(); i++) {
156 const auto value = other.values_[i].load(std::memory_order_relaxed);
157 sum += value;
158 values_[i].fetch_add(value, std::memory_order_relaxed);
159 }
160
161 for (size_t i = 0; i < extra_values_.size(); i++) {
162 const auto value = other.extra_values_[i].load(std::memory_order_relaxed);
163 sum += value;
164 extra_values_[i].fetch_add(value, std::memory_order_relaxed);
165 }
166 count_.fetch_add(sum, std::memory_order_release);
167 }
168
169 /// @brief Zero out all the buckets and total number of elements.
170 void Reset() noexcept {
171 for (auto& value : values_) value.store(0, std::memory_order_relaxed);
172 for (auto& value : extra_values_) value.store(0, std::memory_order_relaxed);
173 count_ = 0;
174 }
175
176 /// @brief Total number of elements
177 Counter Count() const noexcept { return count_; }
178
179 private:
180 size_t ExtraBucketToValue(std::size_t bucket) const noexcept {
181 return values_.size() + bucket * ExtraBucketSize;
182 }
183
184 static_assert(std::atomic<Counter>::is_always_lock_free,
185 "`std::atomic<Counter>` is not lock-free. Please choose some "
186 "other `Counter` type");
187
188 std::array<std::atomic<Counter>, M> values_;
189 std::array<std::atomic<Counter>, ExtraBuckets> extra_values_;
190 std::atomic<Counter> count_;
191};
192
193std::string GetPercentileFieldName(double perc);
194
195template <size_t M, typename Counter, size_t ExtraBuckets,
196 size_t ExtraBucketSize>
197void DumpMetric(
198 Writer& writer,
199 const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& perc,
200 std::initializer_list<double> percents = {0, 50, 90, 95, 98, 99, 99.6, 99.9,
201 100}) {
202 for (double percent : percents) {
203 writer.ValueWithLabels(
204 perc.GetPercentile(percent),
205 {"percentile", statistics::GetPercentileFieldName(percent)});
206 }
207}
208
209} // namespace utils::statistics
210
211USERVER_NAMESPACE_END