Struct TokenBucket 

pub(crate) struct TokenBucket<I> {
    rate: u64,
    bucket_max: u64,
    bucket: u64,
    added_tokens_at: I,
}

A token bucket.

Calculations are performed at microsecond resolution. You likely want to call refill() each time you want to access or perform an operation on the token bucket.

This is partially inspired by tor’s token_bucket_ctr_t, but the implementation is quite a bit different. We use larger values here (for example u64), and we aim to avoid drift when refills occur at times that aren’t exactly in period with the refill rate.

It’s possible that we could relax these requirements to reduce memory usage and computation complexity, but that optimization should probably only be made if/when needed since it would make the code more difficult to reason about, and possibly more complex.

Fields

rate: u64

The refill rate in tokens/second.

bucket_max: u64

The max amount of tokens in the bucket. Commonly referred to as the “burst”.

bucket: u64

Current amount of tokens in the bucket.

added_tokens_at: I

Time that the most recent token was added to the bucket.

While this can be thought of as the last time the bucket was partially refilled, it more specifically is the time that the most recent token was added. For example if the bucket refills one token every 100 ms, and the bucket is refilled at time 510 ms, the bucket would gain 5 tokens and the stored time would be 500 ms.

Implementations

impl<I: TokenBucketInstant> TokenBucket<I>

pub(crate) fn new(config: &TokenBucketConfig, now: I) -> Self

A new TokenBucket with a given rate in tokens/second and a max token limit.

The bucket will initially be full. The value max is commonly referred to as the “burst”.

pub(crate) fn is_empty(&self) -> bool

Are there no tokens in the bucket?

pub(crate) fn max(&self) -> u64

The maximum number of tokens that this bucket can hold.

pub(crate) fn drain( &mut self, count: u64, ) -> Result<BecameEmpty, InsufficientTokensError>

Remove count tokens from the bucket.

pub(crate) fn claim( &mut self, count: u64, ) -> Result<ClaimedTokens<'_, I>, InsufficientTokensError>

Claim a number of tokens.

The claim will be held by the returned ClaimedTokens, and committed when dropped.

Note: You probably want to call refill() before this.

pub(crate) fn adjust(&mut self, now: I, config: &TokenBucketConfig)

Adjust the refill rate and max tokens of the bucket.

The token bucket is refilled up to now before changing the rate.

If the new max is smaller than the existing number of tokens, the number of tokens will be reduced to the new max.

A rate and/or max of 0 is allowed.

pub(crate) fn tokens_available_at( &self, tokens: u64, ) -> Result<I, NeverEnoughTokensError>

An estimated time at which the bucket will have tokens available.

It is not guaranteed that tokens will be available at the returned time.

If there are already enough tokens available, a time in the past may be returned.

A value of None implies “never”, for example if the refill rate is 0, the bucket max is too small, or the time is too large to be represented as an I.

pub(crate) fn refill(&mut self, now: I) -> BecameNonEmpty

Refill the bucket.

fn tokens_to_duration(tokens: u64, rate: u64) -> Option<Duration>

How long would it take to refill tokens at rate?

The result is rounded up to the nearest microsecond. If the number of tokens is large, the result may be much lower than the expected duration due to saturating 64-bit arithmetic.

None will be returned if the rate is 0.

fn duration_to_tokens(time: Duration, rate: u64) -> u64

How many tokens would be refilled within time at rate?

The time is truncated to microsecond granularity. If the time or rate is large, the result may be much lower than the expected number of tokens due to saturating 64-bit arithmetic.

Trait Implementations

impl<I: Debug> Debug for TokenBucket<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.