先看一条很典型的监控曲线。日志服务的写入缓冲平时很稳,每秒几千条,p99 一直在一两毫秒。但每隔一段时间,会出现一次五十毫秒左右的写入尖刺,之后马上恢复。尖刺的间隔随着服务运行越来越长,重启后又从头开始。

值班同事先怀疑磁盘,看了眼 IO 队列是空的;又怀疑垃圾回收,加了 GC 日志,发现尖刺和一次较大的内存分配对得上;再怀疑锁,可写入是单线程的。最后把缓冲的实现翻出来,发现它是一个自己维护的动态数组:容量满了就申请一块两倍大的内存,把旧数据全部复制过去。

这次尖刺就是一次扩容。复制本身是 O(n),数据越多复制越久,所以越到后面偶尔越卡。但奇怪的是,从整体吞吐看,这个服务并没有越来越慢,平均每次写入仍然只有一两毫秒。单次最坏明明是 O(n),为什么平均值能写成 O(1)?这就是均摊分析要回答的问题。

现场:一次 50 毫秒的写入尖刺

把缓冲缩成一个最小的可扩容数组。它有三个字段:数据、长度、容量。追加时如果长度等于容量,就申请一块更大的空间,把旧元素逐个复制过去,记录复制了多少个。

class DynArray {
  constructor() {
    this.data = new Array(1);
    this.len = 0;
    this.cap = 1;
    this.copies = 0;
    this.grows = 0;
  }
  push(v) {
    if (this.len === this.cap) {
      const bigger = new Array(this.cap * 2);
      for (let i = 0; i < this.len; i++) bigger[i] = this.data[i];
      this.copies += this.len;
      this.grows++;
      this.data = bigger;
      this.cap = this.cap * 2;
    }
    this.data[this.len++] = v;
  }
}

本机用 Node.js 24 跑了十万次追加:一共扩容 17 次,累计复制 131071 个元素,总耗时约 3.1 毫秒,其中单次扩容最长约 0.54 毫秒。把这套代码换成 Float64Array、把规模加到一千万,结果是扩容 24 次、累计复制 16777215 个元素、单次最长扩容 12.83 毫秒、总耗时约 54.09 毫秒。

单看一次复制更直观。本机整块复制的实测:26.2 万个元素约 0.399 毫秒,105 万个约 1.446 毫秒,419 万个约 6.703 毫秒,839 万个约 14.708 毫秒,1678 万个约 22.644 毫秒。规模翻倍,时间也大致翻倍。

线上看到的五十毫秒,通常比纯复制多两件事:申请新内存的开销,以及旧内存回收。复制 1677 万个元素就要 22.6 毫秒,加上分配和一次 GC,落在五十毫秒并不奇怪。关键是它只在扩容那一次出现。

一次扩容到底做了什么

动态数组有两个数字:长度是存了几个,容量是最多能放几个。长度到顶时不能原地变长,因为数组要求元素连续,后面那块内存可能已被别的对象占了,只能换一块更大的地方。

追加一个元素的三条路
长度小于容量,直接写在末尾
长度等于容量,申请两倍大的新空间
复制旧元素,释放旧空间,再写新元素

从容量 1 开始倍增,扩容发生在这些时刻:放入第二个元素时容量从 1 变 2,放第三个时从 2 变 4,放第五个时从 4 变 8,放第九个时从 8 变 16。本机打印出来的前几次正是这样:长度 1 时容量 1,长度 2 时容量 2,长度 3 时容量 4,长度 5 时容量 8,长度 9 时容量 16。

每次扩容复制的元素个数正好是扩容前的长度:1、2、4、8、16。这个序列是后面所有推导的基础。复制的是已有元素而不是容量,两者在这里恰好相等。

还有一点容易被忽略:扩容后容量翻倍,长度只增加 1,等于买来的空位和已有元素一样多。接下来可以连续追加同样多次而不用复制,这个比例决定了均摊成本是常数。

为什么单次 O(n),均摊却 O(1)

先给结论:连续追加 n 次,复制总量是 1 加 2 加 4 一直加到不超过 n 的最大 2 的幂,这个和小于 2n。再加上 n 次真正的写入,总操作数小于 3n。除以 n 次操作,平均每次小于 3 次操作,所以是 O(1)。

