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 stores M buckets of type Counter and allows easy
18 * calculation of percentiles.
19 *
20 * Bucket X stores how many elements with value X was accounted for, for the
21 * first M buckets. Bucket X stores how many elements with values
22 * [X-ExtraBucketSize/2; X+ExtraBucketSize/2) were accounted for, for the next
23 * ExtraBuckets buckets.
24 *
25 * @tparam M how many buckets store precise value
26 * @tparam Counter bucket type
27 * @tparam ExtraBuckets how many buckets store approximated values
28 * @tparam ExtraBucketSize ExtraBuckets store values with this precision
29 * @see GetPercentile
30 * @see Account
31 *
32 * Example:
33 * Precisely count for first 500 milliseconds of execution using uint32_t
34 * counters and leave 100 buckets for all the other values with precision
35 * of 42 milliseconds:
36 *
37 * @code
38 * using Percentile =
39 * utils::statistics::Percentile<500, std::uint32_t, 100, 42>;
40 *
41 * void Account(Percentile& perc, std::chrono::milliseconds ms) {
42 * perc.Account(ms.count());
43 * }
44 *
45 * formats::json::Value ExtendStatistics(
46 * formats::json::ValueBuilder& stats_builder, Percentile& perc) {
47 *
48 * stats_builder["timings"]["1min"] = PercentileToJson(perc).ExtractValue();
49 *
50 * return stats_builder.ExtractValue();
51 * }
52 * @endcode
53 */
54template <size_t M, typename Counter = uint32_t, size_t ExtraBuckets = 0,
55 size_t ExtraBucketSize = 500>
56class Percentile final {
57 public:
58 Percentile() {
59 for (auto& value : values_) value.store(0, std::memory_order_relaxed);
60 for (auto& value : extra_values_) value.store(0, std::memory_order_relaxed);
61 count_.store(0, std::memory_order_release);
62 }
63
64 Percentile(const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>&
65 other) noexcept {
66 *this = other;
67 }
68
69 Percentile& operator=(const Percentile& rhs) noexcept {
70 if (this == &rhs) return *this;
71
72 size_t sum = 0;
73 for (size_t i = 0; i < values_.size(); i++) {
74 const auto value = rhs.values_[i].load(std::memory_order_relaxed);
75 values_[i].store(value, std::memory_order_relaxed);
76 sum += value;
77 }
78
79 for (size_t i = 0; i < extra_values_.size(); i++) {
80 const auto value = rhs.extra_values_[i].load(std::memory_order_relaxed);
81 extra_values_[i].store(value, std::memory_order_relaxed);
82 sum += value;
83 }
84 count_ = sum;
85 return *this;
86 }
87
88 /** \brief Account for another value. Value is truncated [0..M) and
89 * added to the corresponding bucket
90 */
91 void Account(size_t value) {
92 if (value < values_.size()) {
93 values_[value].fetch_add(1, std::memory_order_relaxed);
94 } else {
95 if (!extra_values_.empty()) {
96 size_t extra_bucket =
97 (value - values_.size() + ExtraBucketSize / 2) / ExtraBucketSize;
98 if (extra_bucket >= extra_values_.size()) {
99 extra_bucket = extra_values_.size() - 1;
100 }
101 extra_values_[extra_bucket].fetch_add(1, std::memory_order_relaxed);
102 } else {
103 values_.back().fetch_add(1, std::memory_order_relaxed);
104 }
105 }
106 count_.fetch_add(1, std::memory_order_release);
107 }
108
109 /** \brief Get X percentile - min value P in [0..M) so that total number
110 * of elements in buckets 0..P is no less than X percent
111 * @param percent - value in [0..100] - requested percentile
112 * if outside of 100, then returns last bucket that
113 * has any element in it.
114 */
116 if (count_ == 0) return 0;
117
118 size_t sum = 0;
119 size_t want_sum = count_.load(std::memory_order_acquire) * percent;
120 size_t max_value = 0;
121 for (size_t i = 0; i < values_.size(); i++) {
122 const auto value = values_[i].load(std::memory_order_relaxed);
123 sum += value;
124 if (sum * 100 > want_sum) return i;
125
126 if (value) max_value = i;
127 }
128
129 for (size_t i = 0; i < extra_values_.size(); i++) {
130 const auto value = extra_values_[i].load(std::memory_order_relaxed);
131 sum += value;
132 if (sum * 100 > want_sum) return ExtraBucketToValue(i);
133
134 if (value) max_value = ExtraBucketToValue(i);
135 }
136
137 return max_value;
138 }
139
140 template <class Duration = std::chrono::seconds>
141 void Add(const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& other,
142 [[maybe_unused]] Duration this_epoch_duration = Duration(),
143 [[maybe_unused]] Duration before_this_epoch_duration = Duration()) {
144 size_t sum = 0;
145 for (size_t i = 0; i < values_.size(); i++) {
146 const auto value = other.values_[i].load(std::memory_order_relaxed);
147 sum += value;
148 values_[i].fetch_add(value, std::memory_order_relaxed);
149 }
150
151 for (size_t i = 0; i < extra_values_.size(); i++) {
152 const auto value = other.extra_values_[i].load(std::memory_order_relaxed);
153 sum += value;
154 extra_values_[i].fetch_add(value, std::memory_order_relaxed);
155 }
156 count_.fetch_add(sum, std::memory_order_release);
157 }
158
159 void Reset() {
160 for (auto& value : values_) value.store(0, std::memory_order_relaxed);
161 for (auto& value : extra_values_) value.store(0, std::memory_order_relaxed);
162 count_ = 0;
163 }
164
165 /** \brief Total number of elements
166 */
167 Counter Count() const { return count_; }
168
169 private:
170 size_t ExtraBucketToValue(size_t bucket) const {
171 return values_.size() + bucket * ExtraBucketSize;
172 }
173
174 std::array<std::atomic<Counter>, M> values_;
175 std::array<std::atomic<Counter>, ExtraBuckets> extra_values_;
176 std::atomic<Counter> count_;
177};
178
179std::string GetPercentileFieldName(double perc);
180
181template <size_t M, typename Counter, size_t ExtraBuckets,
182 size_t ExtraBucketSize>
183void DumpMetric(
184 Writer& writer,
185 const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& perc,
186 std::initializer_list<double> percents = {0, 50, 90, 95, 98, 99, 99.6, 99.9,
187 100}) {
188 for (double percent : percents) {
189 writer.ValueWithLabels(
190 perc.GetPercentile(percent),
191 {"percentile", statistics::GetPercentileFieldName(percent)});
192 }
193}
194
195} // namespace utils::statistics
196
197USERVER_NAMESPACE_END