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

阿东

发布于 2023-01-08 14:38:25

1.6K0

发布于 2023-01-08 14:38:25

文章被收录于专栏：公众号：懒时小窝

引言

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

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