面试官：你知道的限流算法有哪些？

介绍

一般做接口限流主要是为了应对突发流量，避免突发流量拖垮服务。如下面一些场景就有可能发生突发流量

1. 微博热搜
2. 恶意刷单
3. 恶意爬虫
4. 促销活动

接口限流的算法有如下几种

计数器算法

这是最容易理解和实现的算法，假设一个接口1s中最多请求100次。最开始设置一个计数器count=0，来一个请求count+1，1s之内count<=100的请求可以正常访问，count>100的请求则被拒绝，1s之后count被重置为0，重新开始计数

当然这种方式有个弊端，1s内只有最开始的100个请求能正常访问，后面的请求都不能正常访问，即突刺现象。此时我们就可以用滑动窗口算法来解决这个问题，例如把1s分成5个时间段，每个时间段能正常请求20次。

漏桶算法

漏桶算法参考家里使用的漏斗你就能明白了，往漏斗里面倒水，不论倒多少水，下面出水的速率是恒定的。当漏斗满了，多余的水就被直接丢弃了。

类比流量，每秒处理的速率是恒定的，如果有大量的流量过来就先放到漏斗里面。当漏斗也满了，请求则被丢弃。

实现：用队列保存请求，用ScheduledThreadPoolExecutor（支持定时任务的线程池）来定时从队列中取请求来执行

令牌桶算法

令牌桶算法可以说是对漏桶算法的改进。漏桶算法能限制请求的速率。而令牌桶算法在限制请求速率的同时还允许一定程度的突发调用

过程如下

1. 一直放令牌，如果令牌桶达到上限则丢弃令牌，假设每秒放10个
2. 可以应对一定程度的流量激增，如此时令牌桶有100个令牌，突然发生200次调用，则此时最开始的100次请求可以正常调用，后续的请求才会以10个/s的速率来调用

实现：用队列保存令牌，用ScheduledThreadPoolExecutor来定时放令牌

一般使用google提供的guava工具包即可

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

// 每秒生成2个令牌
RateLimiter rateLimiter = RateLimiter.create(2);
for (int i = 0; i < 6; i++) {
    new Thread(() -> {
        // 获得令牌
        rateLimiter.acquire();
        System.out.println(LocalDateTime.now());
    }).start();
}

输出为如下，可以看到每秒执行2个请求

2020-04-11T20:54:45.254
2020-04-11T20:54:45.554
2020-04-11T20:54:46.054
2020-04-11T20:54:46.555
2020-04-11T20:54:47.068
2020-04-11T20:54:47.554

rateLimiter提供了acquire()和tryAcquire()方法

1. acquire()方法，如果没有可用令牌，会一直阻塞到获得令牌
2. tryAcquire()方法，如果没有可用令牌，则直接返回false，可以设置超时获取

欢迎关注

参考博客

[1]https://github.com/doocs/advanced-java/blob/master/docs/high-concurrency/huifer-how-to-limit-current.md
[2]https://www.javashitang.com/?p=543
[3]https://www.cnblogs.com/xrq730/p/11025029.html
[4]https://www.jianshu.com/p/76cc8ba5ca91
[5]https://www.cnblogs.com/linjiqin/p/9707713.html