應用限流思路

在開發(fā)高并發(fā)系統(tǒng)時坛梁，有三把利器用來保護系統(tǒng)：緩存饱苟、降級和限流：

• 緩存：緩存的目的是提升系統(tǒng)訪問速度和增大系統(tǒng)處理容量
• 降級：降級是當服務出現(xiàn)問題或者影響到核心流程時，需要暫時屏蔽掉编矾，待高峰或者問題解決后再打開
• 限流：限流的目的是通過對并發(fā)訪問/請求進行限速熟史，或者對一個時間窗口內(nèi)的請求進行限速來保護系統(tǒng)，一旦達到限制速率則可以拒絕服務窄俏、排隊或等待蹂匹、降級等處理

本文僅針對限流做一些簡單的說明，那么何為限流呢凹蜈？顧名思義限寞，限流就是限制流量忍啸，就像你寬帶包了1個G的流量，用完了就沒了履植。通過限流计雌，我們可以很好地控制系統(tǒng)的qps，從而達到保護系統(tǒng)的目的玫霎。本篇文章將會介紹一下常用的限流算法以及他們各自的特點凿滤。

限流本質(zhì)上是控制某段代碼在一定時間內(nèi)執(zhí)行的次數(shù)，例如我們系統(tǒng)每天五點過后都有130w~140w的數(shù)據(jù)需要插入數(shù)據(jù)庫庶近，若是直接一次性插入這些數(shù)據(jù)翁脆，必將導致數(shù)據(jù)庫連接被占滿無法接收其他處理的請求，數(shù)據(jù)庫的負載壓力會瞬間飆升鼻种，甚至是壓垮數(shù)據(jù)庫造成雪崩現(xiàn)象反番。所以我們需要對此操作進行限流，以一個恒定的速率去插入數(shù)據(jù)叉钥，假設每秒插入400條數(shù)據(jù)罢缸，當然這個數(shù)值需要根據(jù)實際情況去設定，如此一來就可以有效控制同一時間往數(shù)據(jù)庫插入的數(shù)據(jù)流不會很大沼侣，這樣就不會出現(xiàn)上述問題了祖能。如下圖：

image.png

應用限流的常用算法：

• 計數(shù)器法
• 滑動窗口
• 漏桶算法
• 令牌桶算法

計數(shù)器法

計數(shù)器法是限流算法里最簡單也是最容易實現(xiàn)的一種算法。比如我們規(guī)定蛾洛，對于A接口來說养铸，我們1分鐘的訪問次數(shù)不能超過100個。那么我們可以這么做：在一開始的時候轧膘，我們可以設置一個計數(shù)器counter钞螟，每當一個請求過來的時候，counter就加1谎碍，如果counter的值大于100并且該請求與第一個 請求的間隔時間還在1分鐘之內(nèi)鳞滨，那么說明請求數(shù)過多；如果該請求與第一個請求的間隔時間大于1分鐘蟆淀，且counter的值還在限流范圍內(nèi)拯啦，那么就重置 counter，具體算法的示意圖如下：

image.png

具體的偽代碼如下：

public class CounterDemo {
    public long timeStamp = getNowTime();  // 當前時間
    public int reqCount = 0;  // 初始化計數(shù)器
    public final int limit = 100; // 時間窗口內(nèi)最大請求數(shù)
    public final long interval = 1000; // 時間窗口ms
    
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在時間窗口內(nèi)
            reqCount++;
            // 判斷當前時間窗口內(nèi)是否超過最大請求控制數(shù)
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超時后重置
            reqCount = 1;
            return true;
        }
    }
}

這個算法雖然簡單熔任，但是有一個十分致命的問題褒链，那就是臨界問題卡骂，如下圖：

image.png

從上圖中我們可以看到哨苛，假設有一個惡意用戶挂滓，他在0:59時猎贴，瞬間發(fā)送了100個請求是越，并且1:00又瞬間發(fā)送了100個請求哮塞，那么其實這個用戶在 1秒里面冰抢，瞬間發(fā)送了200個請求例衍。我們剛才規(guī)定的是1分鐘最多100個請求，也就是每秒鐘最多1.7個請求恍箭，用戶通過在時間窗口的重置節(jié)點處突發(fā)請求刻恭， 可以瞬間超過我們的速率限制。用戶有可能通過算法的這個漏洞季惯，瞬間壓垮我們的應用吠各。

聰明的朋友可能已經(jīng)看出來了，剛才的問題其實是因為我們統(tǒng)計的精度太低勉抓。那么如何很好地處理這個問題呢？或者說候学，如何將臨界問題的影響降低呢藕筋？我們可以看下面的滑動窗口算法。

滑動窗口

