网站制作将栏目分类,wordpress 发邮件设置,长春火车站防疫要求,莱芜金点子信息港二手房大家好#xff0c;我是锋哥。今天分享关于【你了解哪些Java限流算法?】面试题。希望对大家有帮助#xff1b; 你了解哪些Java限流算法?
1000道 互联网大厂Java工程师 精选面试题-Java资源分享网
Java 中常用的限流算法主要有以下几种#xff0c;它们广泛应用于处理流量控…大家好我是锋哥。今天分享关于【你了解哪些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 LinkedListLong 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 等中间件进行限流会更有效。
