1. 排序这件事远没有课本上讲的那么简单干了十多年开发面试过的人没有一百也有八十我发现一个特别有意思的现象几乎每个人都能把快排、归并、堆排的原理讲得头头是道但一旦问到“给你一个200GB的日志文件内存只有16GB怎么按时间戳排序”能答上来的人瞬间少了一大半。这个分水岭恰恰就是内部排序和外部排序的分界线。内部排序说白了就是所有待排序的数据能一次性装进内存CPU可以随意跳跃访问任意元素我们比拼的是比较次数、交换次数、缓存命中率。而外部排序数据量大到内存根本放不下必须借助磁盘这种外部存储核心矛盾从“比较快不快”变成了“磁盘IO少不少”。这两个场景的优化思路几乎是正交的用内部排序的思维去做外部排序性能会惨不忍睹。这篇内容我打算把这两块彻底讲透。从内部排序的选型逻辑、每种算法的真实适用边界到外部排序的归并趟数计算、置换选择生成初始归并段、败者树优化再到实际工程里怎么把这些理论落地。适合有一定数据结构基础、但在真实项目里被大数据排序坑过的开发者也适合正在准备技术面试、想把这块知识串成体系的朋友。我不会只给你结论每个参数怎么算出来的、为什么这么选都会掰开揉碎讲清楚。2. 内部排序不是越快越好而是越合适越好2.1 先搞清楚你到底在排什么很多人一上来就问“哪个排序算法最快”这个问题本身就问错了。排序算法的选择取决于四个维度数据规模、数据初始状态、元素结构、稳定性要求。我见过太多人不管三七二十一直接上快排结果遇到大量重复元素时性能退化到O(n²)或者需要稳定排序时傻了眼。先看一张我整理的对照表这是选型的第一手依据算法平均时间最坏时间空间稳定性适用场景直接插入O(n²)O(n²)O(1)稳定n50基本有序希尔排序O(n^1.3)O(n²)O(1)不稳定中等规模内存敏感冒泡排序O(n²)O(n²)O(1)稳定教学用实际不用快速排序O(nlogn)O(n²)O(logn)不稳定通用首选随机数据归并排序O(nlogn)O(nlogn)O(n)稳定要求稳定链表排序堆排序O(nlogn)O(nlogn)O(1)不稳定求TopK内存极紧计数排序O(nk)O(nk)O(k)稳定整数范围小基数排序O(d(nk))O(d(nk))O(nk)稳定定长整数/字符串这张表不是让你背的是让你在动手前先问自己几个问题数据量多大有没有可能已经部分有序元素是整数还是对象相等元素的原始顺序要不要保留把这几个问题回答清楚选型基本就定了。2.2 快排为什么是通用首选以及它什么时候会翻车快速排序的平均时间复杂度是O(nlogn)常数因子在所有比较排序里最小加上原地排序、缓存友好所以它是绝大多数标准库的默认选择。C的std::sort、Java的Arrays.sort对基本类型、Python的list.sort底层都是快排的变体通常是内省排序Introsort。但快排有两个致命弱点必须提前防住。第一个是最坏情况退化。当每次选的枢轴都是当前区间的最小值或最大值时递归深度变成n时间复杂度退化成O(n²)。什么情况下会这样数据已经有序或逆序而你恰好每次都取第一个元素做枢轴。解决办法很简单随机化枢轴或者三数取中。三数取中就是取左端、中间、右端三个元素的中位数作为枢轴实测下来对近乎有序的数据提升非常明显。第二个是大量重复元素。标准的两路划分会把等于枢轴的元素分到某一侧导致重复元素多时划分极度不平衡。这时候要用三路划分把数组分成小于、等于、大于枢轴三段等于段不再参与递归。我处理过一批用户行为日志里面时间戳精度只到秒大量记录时间戳相同换成三路快排后耗时从8秒降到了1.2秒。import random def quick_sort_three_way(arr, lo, hi): if lo hi: return # 随机选枢轴并交换到lo位置 rand_idx random.randint(lo, hi) arr[lo], arr[rand_idx] arr[rand_idx], arr[lo] pivot arr[lo] lt lo # arr[lo..lt-1] pivot gt hi # arr[gt1..hi] pivot i lo 1 while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[gt], arr[i] arr[i], arr[gt] gt - 1 else: i 1 quick_sort_three_way(arr, lo, lt - 1) quick_sort_three_way(arr, gt 1, hi)注意快排的递归深度在极端情况下可能达到n对于百万级数据有栈溢出风险。工程上要么用显式栈模拟递归要么在递归深度超过2logn时切换到堆排序这就是内省排序的思路。2.3 归并排序的不可替代性在哪里归并排序的时间复杂度稳定在O(nlogn)没有最坏退化而且是稳定排序。这两个特性决定了它在某些场景下是唯一选择。场景一要求稳定排序。比如电商订单先按金额排序金额相同的要保持下单时间顺序。快排和堆排都做不到归并可以。Java里对对象数组排序用的就是归并TimSort对基本类型才用快排就是因为对象排序通常需要稳定性。场景二链表排序。链表的随机访问是O(n)快排的划分操作会变得很低效。而归并排序天然适合链表合并两个有序链表只需要改变指针空间复杂度可以做到O(1)。LeetCode上那道“排序链表”的题标准解法就是归并。场景三外部排序的基础。这个后面会详细讲外部排序的核心就是多路归并归并排序的思想直接决定了外部排序的性能上限。归并排序的代价是需要O(n)的额外空间。在内存紧张的场景下可以用原地归并如手摇算法但会把时间复杂度推到O(n²)或者实现极其复杂。我的建议是除非内存真的卡死否则老老实实用O(n)辅助空间的版本代码简单、不易出错、性能稳定。2.4 堆排序TopK问题的王者堆排序在通用排序场景下不如快排因为它的缓存不友好——每次访问的元素在内存里跳来跳去CPU缓存命中率低。但在求TopK这个特定问题上堆是无可替代的。求一个10亿数据里的最大100个数你不可能全排序。正确做法是维护一个大小为100的小顶堆遍历数据如果当前元素大于堆顶就替换堆顶并调整堆。遍历完后堆里就是最大的100个数。时间复杂度O(nlogk)空间O(k)k100时几乎可以忽略。import heapq def top_k_largest(nums, k): heap nums[:k] heapq.heapify(heap) # 小顶堆 for num in nums[k:]: if num heap[0]: heapq.heapreplace(heap, num) return heap实操心得求最大K个用小顶堆求最小K个用大顶堆别搞反了。原理是堆顶是当前候选集中最“差”的那个新元素只有比它强才有资格进来。2.5 非比较排序打破O(nlogn)下界的前提基于比较的排序算法下界是O(nlogn)这个结论是确定的。但如果你排的不是通用对象而是有范围的整数就可以用计数排序或基数排序突破这个下界。计数排序要求数据范围k不能太大。比如给100万个0到1000之间的整数排序开一个1001的数组统计频次然后按序输出时间复杂度O(nk)比快排还快。但如果范围是0到10亿开数组就不现实了。基数排序适合定长整数或字符串。从最低位到最高位每一位做一次计数排序。d位数就需要d趟每趟O(nk)。比如排100万个手机号11位数字d11k10总复杂度O(11n)实际跑起来比快排快不少。这里有个坑基数排序的k是每一位的取值范围。如果按十进制位排k10如果按二进制位排k2但d变成32或64。通常十进制更划算因为d小。我实测过对100万个随机32位整数排序基数排序十进制d10比快排快约30%。3. 外部排序当数据装不进内存时该怎么办3.1 外部排序的核心矛盾与整体框架外部排序要解决的根本问题是数据量远大于内存容量如何在有限内存下完成排序。这时候性能瓶颈从CPU比较变成了磁盘IO优化目标从“减少比较次数”变成“减少读写磁盘的次数”。外部排序的标准框架分两步阶段一生成初始归并段。把大文件切成若干个小块每块读进内存用内部排序排好写回磁盘。每个排好序的小块叫一个归并段run。阶段二多路归并。把这些有序归并段合并成一个完整的有序文件。举个例子文件200GB内存16GB。阶段一每次读16GB进内存排序写出一个16GB的有序段一共产生约13个归并段。阶段二对这13个段做多路归并。这里的关键参数是归并趟数。如果有m个初始归并段做k路归并归并趟数S ⌈log_k(m)⌉。每趟归并都要把全部数据从磁盘读一遍再写一遍所以总IO次数约等于 2 × S × 数据总量。减少IO的核心就是增大k或减少m。3.2 多路归并的k到底能开多大理论上k越大归并趟数越少IO越少。但k不能无限大因为k路归并时每次从k个段里选最小值需要比较k-1次。如果线性比较总比较次数是 (k-1) × 数据总量k太大CPU扛不住。解决办法是败者树。败者树是一棵完全二叉树k个叶子节点对应k个归并段内部节点记录比较的“败者”胜者继续向上比较。这样每次选最小值只需要O(logk)次比较而不是O(k)。k可以开到几百甚至上千。但k还受另一个因素限制内存缓冲区。k路归并时每个归并段都需要一个输入缓冲区输出还需要一个输出缓冲区。如果k1000每个缓冲区哪怕只有1MB也要1001MB内存。所以k的大小是内存、IO、CPU三者的平衡。我的经验值是k取内存能容纳的缓冲区数量的最大值。假设内存16GB留2GB给输出缓冲剩下14GB分给输入缓冲每个缓冲128KB那么k最大约 14GB / 128KB ≈ 114688。实际不会开这么大因为k超过一定值后IO减少的收益递减而CPU比较开销线性增长。通常k在64到256之间比较合理。3.3 置换选择把初始归并段数量降下来阶段一如果只是简单地把文件切成等大的块分别排序归并段数量m 总数据量 / 内存大小。200GB / 16GB ≈ 13个段。但如果用置换选择算法可以在内存不变的情况下生成更长的归并段从而减少m。置换选择的工作原理维护一个大小为内存容量的最小堆。从文件读数据填满堆然后反复执行输出堆顶元素到当前归并段从文件读下一个元素如果它比刚输出的元素大就插入堆否则暂存到一个“待定区”等当前归并段结束后再用来构建下一个归并段。这样生成的归并段平均长度是内存容量的两倍对于随机数据。也就是说200GB数据、16GB内存简单分块产生13个段置换选择可以产生约7个段。归并趟数从⌈log_k(13)⌉降到⌈log_k(7)⌉k64时都是1趟但k8时前者2趟后者1趟IO直接减半。import heapq def replacement_selection(input_file, output_prefix, mem_size): 置换选择生成初始归并段 run_index 0 with open(input_file, r) as fin: # 初始填充内存 heap [] for _ in range(mem_size): line fin.readline() if not line: break heap.append(int(line.strip())) heapq.heapify(heap) frozen [] # 待定区 current_run [] while heap: min_val heapq.heappop(heap) current_run.append(min_val) line fin.readline() if line: new_val int(line.strip()) if new_val min_val: heapq.heappush(heap, new_val) else: frozen.append(new_val) if not heap: # 当前归并段结束写出 with open(f{output_prefix}_{run_index}, w) as fout: for v in current_run: fout.write(f{v}\n) run_index 1 current_run [] # 用待定区重建堆 heap frozen heapq.heapify(heap) frozen [] if current_run: with open(f{output_prefix}_{run_index}, w) as fout: for v in current_run: fout.write(f{v}\n)注意置换选择对数据初始有序性很敏感。如果数据已经基本有序生成的归并段长度可能远超内存容量甚至一个段就能装下全部数据。但如果数据完全逆序每个归并段长度就只有内存容量退化成简单分块。3.4 归并趟数的精确计算与IO估算假设总数据量N内存容量M初始归并段数量mk路归并归并趟数S ⌈log_k(m)⌉。每趟归并读写各一遍全部数据总IO量 2 × S × N。拿具体数字算一下。N200GBM16GB简单分块m13。k2二路归并S ⌈log_2(13)⌉ 4趟IO 2×4×200 1600GBk8S ⌈log_8(13)⌉ 2趟IO 2×2×200 800GBk64S ⌈log_64(13)⌉ 1趟IO 2×1×200 400GB从k2到k64IO量减少了75%。这就是为什么外部排序一定要用多路归并而且k要尽量大。如果加上置换选择m降到7k8S ⌈log_8(7)⌉ 1趟IO 400GB可以看到置换选择让k8就能达到简单分块k64的效果。在实际工程中这两个优化通常一起用。3.5 败者树的实现细节败者树是多路归并的性能关键。它的结构是一棵完全二叉树叶子节点是k个归并段的当前元素内部节点记录的是“败者”即较大的元素胜者继续向上传递。根节点之上再设一个冠军节点记录最终胜者。class LoserTree: def __init__(self, k): self.k k self.tree [-1] * k # 记录败者的段索引 self.leaves [None] * k # 各段当前值 self.inf float(inf) def adjust(self, s): 从叶子s向上调整败者树 t (s self.k) // 2 # 父节点 while t 0: if self.leaves[s] is None: challenger self.inf else: challenger self.leaves[s] if self.tree[t] -1: self.tree[t] s s s else: loser self.tree[t] if self.leaves[loser] is None or self.leaves[loser] challenger: self.tree[t] s s loser else: s s t t // 2 self.tree[0] s # 冠军 def get_min(self): return self.tree[0]败者树调整一次的时间复杂度是O(logk)k256时只需要8次比较。相比线性扫描的255次比较性能提升超过30倍。这就是为什么k可以开到很大而CPU不会成为瓶颈。实操心得败者树的数组实现比指针实现更高效因为数组内存连续、缓存友好。tree数组的大小是ktree[0]存冠军tree[1..k-1]存内部节点的败者。调整时从叶子向上每次和父节点记录的败者比较胜者继续向上。4. 从理论到落地完整的外部排序实现4.1 整体流程与参数设计把前面的知识串起来一个完整的外部排序实现包含以下步骤参数计算根据文件大小和可用内存确定初始归并段大小、归并路数k、缓冲区大小。阶段一用置换选择生成初始归并段每个段写成一个临时文件。阶段二用败者树做k路归并如果归并段数量大于k需要多趟归并。清理删除临时文件。参数设计上我通常这样定初始归并段大小 可用内存 × 0.8留20%给程序本身和输出缓冲归并路数k min(可用内存 / (缓冲区大小 × 2), 256)缓冲区大小 64KB到1MB之间根据磁盘块大小调整假设可用内存8GB缓冲区256KBk 8GB / (256KB × 2) ≈ 16384取上限256。初始归并段大小 8GB × 0.8 6.4GB。4.2 阶段一置换选择的工程实现置换选择的实现要注意几个细节。第一输入文件的读取要用缓冲流避免频繁系统调用。第二待定区的数据要存在内存里如果待定区太大说明数据逆序严重可以考虑直接落盘。第三每个归并段写完后要记录其元素范围和大小方便后续归并时做优化。import heapq import os def phase_one(input_path, temp_dir, mem_limit_bytes, buffer_size1024*1024): 阶段一置换选择生成初始归并段 # 估算内存能放多少个元素假设每个元素8字节 max_elements mem_limit_bytes // 8 runs [] with open(input_path, rb, bufferingbuffer_size) as fin: heap [] # 初始填充 for _ in range(max_elements): data fin.read(8) if not data: break heap.append(int.from_bytes(data, little)) heapq.heapify(heap) frozen [] run_file None run_count 0 run_size 0 while heap: min_val heapq.heappop(heap) if run_file is None: run_path os.path.join(temp_dir, frun_{run_count}) run_file open(run_path, wb, bufferingbuffer_size) run_size 0 run_file.write(min_val.to_bytes(8, little)) run_size 1 data fin.read(8) if data: new_val int.from_bytes(data, little) if new_val min_val: heapq.heappush(heap, new_val) else: frozen.append(new_val) if not heap: run_file.close() runs.append((run_path, run_size)) run_count 1 run_file None heap frozen heapq.heapify(heap) frozen [] if run_file: run_file.close() runs.append((run_path, run_size)) return runs4.3 阶段二败者树多路归并归并阶段的核心是败者树。每个归并段对应一个输入缓冲区从缓冲区取当前元素参与比较。缓冲区空了就从对应的归并段文件读下一块。class MergeBuffer: def __init__(self, file_path, buffer_size): self.f open(file_path, rb, bufferingbuffer_size) self.buffer_size buffer_size self.buffer [] self.pos 0 self._fill() def _fill(self): data self.f.read(self.buffer_size) self.buffer [] for i in range(0, len(data), 8): if i 8 len(data): self.buffer.append(int.from_bytes(data[i:i8], little)) self.pos 0 def current(self): if self.pos len(self.buffer): return self.buffer[self.pos] return None def advance(self): self.pos 1 if self.pos len(self.buffer): self._fill() def close(self): self.f.close() def phase_two(runs, output_path, k, buffer_size1024*1024): 阶段二k路归并 # 如果归并段数量超过k先分组归并 while len(runs) k: new_runs [] for i in range(0, len(runs), k): group runs[i:ik] merged_path group[0][0] _merged merge_group(group, merged_path, buffer_size) new_runs.append((merged_path, sum(r[1] for r in group))) runs new_runs # 最后一趟归并到输出文件 merge_group(runs, output_path, buffer_size) def merge_group(runs, output_path, buffer_size): 归并一组归并段 k len(runs) buffers [MergeBuffer(r[0], buffer_size) for r in runs] # 构建败者树 tree [-1] * k leaves [buf.current() for buf in buffers] def adjust(s): t (s k) // 2 while t 0: if tree[t] -1: tree[t] s break loser tree[t] if leaves[loser] is None or (leaves[s] is not None and leaves[s] leaves[loser]): tree[t] s s loser t t // 2 tree[0] s for i in range(k): adjust(i) with open(output_path, wb, bufferingbuffer_size) as fout: while tree[0] ! -1: winner tree[0] if leaves[winner] is None: break fout.write(leaves[winner].to_bytes(8, little)) buffers[winner].advance() leaves[winner] buffers[winner].current() adjust(winner) for buf in buffers: buf.close()4.4 性能实测与调优记录我用这套实现处理过一个150GB的日志文件内存限制8GB机械硬盘。记录几个关键数据配置归并段数归并趟数总耗时IO量简单分块k21954h22m1500GB简单分块k641911h08m300GB置换选择k6410152m300GB置换选择k12810148m300GB从k2到k64耗时从4小时降到1小时提升非常明显。置换选择把归并段从19降到10虽然归并趟数都是1但阶段一的写入量减少了所以又快了16分钟。k从64加到128提升只有4分钟说明k超过64后收益递减。实操心得机械硬盘的随机IO性能极差一定要用大缓冲区做顺序读写。我把缓冲区从64KB调到1MB后阶段一的写入速度提升了近3倍。如果是SSD缓冲区可以小一些因为SSD的随机IO性能好很多。5. 踩过的坑与排查技巧实录5.1 内存溢出缓冲区不是越多越好我最初实现时为了减少IO把k开到了512每个缓冲区1MB结果内存直接爆了。算一下512个输入缓冲 1个输出缓冲 513MB看起来不多但Java的每个缓冲区对象还有额外开销加上败者树、临时对象实际内存占用是理论值的2到3倍。排查方法用Runtime.getRuntime().totalMemory()和freeMemory()监控实际内存或者用/usr/bin/time -v看峰值内存。解决技巧缓冲区大小和k的乘积不要超过可用内存的60%留足余量给JVM或运行时本身。5.2 归并段数量计算错误导致多趟归并有一次我算错了归并段数量以为k64能一趟归并完结果实际产生了70个段程序自动做了两趟归并性能直接翻倍。问题出在阶段一的估算上我用文件大小除以内存大小但置换选择生成的段长度是变化的不能简单除。正确做法阶段一每生成一个归并段就记录下来阶段二开始前根据实际段数决定归并策略。如果段数略大于k可以增大k或者接受两趟归并如果远大于k说明内存估算有问题需要调整。5.3 败者树调整逻辑写错导致死循环败者树的调整逻辑很容易写错特别是边界条件。我见过最常见的错误是当某个归并段已经读完current返回None时没有正确处理导致败者树一直选中这个空段陷入死循环。排查方法在adjust函数里加日志打印每次比较的段索引和值。解决技巧把空段的值视为正无穷这样它永远不会胜出。当所有段都为空时冠军节点的值也是正无穷循环终止。5.4 临时文件磁盘空间不足外部排序会产生大量临时文件总大小可能达到原文件的2到3倍。我有一次处理500GB数据临时目录只挂了1TB的盘跑到一半磁盘满了程序崩溃。预防措施开始前估算临时空间需求。最坏情况下阶段一产生的归并段总大小等于原文件大小阶段二每趟归并产生的新文件也等于原文件大小。如果做S趟归并峰值磁盘占用约等于原文件大小 × (S1)。提前检查磁盘剩余空间不够就清理或者换目录。5.5 常见问题速查表问题现象可能原因排查方法解决方案程序OOMk或缓冲区过大监控峰值内存降低k或缓冲区大小归并趟数超出预期归并段数估算错误打印实际段数调整阶段一参数或增大k归并阶段死循环空段处理错误打印败者树状态空段值设为正无穷磁盘写满临时空间不足检查磁盘剩余清理空间或换目录速度远低于预期缓冲区太小监控IOPS增大缓冲区到1MB以上结果不正确稳定性被破坏检查相等元素顺序归并时优先取靠前的段5.6 一个容易被忽略的优化预读和写回操作系统本身有页缓存但外部排序的数据量太大页缓存根本装不下。我们可以用posix_fadviseLinux或FILE_FLAG_SEQUENTIAL_SCANWindows告诉操作系统这是顺序访问让它调整预读策略。另外写入时用O_DIRECT绕过页缓存避免双重缓冲浪费内存。这些优化在机械硬盘上效果明显能提升20%到30%的吞吐。SSD上提升较小因为SSD本身没有寻道开销。6. 内部排序与外部排序的边界与融合6.1 什么时候该用外部排序判断标准很简单数据量是否显著超过可用内存。如果数据能装进内存内部排序永远更快因为省去了磁盘IO。如果装不下就必须用外部排序。但有个中间地带数据量是内存的1到2倍。这时候可以用内存映射文件mmap让操作系统帮你管理换入换出。mmap的优点是代码简单像操作内存一样操作文件缺点是页错误不可控性能不稳定。我的经验是数据量小于内存2倍时可以用mmap试试超过2倍老老实实外部排序。6.2 数据库是怎么做排序的数据库的排序操作ORDER BY本质上就是外部排序。以MySQL为例它有两种排序策略全字段排序把查询需要的所有字段都读进sort buffer排好后直接返回。适合字段少、行数少的情况。rowid排序只把主键和排序字段读进sort buffer排好后根据主键回表查其他字段。适合字段多、行数多的情况因为sort buffer能放更多行。当sort buffer装不下时MySQL会生成临时文件做归并排序。sort_buffer_size参数控制sort buffer大小max_length_for_sort_data控制切换全字段和rowid的阈值。调大sort_buffer_size可以减少临时文件但会消耗更多内存。6.3 分布式排序的思路数据量大到单机磁盘都装不下时就需要分布式排序。核心思路是分治归并先按范围把数据分到多台机器每台机器内部做外部排序最后做多路归并。分片的关键是选好分片键。比如按时间戳排序可以按时间范围分片每台机器负责一个时间段。这样归并时只需要按时间顺序拼接不需要复杂的比较。如果分片键选得不好导致数据倾斜某些机器负载过高整体性能会被拖垮。分布式排序的归并阶段通常用归并网络或者锦标赛树和单机的败者树原理类似只是节点分布在不同的机器上。网络传输成为新的瓶颈所以压缩和批量传输很重要。6.4 一个实际案例日志分析系统的排序优化某日志分析系统每天处理2TB日志需要按时间戳排序后入库。最初用单机外部排序耗时6小时。后来做了三个优化预分区日志写入时按小时分目录每个目录内的日志时间戳范围已知。排序时只需要对每个小时目录内部排序然后按时间顺序拼接。这样把全局排序变成了局部排序归并段数量从几百降到几十。并行化阶段一用多线程并行生成归并段每个线程处理一个日志文件。阶段二用败者树做多路归并k开到256。SSD缓存把临时文件放在SSD上归并阶段的IO速度提升5倍。优化后耗时从6小时降到40分钟。这个案例说明外部排序的性能不仅取决于算法还取决于数据组织和硬件选型。7. 一些零散但重要的经验7.1 稳定性在外部排序中同样重要外部排序的归并阶段当两个归并段的当前元素相等时应该优先取靠前归并段的元素。因为靠前的归并段包含的是原始数据中更靠前的部分这样能保持稳定性。这个细节很容易被忽略但在需要稳定排序的场景下至关重要。7.2 小文件合并可以减少归并段数量如果输入是大量小文件不要每个文件生成一个归并段。可以先把小文件合并成较大的文件再生成归并段。比如1000个1MB的小文件先合并成10个100MB的文件归并段数量从1000降到10归并趟数大幅减少。7.3 监控指标比调优参数更重要外部排序调优时不要盲目调参数。先监控几个关键指标归并段数量、归并趟数、每趟耗时、磁盘IO吞吐、CPU利用率。根据指标定位瓶颈再针对性调优。如果磁盘IO已经跑满调大k也没用如果CPU利用率很低说明IO是瓶颈应该增大缓冲区或换SSD。7.4 代码实现要防御性编程外部排序涉及大量IO和内存操作出错概率高。关键位置要加校验归并段数量是否一致、每个段的大小是否匹配、输出文件的行数是否等于输入。我习惯在归并结束后统计输出文件的行数和输入对比不一致就报警。这个简单的校验帮我发现过好几次隐蔽的bug。7.5 测试要用真实数据用随机数据测试外部排序性能往往比真实数据好。因为真实数据通常有倾斜、有重复、有局部有序性。我建议测试时至少用三种数据完全随机、完全有序、大量重复。这三种情况覆盖了大多数极端场景能暴露大部分问题。8. 最后分享几个实用技巧如果你只需要排一个几百GB的文件不想自己写外部排序可以用现成的工具。Linux的sort命令支持外部排序sort -S 8G -T /tmp --parallel4 bigfile.txt sorted.txt-S指定内存大小-T指定临时目录--parallel指定并行度。实测下来sort命令的性能相当不错因为它内部就是用归并排序加多路归并实现的。如果是在Java里可以用ExternalSort这类开源库或者自己基于FileChannel和ByteBuffer实现。Python的话pandas的read_csv支持分块读取配合heapq.merge可以做简单的多路归并但性能不如专门的外部排序库。还有一个技巧如果数据是数值型且范围有限可以先用计数排序做一轮预排序把数据分成若干有序的桶再对每个桶做外部排序。这样每个桶内部已经基本有序归并段长度会很长归并趟数减少。我在实际项目里最深的体会是外部排序的瓶颈永远在IO不在CPU。所有的优化都应该围绕减少IO展开。增大k、用置换选择、用SSD、用大缓冲区本质上都是在减少磁盘读写次数。把这一点想明白调优的方向就不会错。
