漏桶算法和令牌桶算法
-
- 漏桶算法
- 令牌桶算法
项目中用到了限流机制，在面试的时候也被面试官问到了，在此做个记录。高并发场景下常用的限流算法有两种，一种是漏桶算法，一种是令牌桶算法。
参考文档：https://www.cnblogs.com/aspirant/p/9093437.html
漏桶算法
漏桶算法思路
水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。
漏桶算法缺点
在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以即使网络中不存在拥塞，漏桶算法也不能使某一个突发的流量通过。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。
令牌桶算法
对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
令牌桶算法的基本过程
- 假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中
- 假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃
- 当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络
- 如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外
对于流量限制外的数据包的处理方式：
- 被丢弃
- 排放在队列中以便当令牌桶中累积了足够多的令牌时再传输
- 继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