常见高并发限流算法一：令牌桶算法

前提

• 在大量并发的环境下，为了防止由于请求暴涨，导致系统崩溃从而引起雪崩，一般会对流量做一定的限制操作。比如等待、排队、降级、拒绝服务、限流等。

说明

• 令牌桶算法是网络流量整形和速率限制中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目,能够应对突发数据的发送。
• 令牌桶可以想象成一个用来装门牌的容器(桶)，要想通过必须拿到门牌。

算法的基本过程

• 假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中
• 假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃
• 当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络
• 如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外
• 算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理
• 它们可以被丢弃
• 它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输
• 它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃

图说明

截图来自网络