令牌桶(Token Bucket)

Python012

令牌桶(Token Bucket),第1张

想象有一个木桶,系统按照固定速率,例如10ms每次,往桶里加入Token,如果桶已经满了就不再添加。新请求来临时,会各自拿走一个Token,如果没有Token 就拒绝服务。这里如果一段时间没有请求时,桶内就会积累一些token,下次一旦有突发流量,只要token足够,也能一次处理。

总结下令牌算法的特点,令牌桶即可以控制进入系统的请求请求量,同时允许突发流量。

在秒杀活动中,用户的请求速率是不固定的,这里我们假定为10r/s,令牌按照5个每秒的速率放入令牌桶,桶中最多存放20个令牌,那系统就只会允许持续的每秒处理5 个请求,或者每隔4 秒,等桶中20 个令牌攒满后,一次处理20个请求的突发情况,保证系统稳定性。

go简易版实现

如果要讲究开箱机即用,用这个开源组件去做http限速你只要按着demo稍微配置下。

令牌桶这个算法

精简版:一个gorontinue定时往里面塞,所有的请求想要被响应必须先去channel取token,没取到的丢弃。

但感觉golang.org/x/time/rate 实现方式巧。它是直接通过计算的一个计算算法表达出token的过程。

着重点是去限制你的服务器并发处理请求的能力。打比方你的服务器最多同时处理1万个请求,它的出现就是同时处理1万个请求,请求处理完毕资源就会被释放,就可以让新的流量进入。

golang版本实现限速参考

算法介绍

tollbooth 一个开箱即用的限速项目

uber漏铜

限速

上篇文章提到固定时间窗口限流无法处理突然请求洪峰情况,本文讲述的令牌桶线路算法则可以比较好的处理此场景。

可以有效处理瞬间的突发流量,桶内存量 token 即可作为流量缓冲区平滑处理突发流量。

实现较为复杂

core/limit/tokenlimit.go

分布式环境下考虑使用 redis 作为桶和令牌的存储容器,采用 lua 脚本实现整个算法流程。

兜底策略的设计考虑得非常细节