面試官：限流算法有哪些？

作者：磊哥 2023-02-20 08:08:48

限流的實(shí)現(xiàn)算法有很多，但常見(jiàn)的限流算法有三種：計(jì)數(shù)器算法、漏桶算法和令牌桶算法。

1、計(jì)數(shù)器算法

計(jì)數(shù)器算法是在一定的時(shí)間間隔里，記錄請(qǐng)求次數(shù)，當(dāng)請(qǐng)求次數(shù)超過(guò)該時(shí)間限制時(shí)，就把計(jì)數(shù)器清零，然后重新計(jì)算。當(dāng)請(qǐng)求次數(shù)超過(guò)間隔內(nèi)的最大次數(shù)時(shí)，拒絕訪問(wèn)。

計(jì)數(shù)器算法的實(shí)現(xiàn)比較簡(jiǎn)單，但存在“突刺現(xiàn)象”。

突刺現(xiàn)象是指，比如限流 QPS（每秒查詢率）為 100，算法的實(shí)現(xiàn)思路就是從第一個(gè)請(qǐng)求進(jìn)來(lái)開(kāi)始計(jì)時(shí)，在接下來(lái)的 1 秒內(nèi)，每來(lái)一個(gè)請(qǐng)求，就把計(jì)數(shù)加 1，如果累加的數(shù)字達(dá)到了 100，后續(xù)的請(qǐng)求就會(huì)被全部拒絕。等到 1 秒結(jié)束后，把計(jì)數(shù)恢復(fù)成 0，重新開(kāi)始計(jì)數(shù)。如果在單位時(shí)間 1 秒內(nèi)的前 10 毫秒處理了 100 個(gè)請(qǐng)求，那么后面的 990 毫秒會(huì)請(qǐng)求拒絕所有的請(qǐng)求，我們把這種現(xiàn)象稱為“突刺現(xiàn)象”。

計(jì)數(shù)器算法的簡(jiǎn)單實(shí)現(xiàn)代碼如下：

import java.util.Calendar;
import java.util.Date;
import java.util.Random;

public class CounterLimit {
    // 記錄上次統(tǒng)計(jì)時(shí)間
    static Date lastDate = new Date();
    // 初始化值
    static int counter = 0;
    // 限流方法
    static boolean countLimit() {
        // 獲取當(dāng)前時(shí)間
        Date now = new Date();
        Calendar calendar = Calendar.getInstance();
        calendar.setTime(now);
        // 當(dāng)前分
        int minute = calendar.get(Calendar.MINUTE);
        calendar.setTime(lastDate);
        int lastMinute = calendar.get(Calendar.MINUTE);
        if (minute != lastMinute) {
            lastDate = now;
            counter = 0;
        }
        ++counter;
        return counter >= 100; // 判斷計(jì)數(shù)器是否大于每分鐘限定的值。
    }

    // 測(cè)試方法
    public static void main(String[] args) {
        for (; ; ) {
            // 模擬一秒
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            Random random = new Random();
            int i = random.nextInt(3);
            // 模擬1秒內(nèi)請(qǐng)求1次
            if (i == 1) {
                if (countLimit()) {
                    System.out.println("限流了" + counter);

                } else {
                    System.out.println("沒(méi)限流" + counter);
                }
            } else if (i == 2) { // 模擬1秒內(nèi)請(qǐng)求2次
                for (int j = 0; j < 2; j++) {
                    if (countLimit()) {
                        System.out.println("限流了" + counter);
                    } else {
                        System.out.println("沒(méi)限流" + counter);
                    }
                }
            } else { // 模擬1秒內(nèi)請(qǐng)求10次
                for (int j = 0; j < 10; j++) {
                    if (countLimit()) {
                        System.out.println("限流了" + counter);
                    } else {
                        System.out.println("沒(méi)限流" + counter);
                    }
                }
            }
        }
    }
}

2、漏桶算法

漏桶算法的實(shí)現(xiàn)思路是，有一個(gè)固定容量的漏桶，水流（請(qǐng)求）可以按照任意速率先進(jìn)入到漏桶里，但漏桶總是以固定的速率勻速流出，當(dāng)流入量過(guò)大的時(shí)候（超過(guò)桶的容量），則多余水流（請(qǐng)求）直接溢出。如下圖所示：

漏桶算法提供了一種機(jī)制，通過(guò)它可以讓突發(fā)流量被整形，以便為系統(tǒng)提供穩(wěn)定的請(qǐng)求，比如 Sentinel 中流量整形（勻速排隊(duì)功能）就是此算法實(shí)現(xiàn)的，如下圖所示：

更多 Sentinel 內(nèi)容詳見(jiàn)：https://mp.weixin.qq.com/s/nF5f18BP8hscqIEmIFRN8Q。

3、令牌桶算法

令牌按固定的速率被放入令牌桶中，桶中最多存放 N 個(gè)令牌（Token），當(dāng)桶裝滿時(shí)，新添加的令牌被丟棄或拒絕。當(dāng)請(qǐng)求到達(dá)時(shí)，將從桶中刪除 1 個(gè)令牌。令牌桶中的令牌不僅可以被移除，還可以往里添加，所以為了保證接口隨時(shí)有數(shù)據(jù)通過(guò)，必須不停地往桶里加令牌。由此可見(jiàn)，往桶里加令牌的速度就決定了數(shù)據(jù)通過(guò)接口的速度。我們通過(guò)控制往令牌桶里加令牌的速度從而控制接口的流量。令牌桶的實(shí)現(xiàn)原理如下圖所示：

4、漏桶算法 VS 令牌桶算法

漏桶算法是按照常量固定速率流出請(qǐng)求的，流入請(qǐng)求速率任意，當(dāng)流入的請(qǐng)求數(shù)累積到漏桶容量時(shí)，新流入的請(qǐng)求被拒絕。令牌桶算法是按照固定速率往桶中添加令牌的，請(qǐng)求是否被處理需要看桶中的令牌是否足夠，當(dāng)令牌數(shù)減為零時(shí)，拒絕新的請(qǐng)求。令牌桶算法允許突發(fā)請(qǐng)求，只要有令牌就可以處理，允許一定程度的突發(fā)流量。漏桶算法限制的是常量流出速率，從而使突發(fā)流入速率平滑。

比如服務(wù)器空閑時(shí)，理論上使用漏桶算法服務(wù)器可以直接處理一次洪峰（一次洪水過(guò)程的最大流量），但是漏桶算法處理請(qǐng)求的速率是恒定的，因此，前期服務(wù)器資源只能根據(jù)恒定的漏水速度逐步處理請(qǐng)求，無(wú)法直接處理這次洪峰。而使用令牌桶算法就不存在這個(gè)問(wèn)題，因?yàn)樗梢韵劝蚜钆仆耙淮涡匝b滿，處理一次洪峰之后再走限流。

總結(jié)

限流的常見(jiàn)算法有以下 3 種：

計(jì)數(shù)器算法：實(shí)現(xiàn)簡(jiǎn)單，但有突刺現(xiàn)象；
漏桶算法：固定速率處理請(qǐng)求，處理任意流量更加平滑，可以實(shí)現(xiàn)流量整形；
令牌桶算法：通過(guò)控制桶中的令牌實(shí)現(xiàn)限流，可以處理一定的突發(fā)流量，比如處理一次洪峰。

參考 & 鳴謝

《分布式微服務(wù)架構(gòu)》

https://blog.csdn.net/chengqiuming/article/details/122385943。

責(zé)任編輯：姜華來(lái)源： Java中文社群

限流算法計(jì)數(shù)器算法令牌桶算法