background

This article has studied the use of RateLimiter stream limiting plug-in in Soul gateway framework, and analyzed its source code implementation.

The classical traffic limiting algorithms include token bucket algorithm and funnel algorithm.

The RateLimiter plug-in realizes the token bucket algorithm through Redis + Lua to complete the distributed traffic limiting function. This article will understand the token bucket algorithm in depth.

Token bucket algorithm

  • Referring to the article on Flow Control by Professor Tang Yang, the basic principle of token bucket algorithm is as follows:

    • To limit the number of accesses per second to N, a token needs to be placed in the bucket every 1/n;

    • When the request arrives, it needs to obtain a token from the bucket first. If there is no token in the bucket, it needs to wait for a new token or refuse service directly.

    • You need to limit the total number of tokens, M. If the limit is exceeded, no new tokens can be added to the bucket.

      — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — image — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

  • The RateLimiter plugin in the Soul gateway framework has two values for limiting traffic:

    • Current limiting rate: Number of requests per second, corresponding to N above;
    • Current limiting capacity: The capacity of the token bucket, corresponding to M above;

  • Why limit the capacity of the token bucket?

    • If the rate of requests is lower than the rate at which tokens are placed, the number of token buckets increases; It is necessary to set a quantity threshold close to the server processing limit, so as to avoid the problem of instantaneous traffic peak to some extent.

  • When implementing the token bucket algorithm, you don’t need to actually create a thread to do the job of putting tokens in, but instead calculate whether there are currently any tokens based on the number of remaining tokens and the time difference. The implementation in the Soul gateway framework is as follows:

    Checksum local last_refreshed = tonumber(redis.call("get", timestamp_key)) //... Checksum local delta = math.max(0, now-last_refreshed) //... -- min(capacity, last_tokens+(delta*rate)) = number of tokens Local filled_tokens = math.min(capacity, last_tokens+(delta*rate))Copy the code

conclusion

  • Traffic limiting is a service protection policy that smoothen the flow. However, in practice, the determination of traffic limiting value is based on the estimation of services on the one hand, and the capacity limit of the system on the other hand, so it generally needs to be adjusted dynamically. Teacher Chen Hao mentioned dynamic current limiting in the article of current limiting design, which can dynamically sense the pressure of the system to achieve automatic flow control;

  • The monitoring and alarm setting of traffic limiting is very important. Through traffic limiting monitoring, the flow changes of the system can be quickly obtained, and timely investigation is needed.

  • The number of requests processed by token bucket algorithm in a fixed unit time does not exceed the number of issued tokens, so it plays a role of traffic limiting.

  • The token bucket algorithm obtains a token every time it obtains a request, which may increase the request delay. A compromise strategy is to obtain a batch of tokens every time to reduce the number of Redis requests.

  • There are various response processing for limiting flow, such as

    • Refuse service, directly return a code, such as when receiving coupons prompt you “too many requests, try again later”;
    • Service degradation, such as returning a bottom-of-the-pocket data;

series

  • Soul source learning [1] – preliminary exploration
  • Soul source learning [2] – divide load balancing plug-in
  • Soul source learning [3] – Dubbo plug-in
  • Soul source learning [4] – RateLimiter stream limiting plug-in
  • Soul source learning [5] – SpringCloud plug-in
  • Soul source learning [6] – Chain of responsibility mode
  • Soul source learning [7] – Data synchronization strategy websocket synchronization
  • [8] – Data synchronization strategy for ZooKeeper synchronization
  • [9] – ZooKeeper Synchronization (2)
  • Soul source learning [10] – Observer mode application
  • Soul source learning [11] – Data synchronization strategy HTTP long poll synchronization
  • Soul source learning [12] – Data Synchronization strategy HTTP long Poll synchronization (2)
  • Soul source learning [13] – data synchronization strategy comparison
  • Soul source learning [14] – Deep into divide plug-in
  • Soul source learning [15] – Deep divide plug-in (2)