percentile.hpp

Go to the documentation of this file.

#pragma once
 
/// @file userver/utils/statistics/percentile.hpp
/// @brief @copybrief utils::statistics::Percentile
 
#include <array>
#include <atomic>
#include <chrono>
#include <string>
 
#include <userver/utils/statistics/writer.hpp>
 
USERVER_NAMESPACE_BEGIN
 
namespace utils::statistics {
 
/** @brief Class allows easy calculation of percentiles.
 *
 * Stores `M + ExtraBuckets` buckets of type `Counter`.
 *
 * On `Account(x)` the bucket to increment is chosen depending on `x` value.
 * If `x` belongs to:
 *
 * - `[0, M)`, then bucket from `M` buckets;
 * - `[M, M + ExtraBuckets * ExtraBucketSize)`, then bucket from `ExtraBuckets`;
 * - all the bigger values, then last bucket from `ExtraBuckets`.
 *
 * On `GetPercentile(percent)` class sums up the required amount of buckets,
 * knowing the total count of `Account(x)` invocations.
 *
 * @tparam M buckets count for value step of `1`
 * @tparam Counter type of all the buckets
 * @tparam ExtraBuckets buckets for value step of `ExtraBucketSize`
 * @tparam ExtraBucketSize `ExtraBuckets` store values with this precision
 * @see GetPercentile
 * @see Account
 *
 * @b Example:
 * Precisely count for first 500 milliseconds of execution using `std::uint32_t`
 * counters and leave 100 buckets for all the other values with precision
 * of 9 milliseconds:
 *
 * @code
 * using Percentile = utils::statistics::Percentile<500, std::uint32_t, 100, 9>;
 * using Timings = utils::statistics::RecentPeriod<Percentile, Percentile>;
 *
 * void Account(Percentile& perc, std::chrono::milliseconds ms) {
 *   perc.Account(ms.count());
 * }
 *
 * void ExtendStatistics(utils::statistics::Writer& writer, Timings& timings) {
 *   writer["timings"]["1min"] = timings;
 * }
 * @endcode
 *
 * Type is safe to read/write concurrently from different threads/coroutines.
 *
 * `Percentile` metrics are non-summable, e.g. given RPS counts and timing
 * percentiles for multiple hosts or handlers, we cannot accurately compute the
 * total timing percentiles.
 *
 * @see utils::statistics::Histogram for the summable equivalent
 */
template <
    std::size_t M,
    typename Counter = std::uint32_t,
    std::size_t ExtraBuckets = 0,
    std::size_t ExtraBucketSize = 500>
class Percentile final {
public:
    Percentile() noexcept {
        for (auto& value : values_) {
            value.store(0, std::memory_order_relaxed);
        }
        for (auto& value : extra_values_) {
            value.store(0, std::memory_order_relaxed);
        }
        count_.store(0, std::memory_order_release);
    }
 
    Percentile(const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& other) noexcept { *this = other; }
 
    Percentile& operator=(const Percentile& rhs) noexcept {
        if (this == &rhs) {
            return *this;
        }
 
        std::size_t sum = 0;
        for (std::size_t i = 0; i < values_.size(); i++) {
            const auto value = rhs.values_[i].load(std::memory_order_relaxed);
            values_[i].store(value, std::memory_order_relaxed);
            sum += value;
        }
 
        for (std::size_t i = 0; i < extra_values_.size(); i++) {
            const auto value = rhs.extra_values_[i].load(std::memory_order_relaxed);
            extra_values_[i].store(value, std::memory_order_relaxed);
            sum += value;
        }
 
        count_ = sum;
        return *this;
    }
 
