Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to achieve token bucket in a script in Spring Cloud Gateway. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.

Preface

In the design of a distributed system with high concurrency, current limitation is a function point that can not be ignored. If there are no effective traffic access restrictions on the system, in the scenario of the peak of traffic such as Singles' Day and ticket grabbing, it will easily bring our system down. As the gateway component of the guard as the system service, as the unified entrance of the system service, it is more necessary to consider the traffic restriction, and it is more appropriate to block the traffic directly in the gateway layer than in each system. The current-limiting function is provided in the implementation of Spring Cloud Gateway. The following mainly analyzes how to achieve the current-limiting function in Spring Cloud Gateway through a lua script.

Review of current limiting algorithm

There are many ways to realize current limitation. Let's review several common implementation algorithms first.

Counter / time window method

This current-limiting algorithm is the simplest and easiest to implement, and the current-limiting purpose can be achieved by setting the maximum number of visits per unit time. For example, a system can carry a general qps of 60, then we can use the calculator method to limit the interface to be accessed only 60 times per second. However, the implementation of this algorithm, like its functional description, has a flaw. If the traffic reaches its peak within the first 1% of the time window, then 99% of the time system in the time window will be blocked outside the door even if it can continue to provide services. This defect is also known as the "spike effect".

Leaky bucket method

The leaky bucket method is different from the calculator method, it effectively avoids the "spike effect" of the current limit of the counter method, and the implementation is not complicated, which can be realized by the way of fixed size queue + timing queue elements. As the name leaky bucket, like a container of water, the leaky bucket method only limits the rate of water out of the container. When the rate of water intake is too high, it will fill the container and cause overflow, and the flow of the overflow part is the rejected flow. For example, if the container size is 100 and the effluent rate is 10 seconds per second, when the bucket is empty, the maximum flow can reach 100 seconds, but even so, limited to a fixed outflow rate, the back end can only handle a maximum of 10 containers per second, and the rest of the flow will be buffered in the leaky bucket. This is also a defect of the leaky bucket method, which can not really deal with sudden flow peaks and is not efficient.

Token bucket method

The token bucket method is also based on the prototype of the bucket, but when it is completely different from the leaky bucket algorithm, there is no outlet. The token bucket controls the flow through the token generation rate + the token bucket volume, which effectively solves the problem of low efficiency of the leaky bucket. For example, for a bucket with a volume of 100, the token generation rate is 50 seconds, which means that when the token in the bucket is full, it can carry a maximum of 100 traffic. If the traffic remains high, requests will be processed at a constant speed of 50 traffic per second. This characteristic of token bucket can effectively deal with the flood peak flow and can not be overwhelmed by the flood peak, which is a common realization method of current limit at present. The more famous implementation is RateLimiter in Google guava. Then the current limit implemented by the token bucket algorithm is also used in the Spring Cloud Gateway that will be analyzed below.

Documentation for guava: https://github.com/google/guava/wiki

Token bucket in Spring Cloud Gateway

The Spring gateway is a distributed flow limit based on token bucket + redis. For more information, please see the following two codes:

Lua script address: resources/META-INF/scripts/request_rate_limiter.lua

RedisRateLimiter:gateway/filter/ratelimit/RedisRateLimiter.java

Try {Listkeys = getKeys (id); / / The arguments to the LUA script. Time () returns unixtime in seconds. ListscriptArgs = Arrays.asList (replenishRate + ", burstCapacity +", Instant.now (). GetEpochSecond () + "," 1 ") / / allowed, tokens_left = redis.eval (SCRIPT, keys, args) Fluxflux = this.redisTemplate.execute (this.script, keys, scriptArgs); / / .log ("redisratelimiter", Level.FINER) Return flux.onErrorResume (throwable-> Flux.just (Arrays.asList (1L,-1L)). Reduce (new ArrayList (), (longs, l)-> {longs.addAll (l); return longs }) .map (results-> {boolean allowed = results.get (0) = = 1L; Long tokensLeft = results.get (1) Response response = new Response (allowed, getHeaders (routeConfig, tokensLeft)) If (log.isDebugEnabled ()) {log.debug ("response:" >

The above blogger intercepts the key code of the current limit part of the Spring gateway. As you can see, the most important thing is to execute a lua script using reids, and then judge whether the traffic is passed by whether the return value [0] is equal to 1. The return value [1] is the number of tokens remaining in the token bucket. The above code does not see any shadow of the token bucket algorithm, right? all the essential implementations are in the request_rate_limiter.lua script, which was originally shared by Paul Tarjan, and the source address pokes me. The script is as follows:

Local tokens_key = KEYS [1] local timestamp_key = KEYS [2] local rate = tonumber (ARGV [1]) local capacity = tonumber (ARGV [2]) local now = tonumber (ARGV [3]) local requested = tonumber (ARGV [4]) local fill_time = capacity/ratelocal ttl = math.floor (fill_time*2) local last_tokens = tonumber (redis.call ("get", tokens_key)) if last_tokens = nil then last_tokens = capacityendlocal last_refreshed = tonumber (redis.call ("get") Timestamp_key) if last_refreshed = = nil then last_refreshed = 0endlocal delta = math.max (0, now-last_refreshed) local filled_tokens = math.min (capacity, last_tokens+ (delta*rate)) local allowed = filled_tokens > = requestedlocal new_tokens = filled_tokenslocal allowed_num = 0if allowed then new_tokens = filled_tokens-requested allowed_num = 1endredis.call ("setex", tokens_key, ttl, new_tokens) redis.call ("setex", timestamp_key, ttl, now) return {allowed_num, new_tokens}

Let's analyze the script line by line. First of all, explain the specific meaning of these attributes that are included in the application:

Tokens_key: the identification of the current current limit, which can be ip or, in a spring cloud system, the serviceID of a service

Timestamp_key: the timestamp of the token bucket refresh, which will be used to calculate the number of tokens currently generated

Rate: rate at which tokens are produced, such as 50 tokens per second

Capacity: the size of the token bucket, such as a maximum of 100. then the system can hold a maximum of 100concurrent requests.

Now: current timestamp

Requested: the number of tokens currently requested. The default in Spring Cloud Gateway is 1, that is, the current request.

The following is the main logical analysis:

-- calculate how long it will take to fill the bucket

-- get twice the time to fill the bucket as the aging time of key in redis to avoid redundant and useless key

It doesn't have much to do with the implementation of the token bucket.

Get the remaining token in the bucket and fill it up if the bucket is empty

-- gets the last refresh time of the current token bucket. If empty, it is set to 0.

-- calculate the time difference between the last token refresh and the current time

-- calculate the current number of tokens, this place is the most critical place, through the number of remaining tokens + tokens generated within the time difference to get the current total number of tokens

-- sets whether the number of tokens in the current token bucket received by allowad is greater than the requested token result

-- sets the current number of tokens

-- if allowed is true, reset the current number of tokens to the number of tokens in the pass-the number of tokens requested, and set the allowed_num identity to 1

-writes the current number of tokens back to redis and resets the last refresh time of the token bucket

-returns whether a token has been applied for and how many tokens are left in the current bucket

So much for sharing a script in Spring Cloud Gateway about how to implement a token bucket. I hope the above content can be of some help and learn more knowledge. If you think the article is good, you can share it for more people to see.

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.