10万TPS级高并发系统——30亿级发送量频次管控（一）
一、背景简介
1.1 频次管控配置
| 限制项 | 限制频率 | 说明 |
|---|---|---|
| 接收频次管控 | 15次/1分钟 | 任意1分钟内，对同一个接收人发送消息最多15次，超出次数会被限制。 |
| 接收频次管控 | 50次/24小时 | 任意24小时内，对同一个接收人发送消息最多50次，超出次数会被限制。 |
| 内容频次管控 | 2次/59秒 | 任意59秒内，对同一个接收人发送同一内容（内容完全相同）最多2次，超出次数会被限制。 |
| 内容频次管控 | 5次/59分钟 | 任意59分钟内，对同一个接收人发送同一消息内容（内容完全相同）最多5次，超出次数会被限制。 |
二、需求分析
基于上述业务场景，我们需要对每个消息接收者做消息接收的频次限制，在每日30亿级的发送量的场景下，接收用户的数量也是亿级的。根据业务频次管控限流要求，需要实现分钟级别和24小时级别的频次管控。即需要对亿级终端接收用户分做独立的限流，限流的时间范围在分钟和24小时级别。
三、方案设计
上述业务需求其实是一种流量控制场景，可以结合一些常用的限流方案进行分析与设计。业务常见的限流方案有：固定窗口计数器、滑动窗口计数器、漏桶算法、令牌桶算法、分布式限流等（详见：四种经典的限流算法），我们先分析现有方案的特点再结合业务场景进行方案设计。
3.1 限流算法选择
基于上述业务场景，需要对每日亿级的终端接收用户做单独限流，结合经典的限流算法特点选择适合的算法：
| 限流算法 | 特点 | 是否适合 | 具体说明 |
|---|---|---|---|
| 固定时间窗口 | 简单，易于实现和理解 | 可选 | 容忍临界问题存在 |
| 滑动时间窗口 | 简单易懂，精度高，可扩展性强 | 适合 | 实现简单精度高 |
| 漏桶算法 | 平滑的限制处理速度 | 不适合 | 无法应对突发流量 |
| 令牌桶算法 | 稳定性高、精度高、可以处理突发流量 | 不适合 | 需要对日发送亿级用户做限流，需要维护上亿个令牌桶，复杂度过高 |
综上，经典的限流算法中滑动时间窗口是最适合的算法，固定时间窗口作为备选方案，因为固定时间窗口存在一个临界问题。
3.2 详细设计
目前系统性能需要达到10万TPS，应用使用集群化方式部署，同时需要实现日亿级用户的限流。所以我们需要实现一个基于滑动时间窗口的分布式限流器，且支持亿级用户做单独的限流。
根据业务及性能要求，我们使用Redis来设计一个基于滑动时间窗口算法的分布式限流器。
基于Redis ZSET集合的特点，我们使用ZSET来实现一个滑动时间窗口，用户每次下发成功后我们向ZSET添加一个成员，该成员的值和分数为当前消息的发送时间戳。
3.2.1 发送限流
发送消息前，我们根据当前时间和滑动时间窗口大小计算出滑动窗口起始时间戳，通过ZSET的Score获取起始时间戳和当前时间戳区间内成员的个数即为用户的消息发送量，如果超出频次限制则限制下发，如果未超过，则将该发送时间添加到ZSET中。
3.2.2 代码实现
下面通过Redis的ZSET数据结构及LUA脚本实现一个滑动窗口计数器，Lua脚本frequency_limit.lua内容如下：
-- 接收参数
local key = KEYS[1]
local windowSize = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
-- 获取精确到毫秒的时间戳
local nowMicros = redis.call('time')
local nowMillis = math.floor(nowMicros[1] * 1000 + nowMicros[2] / 1000)
-- 计算时间窗口的最小值
local minScore = nowMillis - windowSize
-- 获取时间窗口范围内的成员数量
local count = redis.call('ZCOUNT', key, minScore, nowMillis)
-- 如果数量没有超过限制
if count < limit then
-- 查找下一个可用的、未存在于ZSET中的时间戳
local uniqueTimestamp = nowMillis
while redis.call('ZSCORE', key, uniqueTimestamp) do
uniqueTimestamp = uniqueTimestamp + 1
end
-- 将找到的唯一时间戳作为值，当前时间戳作为score添加到ZSET
redis.call('ZADD', key, nowMillis, uniqueTimestamp)
-- 仅当添加了新元素后，才更新ZSET的过期时间
redis.call('EXPIRE', key, windowSize)
end
-- 返回计算出的数量
return count缓存过期时间
每次调用时将缓存的过期时间更新为一个滑动时间窗口大小，当一个滑动时间窗口区间内没有请求进来，则缓存过期。
并发访问问题
我们在ZSET中使用毫秒级别的时间戳来记录访问数量。在高并发的情况下，可能会存在同一毫秒下发多条消息导致发送量出现覆盖，我们采用占用未来时间戳的方式解决并发冲突。
3.2.3 验证测试
上传Lua脚本
[root@develop bin]# ./redis-cli -p 6383 -a 123456 SCRIPT LOAD "$(cat frequency_limit.lua)"
Warning: Using a password with '-a' or '-u' option on the command line interface may not be safe.
"59931c4f3ae5b3601ba2988d12d7aa897afc9549"执行Lua脚本
下面通过Redis执行上述lua脚本，获取18829340001前1分钟的消息发送量，当返回值小于5时，可以继续下发消息；当返回值为5时，表示前1分钟内已经下发了5条，需要进行频次管控。
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 0
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 1
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 2
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 3
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 4
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 5
127.0.0.1:6383> EVALSHA 59931c4f3ae5b3601ba2988d12d7aa897afc9549 1 18829340001 60000 5
(integer) 5四、性能评估
4.1 业务场景分析
即Redis的性能要在30万TPS以上,需要支持亿级数据缓存。
4.2 Redis主备性能评估
该项目使用华为云部署，使用华为云上Redis服务，华为云提供的Redis6主备性能测试数据如下：
Redis主备32G实例的性能在14万TPS作为，无法满足系统30万+TPS性能要求，所以需要使用Redis集群。
4.3 Redis集群性能评估
华为云提供的Redis6集群性能测试数据如下：
华为云Redis6 32G集群实例的性能达到30万tps，为应对业务中配置多条频次管控场景，选择64G 8分片的规格。
但在生产环境中，客户直接选择256G 32分片的规格实例，在配置2条全局的频次管控场景下，压测10万TPS，Redis集群CPU负载在50%以上。
五、总结
本文主要介绍基于Redis的ZSET数据结构实现一个滑动窗口计数器，实现亿级用户的发送频次管控，并根据业务场景和华为云Redis不同规格的性能进行规格选择。
5.1 优化改进
在上述设计方案中，结合业务场景分析频次管控配置数量在1-2个左右，为实现简单所以每个频次管控单独维护一个滑动窗口计数器。如果需要适配较多的窗口大小的场景下，可以将多个滑动窗口进行合并，降低网络消耗，提高性能。
5.2 其它问题
在大数据量、高并发的场景下，Redis的使用还会出现大Key等问题，具体的场景和案例，敬请期待后续文章。
