使用令牌桶来限制函数调用

Question

这个程序是我解决以下问题的尝试：

我们有一个函数，它将被多个线程调用。问题在于找到一种方法来限制该函数每秒执行的次数，因为我们无法控制：

调用此函数的线程数。

b)任何线程每秒调用此函数的次数。

我们需要以某种方式限制它的执行率。

这个程序是我解决这类问题的尝试。为此，我尝试使用令牌桶算法。

用法很简单。它由一个头文件"tokenBucket.hpp“组成。你需要把这个包括在你的程序中。假设您希望限制以下函数的执行率：

void printHelloWorld();

你需要做两件事：

您需要创建一个以所需的速率构造的tokenBucket对象，您希望您的函数以每秒的速度执行。例如tokenBucket aBucket(500)；

调用函数时，不要使用: printHelloWorld()；

你必须做：

if(aBucket.areTokensAvailable()) { 
printHelloWorld();
}

下面是我的头程序：

#ifndef __TOKEN_BUCKET_HPP__
#define __TOKEN_BUCKET_HPP__

#include <chrono>
#include <mutex>
#include <iostream>

class tokenBucket{
  
  public:

    /* Constructor */
    tokenBucket(uint64_t fa_tokenFillRatePerSec): m_tokenFillRatePerSecond(fa_tokenFillRatePerSec),m_bucketSize(fa_tokenFillRatePerSec),m_availableTokens(fa_tokenFillRatePerSec),m_lastRefillTime(std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count()),m_timeIntervalPerRequestInMicroSeconds(NUMBER_OF_MICROSECONDS_IN_A_SECOND/fa_tokenFillRatePerSec){
      fprintf(stdout,"\nToken Bucket initialised with the following values\nm_bucketSize(%lu)\nm_tokenFillRatePerSecond(%lu)\nm_availableTokens(%lu)\nm_lastRefillTime(%lu)\nm_timeIntervalPerRequestInMicroSeconds(%lu)\n",m_bucketSize,m_tokenFillRatePerSecond,m_availableTokens,m_lastRefillTime,m_timeIntervalPerRequestInMicroSeconds);
    }

    /* always called to check if sufficient number of tokens are available to server the request*/
    bool areTokensAvailable(int fa_numberOfRequestedTokens = 1){
      std::lock_guard<std::mutex> lg(m_mu);
      uint64_t now = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
      refill_tokens(now);

      if(m_availableTokens < fa_numberOfRequestedTokens){
        return false;
      }
      else{
        m_availableTokens -= fa_numberOfRequestedTokens;
        return true;
      }
    }


  private:
    static constexpr int NUMBER_OF_MICROSECONDS_IN_A_SECOND = 1000000;
    std::mutex m_mu;
    uint64_t m_bucketSize; //Currently I'm taking Bucket Size = token fill rate per second.
    uint64_t m_tokenFillRatePerSecond;
    uint64_t m_availableTokens; //current number of tokens available in the bucket
    uint64_t m_lastRefillTime;
    uint64_t m_timeIntervalPerRequestInMicroSeconds; // = (pow(10,6)/m_tokenFillRatePerSecond)

    /* to refill the tokens as per time diff */
    void refill_tokens(const uint64_t& fa_currentRequestTime) {
      /*calculate tokens added in particular time difference */
      if (fa_currentRequestTime >= m_lastRefillTime + m_timeIntervalPerRequestInMicroSeconds) {

        uint64_t l_newTokens = (fa_currentRequestTime - m_lastRefillTime)/m_timeIntervalPerRequestInMicroSeconds;

        if(m_availableTokens + l_newTokens < m_bucketSize) {
          m_availableTokens += l_newTokens;
        }
        else {
          m_availableTokens = m_bucketSize;
        }
        m_lastRefillTime = fa_currentRequestTime;
      }
    }
};

#endif

欢迎评论/批评。

Answer 1

避免了过多的

铸造时间

大量代码用于将时间转换为整数。避免过早转换；尽可能多地存储std::chrono类型的时间。实际上，存储桶中有多少令牌，您可以相反地存储桶中有多少时间。然后，只有在areTokensAvailable()中，才需要将桶中的时间转换为令牌的数量。

例如，对std::chrono::...::now()的两个调用的结果可以互相减去，结果是一个可以添加到另一个持续时间的持续时间。

考虑使用较短的函数和变量名称

您的函数和变量名称非常冗长，以至于代码难以阅读。尽量使它们更简洁，删除多余的信息。我还将避免使用前缀，如fa_。它代表function argument吗？从函数定义中可以清楚地看出，这是一个参数。私有成员变量的m_ prefx更常用，有时还有助于避免名称冲突，所以我会保留它。

使用一种类型来存储令牌的数量(

)

在代码中，可以同时使用uint64_t和int来表示令牌的数量。保持一致，坚持单一类型。使用类型别名使其更显式。

使用std::chrono::steady_clock

不要用std::chrono::system_clock来测量时间的流逝。当夏令时、有闰秒和系统时钟被更改时(无论是管理员还是NTP守护进程)，它都会产生不正确的结果。保证std::chrono::steady_clock是一个单调递增的时钟。我还会为它创建一个类型别名来减少输入。

示例

下面是一个如何使代码看起来的示例：

class tokenBucket {
    using count_type = uint64_t;
    using clock = std::chrono::steady_clock;

public:
    tokenBucket(count_type rate): m_rate(rate) {}

    bool request(count_type count) {
        std::lock_guard<std::mutex> lock(m_mutex);
        refill();
        return try_remove(count);
    }

private:
    std::mutex m_mutex;

    count_type m_rate;
    clock::time_point m_last_refill{clock::now()};
    clock::duration m_available{};
    clock::duration m_capacity{std::chrono::seconds(1)};

    void refill() {
        auto now = clock::now();
        m_available += now - m_last_refill;
        m_available = std::min(m_available, m_capacity);
        m_last_refill = now;
    }

    bool try_remove(count_type count) {
        auto requested = count * clock::duration(std::chrono::seconds(1)) / m_rate;

        if (requested <= m_available) {
            m_available -= requested;
            return true;
        } else {
            return false;
        }
    }    
};

注意:这里的m_capacity将存储桶的大小作为一个持续时间。如果它是常量，则可以将其设置为static constexpr变量。

Answer 2

如果您正在编程c++，您应该避免像fprintf这样的函数(来自C)，您应该使用std::cout，这是c++标准库中的函数。