admin
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
