CloudSentinel
限流

常见限流算法

计数器法

定义一个时间窗口，以及时间窗口内最大请求数，当每个请求来时判断请求时间是否小于窗口起始时间加时间窗口时长，即是否在时间窗口内，若在则将计数器加一，且判断当前时间窗口内是否超过最大请求控制数，否则将窗口起始时间重置为当前时间，且重置请求数。缺点精度太低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Counter {
    public long timeStamp = System.currentTimeMillis();  // 当前时间
    public int reqCount = 0;  // 初始化计数器
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000 * 60; // 时间窗口ms

    public boolean limit() {
        long now = System.currentTimeMillis();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
}

滑动时间窗口

为了解决计数器法统计精度太低的问题，引入了滑动窗口算法，红色的矩形框表示一个时间窗口，一个时间窗口就是一分钟，将滑动窗口划成了6格，所以每格代表的是10秒钟，每过10秒钟，时间窗口就会往右滑动一格，每一个格子都有自己独立的计数器counter。

滑动时间窗口算法

计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

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
/**
 * 滑动时间窗口限流实现，假设某个服务最多只能每秒钟处理100个请求，我们可以设置一个1秒钟的滑动时间窗口，
 * 窗口中有10个格子，每个格子100毫秒，每100毫秒移动一次，每次移动都需要记录当前服务请求的次数
 */
public class SlidingTimeWindow {
    //服务访问次数，可以放在Redis中，实现分布式系统的访问计数
    Long counter = 0L;
    //使用LinkedList来记录滑动窗口的10个格子。
    LinkedList<Long> slots = new LinkedList<Long>();

    public static void main(String[] args) throws InterruptedException {
        SlidingTimeWindow timeWindow = new SlidingTimeWindow();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    timeWindow.doCheck();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
        while (true) {
            //TODO 判断限流标记
            timeWindow.counter++;
            Thread.sleep(new Random().nextInt(15));
        }
    }

    private void doCheck() throws InterruptedException {
        while (true) {
            slots.addLast(counter);
            if (slots.size() > 10) {
                slots.removeFirst();
            }
            //比较最后一个和第一个，两者相差100以上就限流
            if ((slots.peekLast() - slots.peekFirst()) > 100) {
                System.out.println("限流了。。");
                //TODO 修改限流标记为true
            } else {
                //TODO 修改限流标记为false
            }
            Thread.sleep(100);
        }
    }
}

漏桶算法

有一个固定容量的桶，有水流进来也有水流出去，对于流进来的水来说，无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，该桶可以固定水流出的速率。且当桶满后多余的水将溢出。漏桶算法天生就限制了请求的速度，当使用了漏桶算法，保证接口会以一个常速速率来处理请求。故漏桶算法天生不会出现临界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeakyBucket {
    public long timeStamp = System.currentTimeMillis();  // 当前时间
    public long capacity; // 桶的容量
    public long rate; // 水漏出的速度(每秒系统能处理的请求数)
    public long water; // 当前水量(当前累积请求数)
    public boolean limit() {
        long now = System.currentTimeMillis();
        water = Math.max(0, water - ((now - timeStamp) / 1000) * rate); // 先执行漏水，计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        } else {
            // 水满，拒绝加水
            return false;
        }
    }
}

令牌桶算法

令牌桶算法比漏桶算法稍显复杂，有一个固定容量的桶，桶里存放着令牌，桶一开始是空的，token以 一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃，每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class TokenBucket {
    public long timeStamp = System.currentTimeMillis();  // 当前时间
    public long capacity; // 桶的容量
    public long rate; // 令牌放入速度
    public long tokens; // 当前令牌数量

    public boolean grant() {
        long now = System.currentTimeMillis();
        // 先添加令牌
        tokens = Math.min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若不到1个令牌,则拒绝
            return false;
        } else {
            // 还有令牌，领取令牌
            tokens -= 1;
            return true;
        }
    }
}

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器，所以滑动窗口在实现上需要更多的存储空间。若滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发，默认的令牌桶算法，取走token是不需要耗费时间的，若桶内有100个token时，则可瞬间允许100个请求通过。