淺析Spring Cloud Gateway中的令牌桶限流演演算法

前言

在一個分散式高並行的系統設計中，限流是一個不可忽視的功能點。如果不對系統進行有效的流量存取限制，在雙十一和搶票這種流量洪峰的場景下，很容易就會把我們的系統打垮。而作為系統服務的衛兵的閘道器元件，作為系統服務的統一入口，更需要考慮流量的限制，直接在閘道器層阻斷流量比在各個系統中實現更合適。Spring Cloud Gateway的實現中，就提供了限流的功能，下面主要分析下Spring Cloud Gateway中是如何實現限流功能的。

回顧限流演演算法

限流的實現方式有多種，下面先回顧下幾種常見的實現演演算法

計數器/時間視窗法

這種限流演演算法最簡單，也是最容易實現的，通過在單位時間內設定最大存取數就可以達到限流的目的。比如某個系統能夠承載的一般qps為60，那我們就可以使用計算器法，在單位時間一秒內，限制介面只能被存取60次即可。但是這個演演算法實現，正如其功能描述一樣，有個缺陷，假如在時間窗的前1%的時間內流量就達到頂峰了，那麼在時間窗內還有99%的時間系統即使能夠繼續提供服務，還是會被限流演演算法的這種缺陷阻斷在門外，這種缺陷也被稱為“突刺效應“

漏桶法

漏桶法不同於計算器法，它有效的避免了計數器法限流的“突刺效應”缺陷,實現也不復雜，通過固定大小的佇列+定時取佇列元素的方式即可實現。如其名漏桶，就像一個盛水的容器，漏桶法只限制容器出水的速率，當進水的速率過大時，將會填滿容器造成溢位，溢位部分的流量也就是拒絕的流量。比如，容器大小為100，出水速率為每秒10/s,當桶為空時，最大的流量可以到達100/s，但是即使這樣，受限於固定的流出速率，後端處理的也只能是最大每秒10個，其餘的流量都會被緩衝在漏桶中。這個也這是漏桶法的缺陷，沒法真正處理突發的流量洪峰，效率不高。

令牌桶法

令牌桶法也是基於桶的原型，但是和漏桶演演算法截然不同的時，沒有出水口。令牌桶通過令牌的產生速率+令牌桶的容積來控制流量，有效的解決了漏桶效率不高的問題。如，容積為100的桶，令牌產生速率為50/s，那麼就代表當桶中令牌已滿的時候，最大能夠承載100的流量，後面如果流量一直居高不下，也會以每秒50個流量的速度恆速處理請求。令牌桶的這種特性有效的處理了洪峰流量也能做到不被洪峰壓垮，是目前限流比較常見的實現方法。比較著名的實現有谷歌guava中的RateLimiter。然後下面將要分析的Spring Cloud Gateway中也是使用的令牌桶演演算法實現的限流

guava的檔案：https://github.com/google/guava/wiki

Spring Cloud Gateway中的令牌桶

Spring閘道器中是基於令牌桶+redis實現的閘道器分散式限流，具體的實現見下面兩個程式碼：

lua指令碼地址：resources/META-INF/scripts/request_rate_limiter.lua

RedisRateLimiter：gateway/filter/ratelimit/RedisRateLimiter.java

try {
			Listkeys = getKeys(id);

			// The arguments to the LUA script. time() returns unixtime in seconds.
			ListscriptArgs = Arrays.asList(replenishRate + "",
					burstCapacity + "", Instant.now().getEpochSecond() + "", "1");
			// allowed, tokens_left = redis.eval(SCRIPT, keys, args)
			Fluxflux = this.redisTemplate.execute(this.script, keys,
					scriptArgs);
			// .log("redisratelimiter", Level.FINER);
			return flux.onErrorResume(throwable -> Flux.just(Arrays.asList(1L, -1L)))
					.reduce(new ArrayList(), (longs, l) -> {
						longs.addAll(l);
						return longs;
					}).map(results -> {
						boolean allowed = results.get(0) == 1L;
						Long tokensLeft = results.get(1);

						Response response = new Response(allowed,
								getHeaders(routeConfig, tokensLeft));

						if (log.isDebugEnabled()) {
							log.debug("response: " + response);
						}
						return response;
					});
		}

上面博主擷取了Spring閘道器限流部分的關鍵程式碼，可以看到，最關鍵的地方在於，使用reids執行了一段lua指令碼，然後通過返回值【0】是否等於1來判斷本次流量是否通過，返回值【1】為令牌桶中剩餘的令牌數。就上面這段程式碼沒有看到任何令牌桶演演算法的影子對吧，所有的精華實現都在lua指令碼裡面，這個指令碼最初是由Paul Tarjan分享出來的，指令碼如下：

local tokens_key = KEYS[1]
local timestamp_key = KEYS[2]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
local fill_time = capacity/rate
local ttl = math.floor(fill_time*2)
local last_tokens = tonumber(redis.call("get", tokens_key))
if last_tokens == nil then
  last_tokens = capacity
end
local last_refreshed = tonumber(redis.call("get", timestamp_key))
if last_refreshed == nil then
  last_refreshed = 0
end
local delta = math.max(0, now-last_refreshed)
local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
local allowed = filled_tokens >= requested
local new_tokens = filled_tokens
local allowed_num = 0
if allowed then
  new_tokens = filled_tokens - requested
  allowed_num = 1
end
redis.call("setex", tokens_key, ttl, new_tokens)
redis.call("setex", timestamp_key, ttl, now)
return { allowed_num, new_tokens }

下面逐行分析下這段指令碼。首先解釋下，從應用中入參進來的這幾個屬性的具體含義：

tokens_key：當前限流的標識，可以是ip，或者在spring cloud系統中，可以是一個服務的serviceID

timestamp_key：令牌桶重新整理的時間戳，後面會被用來計算當前產生的令牌數 

rate ：令牌生產的速率，如每秒產生50個令牌

capacity ：令牌桶的容積大小，比如最大100個，那麼系統最大可承載100個並行請求

now ：當前時間戳

requested：當前請求的令牌數量，Spring Cloud Gateway中預設是1，也就是當前請求

主要邏輯分析

-- 計算填滿桶需要多長時間
-- 得到填滿桶的2倍時間作為redis中key時效的時間，避免冗餘太多無用的key
-- 這裡和令牌桶的實現沒有太大的關係
-- 獲取桶中剩餘的令牌，如果桶是空的，就將他填滿
-- 獲取當前令牌桶最後的重新整理時間，如果為空，則設定為0
-- 計算最後一次重新整理令牌到當前時間的時間差
-- 計算當前令牌數量，這個地方是最關鍵的地方，通過剩餘令牌數 + 時間差內產生的令牌得到當前總令牌數量
-- 設定標識allowad接收當前令牌桶中的令牌數是否大於請求的令牌結果
-- 設定當前令牌數量
-- 如果allowed為true，則將當前令牌數量重置為通中的令牌數 - 請求的令牌數，並且設定allowed_num標識為1
-- 將當前令牌數量寫回到redis中，並重置令牌桶的最後重新整理時間
-- 返回當前是否申請到了令牌，以及當前桶中剩餘多少令牌

以上就是淺析Spring Cloud Gateway中的令牌桶限流演演算法的詳細內容，更多關於pring Cloud Gateway令牌桶限流演演算法的資料請關注it145.com其它相關文章！