Cara menggunakan Go+Redis untuk melaksanakan algoritma pengehadan semasa biasa

Tetingkap tetap

Menggunakan Redis untuk melaksanakan tetingkap tetap agak mudah, terutamanya kerana hanya akan ada satu tetingkap tetap pada masa yang sama, jadi kami boleh melakukannya buat kali pertama Apabila memasuki tetingkap, gunakan perintah pexpire untuk menetapkan masa tamat tempoh kepada saiz masa tetingkap, supaya tetingkap akan tamat tempoh dengan masa tamat tempoh Pada masa yang sama, kami menggunakan incr perintah untuk meningkatkan kiraan tetingkap.

Oleh kerana kita perlu menetapkan masa tamat tempoh tetingkap apabila counter==1, untuk memastikan atomicity, kami menggunakan pelaksanaan skrip Lua yang mudah.

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
`

rrree

Tetingkap gelongsor

pelaksanaan cincang

Kami menggunakan hash Redis untuk menyimpan kiraan setiap tetingkap kecil dan setiap permintaan akan mengumpulkan kiraan semua 有效窗口 Pergi ke count, gunakan hdel untuk memadamkan tetingkap tidak sah, dan akhirnya tentukan sama ada jumlah bilangan tetingkap adalah lebih besar daripada had atas.

Kami pada asasnya meletakkan semua logik ke dalam skrip Lua Bahagian besar ialah traversal hash Kerumitan masa ialah O(N ialah bilangan tingkap kecil tingkap adalah yang terbesar. Adalah lebih baik untuk tidak mempunyai terlalu banyak.

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
}

rrree

Pelaksanaan senarai

Jika bilangan tingkap kecil sangat besar, anda boleh menggunakan list untuk mengoptimumkan kerumitan masa Struktur senarai ialah:

[counter, smallWindow1, count1, smallWindow2, count2, smallWindow3, count3...]

Iaitu, kami menggunakan elemen pertama senarai untuk menyimpan pembilang Setiap tetingkap diwakili oleh dua elemen Elemen pertama mewakili nilai tetingkap kecil, dan elemen kedua mewakili kiraan tingkap kecil ini. Memandangkan skrip Redis Lua tidak menyokong fungsi pemisahan rentetan, nilai dan kiraan tetingkap kecil tidak boleh diletakkan dalam elemen yang sama.

Proses operasi khusus:

1 Dapatkan panjang senarai

2 Jika panjangnya 0, tetapkan pembilang, panjang + 1

3. Jika panjang lebih daripada 1, dapatkan elemen kedua dan ketiga

Jika nilai kurang daripada nilai tetingkap kecil permulaan, balas nilai elemen ketiga, padamkan elemen kedua dan ketiga, panjang-2

4 Jika pembilang lebih besar daripada atau sama dengan had, permintaan gagal

5 Jika panjang lebih daripada 1, dapatkan elemen kedua hingga terakhir

• Jika elemen kedua hingga terakhir Nilai tetingkap kecil elemen adalah lebih besar daripada atau sama dengan nilai tetingkap kecil semasa, yang bermaksud bahawa disebabkan masalah kelewatan rangkaian, tetingkap telah tamat tempoh apabila permintaan semasa mencapai pelayan Elemen kedua dianggap sebagai tetingkap kecil semasa (kerana ia dikemas kini), dan elemen terakhir dianggap sebagai tetingkap kecil semasa (kerana ia dikemas kini dengan nilai elemen +1

• Jika tidak, tambah nilai tetingkap baharu, tambah kiraan baharu (1), kemas kini masa tamat tempoh

6 Jika tidak, tambah nilai tetingkap baharu, tambah kiraan baharu (1), kemas kini masa tamat tempoh

7.kaunter + 1

8. Kembalikan kejayaan

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])

-- 计算当前窗口的请求总数
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

-- 若没到窗口请求上限，当前小窗口计数器+1，请求成功
redis.call("hincrby", KEYS[1], currentSmallWindow, 1)
redis.call("pexpire", KEYS[1], window)
return 1
`

Algoritma ialah semua operasi listKepala atau ekor, jadi kerumitan masa hampir dengan O(1)

Algoritma baldi bocor

Badi bocor perlu menjimatkan paras air semasa dan masa keluaran air terakhir, jadi kami menggunakan hash untuk menjimatkan kedua-dua nilai ini.

package redis

import (
   "context"
   "errors"
   "github.com/go-redis/redis/v8"
   "time"
)

// SlidingWindowLimiter 滑动窗口限流器
type SlidingWindowLimiter struct {
   limit        int           // 窗口请求上限
   window       int64         // 窗口时间大小
   smallWindow  int64         // 小窗口时间大小
   smallWindows int64         // 小窗口数量
   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
}

rrree

Token Baldi

Token Baldi boleh dilihat sebagai bertentangan dengan algoritma baldi bocor Salah satunya ialah menuang air ke dalam baldi, dan satu lagi adalah untuk mendapatkan token daripada baldi.

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，获取倒数第二第一个元素
if len > 1 then
   local smallWindown = tonumber(redis.call("lindex", KEYS[1], -2))
   -- 如果倒数第二个元素小窗口值大于等于当前小窗口值
   if smallWindown >= currentSmallWindow then
      -- 把倒数第二个元素当成当前小窗口（因为它更新），倒数第一个元素值+1
      local countn = redis.call("lindex", KEYS[1], -1)
      redis.call("lset", KEYS[1], -1, countn + 1)
   else 
      -- 否则，添加新的窗口值，添加新的计数（1），更新过期时间
      redis.call("rpush", KEYS[1], currentSmallWindow, 1)
      redis.call("pexpire", KEYS[1], window)
   end
else 
   -- 否则，添加新的窗口值，添加新的计数（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
`

rrree

Log gelongsor

Proses algoritma adalah sama dengan tetingkap gelongsor, kecuali ia boleh menentukan berbilang strategi Pada masa yang sama, apabila permintaan gagal, pemanggil perlu dimaklumkan strategi manakah yang dipintas.

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
`

rrree

Atas ialah kandungan terperinci Cara menggunakan Go+Redis untuk melaksanakan algoritma pengehadan semasa biasa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!