常见的四种限流算法及基础实现
- 什么是限流
- 有哪些限流算法？
- 限流算法
- 固定窗口
- 滑动窗口
- 漏桶算法
- 令牌算法
什么是限流
限流是对某一时间窗口内的请求数进行限制，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。
在高并发系统中，出于系统保护角度考虑，通常会对流量进行限流。
在分布式系统中，高并发场景下，为了防止系统因突然的流量激增而导致的崩溃，同时保证服务的高可用性和稳定性，限流是最常用的手段。
有哪些限流算法？
常见的四种限流算法，分别是：固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。
限流算法
固定窗口
1. 实现原理
-
固定窗口又称固定窗口（又称计数器算法，Fixed Window）限流算法，是最简单的限流算法。
-
实现原理：在指定周期内累加访问次数，当访问次数达到设定的阈值时，触发限流策略，当进入下一个时间周期时进行访问次数的清零。如图所示，我们要求 3 秒内的请求不要超过 150 次：
2. 简易代码实现
public class FixedWindow {
private long time = new Date().getTime();
private Integer count = 0; // 计数器
private final Integer max = 100; // 请求阈值
private final Integer interval = 1000; // 窗口大小
public boolean trafficMonitoring() {
long nowTime = new Date().getTime();
if (nowTime < time + interval) {
// 在时间窗口内
count++;
return max > count;
} else {
time = nowTime; // 开启新的窗口
count = 1; // 初始化计数器,由于这个请求属于当前新开的窗口，所以记录这个请求
return true;
}
}
}
3. 优缺点
- 优点：实现简单，容易理解
- 缺点：
-
限流不够平滑。例如：限流是每秒 3 个，在第一毫秒发送了 3 个请求，达到限流，窗口剩余时间的请求都将会被拒绝，体验不好。
-
无法处理窗口边界问题。因为是在某个时间窗口内进行流量控制，所以可能会出现窗口边界效应，即在时间窗口的边界处可能会有大量的请求被允许通过，从而导致突发流量。
即：如果第 2 到 3 秒内产生了 150 次请求，而第 3 到 4 秒内产生了 150 次请求，那么其实在第 2 秒到第 4
秒这两秒内，就已经发生了 300 次请求了，远远大于我们要求的 3 秒内的请求不要超过 150 次这个限制，如下图所示：
滑动窗口
1. 实现原理
-
滑动窗口为固定窗口的改良版，解决了固定窗口在窗口切换时会受到两倍于阈值数量的请求。在滑动窗口算法中，窗口的起止时间是动态的，窗口的大小固定。这种算法能够较好地处理窗口边界问题，但是实现相对复杂，需要记录每个请求的时间戳。
-
实现原理：滑动窗口在固定窗口的基础上，将时间窗口进行了更精细的分片，将一个窗口分为若干个等份的小窗口，每次仅滑动一小块的时间。每个小窗口对应不同的时间点，拥有独立的计数器，当请求的时间点大于当前窗口的最大时间点时，则将窗口向前平
-
移一个小窗口（将第一个小窗口的数据舍弃，第二个小窗口变成第一个小窗口，当前请求放在最后一个小窗口），整个窗口的所有请求数相加不能大于阈值。其中，Sentinel 就是采用滑动窗口算法来实现限流的。
如图所示：
2. 使用zset实现滑动窗口
通过使用springAOP和redis中的zset进行实现滑动窗口限流
定义注解
@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface RateLimiter {
/**
* 限流时间，单位秒
*/
int time() default 5;
/**
* 限流次数
*/
int count() default 10;
}
对应注解限流处理切面(主要)
@Aspect
@Component
public class RateLimiterAspect {
private static final Logger log = LoggerFactory.getLogger(RateLimiterAspect.class);
@Autowired
private RedisTemplate redisTemplate;
/**
* 实现限流（新思路）
* @param point
* @param rateLimiter
* @throws Throwable
*/
@Before("@annotation(rateLimiter)")
public void doBefore(JoinPoint point, RateLimiter rateLimiter) throws Throwable {
// 在 {time} 秒内仅允许访问 {count} 次。
int time = rateLimiter.time();
int count = rateLimiter.count();
// 根据用户IP（可选）和接口方法，构造key
String combineKey = getCombineKey(point);
System.err.println(combineKey);
// 记录本次访问的时间结点
long currentMs = System.currentTimeMillis();
redisTemplate.opsForZSet().add(combineKey, String.valueOf(currentMs), currentMs);
// 这一步是为了防止一直存在于内存中
redisTemplate.expire(combineKey, time, TimeUnit.SECONDS);
// 移除{time}秒之前的访问记录（滑动窗口思想）
redisTemplate.opsForZSet().removeRangeByScore(combineKey, 0, currentMs - time * 1000);
// 获得当前窗口内的访问记录数
Long currCount = redisTemplate.opsForZSet().zCard(combineKey);
// 限流判断
if (currCount !=null && currCount > count) {
//返回异常提示
log.error("[limit] 限制请求数'{}',当前请求数'{}',缓存key'{}'", count, currCount, combineKey);
//todo 返回异常
}
}
/**
* @param point 切入点
* @return 组合key
*/
private String getCombineKey(JoinPoint point) {
StringBuilder sb = new StringBuilder("rate_limit:");
MethodSignature signature = (MethodSignature) point.getSignature();
Method method = signature.getMethod();
Class<?> targetClass = method.getDeclaringClass();
// keyPrefix + "-" + class + "-" + method //类名加方法名
return sb.append("-").append( targetClass.getName() )
.append("-").append(method.getName()).toString();
}
}
使用@RateLimiter注解进行限流
@RateLimiter(time = 1, count = 10)
@GetMapping("/testIndex")
public String index(){
System.out.println("处理请求");
return "finish";
}
3. 优缺点
- 优点：解决了固定窗口算法的窗口边界问题，避免突发流量压垮服务器。
- 缺点：还是存在限流不够平滑的问题。例如：限流是每秒 3 个，在第一毫秒发送了 3 个请求，达到限流，剩余窗口时间的请求都将会被拒绝，体验不好。
漏桶算法
1. 实现原理
漏桶限流算法是一种常用的流量整形（Traffic Shaping）和流量控制（Traffic Policing）的算法，它可以有效地控制数据的传输速率以及防止网络拥塞。
主要的作用：
- 控制数据注入网络的速度。
- 平滑网络上的突发流量
实现原理：
漏桶是一个很形象的比喻，外部请求就像是水一样不断注入水桶中，而水桶已经设置好了最大出水速率，漏桶会以这个速率匀速放行请求，而当水超过桶的最大容量后则被丢弃。不管上面的水流速度有多块，漏桶水滴的流出速度始终保持不变。消息中间件就采用的漏桶限流的思想。
如图所示：
核心步骤：
- 一个固定容量的漏桶，按照固定速率出水（处理请求）；
- 当流入水（请求数量）的速度过大会直接溢出（请求数量超过限制则直接拒绝）。
- 桶里的水（请求）不够则无法出水（桶内没有请求则不处理）。
2. 简易实现
public class LeakyBucket {
private long capacity; // 漏桶容量
private long rate; // 流出速率
private long water; // 当前水量
private long lastTime; // 上次请求时间
public LeakyBucket(long capacity, long rate) {
this.capacity = capacity;
this.rate = rate;
this.water = 0;
this.lastTime = System.currentTimeMillis();
}
public synchronized boolean allow() {
long now = System.currentTimeMillis();
long elapsedTime = now - lastTime;
lastTime = now;
// 先漏水，根据流出速率计算漏掉的水量
water = Math.max(0, water - elapsedTime * rate);
// 检查水量是否超出了容量
if (water < capacity) {
water++;
return true; // 请求通过，水量增加
} else {
return false; // 请求被拒绝，水量已满
}
}
}
3. 优缺点
- 优点：
- 平滑流量。由于漏桶算法以固定的速率处理请求，可以有效地平滑和整形流量，避免流量的突发和波动（类似于消息队列的削峰填谷的作用）。
- 防止过载。当流入的请求超过桶的容量时，可以直接丢弃请求，防止系统过载。
- 缺点：
- 无法处理突发流量：由于漏桶的出口速度是固定的，无法处理突发流量。例如，即使在流量较小的时候，也无法以更快的速度处理请求。
- 可能会丢失数据：如果入口流量过大，超过了桶的容量，那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中，这可能是一个问题。
- 不适合速率变化大的场景：如果速率变化大，或者需要动态调整速率，那么漏桶算法就无法满足需求。
- 资源利用率：不管当前系统的负载压力如何，所有请求都得进行排队，即使此时服务器的负载处于相对空闲的状态，这样会造成系统资源的浪费。
由于漏桶的缺陷比较明显，所以在实际业务场景中，使用的比较少。
令牌算法
1. 实现原理
令牌桶算法是基于漏桶算法的一种改进，主要在于令牌桶算法能够在限制服务调用的平均速率的同时，还能够允许一定程度内的突发调用。
实现原理：
- 系统以固定的速率向桶中添加令牌；
- 当有请求到来时，会尝试从桶中移除一个令牌，如果桶中有足够的令牌，则请求可以被处理或数据包可以被发送；
- 如果桶中没有令牌，那么请求将被拒绝；
- 桶中的令牌数不能超过桶的容量，如果新生成的令牌超过了桶的容量，那么新的令牌会被丢弃。
令牌桶算法的一个重要特性是，它能够应对突发流量。当桶中有足够的令牌时，可以一次性处理多个请求，这对于需要处理突发流量的应用场景非常有用。但是又不会无限制的增加处理速率导致压垮服务器，因为桶内令牌数量是有限制的。
2. 代码实现
Guava 中的 RateLimiter 就是基于令牌桶实现的，可以直接拿来使用。
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
public void acquireTest() {
//每秒固定生成5个令牌
RateLimiter rateLimiter = RateLimiter.create(5);
for (int i = 0; i < 10; i++) {
double time = rateLimiter.acquire();
logger.info("等待时间：{}s", time);
}
}
3. 优缺点
- 优点
- 可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
- 限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）。
- 灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率。
- 缺点：
- 可能导致过载：如果令牌产生的速度过快，可能会导致大量的突发流量，这可能会使网络或服务过载。
- 需要存储空间：令牌桶需要一定的存储空间来保存令牌，可能会导致内存资源的浪费。
