token_bucket令牌桶算法原理
讲在原理之前
我们今天主要是分析令牌桶算法，分析之前我们先介绍一下使用该算法的背景。
限流
每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.
通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.
令牌桶算法
算法简介
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
算法原理
- 令牌将按照固定的速率被放入令牌桶中。比如每秒放10个。
- 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。
- 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。
- 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。
如下示意图：
通俗的理解，令牌桶是一个水桶，而令牌是通过一根水管流到水桶中的水。
令牌桶的填满时间，是由桶的自身容量、令牌漏出速率（桶下面的水管）、超过平均速率的突发流量持续的时间三个方面共同决定的。如果突发流量的时间比较短，令牌桶不会溢出，在通信流上不会受到影响，如果突发流量比较大，时间比较长，那令牌桶就会溢出，多余的通信流就会被限制。
令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176947.html原文链接：https://javaforall.net
