1，令牌桶算法(Token Bucket)

令牌桶算法(Token Bucket) 随着时间流逝，系统会按恒定1/QPS时间间隔(如果QPS=100，则间隔是10ms)往桶里加入Token，如果桶已经满了就不再加了。新请求来临时，会各自拿走一个Token，如果没有Token可拿了就阻塞或者拒绝服务。

令牌桶的另外一个好处是可以方便的改变速度。 一旦需要提高速率，则按需提高放入桶中的令牌的速率。 一般会定时(比如100毫秒)往桶中增加一定数量的令牌， 有些变种算法则实时的计算应该增加的令牌的数量。

2，算法实现

对于每个 Bucket 设置一个定时器，而一个定时器就是一条线程。那么在你的服务器上，光是分配给定时器的线程就需要和你的用户数量是一个量级的， 几万几十万条线程在服务器上运行，是完全是脱离了实际情况的。 所以最合适的方案是使用时间戳。

1. 当一个请求执行后，先获取缓存中的 Token Bucket 的 key；

2. 如果这个 Token Bucket 在缓存中不存在，那么就新建一个 Token Bucket，然后设置该 Bucket 的 Token 数量为最大值减一(去掉了这次请求获取的 Token）。

3. 如果这个 Token Bucket 在缓存中存在，而且其上一次加入 Token 的时间到现在时间的时间间隔，大于 Token Bucket 的 interval，那么也将 Bucket 的 Token 值重置为最大值减一；

4. 如果 Token Bucket 上次加入 Token 的时间到现在时间的时间间隔，没有大于 interval，那么就计算这次需要补充的 Token 数量，将补充过后的 Token 数量更新到 Token Bucket 中。 

为了增加读取速度，可以使用 Redis 作为缓存。

3，伪代码实现

$max_tokens  = 5; // 最大的访问量
$interval   = 10; // 间隔时间，单位秒

$user_mark = '127.0.0.1';       // 用户标记
$api_mark  = 'index/Test/text';    // API 标记
$cache_mark = $user_mark.'|'.$api_mark; // 缓存标记

$store_tokens = Cache::get($cache_mark);

if($store_tokens === false){
  // 如果 Token Bucket 不存在，创建一个
  $store_tokens = --$max_tokens;
  Cache::set( $cache_mark, $store_tokens, $interval);
} elseif($store_tokens > 0){
  // 如果 Token Bucket > 0，自减
  Cache::dec($cache_mark);
  $store_tokens = Cache::get($cache_mark);
}

return $store_tokens;

4，处理超过限速的请求

github是这样处理超过限速请求的，返回如下信息：

HTTP/1.1 403 Forbidden
Date: Tue, 20 Aug 2013 14:50:41 GMT
Status: 403 Forbidden
X-RateLimit-Limit: 60
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1377013266
{
  "message": "API rate limit exceeded for xxx.xxx.xxx.xxx. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)",
  "documentation_url": "https://developer.github.com/v3/#rate-limiting"
}

5，注意web server 防DDOS 工具的rate limiting

比如我使用的Apache mod_evasive模块，它也有类似令牌桶算法的功能。api的 rate limiting 应该小于 apache mod_evasive的rate limiting。

LoadModule evasive2_module modules/mod_evasive2.so

DOSDisplayToken   On
DOSHashTableSize  3097
DOSSiteCount    100
DOSSiteInterval   1
DOSPageCount    6
DOSPageInterval   1
DOSBlockingPeriod  30
DOSLogDir      "${SRVROOT}/logs/mod_evasive"

参考：

https://javascript.net.cn/article?id=443

https://developer.github.com/v3/#rate-limiting

https://www.cnblogs.com/exceptioneye/p/4783904.html

https://www.jianshu.com/p/2a223024b8de