京东一面：16GB文件4GB内存怎么排序？服务宕机了怎么办？九成人答不圆-尧图网络科技

前两天有个读者找我，说他面京东后端岗，一面项目聊得还行，八股也过得去，结果面试官最后甩了两个场景题，直接把他干懵了。

第一题：给你一个 16GB 的文件，机器内存只有 4GB，怎么让文件内容全局有序？

第二题：如果排序过程中服务宕机了怎么办？

他说第一题勉强答了个"外部排序"，但讲得稀碎——分块怎么分、归并怎么归、堆怎么用，全是模糊的。第二题更惨，直接卡住，说了句"加个 checkpoint"，面试官追了一句"checkpoint 怎么设计，归并到一半宕机了输出的半个文件怎么办"，他彻底接不住。

这两题其实是面试场景题里的经典组合：第一题考算法基本功，第二题考工程容错能力。看起来是两个独立的问题，但如果你第二题答得好，面试官会知道你不只是刷过 LeetCode，而是真正处理过大规模数据。

今天我把这两题拆开聊，每一层都给你讲到落地细节。

如果你也在准备后端面试，这篇建议存下来反复看。

第一题：16GB 文件，4GB 内存，如何全局有序？

不要急着说"外部排序"

很多人一听这道题，条件反射蹦出四个字："外部排序"。

面试官点点头，然后问："具体怎么做？"

你就卡住了。

外部排序不是一个算法，是一类方案的统称。面试官要听的是你能不能把分而治之的思想落地成具体的执行步骤，每一步在干什么、为什么这么干、有什么坑。

第一步：分块排序

16GB 文件，4GB 内存。最直觉的想法是把文件切成小块，每块能在内存里排完。

但切多大？

很多人脱口而出："切成 4GB 一块，正好放内存。"

这是第一个坑。

4GB 是机器总内存，不是你能拿来排序的内存。操作系统要占内存，JVM 自身有开销，堆外内存、GC、线程栈都要空间。真正能用来装数据的，可能只有 2~2.5GB。

所以稳妥的做法是按 2GB 切分，留足余量。

然后每次读一个 chunk 进内存，用快速排序或 TimSort 排好，写回磁盘成一个独立的临时文件。

这一步结束后，磁盘上有 8 个临时文件，每个文件内部有序，但文件之间无序。

第二步：多路归并

现在问题变成了：有 8 个各自有序的文件，怎么合并成一个全局有序的文件？

这就是K 路归并问题。

最笨的办法：每次从 8 个文件里暴力比较当前元素，取最小值。每次比较 O(K)，总共 N 个元素，时间复杂度 O(N×K)。K=8 时还能接受，但如果 chunk 切得更小，K 变成 100 甚至 1000，这个方案就废了。

正确的做法：最小堆（优先队列）。

每个文件维护一个读取指针，先把每个文件的第一个元素放进最小堆。堆顶就是全局最小值，取出来写入结果文件，然后从该元素所在的文件读下一个元素放进堆里。循环直到堆空。

sorted_chunk_1: [1, 3, 5, 7, ...] ─┐ sorted_chunk_2: [2, 4, 6, 8, ...] │ sorted_chunk_3: [0, 9, 10, 15, ...] ├──→ 最小堆 → 全局最小值 → 写入结果 ... │ sorted_chunk_8: [11, 12, 13, ...] ─┘

每次取最小值 O(logK)，总共 O(N×logK)，效率高得多。

这里有个容易被忽略的内存细节：归并阶段虽然不把整个 chunk 读进内存，但 K 个文件各需要一个读缓冲区，外加一个输出缓冲区。假设 8 路归并、每路缓冲区 64MB、输出缓冲区 128MB，光缓冲区就要 8×64+128 = 640MB。如果 4GB 总内存刨去 OS 和 JVM 开销后只剩 2~2.5GB，这部分也要纳入预算。

伪代码

