Is your bucket leaky?
💡 Intro
While reading a post about SeatGeek’s virtual waiting room by Neo Kim from System Design Newsletter I stumbled across an interesting algorithm - a leaky bucket algorithm. Since I have always been fond of algorithms and data structures, it immediately caught my attention.
In this post I’ll write what exactly a leaky bucket algorithm is and give a basic idea behind the implementation. I’ll also give some examples where it is used and show two libraries in Python that implement the algorithm.
Side note: If you are interested in system design and want to find out how some of the largest companies solve their most complex problems check out System Design Newsletter. NK is bringing you complex systems in a simple and very digestible way. Very recommended!
🪣 Basic idea
Basic idea of the leaky bucket algorithm can be described with an analogy of a bucket with a hole on the bottom. If you are pouring water in, the water will leak through the hole on the bottom of the bucket. It doesn’t matter how fast you are pouring the water in, the water will leak out through the hole at a constant rate. If you are adding too much water to the bucket and the bucket gets full, all the excess water will overflow.
🚰 Description
We will describe the leaky bucket algorithm with an example. Let’s say you have a web application and want to limit the rate at which users are sending the requests towards you application.
You will have a counter that will represent the bucket. Whenever a user sends a request towards your application you will increase that counter. That represents the water flowing into your bucket. If the counter is less than some fixed limit, you forward the user’s request to the application. If the counter exceeds the limit, you discard that request, probably by returning HTTP 429 or 503 to the user. This is the overflowing of the water from the bucket.
Counter is decreased periodically, at some fixed rate. Decreasing of the counter represents the water leaking out of the bottom of the bucket.
In the algorithm, we specify two things:
Rate at which the counter is decreased - this determines the average bandwidth, i.e. how many requests on average can our app process.
Bucket limit - this determines what is the size of the bursts of requests that our app can handle.
There is also a slightly different version of the leaky bucket algorithm that is mentioned in the literature. Here, instead of the counter, the bucket is represented with a first-in-first-out queue of a fixed size. The queue is consumed periodically. Since the queue is fixed in size, if there is no room in the queue, the incoming data gets discarded. After some data is processed, and there is room in the queue again, the new incoming data can be added to the queue again.
It was shown that the version with the queue is a special case of the version with the counter.
💻 Usage
The leaky bucket algorithm is widely used in computer and telecommunications networks. It is used to shape and schedule the data transmission, in the form of network packets, so it conforms to the limits of the network.
It is also often used in web applications to control and limit the rate of data or requests passing through a system.
SeatGeek, one of the largest platforms for selling and buying tickets online, uses leaky bucket algorithm in their virtual waiting room implementation. In short, they use the leaky bucket to control the number of users that can enter the protected zone of the website. Only users in the protected zone are able to actually buy the tickets.
NGINX, the most used web server today, also uses the leaky bucket algorithm. They use it for the rate limiting, i.e. for limiting the amount of HTTP requests a user can make in a given period of time to your web server. You can read more here.
🛞 Don’t re-invent the wheel
The algorithm itself is not super complex and you could definitely implement it yourself. However, I found two Python libraries that could do that for you.
aiolimiter
This is a simple asynchronous implementation, you can find it here. It enables you to quickly set-up a bucket (limiter) with a defined number of requests and time period.
Here is a quick example of the basic usage:
PyrateLimiter
This is a bit more complex library, with more features. You can check it out here.
Some of the features:
Tracks any number of rate limits and intervals you want to define.
Handles exceeded rate limits by either raising errors or adding delays.
Can be used as a normal function call or a decorator.
Works both with sync and async calls.
Here is a quick example:
PyrateLimiter also has one really handy feature - you can use Redis and SQLite as a bucket storage. That means you can use it across multiple processes and that it can handle application restarts.
Here is a simple example with Redis:
🏁 Conclusion
Leaky bucket algorithm is one of those algorithms that is used on probably every request to a web application, yet not many engineers know about it. I hope you have learned something new in this post. Who knows, maybe you will have an opportunity to use it in your project soon.
Thank you for reading this article! Please comment and let me know if you have any feedback.