【java】常见限流算法原理及应用

目录

前言

限流的作用

4种常见限流算法

固定窗口限流

基本原理

简单实现

优点和缺点

滑动窗口限流

基本原理

简单实现

优点和缺点

漏桶限流

基本原理

简单实现

优点和缺点

令牌桶限流

基本原理

简单实现

优点和缺点

算法比较与选择

---

前言

在现代分布式系统和高并发场景下，限流已成为保障系统稳定性和可用性的重要手段。随着互联网应用规模的不断扩大，系统经常会面对海量请求和突发流量，如何有效控制和管理这些请求流量成为一项关键挑战。限流算法作为流量控制的重要工具，能够帮助系统平衡资源分配、抵御恶意攻击，并在高峰期维持服务的连续性与可靠性。本文将深入探讨几种常见的限流算法及其应用场景，帮助读者更好地理解限流机制的工作原理与优化策略。

限流的作用

限流的作用在于防止系统过载、保障服务的可用性、优化资源利用、平滑高峰流量，并确保服务质量和用户体验。通过控制请求的频率，限流机制能够在高并发或突发流量的情况下保护系统资源，提升其整体性能和响应能力，从而避免系统崩溃或服务中断。

4种常见限流算法

固定窗口限流

基本原理

计数器算法是在一定的时间间隔里，记录请求次数，当请求次数超过间隔内的最大次数时，触发限流策略。当进入下一个时间窗口时进行访问次数的清零。例如，如果设置了1秒钟内最多允许100个请求的上限，那么系统会统计当前窗口内的请求数量，当请求数量未达到上限时，允许请求通过，一旦达到上限，则拒绝剩余的请求，直到进入下一个时间窗口为止，在新的时间窗口开始时，计数器会被重置，重新统计请求数量。如下图所示：

简单实现

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流键* @param limit      请求限制数量* @param windowSize 窗口大小*/public void doRateLimit(String key, Long limit, Long windowSize) {// 加分布式锁RLock rLock = redissonClient.getLock(key);try {// 加锁rLock.lock(100, TimeUnit.MILLISECONDS);// 获取原子计数器RAtomicLong counter = redissonClient.getAtomicLong(key);// 计数long count = counter.incrementAndGet();// 如果是第一个请求，初始化窗口并设置过期时间if (count == 1) {// 窗口时长设置为1秒counter.expire(windowSize, TimeUnit.SECONDS);}// 如果请求数量超过限制，触发限流if (count > limit) {// 触发限流的不记在请求数量中counter.decrementAndGet();// 执行限流逻辑}// 请求通过，继续处理业务逻辑} finally {rLock.unlock();}}
}

优点和缺点

优点：实现简单，易于理解。

缺点：存在明显的临界问题，比如: 假设限流阀值为5个请求，单位时间窗口是1s,如果我们在单位时间内的前0.8-1s和1-1.2s，分别并发5个请求。虽然都没有超过阀值，但是如果算0.8-1.2s,则并发数高达10，已经超过单位时间1s不超过5阀值的定义啦。

滑动窗口限流

基本原理

滑动窗口顾名思义，就是持续的滑动，它的窗口大小是固定的，但是起止时间是动态的，窗口大小被分割成大小相等的若干子窗口，每次滑动，都会滑过一个子窗口，同时每个子窗口单独计数，并且所有子窗口的计数求和不应大于整体窗口的阈值。这样的话，当新请求的时间点大于时间窗口右边界时，窗口右移一个子窗口，最左边的子窗口的计数值舍弃。 例如，如果设定的限流策略是“每秒钟最多允许100个请求”，那么系统会不断滑动地统计过去1秒内的请求次数。如果请求次数未达到上限，允许请求通过；否则拒绝请求。如下图所示：

简单实现

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流键* @param limit      请求限制数量* @param windowSize 窗口大小*/public void doRateLimit(String key, Long limit, Long windowSize) {// 获取计数的有序集合RScoredSortedSet<Long> counter = redissonClient.getScoredSortedSet(key);// 使用分布式锁RLock rLock = redissonClient.getLock(key);try {// 加锁rLock.lock(200, TimeUnit.MILLISECONDS);// 当前时间戳long currentTimestamp = System.currentTimeMillis();// 窗口起始时间戳long windowStartTimestamp = currentTimestamp - windowSize * 1000;// 移除窗口外的请求（即移除时间小于窗口起始时间的请求）counter.removeRangeByScore(0, true, windowStartTimestamp, false);// 将当前时间戳作为score和member存入有序集合中counter.add(currentTimestamp, currentTimestamp);// 获取当前窗口内的请求数量long count = counter.size();// 判断是否超过限流阈值if (count > limit) {// 执行限流逻辑}// 请求通过，继续处理业务逻辑} finally {rLock.unlock();}}
}

