滑动窗口

滑动窗口原理 为什么需要滑动窗口？ 固定窗口的临界问题： 时间： 0s 0.5s 1s 1.5s 2s |---窗口1---|---窗口2---| 请求： 999个 1个 999个 窗口1：999 < 1000 ✅ 窗口2：999 < 1000 ✅ 实际：0.5s内1998个请求 ❌ 滑动窗口解决方案： 时间： 0s 1s 2s |----窗口-----| | 分成10个格子 | 每个格子：100ms 统计QPS：滑动统计最近1秒的请求 LeapArray实现 核心数据结构 public abstract class LeapArray<T> { protected int windowLengthInMs; // 每个窗口时长 protected int sampleCount; // 窗口数量 protected int intervalInMs; // 总时长 protected final AtomicReferenceArray<WindowWrap<T>> array; public LeapArray(int sampleCount, int intervalInMs) { this.sampleCount = sampleCount; this.intervalInMs = intervalInMs; this.windowLengthInMs = intervalInMs / sampleCount; this.array = new AtomicReferenceArray<>(sampleCount); } } WindowWrap（窗口包装） public class WindowWrap<T> { private final long windowLengthInMs; // 窗口时长 private long windowStart; // 窗口开始时间 private T value; // 统计数据 public WindowWrap(long windowLengthInMs, long windowStart, T value) { this.windowLengthInMs = windowLengthInMs; this.windowStart = windowStart; this.value = value; } public boolean isTimeInWindow(long timeMillis) { return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs; } } MetricBucket（统计桶） public class MetricBucket { private final LongAdder[] counters; // 各项指标计数器 private volatile long minRt; // 最小RT public MetricBucket() { MetricEvent[] events = MetricEvent.values(); this.counters = new LongAdder[events.length]; for (MetricEvent event : events) { counters[event.ordinal()] = new LongAdder(); } initMinRt(); } public long get(MetricEvent event) { return counters[event.ordinal()].sum(); } public void add(MetricEvent event, long n) { counters[event.ordinal()].add(n); } } enum MetricEvent { PASS, // 通过 BLOCK, // 阻塞 EXCEPTION, // 异常 SUCCESS, // 成功 RT, // 响应时间 OCCUPIED_PASS // 占用通过 } 窗口获取算法 public WindowWrap<T> currentWindow(long timeMillis) { if (timeMillis < 0) { return null; } int idx = calculateTimeIdx(timeMillis); long windowStart = calculateWindowStart(timeMillis); while (true) { WindowWrap<T> old = array.get(idx); if (old == null) { // 窗口不存在，创建新窗口 WindowWrap<T> window = new WindowWrap<>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); if (array.compareAndSet(idx, null, window)) { return window; } else { Thread.yield(); } } else if (windowStart == old.windowStart()) { // 窗口存在且有效 return old; } else if (windowStart > old.windowStart()) { // 窗口过期，重置窗口 if (updateLock.tryLock()) { try { return resetWindowTo(old, windowStart); } finally { updateLock.unlock(); } } else { Thread.yield(); } } else if (windowStart < old.windowStart()) { // 时钟回拨 return new WindowWrap<>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); } } } // 计算窗口索引 private int calculateTimeIdx(long timeMillis) { long timeId = timeMillis / windowLengthInMs; return (int) (timeId % array.length()); } // 计算窗口开始时间 private long calculateWindowStart(long timeMillis) { return timeMillis - timeMillis % windowLengthInMs; } QPS计算 public double getQps() { long pass = 0; List<MetricBucket> list = listAll(); for (MetricBucket window : list) { pass += window.pass(); } return pass / intervalInSec(); } public List<MetricBucket> listAll() { List<MetricBucket> result = new ArrayList<>(); long currentTime = TimeUtil.currentTimeMillis(); for (int i = 0; i < array.length(); i++) { WindowWrap<MetricBucket> windowWrap = array.get(i); if (windowWrap == null || isWindowDeprecated(currentTime, windowWrap)) { continue; } result.add(windowWrap.value()); } return result; } 实战示例 统计QPS public class MetricDemo { public static void main(String[] args) throws InterruptedException { // 创建滑动窗口：2个窗口，1秒总时长 ArrayMetric metric = new ArrayMetric(2, 1000); // 模拟请求 for (int i = 0; i < 100; i++) { metric.addPass(1); Thread.sleep(10); } // 统计QPS System.out.println("QPS: " + metric.pass()); System.out.println("Success: " + metric.success()); System.out.println("AvgRT: " + metric.avgRt()); } } 自定义统计 public class CustomMetric extends LeapArray<MetricBucket> { public CustomMetric(int sampleCount, int intervalInMs) { super(sampleCount, intervalInMs); } @Override public MetricBucket newEmptyBucket(long timeMillis) { return new MetricBucket(); } @Override protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long startTime) { w.resetTo(startTime); w.value().reset(); return w; } // 自定义统计方法 public void addCustomEvent(String event, long value) { WindowWrap<MetricBucket> wrap = currentWindow(); wrap.value().add(event, value); } } 性能优化 1. LongAdder替代AtomicLong // 高并发下性能更好 private final LongAdder counter = new LongAdder(); public void increment() { counter.increment(); } public long sum() { return counter.sum(); } 2. 数组环形复用 // 使用固定大小数组，避免GC private final AtomicReferenceArray<WindowWrap<T>> array; // 环形索引 private int idx = (int) (timeId % array.length()); 3. CAS无锁更新 // 使用CAS避免锁竞争 if (array.compareAndSet(idx, null, window)) { return window; } 时间对齐问题 // 问题：时间戳100ms对齐 long timeMillis = 12345; // 实际时间 long windowStart = timeMillis - timeMillis % 100; // 对齐到100ms // 结果 12345 → 12300 12399 → 12300 12400 → 12400 总结 滑动窗口核心： ...

引言 在前面的文章中，我们学习了TCP如何建立连接（三次握手）和断开连接（四次挥手）。今天我们来学习TCP如何在连接建立后高效可靠地传输数据：流量控制机制（Flow Control）。 为什么需要流量控制？ 发送方可能发送得很快，接收方可能处理得很慢 如果发送方不控制速度，接收方的缓冲区会溢出，数据丢失 流量控制让接收方告诉发送方：我能接收多少数据 今天我们来理解： ✅ 滑动窗口（Sliding Window）的工作原理 ✅ 接收窗口（rwnd）和发送窗口的关系 ✅ 零窗口问题与窗口探测 ✅ 如何调整TCP窗口大小以提升性能 第一性原理：为什么需要流量控制？ 问题：接收方处理不过来 场景：文件传输 发送方（高性能服务器） 接收方（低性能客户端） | | | 发送1GB数据，速度1Gbps | 接收速度只有100Mbps |----------------------------> | 接收缓冲区64KB | | | 继续疯狂发送... | 缓冲区满了！ |----------------------------> | ❌ 数据丢失 | | 不同场景的速度差异： 场景 发送方 接收方 问题 服务器 → 客户端 10Gbps网卡 100Mbps网卡 速度差100倍 内存 → 磁盘 内存写入50GB/s 磁盘写入500MB/s 速度差100倍 批量导入 10万条/秒 DB只能处理1万条/秒 处理能力差10倍 流量控制的目标：让发送方的速度匹配接收方的处理能力 滑动窗口：TCP流量控制的核心机制 核心思想 接收方告诉发送方：“我还有X字节的缓冲空间，你最多发送X字节” 接收方 发送方 | | | TCP头部：Window=8192 | |<-------------------------| | | 含义： "我的接收缓冲区还有8192字节空间， 你最多发送8192字节" 接收窗口（rwnd） 接收窗口（Receive Window）：接收方在TCP头部的Window字段通告给发送方的值 ...

核心观点: 限流算法不是单纯的技术选择，而是业务需求与技术约束的权衡。本文从一个真实需求的演进过程出发，深度剖析5种限流算法的设计思路、实现细节和适用场景。 引子：一个API接口的限流需求演进 需求背景 你是某电商平台的后端工程师，负责维护商品查询接口 /api/products/{id}。 初始状态（无限流）: @RestController public class ProductController { @Autowired private ProductService productService; @GetMapping("/api/products/{id}") public Result getProduct(@PathVariable Long id) { Product product = productService.getById(id); return Result.success(product); } } 系统运行良好，日常流量500 QPS，数据库和服务器完全可以承受。 第一次危机：流量突增 某天，运营部门做了一个促销活动，流量突然涨到5000 QPS（10倍）。 后果: 10:00:00 - 活动开始，流量5000 QPS 10:00:30 - 数据库连接池耗尽（最大连接数100） 10:01:00 - 响应时间从50ms暴增到5秒 10:01:30 - 服务器CPU 100%，系统崩溃 CTO找你谈话: “给这个接口加个限流，最多支持1000 QPS。” 你的第一反应：计数器！ 需求演进1：固定窗口计数器 需求: 每秒最多1000个请求。 你快速实现了一个固定窗口计数器： public class FixedWindowRateLimiter { private final int maxRequests; private final AtomicInteger counter = new AtomicInteger(0); private volatile long windowStart = System.currentTimeMillis(); public FixedWindowRateLimiter(int maxRequests) { this.maxRequests = maxRequests; } public boolean tryAcquire() { long now = System.currentTimeMillis(); // 新窗口，重置计数器 if (now - windowStart >= 1000) { synchronized (this) { if (now - windowStart >= 1000) { counter.set(0); windowStart = now; } } } // 当前窗口未超限 return counter.incrementAndGet() <= maxRequests; } } 部署上线，问题解决！系统稳定运行。 ...

限流算法对比 算法 实现难度 精确度 内存占用 适用场景 固定窗口 简单 低 低 粗粒度限流 滑动窗口 中等 高 中 精确限流 漏桶 中等 高 中 流量整形 令牌桶 复杂 高 中 允许突发 1. 固定窗口算法 原理：时间窗口内计数，超过限制则拒绝 @Service public class FixedWindowRateLimiter { @Autowired private RedisTemplate<String, String> redis; // 限流检查 public boolean isAllowed(String key, int limit, int windowSeconds) { String counterKey = key + ":" + (System.currentTimeMillis() / 1000 / windowSeconds); Long current = redis.opsForValue().increment(counterKey); if (current == 1) { redis.expire(counterKey, windowSeconds, TimeUnit.SECONDS); } return current != null && current <= limit; } } // 使用示例 public boolean checkLimit(String userId) { return rateLimiter.isAllowed("api:user:" + userId, 100, 60); // 每分钟100次 } 问题：临界问题 ...

引言：算法决定限流的精度 前面我们学会了使用Sentinel进行限流，只需要一行配置： rule.setCount(100); // 每秒最多100次 但你有没有想过：Sentinel是如何精确控制每秒100次的？ 如果100个请求在1秒的前0.01秒就全部到达，后面0.99秒怎么办？ 如果1秒内有120个请求，是拒绝哪20个？前面的？后面的？ 如果平时QPS是50，突然来了200的瞬间峰值，能否允许？ 这些问题的答案，都隐藏在限流算法中。今天我们将深入理解4种经典限流算法，看看它们各自的特点和适用场景。 一、固定窗口计数器：最简单的限流算法 1.1 算法原理 固定窗口计数器是最直观的限流算法： 时间窗口：每秒钟 限流阈值：100次 秒钟： 0 1 2 3 4 │─────│─────│─────│─────│─────│ 计数： 0→100 0→50 0→120 0→80 0→100 结果： 全通过 全通过 拒20 全通过 全通过 工作流程： 将时间划分为固定窗口（如1秒） 每个窗口维护一个计数器 请求到达时，计数器+1 如果计数器超过阈值，拒绝请求 窗口结束时，计数器归零 1.2 代码实现 public class FixedWindowRateLimiter { private final int limit; // 限流阈值 private final long windowSize; // 窗口大小（毫秒） private AtomicInteger counter; // 当前窗口计数 private long windowStartTime; // 窗口开始时间 public FixedWindowRateLimiter(int limit, long windowSize) { this.limit = limit; this.windowSize = windowSize; this.counter = new AtomicInteger(0); this.windowStartTime = System.currentTimeMillis(); } public synchronized boolean tryAcquire() { long now = System.currentTimeMillis(); // 判断是否需要重置窗口 if (now - windowStartTime >= windowSize) { // 新窗口开始 counter.set(0); windowStartTime = now; } // 判断是否超过限流阈值 if (counter.get() < limit) { counter.incrementAndGet(); return true; // 通过 } else { return false; // 限流 } } } 使用示例： ...