滑动窗口限流算法

1. 算法概述

滑动窗口限流算法是一种常用的限流策略，它通过维护一个时间窗口来控制请求的频率。与固定窗口算法相比，滑动窗口算法能够更平滑地处理请求，避免了窗口边界的突发流量问题。

2. 核心原理

2.1 基本思想

滑动窗口算法的核心思想是：

• 维护一个固定大小的时间窗口
• 窗口随着时间的推移而滑动
• 统计当前窗口内的请求数量
• 当请求数量超过阈值时，拒绝新的请求

2.2 工作机制

1. 时间窗口：定义一个固定时间长度的窗口（如1分钟）
2. 请求记录：记录每个请求的时间戳
3. 窗口滑动：随着时间推移，窗口向前滑动
4. 计数统计：统计当前窗口内的有效请求数
5. 限流判断：比较当前请求数与限制阈值

3. 算法实现

3.1 Java实现示例

import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class SlidingWindowRateLimiter {
    private final int maxRequests; // 最大请求数
    private final long windowSizeMs; // 窗口大小（毫秒）
    private final ConcurrentLinkedQueue<Long> requestTimes; // 请求时间队列
    
    public SlidingWindowRateLimiter(int maxRequests, long windowSizeMs) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.requestTimes = new ConcurrentLinkedQueue<>();
    }
    
    public synchronized boolean allowRequest() {
        long currentTime = System.currentTimeMillis();
        
        // 清理过期的请求记录
        cleanExpiredRequests(currentTime);
        
        // 检查是否超过限制
        if (requestTimes.size() >= maxRequests) {
            return false;
        }
        
        // 记录当前请求
        requestTimes.offer(currentTime);
        return true;
    }
    
    private void cleanExpiredRequests(long currentTime) {
        while (!requestTimes.isEmpty()) {
            Long oldestRequest = requestTimes.peek();
            if (currentTime - oldestRequest > windowSizeMs) {
                requestTimes.poll();
            } else {
                break;
            }
        }
    }
    
    public int getCurrentRequestCount() {
        cleanExpiredRequests(System.currentTimeMillis());
        return requestTimes.size();
    }
}

3.2 使用示例

public class RateLimiterExample {
    public static void main(String[] args) throws InterruptedException {
        // 创建限流器：1秒内最多5个请求
        SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(5, 1000);
        
        // 模拟请求
        for (int i = 0; i < 10; i++) {
            boolean allowed = limiter.allowRequest();
            System.out.println("请求 " + (i + 1) + ": " + 
                (allowed ? "通过" : "被限流") + 
                ", 当前窗口请求数: " + limiter.getCurrentRequestCount());
            
            Thread.sleep(200); // 间隔200ms
        }
    }
}

4. 算法优化

4.1 分段滑动窗口

为了提高性能，可以将窗口分成多个小段：

public class SegmentedSlidingWindow {
    private final int maxRequests;
    private final long windowSizeMs;
    private final int segments;
    private final long segmentSizeMs;
    private final AtomicInteger[] counters;
    private volatile long lastUpdateTime;
    
    public SegmentedSlidingWindow(int maxRequests, long windowSizeMs, int segments) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.segments = segments;
        this.segmentSizeMs = windowSizeMs / segments;
        this.counters = new AtomicInteger[segments];
        this.lastUpdateTime = System.currentTimeMillis();
        
        for (int i = 0; i < segments; i++) {
            counters[i] = new AtomicInteger(0);
        }
    }
    
    public synchronized boolean allowRequest() {
        long currentTime = System.currentTimeMillis();
        updateCounters(currentTime);
        
        int totalRequests = getTotalRequests();
        if (totalRequests >= maxRequests) {
            return false;
        }
        
        int currentSegment = (int) ((currentTime / segmentSizeMs) % segments);
        counters[currentSegment].incrementAndGet();
        return true;
    }
    
    private void updateCounters(long currentTime) {
        long timeDiff = currentTime - lastUpdateTime;
        if (timeDiff >= segmentSizeMs) {
            int segmentsToReset = (int) Math.min(timeDiff / segmentSizeMs, segments);
            int startSegment = (int) ((lastUpdateTime / segmentSizeMs + 1) % segments);
            
            for (int i = 0; i < segmentsToReset; i++) {
                int segmentIndex = (startSegment + i) % segments;
                counters[segmentIndex].set(0);
            }
            
            lastUpdateTime = currentTime;
        }
    }
    
    private int getTotalRequests() {
        int total = 0;
        for (AtomicInteger counter : counters) {
            total += counter.get();
        }
        return total;
    }
}

5. 算法特点

5.1 优点

1. 平滑限流：避免了固定窗口的边界突发问题
2. 精确控制：能够精确控制时间窗口内的请求数量
3. 实时性好：能够实时响应流量变化
4. 内存可控：通过合理设计可以控制内存使用

5.2 缺点

1. 内存开销：需要存储请求时间戳信息
2. 计算复杂度：每次请求都需要清理过期数据
3. 并发处理：需要考虑线程安全问题

6. 应用场景

6.1 API限流

@RestController
public class ApiController {
    private final SlidingWindowRateLimiter rateLimiter = 
        new SlidingWindowRateLimiter(100, 60000); // 1分钟100次
    
    @GetMapping("/api/data")
    public ResponseEntity<?> getData() {
        if (!rateLimiter.allowRequest()) {
            return ResponseEntity.status(429)
                .body("请求过于频繁，请稍后再试");
        }
        
        // 处理正常请求
        return ResponseEntity.ok("数据内容");
    }
}

6.2 用户行为限制

public class UserActionLimiter {
    private final Map<String, SlidingWindowRateLimiter> userLimiters = 
        new ConcurrentHashMap<>();
    
    public boolean checkUserAction(String userId, String action) {
        String key = userId + ":" + action;
        SlidingWindowRateLimiter limiter = userLimiters.computeIfAbsent(key, 
            k -> new SlidingWindowRateLimiter(10, 60000)); // 1分钟10次
        
        return limiter.allowRequest();
    }
}

7. 性能优化建议

7.1 数据结构选择

• 使用环形缓冲区替代队列
• 采用位图或布隆过滤器减少内存占用
• 使用时间轮算法优化时间复杂度

7.2 并发优化

• 使用无锁数据结构
• 分段锁减少竞争
• 异步清理过期数据

7.3 内存管理

• 定期清理过期数据
• 设置最大内存限制
• 使用对象池减少GC压力

8. 总结

滑动窗口限流算法是一种高效的流量控制方案，它在保证限流精度的同时，提供了良好的用户体验。在实际应用中，需要根据具体场景选择合适的实现方式，并注意性能优化和资源管理。

通过合理的参数配置和优化策略，滑动窗口算法能够很好地应对各种流量控制需求，是现代分布式系统中不可或缺的重要组件。