常用限流方式分析 怎么設計出高并發限流方案

來源：樓仔

常用限流方式

計數器

滑動窗口

漏桶

令牌桶

Redis + Lua 分布式限流

聊聊其它

限流對比

什么是限流呢？限流是限制到達系統的并發請求數量，保證系統能夠正常響應部分用戶請求，而對于超過限制的流量，則通過拒絕服務的方式保證整體系統的可用性。

根據限流作用范圍，可以分為單機限流和分布式限流 ；根據限流方式，又分為計數器、滑動窗口、漏桶和令牌桶限流 ，下面我們對這塊詳細進行講解。

常用限流方式

計數器

計數器是一種最簡單限流算法，其原理就是：在一段時間間隔內，對請求進行計數，與閥值進行比較判斷是否需要限流，一旦到了時間臨界點，將計數器清零。

這個就像你去坐車一樣，車廂規定了多少個位置，滿了就不讓上車了，不然就是超載了，被交警叔叔抓到了就要罰款的，如果我們的系統那就不是罰款的事情了，可能直接崩掉了。

程序執行邏輯：

可以在程序中設置一個變量 count，當過來一個請求我就將這個數 +1，同時記錄請求時間。

當下一個請求來的時候判斷 count 的計數值是否超過設定的頻次，以及當前請求的時間和第一次請求時間是否在 1 分鐘內。

如果在 1 分鐘內并且超過設定的頻次則證明請求過多，后面的請求就拒絕掉。

如果該請求與第一個請求的間隔時間大于計數周期，且 count 值還在限流范圍內，就重置 count。

那么問題來了，如果有個需求對于某個接口 /query 每分鐘最多允許訪問 200 次，假設有個用戶在第 59 秒的最后幾毫秒瞬間發送 200 個請求，當 59 秒結束后 Counter 清零了，他在下一秒的時候又發送 200 個請求。

那么在 1 秒鐘內這個用戶發送了 2 倍的請求，這個是符合我們的設計邏輯的，這也是計數器方法的設計缺陷，系統可能會承受惡意用戶的大量請求，甚至擊穿系統。這種方法雖然簡單，但也有個大問題就是沒有很好的處理單位時間的邊界。

不過說實話，這個計數引用了鎖，在高并發場景，這個方式可能不太實用，我建議將鎖去掉，然后將 l.count++ 的邏輯通過原子計數處理，這樣就可以保證 l.count 自增時不會被多個線程同時執行，即通過原子計數的方式實現限流。

滑動窗口

滑動窗口是針對計數器存在的臨界點缺陷，所謂滑動窗口（Sliding window）是一種流量控制技術，這個詞出現在 TCP 協議中?；瑒哟翱诎压潭〞r間片進行劃分，并且隨著時間的流逝，進行移動，固定數量的可以移動的格子，進行計數并判斷閥值。

上圖中我們用紅色的虛線代表一個時間窗口（一分鐘），每個時間窗口有 6 個格子，每個格子是 10 秒鐘。每過 10 秒鐘時間窗口向右移動一格，可以看紅色箭頭的方向。我們為每個格子都設置一個獨立的計數器 Counter，假如一個請求在 0:45 訪問了那么我們將第五個格子的計數器 +1（也是就是 0:40~0:50），在判斷限流的時候需要把所有格子的計數加起來和設定的頻次進行比較即可。

那么滑動窗口如何解決我們上面遇到的問題呢？來看下面的圖：

當用戶在 0:59 秒鐘發送了 200 個請求就會被第六個格子的計數器記錄 +200，當下一秒的時候時間窗口向右移動了一個，此時計數器已經記錄了該用戶發送的 200 個請求，所以再發送的話就會觸發限流，則拒絕新的請求。

其實計數器就是滑動窗口啊，只不過只有一個格子而已，所以想讓限流做的更精確只需要劃分更多的格子就可以了，為了更精確我們也不知道到底該設置多少個格子，格子的數量影響著滑動窗口算法的精度，依然有時間片的概念，無法根本解決臨界點問題。

漏桶

漏桶算法（Leaky Bucket），原理就是一個固定容量的漏桶，按照固定速率流出水滴。

用過水龍頭都知道，打開龍頭開關水就會流下滴到水桶里，而漏桶指的是水桶下面有個漏洞可以出水,如果水龍頭開的特別大那么水流速就會過大，這樣就可能導致水桶的水滿了然后溢出。

一個固定容量的桶，有水流進來，也有水流出去。對于流進來的水來說，我們無法預計一共有多少水會流進來，也無法預計水流的速度。但是對于流出去的水來說，這個桶可以固定水流出的速率（處理速度），從而達到流量整形和流量控制的效果。

