何为过载保护?所谓“过载”,即需求超过了负载能力;而“保护”则是指当“过载”发生了,采取必要的措施保护自己不受“伤害”。在计算机领域,尤其是分布式系统领域,“过载保护”是一个重要的概念。一个不具备“过载保护”功能的系统,是非常危险和脆弱的,很可能由于瞬间的压力激增,引起“雪崩效应”,导致系统的各个部分都同时崩溃,停止服务。这就好像在没有保险丝的保护下,电压突然变高,导致所有的电器都会被损坏一样,“过载保护”功能是系统的“保险丝”。

去年开始,写了一个RPC服务框架,用以承接各个业务系统在其上进行各类业务服务接口的开发与部署,供远端调用。之于此类的框架,“过载保护”就是一个必须具备的功能特性,用以保护底层提供服务的业务系统不受“恶意”调用或突发性调用的破坏。而在整个实现整个功能的过程中,我发现实现“过载保护”算法是一个很有趣也比较有挑战的活。今天就稍微介绍一下这方面的算法吧。

可能跟大多数人一样,拿到这个算法需求很容易想到一个简单而又有点粗暴的算法:设置一个单位时间(如10s)内的最大访问量,并维护一个单位时间里的计数器,当访问请求到达时,先判断单位控制时间是否已经超时,如果已经超时,重置计数器为0;否则,将计数器加1,并判断计数器的值是否超过最大访问量设置,如超过,则拒绝访问。

具体的伪代码如下:(当然,具体的代码实现还有考虑并发的情况)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long timeStamp=getNowTime();
int reqCount=0;
const int maxReqCount=10000;//时间周期内最大请求数
const long effectiveDuration=10;//时间控制周期

bool grant(){
long now=getNowTime();
if (now <timeStamp+effectiveDuration){//在时间控制范围内
reqCount++;
return reqCount>maxReqCount;//当前时间范围内超过最大请求控制数
}else{
timeStamp=now;//超时后重置
reqCount=0;
return true;
}
}

该算法实现确实是实现了“单位时间里最大访问量控制”这一需求,但是,仔细研究下,发现它在两个单位时间的临界值上的处理是有缺陷的。如:设需要控制的最大请求数为1w, 在第一个单位时间的最后一秒里达到的请求数为1w,接下来第二个单位时间内的第一秒里达到请求数也是1w,由于超时重置发生在两个单位时间之间,所以这2w个请求都将通过控制,也就是说在2s里处理2w个请求,与我们设置的10s里1w个请求的需求相违背。

换句话说,这个算法,对请求的控制不够平滑。那是不是还有更平滑的算法呢?有,漏桶算法(Leaky Bucket)就是其一。

(图来自wikipedia)

如上图所示,我们假设系统是一个漏桶,当请求到达时,就是往漏桶里“加水”,而当请求被处理掉,就是水从漏桶的底部漏出。水漏出的速度是固定的,当“加水”太快,桶就会溢出,也就是“拒绝请求”。从而使得桶里的水的体积不可能超出桶的容量。

上面的分析可以看出,该算法存在三个变量:桶的容量capacity,水漏出的速度rate,以及当前的水量water。

算法伪代码如下:

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;//水满,拒绝加水
}
}

以上算法,我们可以通过调整capacity的值,来控制系统处理的最大请求数。而上文我们提到的时间边界处理的不够平滑问题,也可以很好的解决了,因为在每次进桶前都将执行“漏水”的操作,时间的切片不再是一个固定的值。

如果你现在正在维基百科上查看“漏桶算法”的篇章,你会发现有一个与“漏桶算法”相关联的算法叫令牌桶(Tocken Bucket)算法。令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。从原理上看,令牌桶算法和漏桶算法是相反的,一个“进水”,一个是“漏水”。

令牌桶算法伪代码如下,跟漏桶算法很相似:

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 tokens; //当前水量

bool grant() {
//先执行添加令牌的操作
long now = getNowTime();
tokens = max(capacity, tokens+ (now - timeStamp)*rate);
timeStamp = now;
//令牌已用完,拒绝访问
if(tokens<1){
return false;
}else{//还有令牌,领取令牌
tokens--;
retun true;
}
}

以上是关于漏桶算法和令牌桶算法的基本介绍,你趋向于用哪个呢?我现在用的是“漏桶”,没有什么原因,因为我首先看到的它,然后才看到“令牌桶”。但当然,实现这两个算法后,离真正的过载保护还有许多工程上的问题需要解决,比如当系统是多个节点组成的集群来提供服务时,我们需要统一的存储(一般用Redis之类的内存级存储较为合适)来维护当前桶的状态。