共计 4282 个字符,预计需要花费 11 分钟才能阅读完成。
在分布式系统中,高并发场景下,为了防止系统因突然的流量激增而导致的崩溃,同时保证服务的高可用性和稳定性,限流是最常用的手段。
实际开发可能都是直接用现成的轮子,现成的限流框架Sentinel、Zuul、Hystrix等,但是底层的算法还是有必要了解一下。这里主要介绍4种常见的限流算法:固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。
一、固定窗口算法
固定窗口限流算法,也叫计数器限流算法,是最简单的一种限流算法。
1.1 实现原理
原理:在一个固定长度的时间窗口内限制请求数量,来一个请求,次数加一,超过最大限制,就拒绝。
1.2 代码实现
public class FixWindowLimiter {
/**
* 每个窗口的最大请求数量
*/
public static long threshold = 10;
/**
* 窗口大小,1000ms
*/
public static long windowUnit = 1000;
/**
* 窗口内的当前请求数量
*/
public static long count = 0;
/**
* 窗口的开始时间
*/
public static long lastTime = 0;
/**
* 限流方法,返回true表示通过
*/
public boolean limit() {
// 获取系统当前时间
long currentTime = System.currentTimeMillis();
// 判断是否在当前时间窗口内,如果不在就开启一个新的时间窗口
if (currentTime - lastTime > windowUnit) {
// 计数器清零
count = 0;
// 开启新的时间窗口
lastTime = currentTime;
}
// 判断是否超过最大请求量
if (count < threshold) {
count++;
return true;
}
return false;
}
}
1.3 优缺点
优点: 实现简单,容易理解
缺点:
- 限流不够平滑。例如:限流每秒3个,在第一毫秒就处理了3个请求,达到限流阈值,窗口剩余时间的请求都将被拒绝。
- 无法处理窗口边界问题。因为是在某个时间窗口进行流量控制,所以可能出现边界问题,即在时间窗口的边界可能会有大量的请求被允许,导致突发流量。
二、滑动窗口算法
滑动窗口算法是对固定窗口算法的改进。在滑动窗口算法中,窗口的起止时间是动态的,窗口大小是固定的。这种算法能够较好的处理窗口的边界问题,但需要记录每个请求的时间戳。
2.1 实现原理
来一个请求,就向后推一个时间窗口,计算这个窗口内的请求数量。如果数量超过限制就拒绝请求,否则接受请求,并记录请求时间戳,另外还需要一个任务清理过期的时间戳。
2.2 代码实现
public class SlidingWindowLimiter {
/**
* 每个窗口的最大请求数量
*/
public static long threshold = 10;
/**
* 窗口大小,1000ms
*/
public static long windowUnit = 1000;
/**
* 请求集合,用来存储窗口内的请求数量
*/
public static List<Long> requestList = new ArrayList<>();
/**
* 限流方法,返回true表示通过
*/
public boolean limit() {
// 获取系统当前时间
long currentTime = System.currentTimeMillis();
// 统计当前窗口内,有效的请求数量
int sizeOfValid = this.sizeOfValid(currentTime);
// 判断是否超过最大请求数量
if (sizeOfValid < threshold) {
// 把当前请求添加到请求集合里
requestList.add(currentTime);
return true;
}
return false;
}
/**
* 统计当前窗口内,有效的请求数量
*/
private int sizeOfValid(long currentTime) {
int sizeOfValid = 0;
for (Long requestTime : requestList) {
// 判断是否在当前时间窗口内
if (currentTime - requestTime <= windowUnit) {
sizeOfValid++;
}
}
return sizeOfValid;
}
/**
* 清理过期的请求(单独启动一个线程处理)
*/
private void clean() {
// 判断是否超出当前时间窗口内
requestList.removeIf(requestTime -> System.currentTimeMillis() - requestTime > windowUnit);
}
}
2.3 优缺点
优点:解决了固定窗口算法的窗口边界问题,避免了突发流量击垮服务器
缺点:
- 依然存在限流不够平滑的问题。例如:限流每秒3个,在第一毫秒发送了3个请求,达到 限流,剩余的窗口时间内的请求会被拒绝。
三、漏桶算法
漏桶算法是一种常用的流量整形(traffic shaping)和流量控制(traffic policing)的算法,它可以有效的控制数据的传输速率以及网络拥塞。
3.1 实现原理
- 一个固定容量的漏桶,按照固定速率出水(处理请求);
- 当流入谁(请求数量)的速度过大,会直接溢出(超过限制的请求会直接被丢弃/拒绝);
- 桶里的水(请求)不够则无法出水(桶内没有请求则不处理);
当请求流量正常或者较小的时候,请求能够得到正常的处理。当请求流量过大,漏桶限流算法可以通过丢弃部分请求来防止系统过载。
这种算法的一个重要特性是,输出速率始终保持一致,无论输入的流量怎么变化。也正是因为如此,它无法处理突发流量。此外,如果入口流量过大,漏桶可能溢出,导致数据丢失。
3.2 代码实现
public class LeakyBucketLimiter {
/**
* 桶的最大容量
*/
public static long threshold = 10;
/**
* 桶内当前水量
*/
public static long count = 0;
/**
* 漏水速率(每秒5次)
*/
public static long leakRate = 5;
/**
* 上次漏水时间
*/
public static long lastLeakTime = System.currentTimeMillis();
/**
* 限流方法,返回true表示通过
*/
public boolean limit() {
// 调用漏水方法
this.leak();
// 判断是否超过最大请求数量
if (count < threshold) {
count++;
return true;
}
return false;
}
/**
* 漏水方法,计算并更新这段时间内漏水量
*/
private void leak() {
// 获取系统当前时间
long currentTime = System.currentTimeMillis();
// 计算这段时间内,需要流出的水量
long leakWater = (currentTime - lastLeakTime) * leakRate / 1000;
count = Math.max(count - leakWater, 0);
lastLeakTime = currentTime;
}
}
3.3 优缺点
优点:
- 平滑流量。固定的速率处理请求,平滑和整形流量,避免流量突发和波动。
- 防止过载。多余的流量可以直接丢弃。
缺点: - 无法处理突发流量。漏桶的出口速率固定,无法处理突发流量
- 可能会丢失数据。如果入口流量过大,超过桶的容量,那么会丢弃部分请求。在一些不能接受丢失请求的场景不适用
四、令牌桶算法
令牌桶限流算法也是一种常用的流量整形和速率限制算法。
4.1 实现原理
- 系统以固定的速率向桶中添加令牌
- 当有请求到来时,会尝试从桶中移除一个令牌。只要桶中有足够的令牌,则请求都会被处理
- 如果桶中没有令牌,那么请求会被拒绝
- 桶中的令牌数不能超过桶的数量,如果新的令牌超过桶的容量,新的令牌会被丢弃
令牌桶算法的一个重要特性是,它可以应对突发流量。当桶中有足够的令牌,就可一次性处理多个请求。
4.2 代码实现
public class TokenBucketLimiter {
/**
* 桶的最大容量
*/
public static long threshold = 10;
/**
* 桶内当前的令牌数量
*/
public static long count = 0;
/**
* 令牌生成速率(每秒5次)
*/
public static long tokenRate = 5;
/**
* 上次生成令牌的时间
*/
public static long lastRefillTime = System.currentTimeMillis();
/**
* 限流方法,返回true表示通过
*/
public boolean limit() {
// 调用生成令牌方法
this.refillTokens();
// 判断桶内是否还有令牌
if (count > 0) {
count--;
return true;
}
return false;
}
/**
* 生成令牌方法,计算并更新这段时间内生成的令牌数量
*/
private void refillTokens() {
long currentTime = System.currentTimeMillis();
// 计算这段时间内,需要生成的令牌数量
long refillTokens = (currentTime - lastRefillTime) * tokenRate / 1000;
count = Math.min(count + refillTokens, threshold);
lastRefillTime = currentTime;
}
}
4.3 优缺点
优点:
- 可以处理突发流量:令牌桶算法可以处理突发流量。当桶满时,能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
- 限制平均速率:在长期运行中,数据的传输率会被限制在预定义的平均速率(即生成令牌的速率)。
- 灵活性:与漏桶算法相比,令牌桶算法提供了更大的灵活性。例如,可以动态地调整生成令牌的速率。
缺点:
- 可能导致过载:如果令牌产生的速度过快,可能会导致大量的突发流量,这可能会使网络或服务过载。
- 需要存储空间:令牌桶需要一定的存储空间来保存令牌,可能会导致内存资源的浪费。
- 实现稍复杂:相比于计数器算法,令牌桶算法的实现稍微复杂一些。
五、总结
固定窗口算法实现简单,但是限流不够平滑,存在窗口边界问题,适用于需要简单实现限流的场景。
滑动窗口算法解决了窗口边界问题,但是还是存在限流不够平滑的问题,适用于需要控制平均请求速率的场景。
漏桶算法的优点是流量处理更平滑,但是无法应对突发流量,适用于需要平滑流量的场景。
令牌桶算法既能平滑流量,又能处理突发流量,适用于需要处理突发流量的场景。