先还原一次真实事故。归档服务要把一天 10GB 的日志按时间戳重排,再切成按小时的报表。机器是 2 核 2GB 的批处理节点,第一版代码很直接:整个文件读进来,按换行切成数组,调用内置排序,再写回文件。用 200MB 样本测试一切正常,切到全量那天,进程两分钟不到就被系统杀掉。

值班的人先怀疑有超长行,加了截断重跑,还是被杀。真实原因很朴素:10GB 文本读进来,先占一份 10GB 缓冲,切成行以后,每一行在 JavaScript 里都是独立字符串,一亿行就是上亿个对象。数组要存一亿个指针,按八字节算就是八百兆,每个字符串还有对象头等额外字段。实际要的内存是二三十 GB,2GB 的机器不是紧张,是根本装不下。

这篇讲的就是这种时候怎么办。思路只有一句:内存装不下,就别想一次装下。把数据切成若干块,每块在内存里排好序写回磁盘,最后把这些有序块合并成一个文件。这叫外部排序(external sorting),数据主要放在外部存储上,过程中反复读写磁盘。关键动作叫归并(merge),把多个有序序列合成一个,每次只看各序列当前的第一个元素。

现场:为什么读进来再排必然失败

先算账。每行按一百字节算,10GB 大约一亿行。就算原始字节放在一块连续内存也要 10GB,已经超过物理内存;排序要比较,比较要能随机访问每一行,所以必须切成字符串对象。切完之后对象头和指针的开销,能让内存需求再翻两三倍。

这类失败在监控上很好认:内存曲线斜着冲顶、没有回落,然后进程消失;日志里可能是 heap out of memory,也可能什么都没有,因为进程是被系统直接杀的。看到这种曲线,先怀疑一次性对象化,别先怀疑脏数据。

就算内存够大,一次读进来再排也只是勉强能跑。上亿个短命字符串会让垃圾回收反复扫描整个堆,停顿足以让批处理超时。上限不是装不下,而是装得下也跑不动。

外部排序的五个动作
顺序读一块,控制在预算内
块内排序,写成一个有序段
重复切段,直到输入读完
k 路归并,多趟合并段
最后一段就是有序结果

判断标准不是文件多大,而是切成对象后占多少,经验上按原始大小的三到五倍估。超过预算就换外部排序,别去调大堆上限。

堆上限只能在物理内存之内腾挪。2GB 机器把上限调到 4GB,结果是触发交换分区,磁盘当内存用,速度掉到几十分之一,最后还是被杀。

第一步:切段,先造出有序段

第一步不是排序,是切段。顺序读进来,每次只读到内存预算允许的大小,在内存里排好序,写成一个临时文件。这个文件里的数据已经有序,叫有序段(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需要几趟大约读写量说明
27约 140GB二路归并,实现最简单,I/O 最多
103约 60GB常用区间,缓冲和句柄都宽松
1002约 40GB要同时开一百个文件,缓冲降到 1MB 以内
10001约 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 filesk 超过描述符上限,还叠加了日志等占用句柄上限与 k 的比值
内存没超,但任务跑了几个小时按行读写,没有缓冲,系统调用按行计数每次读写的粒度
输出里某值重复或整段丢失堆元素没带来源段,或段读完后没补位堆元素结构与补位判断
最终文件比输入少几行段数向下取整,余数没单独成段切段循环边界与取整方向
结果整体有序,中间一小段乱某趟只合并了部分段,或最后一轮漏合每趟是否把所有段并进下一轮
重启后从头再来,临时文件残留没有检查点,失败后无法续跑是否有段级进度与清理逻辑

最容易误判的是第一行和第三行。换大内存只会把失败推迟到更大的文件;第三行看似磁盘不行,实际是 k 和缓冲配比错了,同一块盘换成 k 等于八就能跑满带宽。

边界与代价

I/O 下限是数据量乘二再乘趟数,每趟都要全量读写,没有取巧。所以上限由磁盘带宽决定。10GB 三趟六十 GB,机械盘百兆每秒就是十分钟上下,优化几乎全在减少趟数上。

空间代价经常被忽略:段文件加起来一份数据,输出再一份,峰值接近两倍。临时分区只剩一份余量,归并到一半就会写满。要检查配额,并保证失败后清理残留,否则反复重试会吃光磁盘。

稳定性取决于两件事:段内排序是否稳定,归并时相等值取哪个段。两件都做到才稳定。很多导出顺序每次不同,根子就在这里,而不是业务代码。

也不是所有大数据都该用。小于内存直接内存排序;已近似有序,一次遍历校验即可;能按天或按用户哈希分区,就先分区再各自排序。真正需要的是全局有序且装不下这个组合。

数据库的 ORDER BY 放不下时会走外部归并,大数据框架的 shuffle 也是分区、局部排序、再归并。理解切段、归并、缓冲三件事,再看这些系统的参数就不陌生。

最后是复杂度代价:临时文件、句柄、检查点、失败重试,代码量是内存排序的十几倍,出错姿势也多。偶尔超标时,先考虑加内存或缩小单批处理量,往往比引入整套外部排序划算。

当天能做的练习

  1. 用本文的 makeRuns,把段大小设成 1000、500、250,跑同一份两万条数据,记录段数,验证它等于总量除以段长向上取整。
  2. 实现八路归并,把最小堆换成线性扫描,统计两种实现的比较次数,解释为什么 k 大时堆的优势更明显。
  3. 构造两个各三条的段,手动推演归并,每一步打印堆里各元素的来源段编号,确认输出有序且没有漏读。
  4. 实现替换选择,用同一份两万条数据分别跑随机输入和近似有序输入,记录段数与平均段长,说明收益差异。
  5. 把 k 设成 200,在 Linux 上用 ulimit -n 100 限制句柄数复现报错,再把 k 降到 8 确认任务能跑完。
环境说明:本文代码用 Node.js 24 在本机实际运行,段数、趟数、替换选择的段数与平均段长均来自这次运行的输出。关于 I/O 总量的推算只是算术结果,不是实测带宽。

小结与下一篇

三句话收一下:外部排序不减少比较次数,只解决内存装不下,做法是切段加归并;k 路归并靠最小堆把每次挑最小降到对数级,k 的大小由内存预算和句柄上限共同决定;替换选择用最小堆把初始段拉长到接近两倍内存,但只在段数跨过阈值时才真的省下一趟。

下一篇从另一个方向看排序:为什么同样的分数,两个学生排出来的先后顺序会变。今天已经碰到过这个问题,归并时相等值先取哪个段、段内排序稳不稳,都会影响最终顺序。下一篇把稳定性的定义、哪些算法稳定、比较器返回零意味着什么,以及 Java 里对象数组和原始类型为什么用两套排序算法,一次讲清楚。