推导只用等比数列求和。容量从 1 翻倍,最后一次扩容前长度不超过 n,把 1、2、4 一直加到不超过 n 的最大 2 的幂,总和是两倍最后一项减一,小于 2n。

「均摊」这个词要说得准确:它不是「每次都是 O(1)」,而是「任意连续 n 次操作的总成本不超过 3n」。单次最坏仍然是 O(n),而且这个最坏一定会发生,只是频率越来越低。均摊给的是总账上的保证,不是每一次的延迟承诺。

这一点在工程上非常关键。如果业务要求每一次写入都在十毫秒内完成,均摊 O(1) 救不了你,因为扩容那一次就是会超。实时系统、音视频、交易撮合常常要避开这种「偶发长尾」,办法是预分配足够容量,或者改用分块存储,把一次大复制拆成很多次小分配。

本机数据也能看出总账和单次的差别:十万次追加平均每次只复制 1.31 个元素,但其中一次复制了 65536 个,开销是平均值的几万倍。

单次最坏扩容那一次要复制全部旧元素,O(n)。数据越大越明显,这就是监控上的尖刺。
总成本n 次追加的复制总量小于 2n,加上写入本身,总计小于 3n。
均摊总成本除以操作次数,小于 3,是与 n 无关的常数,记作 O(1)。

聚合法:把总账一次算清

聚合法(aggregate analysis)是最直白的一种:不管每一次具体花多少,只算 n 次操作一共花了多少,再除以 n。它给出的其实是平均成本的上界,但因为对任意 n 都成立,所以是严格的均摊结论。

用实测数字走一遍。n 等于 1000 时,扩容 10 次,复制 1023 个元素;n 等于 10000 时,扩容 14 次,复制 16383 个;n 等于 100000 时,扩容 17 次,复制 131071 个。三次的复制总量都小于 2n,比例在 1.02 到 1.31 之间。

聚合法好在简单,只要会求等比数列。局限也明显:只给出总上界,没法解释某一次为什么贵。结构复杂时,比如同时有入栈、出栈、缩容,求和就不好写了。

记账法:每次多存一点,扩容时花掉

记账法(accounting method)把每次操作想象成先付一笔固定的「虚拟费用」,多付的部分存进一个余额。只要余额永远不为负,就说明真实总成本没有超过虚拟总成本。

对倍增数组,可以给每次追加记 3 枚硬币:1 枚支付本次写入,另外 2 枚存起来。当长度为 m、容量也为 m 触发扩容时,需要复制 m 个元素,也就是要花 m 枚。而从上次扩容到这次扩容,长度从 m 除 2 涨到 m,一共追加了 m 除 2 次,每次存 2 枚,正好存下 m 枚,够付这次复制。

余额在任何时刻都不会变成负数,所以 n 次操作的真实总成本不超过 3n 枚硬币,均摊下来每次不超过 3,是 O(1)。这个 3 不是唯一答案,你记 4 枚、5 枚也能证,只是界会松一点。关键是选的数要能覆盖最坏那一次。

记账法也能解释增长倍数的差别。1.5 倍增长时,长度为 m 触发扩容,中间只追加了三分之一个 m 次,每次要存 3 枚才够付复制,加上写入的 1 枚就是 4 枚。所以 1.5 倍的均摊常数确实比 2 倍大。

势能法:用一个函数把余额写成公式

势能法(potential method)把余额写成一个关于结构的函数,记作 Φ(读作 Phi)。均摊成本等于真实成本加势能变化量,只要势能不为负,上界就成立。

对倍增数组,取 Φ 等于 2 乘长度减去容量。不扩容时,追加一个元素,真实成本是 1,长度加 1 让势能增加 2,均摊成本是 3。触发扩容时,长度为 m、容量为 m,扩容前势能是 m;扩容后长度 m 加 1、容量 2m,势能变成 2,变化量是 2 减 m。

把真实成本代进去:复制 m 个元素加写入 1 个,是 m 加 1,再加上势能变化 2 减 m,结果正好是 3。两种情况的均摊成本都是 3,所以每次都是 O(1)。这就是势能法的好处:不用按批次算总账,可以直接对单个操作给出界。