// ========== 第一阶段：分块排序 ========== List<File> sortedChunks = new ArrayList<>(); byte[] buffer = new byte[CHUNK_SIZE]; // 2GB int chunkIndex = 0; while (readNextChunk(bigFile, buffer) > 0) { // 读入内存 → 排序 → 写临时文件 long[] data = deserializeToLongArray(buffer); Arrays.sort(data); File sortedFile = writeTempFile(data, "sorted_" + chunkIndex++); sortedChunks.add(sortedFile); } // ========== 第二阶段：多路归并 ========== PriorityQueue<FileReader> minHeap = new PriorityQueue<>( Comparator.comparingLong(FileReader::current) ); // 每个文件一个 reader，取首元素入堆 for (File chunk : sortedChunks) { FileReader reader = new FileReader(chunk); if (reader.hasNext()) { reader.advance(); minHeap.offer(reader); } } // 不断取堆顶最小值，写入最终文件 while (!minHeap.isEmpty()) { FileReader min = minHeap.poll(); output.write(min.current()); if (min.hasNext()) { min.advance(); minHeap.offer(min); } }

面试官追问：还能优化吗？

到这里，如果你只是把基本流程讲清楚，面试官会觉得"还行，基础可以"。但真正拉开差距的是追问环节。

追问 1：归并路数能不能增加？

可以。多轮归并的触发条件是：chunk 数量超过归并路数 K。比如把 chunk 切成 512MB，16GB 文件会切成 32 块——如果只用 8 路归并，需要 2 轮（32 → 4 → 1）；但如果一次做 32 路归并，堆的高度是 log32=5，只比 8 路归并的 log8=3 多一点，磁盘 IO 只需 1 轮。

简单算笔账：每多一轮归并，就要把全部数据完整读+写一遍。16GB 数据多一轮就是多 32GB 的磁盘 IO，代价很大。

路数越多，磁盘 IO 轮数越少，但堆操作开销增加，同时每个归并路需要一个读缓冲区（假设 64MB/路，32 路就是 2GB），内存压力也上来了。这是个 trade-off，实际工程中通常选 8~16 路。

追问 2：能不能利用操作系统缓存？

能。先算笔账：外部排序总共要做 4 次完整的数据读写——读入分块 + 写出排序 chunk + 读入归并 + 写出最终文件，总 IO 量 ≈ 4×16GB = 64GB。所以 IO 是最大瓶颈，顺序读写能让 OS 的 page cache 自动预读（readahead），实际磁盘 IO 量远小于理论值。写代码时不要搞随机读写，老老实实顺序扫描，让 OS 帮你做缓存优化。

追问 3：如果数据是整数，有没有更快的方案？

有。如果知道数据范围，可以用计数排序或桶排序的思想。先扫一遍文件统计每个值的出现次数（只需要一个计数数组，不存原始数据），然后按值顺序写出。时间复杂度 O(N)，完全不需要归并。

但这个方案的前提是你知道数据范围，且范围不能太大。面试时可以作为"特定场景下的优化"提出来，展示你的思维广度。

第二题：排序过程中宕机了怎么办？

第一题答完，面试官点了点头，接着问："你这个排序过程要跑几分钟，如果中途机器宕机了怎么办？"

很多人在这题上翻车，翻车的方式高度一致——说一句"加个 checkpoint"，然后讲不出任何细节。

面试官要听的不是"加 checkpoint"这五个字，而是：checkpoint 记什么、记在哪、什么时候记、重启怎么恢复、恢复时怎么处理写到一半的脏数据。

核心思路：两阶段 Checkpoint

外部排序分两个阶段，每个阶段的容错策略不同。

阶段一：分块排序阶段

这个阶段的粒度天然是 chunk 级别的。每完成一个 chunk 的排序并写回磁盘，就记录一次进度。

处理流程： chunk1 ✓ → checkpoint: {"completed": [1]} chunk2 ✓ → checkpoint: {"completed": [1,2]} chunk3 ✓ → checkpoint: {"completed": [1,2,3]} chunk4 ✗ ← 宕机！

checkpoint 文件可以这样设计：

{ "phase": "split_sort", "total_chunks": 8, "completed_chunks": [1, 2, 3], "input_offset": 6442450944 }

重启后：读 checkpoint → 跳过已完成的 chunk → 从 chunk4 继续。之前排好的 3 个临时文件还在磁盘上，不用重排。

注意：checkpoint 文件本身的写入也要防宕机。如果写 checkpoint 时机器挂了，checkpoint 就是损坏的——重启后读不出来，整个恢复机制直接废掉。所以 checkpoint 文件同样要用 .tmp + fsync + rename 的原子写策略，和下面归并输出文件的写入策略一模一样。

阶段二：归并阶段

归并阶段比排序阶段更难做 checkpoint。

