3
\$\begingroup\$

This program is my attempt at solving the below problem:

We have a function which is going to be called by multiple threads. The problem is to find a way to limit the number of times this function is executed per second given that we don't have a control over:

a) The number of threads calling this function.

b) The number of times per second this function will be called by any thread.

We need to somehow limit its rate of execution.

This program is my attempt at solving this kind of problem. I've tried to use the Token Bucket Algorithm for this.

The usage is simple. It consists of a header file "tokenBucket.hpp". You need to include this in your program. Suppose you want to limit the execution rate of the function given below:

void printHelloWorld();

You need to do 2 things:

You need to create a tokenBucket object constructed with the required rate you want your function to be executed per second. e.g. tokenBucket aBucket(500);

When calling your function, then instead of: printHelloWorld();

you have to do:

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

Given below is my header only program:

#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

Comments/Criticisms are welcome.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Avoid casting time too much

A lot of code is spent on converting time to integers. Avoid casting too early; store time as much as possible as std::chrono types. In fact, intead of storing how much tokens there are in the bucket, you could instead store how much time there is in the bucket. Then only in areTokensAvailable() do you need to cast from the amount of time in the bucket to the number of tokens.

For example, the result of two calls to std::chrono::...::now() can be subtracted from each other, the result is a duration that can be added to another duration.

Consider using shorter function and variable names

Your function and variable names are very verbose, to the point that they make the code harder to read. Try to make them more concise, remove redundant information. I would also avoid using prefixes such as fa_. Does it stand for function argument? It's already clear from the function definition that it's an argument. The m_ prefx for private member variables is more commonly used, and sometimes helps avoid name clashes, so I would keep that.

Use a single type to store the number of tokens

In your code, you use both uint64_t and int for the number of tokens. Be consistent and stick with a single type. Use a type alias to make it more explicit.

Use std::chrono::steady_clock

Don't use std::chrono::system_clock for measuring the passage of time. It will give incorrect results when daylight savings time changes, when there are leap seconds and whenever the system clock gets changed (either by an administrator or by something like an NTP daemon). The std::chrono::steady_clock is guaranteed to be a monotonically increasiing clock. I would also create a type alias for it to reduce typing.

Example

Here's an example of how the code can be made to look:

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;
        }
    }    
};

Note: m_capacity here holds the size of the bucket as a time duration. If it is constant, you can make it a static constexpr variable.

\$\endgroup\$
2
\$\begingroup\$

If you are programming c++ you should avoid functions like fprintf(from C), you should use std::cout that is the one on the standard library of c++

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.