Bagaimana untuk melaksanakan algoritma baldi token menggunakan Redis? (dengan kod)

Artikel ini akan berkongsi dengan anda prinsip algoritma baldi token dan memperkenalkan kaedah menggunakan Redis untuk melaksanakan algoritma baldi token saya harap ia akan membantu semua orang!

Antara algoritma pengehad semasa, terdapat algoritma baldi token, yang boleh menangani letusan trafik yang singkat, yang amat berguna dalam persekitaran kehidupan sebenar di mana trafik berada tidak terlalu seragam, had semasa tidak akan dicetuskan dengan kerap, dan ia lebih mesra kepada pemanggil.

Sebagai contoh, had semasa ialah 10qps, selalunya ia tidak akan melebihi jumlah ini, tetapi kadang-kadang ia akan mencapai 30qps, dan kemudian ia akan kembali normal tidak lama lagi, dengan mengandaikan bahawa ledakan trafik ini tidak akan mempunyai kesan ke atas kestabilan sistem , kami boleh membenarkan trafik pecah serta-merta ini pada tahap tertentu, dengan itu membawa pengalaman ketersediaan yang lebih baik kepada pengguna. Di sinilah algoritma baldi token masuk.

Prinsip Algoritma Token Bucket

Seperti yang ditunjukkan dalam rajah di bawah, prinsip asas algoritma ialah: terdapat baldi token dengan kapasiti ke dalam baldi ini. Jika bilangan token dalam baldi melebihi X, maka ia akan dibuang. Apabila memproses permintaan, anda perlu mengalih keluar token daripada baldi token terlebih dahulu. Jika anda mendapat token, teruskan pemprosesan jika anda tidak boleh mendapatkan token, tolak permintaan.

Ia boleh dilihat bahawa penetapan nombor X, Y dan Z amat penting dalam algoritma baldi token. Z hendaklah lebih besar sedikit daripada bilangan permintaan bagi setiap unit masa Y, dan sistem akan berada dalam keadaan ini untuk masa yang lama Ini menunjukkan bahawa trafik telah melebihi jangkaan, dan puncanya perlu disiasat dengan segera dan langkah yang sepadan diambil.

Redis melaksanakan algoritma baldi token

Saya telah melihat baldi token dilaksanakan oleh beberapa program sebelum ini bilangan token setiap unit masa Y, atau lakukan proses ini dengan kerap dalam Pemasa. Saya tidak begitu berpuas hati dengan kaedah ini. Terdapat dua sebab Satu adalah pembaziran sumber benang, dan satu lagi adalah masa pelaksanaan yang tidak tepat kerana isu penjadualan. [Cadangan berkaitan: Tutorial Video Redis]

Kaedah untuk menentukan bilangan token dalam baldi token adalah melalui pengiraan Pertama, kira berapa lama masa yang telah berlalu dari permintaan terakhir hingga ini permintaan. Untuk masa yang lama, sama ada ambang masa untuk mengeluarkan token telah dicapai, kemudian berapa banyak token ditambah, dan berapa banyak token ini boleh dimasukkan ke dalam baldi.

Ceramah itu murah!

Mari kita lihat cara ia dilaksanakan dalam Redis Kerana ia melibatkan pelbagai interaksi dengan Redis, di sini kami berada di sini untuk meningkatkan daya pemprosesan pemprosesan pengehad semasa dan mengurangkan program dan Bilangan interaksi Redis menggunakan skrip Lua yang disokong oleh Redis Pelaksanaan skrip Lua adalah atom, jadi tidak perlu risau tentang data kotor.

Kod ini dipetik daripada FireflySoft.RateLimit Ia bukan sahaja menyokong penggunaan hamba tuan biasa bagi Redis, tetapi juga menyokong Redis berkelompok, jadi daya tampung boleh dipertingkatkan melalui pengembangan mendatar. Untuk kemudahan membaca, beberapa komen ditambah di sini, tetapi sebenarnya tiada.

-- 定义返回值，是个数组，包含：是否触发限流（1限流 0通过）、当前桶中的令牌数
local ret={}
ret[1]=0
-- Redis集群分片Key，KEYS[1]是限流目标
local cl_key = '{' .. KEYS[1] .. '}'

-- 获取限流惩罚的当前设置，触发限流惩罚时会写一个有过期时间的KV
-- 如果存在限流惩罚，则返回结果[1,-1]
local lock_key=cl_key .. '-lock'
local lock_val=redis.call('get',lock_key)
if lock_val == '1' then
    ret[1]=1
    ret[2]=-1
    return ret;
end

-- 这里省略部分代码

-- 获取[上次向桶中投放令牌的时间]，如果没有设置过这个投放时间，则令牌桶也不存在，此时：
-- 一种情况是：首次执行，此时定义令牌桶就是满的。
-- 另一种情况是：较长时间没有执行过限流处理，导致承载这个时间的KV被释放了，
-- 这个过期时间会超过自然投放令牌到桶中直到桶满的时间，所以令牌桶也应该是满的。
local last_time=redis.call('get',st_key)
if(last_time==false)
then
 -- 本次执行后剩余令牌数量：桶的容量- 本次执行消耗的令牌数量
    bucket_amount = capacity - amount;
    -- 将这个令牌数量更新到令牌桶中，同时这里有个过期时间，如果长时间不执行这个程序，令牌桶KV会被回收
    redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time)
    -- 设置[上次向桶中放入令牌的时间]，后边计算应放入桶中的令牌数量时会用到
    redis.call('set',st_key,start_time,'PX',key_expire_time)
    -- 返回值[当前桶中的令牌数]
    ret[2]=bucket_amount
    -- 无需其它处理
    return ret
