简介
说明
本文介绍限流常用的算法及其优缺点。
常用的限流算法有：
- 计数器（固定窗口）算法
- 滑动窗口算法
- 漏桶算法
- 令牌桶算法
下面将对这几种算法进行分别介绍，并给出具体的实现。
限流的含义
限流是指在系统面临高并发、大流量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。
限流会对少部分用户的请求直接进行拒绝或者延迟处理，影响这些用户的体验。衡量系统处理能力的指标是每秒的QPS或者TPS，假设设置的系统每秒的流量阈值是1000，理论上一秒内有第1001个请求进来时，那么这个请求就会被限流。
以web服务、对外API为例，有以下几种可能导致机器被拖垮：
- 用户增长过快
- 因为某个热点事件（秒杀、微博热搜）
- 竞争对象爬虫
- 恶意的刷单
计数器算法
概述
计数器算法是限流算法里最简单也是最容易实现的一种算法。方案是：在单位时间内累加访问次数，当访问次数达到设定的阈值时，触发限流策略，当进入下一个单位时间时访问次数清零。
假设限制每分钟请求量不超过100。方法是：设置一个计数器，当请求到达时如果计数器到达阈值，则拒绝请求，否则计数器加1；每分钟重置计数器为0。如下图所示：
代码示例
public class CounterTest {
public long timeStamp = getNowTime();
public int reqCount = 0;
public final int limit = 100; // 时间窗口内最大请求数
public final long interval = 1000; // 时间窗口ms
public boolean grant() {
long now = getNowTime();
if (now < timeStamp + interval) {
// 在时间窗口内
reqCount++;
// 判断当前时间窗口内是否超过最大请求控制数
return reqCount <= limit;
} else {
timeStamp = now;
// 超时后重置
reqCount = 1;
return true;
}
}
public long getNowTime() {
return System.currentTimeMillis();
}
} 优缺点
优点
简单，最容易实现。
缺点
临界问题（突刺现象）。
假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，压垮我们的应用。
刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？或者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。
滑动窗口算法
概述
滑动窗口：为了避免计数器中的临界问题，让限制更加平滑，将固定窗口中分割出多个小时间窗口，分别在每个小的时间窗口中记录访问次数，然后根据时间将窗口往前滑动并删除过期的小时间窗口。如下图所示：
整个红色的矩形框表示一个时间窗口，一个时间窗口是1分钟。我们将将滑动窗口 划成了6格，每格代表的是10秒钟。每过10秒钟，时间窗口往右滑动一格，每个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒到达，那么0:30~0:39对应的counter就会加1。
滑动窗口怎么解决刚才的临界问题的呢？0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发了限流。
回顾刚才的计数器算法可以发现，计数器算法也是滑动窗口的一种。它没有对时间窗口做进一步地划分，所以只有1格。当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
优缺点
优点
- 可以基本解决计数器算法的临街问题。
缺点
- 除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，对内存的占用会比较多。
漏桶算法
概述
请求就像水一样以任意速度注入漏桶，桶会按照固定的速度将水漏掉。当注入速度持续大于漏出的速度时，漏桶会变满，此时新进入的请求将会被丢弃。 限流 和 整形 是漏桶算法的两个核心能力。
代码示例
public class LeakyBucketLimiter {
/**
* 上次请求到来的时间
*/
private long preTime = System.currentTimeMillis();
/**
* 漏水速率,n/s
*/
private int leakRate;
/**
* 储蓄桶容量
*/
private int capacity;
/**
* 当前水量
*/
private int water;
public LeakyBucketLimiter(int leakRate, int capacity) {
this.leakRate = leakRate;
this.capacity = capacity;
}
//省略get与set方法
public boolean limit() {
long now = System.currentTimeMillis();
//先漏水,计算剩余水量
water = Math.max(0, water - (int) ((now - preTime) / 1000) * leakRate);
preTime = now;
//桶未满
if (water + 1 <= capacity) {
water++;
return true;
}
return false;
}
} 优缺点
优点
- 确保网络中的突发流量被整合成平滑稳定的额流量。
缺点
- 漏桶对流量的控制过于严格，在有些场景下无法处理突发流量，不能充分使用系统资源。
- 因为漏桶的漏出速率是固定的，即使在某一时刻下游能够处理更大的流量，漏桶也不允许突发流量通过。
令牌桶算法
概述
令牌桶算法既能像漏桶那样匀速，又能像计数器那样处理突发请求。
令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。
令牌桶算法：以恒定速率向令牌桶发送令牌，请求到达时，尝试从令牌桶中拿令牌，只有拿到令牌才能够放行，否则将会被拒绝。
令牌桶大小固定，如果令牌桶被填满，则会丢弃新生成的要放进来的令牌，如果桶内没有令牌则触发限流策略。
代码示例
public class TokenBucketLimiter {
/**
* 上次请求到来的时间
*/
private long preTime = System.currentTimeMillis();
/**
* 放入令牌速率,n/s
*/
private int putRate;
/**
* 令牌桶容量
*/
private int capacity;
/**
* 当前令牌数
*/
private int bucket;
public TokenBucketLimiter(int putRate, int capacity) {
this.putRate = putRate;
this.capacity = capacity;
}
//省略get与set方法
public boolean limit() {
long now = System.currentTimeMillis();
//先放入令牌，再获取令牌
bucket = Math.min(capacity, bucket + (int) ((now - preTime) / 1000) * putRate);
preTime = now;
if (bucket == 0) {
return false;
}
bucket--;
return true;
}
} 优缺点
优点