常见的四种限流算法及基础实现

什么是限流

限流是对某一时间窗口内的请求数进行限制，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。

在高并发系统中，出于系统保护角度考虑，通常会对流量进行限流。

在分布式系统中，高并发场景下，为了防止系统因突然的流量激增而导致的崩溃，同时保证服务的高可用性和稳定性，限流是最常用的手段。

有哪些限流算法？

常见的四种限流算法，分别是：固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。

限流算法

固定窗口

1. 实现原理

• 固定窗口又称固定窗口（又称计数器算法，Fixed Window）限流算法，是最简单的限流算法。

• 实现原理：在指定周期内累加访问次数，当访问次数达到设定的阈值时，触发限流策略，当进入下一个时间周期时进行访问次数的清零。如图所示，我们要求 3 秒内的请求不要超过 150 次：

2. 简易代码实现

public class FixedWindow {

    private long time = new Date().getTime();

    private Integer count = 0; // 计数器
    private final Integer max = 100; // 请求阈值
    private final Integer interval = 1000; // 窗口大小

    public boolean trafficMonitoring() {
        long nowTime = new Date().getTime();
        if (nowTime < time + interval) {
            // 在时间窗口内
            count++;
            return max > count;
        } else {
            time = nowTime; // 开启新的窗口
            count = 1; // 初始化计数器,由于这个请求属于当前新开的窗口，所以记录这个请求
            return true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 优缺点

1. 优点：实现简单，容易理解
2. 缺点：

• 限流不够平滑。例如：限流是每秒 3 个，在第一毫秒发送了 3 个请求，达到限流，窗口剩余时间的请求都将会被拒绝，体验不好。

• 无法处理窗口边界问题。因为是在某个时间窗口内进行流量控制，所以可能会出现窗口边界效应，即在时间窗口的边界处可能会有大量的请求被允许通过，从而导致突发流量。

即：如果第 2 到 3 秒内产生了 150 次请求，而第 3 到 4 秒内产生了 150 次请求，那么其实在第 2 秒到第 4
秒这两秒内，就已经发生了 300 次请求了，远远大于我们要求的 3 秒内的请求不要超过 150 次这个限制，如下图所示：

滑动窗口

1. 实现原理

• 滑动窗口为固定窗口的改良版，解决了固定窗口在窗口切换时会受到两倍于阈值数量的请求。在滑动窗口算法中，窗口的起止时间是动态的，窗口的大小固定。这种算法能够较好地处理窗口边界问题，但是实现相对复杂，需要记录每个请求的时间戳。

• 实现原理：滑动窗口在固定窗口的基础上，将时间窗口进行了更精细的分片，将一个窗口分为若干个等份的小窗口，每次仅滑动一小块的时间。每个小窗口对应不同的时间点，拥有独立的计数器，当请求的时间点大于当前窗口的最大时间点时，则将窗口向前平

• 移一个小窗口（将第一个小窗口的数据舍弃，第二个小窗口变成第一个小窗口，当前请求放在最后一个小窗口），整个窗口的所有请求数相加不能大于阈值。其中，Sentinel 就是采用滑动窗口算法来实现限流的。

如图所示：

2. 使用zset实现滑动窗口

通过使用springAOP和redis中的zset进行实现滑动窗口限流

定义注解

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface RateLimiter {

    /**
     * 限流时间，单位秒
     */
    int time() default 5;

    /**
     * 限流次数
     */
    int count() default 10;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

对应注解限流处理切面(主要)

@Aspect
@Component
public class RateLimiterAspect {

    private static final Logger log = LoggerFactory.getLogger(RateLimiterAspect.class);

    @Autowired
    private RedisTemplate redisTemplate;

    /**
     * 实现限流（新思路）
     * @param point
     * @param rateLimiter
     * @throws Throwable
     */
    @Before("@annotation(rateLimiter)")
    public void doBefore(JoinPoint point, RateLimiter rateLimiter) throws Throwable {
        // 在 {time} 秒内仅允许访问 {count} 次。
        int time = rateLimiter.time();
        int count = rateLimiter.count();
        // 根据用户IP（可选）和接口方法，构造key
        String combineKey = getCombineKey(point);
        System.err.println(combineKey);
        // 记录本次访问的时间结点
        long currentMs = System.currentTimeMillis();
        redisTemplate.opsForZSet().add(combineKey, String.valueOf(currentMs), currentMs);
        // 这一步是为了防止一直存在于内存中
        redisTemplate.expire(combineKey, time, TimeUnit.SECONDS);
        // 移除{time}秒之前的访问记录（滑动窗口思想）
        redisTemplate.opsForZSet().removeRangeByScore(combineKey, 0, currentMs - time * 1000);

        // 获得当前窗口内的访问记录数
        Long currCount = redisTemplate.opsForZSet().zCard(combineKey);
        // 限流判断
        if (currCount !=null && currCount > count) {
            //返回异常提示
            log.error("[limit] 限制请求数'{}',当前请求数'{}',缓存key'{}'", count, currCount, combineKey);
            //todo 返回异常

        }
    }
    /**
     * @param point 切入点
     * @return 组合key
     */
    private String getCombineKey(JoinPoint point) {
        StringBuilder sb = new StringBuilder("rate_limit:");

        MethodSignature signature = (MethodSignature) point.getSignature();
        Method method = signature.getMethod();
        Class<?> targetClass = method.getDeclaringClass();
        // keyPrefix + "-" + class + "-" + method  //类名加方法名
        return sb.append("-").append( targetClass.getName() )
                .append("-").append(method.getName()).toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

使用@RateLimiter注解进行限流

    @RateLimiter(time = 1, count = 10)
    @GetMapping("/testIndex")
    public String index(){
        System.out.println("处理请求");
        return "finish";
    }
1
2
3
4
5
6

3. 优缺点

1. 优点：解决了固定窗口算法的窗口边界问题，避免突发流量压垮服务器。
2. 缺点：还是存在限流不够平滑的问题。例如：限流是每秒 3 个，在第一毫秒发送了 3 个请求，达到限流，剩余窗口时间的请求都将会被拒绝，体验不好。

漏桶算法

1. 实现原理
漏桶限流算法是一种常用的流量整形（Traffic Shaping）和流量控制（Traffic Policing）的算法，它可以有效地控制数据的传输速率以及防止网络拥塞。

主要的作用：

• 控制数据注入网络的速度。
• 平滑网络上的突发流量

实现原理：
漏桶是一个很形象的比喻，外部请求就像是水一样不断注入水桶中，而水桶已经设置好了最大出水速率，漏桶会以这个速率匀速放行请求，而当水超过桶的最大容量后则被丢弃。不管上面的水流速度有多块，漏桶水滴的流出速度始终保持不变。消息中间件就采用的漏桶限流的思想。

如图所示：

核心步骤：

1. 一个固定容量的漏桶，按照固定速率出水（处理请求）；
2. 当流入水（请求数量）的速度过大会直接溢出（请求数量超过限制则直接拒绝）。
3. 桶里的水（请求）不够则无法出水（桶内没有请求则不处理）。

2. 简易实现

public class LeakyBucket {
    private long capacity;  // 漏桶容量
    private long rate;      // 流出速率
    private long water;     // 当前水量
    private long lastTime;  // 上次请求时间

    public LeakyBucket(long capacity, long rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = 0;
        this.lastTime = System.currentTimeMillis();
    }

    public synchronized boolean allow() {
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastTime;
        lastTime = now;

        // 先漏水，根据流出速率计算漏掉的水量
        water = Math.max(0, water - elapsedTime * rate);

        // 检查水量是否超出了容量
        if (water < capacity) {
            water++;
            return true;  // 请求通过，水量增加
        } else {
            return false;  // 请求被拒绝，水量已满
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. 优缺点

1. 优点：

• 平滑流量。由于漏桶算法以固定的速率处理请求，可以有效地平滑和整形流量，避免流量的突发和波动（类似于消息队列的削峰填谷的作用）。
• 防止过载。当流入的请求超过桶的容量时，可以直接丢弃请求，防止系统过载。

2. 缺点：

• 无法处理突发流量：由于漏桶的出口速度是固定的，无法处理突发流量。例如，即使在流量较小的时候，也无法以更快的速度处理请求。
• 可能会丢失数据：如果入口流量过大，超过了桶的容量，那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中，这可能是一个问题。
• 不适合速率变化大的场景：如果速率变化大，或者需要动态调整速率，那么漏桶算法就无法满足需求。
• 资源利用率：不管当前系统的负载压力如何，所有请求都得进行排队，即使此时服务器的负载处于相对空闲的状态，这样会造成系统资源的浪费。

由于漏桶的缺陷比较明显，所以在实际业务场景中，使用的比较少。

令牌算法

1. 实现原理
令牌桶算法是基于漏桶算法的一种改进，主要在于令牌桶算法能够在限制服务调用的平均速率的同时，还能够允许一定程度内的突发调用。

实现原理：

1. 系统以固定的速率向桶中添加令牌；
2. 当有请求到来时，会尝试从桶中移除一个令牌，如果桶中有足够的令牌，则请求可以被处理或数据包可以被发送；
3. 如果桶中没有令牌，那么请求将被拒绝；
4. 桶中的令牌数不能超过桶的容量，如果新生成的令牌超过了桶的容量，那么新的令牌会被丢弃。

令牌桶算法的一个重要特性是，它能够应对突发流量。当桶中有足够的令牌时，可以一次性处理多个请求，这对于需要处理突发流量的应用场景非常有用。但是又不会无限制的增加处理速率导致压垮服务器，因为桶内令牌数量是有限制的。

2. 代码实现
Guava 中的 RateLimiter 就是基于令牌桶实现的，可以直接拿来使用。

<dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>19.0</version>
        </dependency>
1
2
3
4
5

    public void acquireTest() {
        //每秒固定生成5个令牌
        RateLimiter rateLimiter = RateLimiter.create(5);
        for (int i = 0; i < 10; i++) {
            double time = rateLimiter.acquire();
            logger.info("等待时间：{}s", time);
        }
    }
1
2
3
4
5
6
7
8

3. 优缺点

1. 优点

• 可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
• 限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）。
• 灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率。

2. 缺点：

• 可能导致过载：如果令牌产生的速度过快，可能会导致大量的突发流量，这可能会使网络或服务过载。
• 需要存储空间：令牌桶需要一定的存储空间来保存令牌，可能会导致内存资源的浪费。