接口限流了解一下

Contents

1. 前言
2. 限流方法
3. 单机限流算法
1. 3.1. 计数器
4. 滑动窗口
5. 漏桶算法
6. 令牌桶算法
7. Google Guava RateLimiter
8. 令牌桶和漏桶的比较
9. 更多
10. 参考链接

前言

针对一个秒杀系统，可能会有百万级别的用户进行抢购，但实际的商品数量可能只有几百或者几十，远远小于用户数量。如果这些请求都进行入队操作或查询缓存，对于最终的结果没有任何的意义。因此，为了减少资源浪费，减轻后端压力，我们需要对秒杀进行限流，保障部分用户服务正常即可。

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

缓存：缓存的目的是提升系统访问速度和增大系统处理容量

降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略地进行降级，以此释放服务器资源以保证核心任务的正常运行。

限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队

限流方法

限流可分为单机限流和分布式限流。

单机限流工具:

AtomicInterger
RateLimiter
Semaphore

分布式限流工具：

Nginx + Lua
redis + Lua

单机限流算法

计数器

介绍：在接口层面应用比较广泛，即在一段时间内，进行计数，与阈值进行比较，到了时间临界点，将计数器清0。

不足：存在时间临界点的问题，在某个时间临界点会承受恶意用户的大量请求，甚至超出系统预期的承受。

由上图可见，恶意用户可能在0:59时瞬间发送100个请求，在1:00又瞬间发送100个请求，这样一来用户在一秒内就发送了200个请求，极有可能通过这个算法漏洞瞬间压垮我们的应用。

滑动窗口

这里的滑动窗口类似于TCP中的滑动窗口，如果我们把刚刚一分钟看做一个窗口的话，现在我们划分为6格，每格代表10秒钟，比如我们有个请求在0:35秒的时候到来，那么0:30-0:39对应的counter就会加1。

接下来我们看看滑动窗口如何解决计数器的临界问题，0:59到达的100个请求落在灰色的格子里，而1:00到达的100个请求会落在橘黄色的格子里。当时间到达1:00时，我们的时间窗口（虚线表示）会往右移动一格，此时时间窗口内的总请求数量为200个，超过了限定的100个，能够检测出触发限流的条件。

可见，当滑动窗口的格子划分越多，那么滑动窗口的滚动就越平滑，限流的统计就会更精细。

漏桶算法

与上述两种算法不同，漏桶算法脱离了时间片的概念，限流统计的方法更为先进。

在漏洞中没有水时：

如果进水速率小于等于最大出水速率，那么出水速率等于进水速率，此时不会积水
如果进水速率大于最大出水速率，那么漏斗以最大速率出水，此时多余的水会积在漏斗中

在漏洞中有水时：

出水口以最大速率出水
如果漏斗未满，且有进水的话，那么这些水会积在漏斗中
如果漏斗已满，且有进水的话，那么这些水会溢出到漏斗之外

由上可见，漏桶算法可以限制网络传输的速率，但无法处理突发传输，比如接口请求量在某一时刻突然激增到了十多倍，如果应用接口毫无限制地处理请求返回数据包，很有可能造成整个应用的不可用。

示例代码：

public class LeakyBucketDemo {
    //时间刻度
    private static long time = System.currentTimeMillis();
    //桶里面现在的水
    private static int water = 0;
    //桶的大小
    private static int size = 10;
    //出水速率
    private static int rate = 3;

    public static boolean grant() {
        //计算出水的数量
        long now = System.currentTimeMillis();
        int out = (int) ((now - time) / 700 * rate);
        //漏水后的剩余
        water = Math.max(0, water - out);
        time = now;
        if ((water + 1) < size) {
            ++water;
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 500; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    if (grant()) {
                        System.out.println("执行业务逻辑");
                    } else {
                        System.out.println("限流");
                    }
                }
            }).start();
        }
    }
}

令牌桶算法

为解决瞬时大容量导致大部分网络请求被丢弃的情况，使用令牌桶进行了算法改进。

令牌桶算法是一个存放固定容量令牌（token）的桶，按照固定速率往桶里添加令牌。

令牌按固定的速率被放入令牌桶中，如：r tokens/s
桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝
当一个n字节大小的数据包到达，将从桶里删除n个令牌，接着数据包被发送到网络上
如果桶中的令牌不足n个，则不会删除令牌，且数据包将被限流（丢弃或在缓冲区等待）

Google Guava RateLimiter

Guava包的通常用途，详见此链接：

对JDK集合的补充和改进
提供本地缓存Guava Cache
对JDK提供的线程池进行异步回调
提供RateLimter限流工具类

pom依赖如下：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>18.0</version>
</dependency>

示例代码：

public class RateLimiterDemo {
    public static void main(String[] args) {
        ListeningExecutorService executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(100));
        //指定每秒释放一个令牌
        RateLimiter rateLimiter = RateLimiter.create(1);
        for (int i = 0; i < 50; i++) {
            //请求RateLimiter,超过permits会被阻塞
            //acquire(int permits)函数主要用于获取permits个令牌，并计算需要等待多长时间，进而挂起等待，并将该值返回
            Double acquire = null;
            if (i == 1) {
                acquire = rateLimiter.acquire(1);
            } else if (i == 2) {
                acquire = rateLimiter.acquire(10);
            } else if (i == 3) {
                acquire = rateLimiter.acquire(2);
            } else if (i == 4) {
                acquire = rateLimiter.acquire(20);
            } else {
                acquire = rateLimiter.acquire(2);
            }
            executorService.submit(new Task("获取令牌成功，获取耗时：" + acquire + " 第 " + i + " 个任务执行"));
        }
    }


}

class Task implements Runnable {
    String str;

    public Task(String str) {
        this.str = str;
    }

    @Override
    public void run() {
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        System.out.println(simpleDateFormat.format(new Date()) + " | " + Thread.currentThread().getName() + str);
    }
}

输出：

create(double permitsPerSecond)函数用于根据指定的稳定吞吐率创建RateLimiter，这里的吞吐率是指每秒多少许可数（通常是指QPS，每秒多少查询）

acquire(int permits)函数从RateLimiter获取指定许可数，该方法会被阻塞直到获取到请求

由结果可以看出上一次请求获取的permit数越多，那么下一次再次获取授权时等待的时间会更长，反之，如果上一次获取的少，那么时间向后推移的就少，下一次获取许可的时间更短。

令牌桶和漏桶的比较

区别	令牌桶	漏桶
请求何时拒绝	固定速率往桶中添加令牌，如果桶中令牌不够，则拒绝新请求	流入请求速率任意，常量固定速率流出请求。当流入请求数积累到漏桶容量时，则拒绝新请求
速率限制	限制平均流入速率，允许一定程度的突发请求（支持一次拿多个令牌）	限制常量流出速率（流出速率是固定值），从而平滑突发流入速率

Guava官方文档-RateLimiter类

源码解析可参考：

Spring MVC限流实战

分布式限流Redis+Lua实现

JasonRen's Blog

Hello World!