Struct AtomicTokenBucket 

pub(super) struct AtomicTokenBucket {
    available: AtomicU64,
    capacity: u64,
}

The atomic token bucket minus the clock component.

This is lock-free and the owner needs to refill it with a specific number of tokens it wants to be distributed across many actors.

Fields

available: AtomicU64

Every access to these counters is with Ordering::Relaxed as they don’t protect any outside data and so we only care about the atomicity action on the counter. The current token count.

capacity: u64

The maximum number of tokens the bucket may hold a.k.a the burst.

This is atomic because it can be set during runtime. For instance, a config option reconfigure of a bandwidth rate.

Implementations

impl AtomicTokenBucket

pub(super) fn new(capacity: u64) -> Self

A new bucket capped at capacity tokens.

It starts full.

pub(super) fn claim(&self, tokens: u64) -> Option<u64>

Claim all tokens from the bucket or nothing if not enough available.

The request is first clamped to the capacity because the bucket can never hold more than its burst.

Returns Some(claimed) if the bucket held at least the clamped request which indicates that they are now granted to the caller. Note that claimed can be lower than tokens hence why the caller needs to use that value and not what it asked for.

Returns None otherwise, nothing is taken.

pub(super) fn refill(&self, tokens: u64)

Add tokens to the bucket which is capped at the capacity.

We use a CAS loop (Compare-And-Swap) because we need to cap the refill to the internal capacity atomically. A fetch_add + fetch_sub is not possible in order to refill atomically because of this race:

  capacity = 100, available = 90:
    refill: fetch_add(50)  -> available = 140 (above capacity)
    claim:  fetch_sub(140) -> available = 0   (illegal claim, above capacity)
    refill: fetch_sub(40)  -> available underflows (adjust overshoot too late)

Any tokens that overshoot the capacity are forfeited.

Finally, the CAS loop is considered ok because the refill is not in the fast path and should work most of the time on the first iteration.

pub(super) fn drain(&self) -> u64

Take every token out of the bucket and return the amount.

pub(super) fn capacity(&self) -> u64

Return the capacity.

Trait Implementations

impl Debug for AtomicTokenBucket

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

Formats the value using the given formatter.