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

Recently, I wrote a current-limiting plug-in, so I can't avoid coming into contact with some current-limiting algorithms. This article will analyze these common current limiting algorithms.

Before the analysis

As far as I understand it, current restriction should be flexible enough to be done for each interface. For example, if there are five interfaces in a class, then my current-limiting plug-in should be able to have a different current-limiting scheme for each interface. So, since each interface is targeted, you need a key that uniquely identifies this interface (I take the class name + method name + input parameter).

It is highly recommended to use redis+lua or nginx+lua for distributed current restriction.

Here we use two current-limiting conditions as examples to talk about common current-limiting algorithms:

Interface 1 allows a maximum of 100 visits in 10 seconds.

Interface 2 allows a maximum of 100 visits per person in 10 seconds.

Counter algorithm

This algorithm can be said to be the simplest of the current-limiting algorithms.

Core thought

The counter algorithm means that when an interface is accessed in a unit of time, I write down the number of visits until it reaches the upper limit.

Involved variable

Interface (key)

Unit of time (expire)

How many visits are allowed (limit)

Number of visits (value)

Condition one

When a request comes, we get the key.

one

two

three

four

five

six

seven

eight

nine

If (key exists) {

Value++

If (value > = limit) {

No access

}

} else {

Add key,value to 1

Set key expiration time to expire

}

Condition two

Now that condition one has been realized, will condition two be complicated?

Compared to condition 1, there are multiple users corresponding to the same key. Then we just need to add the key to the user's information. For example, key_ user 1, key_ user 2.

Core idea of leaky Bucket algorithm

The leaky bucket algorithm means that the number of times an interface is allowed to be accessed in a unit of time varies dynamically (if 60 visits are allowed in a minute, then only 59 visits are allowed in 59 seconds and 30 visits in 30 seconds, regardless of whether they are accessed or not). Why is that? because there is another thread doing the decrement operation.

Involved variable

Interface (key)

Unit of time (expire)

How many visits are allowed (limit)

Decreasing interval time (interval)

Decreasing step size (step)

Remaining accessible times (value)

Access time of key (lastUpdateTime)

Current time (nowTime) (note that the value of nowTime should be the time obtained by the application, not the time obtained by redis or nginx)

Condition one

Thread one:

one

two

three

four

five

six

seven

eight

If (key exists) {

Value--

If (valueinterval) {

Value=value- (nowTime-lastUpdateTime) / interval*step

LastUpdateTime=nowTime

}

If (value=limit) {

No access

}

} else {

Add key and set value to limit

}

Thread two:

one

two

three

While (past interval time) {

Value+step of all key

}

Condition two

Reference calculator algorithm condition 2 implementation.

Algorithm upgrade

Reference leaky bucket algorithm upgrade implementation.

Code

For code implementation, please refer to my current-limiting framework https://github.com/shiyujun/syj-ratelimit.

This article is from http://zhixiang.org.cn. Please keep it when reproduced.

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.