steal_backoff_strategy.h

Go to the documentation of this file.

// BSD 3-Clause License
// Copyright (c) 2024, 🍀☀🌕🌥 🌊
// See the LICENSE file in the project root for full license information.
 
#pragma once
 
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <random>
 
namespace kcenon::thread
{
 
enum class steal_backoff_strategy : std::uint8_t
{
    fixed,           
    linear,          
    exponential,     
    adaptive_jitter  
};
 
struct steal_backoff_config
{
    steal_backoff_strategy strategy = steal_backoff_strategy::exponential;
    std::chrono::microseconds initial_backoff{50};
    std::chrono::microseconds max_backoff{1000};
    double multiplier = 2.0;        
    double jitter_factor = 0.5;     
};
 
class backoff_calculator
{
public:
    explicit backoff_calculator(steal_backoff_config config = {})
        : config_(config)
        , rng_(std::random_device{}())
    {
    }
 
    [[nodiscard]] auto calculate(std::size_t attempt) -> std::chrono::microseconds
    {
        auto delay = calculate_base_delay(attempt);
 
        if (config_.strategy == steal_backoff_strategy::adaptive_jitter)
        {
            delay = apply_jitter(delay);
        }
 
        return cap_delay(delay);
    }
 
    [[nodiscard]] auto get_config() const -> const steal_backoff_config&
    {
        return config_;
    }
 
    void set_config(steal_backoff_config config)
    {
        config_ = config;
    }
 
private:
    [[nodiscard]] auto calculate_base_delay(std::size_t attempt) const
        -> std::chrono::microseconds
    {
        auto initial = static_cast<double>(config_.initial_backoff.count());
        auto max_count = static_cast<double>(config_.max_backoff.count());
 
        switch (config_.strategy)
        {
        case steal_backoff_strategy::fixed:
            return config_.initial_backoff;
 
        case steal_backoff_strategy::linear:
            return std::chrono::microseconds{
                static_cast<std::int64_t>(initial * static_cast<double>(attempt + 1))};
 
        case steal_backoff_strategy::exponential:
        case steal_backoff_strategy::adaptive_jitter:
        {
            // Calculate multiplier^attempt with overflow protection
            double factor = 1.0;
            for (std::size_t i = 0; i < attempt; ++i)
            {
                factor *= config_.multiplier;
                // Early exit if we've exceeded max to avoid unnecessary computation
                if (factor * initial > max_count)
                {
                    return config_.max_backoff;
                }
            }
            return std::chrono::microseconds{
                static_cast<std::int64_t>(initial * factor)};
        }
 
        default:
            return config_.initial_backoff;
        }
    }
 
    [[nodiscard]] auto apply_jitter(std::chrono::microseconds delay)
        -> std::chrono::microseconds
    {
        using rep = std::chrono::microseconds::rep;
        rep base = delay.count();
        rep jitter_range =
            static_cast<rep>(static_cast<double>(base) * config_.jitter_factor);
 
        if (jitter_range <= 0)
        {
            return delay;
        }
 
        std::uniform_int_distribution<rep> dist(-jitter_range, jitter_range);
        rep jittered = base + dist(rng_);
 
        // Ensure we don't go negative
        return std::chrono::microseconds{std::max(rep{1}, jittered)};
    }
 
    [[nodiscard]] auto cap_delay(std::chrono::microseconds delay) const
        -> std::chrono::microseconds
    {
        return std::min(delay, config_.max_backoff);
    }
 
    steal_backoff_config config_;
    std::mt19937_64 rng_;
};
 
constexpr const char* to_string(steal_backoff_strategy strategy)
{
    switch (strategy)
    {
    case steal_backoff_strategy::fixed:
        return "fixed";
    case steal_backoff_strategy::linear:
        return "linear";
    case steal_backoff_strategy::exponential:
        return "exponential";
    case steal_backoff_strategy::adaptive_jitter:
        return "adaptive_jitter";
    default:
        return "unknown";
    }
}
 
} // namespace kcenon::thread