限流技术(time limiting)是网络Qos的功能,被用作控制网络接口收发通信数据的速率。可以用来优化性能,减少延迟和提高带宽等。现在在应用层也借鉴了这个概念,用来为服务控制请求的速率,

两种常用算法

令牌桶(Token Bucket)和漏桶(leaky bucket)是 最常用的两种限流的算法。

漏桶算法

漏桶算法思路很简单,水(数据或者请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。
leaky_bucket

因为出水速度是一定的,所以请求的处理速度不会超过出水速度。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,如果令牌桶已经满了,则丢弃令牌。而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务或者将请求放入到等待队列中。这样请求的处理速度将和放入令牌的速度一致,但是令牌桶算法对比漏桶算法的一个优点是它允许出现超过令牌放入速度的处理高峰,这个高峰和令牌桶的大小相关。

令牌桶算法

数学模型

设r为放入令牌速率(单位/s),M为系统可以最大处理请求速率(系统的吞吐量)(单位/s),b令牌桶大小,Tmax就是最大爆发时间
Tmax

爆发期间能处理的最大请求数为
burst_size

一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量, 比如华为的专利"采用令牌漏桶进行报文限流的方法"(CN 1536815 A),提供了一种动态计算可用令牌数的方法, 相比其它定时增加令牌的方法,它只在收到一个报文后,计算该报文与前一报文到来的时间间隔内向令牌漏桶内注入的令牌数,并计算判断桶内的令牌数是否满足传送该报文的要求。