近来在看开涛的《亿级流量》这本书,看到了限流这个章节,因为自己平时项目中也经常用到类似的场景,索性系统的整理学习一番,把这块的相关技术理解透彻。

限流概述

限流即流量限制,也叫做流量整形。限流的目的是在遇到流量高峰期或者流量突增(流量尖刺)时,通过对流量速率进行限制,当达到限制速率时,可以拒绝服务(定向到错误页或告知资源没有了)、排队或等待(比如秒杀、评论、下单)、降级(返回兜底数据或默认数据,如商品详情页库存默认有货)。以把流量控制在系统所能接受的合理范围之内,不至于让系统被高流量击垮。

常用的限流算法有哪些

在开发高并发的系统时,我们常用的限流算法有 漏桶算法、令牌桶算法、还有通过计数器来实现。下面对这几种方式分别说明一下

漏桶算法

以前化学实验课的时候,我们都见过漏斗,当我们向漏斗里面倒水的时候,漏斗里的水就会通过下面的孔流出去,如果你倒水的速度过快,便会导致漏斗中的水直接溢了出来。漏桶算法的原理与之类似,我们把用户的请求比做上面的水。就可以理解漏桶算法是如何实现限流的了

clipboard.png

因为流水孔的大小是固定的,所以漏桶是按照常量固定的速率流出请求,而流入请求(倒水)的速率随意,如果流入的请求超过漏桶容量时,那么再流入请求便会被丢弃(溢出)

也就是说,假设我们在压测的时候发现我们的系统处理峰值是1000 RPS,超过这个峰值就会出现错误的响应,所以我们在代理层 nginx 限制最大请求也为1000 RPS,(设置流水孔的大小)如果用户每秒的请求数超过1000,nginx (漏桶的容量)就会暂时储存这些多出的请求,排着队等待处理。但是如果请求量太大,nginx没法暂存的了这么多请求,那么多余的请求就会被拒掉,并返回503状态码,告知服务器不可用。(可以参考 nginx配置实现漏桶算法限流)

漏桶算法实现的伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long timeStamp=getNowTime();
int capacity; // 桶的容量
int rate ; // 水漏出的速度
int water; // 当前水量

bool grant() {
//先执行漏水,因为rate是固定的,所以可以认为“时间间隔*rate”即为漏出的水量
long now = getNowTime();
water = max(0, water- (now - timeStamp)*rate);
timeStamp = now;

if water < capacity { // 水还未满,加水
water ++;
return true;
} else {
return false;//水满,拒绝加水
}
}

令牌桶算法

令牌桶其实也很好理解,它其实就是以一个固定的速率往一个固定容量的桶里添加令牌,如果添加的令牌数已经超过桶的容量的话,那么多余的令牌就会被丢弃。当一个请求来临时,就会向桶里要一个令牌,只要拿到令牌,请求就会被处理,正因为这样,令牌桶是可以允许突发请求的。如果令牌桶里的令牌都没有了,那么再有请求进来就会被拒绝处理。

clipboard.png

假设每秒会有 100 个令牌放入桶中,而我们令牌桶中最多可以存放 1000 个令牌,如果桶满了,新放入的令牌会被丢弃,当有 100 个请求到达时,则会一下消耗 100 个令牌,然后这些拿到令牌的请求将会被处理,如果此刻桶里存在900个令牌,则我们系统就可能会突发处理900个请求(毕竟只要你拿到令牌就会被处理),但是如果桶里此刻根本没有令牌,那么假设这时候再有10个请求进来,这10个请求便有可能被缓存或者被丢弃

计数器限流

计数器限流也是一种比较简单且较易实现的算法了,只要全局总请求数或者一定时间段的总请求数达到设定阈值,则进行限流。

参考文献:

http://manzhizhen.iteye.com/blog/2311691
https://www.chrisyue.com/leaky-bucket-and-nginx-limit_req-module.html