API Rate Limiting 限速

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

真诚赞赏,手留余香
赞赏
随机推荐
Nodejs进阶:MD5入门介绍及crypto模块的应用
Node.js 爬虫常见问题
MySQL汉字转换为拼音
DDOS 专题
PM2 生态系统文件 ecosystem.config.js
Webpack 概念理解 module、chunk 和 bundle 的区别
Android Studio 导出APK
关于字符的一些基础知识
解读浮动闭合最佳方案:clearfix
apiDoc 参考