限流算法

固定窗口计数器算法

即计算单位时间内处理的请求数（注意是处理完的请求数，不是接收的请求数）如一分钟内，每处理一个就处理数量+1，一分钟后处理数超过规定值就熔断。然后重新处理书归零重新开始计数
无法应对突增的流量，如规定值为30，前55秒收到10个，最后五秒钟收到20，然后就冲垮

滑动窗口计数器算法
滑动窗口是固定窗口的升级。升级的地方在于：它把时间以一定比例分片。如规定一分钟最大处理60。然后一分钟分为30个分片。每个分片，即每2秒（60/30）内只能处理2个请求(60/30)
- 窗口数越多，负载越平稳
滑动窗口感觉就是单位时间小很多的固定窗口，没啥太大区别。就是避免了流量突增到系统崩溃前给他阻止掉
不过弊端是不好设置窗口数和最大请求数。设置高了可能不能应对突增，低了又不能充分利用资源。
- 这个在令牌桶算法中得到了解决
  漏桶算法
任意速率接收请求，固定速率处理请求。接收数达到处理数就将接收还未处理的请求熔断。相当于一个水桶，有一个洞，出水速率固定但是倒水速率任意。溢出桶的就丢弃
- 可以使用一个队列保存请求。定期从队列中取请求处理
漏桶算法可以看成另外一种解决限流算法无法应对突增的解决方法，并没有解决滑动窗口算法存在的问题

令牌桶算法
桶里装的是令牌了，请求在被处理之前需要拿到一个令牌，请求处理完毕之后将这个令牌丢弃（删除）。我们根据限流大小，按照一定的速率往桶里添加令牌。如果桶装满了，就不能继续往里面继续添加令牌了。
令牌桶算法相比于漏桶算法固定的处理速率，还允许一定程度的流量突增

限流的具体实现

单机情况
单机限流可以直接使用 Google Guava 自带的限流工具类 RateLimiter 。 RateLimiter 基于令牌桶算法，可以应对突发流量。
- RateLimiter 除了按照收到第一个请求从0个令牌开始添加令牌（即平滑突发限流），还允许进行预热，在无请求时也往桶里添加令牌，让令牌速率逐渐提升至最大处理值（即平滑预热限流）
```
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
```
```java import com.google.common.util.concurrent.RateLimiter;

/**

微信搜 JavaGuide 回复”面试突击”即可免费领取个人原创的 Java 面试手册 *
@author Guide哥
@date 2021/10/08 19:12 **/ public class RateLimiterDemo {

public static void main(String[] args) {
```
 // 1s 放 5 个令牌到桶里也就是 0.2s 放 1个令牌到桶里
 RateLimiter rateLimiter = RateLimiter.create(5);
 for (int i = 0; i < 10; i++) {
     double sleepingTime = rateLimiter.acquire(1);
     System.out.printf("get 1 tokens: %ss%n", sleepingTime);
 }
```
} } get 1 tokens: 0.0s get 1 tokens: 0.188413s get 1 tokens: 0.197811s get 1 tokens: 0.198316s get 1 tokens: 0.19864s get 1 tokens: 0.199363s get 1 tokens: 0.193997s get 1 tokens: 0.199623s get 1 tokens: 0.199357s get 1 tokens: 0.195676s

```java
public class RateLimiterDemo {

    public static void main(String[] args) {
        // 1s 放 5 个令牌到桶里也就是 0.2s 放 1个令牌到桶里
        // 预热时间为3s,也就说刚开始的 3s 内发牌速率会逐渐提升到 0.2s 放 1 个令牌到桶里
        RateLimiter rateLimiter = RateLimiter.create(5, 3, TimeUnit.SECONDS);
        for (int i = 0; i < 20; i++) {
            double sleepingTime = rateLimiter.acquire(1);
            System.out.printf("get 1 tokens: %sds%n", sleepingTime);
        }
    }
}
get 1 tokens: 0.0s
get 1 tokens: 0.561919s
get 1 tokens: 0.516931s
get 1 tokens: 0.463798s
get 1 tokens: 0.41286s
get 1 tokens: 0.356172s
get 1 tokens: 0.300489s
get 1 tokens: 0.252545s
get 1 tokens: 0.203996s
get 1 tokens: 0.198359s

分布式限流

分布式限流常见的方案：
- 借助中间件架限流：可以借助 Sentinel 或者使用 Redis 来自己实现对应的限流逻辑。
- 网关层限流：比较常用的一种方案，直接在网关层把限流给安排上了。不过，通常网关层限流通常也需要借助到中间件/框架。就比如 Spring Cloud Gateway 的分布式限流实现RedisRateLimiter就是基于 Redis+Lua 来实现的，再比如 Spring Cloud Gateway 还可以整合 Sentinel 来做限流。
如果你要基于 Redis 来手动实现限流逻辑的话，建议配合 Lua 脚本来做。
- 网上也有很多现成的脚本供你参考，就比如 Apache 网关项目 ShenYu 的 RateLimiter 限流插件就基于 Redis + Lua 实现了令牌桶算法/并发令牌桶算法、漏桶算法、滑动窗口算法。
Sentinel底层采用滑动窗口算法，可能是为了尽可能提高利用率，许多项目也会采用在gateway处设置redis令牌桶+sentinel共同实现限流

微服务

限流详解

限流算法

固定窗口计数器算法

滑动窗口计数器算法

漏桶算法

令牌桶算法

限流的具体实现

单机情况

分布式限流