六种限流算法与原理详解
原创六种限流算法与原理详解
原创
写bug的高哈哈
发布于 2024-11-02 08:49:29
发布于 2024-11-02 08:49:29
1. 固定窗口算法
固定窗口算法
- 原理：固定窗口算法通过在单位时间内维护一个计数器，限制在每个固定的时间段内请求通过的次数，以达到限流的效果。
- 优点：算法实现简单，容易理解。
- 缺点：不能应对突发流量，可能导致短时间内流量激增，从而影响服务稳定性。
public class FixedWindowRateLimiter {
private long windowSize; // 时间窗口大小，单位毫秒
private int maxRequestCount; // 允许通过请求数
private AtomicInteger count = new AtomicInteger(0); // 当前窗口通过的请求计数
private long windowBorder; // 窗口右边界
public FixedWindowRateLimiter(long windowSize, int maxRequestCount) {
this.windowSize = windowSize;
this.maxRequestCount = maxRequestCount;
windowBorder = System.currentTimeMillis() + windowSize;
}
public synchronized boolean tryAcquire() {
long currentTime = System.currentTimeMillis();
if (windowBorder < currentTime) {
windowBorder += windowSize;
count.set(0);
}
if (count.intValue() < maxRequestCount) {
count.incrementAndGet();
return true;
} else {
return false;
}
}
}2. 滑动窗口算法
滑动窗口算法
- 原理：滑动窗口算法在固定窗口的基础上进行了改进，将时间窗口划分为多个小块，每个小块维护独立的计数器，每次滑动时，减去前一个时间块内的请求数量，并添加一个新的时间块到末尾。
- 优点：流量控制更精细，能够更平滑地处理请求。
- 缺点：需要额外的存储空间来维护每一块时间内的计数器，实现相对复杂。
public class SlidingWindowRateLimiter {
private long windowSize; // 时间窗口大小，单位毫秒
private int shardNum; // 分片窗口数
private int maxRequestCount; // 允许通过请求数
private int[] shardRequestCount; // 各个窗口内请求计数
private int totalCount; // 请求总数
private int shardId; // 当前窗口下标
private long tinyWindowSize; // 每个小窗口大小，毫秒
private long windowBorder; // 窗口右边界
public SlidingWindowRateLimiter(long windowSize, int shardNum, int maxRequestCount) {
this.windowSize = windowSize;
this.shardNum = shardNum;
this.maxRequestCount = maxRequestCount;
shardRequestCount = new int[shardNum];
tinyWindowSize = windowSize / shardNum;
windowBorder = System.currentTimeMillis();
}
public synchronized boolean tryAcquire() {
long currentTime = System.currentTimeMillis();
if (currentTime > windowBorder) {
do {
shardId = (++shardId) % shardNum;
totalCount -= shardRequestCount[shardId];
shardRequestCount[shardId] = 0;
windowBorder += tinyWindowSize;
} while (windowBorder < currentTime);
}
if (totalCount < maxRequestCount) {
shardRequestCount[shardId]++;
totalCount++;
return true;
} else {
return false;
}
}
}3. 漏桶算法
漏桶算法
- 原理：漏桶算法通过以固定速率出水，将外部请求比作水，不断注入水桶中，如果水超过桶的最大容量则被丢弃，以此来控制数据的传输速率。
- 优点：能够有效地控制数据的传输速率，平滑处理请求。
- 缺点：不管系统负载如何，所有请求都得排队，可能导致系统资源的浪费。
public class LeakyBucketRateLimiter {
private int capacity; // 桶的容量
private AtomicInteger water = new AtomicInteger(0); // 桶中现存水量
private long leakTimeStamp; // 开始漏水时间
private int leakRate; // 水流出的速率，即每秒允许通过的请求数
public LeakyBucketRateLimiter(int capacity, int leakRate) {
this.capacity = capacity;
this.leakRate = leakRate;
}
public synchronized boolean tryAcquire() {
if (water.get() == 0) {
leakTimeStamp = System.currentTimeMillis();
water.incrementAndGet();
return water.get() < capacity;
}
long currentTime = System.currentTimeMillis();
int leakedWater = (int)((currentTime - leakTimeStamp) / 1000 * leakRate);
if (leakedWater != 0) {
int leftWater = water.get() - leakedWater;
water.set(Math.max(0, leftWater));
leakTimeStamp = System.currentTimeMillis();
}
if (water.get() < capacity) {
water.incrementAndGet();
return true;
} else {
return false;
}
}
}4. 令牌桶算法
令牌桶算法
- 原理：令牌桶算法通过系统以恒定的速度生成令牌，并将令牌放入令牌桶中，请求必须从令牌桶中获取一个令牌才能被处理，如果桶中没有令牌，则请求被限流。
- 优点：允许一定程度的突发请求，能够限制服务调用的平均速率，同时允许一定程度的突发调用。
- 缺点：无明显缺点，是较为理想的限流算法。
RateLimiter rateLimiter = RateLimiter.create(5);
for (int i = 0; i < 10; i++) {
double time = rateLimiter.acquire();
System.out.println("等待时间：" + time + "s");
}5. 中间件限流
- 工具：Sentinel
- 原理：Sentinel 是 Spring Cloud Alibaba 中的熔断限流组件，通过在服务层的方法上添加注解来实现限流。
- 优点：适用于分布式、微服务架构，提供开箱即用的限流方法。
- 缺点：需要引入额外的组件。
@Service
public class QueryService {
public static final String KEY = "query";
@SentinelResource(value = KEY, blockHandler = "blockHandlerMethod")
public String query(String name) {
return "begin query, name=" + name;
}
public String blockHandlerMethod(String name, BlockException e) {
e.printStackTrace();
return "blockHandlerMethod for Query : " + name;
}
}6. 网关限流
- 工具：Spring Cloud Gateway
- 原理：通过配置网关规则，使用 Redis 加 Lua 脚本的方式实现令牌桶算法进行限流。
- 优点：可以灵活设置限流的维度，如请求路径、用户信息等。
- 缺点：需要配置和维护 Redis。
@Component
public class PathKeyResolver implements KeyResolver {
public Mono<String> resolve(ServerWebExchange exchange) {
String path = exchange.getRequest().getPath().toString();
return Mono.just(path);
}
}结论
限流是确保系统稳定性的关键措施之一。文章介绍了六种限流方法，包括固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法、中间件限流和网关限流，各有优缺点，适用于不同的场景和架构。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
云数据库 Redis®
腾讯云数据库 Redis®（TencentDB for Redis®）是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备，提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
腾讯云开发者
