经典案例：海量数据 Top-K 与实时排行榜系统¶

无论是微博热搜、B站热门视频排行榜、游戏天梯排行榜，还是电商平台的“热销商品 Top 100”，实时排行榜与 Top-K 统计都是系统设计面试中的超高频必考题。

初学者在面对这类题目时，往往容易混淆两类截然不同的业务诉求： 1. 精准排行榜（Exact Leaderboard）：如游戏排位榜，需要精准知道张三排第 1 名、李四排第 2 名，要求百分之百准确； 2. 海量流式近似 Top-K（Heavy Hitters）：如全网每秒数百万次搜索中统计最热的 100 个搜索词，数据量达百亿级，内存根本存不下所有词，允许微小的统计误差，追求极高的吞吐与恒定的内存占用。

1. 需求分析与系统范围 (Requirements & Scope)¶

1.1 功能性需求¶

积分/频次更新：用户的积分或搜索词的频次增加时，实时更新排名；
查询 Top-K 榜单：快速获取当前排名前 \(K\)（如 Top 100）的用户/事件列表；
查询个人排名与周边：查询指定用户的当前排名（Rank）、当前积分（Score）以及前后邻近排名的用户。

1.2 非功能性需求¶

高并发写入 (High Write Throughput)：支撑 \(50,000\sim 100,000\text{ QPS}\) 的上报更新；
极低读取延迟 (Low Read Latency)：榜单查询必须在 \(10\text{ ms}\) 以内返回；
实时性 (Real-Time)：积分变动后，榜单变动应在数秒内对全局用户可见。

2. 场景一：精准实时排行榜 (基于 Redis Sorted Set)¶

在游戏排位、用户积分等中等规模场景下（用户量在数千万以内），Redis 的有序集合（Sorted Set / ZSET）是工业界的绝对标准首选。

2.1 为什么 Redis ZSET 如此高效？底层原理剖析¶

graph TD
    subgraph "Redis ZSET 内部结构"
    HashTable["哈希表 (Hash Table)<br>Key: 成员名 (如 'player:101')<br>Value: 积分分值 (如 2500)<br>查询个人分值: O(1)"]
    SkipList["跳表 (Skip List)<br>按分值从低到高建立多层索引链表<br>插入/删除/更新分值: O(log N)<br>按排名范围检索: O(log N + M)"]
    end

哈希表：保证以 \(O(1)\) 时间复杂度根据用户 ID 查询该用户的当前积分；
跳表（Skip List）：跳表是一种带有层级索引的链表。在跳表中，搜索、插入、更新任何一个元素的时间复杂度均为 \(O(\log N)\)。同时，跳表节点中维护了 span（跨度）属性，使得计算某个节点的绝对排名（ZRANK）耗时也是极其高效的 \(O(\log N)\)。

2.2 核心命令速查与实战¶

# 1. 给玩家增加积分 (若不存在则新增，存在则累加)
ZINCRBY leaderboard 50 "player_1001"

# 2. 查询排名前 3 的玩家 (从高到低排序，包含分数)
ZREVRANGE leaderboard 0 2 WITHSCORES
# 返回: 1) "player_1001", 2) "2550", 3) "player_1002", 4) "2400"...

# 3. 查询某个玩家的当前名次 (从高到低，0 表示第 1 名)
ZREVRANK leaderboard "player_1001"

# 4. 查询某个玩家的具体分数
ZSCORE leaderboard "player_1001"

2.3 当用户量达到 1 亿时：Redis ZSET 单 Key 瓶颈与分桶优化¶

如果系统有 1 亿个用户，一个 ZSET 的内存占用将超过数个 GB，且单 Key 的所有写操作都会落在 Redis 的单线程上，产生严重的 CPU 性能瓶颈。

解决方案：按分数段分桶（Score-Based Bucketing）¶

现实中大部分人的分数都是低分，高分玩家极少。我们可以按照分数区间将排行榜拆分为多个独立的 ZSET：

graph TD
    A[上报玩家得分] --> B{判断玩家分数区间}
    B -->|Score >= 2000| C["王者桶 (ZSET: bucket_king)<br>仅存几千人, 竞争最激烈"]
    B -->|1000 <= Score < 2000| D["黄金桶 (ZSET: bucket_gold)<br>存几十万人"]
    B -->|Score < 1000| E["青铜桶 (ZSET: bucket_bronze)<br>海量玩家, 仅用于个人排名查询"]

    Client[用户请求 Top 100] --> C

查询 Top 100：直接查询 bucket_king 即可，完全不需要扫描数千万的低分用户，性能提升数百倍；
计算全服排名：全服排名 = 大于该玩家所在桶的所有桶成员总数 + 该玩家在当前桶内的相对排名。各个桶的成员总数可以通过 ZCARD 以 \(O(1)\) 快速获取。

3. 场景二：海量流式数据 Top-K 统计 (Count-Min Sketch + 最小堆)¶

当场景切换到“每秒 100 万次搜索，统计过去 1 小时被搜索次数最多的 Top 100 关键词”时，不同的搜索词（Key）可能多达数百亿个。 任何单机或分布式缓存都无法在内存中保存数百亿个 Key 的频次映射！

