如何设计一个排行榜？

发表于 更新于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

你好，我是猿java。

设计排行榜是一项复杂且多方面的任务，它涉及数据存储、排序算法、缓存、并发控制和性能优化等多个方面。这篇文章，我们将详细地分析几种常见的技术方案。

什么是排行榜？

排行榜（Leaderboard）是一种根据某个指标进行排序并展示的系统。

在现实生活中，排行榜的场景特别多，下面列举常见的一些类型：

游戏领域

  • 玩家积分排行榜：根据玩家在游戏中的得分、等级、成就等，进行排名。
  • 公会/团队排行榜：根据公会或团队的综合得分或成就，进行排名。

电子商务

  • 销售排行榜：根据商品的销售量或销售额，进行排名。
  • 用户贡献排行榜：根据用户的购买量、评论数、贡献值等，进行排名。

社交媒体

  • 内容热度排行榜：根据帖子、视频、图片等内容的点赞数、评论数、分享数等，进行排名。
  • 用户影响力排行榜：根据用户的粉丝数、互动量等，进行排名。

教育领域

  • 学生成绩排行榜：根据学生的考试成绩、作业完成情况等，进行排名。
  • 学习进度排行榜：根据学生的学习进度、课程完成情况等，进行排名。

体育领域

  • 运动员成绩排行榜：根据运动员的比赛成绩、积分等，进行排名。
  • 团队成绩排行榜：根据球队的比赛成绩、积分等，进行排名。
  • 步数排行榜：比如微信运动步数排行榜

财经领域

  • 股票排行榜：根据股票的涨跌幅、成交量等，进行排名。
  • 公司市值排行榜：根据公司的市值、营收等，进行排名。

娱乐领域

  • 电影票房排行榜：根据电影的票房收入，进行排名。
  • 音乐排行榜：根据歌曲的播放量、下载量等，进行排名。

健康与健身

  • 健身排行榜：根据用户的运动量、消耗的卡路里等，进行排名。
  • 健康数据排行榜：根据用户的健康数据（如步数、心率等），进行排名。

科技与创新

  • 专利排行榜：根据公司或个人的专利数量、创新指数等，进行排名。
  • 科技公司排名：根据公司的技术实力、市场表现等，进行排名。

旅游与酒店

  • 旅游景点排行榜：根据景点的游客数量、评价等，进行排名。
  • 酒店排行榜 ：根据酒店的入住率、评价等，进行排名。

通过上述列举的场景，我们可以发现它们都存在一个共同的规律：排名，只不过排名的指标不一样而已，因此，设计排行榜绝对不是纸上谈兵，它们在实际生活中的场景太多了。

技术方案

通过上面的介绍，我们已经知道了什么是排行榜以及现实生活中哪些场景存在排行榜，那么，如何设计一个排行榜？这里给出 5种常见的方案：

  1. 数据库排序
  2. 数据库 + Redis
  3. 分布式系统
  4. 基于NoSQL数据库
  5. 最小堆 + Redis

在本文中，我们将用户的排名指标统一抽象成score。

数据库排序

实现

实现排行榜，最简单，最直接的一种方法是使用关系型数据库（如 MySQL）来存储和排序数据，其表结构设计和查询排行的 SQL语句如下：

数据库表结构：

1
2
3
4
CREATE TABLE leaderboard (
    user_id INT PRIMARY KEY,
    score INT NOT NULL
);

获取排行榜的SQL查询：

1
SELECT user_id, score FROM leaderboard ORDER BY score DESC LIMIT 10;

这种方法充分利用了关系型数据库的排序功能，直接通过 SQL查询来获取排行榜。

优缺点

优点：

  • 简单直接，易于实现。
  • 利用数据库的索引和排序功能，无需额外的逻辑。

缺点：

  • 当数据量较大时，查询和排序的性能可能会成为瓶颈。
  • 每次查询都需要访问数据库，可能导致较高的延迟。

数据库 + Redis

实现

为了提高性能，我们可以在内存中缓存排行榜数据，同时定期从数据库同步数据。在这种方法中，我们使用缓存（如Redis）来存储排行榜数据，减少对数据库的访问。

对于数据库，表结构还是和上面的保持一致，如下：

1
2
3
4
CREATE TABLE leaderboard (
    user_id INT PRIMARY KEY,
    score INT NOT NULL
);

对于缓存结构，我们使用 Redis的有序集合（Sorted Set）来存储排行榜数据，有序集合是一个高效的数据结构，适合存储和排序排行榜数据。我们可以在内存中快速获取排行榜，同时定期将数据同步到数据库以持久化。

优缺点

优点：

  • 高性能，读取和写入操作都非常快速。
  • 减少了对数据库的直接访问，降低了数据库的负载。

缺点：

  • 需要处理缓存一致性问题。
  • 需要额外的内存来存储缓存数据。

注意事项

使用 Redis来存储排行榜数据时，需要注意以下问题：

