rate limiting 之 token bucket

前言

在实现限速功能的时候,其中一种常用的方法是使用 token bucket 算法来实现。

token bucket

token bucket

(图片来自 https://gateoverflow.in/39720/gate2016-1-54

token bucket 常见的中文解释是:令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务 [1]

维基百科 [2] 上 token bucket 算法的简单描述如下:

  • A token is added to the bucket every 1/r seconds. 每隔 1/r 秒向 bucket 中增加一个 token。
  • The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded. 这个 bucket 最多只能存放 b 个 token。如果放置 token 时 bucket 已经满了,丢弃这个 token。
  • When a packet (network layer PDU) of n bytes arrives, 当一个包含 n 个字节的数据包进来的时候,
    • if at least n tokens are in the bucket, n tokens are removed from the bucket, and the packet is sent to the network. 如果 bucket 中有 >= n 个 token,将从 bucket 中移除 n 个 token,然后把这个数据包发送出去。
    • if fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant. 如果可用的 token < n,此时不会从 bucket 中移除任何的 token,但是这个数据包会被认为是被限制的数据包。

常见实现方法

一般有两种实现方法。

一种是按照 token bucket 的说明,真的做放 token 的操作:

  • 后台有个线程每 1/n 秒将 bucket 中的 token 数量加一,直至达到 bucket 容量。
  • 主线程检查限速时,比较 bucket 中 token 的数量,如果少于需要的数量,表示当前被限制。 (比如,一个请求进来,检查 bucket 中的 token 数量是否 > 1,如果 > 1请求放行同时把 token 数量减 1, 如果 < 1 说明当前请求已超出速率限制,请求被拒绝。)

这种方法有一个很大的缺点,那就是因为每个 token bucket 都会有一个繁忙的后台线程在更新 token 数量,会 导致严重占用系统 CPU 出现严重的性能问题。假设我们的限速是限制为 1000/s,此时后台每隔 1ms 就会更新一次 token 数量,可以想像每个后台线程都会频繁占用 CPU,用这种方法实现的 rate limiting 处理不了几个请求就会出现 CPU 接近 100% 的情况。所以实践中一般用另一种方法来实现 token bucket。

另一种是在取 token 时计算上次取跟这次取之间按照速率会产生多少个 token 加上上次剩余的 token ,然后比较剩余 token 数是否满足需要。

总结

本文简单介绍了一下 token bucket 算法以及两种常见的实现方法。


Comments

comments powered by Disqus