关于限流:接口限流算法漏桶算法令牌桶算法redis限流

高并发的零碎通常有三把利器：缓存、降级和限流。

缓存：缓存是进步零碎访问速度，缓解 CPU 解决压力的要害，同时能够进步零碎的解决容量。
降级：降级是在忽然的压力剧增的状况，依据业务以及流量对一些服务和页面的策略降级，以此开释服务器资源。
限流：限流是对于并发拜访 / 申请进行限速，或者一个工夫窗口内限速爱护零碎，一旦达到限度速度能够拒绝服务、排队或者期待。

令牌桶和和漏桶，比方 Google 的 Guava 的 RateLimiter 进行令牌痛管制。

漏桶算法是把流量比作水，水先放在桶外面并且以限定的速度出水，水过多会间接溢出，就会拒绝服务。

破绽存在出水口、进水口，出水口以肯定速率出水，并且有最大出水率。

在漏斗没有水的时候：

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

如果漏斗有水的时候：

出水为最大速率。
如果漏斗未满并且有进水，那么这些水会积在漏斗。
如果漏斗已满并且有进水，那么水会溢出到漏斗外。

对于很多利用场景来说，除了要求可能限度数据的均匀传输速率外，还要求容许某种程度的突发传输。这个时候应用令牌桶算法比拟适合。

令牌桶算法以恒定的速率产生令牌，之后再把令牌放回到桶当中，令牌桶有一个容量，当令牌桶满了的时候，再向其中放令牌会被间接抛弃，

https://github.com/google/guava

首先增加 Maven 依赖：

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->  
<dependency>  
   <groupId>com.google.guava</groupId>  
   <artifactId>guava</artifactId>  
   <version>31.1-jre</version>  
</dependency>

acquire(int permits) 函数次要用于获取 permits 个令牌，并计算须要期待多长时间，进而挂起期待，并将该值返回。

import com.google.common.util.concurrent.ListeningExecutorService;  
import com.google.common.util.concurrent.MoreExecutors;  
import com.google.common.util.concurrent.RateLimiter;  
  
import java.text.SimpleDateFormat;  
import java.util.Date;  
import java.util.concurrent.Executors;

public class Test {public static void main(String[] args) {ListeningExecutorService executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(100));
        // 指定每秒放 1 个令牌
  RateLimiter limiter = RateLimiter.create(1);
        for (int i = 1; i < 50; i++) {
            // 申请 RateLimiter, 超过 permits 会被阻塞
  //acquire(int permits)函数次要用于获取 permits 个令牌，并计算须要期待多长时间，进而挂起期待，并将该值返回
  Double acquire = null;
            if (i == 1) {
                // `acquire 1` 时，并没有任何期待 0.0 秒 间接预生产了 1 个令牌  
                acquire = limiter.acquire(1);
            } else if (i == 2) {
                // `acquire 10` 时，因为之前预生产了 1 个令牌，故而期待了 1 秒，之后又预生产了 10 个令牌  
                acquire = limiter.acquire(10);
            } else if (i == 3) {
                 // `acquire 2` 时，因为之前预生产了 10 个令牌，故而期待了 10 秒，之后又预生产了 2 个令牌
                acquire = limiter.acquire(2);
            } else if (i == 4) {
                //`acquire 20` 时，因为之前预生产了 2 个令牌，故而期待了 2 秒，之后又预生产了 20 个令牌  
                acquire = limiter.acquire(20);
            } else {
                // `acquire 2` 时，因为之前预生产了 2 个令牌，故而期待了 2 秒，之后又预生产了 2 个令牌  
                acquire = limiter.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 sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        System.out.println(sdf.format(new Date()) + "|" + Thread.currentThread().getName() + str);
    }
}

一个 RateLimiter 次要定义了发放 permits 的速率。如果没有额定的配置，permits 将以固定的速度调配，单位是每秒多少 permits。默认状况下，Permits 将会被稳固的平缓的发放。

RateLimiter 的执行后果如下

2023-01-03 06:18:53.684 | pool-1-thread- 1 获取令牌胜利，获取耗：0.0 第 1 个工作执行
2023-01-03 06:18:54.653 | pool-1-thread- 2 获取令牌胜利，获取耗：0.985086 第 2 个工作执行
2023-01-03 06:19:04.640 | pool-1-thread- 3 获取令牌胜利，获取耗：9.986942 第 3 个工作执行
2023-01-03 06:19:06.643 | pool-1-thread- 4 获取令牌胜利，获取耗：2.000365 第 4 个工作执行
2023-01-03 06:19:26.641 | pool-1-thread- 5 获取令牌胜利，获取耗：19.99702 第 5 个工作执行
2023-01-03 06:19:28.640 | pool-1-thread- 6 获取令牌胜利，获取耗：1.999456 第 6 个工作执行
2023-01-03 06:19:30.651 | pool-1-thread- 7 获取令牌胜利，获取耗：2.000317 第 7 个工作执行
2023-01-03 06:19:32.640 | pool-1-thread- 8 获取令牌胜利，获取耗：1.988647 第 8 个工作执行

从下面的后果能够晓得，令牌桶具备预生产能力。

`acquire 1` 时，并没有任何期待 0.0 秒 间接预生产了 1 个令牌  
`acquire 10` 时，因为之前预生产了 1 个令牌，故而期待了 1 秒，之后又预生产了 10 个令牌  
`acquire 2` 时，因为之前预生产了 10 个令牌，故而期待了 10 秒，之后又预生产了 2 个令牌  
`acquire 20` 时，因为之前预生产了 2 个令牌，故而期待了 2 秒，之后又预生产了 20 个令牌  
`acquire 2` 时，因为之前预生产了 20 个令牌，故而期待了 20 秒，之后又预生产了 2 个令牌  
`acquire 2` 时，因为之前预生产了 2 个令牌，故而期待了 2 秒，之后又预生产了 2 个令牌  
`acquire 2` 时 .....

预生产能力是一个相似前人挖坑，前人填坑的过程，从下面的运行后果来看，如果上一次申请获取的 permit 数越多，那么下一次再获取受权时更待的时候会更长，反之，如果上一次获取的少，那么工夫向后推移的就少，下一次取得许可的工夫更短。

限流的次要目标就是为了在单位工夫内，有且仅有 N 数量的申请可能拜访我的代码程序，依附setnx 能够轻松实现 CAS 操作，同时被获取的雷同 Key 设置过期工夫（expire），比方 10 秒内限定 20 个申请，那么咱们在 setnx 的时候能够设置过期工夫 10，当申请的 setnx 数量达到 20 时候即达到了限流成果。

setnx的操作的弊病是无奈进行限流统计，如果须要统计 10 秒内获取了多少个“桶”，须要在统计的过程中所有的桶都被持有。

限流波及的最次要的就是滑动窗口，下面也提到 1 -10 怎么变成 2 -11。其实也就是起始值和末端值都各 + 1 即可。

zset 数组能够实现相似滑动数组的形式，每次申请进入的时候，能够生成惟一的 UUID 作为 value，score 能够用以后工夫戳示意，因为 score 咱们能够用来计算以后工夫戳之内有多少的申请数量，同时 Zset 的数据结构提供 range 办法能够获取两个工夫戳范畴内有多少个申请。

具体实现代码如下：

public Response limitFlow(){Long currentTime = new Date().getTime();
        System.out.println(currentTime);
        if(redisTemplate.hasKey("limit")) {Integer count = redisTemplate.opsForZSet().rangeByScore("limit", currentTime -  intervalTime, currentTime).size();        // intervalTime 是限流的工夫 
            System.out.println(count);
            if (count != null && count > 5) {return Response.ok("每分钟最多只能拜访 5 次");
            }
        }
        redisTemplate.opsForZSet().add("limit",UUID.randomUUID().toString(),currentTime);
        return Response.ok("拜访胜利");
    }

zset 的实现形式也比较简单，每 N 秒能够产生 M 个申请，毛病是 zset 会随着构建数据一直增长。

咱们依据前文介绍的令牌桶能够得悉，当输入的速率大于输出的速率，会呈现“溢出”的状况。guava 通过acquire 办法挂起期待获取令牌，这种办法尽管能够做到准确的流量管制，然而会呈现“前人挖坑，前人埋坑”的状况，并且只能用于单 JVM 内存。

面对分布式我的项目，咱们能够通过 Redis 的 List 构造进行革新，实现形式同样非常简单。

依附 List 的 leftPop 来获取令牌：

// 输入令牌
public Response limitFlow2(Long id){Object result = redisTemplate.opsForList().leftPop("limit_list");
    if(result == null){return Response.ok("以后令牌桶中无令牌");
    }
    return Response.ok(articleDescription2);
}

leftPop
语法：LPOP key [count]
移除并返回存储在.key 的列表中的第一个元素。默认状况下，该命令从列表的结尾弹出一个元素。
案例：

redis> RPUSH mylist "one" "two" "three" "four" "five"
(integer) 5
redis> LPOP mylist
"one"
redis> LPOP mylist 2
1) "two"
2) "three"

