写点什么

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

作者:懒时小窝
  • 2023-01-08
    广东
  • 本文字数:4464 字

    阅读完需:约 15 分钟

引言

高并发的系统通常有三把利器:缓存、降级和限流


缓存:缓存是提高系统访问速度,缓解 CPU 处理压力的关键,同时可以提高系统的处理容量。降级:降级是在突然的压力剧增的情况,根据业务以及流量对一些服务和页面的策略降级,以此释放服务器资源。限流:限流是对于并发访问/请求进行限速,或者一个时间窗口内限速保护系统,一旦到达限制速度可以拒绝服务、排队或者等待。

限流算法

令牌桶和和漏桶,比如 Google 的 Guava 的 RateLimiter 进行令牌痛控制。

漏桶算法

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



漏洞存在出水口、进水口,出水口以一定速率出水,并且有最大出水率。


在漏斗没有水的时候:


  • 进水的速率小于等于最大出水率,那么出水速率等于进水速率,此时不会积水。

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


如果漏斗有水的时候:


  • 出水为最大速率。

  • 如果漏斗未满并且有进水,那么这些水会积在漏斗。

  • 如果漏斗已满并且有进水,那么水会溢出到漏斗外。

令牌桶算法

对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这个时候使用令牌桶算法比较合适。


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


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数越多,那么下一次再获取授权时更待的时候会更长,反之,如果上一次获取的少,那么时间向后推移的就少,下一次获得许可的时间更短。

Redis 限流

基于 Redis 的 setnx 的操作

限流的主要目的就是为了在单位时间内,有且仅有 N 数量的请求能够访问我的代码程序,依靠setnx 可以轻松完成 CAS 操作,同时被获取的相同 Key 设置过期时间(expire),比如 10 秒内限定 20 个请求,那么我们在 setnx 的时候可以设置过期时间 10,当请求的 setnx 数量达到 20 时候即达到了限流效果。


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

基于 Redis 的数据结构 zset

限流涉及的最主要的就是滑动窗口,上面也提到 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 会随着构建数据不断增长。

基于 Redis 的令牌桶算法

我们根据前文介绍的令牌桶可以得知,当输出的速率大于输入的速率,会出现“溢出”的情况。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) 5redis> LPOP mylist"one"redis> LPOP mylist 21) "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());     }
复制代码

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

漏桶算法的出水速度是恒定的,那么意味如果出现大流量会把大部分请求同时丢弃(水溢出)。令牌桶的算法也是恒定的,请求获取令牌没有限制,对于大流量可以短时间产生大量令牌,同样获取令牌的过程消耗不是很大。


Redis 的限流不依赖 JVM,是较为靠谱和推荐的方式,具体的实现可以依赖 Redis 本身的数据结构和 Redis 命令天然的原子性实现,唯一需要注意的是在具体编程语言接入的时候能否写出具备线程安全的代码。

小结

注意本文介绍的限流算法都是在 JVM 级别的限流,限流的令牌都是在内存中生成的,需要注意在分布式的环境下不能使用,如果要分布式限流,可以用 redis 限流。


使用 guava 限流是比较常见的,而 Redis 的限流是依赖中间件完成的,实现起来更为简单也更推荐。

参考资料

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


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


用户头像

懒时小窝

关注

赐他一块白石,石头上写着新名 2020-09-23 加入

如果我们想要知道自己想要做什么,必须先找到自己的白色石头。欢迎关注个人公众号“懒时小窝”,不传播焦虑,只分享和思考有价值的内容。

评论

发布
暂无评论
接口限流算法:漏桶算法&令牌桶算法&redis限流_懒时小窝_InfoQ写作社区