常用限流方式

計數器

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

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

程序執行邏輯：

可以在程序中設置一個變量 count，當過來一個請求我就將這個數 +1，同時記錄請求時間。
當下一個請求來的時候判斷 count 的計數值是否超過設定的頻次，以及當前請求的時間和第一次請求時間是否在 1 分鐘內。
如果在 1 分鐘內并且超過設定的頻次則證明請求過多，后面的請求就拒絕掉。
如果該請求與第一個請求的間隔時間大于計數周期，且 count 值還在限流范圍內，就重置 count。

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

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

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

滑動窗口

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

上圖中我們用紅色的虛線代表一個時間窗口（一分鐘），每個時間窗口有 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 腳本代碼如下：

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  --請求數+1，并設置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)); // 執行lua腳本，傳入參數  

    return result == 1;  

}