基于zset与bloom filter的排行榜与点赞方案设计
前言
最近有做较多关于排行榜需求相关迭代，在这期间关于技术方案也进行了很多的思考和调研，到底采用哪种方式更贴合业务，在不过度设计的基础上多多考虑扩展性和稳定性，最终选型中有Mysql、Redis zset、bloom filter等技术，因此在这里做个总结与分享。
排行榜和feed流中个人数据进行点赞的需求很常见，如下图所示为一个排行榜的展示大概展示内容，包括用户基本信息、排行、排行所依赖的数据、其他数据（点赞个数及当前用户对榜单用户点赞状态），一般排行榜有以下几种形式：
- 总榜，从始至终的一个数据统计榜单，凸显用户总成就及投入量；
- 周期榜如日榜、周榜和月榜，统计一段时间内的用户成就值，凸显周期内投入较多的用户；
- 好友（地区或其他条件）及好友周期榜，统计当前用户圈子内的榜单，在技术方案的实现上与上面的那些仅有一些细微的差别；
正文
总榜
首先从总榜来看，其设计方案应该是相对比较简单，即使将所有用户的数据都存入关系型数据库中，那这个空间复杂度也只是On（即用户总量），基本数据结构如下：其中需要为用户id、成就点数建立索引。
| 列名 | 含义 |
|---|---|
| id | 主键id |
| user_id | 用户id |
| honor_stars | 获取成就点数 |
| likes | 被点赞数据 |
| others | 其他数据 |
根据上述设计，总榜中常用到的sql就是 select * from tb order by honor_stars desc,likes desc limit 100，基于成就点数和另外一个纬度的数据进行倒排排序，这里需要注意的就是Mysql innodb引擎对于order by语法的执行优化过程。需要分为order by和where 语句中索引的建立，由于总榜不涉及where条件筛选，所以仅需要考虑对于order by后的字段建立索引，并且如果各位了解联合索引在B+树中的存储结构，order by语句使用的索引应该是需要依据查询的最左前缀原则来创建。
INDEX stars_likes (honor_stars,likes) USING BTREE
建立过索引后，这样的sql就可以通过优化查询器使用联合索引来进行查询，具体为先查询stars_likes索引，由于已经是排序的结果，因此倒排查询100个后，获得stars_likes索引的叶子节点中的主键id列表，拿着主键id列表查询主键索引进行回表，查询出所有数据后返回结果集给server层。如果不需要其他数据，仅需要用户id，则同样可以考虑索引覆盖的情况，建立honor_stars、likes、user_id三个联合索引，省去了回表的成本。
一个正常的总榜方案大概如上，也可以根据业务的容忍程度对榜单数据做缓存，比如榜单每个小时刷新一次等策略。或者如果是要求实时榜单，同样可以对榜单数据做缓存，只是需要对榜单头部用户的成就点数更新做监听，如果有更新，则删除榜单缓存即可。如下图所示，清除缓存的时机可以依据业务需求来定，或是定时清理，或是展示一个伪实时的榜单，仅在榜单上用户数据更新时，清除缓存。
周榜
相对于总榜来说，周榜具有相应的时效性，每周清空一次，数据重要程度没有总榜那样需要持久化，除了还是使用上面关系型数据库的方案外，Redis中的zset也是一个做排行榜的很不错的解决方案，我们分别讨论一下。
基于关系型数据库的周榜实现
如果周榜数据无需归档和记录，那么完全可以使用上面的数据结构新建一个周榜表，然后每周清空一次表即可。如果周榜需要对历史数据进行保留，那么我们需要新增一个字段标识当前记录属于哪一周，然后服务器在进行榜单数据更改时，依据当前时间更新对应数据，这块需要额外考虑时区问题。
| 列名 | 含义 |
|---|---|
| id | 主键id |
| user_id | 用户id |
| honor_stars | 获取成就点数 |
| likes | 被点赞数据 |
| others | 其他数据 |
| week_num | 周标识或是否可用标识 |
更新方案相对比较简单，只是查询的sql需要作出一些变更select * from tb where week_num = 1 order by honor_stars desc,likes desc limit 100，这个sql如果使用explain分析的话，就不能很好的利用到排行数据的联合索引了，可以看到extra 中有个Using filesort的属性。我们可以想象一下sql的执行过程，肯定是先要执行week_num索引的查询，然后回表到主键索引中将honor_stars、likes等字段拿到内存中，进行排序（也就是filesort），最后返回相应结果集。
基于zset的周榜实现
Redis zset使用跳表实现，能够在较低的一个时间复杂度中完成数据的排名、范围内排名数据查询等。一些常用的api如下：，针对于周榜功能的实现，需要用到api中的新增成员、变动其中成员的数据、获取当前成员所在的排名、获取某个区间段的全部成员等功能。
对于zset Node节点的基本数据结构为一个object类型的value字段，以及一个double类型的score字段（用作计算排名），跳表基于score属性进行排序，每个Node有不同的层数属性（Redis 跳表）。除此之外zset内部维护了value与score的map，以备通过value查询score的api。
1. ZADD key score1 member1 [score2 member2]
功能: 向有序集合添加一个或多个成员，或者更新已存在成员的分数
返回值: 添加成功的元素个数(已存在的添加不成功)
2. ZCOUNT key min max
功能: 计算在有序集合中指定区间分数的成员数
返回值: 区间内的元素个数
3. ZINCRBY key increment member
功能: 有序集合中对指定成员的分数加上增量 increment
返回值: member增加后的分数
4. ZREVRANK key member
功能: 返回有序集合中指定成员的排名，有序集成员按分数值递减(从大到小)排序
返回值: member排名或者 nil
5. ZLEXCOUNT key min max
功能: 在有序集合中计算指定字典区间内成员数量
6. ZRANGE key start stop [WITHSCORES]
功能: 通过索引区间返回有序集合指定区间内的成员
返回值: 区间内元素列表
通过业务上对整个周榜zset进行维护，同时设置zset key的过期时间及配置对应归档和删除key的定时任务，即可完成整个周榜功能。
好友榜（区域榜）
好友榜具有用户个人属性，如果在个人维度上单独维护，考虑到其空间复杂度，O(n*n)，因此不建议使用zset进行维护。使用关系型数据库Mysql，依旧可以复用之前的数据结构，只是在查询时需要带上用户id索引，select * from tb where user_id in ("123","333","4444") order by honor_stars desc,likes desc limit 100，通过explain sql分析，依旧可以看到extra 中有个Using filesort的属性。那么我们就来仔细聊聊Mysql innodb 中filesort的一些原理。
如果order by中的字段与where条件中的字段不一致，那么Mysql在执行时就大概率会采用filesort的方式，其中filesort在Mysql中有两种方式实现，具体选择哪一种跟当前select查询数据行信息所占字节、Mysql配置filesort内存排序最大值（max_length_for_sort_data）的关系。
- 如果我们select字段的小于max_length_for_sort_data配置，直接查询出全部的select字段进入sort buffer进行排序，或利用外部文件进行排序，排序后的结果就能直接组成结果集返回至server层。
- 如果我们select字段的总大小超过了max_length_for_sort_data配置，则需要通过主键索引查出主键id、排序字段等必要属性，然后在sort buffer进行排序后，通过主键id再进行回表查询出全部的select字段数据。
因此从上面看，我们的where条件后的数据一定要配置合理的索引，其次对于select的数据尽量精简，否则超过了max_length_for_sort_data配置，便会导致整个查询多一次回表，多了一次磁盘访问不太友好。即使修改max_length_for_sort_data值的配置，如果我们行字段空间较大，也会导致我们整个排序过程中需要操作的数据量过大，内存占用、查询效率都会受到影响。
点赞状态展示方案
从最开始的交互图我们也可以看到有个用户的点赞总数及当前用户针对某个榜单用户的点赞状态。点赞个数这个方案相对比较简单，直接累加就可以了，点赞状态这个就相对棘手，如果要准确的数据，那么就需要我们保存全部的用户关系，重点讨论。
对于点赞状态我们可以预估出如果存储这些数据，它的空间复杂度为O(n*k)k为用户量 n为榜单用户，量级还是挺大的，那么我们就可以考虑到使用布隆过滤器（bloom filter）来去做针对每个用户对于单个榜单中用户的点赞状态。bloom filter是一个典型的使用空间和时间来换取准确率的一种算法和数据结构。如下图所示：它实际上是由一个很长的二进制向量和一系列随机映射函数来实现，布隆过滤器可以用于检索一个元素是否在一个集合中，优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难，错误率是在于由于多个key的多个hash值还是有可能落到同一个slot的，就会导致检查该元素是否在布隆过滤器中返回一个已经错误存在的假象。
因此如果业务对这个点赞状态是否完全准确不做太多要求，而且不需要该用户被那些具体的用户点赞过，那么我们完全可以使用布隆过滤器来作为我们的持久化数据，具体用法为每个榜单上的用户创建一个bloom filter数据，其他用户的点赞状态都会通过多个hash函数散列到二进制向量中，可以对点赞状态进行记录和回查，只是在选择hash函数、创建二进制向量时需要根据用户总量做出调整。
其次如果业务需要完全准确的点赞状态展示，而且针对于单个用户的点赞人需要展示，那么我们就必须将这些点赞关系存入关系型数据库中持久化结构如下，额外的我们依旧可以使用布隆过滤器来做前置的校验条件。比如如果用户A查询用户B的布隆过滤器数据，显示未给榜单中用户B点赞，那就说明是肯定没在榜单中的，如果显示已给榜单中的用户B点过赞，由于布隆过滤器的元素存在准确性问题，我们还需要进入到数据库中确认该点赞关系是否真的存在。这个方案也是新浪微博早期展示用户对于该微博点赞状态的优化方案，对于一些大V用户微博点赞状态的查询不会给数据库带来较大的压力。
| 列名 | 含义 |
|---|---|
| id | 主键id |
| user_id | 用户id |
| liked_user_id | 被点赞用户id |
redisson布隆过滤器api示例
本人是java技术栈，所以也使用了Redisson中对于bloom filter的实现，可以灵活的调整预估元素个数及接受的准确率，Redisson会自行初始化该bloom filter的hash函数及二进制向量即位图的空间大小。
@Service
public class RedissonService {
@Autowired
RedissonClient redissonClient;
public void test() {
RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("bloom-filter");
//初始化bloom filter，预估100000个点赞数据，0.00001的误差容忍度
bloomFilter.tryInit(100000, 0.00001);
for (int i = 0; i < 1000; i++) {
bloomFilter.add("瓜田李下 " + i);
}
System.out.println("'瓜田李下 1'是否存在：" + bloomFilter.contains("瓜田李下 " + 1));
System.out.println("'海贼王'是否存在：" + bloomFilter.contains("海贼王"));
System.out.println("预计插入数量：" + bloomFilter.getExpectedInsertions());
System.out.println("容错率：" + bloomFilter.getFalseProbability());
System.out.println("hash函数的个数：" + bloomFilter.getHashIterations());
System.out.println("插入对象的个数：" + bloomFilter.count());
}
}
//maven 引用
<!-- https://mvnrepository.com/artifact/org.redisson/redisson-spring-boot-starter -->
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.13.6</version>
<exclusions>
<exclusion>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-data-23</artifactId>
</exclusion>
</exclusions>
</dependency>
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-data-21</artifactId>
<version>3.13.6</version>
</dependency>
上面的讨论也仅限于榜单分页的页中数据量没那么大的情况，如果单页显示数据量过大，那么相应的点赞状态需要去多个布隆过滤器中依次验证的效率则是我们需要考虑的事情了。出现了上面的情况，我们还不如直接批量查库来得实在，配置好联合索引，select * from tb where user_id = A and liked_user_id in (B,C,D,E,F)。而使用关系型数据库持久化对应的点赞关系数据，O(n*n)的空间复杂度如果n过于大，则需要考虑使用分库分表的方案，分片键值得考究，简单考虑的话建议采用liked_user_id即被点赞的人id为分片键，这样我们既可以满足单条筛选用户A对于用户B的点赞状态sql，又能满足用户B被点赞全部用户列表查询。
总结
本文我们主要探讨了关于使用关系型数据库Mysql或Redis zset实现排行榜中的总榜、周榜、关系榜的相关方案，对于其中sql优化、缓存方案等提供了思路，排行榜在使用Mysql时要灵活的运用explain和optimize trace等功能；最后也对其中一个相对比较常见的点赞状态展示，我们可以通过布隆过滤器来做空间复杂度的优化，但是也要考虑到业务真实情况来做灵活的调整。