为什么？因为归并的输出是一个连续写入的大文件，不是按 chunk 独立的。如果归并到 60% 时宕机，输出文件里前 60% 是对的，但后面什么都没有。重启后你不能从头归并（浪费），也不能从 60% 继续（因为归并的指针状态丢了）。

解决方案：把归并输出拆成多个 part 文件。

归并输出： output_part_1.dat (0~4GB) ✓ 已完成 output_part_2.dat (4GB~8GB) ✓ 已完成 output_part_3.dat (8GB~12GB) ✗ 写到一半，宕机 output_part_4.dat (12GB~16GB) 未开始

checkpoint 记录已完成哪些 part，以及每个 part 对应的归并指针位置。

{ "phase": "merge", "completed_parts": [1, 2], "current_part": 3, "merge_pointers": { "chunk_1": 268435456, "chunk_2": 536870912, ... } }

重启后：保留已完成的 part1、part2 → 从 part3 的起始位置重新归并。

最致命的问题：写到一半的文件怎么办？

宕机时，output_part_3.dat 可能只写了一半。这个文件是损坏的，不能直接用。

很多人在这卡住了——知道要 checkpoint，但没想过文件本身的完整性问题。

解决方案：写临时文件 + rename。

写入策略： 1. 归并结果先写到 output_part_3.dat.tmp 2. 写完后调用 fsync() 确保文件数据落盘 3. rename("output_part_3.dat.tmp", "output_part_3.dat") 4. fsync 父目录，确保目录项变更也持久化

rename在 Linux ext4/xfs 文件系统上是原子操作——要么成功（文件完整），要么失败（文件不存在），不会出现"半个文件"的状态。

但有个坑：fsync(fd)只保证文件数据落盘，不保证目录项变更（rename 操作）持久化。如果 rename 之后、目录 fsync 之前宕机，重启后可能文件名还是旧的 .tmp。所以第 4 步要对父目录再fsync一次。这个细节在 SQLite、PostgreSQL 的 WAL 实现里都有体现。

重启后扫描输出目录：

有.tmp后缀的文件 → 上次没写完，直接删除
没有后缀的 part 文件 → 已完成，保留

重启恢复流程： 1. 读取 checkpoint 文件 2. 扫描临时文件目录，删除所有 .tmp 文件 3. 根据 checkpoint 确定从哪个阶段、哪个 part 继续 4. 恢复归并指针，继续执行

这个细节看起来小，但面试官听到你提到rename的原子性和fsync的落盘保证，就知道你是真正写过文件系统层面代码的人，不是纸上谈兵。

面试加分点

1. 能说清楚"为什么 chunk 不能切到 4GB"

"4GB 是机器总内存。操作系统要占一部分，JVM 自身有堆开销和 GC 开销，堆外内存和线程栈也要空间。真正能用来装数据排序的可能只有 2~2.5GB。所以 chunk 切到 2GB，留 1.5~2GB 给 JVM 和 OS。"

2. 能联系实际大数据组件

"外部排序不是教科书概念。Hadoop MapReduce 的 Sort 阶段、Spark 的 ExternalSorter、MySQL 的 filesort，底层全都是这个思路——内存放不下就分块，分块排完再归并。"

3. 能提到文件系统的具体语义

"我用rename而不是直接写目标文件，因为rename在 ext4/xfs 上是原子操作。先写.tmp文件，fsync文件数据之后再rename，最后还要fsync父目录——否则 rename 的目录项变更可能没落盘，宕机后文件名还是旧的。这套写法在 SQLite、PostgreSQL 的 WAL 里都有。"

4. 能讲清楚 checkpoint 的设计权衡

"checkpoint 本身也要写磁盘，如果每处理一条数据就记一次，checkpoint 的写入会成为瓶颈。所以 checkpoint 的粒度要和业务粒度对齐——分块排序按 chunk 记，归并按 part 记，既不会太频繁，也不会丢太多进度。另外 checkpoint 文件自身的写入也要防宕机——同样用 .tmp + fsync + rename，否则写 checkpoint 时宕机，恢复机制本身就废了。"

总结

问题	核心考点	关键词
16GB 文件排序	外部排序算法	分块排序、多路归并、最小堆、IO 优化
服务宕机恢复	工程容错能力	Checkpoint、原子写、fsync、rename、临时文件清理

这两题串起来，本质上在考一件事：