你了解哪些Java限流算法?

大家好，我是锋哥。今天分享关于【你了解哪些Java限流算法?】面试题。希望对大家有帮助；

你了解哪些Java限流算法?

1000道 互联网大厂Java工程师 精选面试题-Java资源分享网

Java 中常用的限流算法主要有以下几种，它们广泛应用于处理流量控制、API请求限制等场景：

1. 令牌桶算法（Token Bucket）

令牌桶算法是限流中最常用的一种方法。其基本思想是：

• 系统按固定速率向桶中放入令牌，每次请求需要消耗一个令牌。
• 如果桶中没有足够的令牌，请求会被拒绝或者被延迟处理。
• 如果令牌桶的容量大于实际请求速率，系统允许突发流量（超过速率的流量）。

特点：

• 支持突发流量。
• 限制速率比较平滑，可以动态调整。

实现方式：

• 使用一个线程定时向桶中放入令牌。
• 请求到达时，检查令牌桶是否有令牌。

public class TokenBucket {private final long capacity;private final long refillInterval;private long availableTokens;private long lastRefillTime;public TokenBucket(long capacity, long refillInterval) {this.capacity = capacity;this.refillInterval = refillInterval;this.availableTokens = capacity;this.lastRefillTime = System.currentTimeMillis();}public synchronized boolean acquire() {long now = System.currentTimeMillis();long elapsedTime = now - lastRefillTime;long tokensToAdd = elapsedTime / refillInterval;availableTokens = Math.min(capacity, availableTokens + tokensToAdd);lastRefillTime = now;if (availableTokens > 0) {availableTokens--;return true;}return false;}
}

2. 漏斗算法（Leaky Bucket）

漏斗算法通过一个固定容量的桶来控制请求速率。桶中有一定的容量，固定的速率会“漏掉”桶中的水，水（请求）按一定速率流出。

特点：

• 控制流量的输出速率平稳。
• 不允许突发流量，所有流量都按固定速率流出。

实现方式：

• 每次请求到来时，检查桶中的水量（请求数），如果桶已经满了，就拒绝请求。
• 否则允许请求进入桶，按固定速率流出。

public class LeakyBucket {private final long capacity;private final long leakRate;private long waterLevel;private long lastLeakTime;public LeakyBucket(long capacity, long leakRate) {this.capacity = capacity;this.leakRate = leakRate;this.waterLevel = 0;this.lastLeakTime = System.currentTimeMillis();}public synchronized boolean acquire() {long now = System.currentTimeMillis();long elapsedTime = now - lastLeakTime;long leakedWater = elapsedTime / leakRate;waterLevel = Math.max(0, waterLevel - leakedWater);lastLeakTime = now;if (waterLevel < capacity) {waterLevel++;return true;}return false;}
}

3. 计数窗口算法（Fixed Window Counter）

计数窗口算法是最简单的一种限流算法，它将时间划分为多个固定的时间窗口，每个时间窗口内可以接受一定数量的请求。

特点：

• 简单易理解。
• 容易受到“窗口切分”的影响，可能会在窗口的边界出现突发流量。

实现方式：

• 每个窗口内计数器限制请求次数。
• 请求到来时，检查当前时间窗口是否超过了限制。

public class FixedWindowCounter {private final int limit;private int count;private long lastWindowStartTime;public FixedWindowCounter(int limit) {this.limit = limit;this.count = 0;this.lastWindowStartTime = System.currentTimeMillis();}public synchronized boolean acquire() {long currentTime = System.currentTimeMillis();if (currentTime - lastWindowStartTime >= 1000) { // New windowcount = 0;lastWindowStartTime = currentTime;}if (count < limit) {count++;return true;}return false;}
}

4. 滑动窗口算法（Sliding Window Log）

滑动窗口算法是对固定窗口的改进，避免了固定窗口中产生的突发流量问题。它通过记录每个请求的时间戳，然后根据时间戳来判断请求是否超出了时间窗口。

特点：

• 较为精确地控制请求数量，避免了固定窗口的突发流量问题。
• 实现相对复杂。

实现方式：

• 使用队列记录每个请求的时间戳，当新请求到来时，去除过期的时间戳并检查当前窗口内的请求数量。

import java.util.LinkedList;public class SlidingWindowLog {private final int limit;private final long windowSize;private LinkedList<Long> requests;public SlidingWindowLog(int limit, long windowSize) {this.limit = limit;this.windowSize = windowSize;this.requests = new LinkedList<>();}public synchronized boolean acquire() {long currentTime = System.currentTimeMillis();while (!requests.isEmpty() && currentTime - requests.peekFirst() >= windowSize) {requests.pollFirst();}if (requests.size() < limit) {requests.addLast(currentTime);return true;}return false;}
}

5. Redis限流

使用 Redis 进行限流是分布式环境中常见的一种做法，主要使用 Redis 的 INCR 和 EXPIRE 命令来实现。

特点：

• 适用于分布式系统。
• 可扩展性强。

实现方式：

• 使用 Redis 存储请求计数，设置过期时间。
• 请求时进行计数和判断。

public class RedisRateLimiter {private final String redisKey;private final int limit;private final long period;private final Jedis jedis;public RedisRateLimiter(String redisKey, int limit, long period, Jedis jedis) {this.redisKey = redisKey;this.limit = limit;this.period = period;this.jedis = jedis;}public boolean acquire() {long currentTime = System.currentTimeMillis() / 1000;String key = redisKey + ":" + currentTime;Long count = jedis.incr(key);if (count == 1) {jedis.expire(key, (int) period);}return count <= limit;}
}

6. 漏桶 + 令牌桶混合

某些场景中，结合漏桶算法和令牌桶算法可以平衡处理流量控制。

特点：

• 结合两种算法的优点，既支持突发流量，又能够平稳流量。

---

这些限流算法各有优缺点，适用于不同的场景。令牌桶算法通常用于需要支持突发流量的场景，漏桶算法适用于对流量的平滑控制，而计数窗口和滑动窗口算法适合于较为简单的应用场景。对于分布式应用，使用 Redis 等中间件进行限流会更有效。