知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 大文件排序 > 导读:本文围绕经典面试题"10GB 文件、每行一个整数、内存只有 1GB,怎么排序",讲清外部排序(External Sort)的思路、完整实现、复杂度与生产优化手段。适合准备后端面试,以及需要处理"数据量超过内存容量"这类问题的开发同学。 ## 一、先建立全局认知 ### Q:为什么 10GB 的文件不能直接读进 1GB 内存排序? A:结论先行:因为基于比较的内存排序(如 `Collections.sort`)要求所有待排数据同时驻留内存。10GB 数据远大于 1GB 可用内存,直接读取会触发 OOM(Out Of Memory,内存溢出)。 所以这道题的约束不是"排序算法不够快",而是"数据规模超过了内存容量"。约束一变,解法就要换一类:把"在内存里排一次序"升级为"在磁盘上分批排序 + 多路归并",这就是外部排序。 先给术语一个定义:**外部排序**指数据量大于内存、必须借助外存(磁盘)并通过多次读写才能完成排序的一类排序方法。它的核心不是某个具体算法,而是一种"分而治之 + 有序归并"的组织方式。 ### Q:外部排序的核心思路是什么? A:三个动作:分、排、并。把大文件切成若干能装进内存的小块,每块在内存里排好序写回磁盘,最后把所有有序小块归并成一个有序大文件。 ``` 内存装不下全部数据 → 分批处理 → 归并合并 步骤: 1. 分割:将 10GB 文件分成若干个小文件,每个小文件能装入内存 2. 排序:对每个小文件在内存中排序,写回磁盘 3. 归并:多路归并所有小文件,输出最终有序文件 ```  *图:外部排序的三个阶段——分割、内存排序、多路归并,数据在内存与磁盘之间分批流转。* [编辑 Excalidraw 源图](/images/java-interview-copy/concurrent/09-large-file-sort-large-file-sort-external-merge-sort-diagram.excalidraw) 这套方案的设计取舍很直白:用额外的磁盘空间(临时文件,量级为 O(N))换取内存占用可控;用更多的磁盘 I/O 次数换取算法在有限内存下可执行。如果内存足够,没人愿意做外部排序——它天生是为"内存装不下"这一约束服务的。 ## 二、理解核心机制 ### Q:外部排序的完整实现怎么写? A:下面是一份可直接运行的最小实现,分两步:`splitAndSort` 负责分割并在内存中排序,`mergeFiles` 用最小堆做多路归并。 ```java public class ExternalSort { private static final int CHUNK_SIZE = 100_000; // 每批处理 10 万行 private static final String TEMP_DIR = "/tmp/sort/"; public static void sort(String inputFile, String outputFile) throws IOException { // 第一步:分割并排序 List<String> tempFiles = splitAndSort(inputFile); // 第二步:多路归并 mergeFiles(tempFiles, outputFile); // 清理临时文件 tempFiles.forEach(f -> new File(f).delete()); } // 第一步:将大文件分割成多个有序的小文件 private static List<String> splitAndSort(String inputFile) throws IOException { List<String> tempFiles = new ArrayList<>(); List<Long> buffer = new ArrayList<>(CHUNK_SIZE); int fileIndex = 0; try (BufferedReader reader = new BufferedReader(new FileReader(inputFile))) { String line; while ((line = reader.readLine()) != null) { buffer.add(Long.parseLong(line.trim())); if (buffer.size() >= CHUNK_SIZE) { // 内存中排序,写入临时文件 String tempFile = writeSortedChunk(buffer, fileIndex++); tempFiles.add(tempFile); buffer.clear(); } } // 处理最后一批 if (!buffer.isEmpty()) { tempFiles.add(writeSortedChunk(buffer, fileIndex)); } } return tempFiles; } private static String writeSortedChunk(List<Long> data, int index) throws IOException { Collections.sort(data); String path = TEMP_DIR + "chunk_" + index + ".txt"; new File(TEMP_DIR).mkdirs(); try (PrintWriter writer = new PrintWriter(new FileWriter(path))) { data.forEach(writer::println); } return path; } // 第二步:多路归并(使用最小堆) private static void mergeFiles(List<String> files, String outputFile) throws IOException { // 最小堆:(值, 文件索引) PriorityQueue<long[]> heap = new PriorityQueue<>( Comparator.comparingLong(a -> a[0]) ); // 为每个文件创建 reader,读取第一个元素 List<BufferedReader> readers = new ArrayList<>(); for (int i = 0; i < files.size(); i++) { BufferedReader reader = new BufferedReader(new FileReader(files.get(i))); readers.add(reader); String line = reader.readLine(); if (line != null) { heap.offer(new long[]{Long.parseLong(line.trim()), i}); } } try (PrintWriter writer = new PrintWriter(new FileWriter(outputFile))) { while (!heap.isEmpty()) { long[] min = heap.poll(); writer.println(min[0]); // 写出最小值 // 从该文件读取下一个元素 int fileIdx = (int) min[1]; String nextLine = readers.get(fileIdx).readLine(); if (nextLine != null) { heap.offer(new long[]{Long.parseLong(nextLine.trim()), fileIdx}); } } } // 关闭所有 reader for (BufferedReader reader : readers) { reader.close(); } } } ``` 读这段代码时抓住两个关键点: - 分割阶段每次攒够 `CHUNK_SIZE` 行就排一次序并落盘,所以任意时刻内存里最多只有一批数据,内存占用是常数级。 - 归并阶段为每个临时文件各开一个 `BufferedReader`,只把"当前读到的那个元素"放进堆,而不是把整个文件读进内存。 ### Q:归并阶段为什么用最小堆,而不是每次遍历 k 个文件找最小值? A:因为 k 路归并的本质是反复执行同一个动作——"从 k 个有序序列的当前队首中取出最小值"。用最小堆来做,每次取最小值的代价从遍历的 O(k) 降到 O(log k),而总共要取 N 次,于是归并阶段从 O(N·k) 优化到 O(N·log k)。k 越大(临时文件越多),堆带来的收益越明显。 这也是"选对数据结构"的典型案例:算法骨架没变,只是把"找最小"这一步换成更合适的容器。 ### Q:这套算法的时间与空间复杂度是多少? A:可以用原文给出的估算模型来理解(前提假设见下),结论是总时间复杂度和纯内存排序同量级,额外代价是 O(N) 的磁盘空间。 ``` 假设:文件 10GB,内存 1GB,每行 10 字节,共 10 亿行 分割阶段: 每批 1 亿行(约 1GB),共 10 批 每批排序:O(N/k × log(N/k)),k=10 总时间:O(N log(N/k)) 归并阶段: 10 路归并,每次从堆中取最小值 堆操作:O(log k),共 N 次 总时间:O(N log k) 总时间复杂度:O(N log N)(和内存排序相同量级) 额外磁盘空间:O(N)(临时文件) ``` 要注意这里的"复杂度"只刻画了比较次数,真实的墙钟时间还受磁盘 I/O 主导——外部排序通常不是 CPU 瓶颈,而是 I/O 瓶颈。这一点直接决定了下面优化点的优先级。 ### Q:有哪些可以落地的优化点? A:按"优先从 I/O 入手"的思路,原文给出了五个方向: ``` 1. 增大内存利用率 使用 int[] 而不是 List<Integer>(减少对象开销) int[] 比 Integer[] 节省 4 倍内存 2. 增大 I/O 缓冲区 BufferedReader/Writer 的缓冲区设大一些(如 8MB) 减少系统调用次数 3. 并行化 分割阶段:多线程并行处理多个 chunk 归并阶段:多级归并(先 10 路归并成 1 路,再合并) 4. 减少临时文件数量 增大每个 chunk 的大小(用更多内存) 减少归并路数,降低磁盘 I/O 5. 使用内存映射文件(mmap) 大文件读写用 MappedByteBuffer,减少数据拷贝 ``` 从架构师视角看,这几条其实分属两类取舍:1、4 是"用空间换时间"(多占内存、少开文件);2、5 是"降低单次 I/O 开销"(缓冲区、mmap 减少数据拷贝);3 则是"用并发把等待时间重叠起来"。选择哪条,取决于你的瓶颈是 CPU、磁盘吞吐还是文件句柄数。 ## 三、放进真实场景 ### Q:如果文件里有重复数字,如何去重? A:在归并阶段顺手做即可:记录上一个写出的值,如果堆顶元素和它相同,就跳过不写出。因为在每个 chunk 内部已经是有序的、归并又保证了全局有序,所以所有重复值必然相邻出现,一次线性扫描就能去掉。改动很小,代价是几乎为零的一次比较。 ### Q:如果不是整数,而是字符串,如何排序? A:把类型相关的两处改掉,其他逻辑不变:`Long.parseLong` 改为字符串(不解析成数字),`Comparator.comparingLong` 改为 `Comparator.comparing(a -> a[0])` 做字符串比较。相当于把"数值比较"替换成"字典序比较",外部排序的骨架完全不依赖元素类型。 ### Q:这套逻辑放到生产环境,需要注意哪些工程细节? A:结合外部排序的固有特性,重点关注以下几点(症状 → 原因 → 解决): - 磁盘写满导致任务失败。原因:外部排序需要 O(N) 的额外磁盘空间存放临时文件。解决:落盘前预估可用空间,临时目录单独挂盘并设置配额,任务结束后务必删除临时文件(示例代码里 `tempFiles.forEach(f -> new File(f).delete())` 这一步不能省)。 - 归并时文件句柄耗尽。原因:k 路归并要同时打开 k 个 `BufferedReader`,k 很大时可能超过进程的 fd 上限。解决:控制单次归并的路数,临时文件多时改用多级归并(先归并成若干中间结果,再归并中间结果)。 - 任务比预期慢很多。原因:瓶颈通常在磁盘 I/O 而非 CPU。解决:优先调大读写缓冲区、减少临时文件数量与归并轮数,而不是纠结排序算法本身。 - 临时文件命名冲突。原因:并发跑多个排序任务时,若共用同一个 `TEMP_DIR` 且文件名固定,会互相覆盖。解决:每个任务使用独立子目录,或引入 UUID 前缀。 ### Q:什么情况下不该自己写外部排序? A:如果数据最终要进数据库或数仓,直接用数据库/大数据引擎的能力往往更省事——它们内部同样实现了外部排序与本机/分布式归并。自研只在这些场景才划算:数据不在任何存储系统中、需要极致控制内存与 I/O、或需要在单机脚本里完成一次性处理。判断标准很简单:如果"排序"只是更大流程中的一步,优先复用成熟引擎;只有当排序本身就是核心需求、且引擎用不上时才自研。 ## 四、总结与自测 ### Q:面试里怎么答这道题? A:可以按"结论 → 原理 → 实现 → 优化"四点作答: 1. 结论:内存排不下,用外部排序,思路是"分批内存排序 + 多路归并"。 2. 分割:把大文件切成能装进内存的小块,每块内存排序后写回磁盘。 3. 归并:用最小堆做 k 路归并,每次取最小值写出,并顺手可以支持去重;堆把每次取最小值降到 O(log k)。 4. 复杂度与优化:总时间 O(N log N)、额外空间 O(N);瓶颈多在磁盘 I/O,优化优先增大缓冲区、减少临时文件与归并路数,必要时并行化或用 mmap。 ### Q:这道题真正想考察的是什么? A:表面上考外部排序,实际上考三件事:一是遇到"资源装不下"时能否跳出"换更快算法"的思维定式,转向"分治 + 归并"的架构思路;二是能否为一个方案算清时间、空间与 I/O 代价并说出取舍;三是能否把算法落到可运行、可维护的工程实现上。把这三层说清楚,比背出代码更有说服力。 --- ## 自测 1. 用一句话说明外部排序为什么能在 1GB 内存下排 10GB 数据,以及它付出的代价是什么。 2. 归并阶段用最小堆相比线性扫描 k 个文件,复杂度提升了多少?为什么 k 越大收益越明显? 3. 如果临时文件数量非常多,导致文件句柄耗尽,你会怎么改造归并流程? 4. 为什么说外部排序的瓶颈通常在 I/O 而非 CPU?据此,你会优先做哪几项优化?
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入