1. TopN问题

对于排行榜，一般只会关注前 N名，比如前 1000名，后面的排名其实已经不重要了，所以只要保证前 1000名的排名是正确的话就问题不大

2. 大 Key 问题

如果用户数据量比较大，需要注意大 Key问题，可以考虑将一个大的 ZSet 拆分成多个小的 ZSet，因为排行榜一般都是获取前 N名（比如 1000个），然后在获取排行榜时，可以从每个小的 ZSet中获取前 N名，在放到一个新的 ZSet中在取前 N，这样就可以得到最终的排名

3. 内存占用问题

对于排行榜使用缓存时，我们只存储userId和score，而不存储其他无关信息，其他的信息可以根据 userId 回表查询。

假设userId 是 long类型 8个字节，score也是 long类型 8个字节，总共就是16字节，因此，1000万用户，占用的内存是 16字节 * 1000 * 10000 = 10M，亿级用户消耗的内存是 100M 左右，这个内存消耗还是比较低的。

分布式系统

实现

对于更大规模的系统，我们可以采用分布式系统来实现排行榜。例如，使用 Apache Kafka 进行数据流处理，Apache HBase进行数据存储，利用 Apache Spark 进行排序计算。

  • 首先，使用 Kafka 将用户得分数据流式传输到处理系统；
  • 然后，使用 HBase 存储用户得分数据；
  • 最后，使用 Spark进行排序计算，并将结果存储在缓存中（如 Redis）；

这种方法将数据流处理、存储和计算分离，通过分布式系统来提高性能和可扩展性。Kafka处理数据流，HBase存储数据，Spark进行计算，Redis缓存结果。

优缺点

优点：

  • 高可扩展性，适合大规模数据处理。
  • 各个组件可以独立扩展，提高系统的灵活性。

缺点：

  • 系统复杂度高，需要处理分布式系统的协调和一致性问题。
  • 开发和维护成本较高。

基于 NoSQL数据库

实现

使用 NoSQL数据库（如 MongoDB）来存储和查询排行榜数据。MongoDB支持丰富的查询和排序功能，适合存储大规模的排行榜数据。

数据库表结构：

1
2
3
4
{
  "user_id": 1,
  "score": 100
}

利用 NoSQL数据库的高性能和灵活性，存储和查询排行榜数据。可以通过索引和查询优化来提高性能。

优缺点

优点

  • 高性能，适合大规模数据存储和查询。
  • 灵活的文档结构，易于扩展和维护。

缺点

  • 对于复杂查询和事务支持不如关系型数据库。
  • 需要处理数据一致性和分片等问题。

最小堆 + Redis

实现

对于排行榜，一般只会关注前 N名，因此，我们可以使用最小堆 + Redis的方案来实现。

首先，看下最小堆（Min-Heap）的特点：

  • 堆顶元素最小：最小堆的堆顶总是最小元素，这对于维护前 N 大元素非常有用，因为你可以轻松地判断新元素是否应该加入堆中。
  • 高效的插入和删除：插入和删除操作的时间复杂度为 O(log N)，对于维护一个固定大小的排行榜非常高效。

操作流程：

  • 最小堆：在应用层，初始化一个最小堆，堆的大小为 N（排行榜的大小），比如 Java的 PriorityQueue，
  • 映射关系：将 UserId和 Score的映射关系存储在 Redis中，比如，Redis的INCRBY，INCRBY key increment；
  • 插入元素：如果堆的大小小于 N，直接插入；否则，比较新元素和堆顶元素，如果新元素更大，则替换堆顶元素并调整堆；
  • 获取排行榜：堆中的所有元素即为前 N 大元素；

优缺点

优点：

  • 高效的插入和删除操作：最小堆的插入和删除操作时间复杂度为 O(log N)，对于维护一个固定大小的排行榜非常高效。 榜。
  • 固定大小的内存使用：由于最小堆的大小是固定的（即排行榜的大小 N），内存使用是可控的，不会因为数据量的增加而无限增长。
  • 实现简单易实现

缺点：

  • 不适用于实时更新：如果数据频繁更新，维护最小堆的开销可能较大，因为每次更新都需要进行堆的调整。
  • 只适用于固定大小的排行榜：最小堆适合维护固定大小的排行榜，但如果排行榜的大小需要动态调整，可能需要额外的处理逻辑。

总结

本文分析了实现排行榜5种方案的整体思路：

  1. 数据库排序
  2. 数据库 + Redis
  3. 分布式系统
  4. NoSQL数据库
  5. 最小堆 + Redis

设计排行榜涉及多个方面，包括数据存储、排序算法、缓存、并发控制和性能优化等，不同的技术方案各有优缺点，因此，在实际开发中，需要根据具体的业务需求和数据规模来决定采用什么方案。

学习交流

如果你觉得文章有帮助，请帮忙转发给更多的好友，或关注公众号：猿java，持续输出硬核文章。

drawing