优点和缺点

优点：

• 简单易懂，精度较高，也解决了固定窗口的临界时间处理问题。

缺点：

• 突发流量无法处理，一旦到达限流后，请求都会直接暴力被拒绝，影响用户的体验。

漏桶限流

基本原理

漏桶算法可以形象地理解为一个固定容量的水桶，水以不规则的速度流入桶中，但以固定的速率从桶底漏出。假设水桶的容量是固定的，如果水流入的速度超过了漏出的速度，且水桶已满，多余的水（请求）将被丢弃。如下图所示：

简单实现

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {private static final String KEY_PREFIX = "leakyBucketRateLimiter:";@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流键* @param leakRate   漏出速率* @param bucketSize 桶的容量*/public void doRateLimit(String key, Long leakRate, Long bucketSize) {// 获取当前请求的水位桶RBucket<Long> bucket = redissonClient.getBucket(KEY_PREFIX + key);// 获取最后一次漏出请求的时间RBucket<Long> lastLeakTimeBucket = redissonClient.getBucket(KEY_PREFIX + key + ":lastLeakTime");// 创建分布式锁RLock lock = redissonClient.getLock(KEY_PREFIX + "LOCK:" + key);try {// 尝试获取锁lock.lock(100, TimeUnit.MILLISECONDS);// 当前时间戳long currentTime = System.currentTimeMillis();// 当前水位Long currentWaterLevel = bucket.get();// 上次漏出时间Long lastLeakTime = lastLeakTimeBucket.get();// 初始化水位和漏出时间if (currentWaterLevel == null) {currentWaterLevel = 0L;}if (lastLeakTime == null) {lastLeakTime = currentTime;}// 计算自上次漏出以来经过的时间long timeElapsed = currentTime - lastLeakTime;// 计算漏出的请求数量long leakedAmount = timeElapsed / leakRate;// 更新水位if (leakedAmount > 0) {// 更新水位，确保不为负currentWaterLevel = Math.max(0, currentWaterLevel - leakedAmount);// 更新最后漏出时间lastLeakTimeBucket.set(currentTime);}// 检查是否可以接受新的请求if (currentWaterLevel < bucketSize) {// 接受请求，水位加一bucket.set(currentWaterLevel + 1);// 请求通过，继续处理业务逻辑} // 触发限流逻辑} finally {lock.unlock();}}
}

优点和缺点

优点：

• 既能够限流，还能够平滑控制处理速度。

缺点：

• 需要对请求进行缓存，会增加服务器的内存消耗。
• 无法应对突然激增的流量，因为只能以固定的速率处理请求，对系统资源利用不够友好。
• 桶流入水（发请求）的速率如果一直大于桶流出水（处理请求）的速率的话，那么桶会一直是满的，一部分新的请求会被丢弃，导致服务质量下降。

令牌桶限流

基本原理

令牌桶算法以恒定的速率生成令牌并放入桶中，令牌数不会超过桶容量，当有请求到来时，会尝试申请一块令牌，如果没有令牌则会拒绝请求，有足够的令牌则会处理请求，并且减少桶内令牌数。如下图所示：

简单实现

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key 限流键*/public void doRateLimit(String key) {RRateLimiter rRateLimiter = redissonClient.getRateLimiter(key);// 设置令牌桶限流器的限流效果：如限流的类型、每个限流时间窗口内生成的令牌数量、速率的时间间隔和时间间隔的单位。rRateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS);// 尝试获取 1 个令牌boolean canOp = rRateLimiter.tryAcquire(1);if (!canOp) {// 获取令牌失败// 执行失败后的操作....}// 请求通过，继续处理业务逻辑}
}

优点和缺点

优点：

• 面对突发流量，可以在短时间内提供更多的处理能力，以处理突发流量。
• 与漏桶算法相比，令牌桶算法提供了更大的灵活性，可以动态调整生成令牌的速率。

缺点：

• 如果令牌产生速率和桶的容量设置不合理，可能会出现问题比如大量的请求被丢弃、系统过载。

算法比较与选择

固定窗口算法：业务简单，对突发流量要求不高的场景。

滑动窗口算法：需要精确控制请求速率，平滑限流时使用。

漏桶算法：适合对流量有严格平稳要求的场景，尤其是在处理突发请求能力有限、系统必须稳定输出流量的情况下。

令牌桶算法：对突发流量有要求，对稳定性和精度要求较高的场景。