基於Redis的限流系統的設計「轉」

基於Redis的限流系統的設計，主要會談及限流系統中限流策略這個功能的設計；在實現方面，算法使用的是令牌桶算法來，訪問Redis使用lua腳本。

1、概念

限流是對系統的出入流量進行控制，防止大流量出入，導致資源不足，系統不穩定。

限流系統是對資源訪問的控制組件，控制主要的兩個功能：限流策略和熔斷策略，對於熔斷策略，不同的系統有不同的熔斷策略訴求，有的系統希望直接拒絕、有的系統希望排隊等待、有的系統希望服務降級、有的系統會定製自己的熔斷策略，很難一一列舉，所以本文只針對限流策略這個功能做詳細的設計。

針對限流策略這個功能，限流系統中有兩個基礎概念：資源和策略。

• 資源 ：或者叫稀缺資源，被流量控制的對象；比如寫接口、外部商戶接口、大流量下的讀接口

• 策略 ：限流策略由限流算法和可調節的參數兩部分組成

注：熔斷策略：超出速率閾值的請求的處理策略，是我自己理解的一個叫法，不是業界主流的說法。

2、限流算法

• 限制瞬時併發數

• 限制時間窗最大請求數

• 令牌桶

2.1、限制瞬時併發數

定義：瞬時併發數，系統同時處理的請求/事務數量

優點：這個算法能夠實現控制併發數的效果

缺點：使用場景比較單一，一般用來對入流量進行控制

java偽代碼實現：

