断尾求生 — 简单限流

断尾求生 — 简单限流

简单限流

限流算法在分布式领域是一个经常被提起的话题,当系统处理能力有限时,如何阻止计划外的请求继续对系统施压,这是一个需要重视的问题。

以论坛社区为例,我们可以通过限流控制用户行为,避免垃圾请求。比如用户的发帖、点赞、回复等行为需要严格管控,限定某行为在规定的时间内次数,超过了次数就是非法行为。

设计一个限流接口

我们设计一个接口,限定用户的某个行为在规定的时间之内只能允许执行 N 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface RateLimiter {

/**
* 简单限流接口
*
* @param userId 用户ID
* @param actionKey 行为ID
* @param period 时间周期
* @param maxCount 最大允许次数
* @return 是否被允许操作
*/
boolean isActionAllowed(String userId, String actionKey, int period, int maxCount);

}

// 限定用户的回帖行为一分钟只被允许 5 次
isActionAllowed("Harry", "reply", 60, 5);

如何使用 redis 实现这个限流算法?有两种方案:1.使用 zset 数据结构;2.使用 string 数据结构。

zset 结构实现限流

这种方案有一个叫做「滑动窗口」的概念,窗口期的定义我们使用 score 来实现。score 的值是当前毫秒数,假定限定时间为 60s,那么每次 zadd 时以当前毫秒数为最后时间,当前时间与前 60s 之间作为一个「窗口期」。窗口期之外的数据将被删除,因为超出了时间限制。我们在窗口期之内 zadd 数据,然后 zscard 这个期间所有的元素数量,如果元素大于 maxCount,则不允许操作,否则行为将被允许,以此起到限流的作用。

在以下的例子中,我们以 用户ID+行为ID 为 key,score 是当前时间毫秒数,member 值无意义,只需要保证唯一所以使用时间毫秒值。

  1. 首先,用户的每一次请求,都会 zadd 一个元素到窗口期;
  2. 然后,以 [当前时间前60s,当前时间] 作为窗口期,删除不在窗口期的元素。因为我们只需要知道 “前 60s 中用户的行为操作过几次”
  3. 接着,我们查看窗口期之间一共添加过几个元素。如果这个元素超过了最大限制次数,就起到了限流的效果了
  4. 最后,我们还添加了一个过期时间。如果用户在接下来的 61 秒中没有进行过操作,就把这个 key 自动删除以节省空间,61 秒之后发起的请求将会重新创建一个 zset 并放入一个元素到新的窗口期。
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
26
27
28
29
30
public class SimpleRateLimiter implements RateLimiter {
private Jedis jedis;

public SimpleRateLimiter(Jedis jedis) {
this.jedis = jedis;
}

public static void main(String[] args) {
Jedis jedis = new Jedis();
SimpleRateLimiter limiter = new SimpleRateLimiter(jedis);
for (int i = 0; i < 20; i++) {
System.out.println(limiter.isActionAllowed("Harry", "reply", 60, 5));
}
}

@Override
public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
String key = String.format("hist:%s:%s", userId, actionKey);
long nowTs = System.currentTimeMillis(); // 毫秒
Pipeline pipeline = jedis.pipelined(); // 使用管道批量执行指令
pipeline.multi();
pipeline.zadd(key, nowTs, "" + nowTs);
pipeline.zremrangeByScore(key, 0, nowTs - period * 1000); // 移除"当前时间前60秒"以前的所有 member。单位转换为毫秒
Response<Long> count = pipeline.zcard(key);
pipeline.expire(key, period + 1); // period+1 秒后过期
pipeline.exec();
pipeline.close();
return count.get() <= maxCount; // 限定最大次数只能为 maxCount
}
}

输出:

true
true
true
true
true
false
false
false
false
false
false
false
false
false
false
false
false
false
false
false

string 结构实现限流

这种实现方式是我自己设计的,和 zset 是一样能实现相同的限流效果。这种设计没有窗口期的概念,一切都很简单。同样以 行为ID+用户ID 为 key,不同的是 value 作为请求次数,限流周期是过期时间。

  1. 用户的第一次请求会 set 一个值为 1 的 key,过期时间为 60s;
  2. 在接下来的 60s 中,每次请求都将 value 自增 1,通过自增后的 value 与 maxCount 做比较确定是否限流;
  3. 60s 后,发起请求将会重新创建一个 key,重新计算次数并施加过期时间开始下一个周期的限流。
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
26
27
28
public class SimpleRateLimiterForString implements RateLimiter {
private Jedis jedis;

public SimpleRateLimiterForString(Jedis jedis) {
this.jedis = jedis;
}

public static void main(String[] args) {
SimpleRateLimiterForString limiter = new SimpleRateLimiterForString(new Jedis());
for (int i = 0; i < 20; i++) {
System.out.println(limiter.isActionAllowed("Jessica", "reply", 60, 5));
}
}

@Override
public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
String key = String.format("rate:%s:%s", actionKey, userId);
String count = jedis.get(key);
if (null == count || 0 == count.length()) {
SetParams setParams = new SetParams();
setParams.ex(period + 1);
jedis.set(key, "1", setParams);
return true;
}
Long currentCount = jedis.incr(key);
return currentCount <= maxCount;
}
}

限制条件

这种方式的限流有一个明显的缺陷,我们可以发现 key 的空间和限制次数成正比,用户点击多少次就会有多少个 key 存在。如果想要在一分钟限制请求最多100万次,那么就可能会有 100 万个或者更多的 value 存在,十分消耗空间。所以这种方式适用于点击量不大,并发量不高的情况下使用。

# redis

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×