在推荐系统中，如何高效计算Top-K视频给用户？假设有百万级视频，用户请求需要快速返回前100个推荐视频，请设计一个分布式排序方案，并说明如何保证排序的准确性和效率。
快手算法类难度：中等
答案
1) 【一句话结论】
采用分布式分片（二次哈希+随机偏移分散热门视频）+本地预排序+多阶段归并方案，通过并行计算与通信优化，高效返回全局Top-K，同时保障排序准确性。
2) 【原理/概念讲解】
推荐系统Top-K的核心是平衡效率与准确性。传统单机排序因数据量巨大效率低，需分布式方案：
- 分片（Sharding）：视频按特征（如视频ID哈希+随机偏移）分片，每个节点负责一个分片。热门视频通过二次哈希（如
shard_id = (hash(video_id) + random_offset) % num_nodes）分散到不同节点，避免单点过载（类比：把大书架按书籍ID哈希分成小书架，热门书籍通过随机偏移分散，每个小书架负载均衡）。 - 预排序（Pre-sorting）：每个节点对本地分片计算用户-视频得分（如用户特征向量与视频特征向量的点积），本地排序后取Top-K（本地Top-K，如每个节点取100个）。统一得分计算规则，确保排序逻辑一致。
- 多阶段归并（Multi-stage Merge）：所有节点汇总本地Top-K结果，先合并相邻节点（如节点0与1合并，节点2与3合并），再逐步合并至全局，减少通信开销（类比：先合并两个小书架的Top100，再合并合并后的结果与其他小书架，逐步形成全局Top100）。通过分阶段合并，降低网络通信量，提升整体效率。
3) 【对比与适用场景】
| 方法 | 定义 | 特性 | 使用场景 | 注意点 |
|---|---|---|---|---|
| MapReduce风格（本地排序+合并） | 分片后本地排序，再多阶段归并 | 并行处理，依赖排序键一致性 | 规模较大，数据更新频率低（如离线推荐） | 合并阶段可能成为瓶颈，数据倾斜时需额外处理 |
| 分布式排序树（如Trie） | 用树结构存储排序键，支持动态插入和Top-K查询 | 支持实时更新，查询响应快 | 小规模Top-K（如千级），实时推荐 | 构建和维护树成本高，不适合百万级数据 |
| 多阶段归并（优化版） | 分阶段逐步合并本地Top-K结果（如2-2合并，再逐步扩展） | 通信开销小，适合大规模Top-K | 百万级视频Top-K，需高效合并 | 需合理设计合并阶段数量（如节点数n时，合并阶段数约为log2(n)），避免过度合并导致延迟 |
4) 【示例】
以100个节点处理百万视频，用户请求Top100为例：
- 分片：视频ID按二次哈希分片，如
shard_id = (hash(video_id) + random_offset) % 100（假设100个节点，随机偏移范围0-99，分散热门视频）。 - 本地排序：节点i处理本地分片（如1万视频），计算用户-视频得分，排序后取Top100（本地Top-K）。
- 多阶段归并：
- 先合并相邻节点（节点0与1合并，节点2与3合并，共50组）。
- 再合并这50组结果（如合并第1组与第2组，逐步扩展），最终得到全局Top100。
伪代码（简化多阶段归并）：
def shard(video_id, num_nodes, random_offset):
return (hash(video_id) + random_offset) % num_nodes
def local_sort(node_id, video_ids, user_features):
local_top_k = []
for vid in video_ids:
score = calculate_score(user_features, video_features[vid])
local_top_k.append((vid, score))
local_top_k.sort(key=lambda x: x[1], reverse=True)
return local_top_k[:100]
def multi_stage_merge(local_results, num_nodes):
merged = []
for i in range(0, len(local_results), 2):
merged.append(merge_two(local_results[i], local_results[i+1]))
while len(merged) > 1:
new_merged = []
for i in range(0, len(merged), 2):
new_merged.append(merge_two(merged[i], merged[i+1]))
merged = new_merged
return merged[0]
5) 【面试口播版答案】（约90秒）
“面试官您好，针对百万级视频的Top-K推荐，我会设计一个分布式分片+预排序+多阶段归并的方案。核心思路是将视频库按特征分片到多个节点并行处理，再逐步合并结果。具体来说：
第一步，分片：按视频ID哈希+随机偏移将百万视频分成N个分片，每个节点负责一个分片（比如100个节点，每个节点处理1万视频，热门视频通过二次哈希分散到不同节点，避免单点过载）。
第二步，预排序：每个节点对本地分片计算用户-视频得分（如用户特征与视频特征的点积），本地排序后取Top100（本地Top-K）。
第三步，多阶段归并：所有节点将本地Top-K结果汇总，先合并相邻节点结果（如节点0与1合并，节点2与3合并），再逐步合并至全局，减少通信开销。
这样既利用并行计算提升效率（每个节点处理部分数据，避免单机瓶颈），又通过统一得分计算规则和多阶段归并保证准确性，最终快速返回结果。比如，100个节点并行处理，比单机排序快约50-100倍（实际需根据节点数和通信开销调整，避免夸张表述），同时确保推荐结果符合用户需求。”
6) 【追问清单】
- 问：如何处理数据倾斜？（如热门视频集中在一个节点）
回答要点：用哈希分片结合随机偏移，或对热门视频二次哈希，分散到不同节点，避免单点过载。例如，热门视频ID的哈希值固定，通过随机偏移（如0-99）调整分片位置，确保负载均衡。 - 问：合并阶段是否会成为瓶颈？
回答要点：用多阶段归并（先合并相邻节点，再逐步合并），减少通信量。例如，100个节点时，先合并成50组，再合并成25组，最终1组，通信开销随阶段减少。 - 问：视频/用户特征更新时，如何保证实时性？
回答要点：采用增量更新（离线预排序加入新数据），或在线流排序维护Top-K，结合缓存机制平衡实时性与效率。例如，新视频加入时，更新本地分片，并触发增量归并。 - 问：排序规则是否固定？冷启动用户如何处理？
回答要点：冷启动用户加入行为/内容相似度特征，或使用基于内容的推荐，确保排序规则覆盖不同用户场景。例如，冷启动用户用视频内容特征（如标签、类别）计算得分，避免因行为数据不足导致排序偏差。
7) 【常见坑/雷区】
- 忽略数据倾斜：直接按ID哈希分片导致热门视频集中，排序结果不准确（如热门视频得分过高，影响全局Top-K）。
- 合并阶段通信开销：未考虑网络延迟，导致整体效率下降（如合并阶段节点间通信量过大，成为性能瓶颈）。
- 实时性 vs 离线预排序的平衡：完全离线无法处理实时更新，完全在线效率低（需结合增量更新和缓存）。
- 分片策略选择：分片方式（哈希/范围/一致性哈希）影响负载均衡，选择不当导致节点负载不均（如范围分片导致冷热不均）。