1. 当内存装不下你的数据外部排序的“生存法则”你有没有遇到过这样的场景手头有一个几十GB甚至上百GB的日志文件需要按时间排序或者数据库里一张大表需要按某个字段重新组织。你兴冲冲地写了个快速排序的脚本一运行内存直接爆了。这感觉就像你要整理一个巨大的图书馆但手边只有一个巴掌大的小书架一次只能放几本书大部分书还堆在遥远的仓库里。这时候你需要的就不是普通的“内部排序”了而是我们今天要聊的外部排序。简单来说外部排序就是专门为“内存装不下”的超大数据集设计的排序方法。它的核心思想很朴素化整为零分批处理再有序合并。想象一下你要整理那座图书馆你会怎么做你可能会先一趟趟地从仓库搬一小摞书到小书架上把这摞书整理好放回仓库的某个角落这就是一个有序的“归并段”。重复这个过程直到所有书都被整理成一小堆一小堆有序的。最后你再想办法把这些有序的小堆合并成一个完整的大有序堆。这个“合并”的过程就是外部排序最核心、也最耗时的部分因为它涉及到在内存和硬盘外存之间来回搬运数据。我处理过很多次类似的场景比如分析全年的用户行为日志文件动不动就几百个G。直接加载机器立马“躺平”。外部排序就是解决这类问题的标准答案而它的效率瓶颈几乎全在I/O输入/输出上。硬盘读写速度相比内存慢了好几个数量级所以外部排序算法的设计目标非常明确尽一切可能减少读写硬盘的次数。为了实现这个目标工程师们发明了三件“神器”败者树、置换-选择排序和最佳归并树。它们分别从不同角度优化这个“搬书-整理-合并”的过程。接下来我就结合自己的实战经验带你看看这三件神器到底怎么用以及如何把它们组合起来打造一个高效的外部排序流程。2. 第一件神器败者树——让多路归并不再“选择困难”当我们把大数据集切分成很多个有序的“归并段”后合并就成了关键。最直接的想法是两两合并但这样合并的趟数会非常多I/O次数自然就上去了。很自然地我们会想能不能一次多合并几个比如一次合并8个、16个甚至更多有序段这就是多路平衡归并的思路。但是问题马上来了。假设我们要做8路归并内存里现在有来自8个归并段的8个当前待比较元素。为了找出其中最小的那个输出最简单的办法就是遍历这8个数需要7次比较。输出这个最小的之后我们需要从它所在的归并段再读入下一个数然后再次在8个数里找最小……如此反复。如果总共要输出N个元素那么光是内部比较的次数就是(N-1)*7次。如果归并路数k增加到16比较次数就变成(N-1)*15。归并路数k增大了虽然合并的趟数减少了但每次内部比较的成本却线性增加了这有点得不偿失。这时候败者树就闪亮登场了。它本质上是一种树形选择排序算法专门高效解决“从k个元素中快速选出最小或最大值”的问题并且在这个最小值被替换后能极快地更新并选出下一个最小值。2.1 败者树是怎么工作的你可以把败者树想象成一场持续进行的“锦标赛”。有k个选手对应k个归并段的当前元素它们两两PK败者被记录在“擂台”树节点上胜者晋级到下一轮。最后根节点记录的是这场锦标赛的“总冠军”也就是当前k个元素中的最小值。但败者树巧妙的地方在于它每个内部节点记录的是这场比赛的“败者”而让“胜者”继续向上比赛。最后我们会额外用一个变量记录“总冠军”即全局胜者。这样做有什么好处呢当总冠军被输出后我们需要从它所在的归并段补充一个新元素进来。此时我们只需要让这个新元素沿着它所在的路径重新和它的老对手即父节点记录的败者进行比较即可而不需要和所有其他k-1个元素重新比一遍。让我举个具体的例子。假设我们有一个3路归并的败者树三个归并段当前在内存中的元素分别是[17, 05, 44]。我们构建一个完全二叉树叶子节点就是这三个元素内部节点用于记录败者。初始化首先叶子节点两两比较。17和05比05胜出17是败者被记录在它们的父节点上。44暂时没有对手因为是3路可能需要一个“极大值”的虚拟节点来凑成偶数我们假设它先胜出。向上比较胜者05和44或虚拟胜者再进行比较05胜出44是败者被记录在更上一级的节点通常是根节点但注意根节点记录的是决赛的败者。此时总冠军是05。输出与更新我们输出总冠军05。然后从05所在的归并段读入下一个数假设是21。现在叶子节点变成了[17, 21, 44]。重构我们不需要重新构建整棵树。只需要让新来的21从它所在的叶子节点出发向上回溯。21先和它兄弟节点对应的老胜者之前是05现在这个位置是21自己比较不对这里有个关键我们比较的对象是父节点记录的“败者”。21首先找到它的父节点父节点记录的老败者是17。于是21和17比较17更小17胜出21成为新的败者被记录在这个父节点上。然后胜者17继续向上和根节点记录的老败者44比较17更小17胜出成为新的总冠军44被更新记录为根节点的败者。看到了吗在整个更新过程中我们只进行了2次比较21 vs 17,17 vs 44。而在普通的遍历方法中我们需要比较21, 17, 44这3个数需要2次比较。虽然这个例子中次数一样但当k很大时优势就极其明显了。败者树每次更新和选择新的总冠军所需的比较次数仅仅是树的高度也就是⌈log₂k⌉。对于k1024也只需要10次比较而普通方法需要1023次注意在实际代码实现中我们通常用一个数组来表示这棵完全二叉树并巧妙地利用下标关系来定位父节点和兄弟节点。每个归并段在叶子节点上的位置是固定的。2.2 实战中的权衡归并路数k不是越大越好用了败者树内部比较的次数从O(k)降到了O(logk)似乎我们可以尽情增大k来减少归并趟数了但事情没那么简单。这里有一个关键的硬件限制内存缓冲区。进行k路归并我们至少需要在内存中为每个归并段维护一个输入缓冲区。如果总内存大小固定比如只有1GB那么k越大每个缓冲区的容量就越小。缓冲区越小意味着每次从硬盘读取的数据块就越小。硬盘的特性是顺序读写大块数据的效率远高于频繁读写小块数据。如果缓冲区太小你会陷入频繁的、细碎的I/O操作中硬盘磁头来回寻道的时间可能远远超过数据传输本身的时间导致总体性能反而下降。所以在我的经验里确定最佳的归并路数k是一个需要权衡和测试的过程。你需要根据总内存大小、硬盘的I/O特性特别是顺序读写带宽以及数据集的大小来综合判断。通常这个值会在几十到几百之间而不是盲目地设置成几千。3. 第二件神器置换-选择排序——生成更长的“有序书堆”回忆一下我们整理图书馆的比喻。传统方法是每次用小书架内存整理一小摞书一个块整理好就放回去形成一个短的有序段。如果内存只能容纳w条记录那么每个初始归并段的长度也就大约是w。归并段的数量r 总记录数n / w这个r会很大导致后续的归并趟数增多。有没有办法在内存大小不变的情况下生成比内存容量w更长的有序段呢置换-选择排序就是为了解决这个问题而生的。它的目标是在单次内存处理中尽可能“吞下”更多数据产生更长的初始归并段从而直接减少归并段的数量r。3.1 算法步骤一个精妙的“选择与置换”过程假设我们有一个待排序的大文件FI一个空的内存工作区WA容量为w和一个用于输出归并段的文件FO。算法步骤如下我尽量用大白话解释初始化从FI中读入w条记录填满WA。选出MINIMAX从WA中选出关键字最小的记录我们称它为MINIMAX记录注意这个名字它既是当前最小也是一个“门槛”。输出把这个MINIMAX记录输出到FO这就是当前归并段的一部分。补充新兵如果FI还没空就从FI中读入下一条记录放入WA中刚才输出记录腾出的空位。设置新门槛现在我们只考虑WA中那些关键字值大于等于刚才输出的那个MINIMAX记录的记录。从这些记录中再选出关键字最小的作为新的MINIMAX记录。为什么要有“大于等于”这个限制这是为了保证现在输出的记录不会比之前输出的记录小从而维持归并段的有序性。循环重复步骤3到5输出新的MINIMAX补充新记录在新门槛下选新的MINIMAX。段结束直到某一步WA中所有记录的关键字都小于当前的MINIMAX门槛了。这说明任何记录如果现在输出都会破坏当前归并段的有序性。于是我们结束当前归并段在FO中输出一个段结束标记比如一个特殊值。重新开始此时WA里还有一堆记录它们都小于之前的MINIMAX。我们以它们为基础重复步骤2到7开始生成下一个归并段。直到FI为空且WA也为空所有归并段生成完毕。这个过程听起来有点绕我画个简单的例子。假设数据是[17, 21, 05, 44, 10, 12]内存WA容量w3。第一轮读入[17, 21, 05]。MINIMAX是05输出05。读入44替换05WA[17, 21, 44]。门槛是05候选有17,21,44最小是17输出17。读入10替换17WA[10, 21, 44]。门槛是17候选有21,4410小于17被排除最小是21输出21。读入12替换21WA[10, 12, 44]。门槛是21候选只有44输出44。FI已空不再读入。门槛是44WA中10,12都小于44没有候选。第一个归并段结束内容是[05, 17, 21, 44]。看长度是4超过了内存容量3第二轮WA里还剩[10, 12]。我们重新开始把它们当作初始数据虽然FI空了。MINIMAX是10输出10。没有新数据可读。门槛是10候选有12输出12。WA为空。第二个归并段结束内容是[10, 12]。最终我们得到了两个归并段第一个长度是4。置换-选择排序生成的归并段平均长度大约是内存工作区大小的两倍。这显著减少了归并段的数量为后续的归并阶段节省了大量I/O。3.2 实现关键用败者树加速选择你可能会注意到算法的第5步“从大于门槛的记录中选最小者”如果每次都用遍历的方法在WA较大时效率不高。没错在实际实现中我们正是用败者树来高效完成这个选择过程的。WA中的记录就是败者树的叶子节点我们能够以O(log w)的复杂度快速选出符合条件的MINIMAX这也是置换-选择排序能高效运行的基础。4. 第三件神器最佳归并树——规划最优的“合并路线图”通过置换-选择排序我们得到了一系列长度各不相同的初始归并段。现在要进行多路归并了。假设我们有5个归并段长度分别为10, 20, 30, 40, 50单位可以是万条记录。我们打算用3路归并k3。该怎么合并呢不同的合并顺序产生的磁盘I/O总量是不同的。因为每次合并都需要把所有参与合并的归并段的数据读一遍再把结果写出去。读写的总量就是这些归并段长度之和。我们的目标是让总的I/O代价最小。这听起来是不是很像一个经典问题给一组带权值的叶子节点归并段长度构造一棵k叉树使得树的带权路径长度WPL最小。没错这就是哈夫曼树的思想最佳归并树就是将哈夫曼树的思想推广到k叉树k2。构造原则很简单每次选择当前长度最短的k个归并段进行合并。这样长度小的段优先被合并参与的合并次数少长度大的段晚被合并虽然它本身大但合并的趟数可能少了。从整体上减少了重复读写的数据量。4.1 处理“非严格k叉树”的情况虚段但是k叉哈夫曼树要求每次合并严格地取k个节点。如果初始归并段的数量m不满足(m-1) % (k-1) 0那么在最开始你就无法凑齐k个段进行合并。例如m5, k3(5-1) % (3-1) 4 % 2 0刚好可以。如果m6, k3(6-1) % (3-1) 5 % 2 1余数为1。这时候就需要添加长度为0的“虚段”。添加虚段的目的是为了让第一次合并能凑够k个。添加多少个呢设余数为u则需要添加(k-1) - u个虚段。上面m6的例子u1需要添加(3-1)-1 1个虚段。这样我们就有617个段包含1个虚段(7-1) % 2 0就可以构造了。在构造时权值为0的虚段应该最先被合并因为它不影响I/O代价所以它应该放在离树根最远的地方也就是在算法中每次我们都优先合并包含虚段的组合因为虚段权值最小。4.2 实战意义I/O代价的直观优化让我们算一笔账。假设有5个段长度[10, 20, 30, 40, 50]进行2路归并k2即普通哈夫曼树。随意合并比如先合并10和20代价30得到新段30再合并30和30代价60得到60再合并40和50代价90得到90最后合并60和90代价150。总I/O代价 306090150 330。最佳归并树哈夫曼先合并10和2030再合并30和3060但此时应合并40和5090吗不哈夫曼法是先合并当前最小的两个30新和40代价70得到70再合并50和60代价110得到110最后合并70和110代价180。总代价 306070110180等等这里计算有误。正确构造是合并102030合并303060合并405090此时有[60,90]合并6090150。总代价306090150330和上面一样不对我们漏算了中间段的写入。实际上每次合并的代价是读入参与合并的所有段写出新段。所以第一次合并10和20代价是10203060读10读20写30。这样算太复杂。更标准的计算是考虑每个原始段的读取次数。在最佳归并树哈夫曼树下每个叶节点的权重乘以其到根节点的路径长度之和WPL最小这个WPL就对应了总的读取次数写次数是固定的等于总数据量。对于[10,20,30,40,50]构造哈夫曼树先102030再303060再405090再6090150。路径长度10和20是330是240和50是2。WPL 103 203 302 402 50*2 30606080100 330。这是读取代价。写入代价是总数据量150每个数据最终被写一次。总I/O代价约为330150480如果计读写。如果换一种糟糕的合并顺序((((1020)30)40)50)路径长度10是420是430是340是250是1。WPL4080908050340。看到了吗最佳归并树的WPL(330)小于糟糕顺序的WPL(340)这意味着更少的磁盘读取次数。在数据量巨大时这节省的I/O时间是非常可观的。在实际的数据库或大数据处理框架中最佳归并树的理念被广泛应用。比如Apache Hadoop的MapReduce在Reduce阶段合并Map输出的中间文件时就会采用类似的优化策略来规划合并顺序以最小化磁盘和网络传输开销。5. 实战串联一个完整的外部排序流程设计理论说了这么多最后我们来串一下在一个真实的大数据排序任务中如何把这些技术用起来。假设我们要排序一个100GB的文本文件每行是一条记录我们的机器内存有4GB。阶段一生成初始归并段我们不会用简单的内部排序来生成固定长度的段。我们会采用置换-选择排序。设置内存工作区WA的大小比如3.5GB留一些给系统和其他缓冲区。从这个100GB文件中持续读入数据进行置换-选择排序。最终我们可能得到大约100GB / (2 * 3.5GB) ≈ 15个长度不等的归并段平均长度约为内存的两倍存储在硬盘上。这比用普通内部排序得到的100/3.5≈29个段要少。阶段二多路归并现在我们有15个归并段需要合并成一个有序文件。规划合并路数k总内存4GB需要k个输入缓冲区1个输出缓冲区。每个缓冲区大小需要权衡。假设我们设每个缓冲区256MB那么k (4GB - 输出缓冲区) / 256MB ≈ (4096MB - 256MB) / 256MB 15。我们可以进行15路归并吗不行因为我们只有15个段最后一次合并可能用不满15路。我们可以设计一个多趟的合并计划或者就用稍小的k比如8路。构建最佳归并树我们有15个长度不一的段计划进行8路归并。首先检查是否需要虚段(15-1) % (8-1) 14 % 7 0刚好不需要虚段。然后我们按照哈夫曼规则每次选择最短的8个段进行合并生成新的段再放入候选集重复此过程直到只剩一个段。这就规划出了最优的合并顺序。执行归并在每一趟归并中我们使用败者树来高效地从多路最多8路输入缓冲区中选出当前最小的记录输出到输出缓冲区。输出缓冲区满则写回硬盘输入缓冲区空则从对应的归并段中读取下一块数据。败者树确保了内部比较的高效使得增大k值不会带来严重的CPU开销。优化与调参缓冲区大小这是性能关键。太小的缓冲区导致频繁I/O太大的缓冲区减少k值。需要根据磁盘的序列读写性能通过fio等工具测试来找到一个平衡点。通常设置为磁盘块大小的倍数如1MB, 4MB, 8MB是好的起点。异步I/O与重叠现代系统中可以让磁盘读取、内存比较、磁盘写入这三个操作尽可能重叠。例如当CPU正在用败者树进行比较时可以预读下一个数据块到空闲缓冲区。监控与调整在实际运行中监控磁盘I/O利用率和CPU利用率。如果磁盘I/O一直是瓶颈可以尝试增大缓冲区减少k来获得更大的顺序I/O块。如果CPU是瓶颈虽然在外排中不常见或许可以适当增加k。踩过几次坑之后我深刻体会到外部排序不是一个“设好参数就完事”的算法而是一个需要根据数据特征、硬件资源和性能监控进行动态调整的系统工程。败者树、置换-选择排序和最佳归并树提供了强大的理论工具但真正让它们发挥威力的是对整个I/O路径和内存管理的深刻理解与实践中的反复打磨。下次当你面对一个内存装不下的排序任务时不妨按照这个思路来设计你的方案相信你会对“时间换空间”和“优化I/O”有更切实的体会。