周三下午,财务的月度报表页又被打爆了。页面每次刷新都要从明细表拉出当月几百万行,按科目分组求和,再按部门排序,本机复现跑一次约三秒。同事加了一层内存缓存:第一次算完存起来,十分钟内再来直接返回,页面从三秒掉到三十毫秒。

第二天问题换了面孔:内存从 4GB 涨到 6GB;运营改了科目映射,页面还是旧数字;缓存集中到期那一刻,十几个请求同时回源,数据库连接池被打满,页面又回到三秒。

省下的时间,是用内存、过期窗口和回源风险换来的。这篇拆开讲缓存、索引、预计算各换到什么、各付什么,最后说清什么时候不该换。先定义两个词:空间复杂度指额外内存随数据量怎么增长,时间复杂度指运算次数怎么增长,两者都只讲量级。

现场:三秒变三十毫秒,然后呢

原始逻辑分三段:数据库扫描约两秒,应用层把几百万行按科目累加约一秒,最后序列化成 JSON。缓存加在最外层,键是月份加科目映射版本,值是最终 JSON。

第一个请求缓存为空,照样三秒;之后命中,三十毫秒返回。月初流量集中,命中率高,看起来很好。月中运营频繁改映射,键的版本一直变,命中率掉下去;旧版本的缓存对象还要等到过期才释放,内存一路上涨。

没有哪一步是写错了,错在把缓存当开关,而不是一份要维护的数据。要维护四件事:放什么、放多久、何时作废、装不下丢谁。每次读请求的判断如下。

一次带缓存的读请求
收到读请求
查缓存是否命中
命中就直接返回
未命中则回源计算
写回缓存并返回

图里省掉了一个分支:回源之后、写回之前,数据可能已被别人改过。缓存不是抄一份结果,它引入了一份可能不一致的副本;这份副本由谁保证一致,是设计时第一个要回答的问题。

拆开看:三种常见的换法

空间换时间是一类做法的统称:多存一些东西,让以后少算一些。多存的可以是最终结果、中间结果,或「去哪里找」的目录,对应缓存、预计算、索引。

缓存:存最终结果

把一次计算的输出原样存起来,下次同样的输入直接取。省掉整段计算,代价是要判断「同样」是否成立,以及结果什么时候作废。

索引与预计算:存中间结果

索引存「值在哪里」,预计算存「部分答案」。它们不直接返回给用户,而是让下一次查询少走路、少做重复加法,代价是写入时要同步维护。

工程上要把索引、预计算和缓存分开,因为失效方式不同:缓存可以整体清空重来,索引和物化视图清空一次,可能意味着几分钟业务不可用。

三种形态换来的都是重复访问时的速度,第一次不会更快,甚至更贵。该不该换,核心问题是:会被重复访问多少次,间隔多近。

缓存:命中率决定一切

缓存是一份放在更快介质里的副本。收益不取决于缓存本身多快,而取决于有多少请求能直接拿到副本,这个比例叫命中率。设命中 1 毫秒,未命中回源 3000 毫秒,平均耗时等于命中率乘命中耗时,加上未命中率乘回源耗时。

命中率 95% 时,平均耗时约 150.95 毫秒;99% 时约 30.99 毫秒,命中率只差四个百分点,耗时差了近五倍。命中率 80% 时约 600.8 毫秒,体感仍然是慢,因为每五个请求就有一个在等三秒。

容量和淘汰策略决定命中率的上限。满了必须丢一个,常见规则有先进先出、最近最少使用、最不经常使用。业务访问有热点,最近最少使用通常更合适,但要多维护一条链表或一个计数器,这又是一次小的空间换时间。

失效最难。给每个条目一个存活时间最简单,但同一批数据同时写入会同时到期,所有请求一起回源,这就是缓存雪崩。按写入主动作废要覆盖所有写路径,漏一处就长期不一致。给键带版本号能让旧键自然失效,代价是旧键等过期才释放,内存短期上涨。穿透指查一个不存在的键,每次都不命中,这里不展开。

还有一个成本:缓存对象要能被打散。整个报表 JSON 存成一个大字符串,每次读写都要序列化,命中一次可能从 1 毫秒变成 20 毫秒。拆成按部门的小块,命中率下降,但单次命中更便宜。

线上要看的是命中率和回源次数,不是「缓存有没有开」。只看平均耗时,就分不清是命中率下降还是回源变慢,这两种情况的处理方式完全不同。

索引:用一张目录换更少的路

索引不存结果,存「数据在哪里」。数据库的 B+ 树索引把某一列的值排好序,额外存一棵树。没有索引要从头扫到尾,数据量翻倍时间就翻倍;有了索引,从根走到叶子,层数随数据量对数增长。

