周三下午,财务的月度报表页又被打爆了。页面每次刷新都要从明细表拉出当月几百万行,按科目分组求和,再按部门排序,本机复现跑一次约三秒。同事加了一层内存缓存:第一次算完存起来,十分钟内再来直接返回,页面从三秒掉到三十毫秒。
第二天问题换了面孔:内存从 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 万、10 万、100 万,查询次数固定为 1000 次,记录建表耗时和两种查询的总耗时,找出前缀和开始划算的查询次数。
- 把前缀和的数组从 Int32Array 换成普通数组,再跑同一组查询,记录耗时差异,并解释类型化数组省掉了什么。
- 写一个带存活时间的缓存,容量固定为 100 条,分别用先进先出和最近最少使用两种淘汰策略,喂同一串访问序列,统计命中率。
- 用本文的斐波那契代码,分别计算 fib(30)、fib(50)、fib(70)、fib(78),记录耗时和返回值,再算 fib(79),说明结果为什么不再精确。
- 给一个真实查询估一次缓存容量:统计一小时内不同键的数量和重复比例,按「不同键到达率乘以存活时间」算出条目数,再乘单条大小,和实际内存对比。
小结与下一篇
三句话收一下:空间换时间换的是重复访问的速度,第一次访问不会更快,甚至更贵;缓存看命中率,索引看查询选择率,预计算看重复次数,三者都要为多存的那份付内存和维护成本;写多读少、内存吃紧、强一致、访问不可预测时,不该换。
下一篇讨论一个相反方向的问题:为什么一个标称 O(n) 的接口,在真实机器上会输给一个标称 O(n²) 的旧实现。答案不在复杂度记号里,而在常数因子、缓存命中率、分支预测和内存分配上。那一篇会用本机的数组遍历和排序测量,说明大 O 只是第一层近似,不是性能结论的全部。