0x0 引子
无论做哪种业务都躲不开排行功能. Redis 的 Sorted Sets 结构就是为排行而生的. 它简单易用, 效率奇高. 同时它也有坑, 你真的了解它吗?
老规矩, 先讲故事, 后科普. 这里是 Sorted Sets 知识点传送门.
0x1 好友推荐
事情要从这个需求开始. 产品想让用户通过好友系统互动起来, 那就需要个好友推荐系统, 帮助用户成为好友.
具体的推荐规则大致如下:
每个用户都有自己的成就值, 这个值随着时间和用户的行为而递增. 成就值的大概范围是[1,3500+].
假如用户 U 的成就值为 A, 我们就在成就值为 [A-10,A+10] 这个区间里, 随机取 10 个用户, 然后再按其他匹配规则筛选出来一个目标用户, 推荐给用户 U.
比如某用户的成就值是 100, 我们就在 90-110 这个范围内找 10 个用户, 筛选后最终得到一个目标用户, 推荐给他.
这个就是大概的需求.
我们最初的实现方式是这样的
创建一个 Sorted Set 记录所有用户的 id 和其成就值, 并用成就值排序
每次用 zadd 去更新单个用户的成就值
当需要计算推荐用户时, 先用 zscore 取出其成就值 A
用 zcount 计算出来区间 [A-10,A+10] 里的用户数 N
如果 N>10, offset 取值在 [0,N-10] 内随机
如果 N<=10, offset 取值 0
用 zrangebyscore A-10 A+10 limit offset 10 随机取出来 10 个用户
筛选出目标用户
就这样, 通过四个 Redis 命令, 实现了这个需求的核心功能.
0x2 出事儿了
程序运行了很长一段时间都没有问题, 各项指标都很正常, 都没有过多地关注过它.
突然有一天夜里, 线上发生了波动, 触发了告警. 追查了一下, 发现这台 Redis 的主库 CPU 飙升到了 100%, 进而 failover 到了从库上. 整个故障转移的过程造成了系统的波动. 幸好有自动故障转移, 要不然这一夜又要折腾了.
是福不是祸, 是祸躲不过, 还是排查问题吧.
0x3 追查真相
重点的怀疑对象就是上文中提到的四条 Redis 命令.
- zadd
- zscore
- zcount
- zrangebyscore
命令分析
这个 Sorted Set 的集合大小已经达到了两千万, 我们在这个数量级上分析一下各条命令的复杂度.
zadd
作用: 更新用户的成就值.
时间复杂度: O(log(N)
调用频率: 一般
zsore
作用: 获取用户的成就值
时间复杂度: O(1)
调用频率: 高
zcount
作用: 统计某个区间内的数量
时间复杂度: O(log(N)
调用频率: 高
zrangebyscore
作用: 在指定的偏移量里取一批用户
时间复杂度: O(log(N)+M)
调用频率: 高
通过官方对这个命令的解释 https://redis.io/commands/zrangebyscore 发现, 它的复杂度计算还挺复杂.
M 指获取的用户数, 这里取 10, 几乎可以忽略不计.
但是这个命令可以带 limit 参数, 它的复杂度受 limit 应该很大. limit 很像 MySQL 里 ( SELECT LIMIT offset, count ) 的用法, 如果 offset 比较大, 其时间复杂度趋向于 O(N).
这么分析下来, zrangebyscore 的嫌疑就很大了.
提审 zrangebyscore
如果要证明 zrangebyscore 有问题, 就得分析它的参数 offset 的可能取值是多少.
数据分析
根据上文对需求实现的描述, offset 的取值和当前用户的成就值有关系. 如果这个成就值周围分布的用户比较多, 那 offset 的取值就会很大.
成就段 | 用户数 |
---|---|
1-10 | 4419701 |
10-20 | 3152015 |
21-30 | 1600366 |
结果发现大部分用户的成就值都分布在 1-30. 这也就意味着, 当某个用户的成就值在 1-30 这个范围的时候, offset 的取值可能是 500W-1KW, 这个数量是巨大的.
仔细想想, 这种数据是很合理的. 大部分互联网用户的分布规律都是金字塔型的, 越初级的用户数量越多. 是我们对 Redis 认识的还不深, 对用户认识的也不深.
slow log
Redis 的 showlog 命令可以获取最近一段的慢查询
showlog get 10
得到的结果全是 zrangebyscore, 查询时间长达一分钟
到这里基本上可以断定是 zrangebyscore 的问题了.
0x4 优化方案
问题找到了, 怎么优化呢?
为了简化问题, 我们假设在算法运行的瞬间, Sorted Set 集合是不变的, 也就说我们不考虑并行的问题.
如果替换掉 zrangebyscore, 我们自己算排名并做跳转就行了, 这里可以使用命令 zrange.
新的算法流程大致如下
先用 zscore 取出其成就值 A
用 zcount 计算出区间 [A-10,A+10] 里的用户数 N
用 zcount 计算出区间 [1,A-10) 里的用户数 M
在 [1,N-10] 这个区间里随机出来一个数作为 offset
用 zrange 取出来排名为 [M+offset, M+offset+10] 的 10 位用户
筛选出目标用户
时间复杂度
根据上文, 老算法的时间复杂度为 O(log(N)+offset);
新算法的时间复杂度取决与 zrange,zrange 的时间复杂度为 O(log(N));
新算法的时间复杂度为 O(log(N)), 不再受 offset 的影响.
线上数据测试
从 Redis 备份里恢复一个测试用的实例, 用来测试对比新旧算法.
测试 JS 脚本实现如下
- const MIN_SCORE_DIFF = -10;
- const MAX_SCORE_DIFF = 10;
- const COUNT = 10;
- const CACHE_KEY = 'zset_user_score';
- async function oldRand(uid,random){
- var score = await redisClient.zscoreAsync(CACHE_KEY, uid);
- score = parseInt(score) || 0;
- var min = _.max([score + MIN_SCORE_DIFF, 0]);
- var max = score + MAX_SCORE_DIFF;
- var cnt = await redisClient.zcountAsync(CACHE_KEY,min,max);
- var offset = (cnt - COUNT> 0) ? Math.floor(random * (cnt - COUNT)) : 0;
- return await redisClient.zrangebyscoreAsync(CACHE_KEY,min, max, 'limit', offset,COUNT);
- }
- async function newRand(uid,random){
- var score = await redisClient.zscoreAsync(CACHE_KEY, uid);
- score = parseInt(score) || 0;
- var min = _.max([score + MIN_SCORE_DIFF, 0]);
- var max = score + MAX_SCORE_DIFF;
- var rangeCount = await redisClient.zcountAsync(CACHE_KEY,min,max);
- var baseCount = 0;
- baseCount = await redisClient.zcountAsync(CACHE_KEY,0,min-1);
- // 计算随机区间
- var diff = _.max(rangeCount - COUNT,0);
- var offset = Math.floor(random * diff);
- indexStart = baseCount + offset;
- var indexStop = indexStart + COUNT-1;
- return await redisClient.zrangeAsync(CACHE_KEY,indexStart,indexStop);
- }
正确性
随机测试 10 次, 两个算法的结果是一致的.
结果形如下面的输出
- oldResult: [ 'f4973930-a48f-11e8-84e4-59b2d71a90a4',
- 'f49744d0-f188-11e7-a76b-c9a7594d1140',
- 'f4974590-c683-11e8-ae4e-0befefb1d545',
- 'f4975320-f94f-11e7-a09f-7ba9027c4b77',
- 'f4975430-83a9-11e8-81c5-332d769f65f7',
- 'f4976180-9c92-11e8-8e50-4b5cff93f149',
- 'f4979190-ef31-11e8-befa-194ed3a1a4d0',
- 'f49792f0-ad85-11e8-901a-c17ed1379e08',
- 'f497aed0-9cc2-11e8-8e50-4b5cff93f149',
- 'f497afa0-d6d1-11e7-8320-01f23f01ed8f' ]
- time: 717 ms
- newResult: [ 'f4973930-a48f-11e8-84e4-59b2d71a90a4',
- 'f49744d0-f188-11e7-a76b-c9a7594d1140',
- 'f4974590-c683-11e8-ae4e-0befefb1d545',
- 'f4975320-f94f-11e7-a09f-7ba9027c4b77',
- 'f4975430-83a9-11e8-81c5-332d769f65f7',
- 'f4976180-9c92-11e8-8e50-4b5cff93f149',
- 'f4979190-ef31-11e8-befa-194ed3a1a4d0',
- 'f49792f0-ad85-11e8-901a-c17ed1379e08',
- 'f497aed0-9cc2-11e8-8e50-4b5cff93f149',
- 'f497afa0-d6d1-11e7-8320-01f23f01ed8f' ]
- time: 1 ms
执行效率
单位 ms
old | new |
---|---|
717 | 1 |
637 | 2 |
316 | 2 |
103 | 2 |
2 | 1 |
25 | 2 |
833 | 2 |
109 | 1 |
结论
新算法工作正常, 且执行时间稳定在 1-2 毫秒这个量级的. 是个可行的优化方案.
0x5 OPS 出手了
ops 组的同学根据上面的结论, 实现了 lua 版, 可以嵌入到 Redis 里执行, 解决并行问题.
- local score = Redis.call('ZSCORE', KEYS[1], KEYS[2]) or 0
- local min_score = math.max(score - 10, 0)
- local max_score = score + 10
- local r_count = Redis.call('ZCOUNT', KEYS[1], min_score, max_score)
- local b_count = Redis.call('ZCOUNT', KEYS[1], 0, min_score-1)
- local diff = math.max(r_count - 10, 0)
- local offset = math.floor(KEYS[3]*diff)
- local s_idx = b_count + offset
- local e_idx = s_idx + 9
- local list = Redis.call('ZRANGE', KEYS[1], s_idx, e_idx)
- return list
0x6 知识点
简介
Sorted Sets 是比较常用的结构. 中文翻译为有序集合. 英文名又叫 ZSets , 所以 Redis 以 Z 开头的命令都和这个结构有关系.
它和 Set 结构比较像, 都不允许都重复的元素出现. 它的每个元素都可以指定 score, 这个 score 也是其排序的依据, 如果 score 相同, 就按元素的字典顺序排序. Sorted Sets 始终维护一个升序的有序集合.
相关的命令就不再做过多的介绍, 大家可以去参考相关的文档 http://redisdoc.com/sorted_set/index.html . 但是值得注意的是, 随着 Redis 版本的变化, Sorted Sets 的某些功能也会发生变化, 而且还可能有新功能出现, 所以在阅读文档的时候, 一定要注意其标注的版本号. 编码的时候也要注意.
实现原理
Sorted Sets 的内部实现依赖两种结构 ziplist 和 skiplist .
在通过 ZADD 命令添加第一个元素到空 key 时, Redis 会通过检查输入的第一个元素来决定使用何种结构.
如果第一个元素符合以下条件的话, 就创建一个 ziplist 结构的 ZSet:
Redis 配置 zset_max_ziplist_entries 的值大于 0 (默认为 128 ).
元素的 member 长度小于配置 zset_max_ziplist_value 的值(默认为 64 ).
否则, 创建一个 skiplist 结构的 ZSet.
对于一个 ziplist 结构的 ZSet, 只要满足以下任一条件, 则会被转换为 skiplist 结构:
ziplist 所保存的元素数量超过配置 zset_max_ziplist_entries 的值(默认值为 128 )
新添加元素的 member 的长度大于配置 zset_max_ziplist_value 的值(默认值为 64 )
ziplist 和 skiplist 这两种结构是怎么实现, 如何工作的, 可以参考我转载的两篇文章.
ziplist
skiplist
应用场景
Sorted Sets 的使用场景很多, 常用的有三种.
排行计算
权重队列
时间相关的计算
排行计算
这个是最直接的功能, 而且效率很好. 千万级的数据也能轻松搞定.
权重队列
这个就有点意思了, 如果我们把 score 当做一种权重, 把 member 当做任务 id, 那 Sorted Sets 就可以做为一个简单的带优先级的任务队列来用.
基于 Redis 的队列 Kue https://github.com/Automattic/kue , 就是依赖这种结构实现的.
不过从 5.0 开始, Redis 推出了新结构 stream , 是专门用来做消息队列的, 这是后话.
时间相关的计算
巧妙地处理基于时间的数据.
比如统计最近 5 分钟的活跃用户数, 只需要把用户最后的活跃时间作为 score, 就可以计算最近一段时间的活跃用户数了.
比如获取最新的 5 条评论, 也是同样的道理.
比如实现 LRU 算法.
其他
其他的应用场景还有很多.
比如我们在好友推荐里使用的方式, 其实就是查找一定区间内的不同用户.
还有一种用法是聚合, 就是求交集, 并集, 差集. 涉及到的命令有 ZINTERSTORE,ZUNIONSTORE 等.
更多 Redis 系列
来源: https://www.cnblogs.com/zhroot/p/12371655.html