天天看點
傳回

基于Redis和Lua的分布式限流

基于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指令。

# test.lua腳本的内容
local test = redis.call("get", "test")
local time = redis.call("get", "time")
redis.call("setex", "test", 10, "xx")
redis.call("setex", "time", 10, "xx")
return {test, time}

# 将腳本導入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 seconds
50 parallel clients
3 bytes payload
keep alive: 1

93.54% <= 1 milliseconds
99.90% <= 2 milliseconds
99.97% <= 3 milliseconds
99.98% <= 4 milliseconds
99.99% <= 5 milliseconds
100.00% <= 6 milliseconds
100.00% <= 7 milliseconds
100.00% <= 7 milliseconds
49997.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

是微服務架構

Spring Cloud

的網關元件，它基于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 = 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) 減消耗令牌數( requested )，并設定擷取成功( allowed_num = 1 ) 。
  new_tokens = filled_tokens - requested
  allowed_num = 1
end       

-- 設定令牌桶剩餘令牌數( 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

參考

算法 NoSQL java Redis spring Redis支援lua lua Redis問題 Redis分頁 lua Redis報錯 Redis租戶
上一篇: 如何從根源上解決 HDFS 小檔案問題
下一篇: 【圖像重建】基于matlab疊代步長自适應圖像超分辨重建【含Matlab源碼 048期】

繼續閱讀