How to limit flow of api interface in php

What is interface current limiting?

So what is current limiting? As the name suggests, current limiting is to limit traffic, including concurrent traffic and total traffic within a certain period of time. Just like your broadband package has 1 G of traffic, it will be gone after it is used up, so control your frequency of use and the total traffic in a single time. consumption. Through current limiting, we can well control the qps of the system, thereby achieving the purpose of protecting the stability of the system or interface server.

Commonly used algorithms for interface current limiting

Counter method

The counter method is the simplest and easiest among the current limiting algorithms An algorithm implemented. For example, we stipulate that for interface A, the number of accesses in one minute cannot exceed 100. Then we can do this: at the beginning, we can set a counter counter. Whenever a request comes, the counter will be increased by 1. If the value of counter is greater than 100 and the interval between the request and the first request is still Within 1 minute, it means there are too many requests; if the interval between the request and the first request is greater than 1 minute, and the value of counter is still within the current limit range, then reset counter. The schematic diagram of the specific algorithm is as follows ：

The pseudo code is as follows:

class CounterDemo{
    private  $timeStamp;
    public  $reqCount=0;
    public  $limit=100;//时间窗口内最大请求数
    public $interval=1000; //时间窗口 ms
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        if($now<$this->timeStamp+$this->interval){
            //时间窗口内
            $this->reqCount++;
            return $this->reqCount<=$this->limit;
        }else{
            // 超时后重置
            $this->timeStamp=time();
            $this->reqCount=1;
            return true;
        }
    }
}

This algorithm looks simple but has a very serious problem, which is the criticality problem. See the picture below:

We can see from the picture above that assuming there is a malicious user, he sends 100 requests instantly at 0:59, and again at 1:00 received 100 requests, then this user actually sent 200 requests in 1 second. What we just stipulated is a maximum of 100 requests per minute, which is a maximum of 1.7 requests per second. Users can exceed our rate limit instantly by making burst requests at the reset node of the time window. Users may use this loophole in the algorithm to instantly overwhelm our application.

Related recommendations: "php tutorial"

Smart friends may have noticed that the problem just now is actually because the accuracy of our statistics is too low. So how to deal with this problem well? In other words, how to reduce the impact of critical problems? We can look at the sliding window algorithm below.

Sliding window algorithm

#In the above figure, the entire red rectangular box represents a time window, in our example , a time window is one minute. Then we divide the time window. For example, in the figure, we divide the sliding window into 6 grids, so each grid represents 10 seconds. Every 10 seconds, our time window will slide one frame to the right. Each grid has its own independent counter. For example, when a request arrives at 0:35 seconds, the corresponding counter from 0:30 to 0:39 will be incremented by 1.

So how does the sliding window solve the critical problem just now? We can look at the picture above. The 100 requests arriving at 0:59 will fall in the gray grid, while the requests arriving at 1:00 will fall in the orange grid. When the time reaches 1:00, our window will move one space to the right. Then the total number of requests in the time window at this time is 200, exceeding the limit of 100, so it can be detected that the current limit is triggered at this time. .

Let me review the counter algorithm just now. We can find that the counter algorithm is actually a sliding window algorithm. It's just that it doesn't further divide the time window, so there is only 1 grid.

It can be seen that when the grid of the sliding window is divided into more, the rolling of the sliding window will be smoother, and the statistics of current limiting will be more accurate.

Leaky bucket algorithm

Leaky bucket algorithm, also known as leaky bucket. In order to understand the leaky bucket algorithm, let's take a look at the schematic diagram of the algorithm on Wikipedia:

From the figure we can see that the entire algorithm is actually very simple. First, we have a bucket with a fixed capacity, with water coming in and water going out. For water flowing in, we cannot predict how much water will flow in, nor how fast the water will flow. But for the water flowing out, this bucket can fix the rate at which the water flows out. Also, when the bucket is full, the excess water will overflow.

We replace the water in the algorithm with requests in actual applications. We can see that the leaky bucket algorithm inherently limits the speed of requests. When using the leaky bucket algorithm, we can ensure that the interface will process requests at a constant rate. Therefore, the leaky bucket algorithm inherently does not have criticality problems. The specific pseudocode implementation is as follows:

class LeakyDemo{
    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 水漏出的速度
    public  $water;// 当前水量(当前累积请求数)
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->water=max(0,$this->water-($now-$this->timeStamp)*$this->rate);// 先执行漏水，计算剩余水量
        $this->timeStamp=$now;
        if(($this->water+1)<$this->capacity){
            // 尝试加水,并且水还未满
            $this->water+=1;
            return true;
        }else{
            // 水满，拒绝加水
            return false;
        }
    }
}

Token Bucket Algorithm

令牌桶算法，又称token bucket。为了理解该算法，我们再来看一下维基百科上对该算法的示意图：

从图中我们可以看到，令牌桶算法比漏桶算法稍显复杂。首先，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

具体的伪代码实现如下：

class TokenBucketDemo{
    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 令牌放入的速度
    public  $tokens;// 当前令牌的数量
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->tokens=min(0,$this->tokens+($now-$this->timeStamp)*$this->rate);// 先执行漏水，计算剩余水量
        $this->timeStamp=$now;
        if($this->tokens<1){
            // 若不到1个令牌,则拒绝
            return false;
        }else{
            // 还有令牌，领取令牌
            $this->tokens -= 1;
            return true;
        }
    }
}

临界问题

我们再来考虑一下临界问题的场景。在0:59秒的时候，由于桶内积满了100个token，所以这100个请求可以瞬间通过。但是由于token是以较低的 速率填充的，所以在1:00的时候，桶内的token数量不可能达到100个，那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问题。下图比较了计数器（左）和令牌桶算法（右）在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率，但是下一个突发速率必须要等桶内有足够的token后才能发生。

总结

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。

The above is the detailed content of How to limit flow of api interface in php. For more information, please follow other related articles on the PHP Chinese website!