常用的限流算法
常用的限流策略
限流策略主要用来控制在高并发、大流量的场景中对服务接口请求的速率，例如双十一秒杀、抢购、抢票、抢单等场景。
假设某个接口能够接受的QPS为1K，这时候有1W个请求进来，经过限流模块，会先放1K个请求，其余的请求会阻塞一段时间。不简单粗暴的返回404，让客户端重试，同时又能起到流量削峰的作用。
限流算法可以有效地帮助系统控制请求流量，防止系统因为流量过大而崩溃。在高并发情况下，如果没有限流机制，系统可能会因为请求过多而导致响应速度变慢，甚至瘫痪。
此外限流算法还可以保证系统免受恶意攻击、恶意爬虫等不量行为的侵害，提高系统的安全性和稳定性。
如果要设计一套限流算法主要包括下面三个步骤：
- 流量统计：记录在特定时间段内通过的流量数，为后续的流量判断提供依据；
- 限流判断：判断当前流量是否可以正常通过；
- 流量控制：对于已经被限流的请求，需要进行特殊的处理；
固定窗口算法
固定窗口算法又叫计数器算法，是一种简单方便的限流算法。主要通过一个支持原子操作的计数器来累加1秒内的请求次数，当1秒内的请求次数达到限流阈值时触发拒绝策略。每过1秒，计数器重置为0开始重新计算。
固定窗口算法的核心思想是：将时间划分为固定的窗口，并在每个窗口维护一个计数器，统计请求次数。当计数器超过预设的阈值时，则拒绝后续请求，直到窗口重置。
如下所示为固定窗口算法的一个简单实现：
public class RateLimiterSimpleWindow{
// 阈值
private static Integer QPS = 2;
// 时间窗口（毫秒）
private static long TIME_WINDOWS = 1000;
// 计数器
private static AtomicInteger REQ_COUNT = new AtomicInteger();
// 上次请求的时间
private static long START_TIME = System.currentTimeMillis();
public synchronized static boolean tryAcquire(){
if(System.currentTimeMillis() - START_TIME > TIME_WINDOWS){
REQ_COUNT.set(0);
START_TIME = System.currentTimeMillis();
}
return REQ_COUNT.incrementAndGet() <= QPS;
}
}固定窗口算法的优缺点：
- 优点
- 实现简单：逻辑清晰，代码易于编写和维护；
- 内存效率高：只需要为每个活动的时间窗口存储一个计数器，通常只需要存储当前和上一个窗口的数据；
- 性能较好：对请求判断的时间复杂度是，非常快；
- 缺点
- 存在明显的流量突刺问题（临界问题）：固定窗口算法无法平滑地处理跨窗口边界的流量，在窗口切换的临界点，可能会承受两倍的流量冲击，保护效果不够平滑和精确；
滑动窗口算法
滑动窗口算法的核心思想是：将一个大的时间窗口拆分为多个连续的小时间片，随着时间流逝，窗口不是跳跃式地重置，而是像滑动一样平滑地移动。通过维护这些小时间片的计数，可以更精确地统计任意时刻的流量。
假设现在有一个需求是：每分钟最多允许100个请求，可以将1分钟划分为6个10秒的小时间片。
当一个请求在时间点T到达时：
- 计算T属于哪个时间片：
- 检查这个时间片是否属于当前窗口。如果不是（即时间片太旧，已经滑出窗口），则需要清空整个队列（或重置窗口），并开始一个新的滑动窗口周期；
- 获取当前时间片在队列中对应的计数的count；
- 如果所有时间片的计数总和小于阈值，则允许请求通过，并将这个时间片的计数count加1；
- 如果总和大于等于阈值，则拒绝请求；
滑动窗口算法的简单实现：
public class SlidingWindowRateLimit{
private final int limit; // 时间窗口内允许的最大请求数
private final long windowSizeInMillis; // 总的滑动窗口大小（毫秒）
private final long sliceSizeInMillis; // 每个时间片的大小（毫秒）
private final int sliceNum; // 小时间片的数量
private final Queue<long[]> timeSliceQueue;
public SlidingWindowRateLimit(int limit,long windowSizeInSeconds){
this.limit = limit;
this.windowSizeInMillis = windowSizeInSeconds * 1000;
this.sliceSizeInMillis = 1000;
this.sliceNum = (int) (this.windowSizeInMillis / this.sliceSizeInMills);
this.timeSliceQueue = new LinkedList<>();
}
public synchronized boolean tryAcquire(){
long now = System.currentTimeMillis();
long windowStart = now - this.windowSizeMillis;
// 1.清理队列中所有已经不在当前滑动窗口内的旧时间片
while(!timeSliceQueue.isEmpty() && timeSliceQueue.peek()[0] <= windowStart){
timeSliceQueue.poll();
}
// 2.计算窗口内请求数的总和
int currentTotalRequests = 0;
for(long[] slice:timeSliceQueue){
currentTotalRequests += slice[1];
}
// 3.判断是否允许请求
if(currentTotalRequests < limit){
// 允许请求
long currentSliceTime = (now/sliceSizeInMillis) * sliceSizeInMillis; // 计算当前时间片的起始时间；
if(!timeSliceQueue.isEmpty() && timeSliceQueue.peekLast()[0] == currentSliceTime){
// 如果队列最后一个元素就是当前时间片，则直接计数+1
timeSliceQueue.peekLast()[1]++;
}else{
// 否则创建一个新的时间片并加入队列
timeSliceQueue.offer(new long[]{currentSliceTime,1});
}
return true;
}else{
// 拒绝请求
return fasle;
}
}
}相对于固定窗口而言，滑动窗口在实现上，将时间区间进一步的细化，然后计算流量的方式以求和的方式来实现。
滑动窗口的优缺点：
- 优点
- 解决了临界问题：这是它相对于固定窗口最大的优点。通过对时间进行更精细的划分，流量控制变得平滑，不会在窗口边界出现流量洪峰。
- 精度可控：通过将大窗口拆分成更多、更小的时间片，可以无限逼近真实的流量曲线，精度远高于固定窗口；
- 缺点
- 实现复杂度高：逻辑比固定窗口复杂，需要维护一个队列或环形结构，并处理时间片的清理和更新；
- 内存占用相对较高：需要为每个时间片存储一个技术器。虽然比滑动日志算法好很多，但相比固定窗口，它仍然需要更多的内存；
- 性能开销大：每次请求都需要计算总量，虽然可以通过优化来减少计算量，但依然比固定窗口的查找要慢。
滑动日志算法
滑动日志算法的核心思想是：抛弃窗口的概念，不再对时间进行分片或聚合。它为每一个到来的请求都精确记录它发生的时间戳。让需要进行流量检查时，直接计算出当前时间点往前推一个时间窗口的总请求数，以此来判断是否允许新的请求。
滑动日志算法是滑动窗口算法的一种变式，因为在滑动窗口算法中无论是如何细分小的时间窗口，也仍然会在两个窗口之间出现临界问题。
改用滑动日志算法，每次请求到达的时候只需要根据时间窗口统计在对应的时间窗口内通过的请求的总数，来对流量进行判断。
public class SlidingRateLimiter{
private final long maxRequests; // 时间窗口内最大请求数
private final long windowSizeInMillis; // 时间窗口大小（毫秒）
private final LinkedList<Long> requestTimestamps; // 请求到达的时间戳列表
private final ReentrantLock lock;
public SlidingRateLimiter(long maxRequests,long windowSizeInMillis){
this.maxRequests = maxRequest;
this.windowSizeInMillis = windowSizeInMillis;
// 采用链表的方式在清理失效的时间戳时，可以从头节点快速遍历
this.requestTimestamps = new LinkedList<>();
this.lock = new ReentrantLock();
}
public boolean tryAcquire(){
return tryAcquire(1);
}
public boolean tryAcquire(int permits){
lock.lock();
try{
long currentTime = System.currentTimeMillis();
// 清除过期的时间戳
removeExpiredTimeStamps(currentTime);
if(requestTimeStamp.size() + permits <= maxRequests){
for(int i=0;i<permis;i++){
requestTimestamps.addLast(currentTime);
}
return true;
}
return false;
}finally{
lock.unlock();
}
}
public void removeExpiredTimestamps(long currentTime){
lont cutoffTime = currentTime - windowsSizeInMillis;
while(!requestTimestamps.isEmpty() && requestTimeStamps.getFirst() < cutoffTime){
requestTimestamps.removeFirst();
}
}
}滑动日志算法的优缺点
- 优点
- 高精度限流：记录每个请求确切的时间戳，可以精确到毫秒级；
- 无边界问题：避免了固定窗口算法的边界流量问题；
- 真是反映流量：准确统计任意时间窗口内的实际请求数；
- 平滑限流：请求在时间窗口被均匀分布，不会出现流量突刺；
- 统计准确性：提供准确的当前请求统，可以精确计算剩余可用请求数；
- 缺点
- 内存消耗大；
- 性能开销显著：每次请求都需要清理过期数据，需要同步机制来保证线程安全；
- GC的压力大：大量短生命周期对象增加垃圾回收负担；
漏桶算法
漏桶算法是一种流量整形和限流算法，它模拟了一个底部有恒定漏水速率的桶，无论流入的水多么的湍急，流出的速率始终保持恒定。
对于漏桶算法而言，它可以以均匀的速率消费请求。
public class LeakyBucketRateLimiter {
private final BlockingQueue<Object> bucket;
private final long capacity;
private final long leakRateNanos;
private final AtomicLong lastLeakTime;
private final Thread leakyWorker;
private volatile boolean running;
public LeakyBucketRateLimiter(long capacity, long leakRateNanos) {
this.capacity = capacity;
this.leakRateNanos = leakRateNanos;
this.bucket = new ArrayBlockingQueue<>(Math.toIntExact(capacity));
this.lastLeakTime = new AtomicLong(System.nanoTime());
// 启动漏水线程
this.leakyWorker = new Thread(this::leak);
this.leakyWorker.setDaemon(true);
this.leakyWorker.start();
}
private void leaky() {
while (running) {
try {
long now = System.nanoTime();
long elapsed = now - lastLeakTime.get();
// 计算出应该漏出的请求数量
long expectedLeaks = elapsed / leakRateNanos;
if (expectedLeaks > 0) {
for (long i = 0; i < expectedLeaks && !bucket.isEmpty(); i++) {
Object request = bucket.poll();
if (request != null) {
processRequest(request);
}
}
lastLeakTime.set(now - (elapsed % leakRateNanos));
Thread.sleep(Math.max(1, TimeUnit.NANOSECONDS.toMillis(leakRateNanos) / 10));
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
break;
} catch (Exception e) {
e.printStackTrace();
}
}
}
private void processRequest(Object request) {
System.out.println("处理请求：" + request);
}
public boolean tryAcquire(String requestId) {
if (!running) {
return false;
}
return bucket.offer(requestId);
}
}漏铜算法的优缺点
- 优点
- 输出速率恒定：将不规则的输入流转换为均匀的流，防止突发流量冲击后端系统，处理速率完全可控和可预测；
- 平滑突发流量：有效平滑短时间内的流量峰值，避免系统因突发流量而过载，为下游服务提供稳定的处理节奏；
- 实现相对简单：算法概念直观易懂，有多种实现方式可选，行为可预测便于问题排查
- 缺点：
- 无法应对短时间突发：一般而言系统对于到达的流量可能需要快速的处理完毕，所以它无法快速处理突发流量；
- 可能造成请求延迟：桶满的请求需要等待处理，用户感知到响应时间会变长，长时间等待会导致请求超时；
- 内存消耗：需要内存在存储排队的请求，大量待处理的请求占用系统资源；
令牌桶算法
令牌桶算法是一种非常流行的限流算法，它通过以恒定速率向桶中添加令牌，请求需要获取令牌才能被执行。
令牌桶算法的核心思想是：要以恒定的速率向桶中添加令牌，请求需要获取指令数量的令牌才能被处理。
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.LockSupport;
/**
* 基础令牌桶算法实现
* 使用原子操作保证线程安全和高性能
*/
public class TokenBucketRateLimiter {
private final int capacity; // 桶容量
private final int tokensPerSecond; // 每秒生成的令牌数
private final AtomicInteger availableTokens; // 可用令牌数
private final AtomicLong lastRefillTime; // 上次补充令牌时间
private final int refillIntervalMillis; // 补充令牌间隔（毫秒）
private final int tokensPerRefill; // 每次补充的令牌数
public TokenBucketRateLimiter(int capacity, int tokensPerSecond) {
this.capacity = capacity;
this.tokensPerSecond = tokensPerSecond;
// 计算补充参数
this.refillIntervalMillis = 100; // 固定100ms补充一次
this.tokensPerRefill = tokensPerSecond * refillIntervalMillis / 1000;
this.availableTokens = new AtomicInteger(0);
this.lastRefillTime = new AtomicLong(System.currentTimeMillis());
// 初始时填满桶
this.availableTokens.set(capacity);
}
/**
* 尝试获取一个令牌
* @return true: 获取成功, false: 获取失败
*/
public boolean tryAcquire() {
return tryAcquire(1);
}
/**
* 尝试获取多个令牌
* @param tokens 需要的令牌数量
* @return true: 获取成功, false: 获取失败
*/
public boolean tryAcquire(int tokens) {
if (tokens <= 0) {
return true;
}
if (tokens > capacity) {
return false; // 需要的令牌数超过桶容量
}
// 先补充令牌
refillTokens();
// 尝试消费令牌
int current;
do {
current = availableTokens.get();
if (current < tokens) {
return false; // 令牌不足
}
} while (!availableTokens.compareAndSet(current, current - tokens));
return true;
}
/**
* 阻塞方式获取令牌
* @param tokens 需要的令牌数量
* @param timeoutMillis 超时时间（毫秒）
* @return true: 获取成功, false: 超时
*/
public boolean acquire(int tokens, long timeoutMillis) throws InterruptedException {
long startTime = System.currentTimeMillis();
while (true) {
if (tryAcquire(tokens)) {
return true;
}
if (System.currentTimeMillis() - startTime >= timeoutMillis) {
return false; // 超时
}
// 计算等待时间，避免过度轮询
long waitTime = Math.min(10, timeoutMillis -
(System.currentTimeMillis() - startTime));
LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(waitTime));
if (Thread.currentThread().isInterrupted()) {
throw new InterruptedException();
}
}
}
/**
* 补充令牌
*/
private void refillTokens() {
long now = System.currentTimeMillis();
long lastTime = lastRefillTime.get();
long elapsed = now - lastTime;
if (elapsed < refillIntervalMillis) {
return; // 未到补充时间
}
// 计算应该补充的令牌数量
long refills = elapsed / refillIntervalMillis;
int newTokens = (int) (refills * tokensPerRefill);
if (newTokens > 0) {
int current;
int updated;
do {
current = availableTokens.get();
updated = Math.min(capacity, current + newTokens);
} while (!availableTokens.compareAndSet(current, updated));
// 更新最后补充时间（保留余数）
lastRefillTime.set(lastTime + refills * refillIntervalMillis);
}
}
/**
* 获取当前可用令牌数
*/
public int getAvailableTokens() {
refillTokens();
return availableTokens.get();
}
/**
* 获取桶容量
*/
public int getCapacity() {
return capacity;
}
/**
* 重置令牌桶
*/
public void reset() {
availableTokens.set(capacity);
lastRefillTime.set(System.currentTimeMillis());
}
}