基於Redis和Lua的分布式限流

 Java單機限流可以使用AtomicInteger，RateLimiter或Semaphore來實現，但是上述方案都不支持集群限流。集群限流的應用場景有兩個，一個是網關，常用的方案有Nginx限流和Spring Cloud Gateway，另一個場景是與外部或者下遊服務接口的交互，因為接口限制必須進行限流。

 本文的主要內容為：

• Redis和Lua的使用場景和注意事項，比如說KEY映射的問題。
• Spring Cloud Gateway中限流的實現。

集群限流的難點

 在上篇Guava RateLimiter的分析中，我們學習了令牌桶限流算法的原理，下面我們就探討一下，如果將 RateLimiter擴展，讓它支持集群限流，會遇到哪些問題。

  RateLimiter會維護兩個關鍵的參數 nextFreeTicketMicros和 storedPermits，它們分別是下一次填充時間和當前存儲的令牌數。當 RateLimiter的 acquire函數被調用時，也就是有線程希望獲取令牌時， RateLimiter會對比當前時間和 nextFreeTicketMicros，根據二者差距，刷新 storedPermits，然後再判斷更新後的 storedPermits是否足夠，足夠則直接返回，否則需要等待直到令牌足夠(Guava RateLimiter的實現比較特殊，並不是當前獲取令牌的線程等待，而是下一個獲取令牌的線程等待)。

 由於要支持集群限流，所以 nextFreeTicketMicros和 storedPermits這兩個參數不能只存在JVM的內存中，必須有一個集中式存儲的地方。而且，由於算法要先獲取兩個參數的值，計算後在更新兩個數值，這裡涉及到競態限制，必須要處理並發問題。

 集群限流由於會面對相比單機更大的流量衝擊，所以一般不會進行線程等待，而是直接進行丟棄，因為如果讓拿不到令牌的線程進行睡眠，會導致大量的線程堆積，線程持有的資源也不會釋放，反而容易拖垮伺服器。

Redis和Lua

 分布式限流本質上是一個集群並發問題，Redis單進程單線程的特性，天然可以解決分布式集群的並發問題。所以很多分布式限流都基於Redis，比如說Spring Cloud的網關組件Gateway。

 Redis執行Lua腳本會以原子性方式進行，單線程的方式執行腳本，在執行腳本時不會再執行其他腳本或命令。並且，Redis只要開始執行Lua腳本，就會一直執行完該腳本再進行其他操作，所以Lua腳本中不能進行耗時操作。使用Lua腳本，還可以減少與Redis的交互，減少網絡請求的次數。

 Redis中使用Lua腳本的場景有很多，比如說分布式鎖，限流，秒殺等，總結起來，下面兩種情況下可以使用Lua腳本:

• 使用 Lua 腳本實現原子性操作的CAS，避免不同客戶端先讀Redis數據，經過計算後再寫數據造成的並發問題。
• 前後多次請求的結果有依賴時，使用 Lua 腳本將多個請求整合為一個請求。

 但是使用Lua腳本也有一些注意事項：

• 要保證安全性，在 Lua 腳本中不要定義自己的全局變量，以免汙染 Redis內嵌的Lua環境。因為Lua腳本中你會使用一些預製的全局變量，比如說 redis.call()
• 要注意 Lua 腳本的時間複雜度，Redis 的單線程同樣會阻塞在 Lua 腳本的執行中。
• 使用 Lua 腳本實現原子操作時，要注意如果 Lua 腳本報錯，之前的命令無法回滾，這和Redis所謂的事務機制是相同的。
• 一次發出多個 Redis 請求，但請求前後無依賴時，使用 pipeline，比 Lua 腳本方便。
• Redis要求單個Lua腳本操作的key必須在同一個Redis節點上。解決方案可以看下文對Gateway原理的解析。

性能測試

 Redis雖然以單進程單線程模型進行操作，但是它的性能卻十分優秀。總結來說，主要是因為:

• 絕大部分請求是純粹的內存操作
• 採用單線程,避免了不必要的上下文切換和競爭條件
• 內部實現採用非阻塞IO和epoll，基於epoll自己實現的簡單的事件框架。epoll中的讀、寫、關閉、連接都轉化成了事件，然後利用epoll的多路復用特性，絕不在io上浪費一點時間。

 所以，在集群限流時使用Redis和Lua的組合併不會引入過多的性能損耗。我們下面就簡單的測試一下，順便熟悉一下涉及的Redis命令。

將腳本導入redis，之後調用不需再傳遞腳本內容redis-cli -a 082203 script load "$(cat test.lua)""b978c97518ae7c1e30f246d920f8e3c321c76907"# 使用redis-benchmark和evalsha來執行lua腳本redis-benchmark -a 082203 -n 1000000 evalsha b978c97518ae7c1e30f246d920f8e3c321c76907 0 ======1000000 requests completed in 20.00 seconds50 parallel clients3 bytes payloadkeep alive: 193.54% <= 1 milliseconds99.90% <= 2 milliseconds99.97% <= 3 milliseconds99.98% <= 4 milliseconds99.99% <= 5 milliseconds100.00% <= 6 milliseconds100.00% <= 7 milliseconds100.00% <= 7 milliseconds49997.50 requests per second

 通過上述簡單的測試，我們可以發現本機情況下，使用Redis執行Lua腳本的性能極其優秀，一百萬次執行，99.99%在5毫秒以下。

 本來想找一下官方的性能數據，但是針對Redis + Lua的性能數據較少，只找到了幾篇個人博客，感興趣的同學可以去探索。這篇文章有Lua和zadd的性能比較(具體數據請看原文，連結缺失的話，請看文末)。