滑動窗口梳码，又稱rolling window隐圾。為了解決計數(shù)器法統(tǒng)計精度太低的問題，引入了滑動窗口算法掰茶。如果學過TCP網(wǎng)絡協(xié)議的話暇藏，那么一定對滑動窗口這個名詞不會陌生。下面這張圖濒蒋，很好地解釋了滑動窗口算法：

image.png

在上圖中盐碱，整個紅色的矩形框表示一個時間窗口，在我們的例子中沪伙，一個時間窗口就是一分鐘瓮顽。然后我們將時間窗口進行劃分，比如圖中围橡，我們就將滑動窗口劃成了6格暖混，所以每格代表的是10秒鐘。每過10秒鐘翁授，我們的時間窗口就會往右滑動一格拣播。每一個格子都有自己獨立的計數(shù)器counter，比如當一個請求 在0:35秒的時候到達收擦，那么0:30~0:39對應的counter就會加1贮配。

那么滑動窗口怎么解決剛才的臨界問題的呢？在上圖中炬守，0:59到達的100個請求會落在灰色的格子中牧嫉，而1:00到達的請求會落在橘黃色的格子中。當時間到達1:00時，我們的窗口會往右移動一格酣藻，那么此時時間窗口內(nèi)的總請求數(shù)量一共是200個曹洽，超過了限定的100個，所以此時能夠檢測出來觸發(fā)了限流辽剧。

我再來回顧一下剛才的計數(shù)器算法送淆，我們可以發(fā)現(xiàn)，計數(shù)器算法其實就是滑動窗口算法怕轿。只是它沒有對時間窗口做進一步地劃分偷崩，所以只有1格。

由此可見撞羽，當滑動窗口的格子劃分的越多阐斜，那么滑動窗口的滾動就越平滑，限流的統(tǒng)計就會越精確诀紊。

漏桶算法

漏桶算法谒出，又稱leaky bucket。為了理解漏桶算法邻奠，我們看一下對于該算法的示意圖：

image.png

從圖中我們可以看到笤喳，整個算法其實十分簡單。首先碌宴，我們有一個固定容量的桶杀狡，有水流進來，也有水流出去贰镣。對于流進來的水來說呜象，我們無法預計一共有多少水會流進來，也無法預計水流的速度八孝。但是對于流出去的水來說董朝，這個桶可以固定水流出的速率。而且干跛，當桶滿了之后子姜，多余的水將會溢出。

我們將算法中的水換成實際應用中的請求楼入，我們可以看到漏桶算法天生就限制了請求的速度哥捕。當使用了漏桶算法，我們可以保證接口會以一個常速速率來處理請求嘉熊。所以漏桶算法天生不會出現(xiàn)臨界問題遥赚。

具體的偽代碼如下：

public class LeakyDemo {
        public long timeStamp = getNowTime();  // 當前時間
        public int capacity; // 桶的容量
        public int rate; // 水漏出的速度
        public int water; // 當前水量(當前累積請求數(shù))
        
        public boolean grant() {
            long now = getNowTime();
            water = max(0, water - (now - timeStamp) * rate); // 先執(zhí)行漏水，計算剩余水量
            timeStamp = now;
            if ((water + 1) < capacity) {
                // 嘗試加水,并且水還未滿
                water += 1;
                return true;
            } else {
                // 水滿阐肤，拒絕加水
                return false;
        }
    }
}

令牌桶算法

令牌桶算法凫佛，又稱token bucket讲坎。同樣為了理解該算法，我們來看一下該算法的示意圖：

image.png

從圖中我們可以看到愧薛，令牌桶算法比漏桶算法稍顯復雜晨炕。首先，我們有一個固定容量的桶毫炉，桶里存放著令牌（token）瓮栗。桶一開始是空的，token以 一個固定的速率r往桶里填充瞄勾，直到達到桶的容量费奸，多余的令牌將會被丟棄。每當一個請求過來時进陡，就會嘗試從桶里移除一個令牌愿阐，如果沒有令牌的話，請求無法通過四濒。

具體的偽代碼如下：

public class TokenBucketDemo {
    public long timeStamp = getNowTime();  // 當前時間
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public int tokens; // 當前令牌數(shù)量
    
    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若不到1個令牌,則拒絕
            return false;
        } else {
            // 還有令牌换况，領取令牌
            tokens -= 1;
            return true;
        }
    }
}

若仔細研究該算法，我們會發(fā)現(xiàn)我們默認從桶里移除令牌是不需要耗費時間的盗蟆。如果給移除令牌設置一個延時時間，那么實際上又采用了漏桶算法的思路舒裤。Google的Guava庫下的SmoothWarmingUp類就采用了這個思路喳资。