再依附 Java 的定时工作，定时往 List 中 rightPush 令牌，为了保障分布式环境的强唯一性，能够应用 redission 生成惟一 ID 或者应用雪花算法生成 ID，这样的后果更为靠谱。

下面代码的集成能够应用 AOP 或者 Filter 中退出限流代码即可。较为完满的计划是依附 Redis 的限流，这样能够做到部署多个 JVM 也能够进行失常工作。

如果是单 JVM 则应用 UUID 的后果即可：

// 10S 的速率往令牌桶中增加 UUID，只为保障唯一性     @Scheduled(fixedDelay = 10_000,initialDelay = 0)     public void setIntervalTimeTask(){         redisTemplate.opsForList().rightPush("limit_list",UUID.randomUUID().toString());     }

漏桶算法的出水速度是恒定的，那么象征如果呈现大流量会把大部分申请同时抛弃（水溢出）。令牌桶的算法也是恒定的，申请获取令牌没有限度，对于大流量能够短时间产生大量令牌，同样获取令牌的过程耗费不是很大。

Redis 的限流不依赖 JVM，是较为靠谱和举荐的形式，具体的实现能够依赖 Redis 自身的数据结构和 Redis 命令人造的原子性实现，惟一须要留神的是在具体编程语言接入的时候是否写出具备线程平安的代码。

留神本文介绍的限流算法都是在 JVM 级别的限流，限流的令牌都是在内存中生成的，须要留神在分布式的环境下不能应用，如果要分布式限流，能够用 redis 限流。

应用 guava 限流是比拟常见的，而 Redis 的限流是依赖中间件实现的，实现起来更为简略也更举荐。

Redis 实现限流的三种形式 – 掘金 (juejin.cn)

java – 接口限流算法：漏桶算法 & 令牌桶算法 – 搜云库技术团队 – SegmentFault 思否

关于限流:接口限流算法漏桶算法令牌桶算法redis限流

引言

限流算法

漏桶算法

令牌桶算法

RateLimiter 用法

Redis 限流

基于 Redis 的 setnx 的操作

基于 Redis 的数据结构 zset

基于 Redis 的令牌桶算法

令牌桶算法 VS 漏桶算法 VSRedis 限流

小结

参考资料