速率限制的一些思考

无论是在我们日常的软件使用中还是软件开发中,我们总是会遇到速率限制的问题,例如短信验证码限制一小时最多只能发送5次,这是日常生活的情况;在工作中,我们可能会限制说 DB 的操作不能超过 100 qps,这也是一种限制操作,那么对于这些限制速率的行为,有没有什么好一点的实践或者理论,最近我就看了一些,但是理解可能并不是很深刻,但不妨写出来和大家交流一番。

常用的限流策略

在看了不少的实践文章之后,我发现有主要讲得都是两种方法,而且都是从网络限流中迁移过来的,分别是:Leaky bucketToken bucket,这两种方法可能乍看之下差不多,而且有不少文章并没有明确得指出他们的区别,所以很容易混淆误导;但这不是唯一的原因,还有个原因就是在某些条件下,他们其实达到的效果和实现都是一致的,所以不免让人混淆。

下面我就以我个人的理解分别介绍讲解一下这两种策略,同时,针对 Token bucket 我将会使用 Python 编程语言写一个简单的实现,方便大家有一个更清晰的认识。

Leaky bucket

Leaky bucket 最初也是用在网络方面,用于计算机网络和通信网络中包交换的速率限制,后面也就迁移到其他领域了。Leaky bucket 的理论有两种,分别称为基于 meter 的和 基于 queue 的,他们实现的具体思路不同,而且当你真正实现的时候,会发现有很大的区别,下面我也分别介绍这两种。

基于 meter 的 Leaky bucket

这种基于 meterLeaky bucket 相对来说比较简单,其实它就有一个计数器,然后有消息要发送的时候,就看计数器够不够,如果计数器没有满的话,那么这个消息就可以被处理,如果计数器不足以发送消息的话,那么这个消息将会被丢弃。

那么这个计数器是怎么来的呢,基于 meter 的形式的计数器就是发送的频率,例如你设置得频率是不超过 5条/s ,那么计数器就是 5,在一秒内你每发送一条消息就减少一个,当你发第 6 条的时候计时器就不够了,那么这条消息就被丢弃了。

从这里可以看出基于 meterLeaky bucket 的特点就是肯定不超过指定速率,而且可以一定程度保持原始消息的发送信息,但是不能很好得应对突发的短期流量。

基于 queue 的 Leaky bucket

另外一种基于 queueLeaky bucket 实现起来比较复杂,但是原理却比较简单,和 meter 差不多,也是存在一个 counter,这个 counter 却不表示速率限制,而是表示 bucket 的大小,这里就是当有消息要发送的时候看 bucket 中是否还有位置,如果有,那么就将消息放进 queue 中,注意,这里就是不一样的地方,这里只是将消息放进 Leaky bucket 维护的一个 queue 的,这个 queue 以 FIFO 的形式提供服务;如果 bucket 没有位置了,那么同样得,消息将被抛弃。

在消息被放进 queue 之后,Leaky bucket 还维护了一个定时器,这个定时器的周期就是我们设置的频率周期,例如我们设置得频率是 5条/s,那么定时器的周期就是 200ms,定时器每 200ms 去 queue 里获取一次消息,如果有消息,那么就发送出去,如果没有,那么轮空了。

从上面的描述中,可以看出,对于 基于 queueLeaky bucket 来说,它可以保证的是任务之间的执行间隔严格按照我们设置得频率,不会超频,但是也正是因为如此,完全失去了任务进来的相关信息,而且对于突发流量也完全无法应对,无论流量多或少,都是固定的频率。

Token bucket

Token bucket,我们中文习惯性称之为 令牌桶,它的特点就是有一个 bucket,然后在 bucket 中存放了一定数额的 token,每当你要发送消息的时候,需要从 bucket 中获取一个 token,只要获取成功,那么你就可以发送,否则,那么将被放弃。

既然 token 会被消耗,那么肯定有补充的方式,是的,Token bucket 的 token 补充方式就是以设定的频率往bucket 里放置 token,而 bucket 是有大小的,如果要放置 token 的时候 bucket 满了,那么 token 将被抛弃,否则 bucket 中的 token 数量增加。

这里就是问题的有趣之处,和基于 queue 的 Leaky bucket 的一点区别就在于 bucket 是有容量的,也就是说假设我们设置的频率是 5条/s,但是我将 bucket 的 size 设置为 10,那么也就是说当 bucket 被放满的时候,同一时间我可以提供的 token 数量是 10 个,这意味着我可以临时支持 10条/s 的速率,这就是 token bucket 比较有意思的一点。

Token bucket 可以也能在一定程度上保持流量的来源特征,同时也支持一定的突发流量,但是,从另外一方面也可能导致超频,当然这依赖于你的选择,可以不要。

一个 Python 实现

根据上面的 Token bucket 的描述,我就以 Python 编程语言为例,给出一个

这个例子比较简单, Token bucket 有两个因子,分别是:频率bucket大小,这里我们就将他们定义为 fill_ratetokens,然后当我们需要发送消息的时候,就调用 consume 申请指定数量的 token,如果我们发现 token 是够的,那么 ok 没问题,不够的话就没办法了。

这里的判断 token 数量的逻辑还是不错的,值得同学们稍作思考一番。下面是一个使用的例子:

总结

最后,总结一下两种不同的方式的不同点和优缺点:

Leaky bucket 的优点就是可以保证速率肯定不超过我们设定的速率,最多也就相等;同时,实现可以很简单(meter),也可以很复杂(queue),不过更多情况下我们是认为它不能保持原始流量的特征的。在流量方面, Leaky bucket 不能应对突发流量,但是,反过来想,这个可以用来防御恶意流量,不过这个 bucket 的大小选择是个难题。

Token bucket 的一个比较大的优点就是可以应对突发流量,同时如果我们希望也可以转化为 meter leaky bucket,但是缺点也是比较明显,就是可能会产生突发性的流量,例如一个小时的流量都在第一秒耗完了,当然,这有个比较麻烦得解决方案:滑动窗口,这里没有提到。

Reference

  1. Leaky bucket
  2. Token bucket
  3. 接口限流

· EOF ·

作者: 行者酱油君
个人主页: 利强的博客
微信公众账号:后台架构
扫描左边二维码(或者长按识别二维码)关注 后台架构
本文版权归作者所有,未经作者同意不得转载,本人保留一切权利。
最近爬虫很是凶猛,标注下文章的原文地址: https://liuliqiang.info/post/tips-about-rate-limit/