漏桶算法有以下特點：

漏桶具有固定容量，出水速率是固定常量（流出請求）

如果桶是空的，則不需流出水滴

可以以任意速率流入水滴到漏桶（流入請求）

如果流入水滴超出了桶的容量，則流入的水滴溢出（新請求被拒絕）

漏桶限制的是常量流出速率（即流出速率是一個固定常量值），所以最大的速率就是出水的速率，不能出現突發流量。

令牌桶

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

我們有一個固定的桶，桶里存放著令牌（token）。一開始桶是空的，系統按固定的時間（rate）往桶里添加令牌，直到桶里的令牌數滿，多余的請求會被丟棄。當請求來的時候，從桶里移除一個令牌，如果桶是空的則拒絕請求或者阻塞。

令牌桶有以下特點：

令牌按固定的速率被放入令牌桶中

桶中最多存放 B 個令牌，當桶滿時，新添加的令牌被丟棄或拒絕

如果桶中的令牌不足 N 個，則不會刪除令牌，且請求將被限流（丟棄或阻塞等待）

令牌桶限制的是平均流入速率 （允許突發請求，只要有令牌就可以處理，支持一次拿3個令牌，4個令牌...），并允許一定程度突發流量，所以也是非常常用的限流算法。

Redis + Lua 分布式限流

單機版限流僅能保護自身節點，但無法保護應用依賴的各種服務，并且在進行節點擴容、縮容時也無法準確控制整個服務的請求限制。

而分布式限流，以集群為維度，可以方便的控制這個集群的請求限制，從而保護下游依賴的各種服務資源。

分布式限流最關鍵的是要將限流服務做成原子化 ，我們可以借助 Redis 的計數器，Lua 執行的原子性，進行分布式限流，大致的 Lua 腳本代碼如下：

localkey="rate.limit:"..KEYS[1]--限流KEY

locallimit=tonumber(ARGV[1])--限流大小

localcurrent=tonumber(redis.call('get',key)or"0")

ifcurrent+1>limitthen--如果超出限流大小

return0

else--請求數+1，并設置1秒過期

redis.call("INCRBY",key,"1")

redis.call("expire",key,"1")

returncurrent+1

end

限流邏輯（Java 語言）：

publicstaticbooleanaccquire()throwsIOException,URISyntaxException{

Jedisjedis=newJedis("127.0.0.1");

FileluaFile=newFile(RedisLimitRateWithLUA.class.getResource("/").toURI().getPath()+"limit.lua");

StringluaScript=FileUtils.readFileToString(luaFile);



Stringkey="ip:"+System.currentTimeMillis()/1000;//當前秒

Stringlimit="5";//最大限制

Listkeys=newArrayList();

keys.add(key);

Listargs=newArrayList();

args.add(limit);

Longresult=(Long)(jedis.eval(luaScript,keys,args));//執行lua腳本，傳入參數

returnresult==1;

}

聊聊其它

上面的限流方式，主要是針對服務器進行限流，我們也可以對容器進行限流，比如 Tomcat、Nginx 等限流手段。

Tomcat 可以設置最大線程數（maxThreads），當并發超過最大線程數會排隊等待執行；而 Nginx 提供了兩種限流手段：一是控制速率，二是控制并發連接數。

對于 Java 語言，我們其實有相關的限流組件，比如大家常用的 RateLimiter，其實就是基于令牌桶算法 ，大家知道為什么唯獨選用令牌桶么？

在實際的限流場景中，我們也可以控制單個 IP、城市、渠道、設備 id、用戶 id 等在一定時間內發送的請求數；如果是開放平臺，需要為每個 appkey 設置獨立的訪問速率規則。

限流對比

下面我們就對常用的線程策略，總結它們的優缺點，便于以后選型。

計數器：

優點：固定時間段計數，實現簡單，適用不太精準的場景；

缺點：對邊界沒有很好處理，導致限流不能精準控制。

滑動窗口：

優點：將固定時間段分塊，時間比“計數器”復雜，適用于稍微精準的場景；

缺點：實現稍微復雜，還是不能徹底解決“計數器”存在的邊界問題。

漏桶：

優點：可以很好的控制消費頻率；

缺點：實現稍微復雜，單位時間內，不能多消費，感覺不太靈活。

令牌桶：

優點：可以解決“漏桶”不能靈活消費的問題，又能避免過渡消費，強烈推薦；

缺點：實現稍微復雜，其它缺點沒有想到。

Redis + Lua 分布式限流：

優點：支持分布式限流，有效保護下游依賴的服務資源；

缺點：依賴 Redis，對邊界沒有很好處理，導致限流不能精準控制。