索引的代价在写上。每插入一行都要在相关索引里插键,必要时分裂节点;更新被索引字段要删旧键插新键。五个索引就是五套结构,磁盘占用接近翻倍。读多写少划算,写入密集的日志表会被拖垮。

建了索引不代表一定走。优化器会估算走索引再回表和全表扫描哪个便宜:返回大部分行时全扫可能更快,选择性很高时索引才占优。覆盖索引是延伸,查询字段都在索引里就不用回表,相当于多存一份副本换掉一次随机读。

预计算:前缀和的实测

预计算把重复的部分提前算好。报表最常见的是区间求和:反复问从第 l 个到第 r 个元素的和是多少。最直白的做法每次加一遍,总成本是查询次数乘区间长度。

前缀和先算另一个数组,第 i 项存前 i 个元素的和,之后任意区间和是两个前缀值相减。多存一个长度加一的数组,把每次查询从加一遍变成减一次。

function buildPrefix(a) {
  const p = new Int32Array(a.length + 1);
  for (let i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
  return p;
}
function sumRange(a, l, r) {
  let s = 0;
  for (let i = l; i <= r; i++) s += a[i];
  return s;
}

const N = 200000;
const arr = new Int32Array(N);
for (let i = 0; i < N; i++) arr[i] = (i * 7) % 1000;
const prefix = buildPrefix(arr);
// queries 是 2000 个随机区间,平均长度约 46091
const total1 = queries.reduce((s, [l, r]) => s + sumRange(arr, l, r), 0);
const total2 = queries.reduce((s, [l, r]) => s + prefix[r + 1] - prefix[l], 0);

本机 Node.js 24 的结果:20 万个整数,建一次前缀数组约 0.592 毫秒;2000 次查询,每次重新求和总耗时约 356.74 毫秒,平均每次约 0.1784 毫秒;换成前缀和后总耗时约 2.3144 毫秒,平均每次约 0.00116 毫秒。两边算出的总和都是 46052112916,说明测的不是错代码。按平均每次算,差距约 154 倍。

这笔账只在查询足够多时划算。只查一次,建表的 0.592 毫秒是纯亏。20 万个 32 位整数约 800KB,若有 1000 个月份各建一份就是 800MB;预计算的空间要按份数相乘,不是按单份多大看。

另一个边界是数值范围。元素小于 1000 时总和约 1.99 亿,32 位整数放得下;十亿级金额很快就会溢出,要换 64 位或浮点,空间翻倍,误差要重新评估。

记忆化:把递归树剪掉

缓存也可以存在一个函数内部:同样的参数反复调用,把参数和结果记下来,下次直接返回,这叫记忆化。它和缓存是同一件事,只是粒度更细。

最典型的是朴素递归求斐波那契:第 n 项等于前两项之和。直接按定义写,fib(30) 会把同一棵子树反复算很多遍,调用次数随 n 指数增长。

function fibNaive(n) {
  return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
const memo = new Map([[0, 0], [1, 1]]);
function fibMemo(n) {
  if (memo.has(n)) return memo.get(n);
  const v = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, v);
  return v;
}

本机结果:朴素 fib(30) 约 5.69 毫秒,返回 832040;记忆化版本约 0.0033 毫秒,快约 1736 倍。记忆化算 fib(70) 约 0.0061 毫秒,返回 190392490709135。对比已包含清空表的成本,否则差距只是指数级调用和线性级调用的区别。

多花的内存是不同参数个数乘每个结果的存储开销。fib(30) 只有 31 个参数,表很小;参数是字符串或对象时,表可能比结果还大。先数不同输入有多少,再估每个输入被重复调用多少次,两者都不合适时,表只会白占内存。

数字边界:JavaScript 的 Number 只能精确到 2 的 53 次方减一,约 9.007 乘 10 的 15 次方。fib(78) 还在范围内,fib(79) 约 1.447 乘 10 的 16 次方,已经超出。记忆化能让它算得快,不能让浮点数变准;换的是时间,不是精度。

命中率怎么估,容量怎么定

先用访问日志估命中率:把最近一天的键取出来,看重复键占多少、重复间隔多长。九成请求落在 100 个键上,缓存这 100 个键就有高命中率;键几乎都是新的,缓存只会变成一块只写不读的内存。

容量约等于每秒不同键的到达数乘平均存活时间。每秒 100 个不同键、存活 600 秒,稳态约 6 万个条目,再乘单条大小就是内存下限。真实流量有高峰,通常要留一倍余量,否则高峰频繁淘汰,命中率会低于估算。

命中率下降先分清容量不够还是数据变了。前者淘汰次数高、键的实际存活时间远小于设定;后者键还在但版本变了,或写入后立刻作废。前者加内存或缩短存活时间,后者改失效策略。混在一起时,最常见的错误是把存活时间调长,结果数据更不准。

还要提前算回源失败的账。缓存没命中不可怕,可怕的是所有未命中请求同时回源。给回源加并发上限,或让一个请求去算、其他请求等结果,这叫请求合并,拿一点等待换数据库稳定。

现象、真实原因与第一步查什么

下面这些现象在「加了缓存、索引或预计算」的系统里很常见。它们看起来像性能问题,根子往往在一致性或容量上。按第三列先查一件事,不要一上来就扩容。

现象真实原因第一步查什么
加缓存后页面还是慢命中率低,大部分请求仍在回源命中率与回源次数,而不是总平均耗时
内存持续上涨,重启后恢复旧版本键没有及时释放,缓存条目只增不减缓存条目数、键的版本策略、过期时间
运营改配置后页面数字不变缓存键没有包含配置版本,旧结果仍被命中缓存键由哪些字段组成
整点前后数据库连接被打满大批缓存同时到期,请求集中回源过期时间是否加了随机抖动
写入变慢,磁盘占用翻倍索引过多,每次写入都要维护多套结构表的索引数量与写入路径
建了索引查询仍然全表扫描查询要返回大部分行,优化器判断全扫更便宜执行计划里的扫描行数与选择率
预计算任务越来越慢预计算的数据份数随维度组合增长一共预计算了多少个分组,而不是单份多大
预计算后结果对不上源数据已更新,物化结果没有重算重算触发条件与更新延迟

第一行和第四行最容易被误判。看到慢就加机器,但命中率只有三成时,加机器只是让更多请求同时回源;看到数据库抖动就查慢查询,其实原因是到期时间都设成了整点。顺序应该是先看命中,再看未命中量,最后看回源为什么慢。

什么时候不该换

空间换时间有明确的失效条件,下面四种情况要谨慎,甚至应该直接拒绝。

第一,写多读少。缓存的收益来自重复读,写完就很少再读的数据,缓存只会增加一次写入和一次作废。写入密集的表上堆索引,维护成本也会超过查询节省的时间。

第二,内存比时间贵。缓存把内存打满会触发交换或频繁回收,整个进程都变慢;在容器里超限还会被直接杀掉。用 2GB 内存换 200 毫秒,在报表页可能值得,在逼近内存上限的服务里可能直接导致故障。

第三,数据必须强一致。缓存天生是副本,副本和源之间一定有时间差。支付余额、库存扣减、权限变更这类读,宁可慢也要读源;写完立刻读到新值的业务,不能把这类读交给缓存。

第四,访问模式不可预测。键几乎都是新的,或每次查询条件都不同,缓存条目只会快速堆积又快速淘汰,命中率很低,还额外占内存。这时该优化查询本身,而不是再加一层缓存。

还有一种情况:数据量很小,已经全在内存里。几百条配置直接遍历只要几十微秒,加缓存反而多了一次哈希和一次判断。空间换时间是为重复且昂贵的计算准备的。

当天能做的练习

  1. 用本文的前缀和代码,把数组长度改成 1 万、10 万、100 万,查询次数固定为 1000 次,记录建表耗时和两种查询的总耗时,找出前缀和开始划算的查询次数。
  2. 把前缀和的数组从 Int32Array 换成普通数组,再跑同一组查询,记录耗时差异,并解释类型化数组省掉了什么。
  3. 写一个带存活时间的缓存,容量固定为 100 条,分别用先进先出和最近最少使用两种淘汰策略,喂同一串访问序列,统计命中率。
  4. 用本文的斐波那契代码,分别计算 fib(30)、fib(50)、fib(70)、fib(78),记录耗时和返回值,再算 fib(79),说明结果为什么不再精确。
  5. 给一个真实查询估一次缓存容量:统计一小时内不同键的数量和重复比例,按「不同键到达率乘以存活时间」算出条目数,再乘单条大小,和实际内存对比。
环境说明:本文的前缀和与斐波那契数据用 Node.js 24 在本机实际运行,输出与文中一致;三组命中率平均值也由本机计算脚本算出。不同机器、不同 JavaScript 引擎的数字会有差异,文中的毫秒数只用于比较量级,不是性能承诺。

小结与下一篇

三句话收一下:空间换时间换的是重复访问的速度,第一次访问不会更快,甚至更贵;缓存看命中率,索引看查询选择率,预计算看重复次数,三者都要为多存的那份付内存和维护成本;写多读少、内存吃紧、强一致、访问不可预测时,不该换。

下一篇讨论一个相反方向的问题:为什么一个标称 O(n) 的接口,在真实机器上会输给一个标称 O(n²) 的旧实现。答案不在复杂度记号里,而在常数因子、缓存命中率、分支预测和内存分配上。那一篇会用本机的数组遍历和排序测量,说明大 O 只是第一层近似,不是性能结论的全部。