它的代价是要猜对势能函数。这个 2 乘长度减容量对应「每次预留两份复制预算」的直觉。换成带缩容的数组,还要把缩容包进去,猜错就会推出负数余额。

三种方法证的是同一件事,选哪个看场景:只需要一个总的上界,用聚合法;想逐次解释费用怎么存怎么花,用记账法;要对每一步给严格的界,或者结构复杂到不好分批,用势能法。面试和论文里常见势能法,日常排查看聚合法就够。

1.5 倍与 2 倍:省内存还是省复制

容量增长倍数不一定是 2。很多运行时在数组很大时会改成 1.5 倍,理由是省内存,代价是扩容更频繁。两种都满足均摊 O(1),差别在常数和峰值。

2 倍增长

本机十万次追加:扩容 17 次,复制 131071 个元素,最终容量 131072。复制总量约为 n,但平均有一半容量是空的,内存浪费更大。

1.5 倍增长

本机十万次追加:扩容 28 次,复制 276492 个元素,最终容量 138254。复制总量约为 2n 到 3n,比 2 倍多出一倍以上,但平均空置率更低。

把规模加到一千万,差距更明显。2 倍增长扩容 24 次、复制 16777215 个元素、总耗时约 54.09 毫秒、单次最长 12.83 毫秒;1.5 倍增长扩容 40 次、复制 23917332 个元素、总耗时约 75.57 毫秒、单次最长 11.65 毫秒。复制总量多了约四成,整体更慢。

那为什么还要用 1.5 倍?因为它把「浪费」和「复制」换了个比例。2 倍增长的容量最多可能空一半,1.5 倍最多空三分之一。在内存紧张的进程里,省下这些空间比多复制几次更值钱。反过来,如果元素很大、复制很贵,2 倍增长更划算。

需要强调的是,只要增长倍数是一个大于 1 的常数,均摊就是 O(1)。1.2 倍、1.5 倍、3 倍都成立,只是常数不同。真正会出问题的是「每次只加一个固定数量」,比如容量加 10,那样 n 次追加的总复制量是 n 的平方量级,均摊退化成 O(n),这才是不能接受的写法。

扩容期间的内存峰值

扩容不是「把数组变长」,而是「同时存在两个数组」。新数组申请好之后,旧数组还在,直到复制完成、引用切换过去,旧数组才能被回收。所以峰值内存是旧数组加新数组,而不是新数组本身。

2 倍增长时,长度为 m、容量为 m 触发扩容,新容量 2m,峰值元素数是 m 加 2m 等于 3m。本机十万次追加实测的峰值是 196608 个元素,约等于最后两次扩容时的 65536 加 131072。1.5 倍增长实测峰值是 230423 个元素,比 2 倍还高,因为它的最后一次扩容发生在更大的长度上。

这个峰值对线上服务很实际。一个进程本来占 2GB,扩容一瞬间可能冲到 3GB,容器内存上限如果正好卡在中间,就会触发 OOM(内存不足被强制终止)。多个大数组同时扩容更危险,峰值会叠加,看起来只是「偶尔重启」,其实是复制时的瞬时占用。

本机的整块复制数据可以拿来估算:复制 8388608 个元素约 14.708 毫秒,复制 16777216 个约 22.644 毫秒。这段时间里新旧两块内存都在,如果元素是几十字节的对象,峰值就是几百兆到上 G。均摊分析只管操作次数,不管这段瞬时占用,容量规划要单独算。

如果明确知道数据规模,构造时直接预留容量,能一次性消掉所有扩容、复制和峰值。反之,如果完全无法预估规模,又对单次延迟敏感,就该考虑分块结构,把一次大复制摊成多次小分配。

现象、原因与第一步排查

下面这些现象经常被误判成磁盘慢、GC 抖动或者锁竞争,实际都和扩容的成本模型有关。

