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

Current limiting algorithm token bucket algorithm

The idea of the algorithm is:

Tokens are generated at a fixed rate and cached in the token bucket; when the token bucket is full, excess tokens are discarded; requests consume an equal proportion of tokens before they can be processed; when there are not enough tokens, requests are cached. Leaky bucket algorithm

The idea of the algorithm is:

The water (request) is poured into the bucket from above and flows out from the bottom of the bucket (treated); the water that does not flow out in time is stored in the bucket (buffer) and flows out at a fixed rate; when the bucket is full, it overflows (discarded). The core of this algorithm is: cache requests, uniform processing, and redundant requests are discarded directly.

Compared with the leaky bucket algorithm, the token bucket algorithm is different in that it not only has a "bucket", but also has a queue, which is used to store tokens, and the queue is used to store requests.

In terms of function, the most obvious difference between the leaky bucket algorithm and the token bucket algorithm is whether it allows the processing of burst traffic (burst). The leaky bucket algorithm can forcibly limit the real-time transmission rate of data without additional processing, while the token bucket algorithm can allow a certain degree of burst transmission while limiting the average transmission rate of data.

The Nginx speed limit module uses the leaky bucket algorithm, that is, it can forcibly ensure that the real-time processing speed of the request will not exceed the set threshold.

The official version of Nginx restricts the connection and concurrency of IP to have two modules:

Limit_req_zone is used to limit the number of requests per unit time, that is, rate limit, using the leaky bucket algorithm "leaky bucket". Limit_req_conn is used to limit the number of connections at a time, that is, the concurrency limit. Limit_req_zone parameter configuration Syntax: limit_req zone=name [burst=number] [nodelay]; Default:-Context: http, server, location

Limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s

The first parameter: $binary_remote_addr indicates that the limit is made by the remote_addr identity. The purpose of "binary_" is to abbreviate the memory usage and to limit the same client ip address. The second parameter: zone=one:10m means to generate a 10m memory area named one, which is used to store access frequency information. The third parameter: rate=1r/s means the access frequency of clients with the same identity is allowed, which is limited to once per second, and there can also be, for example, 30r/m.

Limit_req zone=one burst=5 nodelay

The first parameter: zone=one sets which configuration area to use as the limit, corresponding to the name in the limit_req_zone above. The second parameter: burst=5, focus on this configuration, the meaning of burst burst, this configuration means to set a buffer of size 5 when there are a large number of requests (outbreaks) coming, requests that exceed the access frequency limit can be put into this buffer first. The third parameter: nodelay, if set, will directly return 503 if the access frequency is exceeded and the buffer is full, if not set, all requests will be queued.

Example:

