Sort out some common traffic limiting algorithms

  • Token bucket algorithm

    The idea behind the token bucket algorithm is if you want to limit QPS to 1000. So, set up a bucket with a capacity of 1000 and put tokens into the bucket every 1/1000 second at a constant rate. After each request is reached, you need to determine whether there are tokens in the bucket. If so, process the request; If not, refuse service or wait.

    In real development, because of the accuracy or efficiency of the timer, it is not necessary to directly use the strategy of placing one token every 1/1000 second, such as changing to a strategy of placing 10 tokens every 1/100 second.

  • Leaky bucket algorithm has a bucket (or queue) that continuously puts requests into the queue, and the exit of the queue exits at a constant speed.

The difference between the two algorithms is that the flow rate of the leaky bucket is constant regardless of the flow rate. However, there may be a large number of instantaneous requests in the token bucket. For example, if there are 1000 tokens in the token bucket and 999 requests come in a moment, these requests can be passed instantly. ** Pseudocode for token bucket traffic limiting algorithm:

Int bucket_token_num = 0// Timer timeout callback void rate_limit_timeout(){int add_token = get_add_token_by_cfg(); bucket_token_num += add_token; return; }bool rate_limit_bucket_is_empty(){ if (bucket_token_num <= 0) {return true; } return false; }void rate_limit_dec_bucket_token(){ assert(! rate_limit_bucket_is_empty()); bucket_token_num--; Int process_req(){if (! rate_limit_bucket_is_empty()) { rate_limit_dec_bucket_token(); // do-something }}Copy the code

  • One advantage of using Redis to introduce an additional node for traffic limiting is that distributed traffic limiting can be implemented by default. A key is maintained on redis as the number of requests that have been processed.

    Redis is used to limit traffic, using a synchronous interface. Each request needs to be held before it is determined whether to limit traffic or not. Check redis synchronously to see if it can be processed.

    There is another option, which can be pre-allocated. There is a central node (QPS =1000), suppose there are 3 nodes, and 50 nodes are pre-allocated to each node and 30 are reserved. When requests come in, they are deducted directly from the pre-allocated pool, and when requests start using tokens from the standby pool, the nodes start asking the central node for quotas again.

    This kind of pre-allocation scheme is relatively efficient, which introduces a problem. If a large number of requests come to a node instantly, and all the pre-allocated tokens and standby tokens are consumed on the node, the processing of the requests will be stuck before the quota applied by the node again arrives.

  • cur_num = tonumber(redis.call('get', key) or "0")if (cur_num + 1 >= limit_num){ return -1; Redis. call('INCRBY', key, 1); redis.call('INCRBY', key, 1); If (cur_num == 0) {redis. Call ('EXPIRE', key, TTL)} return 0; // unrestricted}Copy the code

Some related references:

  1. www.cyhone.com/articles/an…

  2. Chai2010. Cn/advanced – go…

  3. Github.com/yangwenmai/…

  4. Pandaychen. Making. IO / 2020/09/21 /…

​