end

-- 令牌桶存在，获取令牌桶中的当前令牌数
local current_value = redis.call('get',KEYS[1])
current_value = tonumber(current_value)

-- 判断是不是该放入新令牌到桶中了：当前时间-上次投放的时间 >= 投放的时间间隔
last_time=tonumber(last_time)
local last_time_changed=0
local past_time=current_time-last_time
if(past_time<inflow_unit)
then
 -- 不到投放的时候，直接从令牌桶中取走令牌
    bucket_amount=current_value-amount
else
 -- 需要放入一些令牌, 预计投放数量 = (距上次投放过去的时间/投放的时间间隔)*每单位时间投放的数量
    local past_inflow_unit_quantity = past_time/inflow_unit
    past_inflow_unit_quantity=math.floor(past_inflow_unit_quantity)
    last_time=last_time+past_inflow_unit_quantity*inflow_unit
    last_time_changed=1
    local past_inflow_quantity=past_inflow_unit_quantity*inflow_quantity_per_unit
    bucket_amount=current_value+past_inflow_quantity-amount
end

-- 这里省略部分代码

ret[2]=bucket_amount

-- 如果桶中剩余数量小于0，则看看是否需要限流惩罚，如果需要则写入一个惩罚KV，过期时间为惩罚的秒数
if(bucket_amount<0)
then
    if lock_seconds>0 then
        redis.call(&#39;set&#39;,lock_key,&#39;1&#39;,&#39;EX&#39;,lock_seconds,&#39;NX&#39;)
    end
    ret[1]=1
    return ret
end

-- 来到这里，代表可以成功扣减令牌，则需要更新令牌桶KV
if last_time_changed==1 then
    redis.call(&#39;set&#39;,KEYS[1],bucket_amount,&#39;PX&#39;,key_expire_time)
 -- 有新投放，更新[上次投放时间]为本次投放时间
    redis.call(&#39;set&#39;,st_key,last_time,&#39;PX&#39;,key_expire_time)
else
    redis.call(&#39;set&#39;,KEYS[1],bucket_amount,&#39;PX&#39;,key_expire_time)
end
return ret

Daripada kod di atas, dapat dilihat bahawa proses pemprosesan utama ialah:

1. Tentukan sama ada terdapat penalti had semasa, kembalikan terus , pergi ke langkah seterusnya.

2. Tentukan sama ada baldi token itu wujud, buat baldi token dahulu, kemudian tolak token dan kembalikan, pergi ke langkah seterusnya.

3. Tentukan sama ada token perlu dikeluarkan, jika tidak, token akan ditolak secara langsung.

4. Tentukan bilangan token selepas potongan Jika kurang daripada 0, kembali ke had semasa, dan tetapkan penalti had semasa jika lebih besar daripada atau sama dengan 0, pergi ke yang seterusnya langkah.

5. Kemas kini bilangan token dalam baldi kepada Redis.

Anda boleh menyerahkan dan menjalankan skrip Lua ini dalam perpustakaan Redis bagi mana-mana bahasa pembangunan Jika anda menggunakan platform .NET, anda boleh merujuk artikel ini: Kadar baldi token Penggunaan Teras ASP.NET had (https://blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/).

Mengenai FireflySoft.RateLimit

FireflySoft.RateLimit ialah perpustakaan kelas mengehadkan semasa berdasarkan .NET Standard terasnya ringkas dan ringan serta boleh fleksibel menghadapi pelbagai senario menghadkan semasa Permintaan.

Ciri utamanya termasuk:

• Algoritma pengehadan berbilang semasa: empat algoritma terbina dalam: tetingkap tetap, tetingkap gelongsor, baldi bocor dan baldi token, yang juga boleh disesuaikan dan dikembangkan.
• Storan berbilang kiraan: pada masa ini menyokong dua kaedah storan: memori dan Redis.
• Mesra teragih: menyokong pengiraan bersatu program yang diedarkan melalui storan Redis.
• Sasaran pengehad semasa yang fleksibel: Pelbagai data boleh diekstrak daripada permintaan untuk menetapkan sasaran pengehad semasa.
• Sokong penalti mengehadkan semasa: anda boleh mengunci klien untuk tempoh masa selepas mencetuskan pengehadan semasa dan tidak membenarkan akses.
• Perubahan peraturan dinamik: Menyokong peraturan pengehad semasa yang berubah secara dinamik semasa program sedang berjalan.
• Ralat tersuai: Anda boleh menyesuaikan kod ralat dan mesej ralat selepas mencetuskan had semasa.
• Kesesuaian universal: Pada dasarnya, ia boleh memenuhi sebarang senario yang memerlukan pengehadan semasa.

Alamat sumber terbuka Github: https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md

Artikel ini diterbitkan semula daripada: https://juejin.cn/post/7039105263168651301

Pengarang: Yinghuo Architecture

Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Video pengaturcaraan ! !

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma baldi token menggunakan Redis? (dengan kod). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!