【java】常见限流算法原理及应用
目录
前言
在现代分布式系统和高并发场景下，限流已成为保障系统稳定性和可用性的重要手段。随着互联网应用规模的不断扩大，系统经常会面对海量请求和突发流量，如何有效控制和管理这些请求流量成为一项关键挑战。限流算法作为流量控制的重要工具，能够帮助系统平衡资源分配、抵御恶意攻击，并在高峰期维持服务的连续性与可靠性。本文将深入探讨几种常见的限流算法及其应用场景，帮助读者更好地理解限流机制的工作原理与优化策略。
限流的作用
限流的作用在于防止系统过载、保障服务的可用性、优化资源利用、平滑高峰流量，并确保服务质量和用户体验。通过控制请求的频率，限流机制能够在高并发或突发流量的情况下保护系统资源，提升其整体性能和响应能力，从而避免系统崩溃或服务中断。
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 {
@Resource
RedissonClient 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 {
@Resource
RedissonClient 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:";
@Resource
RedissonClient 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 {
@Resource
RedissonClient 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) {
// 获取令牌失败
// 执行失败后的操作....
}
// 请求通过，继续处理业务逻辑
}
}优点和缺点
优点：
- 面对突发流量，可以在短时间内提供更多的处理能力，以处理突发流量。
- 与漏桶算法相比，令牌桶算法提供了更大的灵活性，可以动态调整生成令牌的速率。
缺点：
- 如果令牌产生速率和桶的容量设置不合理，可能会出现问题比如大量的请求被丢弃、系统过载。
算法比较与选择
固定窗口算法：业务简单，对突发流量要求不高的场景。
滑动窗口算法：需要精确控制请求速率，平滑限流时使用。
漏桶算法：适合对流量有严格平稳要求的场景，尤其是在处理突发请求能力有限、系统必须稳定输出流量的情况下。
令牌桶算法：对突发流量有要求，对稳定性和精度要求较高的场景。
原文地址：https://blog.csdn.net/qq_62095670/article/details/142336487
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！