Before the analysis

In my opinion, limiting traffic should be flexible enough to be done for each interface. For example, if there are five interfaces in a class, my stream limiting plug-in should be able to create different limiting schemes for each interface. So, for each interface, we need a key that uniquely identifies the interface (I took the class name + method name + input parameter).

It is highly recommended to use Redis + Lua or Nginx + Lua for distributed traffic limiting.

Here we use two traffic limiting conditions as examples to describe common traffic limiting algorithms:

  1. Interface 1 Allows a maximum of 100 accesses per 10 seconds

  2. Interface 2 it allows a maximum of 100 accesses per person per 10 seconds. Counter algorithm This algorithm can be said to be the simplest algorithm in the limiting algorithm.

core idea

What the counter algorithm means is that when an interface is accessed in a unit of time, I keep track of the number of accesses until it reaches an upper limit.

Involving variable

  1. Interface (Key)

  2. Time unit (expire)

  3. How many accesses are allowed (limit)

  4. Number of visits (value)

Conditions for a

When a request comes in, we get this key.

if(key exists){value++;if(value>=limit){cannot access}}else{add key, value 1; set key expiration time to expire}Copy the code

Condition 2

Now that condition one is already fulfilled, is condition two complicated?

Compared with condition 1, the same key corresponds to multiple users. So we just need to add the key to the user’s information. For example, key_ user 1 and key_ user 2.

Bucket algorithm

core idea

Leaky bucket algorithm means that the number of times an interface is allowed to be accessed dynamically in a unit of time (if 60 times are allowed in a minute, then only 59 times are allowed in 59 seconds and only 30 times are allowed in 30 seconds from the start of the timing, regardless of whether the interface is accessed or not). Why is that? Because there’s another thread doing decrement

Involving variable

  1. Interface (Key)

  2. Time unit (expire)

  3. How many accesses are allowed (limit)

  4. Decreasing interval (interval)

  5. Decreasing step size (step)

  6. Remaining number of accessible times (value)

  7. Access time (lastUpdateTime)

  8. The current time (nowTime) (note that nowTime should be the time obtained by the application, not the time obtained by Redis or nginx)

Conditions for a

Thread one:

if(key exists){value--;if(value<=0){cannot access}}else{add key and set value tolimit
   }
Copy the code

Thread 2:

while(past interval time){value step for all keys}Copy the code

Condition 2

Reference counter algorithm condition two implementation.

Algorithm to upgrade

It can be seen that the leaky bucket algorithm requires another thread to traverse the value of the key every interval to do the decrement operation, so is there any way to omit this step? The answer is yes.

if(key exists){value--;if((nowtime-lastupdatetime) >interval) {value=value- (nowtime-lastupdatetime) /interval*step; lastUpdateTime=nowTime; }if(value<=0){cannot access}}else{add key and set value tolimit; LastUpdateTime = nowTime; }Copy the code

Token bucket algorithm

core idea

The token bucket algorithm is the opposite of the leaky bucket algorithm, but it’s recommended. I’m not going to tell you how this algorithm works, but I think you’re smart enough to see the pseudo-code.

Involving variable

  1. Interface (Key)

  2. Time unit (expire)

  3. How many accesses are allowed (limit)

  4. Increasing interval (interval)

  5. Increasing step (step)

  6. Current Number of accesses (value)

  7. Access time (lastUpdateTime)

  8. NowTime (refer to leaky bucket algorithm)

Conditions for a

Thread one:

if(key exists){value++;if(value>=limit){cannot access}}else{add key and set value tolimit
   }
Copy the code

Thread 2:

while(past interval time){all key values +step}Copy the code

Condition 2

Reference calculator algorithm condition two implementation.

Algorithm to upgrade

Refer to the leaky bucket algorithm to upgrade.

code

Code implementation please refer to my limiting framework (click below to read the original text directly) :

https://github.com/2388386839/syj-ratelimit