What is the Leaky Bucket Algorithm?
As the name suggests, the Leaky Bucket algorithm uses a leaky bucket to limit traffic.
Because there is a hole at the bottom of the bucket, it will leak water at regular intervals, and we can imagine the traffic as water falling into the bucket from above.
This leads to two situations. If the speed at which traffic is injected into the bucket is slower than the speed at which the bucket leaks, the bucket will be in an empty state, that is, it is not overloaded.
The second situation is that if the speed of traffic injection into the bucket is faster than the bucket, then the bucket will gradually exceed its maximum capacity. For the overflow traffic, the bucket will reject it to prevent further traffic from entering.
Implementation in Java
Here we define an “empty capacity” to represent the freed space. It can also be calculated by the remaining water to calculate the space occupied by the water, which are two perspectives. But we use “empty capacity”.
For the new traffic, we need to judge whether the Empty Capacity can accommodate these flows. If it can, reduce the size of the Empty Capacity. If it can’t, reject it.
Differences from the Token Bucket
The token bucket puts tokens in at regular intervals, while the leaky bucket flows data at regular intervals.
The naive implementation of the token bucket calculates the time that can handle the overflow request and blocks it, while the leaky bucket will reject the overflow traffic.