现象真实原因第一步查什么
写入偶发几十毫秒尖刺,间隔越来越长动态数组扩容,复制量与当前长度成正比尖刺时刻是否有一次大内存分配或数组复制
平均延迟正常,p999 很难看均摊成本被平均掩盖,最坏单次仍然是 O(n)看最坏那几次的耗时和当时的数据规模
服务越跑越慢,重启后恢复容量翻倍后单次复制变长,且峰值内存上升统计扩容次数和每次复制的元素数
容器偶发 OOM,但常驻内存看起来正常扩容瞬间新旧数组同时存在,峰值远高于稳态对比尖刺时刻的 RSS 与稳态 RSS
换 1.5 倍增长后内存降了但更慢扩容更频繁,复制总量约为 2n统计两种倍数下的扩容次数与复制总量
每次只扩容一点点,耗时随数据量平方增长容量按固定数量增长,不是按倍数检查容量更新是乘常数还是加常数
预留容量后尖刺消失没有扩容就没有复制,均摊问题被绕开构造时是否传入了初始容量
批量导入比逐条写入快很多逐条写入反复触发扩容,批量可以一次预留是否能在导入前算出总量

第一行和第四行最值得记住。第一行是时间上的尖刺,第四行是空间上的尖刺,两者都来自同一次复制。排查时不要只看平均值,也不要只看常驻内存,要把「扩容那一刻」单独拎出来看。很多所谓的偶发问题,其实有着完全确定的触发条件。

边界与代价:均摊不是万能的

均摊分析有三条前提。第一,操作序列必须是连续的,中间不能有别的结构变化把余额清空;第二,增长倍数必须是大于 1 的常数;第三,它只保证总成本,不保证单次延迟。任何一条不成立,O(1) 的结论都要重新检查。

还要注意「均摊」和「平均」的区别。平均是对输入分布取期望,输入变了结论就变;均摊是对最坏操作序列做的除法,不依赖输入分布。所以均摊是更硬的保证。但再硬的保证也只管操作次数,管不了缓存、内存带宽和 GC,实际耗时仍然会抖。

工程上最实用的两条对策:能预估规模就预分配,把扩容从运行期挪到构造期;不能预估就接受偶发尖刺,但要在监控里把它和真正的故障区分开。扩容尖刺有明确特征:耗时和当前长度成正比,间隔按倍数增长,重启后重新开始。

最后是实现的复杂度。手写扩容要处理空数组、容量为零、复制失败、缩容阈值这些边界,代码不长但容易漏。标准库的动态数组已经把这些坑踩过一遍,除非有特殊需求,直接用现成的比自己写更稳。理解均摊,是为了在选型和排查时不被数字骗,不是为了重造一遍轮子。

当天能做的练习

  1. 把本文的 DynArray 敲进编辑器,追加十万次,打印扩容次数、复制总数、复制总数除以 n,确认结果和文中的 17 次、131071 个一致。
  2. 把增长倍数改成 1.5,再跑十万次,记录扩容次数和复制总数,和 2 倍的结果对比,解释为什么复制总量多了约一倍。
  3. 记录每次扩容的耗时,画出「长度与单次扩容耗时」的散点,指出哪几次是明显的尖刺,并说明尖刺的间隔为什么越来越长。
  4. 实现缩容:长度降到容量的四分之一时把容量减半。先用聚合法估算缩容会不会破坏 O(1),再用记账法验证余额是否会变成负数。
  5. 在一个已知规模的导入场景里,分别测「构造时预留容量」和「不预留」两种写法,记录总耗时与峰值内存,说明预分配省掉了什么。
环境说明:本文的扩容次数、复制总量和耗时均来自本机 Node.js 24 的实际运行,规模为十万与一千万两档。不同语言的内存布局和分配器会改变毫秒数,但复制总量、扩容次数与均摊结论与语言无关。

小结与下一篇

三句话收一下:扩容单次要复制全部旧元素,所以最坏是 O(n);但复制总量按 1、2、4 的等比数列增长,n 次追加的总量小于 2n,均摊下来每次 O(1);聚合法、记账法、势能法只是三种算法,结论相同,粒度不同。

下一篇讲空间换时间。均摊分析关心的是「一段时间里的总成本」,而缓存、索引、预计算关心的是「用更多内存换更少的重复计算」。它们经常被混为一谈,其实解决的是不同的问题:前者是把一次大开销摊薄,后者是把重复开销消掉。下一篇会把这三者的适用条件和代价摆在一起。