Current limit algorithm

Counter:

The counter is relatively simple and crude, for example, we want to limit the number of requests that can pass 1s, the idea of implementation is to start the timer from the first request in, in the next 1s, each request in the number of requests +1, the request exceeding the maximum number of requests will be rejected, until the end of 1s count zero, start counting again.

This approach has a major drawback: for example, if the maximum number of requests has been passed in the first 10ms, the subsequent 990ms requests can only be rejected. This phenomenon is called “spike”.

Leaky bucket algorithm:

That is, the speed of water outlet at the bottom of the bucket is constant, the speed of water intake may be different, but when the amount of water into the bucket is greater than the amount of water, the water will be placed in the bucket, will not be directly discarded; But there is a limit to the bucket’s capacity, and when the bucket is filled with water, any overflow is discarded.

Algorithm implementation: A queue can be prepared to hold temporarily unprocessed requests, and then a thread pool can periodically fetch requests from the queue for execution.

Token bucket algorithm:

A token bucket is a place where access tokens are produced at a constant rate. Users can access tokens when there are tokens in the bucket. Otherwise, traffic limiting is triggered.

Implementation solution: Guava RateLimiter Stream limiting

Guava RateLimiter is a Google-provided stream limiting algorithm that is based on the token bucket algorithm and is suitable for single-instance systems.

Specific implementation of current limiting

Gateway traffic limiting:

Spring Cloud Gateway provides RequestRateLimiterGatewayFilterFactory class, this is based on the realization of the token bucket. It has RedisReteLimiter built in and relies on Redis to store limiting configurations and statistics, which we can also inherit

Org. Springframework. Cloud. Gateway. Filter. Ratelimit. AbstractRateLimiter or implementation

Org. Springframework. Cloud. Gateway. Filter. Ratelimit. To achieve their own RateLimiter RateLimiter interface.

The concrete implementation is as follows:

1. First introduce dependencies into the gateway service

2. The configuration is as follows

3. Traffic limiting based on three dimensions can be realized:

The configuration shown above generates 1 token per second and returns a status code of 429 when our request speed is greater than that

redis+lua

1. Introduce lua scripts into the service

2. Read the lua

3. Determine whether the stream limiting code is required

4. We can see above that normally only 3 tokens are generated within 10s. Let’s take a look at the effect

You can see that within 10 seconds only the first three requests are approved, the rest are rejected, and after 10 seconds, three more requests are approved, which is exactly what we expected.

Nginx current-limiting

Limit access frequency:

Nginx can use the ngx_HTTP_limit_req_module parameter to limit access frequency, using the leaky bucket algorithm implementation; The limit_req_zone command and the limit_req command can limit the request processing frequency for a single IP address.

Limit connection number:

The ngx_HTTP_limit_conn_module module provides the function of the number of concurrent connections. You can configure the limit_conn_zone command and limit_conn command based on the leak-bucket algorithm.

In addition to writing the article behind the author will maintain an open source project, so students with source code needs can pay attention to mumu, it is expected to open during the Spring Festival this year.