分布式 令牌桶算法 总结
前言
相关系列
- 《分布式 & 目录》
- 《分布式 & 令牌桶算法 & 总结》
- 《分布式 & 令牌桶算法 & 问题》
参考文献
- 《【算法】令牌桶算法》
概述
简介
TBA @ Token Bucket Algorithm @ 令牌桶算法是一种流行于网络通信领域的流量控制/频率限制算法。令牌桶算法的核心原理是通过一个概念上的“桶”来控制请求的访问频率，这个桶中会保存一定数量的“令牌”，每个请求只有获得令牌后才能正式访问系统，否则就只能等待/放弃。而由于桶中的令牌会以固定的频率生成，因此令牌桶算法就可以达到持续控制请求访问数量&频率的效果。此外由于桶可以按配置预存一定数量的令牌，因此在日常请求访问频率 < 令牌产生频率的情况下，令牌桶算法还可以支持一定程度流量高/突发，这是另一种限流算法“漏桶”所不具备的能力。
场景
- 限制网络带宽：控制访问流量；
- 限制API频率：限制API调用频率；
- 功能分级：为不同级别的用户提供不同频率的服务；
- 任务调度：限制任务执行频率以避免资源争用。
原理
概念
- 令牌桶：用于存放指定数量令牌的虚拟容器，通常使用Redis一类的中间件实现；
- 令牌填充频率：系统向令牌桶中生成/置入令牌的频率，一般是系统平均QPS/s；
- 令牌消耗：每当请求到达时从桶中移除一个令牌以支持其访问系统。如果桶中没有令牌，那么请求将被延迟/丢弃。
流程
- 系统持续以指定频率产生指定数量的令牌至于令牌桶中，如果令牌桶已满则丢弃；
- 客户端访问系统，在网关被拦截。随后网关会判断当前请求是否免限流，是则直接访问；
- 如果当前请求不免限流，则网关会从尝试从令牌桶中获取令牌。如果令牌不存在则拒绝请求；否则允许请求按预期目的访问系统。