Comment implémenter l'algorithme du token bucket à l'aide de Redis ? (avec code)

Cet article partagera avec vous le principe de l'algorithme du bucket de jetons et présentera la méthode d'utilisation de Redis pour implémenter l'algorithme du bucket de jetons. J'espère qu'il sera utile à tout le monde !

Il existe un algorithme de compartiment de jetons parmi les algorithmes de limitation actuels. Cet algorithme peut gérer de courtes rafales de trafic. Ceci est particulièrement utile pour les situations où le trafic n'est pas très uniforme dans des environnements réels. fréquemment. L’appelant est relativement amical.

Par exemple, la limite actuelle est de 10qps, la plupart du temps elle ne dépassera pas ce montant, mais occasionnellement elle atteindra 30qps, puis elle reviendra bientôt à la normale en supposant que cette explosion de trafic n'ait pas d'impact sur. stabilité du système, nous pouvons Ce type de trafic en rafale instantanée est autorisé dans une certaine mesure, offrant ainsi aux utilisateurs une meilleure expérience d'utilisation. C’est là qu’intervient l’algorithme du token bucket.

Principe de l'algorithme de seau de jetons

Comme le montre la figure ci-dessous, le principe de base de l'algorithme est le suivant : il existe un seau de jetons d'une capacité de X, et les jetons Z sont placés dans le seau chaque unité de temps Y. Si le nombre de jetons dans le compartiment dépasse X, il sera supprimé. Lors du traitement d'une demande, vous devez d'abord supprimer le jeton du compartiment de jetons. Si vous obtenez le jeton, poursuivez le traitement. Si vous ne parvenez pas à obtenir le jeton, rejetez la demande.

On peut voir que la définition du nombre de X, Y et Z est particulièrement importante dans l'algorithme du token bucket. Z doit être légèrement supérieur au nombre de requêtes par unité de temps Y, et le système restera dans cet état pendant une longue période. Cela indique que le trafic a dépassé les attentes et que la cause doit être étudiée rapidement et que les mesures correspondantes doivent être prises.

Redis implémente l'algorithme du compartiment à jetons

J'ai déjà vu des compartiments à jetons implémentés par certains programmes. La méthode pour mettre des jetons dans le compartiment consiste à démarrer un thread et à augmenter le nombre de jetons chaque fois qu'une unité Y, ou à exécuter ceci. traiter régulièrement dans Timer. Je ne suis pas très satisfait de cette méthode. Il y a deux raisons. L'une est un gaspillage de ressources de thread et l'autre est le temps d'exécution inexact en raison de problèmes de planification. [Recommandations associées : Tutoriel vidéo Redis]

La méthode pour déterminer le nombre de jetons dans le compartiment de jetons ici consiste à calculer. Tout d'abord, calculez combien de temps s'est écoulé depuis la dernière requête pour cette requête et si cela est suffisant. pour émettre des jetons, puis combien de jetons sont ajoutés et combien de ces jetons peuvent être mis dans le compartiment.

Parler ne coûte pas cher !

Jetons un coup d'œil à la façon dont il est implémenté dans Redis Parce qu'il implique plusieurs interactions avec Redis, afin d'améliorer le débit du traitement de limitation de courant et de réduire le nombre d'interactions entre le programme et Redis, Redis est utilisé Script Lua pris en charge, l'exécution du script Lua est atomique, il n'y a donc pas lieu de s'inquiéter des données sales.

Le code est extrait de FireflySoft.RateLimit, qui prend non seulement en charge le déploiement maître-esclave ordinaire de Redis, mais prend également en charge Redis en cluster, de sorte que le débit peut être amélioré grâce à une expansion horizontale. Pour faciliter la lecture, quelques commentaires sont ajoutés ici, mais il n'y en a en réalité aucun.

-- 定义返回值，是个数组，包含：是否触发限流（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

Grâce au code ci-dessus, on peut voir que le processus de traitement principal est :

1. Déterminez s'il existe une pénalité de limite actuelle. Si c'est le cas, revenez directement. Sinon, passez à l'étape suivante.

2. Déterminez si le compartiment de jetons existe. S'il n'existe pas, créez d'abord le compartiment de jetons, puis déduisez le jeton et renvoyez-le s'il existe, passez à l'étape suivante.

3. Déterminez si les jetons doivent être libérés. Sinon, les jetons seront déduits directement si nécessaire, les jetons seront d'abord libérés, puis les jetons seront déduits.

4. Déterminez le nombre de jetons après déduction. S'il est inférieur à 0, revenez à la limite actuelle et définissez la pénalité de limite actuelle. S'il est supérieur ou égal à 0, passez à l'étape suivante.

5. Mettez à jour le nombre de jetons dans le bucket vers Redis.

Vous pouvez soumettre et exécuter ce script Lua dans la bibliothèque Redis de n'importe quel langage de développement. Si vous utilisez la plateforme .NET, vous pouvez vous référer à cet article : Utilisation de la limitation actuelle du bucket de jetons dans ASP.NET Core (https :/ /blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/) .

À propos de FireflySoft.RateLimit

FireflySoft.RateLimit est une bibliothèque de classes de limitation actuelle basée sur la norme .NET. Son noyau est simple et léger, et peut répondre de manière flexible aux divers besoins des scénarios de limitation actuels.

Les principales fonctionnalités incluent :

• Plusieurs algorithmes de limitation de courant : quatre algorithmes intégrés : fenêtre fixe, fenêtre coulissante, compartiment à fuite et compartiment à jetons, qui peuvent également être personnalisés et étendus.
• Stockage à plusieurs comptes : prend actuellement en charge deux méthodes de stockage : mémoire et Redis.
• Adapté à la distribution : prend en charge le comptage unifié des programmes distribués via le stockage Redis.
• Cible de limitation de courant flexible : diverses données peuvent être extraites de la demande pour définir l'objectif de limitation de courant.
• Prend en charge la pénalité de limitation de courant : il peut être verrouillé pendant un certain temps après que le client a déclenché la limitation de courant et n'autorise pas l'accès.
• Changement dynamique des règles : prend en charge la modification dynamique des règles de limitation de courant pendant l'exécution du programme.
• Erreur personnalisée : vous pouvez personnaliser le code d'erreur et le message d'erreur après avoir déclenché la limite actuelle.
• Applicabilité universelle : en principe, il peut répondre à tout scénario nécessitant une limitation de courant.

Adresse open source Github : https://github.com/bosima/FireflySoft.RateLimit/blob/master/README.zh-CN.md

Cet article est reproduit à partir de : https://juejin. cn/post /7039105263168651301

Auteur : Yinghuo Architecture

Pour plus de connaissances liées à la programmation, veuillez visiter : Vidéo de programmation ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!