Redis를 사용하여 토큰 버킷 알고리즘을 구현하는 방법은 무엇입니까? (코드 포함)-Redis-php.cn

本篇文章给大家分享一下令牌桶算法原理，并介绍一下利用Redis实现令牌桶算法的方法，希望对大家有所帮助！

Redis를 사용하여 토큰 버킷 알고리즘을 구현하는 방법은 무엇입니까? (코드 포함)

在限流算法中有一种令牌桶算法，该算法可以应对短暂的突发流量，这对于现实环境中流量不怎么均匀的情况特别有用，不会频繁的触发限流，对调用方比较友好。

例如，当前限制10qps，大多数情况下不会超过此数量，但偶尔会达到30qps，然后很快就会恢复正常，假设这种突发流量不会对系统稳定性产生影响，我们可以在一定程度上允许这种瞬时突发流量，从而为用户带来更好的可用性体验。这就是使用令牌桶算法的地方。

令牌桶算法原理

如下图所示，该算法的基本原理是：有一个容量为X的令牌桶，每Y单位时间内将Z个令牌放入该桶。如果桶中的令牌数量超过X，那么它将被丢弃。处理请求时，需要先从令牌桶中取出令牌，如果拿到了令牌，则继续处理；如果拿不到令牌，则拒绝请求。

Redis를 사용하여 토큰 버킷 알고리즘을 구현하는 방법은 무엇입니까? (코드 포함)

可以看出，在令牌桶算法中设置X，Y和Z的数量尤为重要。Z应该比每Y单位时间内的请求数稍大，系统将长时间处于此状态；X是系统允许的瞬时最大请求数，并且系统不应该长时间处于此状态，否则就会频繁触发限流，此时表明流量出现了超预期的情况，需要及时调查原因并采取相应措施。

Redis实现令牌桶算法

之前看过有些程序实现的令牌桶，其向桶中放入令牌的方法是启动一个线程，每隔Y单位时间增加一次令牌数量，或者在Timer中定时执行这一过程。我不太满意这种方法，原因有二，一是浪费线程资源，二是因为调度的问题执行时间不精确。【相关推荐：Redis视频教程】

这里确定令牌桶中令牌数量的方法是通过计算得出，首先算出从上次请求到这次请求经过了多长时间，是否达到发令牌的时间阈值，然后增加的令牌数是多少，这些令牌能够放到桶中的是多少。

Talk is cheap!

下边就来看看Redis中怎么实现的，因为涉及到多次与Redis的交互，这里为了提高限流处理的吞吐量，减少程序与Redis的交互次数，采用了Redis支持的Lua script，Lua script的执行是原子的，所以也不用担心出现脏数据的问题。

代码节选自FireflySoft.RateLimit，它不仅支持普通主从部署Redis，还支持集群Redis，所以吞吐量可以通过水平扩展的方式进行提升。为了方便阅读，这里增加一些注释，实际是没有的。

-- 定义返回值，是个数组，包含：是否触发限流（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_time0 then redis.call('set',lock_key,'1','EX',lock_seconds,'NX') end ret[1]=1 return ret end -- 来到这里，代表可以成功扣减令牌，则需要更新令牌桶KV if last_time_changed==1 then redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time) -- 有新投放，更新[上次投放时间]为本次投放时间 redis.call('set',st_key,last_time,'PX',key_expire_time) else redis.call('set',KEYS[1],bucket_amount,'PX',key_expire_time) end return ret

로그인 후 복사

通过以上代码，可以看出，其主要处理过程是：

1、判断有没有被限流惩罚，有则直接返回，无则进入下一步。

2、判断令牌桶是否存在，不存在则先创建令牌桶，然后扣减令牌返回，存在则进入下一步。

3、判断是否需要投放令牌，不需要则直接扣减令牌，需要则先投放令牌再扣减令牌。

4、判断扣减后的令牌数，如果小于0则返回限流，同时设置限流惩罚，如果大于等于0则进入下一步。

5、更新桶中的令牌数到Redis。

你可以在任何一种开发语言的Redis库中提交并运行这段Lua script脚本，如果你使用的是.NET平台，可以参考这篇文章：ASP.NET Core中使用令牌桶限流（https://blog.bossma.cn/dotnet/asp-net-core-token-bucket-algorithm-of-rate-limit/）。

关于FireflySoft.RateLimit

FireflySoft.RateLimit 是一个基于 .NET Standard 的限流类库，其内核简单轻巧，能够灵活应对各种需求的限流场景。

其主要特点包括：

다중 전류 제한 알고리즘: 고정 창, 슬라이딩 창, 누출 버킷, 토큰 버킷의 4가지 알고리즘이 내장되어 있으며 사용자 정의 및 확장도 가능합니다.
다중 카운트 저장소: 현재 메모리와 Redis라는 두 가지 저장소 방법을 지원합니다.
분산 친화적: Redis 저장소를 통해 분산 프로그램의 통합 계산을 지원합니다.
유연한 전류 제한 목표: 전류 제한 목표를 설정하기 위한 요청에서 다양한 데이터를 추출할 수 있습니다.
현재 제한 페널티 지원: 전류 제한을 실행한 후 일정 시간 동안 클라이언트를 잠그고 액세스를 허용하지 않을 수 있습니다.
규칙의 동적 변경: 프로그램이 실행되는 동안 현재 제한 규칙을 동적으로 변경하는 것을 지원합니다.
사용자 정의된 오류: 현재 제한을 트리거한 후 오류 코드와 오류 메시지를 사용자 정의할 수 있습니다.
범용 적용성: 원칙적으로 전류 제한이 필요한 모든 시나리오를 충족할 수 있습니다.