以上lua腳本的性能大概是zadd的70%-80%，但是在可接受的範圍內，在生產環境可以使用。負載大概是zadd的1.5-2倍，網絡流量相差不大，IO是zadd的3倍，可能是開啟了AOF，執行了三次操作。

Spring Cloud Gateway的限流實現

  Gateway是微服務架構 SpringCloud的網關組件，它基於Redis和Lua實現了令牌桶算法的限流功能，下面我們就來看一下它的原理和細節吧。

  Gateway基於Filter模式，提供了限流過濾器 RequestRateLimiterGatewayFilterFactory。只需在其配置文件中進行配置，就可以使用。具體的配置感興趣的同學自行學習，我們直接來看它的實現。

  RequestRateLimiterGatewayFilterFactory依賴 RedisRateLimiter的 isAllowed函數來判斷一個請求是否要被限流拋棄。

public Mono<Response> isAllowed(String routeId, String id) { //routeId是ip地址，id是使用KeyResolver獲取的限流維度id，比如說基於uri,IP或者用戶等等。 Config routeConfig = loadConfiguration(routeId); // 每秒能夠通過的請求數 int replenishRate = routeConfig.getReplenishRate(); // 最大流量 int burstCapacity = routeConfig.getBurstCapacity(); try { // 組裝Lua腳本的KEY List<String> keys = getKeys(id); // 組裝Lua腳本需要的參數，1是指一次獲取一個令牌 List<String> scriptArgs = Arrays.asList(replenishRate + "", burstCapacity + "", Instant.now().getEpochSecond() + "", "1"); // 調用Redis，tokens_left = redis.eval(SCRIPT, keys, args) Flux<List<Long>> flux = this.redisTemplate.execute(this.script, keys, scriptArgs); ..... // 省略 }static List<String> getKeys(String id) { String prefix = "request_rate_limiter.{" + id; String tokenKey = prefix + "}.tokens"; String timestampKey = prefix + "}.timestamp"; return Arrays.asList(tokenKey, timestampKey);}

 需要注意的是 getKeys函數的prefix包含了"{id}"，這是為了解決Redis集群鍵值映射問題。Redis的KeySlot算法中，如果key包含{}，就會使用第一個{}內部的字符串作為hash key，這樣就可以保證擁有同樣{}內部字符串的key就會擁有相同slot。Redis要求單個Lua腳本操作的key必須在同一個節點上，但是Cluster會將數據自動分布到不同的節點，使用這種方法就解決了上述的問題。

 然後我們來看一下Lua腳本的實現，該腳本就在Gateway項目的resource文件夾下。它就是如同 Guava的 RateLimiter一樣，實現了令牌桶算法，只不過不在需要進行線程休眠，而是直接返回是否能夠獲取。

local tokens_key = KEYS[1] -- request_rate_limiter.${id}.tokens 令牌桶剩餘令牌數的KEY值local timestamp_key = KEYS[2] -- 令牌桶最後填充令牌時間的KEY值local rate = tonumber(ARGV[1]) -- replenishRate 令令牌桶填充平均速率local capacity = tonumber(ARGV[2]) -- burstCapacity 令牌桶上限local now = tonumber(ARGV[3]) -- 得到從 1970-01-01 00:00:00 開始的秒數local requested = tonumber(ARGV[4]) -- 消耗令牌數量，默認 1 local fill_time = capacity/rate -- 計算令牌桶填充滿令牌需要多久時間local ttl = math.floor(fill_time*2) -- *2 保證時間充足local last_tokens = tonumber(redis.call("get", tokens_key)) -- 獲得令牌桶剩餘令牌數if last_tokens == nil then -- 第一次時，沒有數值，所以桶時滿的 last_tokens = capacityendlocal last_refreshed = tonumber(redis.call("get", timestamp_key)) -- 令牌桶最後填充令牌時間if last_refreshed == nil then last_refreshed = 0endlocal 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_tokenslocal allowed_num = 0if allowed then-- 若成功，令牌桶剩餘令牌數(new_tokens) 減消耗令牌數( requested )，並設置獲取成功( allowed_num = 1 ) 。 new_tokens = filled_tokens - requested allowed_num = 1end -- 設置令牌桶剩餘令牌數( new_tokens ) ，令牌桶最後填充令牌時間(now) ttl是超時時間？redis.call("setex", tokens_key, ttl, new_tokens)redis.call("setex", timestamp_key, ttl, now)-- 返回數組結果return { allowed_num, new_tokens }

後記

 Redis的主從異步複製機制可能丟失數據，出現限流流量計算不準確的情況，當然限流畢竟不同於分布式鎖這種場景，對於結果的精確性要求不是很高，即使多流入一些流量，也不會影響太大。

 正如Martin在他質疑Redis分布式鎖RedLock文章中說的，Redis的數據丟棄了也無所謂時再使用Redis存儲數據。

I think it’s a good fit in situations where you want to share some transient, approximate, fast-changing data between servers, and where it’s not a big deal if you occasionally lose that data for whatever reason

 接下來我們回來學習阿里開源的分布式限流組件 sentinel，希望大家持續關注。

個人微信公眾號: 張狗蛋的技術之路 remcarpediem

個人博客:

參考

• https://www.cnblogs.com/itrena/p/5926878.html
• 壓測的文章：https://www.fuwuqizhijia.com/redis/201704/60935.html
• https://blog.csdn.net/forezp/article/details/85081162
• https://blog.csdn.net/xixingzhe2/article/details/86167859
• Matin RedLock http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html