Rate Limiting Using Token Bucket Filter
Explore how to design and implement a thread-safe token bucket filter in Python for rate limiting use cases. This lesson teaches you to handle concurrency challenges by managing token generation and consumption without relying on background threads. Understand lock usage to ensure safe access, and discover an efficient approach to control the rate at which threads obtain tokens, preparing you for common concurrency problems in engineering interviews.
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 get_token() 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 the majority of candidates incorrectly start with a multithreaded approach when taking a stab at the problem. One is tempted to create a background thread to fill the bucket with tokens at regular intervals but there is a far simpler ...