AtomicInteger atomic = new AtomicInteger(1)try {  if(atomic.incrementAndGet() > 限流數) {  //熔斷邏輯 } else { //處理邏輯 } } finally { atomic.decrementAndGet();}

2.2、限制時間窗最大請求數

定義：時間窗最大請求數，指定的時間範圍內允許的最大請求數

優點：這個算法能夠滿足絕大多數的流控需求，通過時間窗最大請求數可以直接換算出最大的QPS（QPS = 請求數/時間窗）

缺點：這種方式可能會出現流量不平滑的情況，時間窗內一小段流量佔比特別大

lua代碼實現：

--- 資源唯一標識local key = KEYS[1]--- 時間窗最大併發數local max_window_concurrency = tonumber(ARGV[1]) --- 時間窗local window = tonumber(ARGV[2]) --- 時間窗內當前併發數local curr_window_concurrency = tonumber(redis.call('get', key) or 0) if current + 1 > limit then return falseelse redis.call("INCRBY", key,1)  if window > -1 then redis.call("expire", key,window)  end return trueend

2.3、令牌桶

算法描述

• 假如用戶配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中

• 假設桶中最多可以存放b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丟棄

• 當流量以速率v進入，從桶中以速率v取令牌，拿到令牌的流量通過，拿不到令牌流量不通過，執行熔斷邏輯

屬性

• 長期來看，符合流量的速率是受到令牌添加速率的影響，被穩定為：r

• 因為令牌桶有一定的存儲量，可以抵擋一定的流量突發情況

• M是以字節/秒為單位的最大可能傳輸速率：M>r

• T max = b/(M-r) 承受最大傳輸速率的時間

• B max = T max * M 承受最大傳輸速率的時間內傳輸的流量

優點：流量比較平滑，並且可以抵擋一定的流量突發情況

因為我們限流系統的實現就是基於令牌桶這個算法，具體的代碼實現參考下文。

3、工程實現

3.1、技術選型

• mysql:存儲限流策略的參數等元數據

• redis+lua:令牌桶算法實現

注：因為我們把redis 定位為：緩存、計算媒介，所以元數據都是存在db中

3.2、架構圖

3.3、 數據結構

限流系統的實現是基於redis的，本可以和應用無關，但是為了做限流元數據配置的統一管理，按應用維度管理和使用，在數據結構中加入了apps這個字段，出現問題，排查起來也比較方便。

3.4、代碼實現

3.4.1、代碼實現遇到的問題

參考令牌桶的算法描述，一般思路是在RateLimiter-client放一個重複執行的線程，線程根據配置往令牌桶裡添加令牌，這樣的實現由如下缺點：

• 需要為每個令牌桶配置添加一個重複執行的線程

• 重複的間隔精度不夠精確：線程需要每1/r秒向桶裡添加一個令牌，當r>1000 時間線程執行的時間間隔根本沒辦法設置（從後面性能測試的變現來看RateLimiter-client 是可以承擔 QPS > 5000 的請求速率）

3.4.2、解決方案

基於上面的缺點，參考了google的guava中RateLimiter中的實現，我們使用了觸發式添加令牌的方式。

算法描述

• 基於上述的令牌桶算法

• 將添加令牌改成觸發式的方式，取令牌的是做添加令牌的動作

• 在去令牌的時候，通過計算上一次添加令牌和當前的時間差，計算出這段間應該添加的令牌數，然後往桶裡添加

• curr_mill_second = 當前毫秒數

• last_mill_second = 上一次添加令牌的毫秒數

• r = 添加令牌的速率

• reserve_permits = (curr_mill_second-last_mill_second)/1000 * r

• 添加完令牌之後再執行取令牌邏輯

3.4.3、 lua代碼實現

--- 獲取令牌--- 返回碼--- 0 沒有令牌桶配置--- -1 表示取令牌失敗，也就是桶裡沒有令牌--- 1 表示取令牌成功--- @param key 令牌（資源）的唯一標識--- @param permits 請求令牌數量--- @param curr_mill_second 當前毫秒數--- @param context 使用令牌的應用標識local function acquire(key, permits, curr_mill_second, context) local rate_limit_info = redis.pcall("HMGET", key, "last_mill_second", "curr_permits", "max_permits", "rate", "apps")  local last_mill_second = rate_limit_info[1]  local curr_permits = tonumber(rate_limit_info[2])  local max_permits = tonumber(rate_limit_info[3])  local rate = rate_limit_info[4]  local apps = rate_limit_info[5]  --- 標識沒有配置令牌桶 if type(apps) == 'boolean' or apps == nil or not contains(apps, context) then return 0 end local local_curr_permits = max_permits;  --- 令牌桶剛剛創建，上一次獲取令牌的毫秒數為空 --- 根據和上一次向桶裡添加令牌的時間和當前時間差，觸發式往桶裡添加令牌 --- 並且更新上一次向桶裡添加令牌的時間 --- 如果向桶裡添加的令牌數不足一個，則不更新上一次向桶裡添加令牌的時間 if (type(last_mill_second) ~= 'boolean' and last_mill_second ~= false and last_mill_second ~= nil) then local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate)  local expect_curr_permits = reverse_permits + curr_permits; local_curr_permits = math.min(expect_curr_permits, max_permits);  --- 大於0表示不是第一次獲取令牌，也沒有向桶裡添加令牌 if (reverse_permits > 0) then redis.pcall("HSET", key, "last_mill_second", curr_mill_second)  end else redis.pcall("HSET", key, "last_mill_second", curr_mill_second)  end local result = -1 if (local_curr_permits - permits >= 0) then result = 1 redis.pcall("HSET", key, "curr_permits", local_curr_permits - permits)  else redis.pcall("HSET", key, "curr_permits", local_curr_permits)  end return resultend

3.4.4、管理界面

限流的配置是和應用關聯的，為了更夠更好的管理配置，需要一個統一的管理頁面去對配置進行管控：

• 按應用對限流配置進行管理

• 不同的人分配不同的權限；相關人員有查看配置的權限，負責人有修改和刪除配置的權限

3.5、性能測試

配置：aws-elasticcache-redis 2核4g

因為Ratelimiter-client的功能比較簡單，基本上是redis的性能打個折扣。

• 單線程取令牌：Ratelimiter-client的 QPS = 250/s

• 10個線程取令牌：Ratelimiter-client的 QPS = 2000/s

• 100個線程取令牌：Ratelimiter-client的 QPS = 5000/s

4、總結

限流系統從設計到實現都比較簡單，但是確實很實用，用四個字來形容就是：短小強悍，其中比較重要的是結合公司的權限體系和系統結構，設計出符合自己公司規範的限流系統。

不足：

• redis 我們用的是單點redis，只做了主從，沒有使用redis高可用集群（可能使用redis高可用集群，會帶來新的問題）

• 限流系統目前只做了應用層面的實現，沒有做接口網關上的實現

• 熔斷策略需要自己定製，如果實現的好一點，可以給一些常用的熔斷策略模板