    /// @brief Account for another value.
    ///
    /// `1` is added to the bucket corresponding to `value`
    void Account(std::size_t value) noexcept {
        if (value < values_.size()) {
            values_[value].fetch_add(1, std::memory_order_relaxed);
        } else {
            if (!extra_values_.empty()) {
                std::size_t extra_bucket = (value - values_.size() + ExtraBucketSize / 2) / ExtraBucketSize;
                if (extra_bucket >= extra_values_.size()) {
                    extra_bucket = extra_values_.size() - 1;
                }
                extra_values_[extra_bucket].fetch_add(1, std::memory_order_relaxed);
            } else {
                values_.back().fetch_add(1, std::memory_order_relaxed);
            }
        }
        count_.fetch_add(1, std::memory_order_release);
    }
 
    /// @brief Get X percentile - min value P so that total number
    /// of elements in buckets is no less than X percent.
    ///
    /// @param percent - value in [0..100] - requested percentile.
    /// If outside of 100, then returns last bucket that has any element in it.
    std::size_t GetPercentile(double percent) const {
        if (count_ == 0) {
            return 0;
        }
 
        std::size_t sum = 0;
        const std::size_t want_sum = count_.load(std::memory_order_acquire) * percent;
        std::size_t max_value = 0;
        for (std::size_t i = 0; i < values_.size(); i++) {
            const auto value = values_[i].load(std::memory_order_relaxed);
            sum += value;
            if (sum * 100 > want_sum) {
                return i;
            }
 
            if (value) {
                max_value = i;
            }
        }
 
        for (size_t i = 0; i < extra_values_.size(); i++) {
            const auto value = extra_values_[i].load(std::memory_order_relaxed);
            sum += value;
            if (sum * 100 > want_sum) {
                return ExtraBucketToValue(i);
            }
 
            if (value) {
                max_value = ExtraBucketToValue(i);
            }
        }
 
        return max_value;
    }
 
    template <class Duration = std::chrono::seconds>
    void Add(
        const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& other,
        [[maybe_unused]] Duration this_epoch_duration = Duration(),
        [[maybe_unused]] Duration before_this_epoch_duration = Duration()
    ) {
        size_t sum = 0;
        for (size_t i = 0; i < values_.size(); i++) {
            const auto value = other.values_[i].load(std::memory_order_relaxed);
            sum += value;
            values_[i].fetch_add(value, std::memory_order_relaxed);
        }
 
        for (size_t i = 0; i < extra_values_.size(); i++) {
            const auto value = other.extra_values_[i].load(std::memory_order_relaxed);
            sum += value;
            extra_values_[i].fetch_add(value, std::memory_order_relaxed);
        }
        count_.fetch_add(sum, std::memory_order_release);
    }
 
    /// @brief Zero out all the buckets and total number of elements.
    void Reset() noexcept {
        for (auto& value : values_) {
            value.store(0, std::memory_order_relaxed);
        }
        for (auto& value : extra_values_) {
            value.store(0, std::memory_order_relaxed);
        }
        count_ = 0;
    }
 
    /// @brief Total number of elements
    Counter Count() const noexcept { return count_; }
 
private:
    size_t ExtraBucketToValue(std::size_t bucket) const noexcept { return values_.size() + bucket * ExtraBucketSize; }
 
    static_assert(
        std::atomic<Counter>::is_always_lock_free,
        "`std::atomic<Counter>` is not lock-free. Please choose some "
        "other `Counter` type"
    );
 
    std::array<std::atomic<Counter>, M> values_;
    std::array<std::atomic<Counter>, ExtraBuckets> extra_values_;
    std::atomic<Counter> count_;
};
 
std::string GetPercentileFieldName(double perc);
 
template <size_t M, typename Counter, size_t ExtraBuckets, size_t ExtraBucketSize>
void DumpMetric(
    Writer& writer,
    const Percentile<M, Counter, ExtraBuckets, ExtraBucketSize>& perc,
    std::initializer_list<double> percents = {0, 50, 90, 95, 98, 99, 99.6, 99.9, 100}
) {
    for (const double percent : percents) {
        writer
            .ValueWithLabels(perc.GetPercentile(percent), {"percentile", statistics::GetPercentileFieldName(percent)});
    }
}
 
}  // namespace utils::statistics
 
USERVER_NAMESPACE_END