Rate Limiting Using Token Bucket Filter
Explore the implementation of rate limiting using the token bucket filter pattern in C#. Learn how to create a thread-safe getToken method that controls access based on token availability without extra threads. Understand key concurrency principles and mutex use to solve this common interview problem effectively.
We'll cover the following...
Rate Limiting Using Token Bucket Filter
This is an actual interview question asked at Uber and Oracle.
Imagine you have a bucket that gets filled with tokens at the rate of 1 token per second. The bucket can hold a maximum of N tokens. Implement a thread-safe class that lets threads get a token when one is available. If no token is available, then the token-requesting threads should block.
The class should expose an API called getToken() that various threads can call to get a token
Solution
This problem is a naive form of a class of algorithms called the "token bucket" algorithms. A complimentary set of algorithms is called "leaky bucket" algorithms. One application of these algorithms is shaping network traffic flows. This particular problem is interesting because ...