我們再來考慮一下臨界問題的場景。在0:59秒的時候腾供，由于桶內(nèi)積滿了100個token仆邓，所以這100個請求可以瞬間通過。但是由于token是以較低的速率填充的伴鳖，所以在1:00的時候节值，桶內(nèi)的token數(shù)量不可能達到100個，那么此時不可能再有100個請求通過榜聂。所以令牌桶算法可以很好地解決臨界問題搞疗。下圖比較了計數(shù)器（左）和令牌桶算法（右）在臨界點的速率變化。我們可以看到雖然令牌桶算法允許突發(fā)速率须肆，但是下一個突發(fā)速率必須要等桶內(nèi)有足夠的 token后才能發(fā)生：

image.png

限流算法小結

計數(shù)器 VS 滑動窗口：

計數(shù)器算法是最簡單的算法匿乃，可以看成是滑動窗口的低精度實現(xiàn)⊥慊悖滑動窗口由于需要存儲多份的計數(shù)器（每一個格子存一份）幢炸，所以滑動窗口在實現(xiàn)上需要更多的存儲空間。也就是說拒贱，如果滑動窗口的精度越高宛徊，需要的存儲空間就越大佛嬉。

漏桶算法 VS 令牌桶算法：

漏桶算法和令牌桶算法最明顯的區(qū)別是令牌桶算法允許流量一定程度的突發(fā)。因為默認的令牌桶算法闸天，取走token是不需要耗費時間的暖呕，也就是說，假設桶內(nèi)有100個token時号枕，那么可以瞬間允許100個請求通過缰揪。

令牌桶算法由于實現(xiàn)簡單，且允許某些流量的突發(fā)葱淳，對用戶友好钝腺，所以被業(yè)界采用地較多。當然我們需要具體情況具體分析赞厕，只有最合適的算法艳狐，沒有最優(yōu)的算法。

RateLimiter使用示例

Google開源工具包Guava提供了限流工具類RateLimiter皿桑，該類基于令牌桶算法(Token Bucket)來完成限流毫目，非常易于使用。RateLimiter經(jīng)常用于限制對一些物理資源或者邏輯資源的訪問速率诲侮，它支持兩種獲取permits接口镀虐，一種是如果拿不到立刻返回false（tryAcquire()），一種會阻塞等待一段時間看能不能拿到（tryAcquire(long timeout, TimeUnit unit)）沟绪。

使用tryAcquire方法獲取令牌的示例代碼：

@Slf4j
public class RateLimiterExample1 {
    /**
     * 每秒鐘放入5個令牌刮便，相當于每秒只允許執(zhí)行5個請求
     */
    private static final RateLimiter RATE_LIMITER = RateLimiter.create(5);

    public static void main(String[] args) {
        // 模擬有100個請求
        for (int i = 0; i < 100; i++) {
            // 嘗試從令牌桶中獲取令牌，若獲取不到則等待300毫秒看能不能獲取到
            if (RATE_LIMITER.tryAcquire(300, TimeUnit.MILLISECONDS)) {
                // 獲取成功绽慈，執(zhí)行相應邏輯
                handle(i);
            }
        }
    }

    private static void handle(int i) {
        log.info("{}", i);
    }
}

若想保證所有的請求都被執(zhí)行恨旱，而不會被拋棄的話，可以選擇使用acquire方法：

@Slf4j
public class RateLimiterExample2 {
    /**
     * 每秒鐘放入5個令牌坝疼，相當于每秒只允許執(zhí)行5個請求
     */
    private static final RateLimiter RATE_LIMITER = RateLimiter.create(5);

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            // 從令牌桶中獲取一個令牌搜贤，若沒有獲取到會阻塞直到獲取到為止，所以所有的請求都會被執(zhí)行
            RATE_LIMITER.acquire();
            // 獲取成功钝凶，執(zhí)行相應邏輯
            handle(i);
        }
    }

    private static void handle(int i) {
        log.info("{}", i);
    }
}

集群限流

前面討論的幾種算法都屬于單機限流的范疇仪芒，但是業(yè)務需求五花八門，簡單的單機限流腿椎，根本無法滿足他們桌硫。

比如為了限制某個資源被每個用戶或者商戶的訪問次數(shù)，5s只能訪問2次啃炸，或者一天只能調(diào)用1000次铆隘，這種需求，單機限流是無法實現(xiàn)的南用，這時就需要通過集群限流進行實現(xiàn)膀钠。

如何實現(xiàn)掏湾？為了控制訪問次數(shù)，肯定需要一個計數(shù)器肿嘲，而且這個計數(shù)器只能保存在第三方服務融击，比如redis。

大概思路：每次有相關操作的時候雳窟，就向redis服務器發(fā)送一個incr命令尊浪，比如需要限制某個用戶訪問/index接口的次數(shù)，只需要拼接用戶id和接口名生成redis的key封救，每次該用戶訪問此接口時拇涤，只需要對這個key執(zhí)行incr命令，在這個key帶上過期時間誉结，就可以實現(xiàn)指定時間的訪問頻率鹅士。