This example demonstrates multiple implementations of the token-bucket algorithm in Elixir. These are for learning purposes only and their use in a production environment is discouraged.
This example implements two token buckets in Elixir. One uses lockless concurrency primitives from the OTP Atomics module to achieve high-throughput intra-node rate-limiting. The other utilizes an Agent process to implement a distributable but substantially slower rate-limiter.
For testing and benchmarking convenience, both implementations adhere to the TokenBucket behavior and TokenBucket.Bucket protocol, defined in token_bucket.ex.
1. Agent Bucket
The agent bucket implementation uses an Elixir Agent to keep a counter of tokens which other processes may request. By virtue of message passing, the implementation achieves mutual exclusion in a distributed environment, so it is theoretically suitable to guard a shared resource. On a fixed interval, an OTP timer process adds tokens to the bucket.
Ad-hoc benchmarks show throughput of approximately 200 requests per millisecond on my machine. For contrast, the "control" bucket (which is a no-op) could fire 4,500 times per millisecond. Actual performance of the agent implementation would likely be worse since network latency would become a factor in practical use-cases.
2. Atomic Bucket
The atomic bucket implementation relies on the OTP atomics module for counting available tokens. This module utilizes compare-and-swap hardware instructions to achieve high-performance, lockless atomic updates of shared data, which enables very high throughput updates of the shared token counter in the context of a single node. Similar to the agent bucket, an OTP timer process adds tokens to the bucket on a fixed interval.
Ad-hoc benchmarks show throughput of approximately 2,900 - 3700 requests per millisecond on my machine, with higher throughput when requests are denied and slower throughput when requests are granted. For contrast, the "control" bucket (which is a no-op) could fire 4,500 times per millisecond.
The difference in performance between when requests are denied and when requests are granted is rooted in the implementation. In either case, the bucket must atomically read the value of the token counter. When there are too few tokens, however, the denied case can exit immediately. The granted case must then attempt to update the token counter, which could require several attempts. Reference the implementation of take:
def take(bucket, tokens) do
if tokens < 1 do
raise ArgumentError, "Must request one or more tokens"
end
take_validated(bucket, tokens)
end
defp take_validated(bucket, tokens) do
available = :atomics.get(bucket.atomics, 1)
if available >= tokens do
if :ok == :atomics.compare_exchange(
bucket.atomics, 1, available, available - tokens)
do
:granted
else
take_validated(bucket, tokens)
end
else
:denied
end
end