Example Analysis of Classic Current Limiting Algorithm in Java

What is rate limiting?

The concept of Wikipedia is as follows:

In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks and limit web scraping

Simple translation: In computer networks, current limiting is to control the rate at which the network interface sends or receives requests. It can prevent DoS attacks. and limit web crawlers.

Current limiting, also called flow control. It means that when the system faces high concurrency or large traffic requests, it restricts the access of new requests to the system, thereby ensuring the stability of the system. Current limiting will cause some user requests to be processed untimely or be rejected, which affects the user experience. Therefore, it is generally necessary to balance between system stability and user experience. To give an example from daily life:

★

Some popular tourist attractions generally have restrictions on the number of daily visitors. Only a fixed number of tickets will be sold every day, such as 5,000. If you arrive late during the May Day or National Day holidays, the tickets for the day may have been sold out, and you will not be able to go in and play. Even if you get in, the queue will make you doubt your life.

”

Common current limiting algorithm

Fixed window current limiting algorithm

First maintain a counter, treat the unit time period as a window, and the counter records the reception of this window The number of requests.

• When the number is less than the current limit threshold, access is allowed, and counter 1

• When the number is greater than the current limit valve value, access is denied.

• After the current time window has passed, the counter is cleared.

Assuming that the unit time is 1 second, the current limit The threshold is 3. Within 1 second of unit time, every time a request comes, the counter will be incremented by 1. If the accumulated number of times in the counter exceeds the current limit threshold of 3, all subsequent requests will be rejected. After 1s is over, the counter will be cleared to 0 and restarted. Start counting. As shown below:

The pseudo code is as follows:

    /**
     * 固定窗口时间算法
     * @return
     */
    boolean fixedWindowsTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        if (currentTime - lastRequestTime > windowUnit) {  //检查是否在时间窗口内
            counter = 0;  // 计数器清0
            lastRequestTime = currentTime;  //开启新的时间窗口
        }
        if (counter < threshold) {  // 小于阀值
            counter++;  //计数器加1
            return true;
        }

        return false;
    }

However, this algorithm has an obvious critical problem : Assume that the current limiting threshold is 5 requests and the unit time window is 1s. If we concurrently send 5 requests in the first 0.8-1s and 1-1.2s of the unit time. Although they do not exceed the threshold, if calculated 0.8-1.2s, the number of concurrency is as high as 10, which has exceeded the definition of the threshold of not exceeding 5 per unit time 1s.

Sliding window current limit Algorithm

Sliding window current limiting solves the problem of fixed window critical value. It divides the unit time period into n small periods, records the number of accesses to the interface in each small period, and deletes expired ones according to the time sliding Small period.

A picture explains the sliding window algorithm, as follows:

Assuming that the unit time is still 1s, the sliding window algorithm divides it into 5 small periods. The cycle, that is, the sliding window (unit time) is divided into 5 small grids. Each grid represents 0.2s. Every 0.2s, the time window will slide one grid to the right. Then, each small period has its own Independent counter, if the request arrives in 0.83s, the counter corresponding to 0.8~1.0s will be incremented by 1.

Let’s see how the sliding window solves the critical problem?

Assumption Our current limit threshold is still 5 requests within 1 second. Within 0.8~1.0s (for example, 0.9s), 5 requests came, falling in the yellow grid. After the 1.0s point, another 5 requests came The request falls in the purple grid. If is a fixed window algorithm, it will not be current limited, but if is a sliding window, it will move one small grid to the right after every small period. After passing the 1.0s point, it will move a small square to the right. The current unit time period is 0.2~1.2s. The requests in this area have exceeded the limit of 5, and the current limit has been triggered. In fact, purple All grid requests have been rejected.

TIPS: When the grid period of the sliding window is divided into more, the rolling of the sliding window will be smoother, and the current limiting statistics will be more accurate. .

Sliding window algorithmPseudo code implementation is as follows:

 /**
     * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分钟限流请求数
     */
    private int thresholdPerMin = 100;

    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

   /**
     * 滑动窗口时间算法实现
     */
    boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

        //超过阀值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //计数器+1
        counters.get(currentWindowTime)++;
        return true;
    }

   /**
    * 统计当前窗口的请求数
    */
    private int countCurrentWindow(long currentWindowTime) {
        //计算窗口开始位置
        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
        int count = 0;

        //遍历存储的计数器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 删除无效过期的子窗口计数器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加当前窗口的所有计数器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }

Although the sliding window algorithm solves the critical problem of fixed window, once the current limit is reached Afterwards, the request will be rejected directly and violently. Jiangzi, we will lose part of the requests, which is actually not very friendly to the product.

Leaky Bucket Algorithm

The leaky bucket algorithm is more flexible when faced with current restrictions, and there is no direct and violent rejection.

Its principle is very simple, it can be thought of as the process of water injection and leakage. Water flows into the leaky bucket at any rate and water flows out at a fixed rate. When the water exceeds the capacity of the bucket, it will be overflowed, that is, discarded. Because the bucket capacity remains unchanged, the overall speed is guaranteed.

• The inflowing water droplets can be regarded as requests to access the system. The inflow rate is uncertain.

• 桶的容量一般表示系统所能处理的请求数。

• 如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）

• 流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。

漏桶算法伪代码实现如下：

 /**
     * 每秒处理数（出水率）
     */
    private long rate;

    /**
     *  当前剩余水量
     */
    private long currentWater;

    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 桶容量
     */
    private long capacity;

    /**
     * 漏桶算法
     * @return
     */
    boolean leakybucketLimitTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
        long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
        refreshTime = currentTime; // 刷新时间

        // 当前剩余水量还是小于桶的容量，则请求放行
        if (currentWater < capacity) {
            currentWater++;
            return true;
        }
        
        // 当前剩余水量大于等于桶的容量，限流
        return false;
    }

在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。

令牌桶算法

面对突发流量的时候，我们可以使用令牌桶算法限流。

令牌桶算法原理：

• 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。

• 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。

• 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；

• 如果拿不到令牌，就直接拒绝这个请求。

漏桶算法伪代码实现如下：

    /**
     * 每秒处理数（放入令牌数量）
     */
    private long putTokenRate;
    
    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 令牌桶容量
     */
    private long capacity;
    
    /**
     * 当前桶内令牌数
     */
    private long currentToken = 0L;

    /**
     * 漏桶算法
     * @return
     */
    boolean tokenBucketTryAcquire() {

        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
        currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
        refreshTime = currentTime; // 刷新时间
        
        //桶里面还有令牌，请求正常处理
        if (currentToken > 0) {
            currentToken--; //令牌数量-1
            return true;
        }
        
        return false;
    }

如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。

The above is the detailed content of Example Analysis of Classic Current Limiting Algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!