深入了解常见的限流算法及其实现方式

限流是一种重要的系统设计技术，用于控制系统在一定时间内的请求数量，以保护系统免受过载的影响。下面我们将详细介绍常见的限流算法及其实现方式。

计数器限流(固定窗口) 计数器限流是最简单的一种限流算法，它将时间划分为多个固定大小的窗口，在每个窗口内对请求进行计数，如果某个窗口内的请求数超过了限流阈值，则后续的请求将被拒绝。

示例代码：

<code>// Java示例代码 public class FixedWindow { private static final int QPS = 2; // 限流阈值 private static final long TIME_WINDOWS = 1000; // 时间窗口大小（毫秒） private static final 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; } public static void main(String[] args) throws InterruptedException { for (int i = 0; i < 10; i++) { Thread.sleep(250); if (!tryAcquire()) { System.out.println("被限流"); } else { System.out.println("做点什么"); } } } }</code>

滑动窗口算法 滑动窗口算法是对固定窗口算法的改进，它将时间划分为多个小的时间段，并在每个时间段内对请求进行计数。随着时间的推移，窗口会向右滑动，丢弃最老的一个时间段，加入一个新的时间段，从而动态地调整窗口内的请求数。

示例代码：

<code>// Java示例代码 public class SlidingWindow { private final int qps; // 限流阈值 private final long windowSize; // 时间窗口总大小（毫秒） private final int windowCount; // 子窗口数量 private final WindowInfo[] windowArray; // 窗口列表 public SlidingWindow(int qps) { this.qps = qps; this.windowSize = 1000; this.windowCount = 10; this.windowArray = new WindowInfo[windowCount]; long currentTimeMillis = System.currentTimeMillis(); for (int i = 0; i < windowArray.length; i++) { windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0)); } } public synchronized boolean tryAcquire() { long currentTimeMillis = System.currentTimeMillis(); int currentIndex = (int) (currentTimeMillis % windowSize / (windowSize / windowCount)); int sum = 0; for (int i = 0; i < windowArray.length; i++) { WindowInfo windowInfo = windowArray[i]; if ((currentTimeMillis - windowInfo.getTime()) > windowSize) { windowInfo.getNumber().set(0); windowInfo.setTime(currentTimeMillis); } if (currentIndex == i && windowInfo.getNumber().get() < qps) { windowInfo.getNumber().incrementAndGet(); } sum += windowInfo.getNumber().get(); } return sum <= qps; } private static class WindowInfo { private Long time; private AtomicInteger number; public WindowInfo(long time, AtomicInteger number) { this.time = time; this.number = number; } } public static void main(String[] args) throws InterruptedException { SlidingWindow slidingWindow = new SlidingWindow(2); for (int i = 0; i < 10; i++) { Thread.sleep(250); if (!slidingWindow.tryAcquire()) { System.out.println("被限流"); } else { System.out.println("做点什么"); } } } }</code>

漏桶算法 漏桶算法是一种简单而有效的限流算法，它将请求看作是水流，系统处理能力看作是一个固定大小的漏桶。请求先进入漏桶，然后以恒定的速率从漏桶中流出，当漏桶已满时，后续的请求将被拒绝。

示例代码：

<code>// Java示例代码 public class LeakyBucket { private final int bucket; // 水桶大小 private final int qps; // 水流出速率 private long water; // 当前水量 private long timeStamp = System.currentTimeMillis(); public LeakyBucket(int bucket, int qps) { this.bucket = bucket; this.qps = qps; } public synchronized boolean tryAcquire() { long now = System.currentTimeMillis(); long timeGap = (now - timeStamp) / 1000; water = Math.max(0, water - timeGap * qps); timeStamp = now; if (water < bucket) { water++; return true; } return false; } public static void main(String[] args) throws InterruptedException { LeakyBucket leakyBucket = new LeakyBucket(20, 2); for (int i = 0; i < 10; i++) { Thread.sleep(250); if (!leakyBucket.tryAcquire()) { System.out.println("被限流"); } else { System.out.println("做点什么"); } } } }</code>

令牌桶算法 令牌桶算法是一种常用的限流算法，它维护一个令牌桶，以一个恒定的速率向桶中放入令牌。每个请求在被处理前需要先从令牌桶中获取一个令牌，如果桶中没有足够的令牌，则请求将被拒绝。

示例代码：

<code>// Java示例代码 public class TokenBucket { private final int capacity; // 桶的容量 private final int qps; // 每秒生成的令牌数 private int tokens; // 当前令牌数 private long lastRefillTime = System.currentTimeMillis(); public TokenBucket(int capacity, int qps) { this.capacity = capacity; this.qps = qps; this.tokens = capacity; } public synchronized boolean tryAcquire() { refill(); if (tokens > 0) { tokens--; return true; } return false; } private void refill() { long now = System.currentTimeMillis(); long timePassed = now - lastRefillTime; int newTokens = (int) (timePassed * qps / 1000); tokens = Math.min(capacity, tokens + newTokens); lastRefillTime = now; } public static void main(String[] args) throws InterruptedException { TokenBucket tokenBucket = new TokenBucket(20, 2); for (int i = 0; i < 10; i++) { Thread.sleep(250); if (!tokenBucket.tryAcquire()) { System.out.println("被限流"); } else { System.out.println("做点什么"); } } } }</code>

以上是常见的限流算法及其实现方式，不同的算法适用于不同的场景，可以根据实际情况选择合适的算法来保护系统的稳定性和可用性。