Take you to quickly understand: leaky bucket and token bucket algorithm in current limiting

[[346652]]

This article is reprinted from the WeChat public account "脑进煎鱼了", written by Chen Jianyu. To reprint this article, please contact the public account "脑进煎鱼了".

Preface

In theory, every resource point that provides functions externally or internally needs to be subject to certain traffic control. Otherwise, in the continuous iteration of the business, sudden traffic may occur (just like the sudden changes in some industries at the beginning of the year, which led to a sudden surge in business traffic):

Burst traffic

If there is no flow limiting, some strange problems will occur. In fact, the system cannot withstand this wave of traffic and gradually collapses, leading to system failure.

Real-life scenarios

The most common real-life scenario is the power strips and sockets that can be seen everywhere in daily life. Their built-in fuses, also known as current fuses, mainly serve as overload protection. When the current abnormally rises to a certain height and temperature, the fuse will melt and cut off the current, thereby protecting the safe operation of the circuit.

Therefore, there are many scenarios in the real world that are similar to current limiting and circuit breaking in software engineering, which are also for controlling the amount and cutting off when the amount exceeds the limit. You can also think about whether you have encountered other similar examples in real life?

[[346653]]

Fuse (picture from the Internet)

Leaky Bucket

The leaky bucket algorithm is a commonly used algorithm for traffic shaping or rate limiting in the network. Its main purpose is to control the rate at which data is injected into the network and smooth out burst traffic on the network.

The leaky bucket algorithm regulates traffic access through its algorithm, so that burst traffic can be shaped and deburred to become relatively mild, so as to provide a stable flow for the network.

The storage bucket of the leaky bucket algorithm is mainly defined by three parameters: the capacity of the bucket, the rate at which water flows out of the bucket, and the initial fullness of the bucket.

The core concept is exactly what it sounds like: a leaky bucket.

Image from geeksforgeeks

Bursty Flow

In the figure above, the tap represents bursty flow. When there is bursty flow in the network without any regulation, a similar scenario will occur as in the case of Bursty Data. The host sends data at a rate of 12 Mbps for 2 seconds, totaling 24 Mbits of data. The host then pauses sending data for 5 seconds, and then sends data at a rate of 2 Mbps for 3 seconds, ultimately sending a total of 6 Mbits of data.

Therefore, the host sends a total of 30 Mbits of data in 10 seconds. But there is a problem here, that is, the data transmission is not smooth, there is a large peak. If all traffic is transmitted in this way, it will be "some die from drought and some die from flood", which is not particularly friendly to the system.

Fixed Flow

In order to solve the problem of Bursty Flow scenario, Leaky Bucket appeared, which has a fixed outflow rate and fixed capacity.

In the figure above, the leaky bucket continues to send data at a rate of 3 Mbps in the same 10 seconds to smooth the traffic. If the water (traffic) comes too fast, but the water flow (leakage) is not fast enough, the final result is that the water overflows directly, which is presented as a rejection of requests/queue waiting. In addition, when the buckets are empty, there is a possibility that the water that reaches the bucket capacity limit will be poured in at once, and peaks may also appear at this time.

Simply put, it is like a leaky bucket. Water flows in, but the bucket has only a fixed flow rate to flow water out. If the capacity is full, it will be rejected, otherwise the flow will continue to flow out.

Token Bucket Algorithm

The token bucket algorithm is also a commonly used algorithm for traffic shaping or rate limiting in the network. Its main purpose is to control the amount of data sent to the network and allow burst data to be sent.

The token bucket algorithm puts tokens into the bucket at a constant rate. If a new request comes in and wants to be processed, it must first get an available token from the bucket before it can be processed. If there is no token available in the bucket, the request is rejected/queued.

Image from gateoverflow

1. A token is added to the buckets every 1/r seconds.
2. Buckets can hold up to b tokens. If the bucket is full, the newly added token will be discarded (that is, no new token is needed).
3. When the host transmits n bytes packets, if there are n tokens in the buckets, the required token is obtained and n bytes are successfully transmitted.
4. When the available token is less than n bytes, no token will be obtained from the buckets and the request will be rejected/queued.

Leaky Bucket vs Token Bucket

The leaky bucket algorithm and the token bucket algorithm are essentially for traffic shaping or rate limiting to prevent the system from being crashed due to large traffic, but the core difference between the two is that the direction of the flow limitation is opposite.

The token bucket limits the average inflow rate of traffic and allows a certain degree of sudden traffic, with the maximum rate being the capacity of the bucket and the rate at which tokens are generated. The leaky bucket limits the outflow rate of traffic, which is relatively fixed.

Therefore, it will also bring a problem. In some scenarios, the leaky bucket algorithm cannot effectively use network resources because the leaky bucket's leakage rate is relatively fixed. Therefore, when the network is in good condition and there is no congestion, the leaky bucket is still limited and there is no way to release the amount. The token bucket algorithm is different. It can limit the average rate while supporting a certain degree of burst traffic.

Summarize

In software systems, current limiting often represents traffic shaping and rate limiting, which is a very common means of regulation. Generally, we will integrate it into the unified framework, gateway, and Mesh in the early stage. Therefore, it is recommended that students who are involved in business should consider this area to facilitate subsequent rapid use/access. After all, business traffic bursts always come suddenly and may even be malicious attacks.

The leaky bucket and token bucket mentioned in this article are both very common methods. Although they are analyzed separately, from the perspective of software development, do you think they can be integrated to combine their advantages?