Why do we have to limit the flow

First of all, let’s take a look at why we should do “flow limiting” in system architecture design.

Tourist attractions there are usually the largest hotels “, could not have unlimited put tourists to enter, like the Forbidden City every day to sell eighty thousand tickets, only more than eighty thousand tourists, can’t buy a ticket to enter, because if the more than eighty thousand people, scenic spot of staff may be busy not to come over, overcrowded attractions may also affect tourists’ experiences and feelings, there will be a safety hazard; “Only selling N tickets is a way to limit traffic.”

Service flow limiting in software architecture is similar. When the system resources are insufficient, it can no longer cope with a large number of requests. In order to ensure the normal operation of services, according to the rules, “the system will directly reject the redundant requests to achieve the effect of flow limiting”.

I don’t know if you have noticed, for example, on Double 11, just after 12 o ‘clock, some customers’ websites or apps will show the warning of failure to place orders, and some of them are blocked.

Common traffic limiting algorithms

Counting method

For example, I can only handle 1000 requests per minute. Then we can set a counter, incr+1 for each request. When the number of requests in 1 minute is greater than or equal to 1000, no processing can be done

$redis = new Redis(); $redis - > connect (127.0.0.1, 6379); $rate_limit = 1000; $rate_seconds = 60; $redis_key = "redis_limit"; $count = $redis->get($redis_key); If ($count >= $rate_limit){return $redis->incr($redis_key, 1); $redis->expire($redis, $rate_seconds); // Set the expiration time to 60s//to do Service logic processing.......Copy the code

This counting method is relatively simple and quick, but it has a big disadvantage, because the request access is not necessarily smooth, if 0:59 1000 requests come, 1:01 is the next window, another 1000 requests come, but in fact 2000 requests come in three seconds, already exceeded our traffic limit. So this method is not recommended.

Sliding window algorithm

Take the example above, one minute in six parts, 10 seconds each; Every 10 seconds, our time window will slide one grid to the right, each grid has an independent counter, we calculate the number of time window each time, can solve the problem in the counter method, and when the sliding window more grids, the more accurate the statistics will be. Specific can refer to figure below, see a picture is clearerThe pseudo-code implementation is as follows

function api_limit($scene, $period, $maxCount){ $redis = new Redis(); $redis - > connect (127.0.0.1, 6379); $key = sprintf('hist:%s', $scene); $now = msecTime (); $pipe=$redis->multi(PIPELINE ::PIPELINE); $pipe->zadd($key, $now, $now); $pipe-> zremrangebyScore ($key, 0, $now - $period); $pipe->zcard($key); $pipe->zcard($key); $pipe->expire($key, $period/1000 + 1); $replies = $pipe->exec(); return $replies[2] <= $maxCount; }for ($I =0; $replies[2] $replies $i<20; $i++){var_dump(isActionAllowed("uniq_scene", 60*1000, 5)); Function msectime() {list($msec, $SEC) = explode(' ', microtime()); $msectime = (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000); return $msectime; }Copy the code

This code is still a bit complex and will take some time to digest. The whole idea is to maintain a time window for each action as it comes in. All the records outside the time window are cleared, and only the records inside the window are kept.

Because these several consecutive Redis operations are for the same key, using pipeline can significantly improve Redis access efficiency. “However, this scheme also has disadvantages, because it needs to record all behaviors in the time window. If the amount is very large, such as limiting the operation to 100W times within 60 seconds, it is not suitable for such limiting, because it will consume a lot of storage space.”

There are also leaky bucket algorithm and token bucket algorithm behind, because their implementation is more complex, so I plan to open a new article to describe separately