限流的经典算法
常见限流用法
固定窗口限流
首先维护一个计数器，将单位时间段当做一个窗口，计数器记录这个窗口接收请求的次数。
- 当次数少于限流阀值，就允许访问，并且计数器+1
- 当次数大于限流阀值，就拒绝访问。
- 当前的时间窗口过去之后，计数器清零。
假设单位时间是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
|
boolean fixedWindowsTryAcquire() {
long windowUnit = 1;
long lastTime = 0;
long currentTime = System.currentTimeMillis();
if (currentTime - lastRequestTime > windowUnit) {
counter = 0;
lastRequestTime = currentTime;
}
if (counter < threshold) {
counter++;
return true;
}
return false;
}
|
- 优势： 实现简单
- 缺点：不能均匀的分配时间，可能出现流量突刺(在两个时间窗口临界位置来10个请求)
滑动窗口限流算法
滑动窗口限流解决固定窗口临界值的问题。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。
每次过期一个小窗口，计算大窗口的请求是否达到阈值，如果大窗口达到阈值，就会拒接临界的小窗口请求
- 优势： 能够解决上述流量突刺的问题
- 缺点：实现相对固定窗口来说比较复杂
漏桶算法
漏桶算法面对限流，就更加的柔性，不存在直接的粗暴拒绝。
它的原理很简单，可以认为就是注水漏水的过程。往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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;
}
|
- 优势：能够一定程度上应对流量突刺，能够固定速率处理请求，保证服务器的安全。
- 缺点：没有固定速率处理一批请求，只能一个一个按顺序来处理（固定速率的缺点无法应对访问高峰期）
令牌桶算法
面对突发流量的时候，我们可以使用令牌桶算法限流。
令牌桶算法（Token Bucket Algorithm） 令牌桶算法可以看作一个令牌桶，其中令牌以恒定的速率产生。当一个请求到达时，如果令牌桶中仍然有令牌，则该请求得到处理并从令牌桶中减去一个令牌。如果令牌桶中没有令牌，则请求将被拒绝。在此算法中，令牌代表请求能够被处理的数量，而桶则代表着请求被处理的容器。
实现过程：
- 初始化令牌桶容量和速率；
- 以恒定速率往令牌桶中添加令牌；
- 当请求到达时，如令牌桶中仍有令牌，则从桶中移除一个令牌，并处理该请求；
- 如果没有足够的令牌，拒绝该请求。
令牌桶算法可以缓解漏桶算法的缺点，但在一些场景下可能存在一定问题。比如在应对短时间内的高并发请求时，由于令牌数有限，引入过大的并发请求会导致严重的性能问题，也可能会造成请求失败或者拒绝。
管理员先生成一批令牌，每秒生成10个令牌；当用户要操作前，先去拿到一个令牌，有令牌的人就有资格执行操作、同时执行操作；拿不到令牌的就等着
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
boolean tokenBucketTryAcquire() {
long currentTime = System.currentTimeMillis();
long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate;
currentToken = Math.min(capacity, generateToken + currentToken);
refreshTime = currentTime;
if (currentToken > 0) {
currentToken--;
return true;
}
return false;
}
|
- 优势：能够并发处理同时的请求，并发性能会更高
- 缺点：时间单位较难选取
限流的常用实现
单机限流
本地限流（单机限流）
每个服务器单独限流，一般适用于单体项目，就是你的 项目只有一个服务器 。
- 导入依赖
1
2
3
4
5
| <dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>
|
- Guava RateLimiter：业务实现
1
2
3
4
5
6
7
8
| import com.google.common.util.concurrent.RateLimiter;
public boolean doLimter(String[] args) {
RateLimiter limiter = RateLimiter.create(5.0);
return limiter.tryAcquire();
}
|
分布式限流
如果你的项目有多个服务器，比如微服务，那么建议使用分布式限流。
- 把用户的使用频率等数据放到一个集中的存储进行统计，比如Rdis,这样无论用户的请求落到了哪台服务器，都以集中的数据存储内的数据为准 (Redisson，是一个操作Redis的工具库)
- 在网关集中进行限流和统计（比如Sentinel、Spring Cloud Gateway)
Redisson限流实现
- 导入依赖
1
2
3
4
5
| <dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.21.3</version>
</dependency>
|
- 创建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;
}
}
|
- 编写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;
public void doRateLimit(String key) {
RRateLimiter rateLimiter = redissonClient.getRateLimiter(key);
rateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS);
boolean canOp = rateLimiter.tryAcquire(1);
ThrowUtils.throwIf(!canOp,ErrorCode.TOO_MANY_REQUEST);
}
}
|
