令牌桶是一種用于控制請(qǐng)求速率的算法。它可以限制在特定時(shí)間內(nèi)可以提交的請(qǐng)求數(shù)量，以避免超過(guò)系統(tǒng)的處理能力。
令牌桶概念
令牌桶是一種用于控制請(qǐng)求速率的算法。它可以限制在特定時(shí)間內(nèi)可以提交的請(qǐng)求數(shù)量，以避免超過(guò)系統(tǒng)的處理能力。令牌桶算法基于一個(gè)抽象的“令牌桶”，該桶中可以存放一定數(shù)量的令牌。在每個(gè)時(shí)間單位內(nèi)，新的令牌會(huì)按一定的速率添加到桶中。如果一個(gè)請(qǐng)求需要處理，就需要從桶中消耗一定數(shù)量的令牌。如果桶中沒有足夠的令牌，則請(qǐng)求將被拒絕。令牌桶算法的優(yōu)點(diǎn)在于它可以根據(jù)當(dāng)前的系統(tǒng)負(fù)載動(dòng)態(tài)調(diào)整請(qǐng)求的處理速率，并可以控制請(qǐng)求的速率和延遲。
優(yōu)缺點(diǎn)
- 可能會(huì)導(dǎo)致請(qǐng)求延遲，如果請(qǐng)求速率較高，則桶中的令牌可能會(huì)被消耗完，導(dǎo)致新的請(qǐng)求無(wú)法被處理。
- 可以避免系統(tǒng)被大量請(qǐng)求涌入而導(dǎo)致的資源耗盡，并可以根據(jù)實(shí)際情況動(dòng)態(tài)調(diào)整請(qǐng)求處理速率。
分析
核心參數(shù)：
- 桶的容量：它表示桶中最多能存放多少令牌。
- 令牌添加速率：每個(gè)時(shí)間單位內(nèi)（1s）令牌桶中能添加的令牌數(shù)量。
- 每個(gè)請(qǐng)求需要的令牌數(shù)量：表示每個(gè)請(qǐng)求需要消耗的令牌數(shù)量，一般默認(rèn)為 1。
其中令牌添加速率的實(shí)現(xiàn)方式為：維護(hù)一個(gè)時(shí)間戳，來(lái)記錄上一次添加令牌的時(shí)間，以便在處理請(qǐng)求時(shí)計(jì)算令牌添加速率。
綜上可以進(jìn)行代碼設(shè)計(jì)：
public class RedisRateLimiterReq {
/**
* 限流唯一性標(biāo)識(shí)
*/
@NotBlank
private String id;
/**
* 令牌添加速率
*/
@Min(1)
private int replenishRate;
/**
* 桶的容量
*/
@Min(0)
private int burstCapacity = 1;
/**
* 每個(gè)請(qǐng)求需要的令牌數(shù)量
*/
@Min(1)
private int requestedTokens = 1;
}基于Redis+lua的分布式令牌桶限流
redis key 設(shè)計(jì)：
- Key[1] ：記錄桶的剩余容量
- Key[2] ：記錄桶上次刷新時(shí)間，以此推算當(dāng)前需要填入的令牌數(shù)量
- 第一次：需要新填入的令牌數(shù)量 = (當(dāng)前時(shí)間 - 0) * 速率
- 其他后：需要新填入的令牌數(shù)量 = (當(dāng)前時(shí)間 - Key[2]) * 速率
綜上：當(dāng)前桶內(nèi)可用令牌數(shù) = 桶的剩余容量 + 需要新填入的令牌數(shù)量
參數(shù)設(shè)計(jì)：
- capacity：桶的容量：它表示桶中最多能存放多少令牌。
- rate：令牌添加速率：每個(gè)時(shí)間單位內(nèi)（1s）令牌桶中能添加的令牌數(shù)量。
- requested：每個(gè)請(qǐng)求需要的令牌數(shù)量：表示每個(gè)請(qǐng)求需要消耗的令牌數(shù)量，一般默認(rèn)為 1。
核心公式：
- fill_time：填充時(shí)間：capacity / rate，例如 10/2，即每秒填充 5 個(gè)令牌。
- ttl：redis key[1]、key[2] 的過(guò)期時(shí)間，填充時(shí)間*2；為什么是2倍：這樣可以保證令牌桶中的令牌能夠被充分利用，并避免過(guò)早的過(guò)期。例如，如果填充時(shí)間的值為 10 秒，那么過(guò)期時(shí)間的值就應(yīng)該設(shè)置為 20 秒。這樣，在令牌桶的生存周期內(nèi)，用戶就有足夠的時(shí)間來(lái)使用令牌桶中的令牌。
LUA 腳本
redis.replicate_commands()
-- 記錄桶的剩余容量
local tokens_key = KEYS[1]
-- 記錄桶上次刷新時(shí)間，以此推算當(dāng)前需要填入的令牌數(shù)量
-- 第一次：需要新填入的令牌數(shù)量 = (當(dāng)前時(shí)間 - 0) * 速率
-- 其他后：需要新填入的令牌數(shù)量 = (當(dāng)前時(shí)間 - Key[2]) * 速率
local timestamp_key = KEYS[2]
-- 綜上：**當(dāng)前桶內(nèi)可用令牌數(shù) = 桶的剩余容量 + 需要新填入的令牌數(shù)量**
redis.log(redis.LOG_WARNING, "tokens_key " .. tokens_key)
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = redis.call('TIME')[1]
local requested = tonumber(ARGV[4])
local fill_time = capacity/rate
-- redis key[1]、key[2] 的過(guò)期時(shí)間
-- 令牌過(guò)期時(shí)間：填充時(shí)間*2
-- 返回小于參數(shù)x的最大整數(shù)
-- 這樣可以保證令牌桶中的令牌能夠被充分利用，并避免過(guò)早的過(guò)期。
-- 例如，如果填充時(shí)間的值為 10 秒，那么過(guò)期時(shí)間的值就應(yīng)該設(shè)置為 20 秒。這樣，在令牌桶的生存周期內(nèi)，用戶就有足夠的時(shí)間來(lái)使用令牌桶中的令牌。
local ttl = math.floor(fill_time*2)
redis.log(redis.LOG_WARNING, "rate " .. ARGV[1])
redis.log(redis.LOG_WARNING, "capacity " .. ARGV[2])
redis.log(redis.LOG_WARNING, "now " .. now)
redis.log(redis.LOG_WARNING, "requested " .. ARGV[4])
redis.log(redis.LOG_WARNING, "filltime " .. fill_time)
redis.log(redis.LOG_WARNING, "ttl " .. ttl)
local last_tokens = tonumber(redis.call("get", tokens_key))
if last_tokens == nil then
last_tokens = capacity
end
redis.log(redis.LOG_WARNING, "last_tokens " .. last_tokens)
local last_refreshed = tonumber(redis.call("get", timestamp_key))
if last_refreshed == nil then
last_refreshed = 0
end
redis.log(redis.LOG_WARNING, "last_refreshed " .. last_refreshed)
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.log(redis.LOG_WARNING, "delta " .. delta)
--redis.log(redis.LOG_WARNING, "filled_tokens " .. filled_tokens)
--redis.log(redis.LOG_WARNING, "allowed_num " .. allowed_num)
--redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
if ttl > 0 then
redis.call("setex", tokens_key, ttl, new_tokens)
redis.call("setex", timestamp_key, ttl, now)
end
-- return { allowed_num, new_tokens, capacity, filled_tokens, requested, new_tokens }
return { allowed_num, new_tokens }
redis.replicate_commands() 是 Redis 客戶端的一個(gè)方法，它用于啟用命令復(fù)制（command replication）。命令復(fù)制是指，在多個(gè) Redis 實(shí)例之間復(fù)制命令，以保證數(shù)據(jù)的一致性。
例如，如果你在一個(gè) Redis 集群中執(zhí)行了一條寫入命令，那么這條命令就會(huì)被復(fù)制到集群中的其他實(shí)例中。這樣，就可以保證集群中的所有實(shí)例都保存了相同的數(shù)據(jù)，并且可以提供高可用性和數(shù)據(jù)安全性。
