什么是限流呢俭茧？限流是限制到達系統(tǒng)的并發(fā)請求數(shù)量，保證系統(tǒng)能夠正常響應(yīng)部分用戶請求漓帚，而對于超過限制的流量母债，則通過拒絕服務(wù)的方式保證整體系統(tǒng)的可用性。

根據(jù)限流作用范圍尝抖，可以分為 單機限流和分布式限流 毡们；根據(jù)限流方式，又分為 計數(shù)器昧辽、滑動窗口衙熔、漏桶和令牌桶限流 ，下面我們對這塊詳細進行講解搅荞。

常用限流方式

計數(shù)器

計數(shù)器是一種最簡單限流算法红氯，其原理就是：在一段時間間隔內(nèi)，對請求進行計數(shù)咕痛，與閥值進行比較判斷是否需要限流痢甘，一旦到了時間臨界點，將計數(shù)器清零茉贡。

這個就像你去坐車一樣塞栅，車廂規(guī)定了多少個位置，滿了就不讓上車了腔丧，不然就是超載了放椰，被交警叔叔抓到了就要罰款的，如果我們的系統(tǒng)那就不是罰款的事情了愉粤，可能直接崩掉了砾医。

程序執(zhí)行邏輯：

• 可以在程序中設(shè)置一個變量 count，當過來一個請求我就將這個數(shù) +1科汗，同時記錄請求時間藻烤。

• 當下一個請求來的時候判斷 count 的計數(shù)值是否超過設(shè)定的頻次，以及當前請求的時間和第一次請求時間是否在 1 分鐘內(nèi)头滔。

• 如果在 1 分鐘內(nèi)并且超過設(shè)定的頻次則證明請求過多怖亭，后面的請求就拒絕掉。

• 如果該請求與第一個請求的間隔時間大于計數(shù)周期坤检，且 count 值還在限流范圍內(nèi)兴猩，就重置 count。

那么問題來了早歇，如果有個需求對于某個接口 /query 每分鐘最多允許訪問 200 次倾芝，假設(shè)有個用戶在第 59 秒的最后幾毫秒瞬間發(fā)送 200 個請求讨勤，當 59 秒結(jié)束后 Counter 清零了，他在下一秒的時候又發(fā)送 200 個請求晨另。

那么在 1 秒鐘內(nèi)這個用戶發(fā)送了 2 倍的請求潭千，這個是符合我們的設(shè)計邏輯的，這也是計數(shù)器方法的設(shè)計缺陷借尿，系統(tǒng)可能會承受惡意用戶的大量請求刨晴，甚至擊穿系統(tǒng)。 這種方法雖然簡單路翻，但也有個大問題就是沒有很好的處理單位時間的邊界狈癞。

image.png

不過說實話，這個計數(shù)引用了鎖茂契，在高并發(fā)場景蝶桶，這個方式可能不太實用，我建議將鎖去掉掉冶，然后將 l.count++ 的邏輯通過原子計數(shù)處理真竖，這樣就可以保證 l.count 自增時不會被多個線程同時執(zhí)行， 即通過原子計數(shù)的方式實現(xiàn)限流郭蕉。

滑動窗口

滑動窗口是針對計數(shù)器存在的臨界點缺陷疼邀，所謂滑動窗口（Sliding window）是一種流量控制技術(shù)喂江，這個詞出現(xiàn)在 TCP 協(xié)議中召锈。滑動窗口把固定時間片進行劃分获询，并且隨著時間的流逝涨岁，進行移動，固定數(shù)量的可以移動的格子吉嚣，進行計數(shù)并判斷閥值梢薪。

image.png

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

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

image.png

當用戶在 0:59 秒鐘發(fā)送了 200 個請求就會被第六個格子的計數(shù)器記錄 +200，當下一秒的時候時間窗口向右移動了一個歧胁，此時計數(shù)器已經(jīng)記錄了該用戶發(fā)送的 200 個請求滋饲，所以再發(fā)送的話就會觸發(fā)限流厉碟，則拒絕新的請求。

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

漏桶

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

用過水龍頭都知道背稼，打開龍頭開關(guān)水就會流下滴到水桶里，而漏桶指的是水桶下面有個漏洞可以出水,如果水龍頭開的特別大那么水流速就會過大玻蝌，這樣就可能導(dǎo)致水桶的水滿了然后溢出蟹肘。

image.png

一個固定容量的桶，有水流進來俯树，也有水流出去帘腹。對于流進來的水來說，我們無法預(yù)計一共有多少水會流進來许饿，也無法預(yù)計水流的速度阳欲。但是對于流出去的水來說，這個桶可以固定水流出的速率（處理速度）陋率，從而達到流量整形和流量控制的效果球化。

漏桶算法有以下特點：

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

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

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

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

漏桶限制的是常量流出速率（即流出速率是一個固定常量值）， 所以最大的速率就是出水的速率菩浙，不能出現(xiàn)突發(fā)流量巢掺。

