先还原一次真实事故。归档服务要把一天 10GB 的日志按时间戳重排,再切成按小时的报表。机器是 2 核 2GB 的批处理节点,第一版代码很直接:整个文件读进来,按换行切成数组,调用内置排序,再写回文件。用 200MB 样本测试一切正常,切到全量那天,进程两分钟不到就被系统杀掉。
值班的人先怀疑有超长行,加了截断重跑,还是被杀。真实原因很朴素:10GB 文本读进来,先占一份 10GB 缓冲,切成行以后,每一行在 JavaScript 里都是独立字符串,一亿行就是上亿个对象。数组要存一亿个指针,按八字节算就是八百兆,每个字符串还有对象头等额外字段。实际要的内存是二三十 GB,2GB 的机器不是紧张,是根本装不下。
这篇讲的就是这种时候怎么办。思路只有一句:内存装不下,就别想一次装下。把数据切成若干块,每块在内存里排好序写回磁盘,最后把这些有序块合并成一个文件。这叫外部排序(external sorting),数据主要放在外部存储上,过程中反复读写磁盘。关键动作叫归并(merge),把多个有序序列合成一个,每次只看各序列当前的第一个元素。
现场:为什么读进来再排必然失败
先算账。每行按一百字节算,10GB 大约一亿行。就算原始字节放在一块连续内存也要 10GB,已经超过物理内存;排序要比较,比较要能随机访问每一行,所以必须切成字符串对象。切完之后对象头和指针的开销,能让内存需求再翻两三倍。
这类失败在监控上很好认:内存曲线斜着冲顶、没有回落,然后进程消失;日志里可能是 heap out of memory,也可能什么都没有,因为进程是被系统直接杀的。看到这种曲线,先怀疑一次性对象化,别先怀疑脏数据。
就算内存够大,一次读进来再排也只是勉强能跑。上亿个短命字符串会让垃圾回收反复扫描整个堆,停顿足以让批处理超时。上限不是装不下,而是装得下也跑不动。
判断标准不是文件多大,而是切成对象后占多少,经验上按原始大小的三到五倍估。超过预算就换外部排序,别去调大堆上限。
第一步:切段,先造出有序段
第一步不是排序,是切段。顺序读进来,每次只读到内存预算允许的大小,在内存里排好序,写成一个临时文件。这个文件里的数据已经有序,叫有序段(run),也叫初始段。
段大小要留余量。2GB 机器不能把 2GB 全给数据,运行时、排序临时空间、读写缓冲、垃圾回收都要占,实际常取可用内存的一半到七成。段太小段数多、趟数多,段太大容易撞内存峰值。
// 每次只读一块,排好序写成一个临时段文件
const fs = require('fs');
const CHUNK = 1000; // 模拟内存上限:一次只放 1000 条
function makeRuns(input, dir) {
let runs = 0;
for (let i = 0; i < input.length; i += CHUNK) {
const chunk = input.slice(i, i + CHUNK);
chunk.sort((a, b) => a - b);
fs.writeFileSync(`${dir}/run-${runs}.txt`, chunk.join('\n'));
runs++;
}
return runs;
}
本机用两万条随机整数、每段一千条模拟,切出二十个段。换到 10GB、每段 100MB,就是 102.4 向上取整一百零三段。注意是向上取整:最后不满一段的数据也要单独成段,否则会少几行,而且很难在结果里发现。
写段文件最好顺序追加到一个大临时文件的连续区域,用偏移量记每段位置,比开一百多个小文件好管理。写完就落盘关闭,不要全部开着,否则句柄还没归并就先撞上限。切段的成本是读一遍写一遍,两倍数据量,省不掉。
k 路归并:最小堆挑出当前最小值
把两个有序段合成一个是二路归并:各有一个读指针,比较两个当前值,小的先写出。一百零三段做二路归并要七趟,每趟全部读写一遍,太多。
实际用 k 路归并,同时打开 k 个段,每次从 k 个当前值里挑最小的。最直白的挑法是线性扫描,每条数据比较 k 次,总比较次数是条数乘 k,k 等于一百时就不可接受。
最小堆(min-heap)把挑最小降到对数级。它是完全二叉树,父节点不大于子节点,最小值在根上。实现用数组:下标 i 的父节点是 (i-1)/2,子节点是 2i+1 和 2i+2。取走堆顶后把末尾搬到根上,和更小的子节点交换,叫下沉;新元素放末尾,和父节点比较,叫上浮。两个操作都是 O(log k)。
function heapPush(h, v) {
h.push(v);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p].val <= h[i].val) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
function heapPop(h) {
const top = h[0];
const last = h.pop();
if (h.length) {
h[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < h.length && h[l].val < h[m].val) m = l;
if (r < h.length && h[r].val < h[m].val) m = r;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]];
i = m;
}
}
return top;
}
堆元素不能只存值,还要存来自哪个段,否则写出一个值后不知道从哪补下一个,结果要么重复、要么漏段。取出后从对应段的读缓冲再取一个推进堆。
function mergeRuns(files, out) {
const h = [];
const rs = files.map((f, i) => ({ lines: readLines(f), idx: 0, i }));
for (const r of rs) {
if (r.lines.length) heapPush(h, { val: r.lines[0], r });
}
const buf = [];
while (h.length) {
const { val, r } = heapPop(h);
buf.push(val);
if (buf.length === 4096) { writeBuf(out, buf); buf.length = 0; }
r.idx++;
if (r.idx < r.lines.length) {
heapPush(h, { val: r.lines[r.idx], r });
}
}
writeBuf(out, buf);
}
本机十路归并两万条、二十个段,段数从二十降到二再降到一,两趟完成,输出两万条,有序校验通过。
读写缓冲:真正的瓶颈在这里
按行读写的话,瓶颈根本不在比较。读一行就是一次 read,一亿行一亿次调用,每次几微秒也是几百秒,还没算磁盘访问;写每一条都落盘,磁盘会被拖垮。
所以要缓冲:每路输入配一块 64KB 到 1MB 的读缓冲,一次读一批,归并时从内存取;输出端配写缓冲,攒够一批再写。系统调用次数从按行降到按块,低三到四个数量级。
缓冲要常驻内存,不是按需借用。可用 100MB、每路 1MB,k 等于一百时光缓冲就一百 MB,还没算堆、段内排序的临时空间和输出缓冲。k 是由剩下的内存除以每路缓冲算出来的,不是拍脑袋定的。
还有隐性成本:k 个段同时读,磁盘位置分散。机械盘每次切换段要寻道,k 越大越频繁;固态盘没有寻道,但随机读带宽仍低于顺序读,而且会把页缓存挤出去。页缓存一被冲垮,每次读都落到磁盘上。
趟数与 k 的关系
趟数等于以 k 为底、段数的对数向上取整:一趟把 k 段并成一段,段数降为原来的 k 分之一,降到一就结束。初始段数等于总量除以段长,向上取整。
10GB、100MB 一段是一百零三段:k 等于二要七趟,k 等于十要三趟,k 等于一百要两趟,k 等于一千只要一趟。每趟读一遍写一遍,总 I/O 约为数据量两倍乘趟数,三趟六十 GB,两趟四十 GB,一趟二十 GB。
| 归并路数 k | 需要几趟 | 大约读写量 | 说明 |
|---|---|---|---|
| 2 | 7 | 约 140GB | 二路归并,实现最简单,I/O 最多 |
| 10 | 3 | 约 60GB | 常用区间,缓冲和句柄都宽松 |
| 100 | 2 | 约 40GB | 要同时开一百个文件,缓冲降到 1MB 以内 |
| 1000 | 1 | 约 20GB | 句柄和缓冲都吃紧,实际很少这么取 |
收益是递减的。k 从二到十少四趟,从十到一百只少一趟,从一百到一千再少一趟,却要同时开一千个文件、常驻一千块缓冲。经验值通常在八到六十四。
而且加大 k 不总能少一趟:一百零三段、k 等于十时必须三趟,因为十的平方只有一百。段数压到一百以内,同样 k 就只要两趟。这正是替换选择想达到的效果。
为什么 k 不是越大越好
第一道硬限制是文件句柄。每个打开的文件占一个描述符,默认上限常见一千零二十四。k 取到一千,再算日志、网络连接、临时文件,很容易报 too many open files。撞上不是变慢,是中途直接失败。
第二道是缓冲内存。k 块输入缓冲必须同时驻留。每路缓冲从 1MB 降到 100KB,读调用次数涨十倍,省下的一趟 I/O 又被读放大吃回去。
第三道是缓存与寻道。归并每写一个元素就要切换到 k 个段中的一个,k 越大同时活跃的数据块越多,页缓存越容易被冲垮,机械盘磁头来回跑。这个成本不会出现在任何复杂度公式里。
第四道是打开关闭的固定开销,每趟开 k 个、关 k 个,还要读文件头,k 大时乘以趟数也不是小数目。
正确顺序是先定内存预算,减去输出缓冲、堆和运行时开销,按 k 分摊得到每路缓冲;每路低于三十二到六十四 KB 就说明 k 太大,应该降下来多跑一趟。多跑一趟是确定的线性成本,读放大可能成倍。
一句话:k 要大到减少趟数,小到留住缓冲。冲突时优先保缓冲,因为缓冲决定每次 I/O 的有效载荷。
替换选择:让初始段自己变长
普通切段有天花板:段长最多等于内存条数。想少趟,要么加内存,要么让段变长。替换选择(replacement selection)用最小堆把平均段长做到接近内存容量的两倍。
做法是先装满 M 条建最小堆,反复取堆顶写进当前段,同时从输入读一条新记录:比刚写出的大就放回堆,能接在后面;更小就暂存到一边,等这段结束再用来开下一段。
为什么变长:堆里始终留着不小于已输出值的记录,当前段就能一直延伸,直到堆里所有元素都比刚输出的小。随机输入平均约两倍内存容量,近似有序输入可能一口气生成覆盖全文件的超长段,后面直接省掉归并。
本机实测:两万条随机整数、堆容量一千,普通切段二十段,替换选择十一段,平均段长一千八百一十八,内存占用没增加。
但段数减半不等于趟数减半,要看是否跨过 k 的幂。这组数据用十路,二十段和十一段都两趟,没省;换成二路,一百零三段七趟、五十二段六趟,才真的少一趟。
代价是暂存区,最坏情况会攒下接近一整段的数据,实现也复杂。数据均匀随机时收益是段数减半,局部性强时收益更大。先看输入是否近似有序、段数是否卡在阈值附近,两个都不满足时普通切段更省事。
普通切段
读满一块、内存排序、整段写出。段长等于内存容量,段数可精确预估,实现只有十几行。适合数据完全无序、段数离阈值较远的情况。
替换选择
用最小堆边读边输出,段长平均接近两倍内存。实现复杂,需要暂存区,段数不可精确预估。适合输入近似有序,或段数卡在阈值上方的情况。
现象、原因与第一步排查
下面这些症状经常被误判成磁盘慢或数据有问题,先按表里的第一步定位,不要一上来就换机器。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 进程跑两分钟就被杀,内存曲线冲顶 | 一次性读入并对象化,实际占用是文件大小的数倍 | 是否先读全量再切分 |
| 临时段文件数量远超预估 | 每段数据量太小,或没算对象开销 | 段数是否等于总量除以段长向上取整 |
| 归并阶段磁盘满载但进度极慢 | k 太大,页缓存被冲垮,缓冲又太小 | k 与每路缓冲、缓存容量的比例 |
| 归并中途报 too many open files | k 超过描述符上限,还叠加了日志等占用 | 句柄上限与 k 的比值 |
| 内存没超,但任务跑了几个小时 | 按行读写,没有缓冲,系统调用按行计数 | 每次读写的粒度 |
| 输出里某值重复或整段丢失 | 堆元素没带来源段,或段读完后没补位 | 堆元素结构与补位判断 |
| 最终文件比输入少几行 | 段数向下取整,余数没单独成段 | 切段循环边界与取整方向 |
| 结果整体有序,中间一小段乱 | 某趟只合并了部分段,或最后一轮漏合 | 每趟是否把所有段并进下一轮 |
| 重启后从头再来,临时文件残留 | 没有检查点,失败后无法续跑 | 是否有段级进度与清理逻辑 |
最容易误判的是第一行和第三行。换大内存只会把失败推迟到更大的文件;第三行看似磁盘不行,实际是 k 和缓冲配比错了,同一块盘换成 k 等于八就能跑满带宽。
边界与代价
I/O 下限是数据量乘二再乘趟数,每趟都要全量读写,没有取巧。所以上限由磁盘带宽决定。10GB 三趟六十 GB,机械盘百兆每秒就是十分钟上下,优化几乎全在减少趟数上。
空间代价经常被忽略:段文件加起来一份数据,输出再一份,峰值接近两倍。临时分区只剩一份余量,归并到一半就会写满。要检查配额,并保证失败后清理残留,否则反复重试会吃光磁盘。
稳定性取决于两件事:段内排序是否稳定,归并时相等值取哪个段。两件都做到才稳定。很多导出顺序每次不同,根子就在这里,而不是业务代码。
也不是所有大数据都该用。小于内存直接内存排序;已近似有序,一次遍历校验即可;能按天或按用户哈希分区,就先分区再各自排序。真正需要的是全局有序且装不下这个组合。
数据库的 ORDER BY 放不下时会走外部归并,大数据框架的 shuffle 也是分区、局部排序、再归并。理解切段、归并、缓冲三件事,再看这些系统的参数就不陌生。
最后是复杂度代价:临时文件、句柄、检查点、失败重试,代码量是内存排序的十几倍,出错姿势也多。偶尔超标时,先考虑加内存或缩小单批处理量,往往比引入整套外部排序划算。
当天能做的练习
- 用本文的
makeRuns,把段大小设成 1000、500、250,跑同一份两万条数据,记录段数,验证它等于总量除以段长向上取整。 - 实现八路归并,把最小堆换成线性扫描,统计两种实现的比较次数,解释为什么 k 大时堆的优势更明显。
- 构造两个各三条的段,手动推演归并,每一步打印堆里各元素的来源段编号,确认输出有序且没有漏读。
- 实现替换选择,用同一份两万条数据分别跑随机输入和近似有序输入,记录段数与平均段长,说明收益差异。
- 把 k 设成 200,在 Linux 上用
ulimit -n 100限制句柄数复现报错,再把 k 降到 8 确认任务能跑完。
小结与下一篇
三句话收一下:外部排序不减少比较次数,只解决内存装不下,做法是切段加归并;k 路归并靠最小堆把每次挑最小降到对数级,k 的大小由内存预算和句柄上限共同决定;替换选择用最小堆把初始段拉长到接近两倍内存,但只在段数跨过阈值时才真的省下一趟。
下一篇从另一个方向看排序:为什么同样的分数,两个学生排出来的先后顺序会变。今天已经碰到过这个问题,归并时相等值先取哪个段、段内排序稳不稳,都会影响最终顺序。下一篇把稳定性的定义、哪些算法稳定、比较器返回零意味着什么,以及 Java 里对象数组和原始类型为什么用两套排序算法,一次讲清楚。