前两天有个读者找我说他面京东后端岗一面项目聊得还行八股也过得去结果面试官最后甩了两个场景题直接把他干懵了。第一题给你一个 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)。K8 时还能接受但如果 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×64128 640MB。如果 4GB 总内存刨去 OS 和 JVM 开销后只剩 2~2.5GB这部分也要纳入预算。伪代码// 第一阶段分块排序 ListFile 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); } // 第二阶段多路归并 PriorityQueueFileReader 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 切成 512MB16GB 文件会切成 32 块——如果只用 8 路归并需要 2 轮32 → 4 → 1但如果一次做 32 路归并堆的高度是 log325只比 8 路归并的 log83 多一点磁盘 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 不能切到 4GB4GB 是机器总内存。操作系统要占一部分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、临时文件清理这两题串起来本质上在考一件事当数据规模超过单机内存时你能不能既保证算法正确又保证工程可靠。第一题答好说明你算法基础扎实。第二题答好说明你有工程经验、处理过真实的大规模数据场景。两题都答好面试官心里基本有数了。很多人觉得场景题是开卷考试背个方案就行。但面试官追问两层就能看出来——你是真做过还是只是背过。场景题的答案不在脑子里在手上。
的类脑计算实践)
