溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“怎么使用Go+Redis實現(xiàn)常見限流算法”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當，希望這篇“怎么使用Go+Redis實現(xiàn)常見限流算法”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
使用Redis實現(xiàn)固定窗口比較簡單，主要是由于固定窗口同時只會存在一個窗口，所以我們可以在第一次進入窗口時使用pexpire命令設置過期時間為窗口時間大小，這樣窗口會隨過期時間而失效，同時我們使用incr命令增加窗口計數(shù)。
因為我們需要在counter==1的時候設置窗口的過期時間，為了保證原子性，我們使用簡單的Lua腳本實現(xiàn)。
const fixedWindowLimiterTryAcquireRedisScript = `
-- ARGV[1]: 窗口時間大小
-- ARGV[2]: 窗口請求上限
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
-- 獲取原始值
local counter = tonumber(redis.call("get", KEYS[1]))
if counter == nil then
counter = 0
end
-- 若到達窗口請求上限，請求失敗
if counter >= limit then
return 0
end
-- 窗口值+1
redis.call("incr", KEYS[1])
if counter == 0 then
redis.call("pexpire", KEYS[1], window)
end
return 1
`package redis
import (
"context"
"errors"
"github.com/go-redis/redis/v8"
"time"
)
// FixedWindowLimiter 固定窗口限流器
type FixedWindowLimiter struct {
limit int // 窗口請求上限
window int // 窗口時間大小
client *redis.Client // Redis客戶端
script *redis.Script // TryAcquire腳本
}
func NewFixedWindowLimiter(client *redis.Client, limit int, window time.Duration) (*FixedWindowLimiter, error) {
// redis過期時間精度最大到毫秒，因此窗口必須能被毫秒整除
if window%time.Millisecond != 0 {
return nil, errors.New("the window uint must not be less than millisecond")
}
return &FixedWindowLimiter{
limit: limit,
window: int(window / time.Millisecond),
client: client,
script: redis.NewScript(fixedWindowLimiterTryAcquireRedisScript),
}, nil
}
func (l *FixedWindowLimiter) TryAcquire(ctx context.Context, resource string) error {
success, err := l.script.Run(ctx, l.client, []string{resource}, l.window, l.limit).Bool()
if err != nil {
return err
}
// 若到達窗口請求上限，請求失敗
if !success {
return ErrAcquireFailed
}
return nil
}我們使用Redis的hash存儲每個小窗口的計數(shù)，每次請求會把所有有效窗口的計數(shù)累加到count，使用hdel刪除失效窗口，最后判斷窗口的總計數(shù)是否大于上限。
我們基本上把所有的邏輯都放到Lua腳本里面，其中大頭是對hash的遍歷，時間復雜度是O(N)，N是小窗口數(shù)量，所以小窗口數(shù)量最好不要太多。
const slidingWindowLimiterTryAcquireRedisScriptHashImpl = `
-- ARGV[1]: 窗口時間大小
-- ARGV[2]: 窗口請求上限
-- ARGV[3]: 當前小窗口值
-- ARGV[4]: 起始小窗口值
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local currentSmallWindow = tonumber(ARGV[3])
local startSmallWindow = tonumber(ARGV[4])
-- 計算當前窗口的請求總數(shù)
local counters = redis.call("hgetall", KEYS[1])
local count = 0
for i = 1, #(counters) / 2 do
local smallWindow = tonumber(counters[i * 2 - 1])
local counter = tonumber(counters[i * 2])
if smallWindow < startSmallWindow then
redis.call("hdel", KEYS[1], smallWindow)
else
count = count + counter
end
end
-- 若到達窗口請求上限，請求失敗
if count >= limit then
return 0
end
-- 若沒到窗口請求上限，當前小窗口計數(shù)器+1，請求成功
redis.call("hincrby", KEYS[1], currentSmallWindow, 1)
redis.call("pexpire", KEYS[1], window)
return 1
`package redis
import (
"context"
"errors"
"github.com/go-redis/redis/v8"
"time"
)
// SlidingWindowLimiter 滑動窗口限流器
type SlidingWindowLimiter struct {
limit int // 窗口請求上限
window int64 // 窗口時間大小
smallWindow int64 // 小窗口時間大小
smallWindows int64 // 小窗口數(shù)量
client *redis.Client // Redis客戶端
script *redis.Script // TryAcquire腳本
}
func NewSlidingWindowLimiter(client *redis.Client, limit int, window, smallWindow time.Duration) (
*SlidingWindowLimiter, error) {
// redis過期時間精度最大到毫秒，因此窗口必須能被毫秒整除
if window%time.Millisecond != 0 || smallWindow%time.Millisecond != 0 {
return nil, errors.New("the window uint must not be less than millisecond")
}
// 窗口時間必須能夠被小窗口時間整除
if window%smallWindow != 0 {
return nil, errors.New("window cannot be split by integers")
}
return &SlidingWindowLimiter{
limit: limit,
window: int64(window / time.Millisecond),
smallWindow: int64(smallWindow / time.Millisecond),
smallWindows: int64(window / smallWindow),
client: client,
script: redis.NewScript(slidingWindowLimiterTryAcquireRedisScriptHashImpl),
}, nil
}
func (l *SlidingWindowLimiter) TryAcquire(ctx context.Context, resource string) error {
// 獲取當前小窗口值
currentSmallWindow := time.Now().UnixMilli() / l.smallWindow * l.smallWindow
// 獲取起始小窗口值
startSmallWindow := currentSmallWindow - l.smallWindow*(l.smallWindows-1)
success, err := l.script.Run(
ctx, l.client, []string{resource}, l.window, l.limit, currentSmallWindow, startSmallWindow).Bool()
if err != nil {
return err
}
// 若到達窗口請求上限，請求失敗
if !success {
return ErrAcquireFailed
}
return nil
}如果小窗口數(shù)量特別多，可以使用list優(yōu)化時間復雜度，list的結構是：
[counter, smallWindow1, count1, smallWindow2, count2, smallWindow3, count3...]
也就是我們使用list的第一個元素存儲計數(shù)器，每個窗口用兩個元素表示，第一個元素表示小窗口值，第二個元素表示這個小窗口的計數(shù)。不直接把小窗口值和計數(shù)放到一個元素里是因為Redis Lua腳本里沒有分割字符串的函數(shù)。
具體操作流程：
1.獲取list長度
2.如果長度是0，設置counter，長度+1
3.如果長度大于1，獲取第二第三個元素
如果該值小于起始小窗口值，counter-第三個元素的值，刪除第二第三個元素，長度-2
4.如果counter大于等于limit，請求失敗
5.如果長度大于1，獲取倒數(shù)第二第一個元素
如果倒數(shù)第二個元素小窗口值大于等于當前小窗口值，表示當前請求因為網(wǎng)絡延遲的問題，到達服務器的時候，窗口已經(jīng)過時了，把倒數(shù)第二個元素當成當前小窗口（因為它更新），倒數(shù)第一個元素值+1
否則，添加新的窗口值，添加新的計數(shù)（1），更新過期時間
6.否則，添加新的窗口值，添加新的計數(shù)（1），更新過期時間
7.counter + 1
8.返回成功
const slidingWindowLimiterTryAcquireRedisScriptListImpl = `
-- ARGV[1]: 窗口時間大小
-- ARGV[2]: 窗口請求上限
-- ARGV[3]: 當前小窗口值
-- ARGV[4]: 起始小窗口值
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local currentSmallWindow = tonumber(ARGV[3])
local startSmallWindow = tonumber(ARGV[4])
-- 獲取list長度
local len = redis.call("llen", KEYS[1])
-- 如果長度是0，設置counter，長度+1
local counter = 0
if len == 0 then
redis.call("rpush", KEYS[1], 0)
redis.call("pexpire", KEYS[1], window)
len = len + 1
else
-- 如果長度大于1，獲取第二第個元素
local smallWindow1 = tonumber(redis.call("lindex", KEYS[1], 1))
counter = tonumber(redis.call("lindex", KEYS[1], 0))
-- 如果該值小于起始小窗口值
if smallWindow1 < startSmallWindow then
local count1 = redis.call("lindex", KEYS[1], 2)
-- counter-第三個元素的值
counter = counter - count1
-- 長度-2
len = len - 2
-- 刪除第二第三個元素
redis.call("lrem", KEYS[1], 1, smallWindow1)
redis.call("lrem", KEYS[1], 1, count1)
end
end
-- 若到達窗口請求上限，請求失敗
if counter >= limit then
return 0
end
-- 如果長度大于1，獲取倒數(shù)第二第一個元素
if len > 1 then
local smallWindown = tonumber(redis.call("lindex", KEYS[1], -2))
-- 如果倒數(shù)第二個元素小窗口值大于等于當前小窗口值
if smallWindown >= currentSmallWindow then
-- 把倒數(shù)第二個元素當成當前小窗口（因為它更新），倒數(shù)第一個元素值+1
local countn = redis.call("lindex", KEYS[1], -1)
redis.call("lset", KEYS[1], -1, countn + 1)
else
-- 否則，添加新的窗口值，添加新的計數(shù)（1），更新過期時間
redis.call("rpush", KEYS[1], currentSmallWindow, 1)
redis.call("pexpire", KEYS[1], window)
end
else
-- 否則，添加新的窗口值，添加新的計數(shù)（1），更新過期時間
redis.call("rpush", KEYS[1], currentSmallWindow, 1)
redis.call("pexpire", KEYS[1], window)
end
-- counter + 1并更新
redis.call("lset", KEYS[1], 0, counter + 1)
return 1
`算法都是操作list頭部或者尾部，所以時間復雜度接近O(1)
漏桶需要保存當前水位和上次放水時間，因此我們使用hash來保存這兩個值。
const leakyBucketLimiterTryAcquireRedisScript = `
-- ARGV[1]: 最高水位
-- ARGV[2]: 水流速度/秒
-- ARGV[3]: 當前時間（秒）
local peakLevel = tonumber(ARGV[1])
local currentVelocity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local lastTime = tonumber(redis.call("hget", KEYS[1], "lastTime"))
local currentLevel = tonumber(redis.call("hget", KEYS[1], "currentLevel"))
-- 初始化
if lastTime == nil then
lastTime = now
currentLevel = 0
redis.call("hmset", KEYS[1], "currentLevel", currentLevel, "lastTime", lastTime)
end
-- 嘗試放水
-- 距離上次放水的時間
local interval = now - lastTime
if interval > 0 then
-- 當前水位-距離上次放水的時間(秒)*水流速度
local newLevel = currentLevel - interval * currentVelocity
if newLevel < 0 then
newLevel = 0
end
currentLevel = newLevel
redis.call("hmset", KEYS[1], "currentLevel", newLevel, "lastTime", now)
end
-- 若到達最高水位，請求失敗
if currentLevel >= peakLevel then
return 0
end
-- 若沒有到達最高水位，當前水位+1，請求成功
redis.call("hincrby", KEYS[1], "currentLevel", 1)
redis.call("expire", KEYS[1], peakLevel / currentVelocity)
return 1
`package redis
import (
"context"
"github.com/go-redis/redis/v8"
"time"
)
// LeakyBucketLimiter 漏桶限流器
type LeakyBucketLimiter struct {
peakLevel int // 最高水位
currentVelocity int // 水流速度/秒
client *redis.Client // Redis客戶端
script *redis.Script // TryAcquire腳本
}
func NewLeakyBucketLimiter(client *redis.Client, peakLevel, currentVelocity int) *LeakyBucketLimiter {
return &LeakyBucketLimiter{
peakLevel: peakLevel,
currentVelocity: currentVelocity,
client: client,
script: redis.NewScript(leakyBucketLimiterTryAcquireRedisScript),
}
}
func (l *LeakyBucketLimiter) TryAcquire(ctx context.Context, resource string) error {
// 當前時間
now := time.Now().Unix()
success, err := l.script.Run(ctx, l.client, []string{resource}, l.peakLevel, l.currentVelocity, now).Bool()
if err != nil {
return err
}
// 若到達窗口請求上限，請求失敗
if !success {
return ErrAcquireFailed
}
return nil
}令牌桶可以看作是漏桶的相反算法，它們一個是把水倒進桶里，一個是從桶里獲取令牌。
const tokenBucketLimiterTryAcquireRedisScript = `
-- ARGV[1]: 容量
-- ARGV[2]: 發(fā)放令牌速率/秒
-- ARGV[3]: 當前時間（秒）
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local lastTime = tonumber(redis.call("hget", KEYS[1], "lastTime"))
local currentTokens = tonumber(redis.call("hget", KEYS[1], "currentTokens"))
-- 初始化
if lastTime == nil then
lastTime = now
currentTokens = capacity
redis.call("hmset", KEYS[1], "currentTokens", currentTokens, "lastTime", lastTime)
end
-- 嘗試發(fā)放令牌
-- 距離上次發(fā)放令牌的時間
local interval = now - lastTime
if interval > 0 then
-- 當前令牌數(shù)量+距離上次發(fā)放令牌的時間(秒)*發(fā)放令牌速率
local newTokens = currentTokens + interval * rate
if newTokens > capacity then
newTokens = capacity
end
currentTokens = newTokens
redis.call("hmset", KEYS[1], "currentTokens", newTokens, "lastTime", now)
end
-- 如果沒有令牌，請求失敗
if currentTokens == 0 then
return 0
end
-- 果有令牌，當前令牌-1，請求成功
redis.call("hincrby", KEYS[1], "currentTokens", -1)
redis.call("expire", KEYS[1], capacity / rate)
return 1
`package redis
import (
"context"
"github.com/go-redis/redis/v8"
"time"
)
// TokenBucketLimiter 令牌桶限流器
type TokenBucketLimiter struct {
capacity int // 容量
rate int // 發(fā)放令牌速率/秒
client *redis.Client // Redis客戶端
script *redis.Script // TryAcquire腳本
}
func NewTokenBucketLimiter(client *redis.Client, capacity, rate int) *TokenBucketLimiter {
return &TokenBucketLimiter{
capacity: capacity,
rate: rate,
client: client,
script: redis.NewScript(tokenBucketLimiterTryAcquireRedisScript),
}
}
func (l *TokenBucketLimiter) TryAcquire(ctx context.Context, resource string) error {
// 當前時間
now := time.Now().Unix()
success, err := l.script.Run(ctx, l.client, []string{resource}, l.capacity, l.rate, now).Bool()
if err != nil {
return err
}
// 若到達窗口請求上限，請求失敗
if !success {
return ErrAcquireFailed
}
return nil
}算法流程與滑動窗口相同，只是它可以指定多個策略，同時在請求失敗的時候，需要通知調(diào)用方是被哪個策略所攔截。
const slidingLogLimiterTryAcquireRedisScriptHashImpl = `
-- ARGV[1]: 當前小窗口值
-- ARGV[2]: 第一個策略的窗口時間大小
-- ARGV[i * 2 + 1]: 每個策略的起始小窗口值
-- ARGV[i * 2 + 2]: 每個策略的窗口請求上限
local currentSmallWindow = tonumber(ARGV[1])
-- 第一個策略的窗口時間大小
local window = tonumber(ARGV[2])
-- 第一個策略的起始小窗口值
local startSmallWindow = tonumber(ARGV[3])
local strategiesLen = #(ARGV) / 2 - 1
-- 計算每個策略當前窗口的請求總數(shù)
local counters = redis.call("hgetall", KEYS[1])
local counts = {}
-- 初始化counts
for j = 1, strategiesLen do
counts[j] = 0
end
for i = 1, #(counters) / 2 do
local smallWindow = tonumber(counters[i * 2 - 1])
local counter = tonumber(counters[i * 2])
if smallWindow < startSmallWindow then
redis.call("hdel", KEYS[1], smallWindow)
else
for j = 1, strategiesLen do
if smallWindow >= tonumber(ARGV[j * 2 + 1]) then
counts[j] = counts[j] + counter
end
end
end
end
-- 若到達對應策略窗口請求上限，請求失敗，返回違背的策略下標
for i = 1, strategiesLen do
if counts[i] >= tonumber(ARGV[i * 2 + 2]) then
return i - 1
end
end
-- 若沒到窗口請求上限，當前小窗口計數(shù)器+1，請求成功
redis.call("hincrby", KEYS[1], currentSmallWindow, 1)
redis.call("pexpire", KEYS[1], window)
return -1
`package redis
import (
"context"
"errors"
"fmt"
"github.com/go-redis/redis/v8"
"sort"
"time"
)
// ViolationStrategyError 違背策略錯誤
type ViolationStrategyError struct {
Limit int // 窗口請求上限
Window time.Duration // 窗口時間大小
}
func (e *ViolationStrategyError) Error() string {
return fmt.Sprintf("violation strategy that limit = %d and window = %d", e.Limit, e.Window)
}
// SlidingLogLimiterStrategy 滑動日志限流器的策略
type SlidingLogLimiterStrategy struct {
limit int // 窗口請求上限
window int64 // 窗口時間大小
smallWindows int64 // 小窗口數(shù)量
}
func NewSlidingLogLimiterStrategy(limit int, window time.Duration) *SlidingLogLimiterStrategy {
return &SlidingLogLimiterStrategy{
limit: limit,
window: int64(window),
}
}
// SlidingLogLimiter 滑動日志限流器
type SlidingLogLimiter struct {
strategies []*SlidingLogLimiterStrategy // 滑動日志限流器策略列表
smallWindow int64 // 小窗口時間大小
client *redis.Client // Redis客戶端
script *redis.Script // TryAcquire腳本
}
func NewSlidingLogLimiter(client *redis.Client, smallWindow time.Duration, strategies ...*SlidingLogLimiterStrategy) (
*SlidingLogLimiter, error) {
// 復制策略避免被修改
strategies = append(make([]*SlidingLogLimiterStrategy, 0, len(strategies)), strategies...)
// 不能不設置策略
if len(strategies) == 0 {
return nil, errors.New("must be set strategies")
}
// redis過期時間精度最大到毫秒，因此窗口必須能被毫秒整除
if smallWindow%time.Millisecond != 0 {
return nil, errors.New("the window uint must not be less than millisecond")
}
smallWindow = smallWindow / time.Millisecond
for _, strategy := range strategies {
if strategy.window%int64(time.Millisecond) != 0 {
return nil, errors.New("the window uint must not be less than millisecond")
}
strategy.window = strategy.window / int64(time.Millisecond)
}
// 排序策略，窗口時間大的排前面，相同窗口上限大的排前面
sort.Slice(strategies, func(i, j int) bool {
a, b := strategies[i], strategies[j]
if a.window == b.window {
return a.limit > b.limit
}
return a.window > b.window
})
for i, strategy := range strategies {
// 隨著窗口時間變小，窗口上限也應該變小
if i > 0 {
if strategy.limit >= strategies[i-1].limit {
return nil, errors.New("the smaller window should be the smaller limit")
}
}
// 窗口時間必須能夠被小窗口時間整除
if strategy.window%int64(smallWindow) != 0 {
return nil, errors.New("window cannot be split by integers")
}
strategy.smallWindows = strategy.window / int64(smallWindow)
}
return &SlidingLogLimiter{
strategies: strategies,
smallWindow: int64(smallWindow),
client: client,
script: redis.NewScript(slidingLogLimiterTryAcquireRedisScriptHashImpl),
}, nil
}
func (l *SlidingLogLimiter) TryAcquire(ctx context.Context, resource string) error {
// 獲取當前小窗口值
currentSmallWindow := time.Now().UnixMilli() / l.smallWindow * l.smallWindow
args := make([]interface{}, len(l.strategies)*2+2)
args[0] = currentSmallWindow
args[1] = l.strategies[0].window
// 獲取每個策略的起始小窗口值
for i, strategy := range l.strategies {
args[i*2+2] = currentSmallWindow - l.smallWindow*(strategy.smallWindows-1)
args[i*2+3] = strategy.limit
}
index, err := l.script.Run(
ctx, l.client, []string{resource}, args...).Int()
if err != nil {
return err
}
// 若到達窗口請求上限，請求失敗
if index != -1 {
return &ViolationStrategyError{
Limit: l.strategies[index].limit,
Window: time.Duration(l.strategies[index].window),
}
}
return nil
}讀到這里，這篇“怎么使用Go+Redis實現(xiàn)常見限流算法”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內(nèi)容的文章，歡迎關注億速云行業(yè)資訊頻道。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
