限流的算法

Posted by A Chang on March 16, 2020

限流的算法

常见的限流算法有令牌同、漏桶,还有一种计数器。

令牌桶

令牌算法的过程如下:
假如用户配置的平均发送速率为r,则每隔1/r秒一个令牌被加入到桶中。
假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了,那么这个令牌会被丢弃;
当一个n个字节的数据包到达时,就从令牌桶中删除n个令牌,并且数据包被发送到网络;
如果令牌桶中少于n个令牌,那么不会删除令牌,并且认为这个数据包在流量限制之外,要不丢弃要不缓冲区等待。

漏桶

一直觉得应该叫漏斗啊。
一个固定容量的漏桶,按照固定速率流出漏桶,
可以以任意速度流入水桶。
如果流入的水超过桶的容量,则水就溢出,被丢弃。

令牌桶和漏桶的比较

令牌桶是按照固定速率往桶中添加令牌,请求是否处理主要看同种是否有令牌,流入不限制,可以一次拿多个令牌,只要桶中有令牌,则处理请求;如果没有令牌,则拒绝请求。
漏桶则是流入请求不限制,按照固定速率流出请求,如果流入的请求的速度小于等于流出的请求,桶为空桶,则处理请求;如果流入的请求的速度大于流出的请求,累积请求留在同种,但是桶未满,则处理请求;如果累积请求大于桶容量时,则拒绝请求。
两个算法实现一样,方向相反,令牌是匀速流入,流通是匀速流出。

计数器

计数器比较简单,没有什么算法和描述。满足一定的条件的流量计数加1,达到阀值了限制,顾名思义叫计数限流。