过载保护算法

保护 瞬间的压力激增，引起“雪崩效应”，系统各个部分同时崩溃，停止服务

简单粗暴的算法

设置一个单位时间（如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）

假设系统是一个漏桶，请求时往漏桶里“加水”，请求被处理掉，就是水从漏桶的底部漏出

水漏出的速度是固定的，当“加水”太快，桶就会溢出，也就是“拒绝请求”。从而使得桶里的水的体积不可能超出桶的容量

算法存在三个变量：桶的容量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之类的内存级存储较为合适）来维护当前桶的状态

categories: dev tags: lang pattern