shared-token-bucket.md

Shared token bucket

Intro

The classical token bucket has two parameters -- rate and limit. The rate is the amount of tokens that are put into bucket per some period of time (say -- second), the limit is the maximum amount of tokens that can be accumulated in the bucket. The process of regeneration of tokens this way is called "replenishing" below. When a request needs to be served it should try to get a certain amount of tokens from the bucket.

The shared token bucket implements the above model for seastar sharded architecture. The implementation doesn't use locks and is built on atomic arithmetics.

Theory

Rovers

The bucket is implemented as a pair of increasing counters -- tail and head rovers. The consumer of tokens advances the tail rover. To replenish tokens into the bucket the head rover is advanced.

+--------------------------------------------------------------------->
^             ^
tail          head

grab N tokens:

+--------------------------------------------------------------------->
.---> ^       ^
      tail    head

replenish N tokens:

+--------------------------------------------------------------------->
      ^       .---> ^
      tail          head

It's possible that after grab the tail would overrun the head and will occur in front of it. This would mean that there's not enough tokens in the bucket and that some amount of tokens were claimed from it.

grab a lot of tokens:

+--------------------------------------------------------------------->
      .------------ ^ --> ^
                    head  tail

To check if the tokens were grabbed the caller needs to check if the head is (still) in front of the tail. This approach adds the ability for the consumers to line up in the queue when they all try to grab tokens from a contented bucket. The "ticket lock" model works the same way.

Capped release

The implementation additionally support so called "capped release". This is when tokens are not replenished from nowhere, but leak into the main bucket from another bucket into which the caller should explicitly put them. This mode can be useful in cases when the token bucket guards the entrance into some location that can temporarily (or constantly, but in that case it would denote a bucket misconfiguration) slow down and stop handling tokens at the given rate. To prevent token bucket from over-subscribing the guardee at those times, the second bucket can be refilled with the completions coming from the latter.

In terms of rovers this is implemented with the help of a third rover called ceiling (or ceil in the code). This ceil rover actually defines the upper limit at which the head rover may point. Respectively, putting tokens into the second bucket (it's called releasing below) means advancing the ceil.

Practice

API

To work with the token bucket there are 4 calls:

• grab(N) -- grabs a certain amount of tokens from the bucket and returns back the resulting "tail" rover value. The value is useless per-se and is only needed to call the deficiency() method

• replenish(time) -- tries to replenish tokens into the bucket. The amount of replenished tokens is how many had accumulated since last replenish till the time parameter

• release(N) -- releases the given number of token making them available for replenishment. Only works if capped release is turned on by the template parameter, otherwise asserts

• deficiency(tail) -- returns back the number of tokens that were claimed from the bucket but that are not yet there. Non-zero number means that the bucket is contented and the request dispatching should be delayed

Example

For example, the simple dispatch loop may look like this

while (true) {
    request = get_next_request()
    tail = token_bucket.grab(request.cost())
    while (token_bucket.deficiency(tail)) {
        yield
    }
    request.dispatch()
}

And in the background there should run a timer calling token_bucket.replenish(now())

Additionally, if there's a need to cap the token bucket with the real request serving rate, upon request completion one should call token_bucket.release(request.cost())