folly::BasicDynamicTokenBucket< Clock > Class Template Reference

#include <TokenBucket.h>

Public Member Functions
	BasicDynamicTokenBucket (double zeroTime=0) noexcept
	BasicDynamicTokenBucket (const BasicDynamicTokenBucket &other) noexcept
BasicDynamicTokenBucket &	operator= (const BasicDynamicTokenBucket &other) noexcept
void	reset (double zeroTime=0) noexcept
bool	consume (double toConsume, double rate, double burstSize, double nowInSeconds=defaultClockNow())
double	consumeOrDrain (double toConsume, double rate, double burstSize, double nowInSeconds=defaultClockNow())
double	available (double rate, double burstSize, double nowInSeconds=defaultClockNow()) const noexcept

Static Public Member Functions
static double	defaultClockNow () noexcept

Private Member Functions
template<typename TCallback >
bool	consumeImpl (double rate, double burstSize, double nowInSeconds, const TCallback &callback)

Private Attributes
std::atomic< double >	zeroTime_

Detailed Description

template<typename Clock = std::chrono::steady_clock>
class folly::BasicDynamicTokenBucket< Clock >

Thread-safe (atomic) token bucket implementation.

A token bucket (http://en.wikipedia.org/wiki/Token_bucket) models a stream of events with an average rate and some amount of burstiness. The canonical example is a packet switched network: the network can accept some number of bytes per second and the bytes come in finite packets (bursts). A token bucket stores up to a fixed number of tokens (the burst size). Some number of tokens are removed when an event occurs. The tokens are replenished at a fixed rate.

This implementation records the last time it was updated. This allows the token bucket to add tokens "just in time" when tokens are requested.

The "dynamic" base variant allows the token generation rate and maximum burst size to change with every token consumption.

Template Parameters

Clock

Clock type, must be steady i.e. monotonic.

Definition at line 48 of file TokenBucket.h.

Constructor & Destructor Documentation

template<typename Clock = std::chrono::steady_clock>

folly::BasicDynamicTokenBucket< Clock >::BasicDynamicTokenBucket ( double  zeroTime = 0 )

inlineexplicitnoexcept

Constructor.

Parameters

zeroTime

Initial time at which to consider the token bucket starting to fill. Defaults to 0, so by default token buckets are "full" after construction.

Definition at line 59 of file TokenBucket.h.

      : zeroTime_(zeroTime) {}

template<typename Clock = std::chrono::steady_clock>

folly::BasicDynamicTokenBucket< Clock >::BasicDynamicTokenBucket ( const BasicDynamicTokenBucket< Clock > &  other )

inlinenoexcept

Copy constructor.

Thread-safe. (Copy constructors of derived classes may not be thread-safe however.)

Definition at line 68 of file TokenBucket.h.

      : zeroTime_(other.zeroTime_.load()) {}

Member Function Documentation

template<typename Clock = std::chrono::steady_clock>

double folly::BasicDynamicTokenBucket< Clock >::available ( double  rate, double  burstSize, double  nowInSeconds = defaultClockNow()  ) const

inlinenoexcept

Returns the number of tokens currently available.

Thread-safe (but returned value may immediately be outdated).

Definition at line 182 of file TokenBucket.h.

References min, and folly::BasicDynamicTokenBucket< Clock >::zeroTime_.

Referenced by folly::BasicTokenBucket< Clock >::reset(), and TEST().

                                                              {
    assert(rate > 0);
    assert(burstSize > 0);

    return std::min((nowInSeconds - this->zeroTime_) * rate, burstSize);
  }

template<typename Clock = std::chrono::steady_clock>

bool folly::BasicDynamicTokenBucket< Clock >::consume ( double  toConsume, double  rate, double  burstSize, double  nowInSeconds = defaultClockNow()  )

inline

Attempts to consume some number of tokens. Tokens are first added to the bucket based on the time elapsed since the last attempt to consume tokens. Note: Attempts to consume more tokens than the burst size will always fail.

Thread-safe.

Parameters

toConsume	The number of tokens to consume.
rate	Number of tokens to generate per second.
burstSize	Maximum burst size. Must be greater than 0.
nowInSeconds	Current time in seconds. Should be monotonically increasing from the nowInSeconds specified in this token bucket's constructor.

Returns

True if the rate limit check passed, false otherwise.

Definition at line 121 of file TokenBucket.h.

References folly::BasicDynamicTokenBucket< Clock >::consumeImpl(), and tokens.

Referenced by TEST().

                                               {
    assert(rate > 0);
    assert(burstSize > 0);

    return consumeImpl(
        rate, burstSize, nowInSeconds, [toConsume](double& tokens) {
          if (tokens < toConsume) {
            return false;
          }
          tokens -= toConsume;
          return true;
        });
  }

template<typename Clock = std::chrono::steady_clock>

template<typename TCallback >

bool folly::BasicDynamicTokenBucket< Clock >::consumeImpl ( double  rate, double  burstSize, double  nowInSeconds, const TCallback &  callback  )

inlineprivate

Definition at line 194 of file TokenBucket.h.

References min, tokens, UNLIKELY, and folly::BasicDynamicTokenBucket< Clock >::zeroTime_.

Referenced by folly::BasicDynamicTokenBucket< Clock >::consume(), and folly::BasicDynamicTokenBucket< Clock >::consumeOrDrain().

                                 {
    auto zeroTimeOld = zeroTime_.load();
    double zeroTimeNew;
    do {
      auto tokens = std::min((nowInSeconds - zeroTimeOld) * rate, burstSize);
      if (!callback(tokens)) {
        return false;
      }
      zeroTimeNew = nowInSeconds - tokens / rate;
    } while (
        UNLIKELY(!zeroTime_.compare_exchange_weak(zeroTimeOld, zeroTimeNew)));

    return true;
  }

template<typename Clock = std::chrono::steady_clock>

double folly::BasicDynamicTokenBucket< Clock >::consumeOrDrain ( double  toConsume, double  rate, double  burstSize, double  nowInSeconds = defaultClockNow()  )

inline

Similar to consume, but always consumes some number of tokens. If the bucket contains enough tokens - consumes toConsume tokens. Otherwise the bucket is drained.

Thread-safe.

Parameters

toConsume	The number of tokens to consume.
rate	Number of tokens to generate per second.
burstSize	Maximum burst size. Must be greater than 0.
nowInSeconds	Current time in seconds. Should be monotonically increasing from the nowInSeconds specified in this token bucket's constructor.

Returns

number of tokens that were consumed.

Definition at line 154 of file TokenBucket.h.

References folly::BasicDynamicTokenBucket< Clock >::consumeImpl(), and tokens.

Referenced by TEST().

                                               {
    assert(rate > 0);
    assert(burstSize > 0);

    double consumed;
    consumeImpl(
        rate, burstSize, nowInSeconds, [&consumed, toConsume](double& tokens) {
          if (tokens < toConsume) {
            consumed = tokens;
            tokens = 0.0;
          } else {
            consumed = toConsume;
            tokens -= toConsume;
          }
          return true;
        });
    return consumed;
  }

template<typename Clock = std::chrono::steady_clock>

static double folly::BasicDynamicTokenBucket< Clock >::defaultClockNow ( )

inlinestaticnoexcept

Returns the current time in seconds since Epoch.

Definition at line 99 of file TokenBucket.h.

References count, and now().

                                           {
    using dur = std::chrono::duration<double>;
    auto const now = Clock::now().time_since_epoch();
    return std::chrono::duration_cast<dur>(now).count();
  }

template<typename Clock = std::chrono::steady_clock>

BasicDynamicTokenBucket& folly::BasicDynamicTokenBucket< Clock >::operator= ( const BasicDynamicTokenBucket< Clock > &  other )

inlinenoexcept

Copy-assignment operator.

Warning: not thread safe for the object being assigned to (including self-assignment). Thread-safe for the other object.

Definition at line 77 of file TokenBucket.h.

References folly::BasicDynamicTokenBucket< Clock >::zeroTime_.

Referenced by folly::BasicTokenBucket< Clock >::BasicTokenBucket().

                                                     {
    zeroTime_ = other.zeroTime_.load();
    return *this;
  }

template<typename Clock = std::chrono::steady_clock>

void folly::BasicDynamicTokenBucket< Clock >::reset ( double  zeroTime = 0 )

inlinenoexcept

Re-initialize token bucket.

Thread-safe.

Parameters

zeroTime

Initial time at which to consider the token bucket starting to fill. Defaults to 0, so by default token bucket is reset to "full".

Definition at line 92 of file TokenBucket.h.

References folly::BasicDynamicTokenBucket< Clock >::zeroTime_.

                                           {
    zeroTime_ = zeroTime;
  }

Member Data Documentation

template<typename Clock = std::chrono::steady_clock>

std::atomic<double> folly::BasicDynamicTokenBucket< Clock >::zeroTime_

private

Definition at line 213 of file TokenBucket.h.

Referenced by folly::BasicDynamicTokenBucket< Clock >::available(), folly::BasicDynamicTokenBucket< Clock >::consumeImpl(), folly::BasicDynamicTokenBucket< Clock >::operator=(), and folly::BasicDynamicTokenBucket< Clock >::reset().

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/TokenBucket.h