Hello World

吞风吻雨葬落日 欺山赶海踏雪径

0%

限流

发表于 更新于 分类于

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流

缓存 缓存的目的是提升系统访问速度和增大系统处理容量
降级 降级是当服务出现问题或者影响到核心流程时，需要暂时屏蔽掉，待高峰或者问题解决后再打开
限流 限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

本次研究一下限流

限流算法

三种限流算法

  • 计数器法
  • 漏桶算法
  • 令牌桶算法

计数器法

是限流算法中最简单的一种。每个时间间隔设置一个计数器，每收到一个请求计数器加一，当计数器数值达到指定阈值的时候比较计数开始时间和当前时间的差是否大于指定时间间隔，大于时间间隔则计数器清零重新开始计数，否则丢弃请求。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import org.apache.commons.lang3.RandomUtils;

public class LimitCounter {

    /**
     *  计数器的限制大小
     */
    private final int LIMIT_SIZE = 100 ;

    /**
     * 计数花时间间隔
     */
    private final int PERIOD = 1000 ;

    //开始时间
    private long start = -1L;

    //计数器
    public int counter = 0 ;

    /**
     * 限流校验
     * @param req 请求数
     * @return
     */
    public boolean check(int req){

        //初始化开始时间
        if(start < 0 ){
            start = System.currentTimeMillis();
        }

        //当前时间
        long now = System.currentTimeMillis();

        //校验间隔，超出时间间隔重置计数器
        if( now - start > PERIOD ){
            //重置开始时间 和 计数器
            start = now;
            counter = 0 ;
        }

        //消费请求数
        counter += req;
        //请求数超过请求值
        if(counter > LIMIT_SIZE){
            return  false;
        }

        return true ;
    }

    public static void main(String[] args) {

        LimitCounter limitCounter = new LimitCounter();
        while(true){

            try {

                int time = RandomUtils.nextInt(0,999);
                int req = RandomUtils.nextInt(0,100);

                Thread.sleep(time);

                boolean check = limitCounter.check(req);
                System.out.println( (System.currentTimeMillis()) + " sleep="+ time +",req="+req +",check="+check);

            } catch (InterruptedException e) {
            }

        }
    }

}

返回结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1533891929746 sleep=821,req=30,check=true
1533891929844 sleep=96,req=17,check=true
1533891930613 sleep=766,req=65,check=false
1533891930688 sleep=72,req=46,check=false
1533891930788 sleep=95,req=51,check=true
1533891931303 sleep=511,req=71,check=false
1533891931495 sleep=189,req=67,check=false
1533891932445 sleep=948,req=48,check=true
1533891932909 sleep=460,req=51,check=true
1533891933444 sleep=532,req=77,check=false
1533891933621 sleep=175,req=35,check=true
1533891934037 sleep=412,req=3,check=true
1533891934262 sleep=220,req=0,check=true
1533891934996 sleep=731,req=11,check=true
1533891935702 sleep=701,req=85,check=true
1533891936475 sleep=769,req=30,check=true
1533891937174 sleep=697,req=4,check=true
1533891937588 sleep=411,req=25,check=true
1533891937836 sleep=244,req=82,check=false
1533891938614 sleep=775,req=96,check=true

注意这两条结果

1
2
1533891935702 sleep=701,req=85,check=true
1533891936475 sleep=769,req=30,check=true

在指定1000ms间隔内其实处理了85+30=115次的请求，大于了限制的100次。这就是计数器算法的缺点——两次计数时间范围边界请求无法控制的问题。

滑动窗口

针对于以上问题，我们引入滑动窗口算法。算法核心思想如下图所示

把计数的时间域划分为多个窗口，每个窗口有自己独立的计数器，随着时间的推移而向前滑动窗口，解决边界问题。（其实是把窗口划分的粒度更小来规避边界问题）

漏桶算法

令牌桶算法