限流的经典算法

常见限流用法

固定窗口限流

首先维护一个计数器,将单位时间段当做一个窗口,计数器记录这个窗口接收请求的次数。

  1. 当次数少于限流阀值,就允许访问,并且计数器+1
  2. 当次数大于限流阀值,就拒绝访问。
  3. 当前的时间窗口过去之后,计数器清零。

假设单位时间是1秒,限流阀值为3。在单位时间1秒内,每来一个请求,计数器就加1,如果计数器累加的次数超过限流阀值3,后续的请求全部拒绝。等到1s结束后,计数器清0,重新开始计数。如下图:

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 固定窗口时间算法
* @return
*/
boolean fixedWindowsTryAcquire() {
long windowUnit = 1; //设置窗口时间单位
long lastTime = 0; // 初始时间
long currentTime = System.currentTimeMillis(); //获取系统当前时间
if (currentTime - lastRequestTime > windowUnit) { //检查是否在时间窗口内
counter = 0; // 计数器清0
lastRequestTime = currentTime; //开启新的时间窗口
}
if (counter < threshold) { // 小于阀值
counter++; //计数器加1
return true;
}
return false;
}
  1. 优势: 实现简单
  2. 缺点:不能均匀的分配时间,可能出现流量突刺(在两个时间窗口临界位置来10个请求)

滑动窗口限流算法

滑动窗口限流解决固定窗口临界值的问题。它将单位时间周期分为n个小周期,分别记录每个小周期内接口的访问次数,并且根据时间滑动删除过期的小周期。

每次过期一个小窗口,计算大窗口的请求是否达到阈值,如果大窗口达到阈值,就会拒接临界的小窗口请求

  1. 优势: 能够解决上述流量突刺的问题
  2. 缺点:实现相对固定窗口来说比较复杂

漏桶算法

漏桶算法面对限流,就更加的柔性,不存在直接的粗暴拒绝。

它的原理很简单,可以认为就是注水漏水的过程。往漏桶中以任意速率流入水,以固定的速率流出水。当水超过桶的容量时,会被溢出,也就是被丢弃。因为桶容量是不变的,保证了整体的速率。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 漏桶算法
* @return
*/
boolean leakybucketLimitTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
refreshTime = currentTime; // 刷新时间

// 当前剩余水量还是小于桶的容量,则请求放行
if (currentWater < capacity) {
currentWater++;
return true;
}

// 当前剩余水量大于等于桶的容量,限流
return false;
}
  1. 优势:能够一定程度上应对流量突刺,能够固定速率处理请求,保证服务器的安全。
  2. 缺点:没有固定速率处理一批请求,只能一个一个按顺序来处理(固定速率的缺点无法应对访问高峰期)

令牌桶算法

面对突发流量的时候,我们可以使用令牌桶算法限流。

令牌桶算法(Token Bucket Algorithm) 令牌桶算法可以看作一个令牌桶,其中令牌以恒定的速率产生。当一个请求到达时,如果令牌桶中仍然有令牌,则该请求得到处理并从令牌桶中减去一个令牌。如果令牌桶中没有令牌,则请求将被拒绝。在此算法中,令牌代表请求能够被处理的数量,而桶则代表着请求被处理的容器。

实现过程:

  1. 初始化令牌桶容量和速率;
  2. 以恒定速率往令牌桶中添加令牌;
  3. 当请求到达时,如令牌桶中仍有令牌,则从桶中移除一个令牌,并处理该请求;
  4. 如果没有足够的令牌,拒绝该请求。

令牌桶算法可以缓解漏桶算法的缺点,但在一些场景下可能存在一定问题。比如在应对短时间内的高并发请求时,由于令牌数有限,引入过大的并发请求会导致严重的性能问题,也可能会造成请求失败或者拒绝。

管理员先生成一批令牌,每秒生成10个令牌;当用户要操作前,先去拿到一个令牌,有令牌的人就有资格执行操作、同时执行操作;拿不到令牌的就等着

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 令牌桶算法
* @return
*/
boolean tokenBucketTryAcquire() {

long currentTime = System.currentTimeMillis(); //获取系统当前时间
long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
refreshTime = currentTime; // 刷新时间

//桶里面还有令牌,请求正常处理
if (currentToken > 0) {
currentToken--; //令牌数量-1
return true;
}

return false;
}
  1. 优势:能够并发处理同时的请求,并发性能会更高
  2. 缺点:时间单位较难选取

限流的常用实现

单机限流

本地限流(单机限流)

每个服务器单独限流,一般适用于单体项目,就是你的 项目只有一个服务器 。

  1. 导入依赖
1
2
3
4
5
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>
  1. Guava RateLimiter:业务实现
1
2
3
4
5
6
7
8
import com.google.common.util.concurrent.RateLimiter;

public boolean doLimter(String[] args) {
// 每秒限流5个请求
RateLimiter limiter = RateLimiter.create(5.0);

return limiter.tryAcquire(); // true 接受请求 false 拒接请求
}

分布式限流

如果你的项目有多个服务器,比如微服务,那么建议使用分布式限流。

  1. 把用户的使用频率等数据放到一个集中的存储进行统计,比如Rdis,这样无论用户的请求落到了哪台服务器,都以集中的数据存储内的数据为准 (Redisson,是一个操作Redis的工具库)
  2. 在网关集中进行限流和统计(比如Sentinel、Spring Cloud Gateway)

Redisson限流实现

  1. 导入依赖
1
2
3
4
5
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.21.3</version>
</dependency>
  1. 创建RedissonConfig配置类,用于初始化RedissonClient对象单例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Data
@ConfigurationProperties(prefix = "spring.redis")
@Configuration
public class RedissonConfig {
private Integer database;
private String host;
private Integer port;
private String password;
private Integer timeout;

@Bean
public RedissonClient redissonClient() {
Config config = new Config();
config.useSingleServer()
.setDatabase(database)
.setAddress("redis://" + host + ":" + port)
.setPassword(password)
.setTimeout(timeout);
RedissonClient redisson = Redisson.create();
return redisson;
}
}
  1. 编写RedisLimiterManager
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@Service
public class RedisLimiterManager {

@Resource
private RedissonClient redissonClient;

/**
* 限流操作
*
* @param key 区分不同的限流器,比如不同的用户 id 应该分别统计
*/
public void doRateLimit(String key) {
// 创建一个限流器
RRateLimiter rateLimiter = redissonClient.getRateLimiter(key);
// 每秒最多访问 2 次
// 参数1 type:限流类型,可以是自定义的任何类型,用于区分不同的限流策略。
// 参数2 rate:限流速率,即单位时间内允许通过的请求数量。
// 参数3 rateInterval:限流时间间隔,即限流速率的计算周期长度。
// 参数4 unit:限流时间间隔单位,可以是秒、毫秒等。
rateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS);
// 每当一个操作来了后,请求一个令牌
boolean canOp = rateLimiter.tryAcquire(1);
ThrowUtils.throwIf(!canOp,ErrorCode.TOO_MANY_REQUEST);
}
}