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

Most people don't understand the knowledge points of this article "Token bucket current limiting algorithm example analysis in Spring Cloud Gateway", so Xiaobian summarizes the following contents for everyone. The content is detailed, the steps are clear, and it has certain reference value. I hope everyone can gain something after reading this article. Let's take a look at this article "Token bucket current limiting algorithm example analysis in Spring Cloud Gateway".

preface

Current limiting is a function point that cannot be ignored in the design of a distributed high concurrency system. If we don't effectively restrict the traffic access to the system, it is easy to bring down our system in the case of double eleven and ticket rush. As the guard of system service, gateway component, as the uniform entrance of system service, needs to consider the traffic restriction more, and it is more appropriate to block traffic directly in gateway layer than in each system. In the implementation of Spring Cloud Gateway, the current limiting function is provided. The following is a main analysis of how to implement the current limiting function in Spring Cloud Gateway.

Review Current Limiting Algorithm

There are many ways to implement current limiting. Here are a few common implementation algorithms.

counter/time window method

This kind of current-limiting algorithm is the simplest and the easiest to realize. By setting the maximum number of visits per unit time, the purpose of current-limiting can be achieved. For example, if the qps that a certain system can carry is 60, then we can use the calculator method to limit the interface to only 60 accesses per second. But this algorithm implementation, just like its functional description, has a flaw. If traffic peaks in the first 1% of the time window, then 99% of the time the system will be blocked by this flaw in the current limiting algorithm, even if it can continue to provide service. This flaw is also called "spike effect".

leaky bucket method

Leaky bucket method is different from calculator method, it effectively avoids the "spike effect" defect of counter method current limiting, and its implementation is not complicated, it can be realized by fixed size queue + timing queue element fetching. As its name implies, a leaky bucket is like a container containing water. The leaky bucket method only limits the rate at which the container can be discharged. When the rate of water inflow is too high, it will fill the container and cause overflow. The flow rate of the overflow part is also the rejected flow rate. For example, if the container size is 100 and the outflow rate is 10/s, when the bucket is empty, the maximum flow rate can reach 100/s, but even then, limited by the fixed outflow rate, the backend can only process a maximum of 10 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. It cannot really deal with sudden flow peaks and is not efficient.

token bucket method

Token bucket is also a bucket-based prototype, but unlike leaky bucket algorithms, there is no outlet. Token bucket flow is controlled by token generation rate + token bucket volume, which effectively solves the problem of low efficiency of leaky bucket. For example, a bucket with a volume of 100 and a token generation rate of 50/s means that when the bucket is full of tokens, it can carry a maximum of 100 traffic. If the traffic remains high, it will also process requests at a constant rate of 50 traffic per second. This characteristic of token bucket can effectively deal with peak flow and can not be crushed by peak flow, which is a common method to realize current limiting. A well-known implementation is RateLimiter in Google guava. Then the Spring Cloud Gateway that will be analyzed below is also the current limit implemented by the token bucket algorithm

Token buckets in Spring Cloud Gateway

Spring Gateway is a gateway distributed current limiting based on token bucket +redis. For specific implementation, see the following two codes:

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: " + response); } return response; }); }

The blogger above intercepted the key code of the Spring Gateway traffic limiting part. As you can see, the most critical point is that a lua script is executed using reids, and then whether the traffic passes this time is judged 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 essence of the implementation is in the lua script, which was originally shared by Paul Tarjan. 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 }

Here is a line-by-line analysis of this script. First of all, explain the specific meaning of these attributes that come in from the application:

tokens_key: identifier of current limit, which can be ip, or in spring cloud system, it can be serviceID of a service

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

rate: The rate at which tokens are produced, e.g. 50 tokens per second

capacity: the capacity of the token bucket, such as a maximum of 100, then the system can support a maximum of 100 concurrent requests

now: current time stamp

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

primary logic analysis

--Calculate how long it takes to fill the bucket

--Get twice the time to fill the bucket as the key aging time in redis to avoid too many redundant useless keys

--This has nothing to do with the implementation of token buckets.

--Get the remaining tokens in the bucket and fill it if the bucket is empty

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

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

--Calculate the current token count, this is the most critical place, the current total token count is obtained by the number of remaining tokens + tokens generated within the time difference

--Set ID allowad to receive whether the number of tokens in the current token bucket is greater than the token requested result

--Set current token count

--If allowed is true, reset the current token count to token count in pass-token count requested, and set allowed_num flag to 1

--Write the current token count back to redis and reset the last refresh time of the token bucket

--Returns whether tokens have been applied for and how many tokens remain in the current bucket

The above is about the content of this article "Token bucket current limiting algorithm example analysis in Spring Cloud Gateway". I believe everyone has a certain understanding. I hope the content shared by Xiaobian will be helpful to everyone. If you want to know more relevant knowledge, please pay attention to the industry information channel.

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.