Shulou(Shulou.com)05/31 Report--

Editor to share with you how to use Redis to achieve token bucket algorithm, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

In the current limiting algorithm, there is a token bucket algorithm, which can deal with short burst traffic, which is especially useful for the situation where the traffic is not uniform in the real environment, and it will not trigger current limiting frequently and is friendly to the caller.

For example, the current limit on 10qps will not exceed this number in most cases, but it will occasionally reach 30qps, and then it will soon return to normal. Assuming that this burst of traffic will not affect the stability of the system, we can allow this instantaneous burst of traffic to a certain extent, thus bringing a better usability experience to users. This is where the token bucket algorithm is used.

Principle of token bucket algorithm

As shown in the following figure, the basic principle of the algorithm is that there is a token bucket with a capacity of X into which Z tokens are placed per Y unit of time. If the number of tokens in the bucket exceeds X, it will be discarded. When processing a request, you need to take the token out of the token bucket, continue processing if you get the token, and reject the request if you can't get the token.

As you can see, it is particularly important to set the number of XQuery 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 be in this state for a long time, otherwise current limit will be triggered frequently. This indicates that the traffic has exceeded expectations, and the cause needs to be investigated in time and corresponding measures need to be taken.

Implementing token Bucket algorithm with Redis

I've seen token buckets implemented by some programs, and the way to put tokens into the bucket is to start a thread, increase the number of tokens every Y unit of time, or execute this process regularly in Timer. I am not satisfied with this method for two reasons, one is a waste of thread resources, and the other is that the execution time of the scheduling problem is not accurate. [related recommendation: Redis video tutorial]

Here, the method to determine the number of tokens in the token bucket is to calculate how long it took from the last request to this request, whether it reached the time threshold for issuing tokens, and then how many tokens can be added. How many these tokens can be put in the bucket.

Talk is cheap!

Let's take a look at how it is implemented in Redis. Because multiple interactions with Redis are involved, in order to improve the throughput of current-limiting processing and reduce the number of interactions between programs and Redis, the implementation of Lua script,Lua script supported by Redis is atomic, so you don't have to worry about dirty data.

The code is excerpted from FireflySoft.RateLimit, which supports not only the normal master-slave deployment Redis, but also the cluster Redis, so the throughput can be improved by horizontal scaling. In order to make it easier to read, some notes are added here, which are actually not available.

-- defines the return value, which is an array, including: whether to trigger current limit (1 current limit 0 passes), the number of tokens in the current bucket local ret= {} ret [1] = 0mi-Redis cluster shard Key,KEYS [1] is the current limit target local cl_key ='{'.. KEYS [1].. '}'-- gets the current setting of the current limit penalty. When triggering the current limit penalty, a KV-- with expiration time is written. If there is a current limit penalty, the result [1] local lock_key=cl_key is returned. '- lock'local lock_val=redis.call (' get',lock_key) if lock_val= ='1' then ret [1] = 1 ret [2] =-1 return ret;end-- omits part of the code here-- get [the time when the token was last dropped into the bucket]. If the drop time has not been set, the token bucket does not exist. At this time:-- in one case, the token bucket is full when it is executed for the first time. -- another situation is that the current limit processing has not been performed for a long time, resulting in the release of the KV hosting this time.-- this expiration time will exceed the time it takes to naturally 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: capacity of buckets-number of tokens consumed in this execution bucket_amount = capacity-amount -- updates the number of tokens to the token bucket, and there is an expiration time. If you do not execute this program 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 the token was last placed in the bucket] Redis.call ('set',st_key,start_time,'PX',key_expire_time) is used later to calculate the number of tokens that should be placed in the bucket-- the return value [number of tokens in the current bucket] ret [2] = bucket_amount-- No additional processing is required for the existence of the return retend-- token bucket Get the current number of tokens in the token bucket local current_value = redis.call ('get',KEYS [1]) current_value = tonumber (current_value)-determine whether it is time to put a new token in the bucket: current time-last time > = time interval last_time=tonumber (last_time) local last_time_changed=0local past_time=current_time-last_timeif (past_time)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.