工业界的标准解法是结合两大算法：Count-Min Sketch（空间极小的概率计数器）+ Min-Heap（小顶堆维护当前 Top-K）。

graph TD
    Stream["数据流 (海量搜索请求: 'chatgpt', 'iphone', 'nba'...)"] --> Worker["流式计算引擎 (Flink / Spark)"]

    subgraph "核心处理组件 (恒定内存占用)"
    CMS["1. Count-Min Sketch (二维哈希计数矩阵)<br>以极小内存估算当前 Query 的出现频次"]
    Heap["2. 最小堆 (Min-Heap, 容量 K = 100)<br>堆顶是当前第 100 名的频次"]
    end

    Worker --> CMS
    Worker --> Heap
    CMS -.->|返回估算频次| Heap
    Heap --> Cache[定时刷新到 Redis 榜单缓存]

3.1 核心算法 1：Count-Min Sketch (CMS) 计数矩阵¶

Count-Min Sketch 类似于布隆过滤器（Bloom Filter），但它不是用来判断“是否存在”，而是用来估算“出现的频次”。

内部结构：¶

一个由 \(d\) 行、\(w\) 列组成的二维整数数组（初始全为 0）；
\(d\) 个相互独立的哈希函数 \(h_1, h_2, \dots, h_d\)，每个哈希函数将输入映射到 \([0, w-1]\)。

        Column 0    Column 1    Column 2  ...  Column w-1
Row 1: [   0    ]  [   15   ]  [   0    ] ... [   2    ]   <- h1(x)
Row 2: [   8    ]  [   0    ]  [   15   ] ... [   1    ]   <- h2(x)
...
Row d: [   0    ]  [   20   ]  [   15   ] ... [   0    ]   <- hd(x)

工作流程：¶

更新频次（Add）：
当收到一个单词 \(x\) 时，分别用 \(d\) 个哈希函数计算列位置：\(c_1 = h_1(x), c_2 = h_2(x), \dots, c_d = h_d(x)\)；
将对应位置的计数器分别加 1：Matrix[i][c_i] += 1。
查询频次（Estimate）：
查询单词 \(x\) 的频次时，取出所有 \(d\) 个位置的值：

\[ \text{Estimated Count} = \min_{1 \le i \le d} \text{Matrix}[i][h_i(x)] \]

为什么取最小值（Min）？¶

因为哈希碰撞只会让某个位置的计数值虚高（Over-count），而绝不可能变小。因此，\(d\) 个位置中的最小值是最接近真实频次的估计值！

3.2 核心算法 2：结合最小堆维护 Top-K (Min-Heap)¶

我们维护一个容量固定为 \(K = 100\) 的最小堆 (Min-Heap)： - 堆中的元素为 (Query, Estimated_Count)； - 堆顶元素是当前 Top 100 中频次最低的那一个。

实时流处理逻辑：¶

收到一个 Query \(q\)；
更新 Count-Min Sketch 计数器，并获取其最新估算频次 \(cnt\)；
检查是否能进入 Top-K 堆：
若 \(q\) 已经在堆中：更新其分值为 \(cnt\)，并调整堆结构；
若 \(q\) 不在堆中：
- 若当前堆元素不足 100 个：直接将 \((q, cnt)\) 压入堆中；
- 若堆已满且 \(cnt > \text{min\_heap.top().count}\)（即大于当前堆顶元素的频次）：将当前堆顶元素弹出，并将 \((q, cnt)\) 插入堆中！

通过这种机制，我们只需要一个几兆字节（MB）的 Count-Min Sketch 矩阵和一个仅含 100 个节点的内存小顶堆，即可在恒定极小的内存下，轻松处理每秒数十万甚至数百万的流式高频词统计！

4. 全链路工业级生产架构 (End-to-End Architecture)¶

将上述组件串联为端到端的高可用系统：

graph TD
    Client[海量用户客户端] --> Gateway[API 网关 / 负载均衡]

    subgraph 数据采集与缓冲
    Gateway --> Kafka[(消息队列 Kafka: 解耦与防压垮)]
    end

    subgraph 实时计算引擎
    Kafka --> Flink[Apache Flink 流处理集群]
    Flink --> CMS[Count-Min Sketch + Min-Heap<br>滑动窗口聚合: 统计最近 1 小时]
    end

    subgraph 结果缓存与展示
    Flink -->|每 5 秒输出一次 Top 100| Redis[(Redis 榜单缓存)]
    User[用户打开热搜榜] --> QueryAPI[查询服务 API]
    QueryAPI --> Redis
    end

客户端上报：用户的所有搜索、点击行为由前端异步上报到 API 网关；
Kafka 削峰：网关只做数据合法性校验，立即将事件写入 Kafka 消息队列，彻底解耦计算与上报；
Flink 流处理：
采用滑动时间窗口（Sliding Window）（例如：每 5 秒计算一次过去 1 小时的数据）；
在每个 Window 内利用 Count-Min Sketch 统计频次并用 Min-Heap 维护 Top 100；
结果缓存刷新：每 5 秒计算完成后，将最新的 Top 100 榜单写入 Redis 缓存；
用户查询：前端用户刷新热搜榜时，直接读取 Redis 缓存，响应时间小于 \(5\text{ ms}\)，轻松应对亿级并发查询。