面经策

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

  • 标签：后端、场景题

🏛 业务架构师 ​

500G 数据 4G 内存排序是典型的外部排序问题，我先给标准解法，再讲工程上的真实选择。

标准解法：分块排序 + 多路归并

  1. 切分：每次读 4G 内存能容纳的块（比如 1G 数据），在内存内排序（快排），写回磁盘临时文件——得到约 500 个各自有序的块
  2. 归并：对 500 个有序文件做 K 路归并，用**小顶堆（或败者树）**维护每个块的当前元素，每次取出全局最小值写出，复杂度 O(N log K)
  3. 磁盘剩余足够时可以两阶段：先归并成少量大文件再最终归并，减少同时打开的文件句柄
java
// K路归并核心：小顶堆取当前K个块的最小元素
PriorityQueue<Record> heap = new PriorityQueue<>(comparator);

优化方向：I/O 是瓶颈而非 CPU——增大块大小减少归并趟数、利用顺序读写、压缩临时文件。

工程上的真实答案（架构师视角）

真实业务里我不会用 Java 单机写外排，而是：

  • 直接用平台：Spark/Hive 一行 sort by 就完成，框架自动处理切分、排序、落盘、容错——500G 对分布式集群是分钟级任务
  • 先问业务：排序的目的是 TopN（销量榜）还是全序（对账文件）？TopN 用堆保留前 N 即可，根本不用全排；对账要全序但可以用 join 代替排序
  • 再问数据：如果 key 茳围有限（如按用户 ID 分桶），先 hash 分桶再桶内排序，可以并行且天然有序

收尾：这题考的排序思路是基础，但**"知道什么时候不该手写、用什么现成工具、能不能把问题等价变换得更便宜"才是架构师的价值。**

🏗 系统架构师 ​

500G 数据、4G 内存，排序必须用外部排序：分块排序 + 多路归并。

算法流程

  1. 切分排序：每次读约 1G 数据（留足排序和缓冲空间）在内存排好，写回磁盘临时文件。共产生约 500 个有序块。
  2. 多路归并：每个块各开一个小读缓冲（比如 4MB），用小顶堆或败者树维护 500 路的当前元素，每次取出全局最小值写出，补入对应路的下一个元素。堆的高度是 log500 ≈ 9，代价可控。
  3. 如果 500 路并发打开文件太多/缓冲太大，可做两阶段归并：先 50 路归并成 10 个大块，再 10 路归并成最终结果，用轮次换单轮路数。

容量与性能估算（体现架构师习惯）

  • 500 块 × 4MB 输入缓冲 + 8MB 输出缓冲 ≈ 2G 左右，卡在 4G 限制内。
  • 瓶颈是磁盘顺序读写：SSD 500MB/s 的话，读写共约 1.5~2TB 流量，理论几十分钟到小时级，内存排序本身占比很小。

工程优化

  • 第一阶段就是 MapReduce 的 map，归并就是 reduce，有集群条件直接 Spark/MapReduce，每台机器排本地分片再全局归并，把时间从小时压到分钟。
  • 若数据特性允许，可跳过比较排序：数值域有限就用计数排序/桶排序，按高位分桶天然有序，只需一遍分布。
  • 压缩临时文件（有序数据压缩率高）能显著降 IO。

核心思想一句话：内存装不下就让"有序性"分阶段建立，任何时刻内存里只保留每路的一个小窗口。

💻 全栈开发专家 ​

经典外部排序：分块排序 + 多路归并，4G 内存当缓冲区用。

思路

  1. 每次读约 500MB~1GB 数据进内存，快排后写临时文件，得到约 500~1000 个有序块。
  2. 对所有临时文件做 K 路归并：每个文件维护一个读指针，用小顶堆（或败者树）每次取全局最小值写出，堆操作 O(logK)。归并阶段用双缓冲：一边排序写盘、一边归并读盘，IO 与计算重叠。

务实做法：先上 Linux 自带 sort

bash
sort -S 2G -t, -k1,1 input.txt -o sorted.txt

-S 限定内存 buffer，超出自动走外部排序（临时文件 + 归并），性能久经考验。生产上除非有特殊逻辑（多字段、业务比较器），我不会手写。

Java 手写要点

  • 归并用 BufferedReader 每块预读一批进堆，别一行一行裸读。
  • 大文件场景优先 FileChannel 顺序读写，减少系统调用。

踩过的坑

  • 临时文件目录要预留 2 倍源文件大小的磁盘，注意清理，我见过把根分区写满的。
  • 数据有重复需要去重时，归并时跳过相邻重复值即可，一步到位。
  • 如果只是要 TopN 或特定统计，别全排序，用堆或分桶（按 hash 分文件再各自处理）省得多。