令牌桶

令牌桶算法（Token Bucket）是網(wǎng)絡(luò)流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下劲蜻，令牌桶算法用來控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目陆淀，并允許突發(fā)數(shù)據(jù)的發(fā)送。

image.png

我們有一個固定的桶斋竞，桶里存放著令牌（token）倔约。一開始桶是空的，系統(tǒng)按固定的時間（rate）往桶里添加令牌坝初，直到桶里的令牌數(shù)滿浸剩，多余的請求會被丟棄钾军。當請求來的時候，從桶里移除一個令牌绢要，如果桶是空的則拒絕請求或者阻塞吏恭。

令牌桶有以下特點：

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

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

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

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

Redis + Lua 分布式限流

單機版限流僅能保護自身節(jié)點蝇更，但無法保護應(yīng)用依賴的各種服務(wù)沪编，并且在進行節(jié)點擴容、縮容時也無法準確控制整個服務(wù)的請求限制年扩。

而分布式限流蚁廓，以集群為維度，可以方便的控制這個集群的請求限制厨幻，從而保護下游依賴的各種服務(wù)資源相嵌。

分布式限流最關(guān)鍵的是要將限流服務(wù)做成原子化，我們可以借助 Redis 的計數(shù)器克胳，Lua 執(zhí)行的原子性平绩，進行分布式限流，大致的 Lua 腳本代碼如下：

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

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

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

if current + 1 > limit then --如果超出限流大小  

  return 0  

else  --請求數(shù)+1漠另，并設(shè)置1秒過期  

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

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

   return current + 1  

end  

限流邏輯（Java 語言）：

public static boolean accquire() throws IOException, URISyntaxException {  

    Jedis jedis = new Jedis("127.0.0.1");  

    File luaFile = new File(RedisLimitRateWithLUA.class.getResource("/").toURI().getPath() + "limit.lua");  

    String luaScript = FileUtils.readFileToString(luaFile);  

  

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

    String limit = "5"; // 最大限制  

    List<String> keys = new ArrayList<String>();  

    keys.add(key);  

    List<String> args = new ArrayList<String>();  

    args.add(limit);  

    Long result = (Long)(jedis.eval(luaScript, keys, args)); // 執(zhí)行l(wèi)ua腳本，傳入?yún)?shù)  

    return result == 1;  

}  

聊聊其它

上面的限流方式跃赚，主要是針對服務(wù)器進行限流笆搓， 我們也可以對容器進行限流，比如 Tomcat纬傲、Nginx 等限流手段满败。

Tomcat 可以設(shè)置最大線程數(shù)（maxThreads），當并發(fā)超過最大線程數(shù)會排隊等待執(zhí)行叹括；而 Nginx 提供了兩種限流手段：一是控制速率算墨，二是控制并發(fā)連接數(shù)。

對于 Java 語言汁雷，我們其實有相關(guān)的限流組件净嘀，比如 大家常用的 RateLimiter报咳，其實就是基于令牌桶算法 ，大家知道為什么唯獨選用令牌桶么挖藏？

在實際的限流場景中暑刃，我們也可以控制單個 IP璃搜、城市粟关、渠道、設(shè)備 id向臀、用戶 id 等在一定時間內(nèi)發(fā)送的請求數(shù)宵膨；如果是開放平臺架谎，需要為每個 appkey 設(shè)置獨立的訪問速率規(guī)則。

限流對比

下面我們就對常用的線程策略辟躏，總結(jié)它們的優(yōu)缺點狐树，便于以后選型。

計數(shù)器：

• 優(yōu)點：固定時間段計數(shù)鸿脓，實現(xiàn)簡單抑钟，適用不太精準的場景；

• 缺點：對邊界沒有很好處理野哭，導(dǎo)致限流不能精準控制在塔。

滑動窗口：

• 優(yōu)點：將固定時間段分塊，時間比“計數(shù)器”復(fù)雜拨黔，適用于稍微精準的場景蛔溃；

• 缺點：實現(xiàn)稍微復(fù)雜，還是不能徹底解決“計數(shù)器”存在的邊界問題篱蝇。

漏桶：

• 優(yōu)點：可以很好的控制消費頻率贺待；

• 缺點：實現(xiàn)稍微復(fù)雜，單位時間內(nèi)零截，不能多消費麸塞，感覺不太靈活。

令牌桶：

• 優(yōu)點：可以解決“漏桶”不能靈活消費的問題涧衙，又能避免過渡消費哪工，強烈推薦；

• 缺點：實現(xiàn)稍微復(fù)雜弧哎，其它缺點沒有想到雁比。

Redis + Lua 分布式限流：

• 優(yōu)點：支持分布式限流，有效保護下游依賴的服務(wù)資源撤嫩；

• 缺點：依賴 Redis偎捎，對邊界沒有很好處理，導(dǎo)致限流不能精準控制。