一篇文章弄懂限流怎麼做

• 2019 年 10 月 10 日
• 筆記

限流是保護高並發系統的三把利器（限流、緩存、降級）之一。限流在很多場景中用來限制並發和請求量，保護自身系統和下游系統不被巨型流量衝垮。比如秒殺業務或者一些訪問量很高的基礎性服務都會用到限流的技術。

幾種常見的限流算法

1、計數器算法

計數器算法是限流算法里最簡單也是最容易實現的一種算法。假設我們限制一分鐘的能夠通過的請求數為100，算法的實現思路就是從第一個請求進來開始計時，在接下去的1分鐘內，每來一個請求，就把計數加1，如果累加的數字達到了100，那麼後續的請求就會被全部拒絕。等到1分鐘結束後，把計數恢復成0，重新開始計數。

貼一個之前IM項目中，控制每個tcp連接消息速率的限速器，基於計數器算法實現。

這個方法簡單、有效，還能很好適應移動端瞬時流量的情況（因為網絡原因，手機端在連上網絡後可能瞬時發送多條消息到服務端）。

然而這個方法有一個十分致命傷，那就是臨界問題，看下圖

假設有一個惡意用戶，在0:59時，瞬間發送了100個請求，並且1:00又瞬間發送了100個請求，那麼其實這個用戶在 1秒裏面，瞬間發送了200個請求。我們剛才規定的是1分鐘最多100個請求，也就是每秒鐘最多1.7個請求，用戶通過在時間窗口的重置節點處突發請求， 可以瞬間超過我們的速率限制。用戶有可能通過算法的這個漏洞，瞬間壓垮後端應用。滑動窗口可以解決這個問題

2、滑動窗口

滑動窗口，又稱rolling window。如果學過TCP網絡協議，一定對滑動窗口這個名詞不會陌生。下圖很好地解釋了滑動窗口算法

在上圖中，整個紅色的矩形框表示一個時間窗口，在這個例子中，一個時間窗口就是一分鐘。我們將滑動窗口劃成6格，每格代表10秒鐘。每過10秒鐘，時間窗口就會往右滑動一格。每一個格子都有自己獨立的計數器counter，比如一個請求在0:35秒時到達，那麼0:30~0:39對應的counter就會加1。

滑動窗口怎麼解決剛才的臨界問題的呢？我們可以看上圖，0:59到達的100個請求會落在灰色的格子中，而1:00到達的請求會落在橘黃色的格子中。當時間到達1:00時，窗口會往右移動一格，此時時間窗口內的總請求數量一共是200個，超過了限定的100個，所以此時能夠檢測出來觸發了限流。

回顧一下剛才的計數器算法，其實就是滑動窗口。只是它沒有對時間窗口做進一步地劃分，只有1格。

由此可見，滑動窗口格子劃分越多，窗口滾動就越平滑，限流統計就會越精確。

3、漏桶算法

漏桶算法（Leaky Bucket），主要目的是控制數據注入到網絡的速率，平滑網絡上的突發流量。漏桶算法提供了一種機制，通過它，突發流量可以被整形以便為網絡提供一個穩定的流量。

算法思路很簡單，水（請求）先進入到漏桶里，漏桶以一定的速度出水（接口有響應速率），當水流入速度過大會直接溢出（訪問頻率超過接口響應速率），然後就拒絕請求，可以看出漏桶算法能強行限制數據的傳輸速率。

漏桶算法的實現往往依賴於隊列，請求到達如果隊列未滿則直接放入隊列，有一個處理器按照固定頻率從隊列頭取出請求進行處理。如果請求量大，則會導致隊列滿，那麼新來的請求就會被拋棄。

用MQ來做流量削峰，就是這個算法的一種實踐！

4、令牌桶算法

令牌桶算法（Token Bucket），是網絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發送到網絡上的數據的數目，並允許突發數據的發送。令牌桶算法示意圖如下所示

令牌桶算法則是一個存放固定容量令牌的桶，按照固定速率往桶里添加令牌。桶中存放的令牌數有最大上限，超出之後就被丟棄或者拒絕。當流量或者網絡請求到達時，每個請求都要獲取一個令牌，如果能夠獲取到，則直接處理，並且令牌桶刪除一個令牌。如果獲取不同，該請求就要被限流，要麼直接丟棄，要麼在緩衝區等待。

Guava的RateLimiter提供了令牌桶算法實現：平滑突發限流(SmoothBursty)和平滑預熱限流(SmoothWarmingUp)實現。

Guava是Java領域優秀的開源項目，它包含了Google在Java項目中使用一些核心庫，包含集合(Collections)，緩存(Caching)，並發編程庫(Concurrency)，常用註解(Common annotations)，String操作，I/O操作方面的眾多非常實用的函數。

截一段RateLimiter加了注釋的源代碼

這4個算法涵蓋了目前主要的限流思想。本文提供的實現基本都是單機環境，那麼分佈式環境下限流怎麼做呢？