【限流】浅入解析限流基础算法

浅入解析限流基础算法

前言

针对大型的分布式集群系统，我们优化各项指标，旨在优化API的吞吐量和QPS。但是总归有一个上线，一瞬间的高并发请求如果被API全盘接收，可能会导致本来效率为500的接口不可用，且后续时间内效率也一直不会达到正常值。

此时我们针对这种大量的突刺访问，就必须要找到一种解决方法去解决这个问题。这里要讲的“限流”就是为了应对巨大流量的瞬间提交的解决方案。

一、计数器算法限流

同算法名称一样，就像我们规定，对于A接口，我们一分钟的访问次数不能超过1000个。那么我们就可以在一开始的时候，设置一个计数器cnt，每当一个请求过来的时候，cnt就加1，如果cnt的值大于100，并且该请求和第一个请求的间隔时间还在一分钟以内，就说明请求过多，直接返回失败。如果判断间隔超过一分钟，且cnt还没超过100，则就重置cnt。

如下所示：

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

该算法在一定程度上能实现限流方案，但是有比较明显的问题。

如果请求的频率不是均衡的，不是在这段时间内平均时间请求或较为平均的请求的时候。这个限流方案就会有临界问题。

如在0:59，发送了大量请求，在1:00，因为被重置了计数器，所以也可以发送100个请求。那么在这两秒钟内。总共发送了200个请求，并没有实现和我们规定的一分钟只能访问100个请求的方案。

二、滑动窗口

rolling window。为了解决上述计数器方法的缺陷，我们引入了滑动窗口的算法的精简版。

上图中，整个红色的矩形圈出来的部分表示一个时间窗口。比如一个时间窗口代表一分钟，如果我们像图里一样划分出了6格，那么每格就代表的是十秒钟。每过10秒钟，我们的时间窗口会往右滑动一格。每一个格子都有自己独立的计数器cnt，比如一个请求在0:35的时候到达，那么0:30-0.39对应的格子的cnt都会加1。

这样，在第一个计数器算法的缺陷问题我们因为每个格子都会加上响应的cnt，所以能进一步解决这个问题。此处可见，如果格子划分的更精细，滑动窗口的滚动就越平滑。限流的统计就会更精确。

三、漏桶算法

leaky bucket。

漏桶算法的思路，就是把请求当作一单位水，如一滴水。水先进入到漏桶里，漏桶以一定的速度出水，如果漏桶满了，则直接溢出算请求失败。

例子：

public class LeakyBucket {
        public long timeStamp = System.currentTimeMillis();  // 当前时间
        public long capacity; // 桶的容量
        public long rate; // 水漏出的速度
        public long water; // 当前水量(当前累积请求数)

        public boolean grant() {
            long now = System.currentTimeMillis();
            // 先执行漏水，计算剩余水量
            water = Math.max(0, water - (now - timeStamp) * rate); 
            
            timeStamp = now;
            if ((water + 1) < capacity) {
                // 尝试加水,并且水还未满
                water += 1;
                return true;
            } else {
                // 水满，拒绝加水
                return false;
        }
    }}
           

四、令牌桶算法

令牌桶算法的基本过程是

1. 假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；
2. 假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；
3. 当一个有n个单请求的业务请求到达时，就从令牌桶中删除n个令牌，并且将请求发送给下游服务
4. 如果令牌桶中少于n个令牌，那么不会删除令牌，请求被拒绝

附一个RateLimiter的demo

@RestController
public class HelloController {

    private static final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    private static final RateLimiter rateLimiter = RateLimiter.create(2);

    /**
     * tryAcquire尝试获取permit，默认超时时间是0，意思是拿不到就立即返回false
     */
    @RequestMapping("/sayHello")
    public String sayHello() {
        if (rateLimiter.tryAcquire()) { //  一次拿1个
            System.out.println(sdf.format(new Date()));
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }else {
            System.out.println("limit");
        }
        return "hello";
    }

    /**
     * acquire拿不到就等待，拿到为止
     */
    @RequestMapping("/sayHi")
    public String sayHi() {
        rateLimiter.acquire(5); //  一次拿5个
        System.out.println(sdf.format(new Date()));
        return "hi";
    }

}