第一幕崩溃的实习生与“不可能完成的任务”周一早晨阳光透过百叶窗洒在工位上但实习生小刘的脸色却比阴天还难看。他抱着笔记本电脑像抱着炸药包一样冲到杨工桌前。“杨工救命啊”小刘的声音里带着哭腔“老板让我把服务器上的 500G 日志文件按时间戳排序可我刚跑了几分钟程序就崩了报OutOfMemoryError咱们服务器内存不是有 64G 吗怎么还是不够”杨工正端着保温杯慢悠悠地吹了吹浮沫抬眼看了看小刘屏幕上的报错信息笑了“500G 的数据你指望一次性全塞进内存里排别说咱们服务器就是把你卖了换内存条也不够啊。”小刘挠了挠头一脸委屈“可是Arrays.sort()和Collections.sort()不都是这么用的吗以前处理几个 G 的数据都没事啊。”“以前是以前现在是大数据时代。”杨工放下杯子拉过一把椅子让小刘坐下“当数据量大到内存装不下时我们就不能再用‘内部排序’的思维了得请出今天的主角——外部排序。”“外部排序”小刘眼睛一亮“听起来像是个高级算法。”“不它不是一个单一的算法而是一套策略。”杨工拿起白板笔在白板上写下四个大字分而治之。第二幕切蛋糕——把大象装进冰箱“来想象一下你面前有一个 500G 的大蛋糕但你只有一个能装 4G 奶油的小盒子内存。你怎么把蛋糕整理好”杨工问。小刘想了想“切块一次切一块放进盒子里弄好再拿出来”“宾果”杨工打了个响指“这就是外部排序的第一步分块Chunking。”杨工在白板上画了一个巨大的长方形代表 500G 文件然后画了一条虚线把它切成无数个小方块。“我们的内存限制是 4G。为了稳妥我们不能把 4G 全占满得留点空间给操作系统和排序算法的递归栈。假设我们每次只读3.5G数据进内存。”计算时间500÷3.5≈143500÷3.5≈143 。结论我们需要把这 500G 数据切成大约143 个小文件。“第一步操作很简单”杨工边写边说“写一个循环每次从原文件读取 3.5G 数据到内存缓冲区。这就好比把大蛋糕切成了 143 块小蛋糕。”第三幕各个击破——内存里的极速排序“切好之后呢”小刘问。“切好之后这 3.5G 数据就在内存里了这时候它就是个普通的小数组。”杨工在白板的每个小方块上写了个“Sort”。“这时候你就可以尽情使用你熟悉的快速排序或者归并排序了。甚至直接调用语言自带的排序库比如 Java 的Arrays.sort()或 C 的std::sort。这些算法在内存里的速度是非常快的。”杨工强调道“排好序后立刻把这个有序的 3.5G 数据写回磁盘命名为temp_001.dattemp_002.dat……以此类推。注意这时候每个小文件内部都是有序的了”小刘恍然大悟“哦所以我先产生了 143 个‘局部有序’的小文件”“对这就是第二步内部排序。”杨工点头“现在难题从‘如何排序 500G 数据’变成了‘如何合并 143 个有序小文件’。”第四幕决战时刻——多路归并与最小堆小刘看着白板上的 143 个小方块又犯了难“杨工合并我会啊。我把temp_001和temp_002合并成一个新的再和temp_003合并……就像归并排序那样两两合并行不行”杨工摇摇头“理论上可行但效率太低。你要知道磁盘 I/O 是最慢的。如果你两两合并这 143 个文件要反反复复读写磁盘好多轮硬盘会冒烟的。”“那怎么办143 个文件一起读那内存又爆了”“这就是最精彩的部分——多路归并K-way Merge。”杨工在白板上画了一个漏斗形状的结构上面是 143 根管子下面汇聚成一根管子。“我们不需要把 143 个文件的内容全读进内存我们只需要维护一个最小堆Min-Heap。”杨工开始画图讲解核心逻辑建立缓冲区我们在内存里为这 143 个文件每个开辟一个小窗口比如每个文件只读 1MB 到内存缓冲区。这样 143MB 的内存占用微乎其微。初始化堆从每个文件的缓冲区里取出第一个元素也就是该文件当前的最小值扔进一个大小为 143 的最小堆里。取最小值堆顶的元素一定是所有文件里全局最小的那个把它拿出来写入最终的result.dat文件。补充元素堆顶元素被拿走了空了一个位置。那就从刚才那个元素所属的文件里再读一个下一个元素补进去调整堆结构。循环重复步骤 3 和 4直到所有文件都读完。小刘盯着图看了半天突然拍大腿“我懂了这就好比 143 个赛跑选手每个人手里拿着一张写着时间的卡片。裁判堆每次只看谁手里的卡片数字最小就把谁的成绩记录到总榜上然后让那个人再掏出一张新卡片。裁判不需要知道所有人所有的成绩只需要盯着眼前的 143 张卡片就行”“比喻非常精准”杨工竖起大拇指“这就是用极小的内存代价完成了海量数据的有序合并。”第五幕高手的进阶——置换选择排序小刘兴奋地收拾东西准备去写代码杨工叫住了他“等等还有个进阶技巧如果你想让老板对你刮目相看可以用上这个。”“还有更厉害的”“刚才我们说每个小块只能排 3.5G对吧”杨工神秘一笑“其实利用堆的特性我们可以生成平均长度为 2 倍内存大小的有序块。这叫置换选择排序。”“怎么做到的”“在归并或者生成初始块的时候如果新读进来的元素比当前输出的元素小它肯定不能排在后面。普通做法是把它留到下一轮。但在置换选择里我们可以把它暂时‘冻结’在堆的叶子节点不参与当前轮的比较等这一轮结束了再解冻。这样原本只能装 3.5G 的内存平均能产出 7G 的有序块”杨工总结道“这意味着你的临时文件数量直接从 143 个减少到 70 多个归并时的 I/O 压力直接减半”尾声代码跑通的那一刻两个小时后服务器机房传来风扇的轰鸣声。小刘盯着终端屏幕上跳动的进度条最终显示Sort Completed. Time: 45m 20s。“成了”小刘欢呼道“500G 数据4G 内存限制完美排序”杨工走过来看了一眼日志“不错。记住今天的教训在大数据面前内存是昂贵的奢侈品磁盘才是我们坚实的依靠。学会尊重 I/O学会分而治之这才是工程师的思维。”小刘用力点点头在笔记本上重重地写下了一行字外部排序 分块内排 多路归并最小堆。 500G 数据只有 4G 内存怎么排？杨工带小刘实战“外部排序”
第一幕崩溃的实习生与“不可能完成的任务”周一早晨阳光透过百叶窗洒在工位上但实习生小刘的脸色却比阴天还难看。他抱着笔记本电脑像抱着炸药包一样冲到杨工桌前。“杨工救命啊”小刘的声音里带着哭腔“老板让我把服务器上的 500G 日志文件按时间戳排序可我刚跑了几分钟程序就崩了报OutOfMemoryError咱们服务器内存不是有 64G 吗怎么还是不够”杨工正端着保温杯慢悠悠地吹了吹浮沫抬眼看了看小刘屏幕上的报错信息笑了“500G 的数据你指望一次性全塞进内存里排别说咱们服务器就是把你卖了换内存条也不够啊。”小刘挠了挠头一脸委屈“可是Arrays.sort()和Collections.sort()不都是这么用的吗以前处理几个 G 的数据都没事啊。”“以前是以前现在是大数据时代。”杨工放下杯子拉过一把椅子让小刘坐下“当数据量大到内存装不下时我们就不能再用‘内部排序’的思维了得请出今天的主角——外部排序。”“外部排序”小刘眼睛一亮“听起来像是个高级算法。”“不它不是一个单一的算法而是一套策略。”杨工拿起白板笔在白板上写下四个大字分而治之。第二幕切蛋糕——把大象装进冰箱“来想象一下你面前有一个 500G 的大蛋糕但你只有一个能装 4G 奶油的小盒子内存。你怎么把蛋糕整理好”杨工问。小刘想了想“切块一次切一块放进盒子里弄好再拿出来”“宾果”杨工打了个响指“这就是外部排序的第一步分块Chunking。”杨工在白板上画了一个巨大的长方形代表 500G 文件然后画了一条虚线把它切成无数个小方块。“我们的内存限制是 4G。为了稳妥我们不能把 4G 全占满得留点空间给操作系统和排序算法的递归栈。假设我们每次只读3.5G数据进内存。”计算时间500÷3.5≈143500÷3.5≈143 。结论我们需要把这 500G 数据切成大约143 个小文件。“第一步操作很简单”杨工边写边说“写一个循环每次从原文件读取 3.5G 数据到内存缓冲区。这就好比把大蛋糕切成了 143 块小蛋糕。”第三幕各个击破——内存里的极速排序“切好之后呢”小刘问。“切好之后这 3.5G 数据就在内存里了这时候它就是个普通的小数组。”杨工在白板的每个小方块上写了个“Sort”。“这时候你就可以尽情使用你熟悉的快速排序或者归并排序了。甚至直接调用语言自带的排序库比如 Java 的Arrays.sort()或 C 的std::sort。这些算法在内存里的速度是非常快的。”杨工强调道“排好序后立刻把这个有序的 3.5G 数据写回磁盘命名为temp_001.dattemp_002.dat……以此类推。注意这时候每个小文件内部都是有序的了”小刘恍然大悟“哦所以我先产生了 143 个‘局部有序’的小文件”“对这就是第二步内部排序。”杨工点头“现在难题从‘如何排序 500G 数据’变成了‘如何合并 143 个有序小文件’。”第四幕决战时刻——多路归并与最小堆小刘看着白板上的 143 个小方块又犯了难“杨工合并我会啊。我把temp_001和temp_002合并成一个新的再和temp_003合并……就像归并排序那样两两合并行不行”杨工摇摇头“理论上可行但效率太低。你要知道磁盘 I/O 是最慢的。如果你两两合并这 143 个文件要反反复复读写磁盘好多轮硬盘会冒烟的。”“那怎么办143 个文件一起读那内存又爆了”“这就是最精彩的部分——多路归并K-way Merge。”杨工在白板上画了一个漏斗形状的结构上面是 143 根管子下面汇聚成一根管子。“我们不需要把 143 个文件的内容全读进内存我们只需要维护一个最小堆Min-Heap。”杨工开始画图讲解核心逻辑建立缓冲区我们在内存里为这 143 个文件每个开辟一个小窗口比如每个文件只读 1MB 到内存缓冲区。这样 143MB 的内存占用微乎其微。初始化堆从每个文件的缓冲区里取出第一个元素也就是该文件当前的最小值扔进一个大小为 143 的最小堆里。取最小值堆顶的元素一定是所有文件里全局最小的那个把它拿出来写入最终的result.dat文件。补充元素堆顶元素被拿走了空了一个位置。那就从刚才那个元素所属的文件里再读一个下一个元素补进去调整堆结构。循环重复步骤 3 和 4直到所有文件都读完。小刘盯着图看了半天突然拍大腿“我懂了这就好比 143 个赛跑选手每个人手里拿着一张写着时间的卡片。裁判堆每次只看谁手里的卡片数字最小就把谁的成绩记录到总榜上然后让那个人再掏出一张新卡片。裁判不需要知道所有人所有的成绩只需要盯着眼前的 143 张卡片就行”“比喻非常精准”杨工竖起大拇指“这就是用极小的内存代价完成了海量数据的有序合并。”第五幕高手的进阶——置换选择排序小刘兴奋地收拾东西准备去写代码杨工叫住了他“等等还有个进阶技巧如果你想让老板对你刮目相看可以用上这个。”“还有更厉害的”“刚才我们说每个小块只能排 3.5G对吧”杨工神秘一笑“其实利用堆的特性我们可以生成平均长度为 2 倍内存大小的有序块。这叫置换选择排序。”“怎么做到的”“在归并或者生成初始块的时候如果新读进来的元素比当前输出的元素小它肯定不能排在后面。普通做法是把它留到下一轮。但在置换选择里我们可以把它暂时‘冻结’在堆的叶子节点不参与当前轮的比较等这一轮结束了再解冻。这样原本只能装 3.5G 的内存平均能产出 7G 的有序块”杨工总结道“这意味着你的临时文件数量直接从 143 个减少到 70 多个归并时的 I/O 压力直接减半”尾声代码跑通的那一刻两个小时后服务器机房传来风扇的轰鸣声。小刘盯着终端屏幕上跳动的进度条最终显示Sort Completed. Time: 45m 20s。“成了”小刘欢呼道“500G 数据4G 内存限制完美排序”杨工走过来看了一眼日志“不错。记住今天的教训在大数据面前内存是昂贵的奢侈品磁盘才是我们坚实的依靠。学会尊重 I/O学会分而治之这才是工程师的思维。”小刘用力点点头在笔记本上重重地写下了一行字外部排序 分块内排 多路归并最小堆。