Among the traffic limiting algorithms, there is a token bucket algorithm, which can deal with the transient burst of traffic, which is especially useful for the situation of uneven traffic in the real environment. It will not trigger traffic limiting frequently and is friendly to the caller.

For example, the current limit of 10qps will not exceed this amount most of the time, but will occasionally reach 30qps and then return to normal quickly. Assuming that this burst of traffic does not have an impact on system stability, we can allow this burst of traffic to a certain extent, resulting in a better usability experience for users. This is where the token bucket algorithm comes in.

Principle of token bucket algorithm

As shown in the figure below, the basic principle of the algorithm is that there is a token bucket with a capacity of X and Z tokens are put into the bucket every Y unit of time. If the number of tokens in the bucket exceeds X, it is discarded. To process a request, you need to retrieve the token from the token bucket. If you get the token, you continue processing. If the token is not available, the request is rejected.

As you can see, it is particularly important to set the number of X, Y, and Z in the token bucket algorithm. Z should be slightly larger than the number of requests per Y unit of time, and the system will be in this state for a long time; X is the instantaneous maximum number of requests allowed by the system, and the system should not stay in this state for a long time. Otherwise, traffic limiting will be triggered frequently. In this case, it indicates that the traffic exceeds the expectation, and the cause needs to be investigated in time and corresponding measures should be taken.

Redis implements the token bucket algorithm

You’ve seen some programs implement token buckets where you put tokens into the bucket either by starting a thread and increasing the number of tokens every Y units of time, or by timing the process in a Timer. I am not satisfied with this method for two reasons: (1) it wastes thread resources and (2) the execution time is not accurate due to scheduling issues.

The way to determine the number of tokens in the token bucket here is to calculate first how much time has elapsed since the last request, whether the token time threshold has been reached, and then how many tokens are added and how many can be placed in the bucket.

Talk is cheap!

The following is to see how to achieve Redis, because it involves many interactions with Redis, here in order to improve the throughput of limiting the flow processing, reduce the number of interactions between the program and Redis, the use of Redis support Lua Script, Lua script execution is atomic, So you don’t have to worry about dirty data.

The code is adapted from FireflySoft.ratelimit, which supports not only plain primary/secondary deployment Redis, but also cluster Redis, so throughput can be improved by scaling out horizontally. To make it easier to read, here are some comments, which are not actually available.

-- Defines the return value, which is an array, including whether flow limiting is triggered (1 flow limiting 0 passes) and the number of tokens in the current bucket
local ret={}
ret[1] =0
Redis cluster sharding Key, KEYS[1] is the traffic limiting target
local cl_key = '{'. KEYS[1]..'} '

-- Gets the current setting of the current limit penalty. When the limit penalty is triggered, a KV with an expiration time will be written
If there is a limiting penalty, return result [1,-1]
local lock_key=cl_key .. '-lock'
local lock_val=redis.call('get',lock_key)
if lock_val == '1' then
    ret[1] =1
    ret[2] =- 1
    return ret;
end

-- Some code is omitted here

Get [last time a token was put into the bucket], if this time was not set, then the token bucket does not exist, then:
One case is the first execution where the token bucket is full.
-- Another case is that the current limiting process has not been carried out for a long time, resulting in the release of KV carrying this time.
The expiration time is longer than the natural time to put the token into the bucket until the bucket is full, so the token bucket should also be full.
local last_time=redis.call('get',st_key)
if(last_time==false)
then
 - Number of tokens remaining after this execution: bucket capacity - Number of tokens consumed during this execution
    bucket_amount = capacity - amount;
    -- Update this token count to the token bucket, and there is an expiration time. If this procedure is not executed for a long time, the token bucket KV will be recycled
    redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time)
    Set the time when tokens were last added to the bucket, which will be used later to calculate the number of tokens that should be added to the bucket
    redis.call('set',st_key,start_time,'PX',key_expire_time)
    -- Return value [number of tokens in the current bucket]
    ret[2]=bucket_amount
    -- No other processing required
    return ret
end

-- Token bucket exists and gets the current number of tokens in the token bucket
local current_value = redis.call('get',KEYS[1])
current_value = tonumber(current_value)

Determine if it is time to add a new token to the bucket: current time - time of last drop >= Time interval between drops
last_time=tonumber(last_time)
local last_time_changed=0
local past_time=current_time-last_time
if(past_time<inflow_unit)
then
 -- Take the token directly from the token bucket before placing it
    bucket_amount=current_value-amount
else
 -- Some tokens need to be put in, estimated number of places = (time since last place/time interval between places)* Number of places per unit of time
    local past_inflow_unit_quantity = past_time/inflow_unit
    past_inflow_unit_quantity=math.floor(past_inflow_unit_quantity)
    last_time=last_time+past_inflow_unit_quantity*inflow_unit
    last_time_changed=1
    local past_inflow_quantity=past_inflow_unit_quantity*inflow_quantity_per_unit
    bucket_amount=current_value+past_inflow_quantity-amount
end

-- Some code is omitted here

ret[2]=bucket_amount

-- If the amount left in the bucket is less than 0, then see if the current limiting penalty is needed, and if so write a penalty KV with the expiration time of the penalty seconds
if(bucket_amount<0)
then
    if lock_seconds>0 then
        redis.call('set',lock_key,'1'.'EX',lock_seconds,'NX')
    end
    ret[1] =1
    return ret
end

-- If the token can be successfully deducted, the token bucket KV needs to be updated
if last_time_changed==1 then
    redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time)
 -- There is a new release, update [last release time] to this release time
    redis.call('set',st_key,last_time,'PX',key_expire_time)
else
    redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time)
end
return ret
Copy the code

From the above code, it can be seen that the main processing process is:

1. Determine whether there is a flow restriction penalty, return directly if there is, and enter the next step if there is no.

2. Determine whether the token bucket exists. If it does not exist, create the token bucket first, and then deduct the token to return.

3. Judge whether it is necessary to place a token. If it is not necessary, the token will be directly deducted; if it is necessary, the token will be placed first and then deducted.

4. Judge the number of deducted tokens. If it is less than 0, return flow limiting and set the penalty of flow limiting; if it is greater than or equal to 0, go to the next step.

Update the number of tokens in the bucket to Redis.

You can submit and run this Lua script in the Redis library of any development language if you are using. NET platform, see this article: using token buckets in ASP.NET Core.

About FireflySoft RateLimit

Fireflysoft. RateLimit is a traffic limiting library based on the.NET Standard. Its kernel is simple and lightweight, and it can flexibly respond to traffic limiting scenarios of various requirements.

Its main features include:

  • A variety of traffic limiting algorithms: built-in fixed window, sliding window, leakage bucket, token bucket four algorithms, can also be customized expansion.
  • Multiple count storage: currently, memory and Redis storage are supported.
  • Distributed friendly: Support unified counting of distributed applications through Redis storage.
  • Flexible traffic limiting target: Various data can be extracted from the request to set the traffic limiting target.
  • Traffic limiting punishment: After traffic limiting is triggered, the client can be locked for a period of time.
  • Dynamic change rules: Supports dynamic change of traffic limiting rules while the program is running.
  • Custom error: You can customize the error code and error message after traffic limiting is triggered.
  • Universality: In principle, it can meet any scenario requiring traffic limiting.

Github open Source: github.com/bosima/Fire…

To learn more about architecture, check out the public account FireflySoft. Original content, reproduced please indicate the source.