阿东lazy

V2

2023/01/08阅读:33主题:橙心

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

引言

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

缓存:缓存是提高系统访问速度,缓解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) 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());     }

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

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

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

小结

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

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

参考资料

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

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

分类:

后端

标签:

Java

作者介绍

阿东lazy
V2

摸鱼JAVA工程师 公众号:懒时小窝