500G 数据需要排序但只有 4G 内存，如何实现？

日期：2026-07-11
标签：#面试 #八股 #后端 #外部排序 #场景题

一句话答案

使用外部归并排序：分批读入内存排序生成有序段，再通过多路归并顺序读写磁盘得到最终结果。

面试口语版

500G 放不进 4G 内存，所以先预留程序和缓冲区空间，例如每次读取 2G 数据，在内存排序后写成一个有序临时文件，得到约 250 个有序段。第二阶段用最小堆做 K 路归并，每个文件只保留一小块读缓冲，堆中保存各段当前最小元素，反复弹出并补充，写入输出缓冲。若一次无法打开这么多文件或内存不足，就分多轮归并。瓶颈主要是磁盘 I/O，应尽量顺序读写、使用大块缓冲和多盘并行。

原理拆解

flowchart LR
  A[500G输入] --> B[分块读取]
  B --> C[内存排序]
  C --> D[多个有序段]
  D --> E[K路最小堆归并]
  E --> F[最终有序文件]

生成初始段复杂度约为各分块排序之和。
K 路归并每条记录进行一次 log K 堆操作。
可使用置换选择生成平均更长的初始有序段，减少归并轮数。

关键细节

先问记录大小、排序 Key、稳定性、磁盘数量和允许耗时。
临时空间通常至少需要接近一份输入大小，必须评估磁盘容量。
数据倾斜对范围分区并行排序影响很大，需采样确定分区边界。
分布式场景可使用 MapReduce/Spark 的 Shuffle Sort，但原理仍是分区加外部归并。

面试官追问

K 取多大合适？
如何减少归并轮数？
排序过程中机器宕机如何恢复？
多块磁盘如何并行？

面试官追问参考答案

1. K 取多大合适？

受可用内存、每路读缓冲、输出缓冲、文件句柄和堆操作成本共同限制。K 越大归并轮数越少，但每路缓冲更小且随机切换更多；应先保证足够大的顺序读缓冲，再在文件句柄上限内压测选择。

2. 如何减少归并轮数？

增大初始内存块、用置换选择生成更长有序段、提高单次归并路数，或用更多机器按范围分区并行排序。核心是减少初始段数量和提高每轮合并规模，但不能牺牲顺序 I/O 效率。

3. 排序过程中机器宕机如何恢复？

每个有序段写临时文件，完成刷盘和校验后原子登记到任务清单；归并输出也按阶段生成新文件并记录输入列表。重启后删除未完成临时文件，从最近完整阶段继续，最终文件通过原子重命名或元数据切换发布。

4. 多块磁盘如何并行？

将输入段和临时段均匀分布到不同磁盘，独立线程做顺序读写，避免同一磁盘同时承担读写热点。归并时从多盘并行预取到缓冲区，输出写另一块磁盘；并发度以磁盘实际带宽和队列延迟为准。

学习清单

能画出“分块排序 + 多路归并”流程。
能分析内存、临时磁盘和文件句柄约束。