Http {limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s; server {location / search/ {limit_req zone=one burst=5 nodelay;}}

The following configuration restricts access to specific UA, such as search engines:

Limit_req_zone $anti_spider zone=one:10m rate=10r/s;limit_req zone=one burst=100 nodelay;if ($http_user_agent ~ * "googlebot | bingbot | Feedfetcher-Google") {set $anti_spider $http_user_agent;}

Other parameters

Syntax: limit_req_log_level info | notice | warn | error;Default: limit_req_log_level error;Context: http, server, location

When the server is speed-limited or cached due to limit, the configuration writes to the log. Delayed records are one level lower than rejected records. Example: the delay of limit_req_log_level notice is basically info.

Syntax: limit_req_status code;Default: limit_req_status 503; context: http, server, location

Sets the return value for rejecting the request. The value can only be set between 400 and 599.

Ngx_http_limit_conn_module parameter configuration

This module is used to limit the number of requests for a single IP. Not all connections are counted. Connections are counted only if the server has processed the request and has read the entire request header.

Syntax: limit_conn zone number;Default:-Context: http, server, locationlimit_conn_zone $binary_remote_addr zone=addr:10m;server {location / download/ {limit_conn addr 1;}

Only one connection per IP address is allowed at a time.

Limit_conn_zone $binary_remote_addr zone=perip:10m;limit_conn_zone $server_name zone=perserver:10m;server {... Limit_conn perip 10; limit_conn perserver 100;}

Multiple limit_conn instructions can be configured. For example, the above configuration limits the number of IP connections per client to the server and the total number of connections to the virtual server.

Syntax: limit_conn_zone key zone=name:size;Default:-Context: httplimit_conn_zone $binary_remote_addr zone=addr:10m

Here, the client IP address is the key. Note that instead of $remote_addr, you use the $binary_remote_addr variable. The size of the $remote_addr variable can range from 7 to 15 bytes. The stored state takes up 32 or 64 bytes of memory on a 32-bit platform and always 64 bytes on a 64-bit platform. The size of the $binary_remote_addr variable is always 4 bytes for IPv4 addresses and 16 bytes for IPv6 addresses. The storage state always takes up 32 or 64 bytes on 32-bit platforms and 64 bytes on 64-bit platforms. A megabyte area can maintain a state of about 32000 32 bytes or about 16000 64 bytes. If the zone storage is exhausted, the server returns the error to all other requests.

Syntax: limit_conn_log_level info | notice | warn | error;Default: limit_conn_log_level error;Context: http, server, location

When the server limits the number of connections, set the required logging level.

Syntax: limit_conn_status code;Default: limit_conn_status 503; context: http, server, location

Sets the return value for rejecting the request.

Practical example one: limit the access rate limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;server {location / {limit_req zone=mylimit;}}

The above rule limits the speed of each IP access to 2r/s and applies the rule to the root directory. What happens if a single IP sends multiple requests concurrently in a very short period of time?

We used a single IP to send and send six requests within the 10ms, only one was successful, and the remaining five were rejected. The speed we set is 2r/s, why only one is successful? is the Nginx limit wrong? Of course not, because the current limit statistics of Nginx are based on milliseconds. We set the speed to 2r/s, which means that only one request is allowed for a single IP in the 500ms, and only the second request is allowed from 501ms.

Example 2 burst cache processing

We can see that we have sent a large number of requests in a short period of time. According to the precision of milliseconds, Nginx directly rejects requests that exceed the limit. This is too harsh in the actual scene, the request in the real network environment is not uniform, there is likely to be a request "sudden" situation, that is, "a group". With this in mind, Nginx can turn on caching of burst requests with the burst keyword instead of rejecting them directly.

Take a look at our configuration:

Limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;server {location / {limit_req zone=mylimit burst=4;}}

We have added burst=4, which means that each key (in this case, each IP) allows a maximum of four burst requests. What happens if a single IP sends six requests within 10ms?

Compared with instance-1, the number of successes increased by 4, and the number of burst we set is the same. The specific process is as follows: one request is processed immediately, four requests are placed in the burst queue, and the other request is rejected. Through the burst parameter, we make the Nginx current limit have the ability of cache to deal with burst traffic.

But please note: the purpose of burst is to allow extra requests to be put in the queue first and processed slowly. Without the nodelay parameter, requests in the queue are not processed immediately, but are slowly processed at a precise millisecond speed set by rate.

Example 3 nodelay reduces queuing time

In example 2, we can see that by setting the burst parameter, we can allow Nginx cache to handle bursts to a certain extent, and redundant requests can be put in the queue first and processed slowly, which plays a role in smoothing traffic. However, if the queue is set to a large size, the request queue time will be longer. From the user's point of view, the RT becomes longer, which is very unfriendly to users. Is there any solution? The nodelay parameter allows the request to be processed immediately when it is queued, that is, as soon as the request enters the burst queue, it will be processed by the backend worker immediately. Note that when nodelay is set by burst, the instantaneous QPS of the system may exceed the threshold set by rate. The nodelay parameter must be used with burst to have an effect.

To continue the configuration of example 2, we add the nodelay option:

Limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;server {location / {limit_req zone=mylimit burst=4 nodelay;}}

Six requests are sent concurrently within a single IP 10ms. The results are as follows:

Compared with example 2, the success rate of the request remains the same, but the overall time is shorter. How do you explain that? In example 2, four requests are placed in the burst queue. The worker process takes one request every other 500ms (rate=2r/s) for processing, and the last request has to be queued for 2 seconds before it is processed. In example 3, the request in the queue is the same as in instance 2, but the difference is that the requests in the queue are qualified to be processed at the same time, so the five requests in instance 3 can be said to be processed at the same time, and the time taken is naturally shortened.

Note, however, that although setting burst and nodelay can reduce the processing time of burst requests, it does not increase the upper limit of throughput in the long run. The upper limit of long-term throughput is determined by rate, because nodelay can only guarantee that burst requests are processed immediately, but Nginx limits the release of queue elements, just as it limits the speed at which tokens are generated in a token bucket.

When you see here, you may ask, after adding the nodelay parameter, which speed limit algorithm is a "bucket", a leaky bucket algorithm or a token bucket algorithm? It's a leaky bucket algorithm, of course. Consider a situation where what happens when the token of the token bucket algorithm runs out? Because it has a request queue, the next request is cached, and the cache is limited by the queue size. But does it make sense to cache these requests at this time? If the server is overloaded, the cache queue is getting longer, and the RT is getting higher and higher, even if the request is processed after a long time, it is of little value to the user. So when token is not enough, the wisest thing to do is to reject the user's request directly, which becomes the leaky bucket algorithm.

Example 4 Custom return value limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;server {location / {limit_req zone=mylimit burst=4 nodelay; limit_req_status 598;}}

The status of the status return value is not configured by default:

The status of the custom status return value:

Reference documentation

Nginx limit access rate and maximum number of concurrent connections module-limit (prevent DDOS attacks)

Nginx current limit

On the Speed limit Module of nginx

Nginx source code notes-HTTP module-flow control

Module ngx_http_limit_conn_module

Module ngx_http_limit_req_module

A preliminary study on the Speed limit Module of Nginx

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.