01 时间与空间的权衡：所有优化的第一性问题

开篇提问

先给你一道题，别急着算，先凭直觉猜：

你要在一台 8GB 内存的机器上，对一个 100GB 的文件排序。怎么做？

这不是脑筋急转弯，这是真实世界里天天发生的事。而你解决这个问题的方式，本质上就是用时间换空间——一次读一部分、排序、写回，最后归并。

那么问题来了，请往深里想一层：

为什么”时间和空间可以互相换”这件事成立？它的物理根源是什么？如果内存无限大、CPU 无限快，这个权衡还存在吗？

想清楚这个，你就拿到了理解计算机领域一半优化手段的钥匙。因为时空权衡不是一种技巧，它是所有优化的第一性原理——索引、缓存、压缩、记忆化、预计算，所有这些手段，扒开皮都是同一件事。

子主题一：时空可换的根源——信息是可以被”重算”的

时间能换空间，是因为：任何一份数据，要么你存着它（占空间），要么你在需要时重新算出来（花时间）。

这就是全部的秘密。

斐波那契数列：递归算 fib(40) 要算几亿次（花时间、不存东西）；用数组把中间结果存下来（占空间、但只算 40 次）。这就是”记忆化”。
数据库索引：不建索引，查一条数据要全表扫描（花时间）；建了 B 树索引（占空间），几次磁盘 IO 就定位到。
压缩：存原始数据（占空间大、读出来直接用）；存压缩数据（占空间小、每次读要解压花时间）。

你会发现它们的共同结构：存在一个”中间结果”，你选择”存”还是”算”。

那什么情况下”存”划算、什么情况下”算”划算？这里有个简单的判据：

如果一份数据的”重算成本 × 使用次数” > “存储成本”，那就该存；否则该算。

这个判据看着简单，但它能解释大量工程决策：热点数据才值得缓存（使用次数高）、大表才需要索引（重算成本高）、冷数据该压缩（使用次数低，宁可每次解压）。

子主题二：这个权衡为什么无法被消除

你可能会想：内存越来越便宜、CPU 越来越快，这个权衡总有一天会消失吧？

不会。原因有三层，一层比一层硬：

第一层：存储和计算都受物理定律约束。 存储密度受材料、功耗、散热限制；计算速度受光速、晶体管开关速度、散热限制。两者都在进步，但它们的比值不会无限变化——因为两者共享同一套物理基础。

第二层（更硬）：存储离计算越远，访问越慢。 这是内存层次结构的必然：寄存器最快也最贵、L1/L2/L3 缓存次之、内存再次、磁盘最慢也最便宜。这不是设计缺陷，这是成本约束下的最优解——你不可能把 100TB 数据都放在寄存器里。

第三层（最硬）：问题规模的增长快过硬件进步。 数据量的增长（互联网、IoT、视频）常年快过存储和算力的增长。摩尔定律放缓之后，这个差距更明显了。硬件永远追不上需求的膨胀，所以权衡永远存在。

所以时空权衡不是”暂时的技术问题”，而是一个结构性事实。所有优化，本质都是在给定的硬件和约束下，重新分配”哪部分花时间、哪部分花空间”。

子主题三：时空权衡的几种经典形态

我们要把这个抽象原理，落成你能认出来的具体形态。

形态一：用空间换时间（最常见）

缓存 / 记忆化：存中间结果
索引：存额外的数据结构
预计算：提前算好（比如报表预聚合）
冗余存储：多存几份副本，就近读取

形态二：用时间换空间

压缩：存得少、读时解压
流式处理：不把全量数据加载进内存，边读边处理
外部排序：内存装不下就分块排序再归并
虚拟化 / 按需分页：不用的页换出到磁盘

形态三：双向优化（既省时间又省空间，罕见但珍贵）

算法改进（比如快排替代冒泡，时间和空间都更优）
数据结构的重新设计（比如用位图替代布尔数组）
更紧致的数据布局（结构体字段重排减少 padding）

形态四：把权衡”转移”给别人（工程里最常用的一招）

把计算从运行时转移到编译时（编译器优化、模板展开）
把计算从在线转移到离线（预计算、批处理）
把计算从服务端转移到客户端（前端渲染、CDN）

第四种形态特别值得你记住：很多时候”解决”一个权衡的方式，不是平衡它，而是把它挪到一个成本更低的地方去。 这是工程上最高级的一类解法——你没消灭矛盾，你只是找了个更便宜的地方让它发生。

子主题四：怎么判断”该往哪边换”

落到实际工作，你面对一个性能问题时，怎么决定该花空间还是花时间？给你一个可操作的判断流程：

先量化代价：存这份数据要多少空间？重算要多少时间？使用频率多高？
找真正的瓶颈：是空间不够（OOM、磁盘满），还是时间不够（延迟高、超时）？只能优化那个真正的瓶颈——内存都爆了你还去预计算，是加速崩溃。
看访问模式：是随机访问还是顺序访问？热点集中还是分散？局部性好的场景，空间换时间的收益最大（缓存命中率高）。
算收益：用前面那个判据，“重算成本 × 使用次数” 是否真的大于 “存储成本”？别凭感觉，算一算。

最后提醒一句：这个权衡不是”选一次定终身”的。随着数据量、访问模式、硬件的变化，最优解会漂移。所以好的系统会把这个选择做成可调的参数（缓存大小、批大小、压缩级别），而不是写死在代码里。

子主题五：记忆化与动态规划——空间换时间最干净的范式

我们先从你最熟的东西开刀，但请你用全新的眼光看它。

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

这段代码慢得离谱，fib(40) 要算几亿次。可你有没有停下来问过一句：它到底在重复算什么？为什么重复的偏偏是”同样的东西”？

把递归树画出来你就看到了：fib(35) 被算了一次又一次，fib(30) 被算了成千上万次。整个递归树里，不同的子问题只有 41 个，但被计算了几亿次。

这就是关键概念——重叠子问题（overlapping subproblems）。

请你咬住这个词，因为它是整个”空间换时间”能成立的充要条件：

只有当”同一份中间结果会被反复用到”时，把它存下来才划算。

反过来说，如果一个问题的子问题彼此不重叠（比如归并排序，左右两半处理的是完全不同的数据段），你存中间结果就是纯亏——存了，永远没人再来读。这就是分治和动态规划的分界线，不是”递推 vs 递归”，不是”循环 vs 函数”，而是子问题重不重叠。你觉得呢？很多人背了十年 DP 模板，却没意识到区别在这一层。

买空间，就是给子问题”编号”

记忆化（memoization）的做法最朴素：加个哈希表或数组，算完存进去，下次先查。

memo = {0:0, 1:1}
def fib(n):
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

几亿次变成几十次。你付出的代价是一个数组，买到的是指数级的时间。

但这里有个更深的洞察，值得你停一下：

DP 数组的每一个维度，本质上是你为”描述一个子问题”所付的空间租金。

一维 DP（比如背包）意味着”子问题只需要一个参数就能区分”；二维 DP（比如最长公共子序列）意味着要两个参数；区间 DP 要三个量级的空间，因为子问题是一个区间。维度的增加 = 子问题空间的膨胀 = 你要买更多空间。

那么问题来了：买来的空间里，每一格都是必需的吗？

滚动数组：空间换时间内部，还有一层再权衡

一维背包可以压缩成一维数组，二维 LCS 可以压成两行。这叫滚动数组（rolling array）。

为什么能压？因为依赖模式决定了”哪些历史必须留下”。背包 dp[i][j] 只依赖 dp[i-1][...]，所以 i-2 及更早的行就是废物——它们再也不会被读了，占着内存纯属交了冤枉租金。

但 Floyd 不能这么压（留给你自己想，答案就在它的三重循环顺序里）。

这里藏着一个非常实用的判断习惯，我希望你带走：

拿到一个”空间换时间”的方案，先问一句：它买的这块空间里，有多少格是会被反复读的？有多少格写完就再没人看了？

后者就是可优化的空间。缓存里塞了一堆永不过期也永不命中的 key，是同一个毛病的不同马甲。

第二个例子：最短路径里的三方博弈

斐波那契太简单，我们换个能打的真实问题：求任意两点间的最短距离（All-Pairs Shortest Path）。

方案 A：对每个点跑一次 Dijkstra。稀疏图上大抵是 O(V · E log V)，空间 O(V + E)。方案 B：Floyd-Warshall。三重循环，O(V³) 时间，O(V²) 空间。

哪个快？取决于图是稠是疏。

稠密图（E 接近 V²）：A 退化成 O(V³ log V)，B 是 O(V³)。B 赢，而且 B 只需要一个二维数组，实现只要五行。
稀疏图（E 接近 V）：A 是 O(V² log V)，A 完胜 B 的 O(V³)。

你看出味道了吗？Floyd 是典型的”用 O(V²) 的空间，把很多冗余的重算一次性合并掉”；而”跑 V 次 Dijkstra”是”不买那份大数组，宁可把中间结果扔了重算 V 遍”。

同一道题，同一套”存还是算”的判据，因为**图的形状（数据分布）**不同，最优解直接翻转。

这就是为什么我反复强调：**时空权衡没有标准答案，只有”在你的数据分布下的答案”。**所有脱离数据分布谈”该不该建索引/该不该缓存”的讨论，都是空转。

一个狠类比

记忆化就像错题本。

错题本值钱的前提是：同一类题你会反复错。如果你做的每张卷子都是全新的题型，那么认认真真整理错题本，就是每天花两小时抄写永远不再看的纸——勤奋地浪费。

工程里最常见的同类浪费是什么？给一个参数空间近乎无限、key 永远不重复的接口加缓存。命中率 0.3%，内存却涨了 4 个 G。你不是在做优化，你是在用内存发电。

顺带说一个”记忆化没有、但缓存有”的麻烦

记忆化的 fib 是纯函数：同样的 n，永远得到同样的结果，所以存下来的东西永远有效。

现实世界的接口不纯。数据库里的那行数据会被别人改掉。于是缓存多出一个记忆化完全没有的问题：失效（invalidation）。

这提醒你一件事：**“空间换时间”里，你买的那些空间，买的不只是字节，还买了”维护这些字节与真实世界一致性”的债。**存的东西越多、活得越久，这笔债越重。

记住这句话，后面讲多级缓存的一致性灾难时，你会再见到它。

子主题六：预计算与离线计算——把时间成本搬到”另一个时间点”

现在换个战场。

你的运营后台首页要显示”过去 30 天 GMV”，底下是几亿行订单明细。每次打开页面都去 SUM(amount) 一遍？

当然不。你会建一张日汇总表，定时跑批，页面直接查那张小表。

看起来平平无奇。但请你往深里想一层：这个动作的本质是什么？

你把成本从”读路径”搬到了”写路径”。

数据写入时（或定时批处理时）多做一点事，换取每次读取时少做很多事。这不是”消灭了计算量”，而是把计算挪到了一个发生次数更少的地方——正好呼应子主题三的第四种形态。

预计算的三种姿势

姿势	做法	代价	适用
全量重算	每晚把汇总表整个重刷	计算量大、有”数据窗口”空白期	逻辑复杂、变化频繁、容忍 T+1
增量更新	每来一条流水就更新汇总	写路径变复杂、要保证幂等	实时性要求高
物化视图	由数据库/引擎维护，声明式	维护开销、刷新策略难调优	中等实时性、不想自己写同步逻辑

三者没有优劣，只有新鲜度 vs 成本的不同切点。

**这里出现了一个新维度：数据新鲜度。**你会发现它其实也是权衡家族的一员——用”延迟”换”吞吐/成本”。批处理里的经典权衡（延迟 vs 吞吐）换个马甲又来了。

立方体爆炸：为什么不能什么都预计算

假设你有 5 个维度：时间、地区、品类、渠道、用户等级。老板说”我要能按任意组合下钻”。

天真做法：把所有维度组合的聚合结果都算出来存着。5 个维度的组合数是 2⁵ = 32 个立方体（这还只是组合，没算每个维度内部的层级：年/季/月/日、省/市/区……）。维度一多就是组合爆炸。

所以现实中的做法是：只预计算高频组合，剩下的让它现算。

你看——又是那个判据：**“重算成本 × 使用次数 > 存储成本”才该存。**冷门的维度组合使用次数低，就让它每次慢慢算。

这个思路在 OLAP 里叫”预聚合立方体的剪枝”，在缓存里叫”只缓存热点”，在索引里叫”只给高频查询建索引”。**三个领域，同一个公式。**你还能想到第四个吗？

CDN 预热：把”分发”挪到用户到来之前

预计算还有一个漂亮的变体——CDN 预热（pre-warming）。

不预热的时候，第一个用户访问某个资源，CDN 边缘节点没有，回源拉取，慢；后面的用户才快。这就是冷启动惩罚。

预热就是：发布新版本时，主动把资源推到边缘节点，或者主动发一波请求触发回源。把”第一次访问的慢”，从用户身上挪到了发布流程里。

为什么这招好使？因为用户的耐心比发布流水线的耐心贵得多。同样是等 3 秒，流水线等得起，用户等不起。

把成本挪到”更能承受它的地方”——这就是子主题三第四种形态的精髓。请记住这个句式，它在本章剩余部分还会出现两次。

编译期计算：同一招，挪到了构建阶段

常量折叠：2 * 60 * 60 在编译期就算成 7200。
模板元编程 / constexpr / comptime：把斐波那契在编译期算完，运行时只剩一个常量。
循环展开：省掉循环控制的分支与自增指令，代价是指令变多。
查表法：把三角函数、CRC、伽马校正的结果预先算成表，运行时只做一次数组寻址。这是编译期预计算 + 运行期记忆化的混合体，嵌入式和图形学里遍地都是。

现在请你回答我刚才那个问题：编译期计算和预计算报表，是同一件事吗？

是的。结构完全一致：都存在一份”中间结果”，都存在两个时间点（A 点算、B 点用），你选择在哪一点算。报表选择”离线批处理时算”，编译期计算选择”构建时算”。判断依据也一致：哪边发生次数少、哪边更能承受延迟，就把计算放哪边。

一记回旋镖：编译期计算也会伤性能

别以为把东西全塞进编译期就赢了。看两个反噬：

编译时间爆炸。模板元编程玩嗨了，一次全量构建从几十秒涨到十几分钟，迭代速度垮掉。你省了运行时的时间，赔上了开发者的时间——而开发者的时间往往比 CPU 时间贵几个数量级。这笔账算过吗？
代码膨胀伤 I-cache。激进的循环展开和模板实例化会让二进制体积暴涨。指令也是要占缓存的（I-cache，通常也就几十 KB 量级），代码太大 → 指令缓存命中率下降 → CPU 取指停顿 → 你省下的计算时间，被取指的等待吃回去了。

这就是时空权衡最阴险的地方：**它会在你没注意的层次上，把账重新算一遍。**你以为自己在 L1 这一层赢了，结果在 I-cache 那一层输了。

所以：任何”纯赢”的优化宣称，都值得你追问一句——成本被挪到哪一层去了？

子主题七：压缩——时间换空间，以及它为什么会”反向双赢”

压缩的本质，一句话：你存的不是数据本身，你存的是”能重新生成这份数据的一段程序”。

读的时候，跑一遍这段程序（解压），数据就回来了。**存 = 空间，跑 = 时间。**完美吻合我们最开始那个定义：“要么存着，要么重算”。

狠类比：宜家

压缩就是宜家的平板包装。

一件组装好的衣柜，体积巨大，运输成本极高；拆成板件装箱，一辆车能拉十倍的货——但你（或快递小哥）得花一小时把它拼起来。

**宜家的整个商业模式，本质上是”把空间成本换成顾客的时间成本”，然后用低价把这笔账补给你。**它在用你的时间补贴它的物流。想通这一点，你就再也不会觉得”压缩”只是个技术细节了。

压缩率与速度的光谱

现实中没有”最好的压缩算法”，只有一条你必须在上面选一个点的光谱：

省空间 ◄──────────────────────────► 省时间
 xz/brotli(高比率)  gzip   zstd   lz4/snappy   不压缩

不同场景选不同点：

归档冷数据（几乎不读）：选左端。压缩慢无所谓，一次压缩终身省空间。
日志/消息队列（写多、偶尔读）：选中段，zstd 之类性价比高。
内存缓存/RPC 序列化（高频读写）：选右端甚至不压缩。压缩延迟会直接叠在你的 P99 上。

注意这和子主题四最后那句话的呼应：**这个选择必须做成可配参数，不能写死。**今天你的服务 CPU 有余、带宽紧张，明天加了机器、带宽升级，最优解就漂走了。

反直觉：压缩有时反而更快

这一点非常重要，很多人第一次听会愣住。

当 IO 是瓶颈时，压缩能让读写变快。

算一笔账：从磁盘读 1GB 数据，做 100MB 的解压计算。磁盘 IO 省了约 900MB，多花了些 CPU。如果 IO 那 900MB 的时间 > 解压的 CPU 时间，总耗时下降。

同样的道理在内存里更明显：现代 CPU 的核心痛点常常不是算力，而是内存带宽和访存延迟。把数据压小了 → 同样一次内存访问能带回来更多有效数据 → 缓存能装下更多东西 → 访存次数减少，反而更快。

工程上真这么干的：

指针压缩（JVM 的 compressed oops）：64 位地址压成 32 位偏移，省内存还提升缓存命中。
变长整数编码（varint / zigzag）：小数字用 1 字节存。
字符串驻留（interning）：重复的字符串只存一份，用指针引用。
字典编码 / 位图索引：把长字符串换成小整数 id。

于是出现了那个美妙的结论：

**“时间换空间”和”空间换时间”不是两条平行线，它们会在 IO/带宽这个瓶颈点上交叉。**在算力过剩、带宽稀缺的系统里，压缩这个”时间换空间”的操作，结果是时间和空间双降。

**判断条件就一句：你省的 IO/带宽时间，是否大于你新增的 CPU 时间。**算一算，别猜。

什么时候不该压缩

三个红灯：

数据本身已经压缩过（JPEG、H.264、已经 gzip 的内容）。再压一遍，CPU 白烧，体积几乎不变，甚至变大（因为要加头部）。
需要高频随机访问单条记录。压缩通常是块级的——改一个字节可能要重写整个块、或者读一条记录要解压整个块。页级压缩（数据库常见做法）就是在这两者之间找平衡：块要大到有压缩收益，又要小到随机读写不亏。
CPU 已经打满。这时候压缩就是在已经堵死的高速公路上再塞一辆车。

列式存储：压缩率为什么能高一个量级

铺垫到这里，列存（columnar storage）的道理就非常自然了。

行存把一整行数据挨着放：

[id=1, name="张三", city="北京", age=28, amount=99]
[id=2, name="李四", city="上海", age=35, amount=150]

列存把同一列的数据挨着放：

city: "北京", "上海", "北京", "北京", "广州", ...
age:   28,     35,     31,     29,     41,    ...

为什么列存压得动、行存压不动？三个理由，一个比一个深：

**局部同质，熵更低。**一列里全是同一种类型、同一种语义、值域相近的数据。“城市”这一列只有几千个取值，重复度极高；而一行里混合了字符串、整数、金额，像一盘炒饭，没法针对任何一种食材优化。
天然适配专用编码。列存可以用字典编码（几千个城市名 → 一个字符串数组 + 一堆整数 id）、RLE 行程编码（排好序的列里连续相同值压成一个 (值, 次数)）、位图、差值编码（时间戳列存差值，数字一下子变得很小）。这些招数在行存里基本用不上，因为”邻居”和自己的类型都不一样。
顺带省了 IO。分析查询通常只关心几列。SELECT city, SUM(amount) FROM t GROUP BY city 只读两列，另外几十列根本不碰。

第 3 点其实已经不是压缩了，是减少读取量。所以准确地说，列存带来的是三重收益叠加：少读 + 好压 + 向量化执行友好。

留一个伏笔：**列存不是”又一种压缩技巧”，它是”重新安排数据布局，让压缩算法有东西可压”。**先改变数据的排列，再谈算法——这个顺序在工程里反复出现（结构体字段重排、数据对齐、把 AoS 改成 SoA，全是同一招）。这一层我们点到为止，第 22 章会专门拆开讲。

子主题八：流式处理与外部排序——内存装不下怎么办

回到开篇那道题，这次正式解。

8GB 内存，100GB 文件，请排序。

外部排序：多趟 IO 换内存

标准做法，四步：

分块：每次读 8GB（留一点余量，比如每块 1GB），在内存里用快排/堆排序排好。
写回：把每块有序的结果写成临时文件（run）。100 个 1GB 的有序段。
多路归并：开 100 个读句柄，每次从每个文件的当前位置取最小的一个输出。
用堆加速：维护一个大小为 k（k = 归并路数）的小顶堆，每次取堆顶，再从对应文件补一个进来。每次比较 O(log k)。

空间：O(k) 的输入缓冲（每路一个 buffer）+ 输出缓冲，都在内存里。时间：多读一遍、多写一遍，加上归并时的随机/交织 IO。

这就是典型的时间换空间：用磁盘空间 + 多趟 IO 时间，换掉了”必须一次性装进内存”的要求。

现在问你个更细的问题：内存变大了，这个算法会变快吗？会，为什么？

因为归并路数 k 受内存限制——每开一路就要一份输入缓冲区，内存越大，k 越大。归并趟数大致是 log_k(N/M)（N 是总数据量，M 是内存大小）。k 从 10 涨到 100，趟数直接砍半。

**你加的内存没有让”装得下”这件事发生质变，它买的是”更少的 IO 趟数”。**内存买时间，又一次应验。

（顺带一提，真实系统里还有两个手法：败者树降低多路归并的比较次数；**替换选择（replacement selection）**让初始 run 的长度超过内存大小。原理不展开，但你要知道这类”在常数和趟数上继续抠”的技巧确实存在。）

流式处理：一趟搞定，永不 materialize

外部排序允许多趟。流式（streaming）更狠：只允许一趟，且内存恒定。

一条管道：读进来 → 处理 → 吐出去。数据像水流过，从不整体停留。

哪些运算能流式做？

能流式	不能流式（或很难）
filter / where	sort（全局有序要求看到全量）
map / 投影	distinct / 去重
可结合的聚合：sum / count / min / max	精确中位数、精确分位数
采样、限流	大表 join（除非一边能装进内存）
正则匹配、ETL 清洗	group by 基数极高时

**判据是什么？**两条：

运算是否可结合（associative）：(a+b)+c == a+(b+c)。可结合意味着你可以拿着一个”部分结果”往前走，永远不需要回头——这个部分结果就是你的常数级状态。sum 的状态是一个数，count 是一个数，min/max 是一个数。
运算是否需要全局视野：排序需要知道”全天下最小的那个是谁”，不看完不敢输出。

请你用这两条判据去套一遍上表，看看是不是严丝合缝。套完你会发现：**能不能流式，本质上是”维持正确输出所需的最小状态有多大”。**状态是 O(1) → 随便流；状态是 O(N) → 流式不了。

而这个”状态”，就是你为了省空间而付出的时间债的反面——它是你为了省时间而必须留下的空间。看，又回来了。

实在流式不了怎么办？牺牲精度

这就是近似算法登场的时刻：

HyperLogLog：估算去重计数（UV）。十亿级别的基数，用 KB 级内存，误差在百分位量级。
Count-Min Sketch：估算某个 key 的出现频次。用多个哈希 + 一个二维计数数组，只会高估不会低估。
Bloom Filter：判断”某元素是否可能存在”。省掉大量无效的磁盘/网络查询，用一点点假阳性换巨大的空间节省——这是数据库和分布式系统的常青树。
蓄水池抽样：从未知长度的数据流里等概率抽 k 个，内存 O(k)。
t-digest / 分位数草图：估算 P99、P95。

这些算法的共同点：它们放弃了精确性，换取了 O(1) 或 O(k) 的空间。

那问题来了：近似算法算不算时空权衡？

我认为算，而且是它的自然推广。更准确地说，真实的资源权衡是一个三角：

             时间
              /\
             /  \
            /    \
           /  精度  \
          /__________\
       空间

**时间、空间、精度，三者你最多按下去两个。**Bloom Filter 用精度换空间；流式聚合用精度换空间和时间；精确排序三个都不肯放手，于是只能吃多趟 IO。

**当你发现”存也存不下、算也算不完”时，正确的反应不是更努力地优化，而是问一句：能不能不要那么准？**这是工程上被严重低估的一招。

外部排序 vs 流式：怎么选

一句话：看你能不能”重放”数据。

数据在磁盘/对象存储上，可以反复读 → 外部排序，多趟无所谓。
数据来自消息队列/网络流，读一次就没了 → 必须流式（或者先落盘把它变成可重放的，这本身又是”用空间换能力”）。

“能不能重放”这个性质，比算法本身更能决定你的设计空间。这也是为什么日志（WAL、Kafka）在现代系统里地位这么高——它把”只能流一次的数据”变成了”可以重放的数据”，用磁盘空间买来了架构上的灵活性。这笔买卖划算得离谱。

子主题九：分层——时空权衡最优雅的工程解

现在到了本章我最想让你带走的一节。

先看一个现象，请你自己解释它：

一台机器里有：寄存器、L1、L2、L3、内存、SSD、HDD、网络存储、磁带库。一个系统里有：CPU 缓存、进程内缓存、Redis、本地磁盘、数据库、对象存储、离线数仓、冷备份。

为什么需要这么多层？做一个”又快又大又便宜”的东西不行吗？

不行。因为这三个属性在物理上互斥：

快 → 必须离计算近 → 面积受限、功耗密度高 → 贵且小
大 → 必须靠材料堆叠 → 离计算远、寻址慢 → 慢
便宜 → 必须用低成本介质 → 慢，或者易失/易损

没有任何单一介质能同时占住三角形的三个角。

于是人类想出的解法是：不要试图在一个介质上解决矛盾，要用一串介质，让每一层只负责一段。

这就是分层（tiering / hierarchy）。

狠类比：你的办公桌

想想你怎么安排手边的东西：

桌面上：正在写的那份文件、昨天没看完的三页纸。伸手就到，但桌面只有两平米。
抽屉里：这周要用的资料。起身拉开，几秒钟。
柜子里：这个月的项目。走过去翻，一分钟。
地下室/仓库：今年的归档。开车去，一小时。

你不会把所有东西摊在桌上（放不下），也不会为了找一支笔跑一趟仓库（慢死）。你本能地按”使用频率”分了层，并且本能地把常用的往上提、不常用的往下沉。

计算机的内存层次结构，就是这套办公桌逻辑的硅基版本。而你作为工程师做的事，无非是决定什么放桌面、什么进仓库。

分层到底”优雅”在哪

三个理由：

第一，它把”全局的二选一”拆成了”多个局部的二选一”。

不分层的世界里，你要做一个痛苦的决定：“这份数据放内存还是放磁盘？“——非黑即白。

分层的世界里，你问的是：“这份数据该待在哪一层？“——这是个连续的光谱。热数据放 L3，温数据放内存，冷数据放 SSD，冰数据放对象存储。选择从布尔值变成了枚举值，而且可以随时迁移。

第二，它自动利用了”局部性”。

分层能生效，靠的是两条经验规律：

时间局部性：刚被访问过的数据，很可能马上再被访问。
空间局部性：刚被访问的数据，其邻居很可能马上被访问。

后者直接解释了**缓存行（cache line）**的存在：CPU 不只把你请求的那个字节取进来，而是把周围一整块（量级上几十字节，常见 64 字节）一起搬。赌的就是”你要了 a[0]，八成立刻要 a[1]”。这个赌注十赌九赢，这才是分层敢这么设计的基础。

同样的规律在软件层一遍遍重现：磁盘预读、数据库的 page（而不是 row）、Kafka 的顺序写与批量拉取、列的向量化读取。全都是”一次多拿点，赌你接着要”。

（副作用也一并记住：伪共享 false sharing——两个线程写同一缓存行里的不同变量，会导致缓存行在两个核之间来回弹。你享受了空间局部性的好处，就得承担它的耦合成本。世上没有单边的好事。）

第三，它让每一层可以独立演进。

换 SSD 不用改应用代码；加一层 Redis 不用改存储引擎。分层给系统装了”可替换的关节”。这是它能在工程上长盛不衰的真正原因——不只是性能好，而是好改。

命中率：为什么 90% 到 99% 是天壤之别

来算一笔简单的账，数字取公认量级，只为说明关系：

设快速层访问约 1ns（L1 量级），慢速层约 100ns（内存量级）。

命中率 90%：平均 ≈ 0.9 × 1 + 0.1 × 100 ≈ 11ns
命中率 99%：平均 ≈ 0.99 × 1 + 0.01 × 100 ≈ 2ns

命中率只涨了 9 个百分点，平均延迟却差了约 5 倍。

**为什么？**因为决定平均延迟的是那个”未命中的小尾巴”——只要还有 10% 的请求要掉下去付 100ns，那个 100ns 就会以 10% 的权重死死压在你的平均值上。命中率越接近 100%，每一小步的价值越大。

反过来看也成立：**命中率从 99% 掉到 95%，你的平均延迟可能翻倍。**这就是为什么一次”缓存预热没做完就切流量”能直接把服务打挂——不是慢一点，是慢几倍。

用一张曲线理解”为什么是多层，不是两层”

把”缓存容量”画在横轴、“命中率”画在纵轴，你会得到一条边际递减的曲线：

从 0 加到 64KB，命中率飙升（工作集的主体进来了）；
从 64KB 加到 1MB，涨势放缓；
从 1MB 加到 64MB，可能只多捞到几个百分点；
再往后，曲线几乎是平的。

**每一层都停在”再加容量不划算”的那个拐点上。**L1 小因为再大边际收益就掉；内存大因为它便宜且拐点靠后；磁盘巨大因为它最便宜。层次结构就是这条边际收益曲线被切成几段的结果。

这个视角极其好用：下次有人问”Redis 要不要再加 64G”，正确的回答是”看命中率曲线的斜率”，而不是”内存反正便宜”。

冷热分离：分层在”时间维度”上的投影

前面讲的是”访问速度”的分层。还有一层，是数据的年龄。

热数据（最近几天）：SSD，多副本，可能被缓存。每 GB 贵，但访问频繁，摊薄了。
温数据（几个月）：普通磁盘/标准型对象存储。
冷数据（合规要求存几年）：归档存储，价格低一个量级，但取回要等（分钟到小时级），甚至有最低存储期限。

这就是冷热分离 / 数据生命周期管理。

它和缓存是同一个思想的两面：

缓存：把热的往上提（主动搬运）。
冷热分离：把冷的往下沉（主动沉降）。

方向相反，机制相同——按访问频率，把数据放到成本匹配的那层去。

分层的代价：一致性

我不会把这节写成一个纯赞歌。分层有它昂贵的账单：

多级失效：L1/L2/L3 的硬件一致性协议（MESI 及其变体）已经足够复杂；软件层的”进程缓存 + Redis + DB”三级，失效顺序、时序窗口、脏数据传播，是无数线上事故的源头。
缓存穿透 / 击穿 / 雪崩：每一层都是一个可能”突然变空”的池子。
观测困难：你说不清一个慢请求到底卡在哪一层。
运维心智负担：你要同时理解 N 层的容量、命中率、失效策略、降级行为。

所以请记住这句平衡的话：

分层把”存还是算”的二选一，变成了”存在哪一层”的多选一；代价是，你换来了一个”什么时候失效”的 N 选难题。

工程上没有免费的午餐，只有换了个地方付账。

子主题十：三个业界对照——同一原理的三种截然不同的长相

我们来拆三个真实系统，看同一个原理怎么长出三副完全不同的面孔。

对照一：数据库索引（空间换时间）

不建索引：查 WHERE user_id = 42，全表扫描，O(N) 次 IO。建 B+ 树索引：树高很矮（百万行通常也就三四层），几次 IO 定位，然后再一次 IO 取行。

你付的账单有四项，很多人只想到了第一项：

索引本身的存储：可能达到数据量的相当比例，多建几个索引，索引比数据还大是常事。
写放大：每插一行，要更新所有相关索引。一个表建了 8 个索引，一次 INSERT 就是 9 次写入。你省的读时间，是从写路径上预支的。
随机 IO：索引维护（尤其 B+ 树的分裂合并）会产生随机写，而随机写比顺序写慢得多。
优化器的复杂度：索引越多，优化器选错执行计划的可能越大。

那为什么还建？因为绝大多数业务是读多写少，而且”使用次数”判据在这里极端有利——一张表被查几百万次，只被写几十万次。

进阶一层：覆盖索引。

如果索引里已经包含了查询需要的全部列，数据库就不必”回表”再去聚簇索引里取整行。**再多用一点空间，换掉一次随机 IO。**这是”空间换时间”内部再叠一层”空间换时间”的漂亮例子。

**反问：索引越多越好吗？**现在你应该能自己答了：索引是把读的成本转账给写。写密集的表（日志表、流水表、消息队列持久化）上堆索引，是把系统往死里坑。判断依据永远是读写比和数据分布，不是”反正加了没坏处”。

对照二：虚拟机内存气球与按需分页（时间换空间）

虚拟化场景：宿主机上运行着 20 台虚拟机，每台都声称自己有 8GB。总需求 160GB，物理内存只有 64GB。

这靠两个机制撑着。

机制一：按需分页（demand paging）+ overcommit。

客户机刚启动时，宿主机并不真的分配 8GB 物理页。客户机访问哪页，才分配哪页（缺页中断 → 分配 → 建立映射）。

**这就是”惰性求值”在系统层面的形态：不到最后一刻不干活。**它的赌注是——大部分申请了的内存，永远不会被真正写。而它赌赢了，这就是为什么云计算能靠超卖赚钱。

机制二：内存气球（balloon driver）。

现在宿主机内存真的紧张了，需要回收。怎么办？

笨办法：宿主机直接把客户机的某些页换出到自己的 swap。问题是宿主机不知道客户机里哪些页是冷的——它只看到一堆物理页，分不清哪个是文件缓存（扔了没事）、哪个是关键进程的堆（扔了要命）。

聪明的办法：在客户机里装一个”气球”驱动。

宿主机需要内存 → 通知气球驱动”膨胀”。
气球驱动在客户机内部申请一批内存页（比如 1GB），并把它锁住。
客户机内核发现自己内存不够了 → 由客户机自己的内存管理逻辑决定换出哪些页、回收哪些缓存。
气球驱动把拿到的这 1GB 物理页交给宿主机，宿主机回收给别的客户机。

绝妙在哪？宿主机没有替客户机做”扔掉什么”的决策，它只提了一个数量要求（“我要 1GB”），然后把决策权下放给了最懂这份数据的人——客户机自己。

狠类比：气球就像房东来收房。

房东不关心你扔哪件家具，他只说”腾出 20 平米”。而你比房东清楚得多：过季的衣服可以进储物间，结婚照不行。如果房东直接冲进来扔，他很可能会把你的结婚照当废纸卖了。

**这就是一个普适的设计原则：回收资源时，只下指标，不下指令；把淘汰策略留给拥有局部知识的一方。**你在写 LRU 缓存、连接池、线程池的时候，同样适用。

反面：抖动（thrashing）。

如果气球吹得太大、或者 overcommit 太激进，客户机会陷入”刚换出的页马上又要用、换进来又把另一页挤出去”的死循环。此时 CPU 看起来很忙，IO 打满，但有效工作几乎为零。

**这就是”时间换空间换过头了”的样子：你省下的每一 MB 内存，都在用远超过它价值的 IO 时间来偿还。**判据再次生效——当”重算（换入）成本 × 频率”超过”存储成本”时，这个方向就是亏的。

对照三：JIT 编译（把运行时的时间转移到编译时，而这个”编译时”仍在运行时里）

JIT（即时编译）最有意思，因为它把”转移”这件事玩出了层次。

先看它解决的问题：

纯解释执行：启动快，但每次执行都要解析字节码，慢。
纯静态编译（AOT）：运行飞快，但编译耗时长，且缺少运行时信息——它不知道哪个分支真的热、哪个虚方法的实际类型是什么。

JIT 的做法：先跑起来，边跑边看，看准了再编译。

典型的分层编译（tiered compilation）长这样：

第 0 层：解释器（立刻开始执行，同时收集 profile）
   ↓  某个方法调用次数/循环回边次数超过阈值
第 1 层：C1 快速编译（编译快，优化少，立刻提速）
   ↓  持续收集 profile，确认真的是热点
第 2 层：C2 深度编译（编译慢，但做激进优化：内联、逃逸分析、循环优化……）

请你注意这里发生了几件极其漂亮的事：

这是”分层思想”在”计算时间”维度上的应用，不是存储维度。快而浅的层、慢而深的层，按热度往上提——和缓存层次结构同构。
**观察本身也是成本。**收集 profile（计数器、类型记录）要插桩，要占 CPU，要占内存。**你为了”知道哪里值得优化”，先付了一笔信息费。**这笔费用得值不值，取决于代码是否真的会跑很久——短命的脚本进程，JIT 可能永远收不回这笔投资。
它还会”去优化”（deoptimization）。如果 C2 基于 profile 做了一个投机性假设（比如”这个虚方法只有一个实现类，内联它”），后来假设被打破了，运行时必须能安全地把优化后的代码退回解释器。所以 JIT 不只是”加优化”，它还得为每一处投机准备一条退路，并把”从优化态回到未优化态”所需的元数据一直存着——又是一笔空间开销，用来买那份激进优化的时间收益。
**编译本身占内存。**编译后的机器码、profile 数据、内联缓存，都要存在内存里（所谓的 code cache）。你买的那份”快”，也是用空间买的。

三个对照的共同结构，请你在心里过一遍：

案例	方向	把成本从哪	转移到哪	必须额外付的
数据库索引	空间换时间	查询（读路径）	写入（写路径）	索引存储、写放大、随机 IO
内存气球 / 按需分页	时间换空间	内存占用	缺页 / 换入换出的 IO	缺页处理、swap 空间、抖动风险
JIT 编译	时间换”更好的时间”	逐次解释执行	一次编译 + 后续复用	编译时间、code cache、profile 元数据、去优化机制

看出规律了吗？三者都不是”凭空变出性能”，而是”把成本从一处挪到另一处”，并且每一次转移都要额外付一笔”元数据 + 调度决策”的管理费。

**这笔管理费，才是判断一个优化值不值的真正变量。**很多人只算了”省了多少”，从不算”管理这份优化花了多少”。

子主题十一：实操——用 pprof 和火焰图判断”我的瓶颈是时间还是空间”

理论讲完了，落到你手上的具体问题：

服务的 P99 从 80ms 涨到了 400ms，内存也从 2GB 涨到了 6GB。你先优化哪个？

凭感觉改？那你有一半的概率会把一个小问题变成两个问题——因为时空权衡是零和的，你往一边加码，另一边一定变重。

第一步：看四个信号，先分大类

信号	指向时间瓶颈（CPU bound）	指向空间瓶颈（Memory bound）
CPU 使用率	持续接近打满（且 user 高）	不高，但 sys 高，或 GC 线程吃 CPU
内存 / RSS	平稳	持续上涨，或高位震荡不回落
磁盘 IO	低	高（可能已在 swap / 换页）
延迟形态	稳定地慢	周期性尖刺（GC 停顿、缺页）

第一条经验法则：先看内存，再看 CPU。

为什么？因为内存压力会伪装成 CPU 问题。GC 频繁、换页、分配器竞争，都会让 CPU 看起来很忙。你要是在这时候去优化 CPU，等于对着发烧量体温却去治咳嗽。

第二步：抓 profile，看三类图

以 Go 的 pprof 为例（Java 的 async-profiler、Python 的 py-spy、eBPF 工具链思路完全通用）：

1. CPU profile：/debug/pprof/profile

看什么？找”平顶”。

火焰图的横轴是占比（不是时间流逝！这点经常被误解），纵轴是调用栈深度。

宽平顶，且平顶就在栈顶：函数自己在烧 CPU，没有往下调用了。典型元凶：序列化/反序列化、正则回溯、加密哈希、JSON 编解码、字符串拼接、大量反射。
宽，但不在栈顶：这个函数和它的子调用一起烧 CPU。往下看，谁最宽谁才是真凶。
窄而高的塔：调用链极深，或递归过深。不一定是大问题，但值得看一眼。

2. 堆 profile：/debug/pprof/heap

这里有个 90% 的人会踩的坑，请你务必记住：

pprof 的 heap 有两个完全不同的视角：

--inuse_space / --inuse_objects：当前还活着的对象。→ 这是空间压力：你的常驻内存是谁占的。
--alloc_space / --alloc_objects：历史累计分配的总量（含已回收的）。→ 这是时间压力：你的分配速率有多高，GC 要干多少活。

同一个服务可能同时有两种截然不同的病：

inuse 高、alloc 低 → 你真的持有着一大坨数据。可能是缓存开太大、可能是一次性把大结果集读进了内存、也可能是泄漏。方向：压/分片/流式/改淘汰策略。
inuse 低、alloc 极高 → 你在疯狂地制造短命垃圾。内存看着不高，但 GC 累得半死。方向：复用对象（sync.Pool）、减少逃逸、避免热路径上的隐式装箱/字符串转换、调大 GOGC 或换成更低停顿的 GC。

同一个”内存涨”，两种病，药完全相反。不区分这两个视角就动手，下药必错。

3. 阻塞 / 锁 / 协程 profile

goroutine：有没有协程泄漏（数量随时间线性增长）。
block：卡在 channel、锁、系统调用上。
mutex：锁竞争。

**这些属于”时间瓶颈”的变种——不是算得太慢，是等得太久。**方向完全不同（降低锁粒度、无锁化、批量化）。

第三步：对照决策表，决定往哪边换

你观察到的	诊断	该往哪边换	具体手段
CPU 打满，火焰图有宽平顶，内存平稳	纯时间瓶颈	空间换时间	记忆化、加缓存、建索引、预计算、查表法
CPU 不高，延迟高，IO 打满	IO 瓶颈（可能是空间不足的后果）	先用空间换时间	加大缓存命中、批量读写、合并小 IO；注意这时候开压缩可能反而变快
GC 占比高，`alloc_space` 极高	分配速率过高（时间瓶颈的伪装）	空间换时间	对象池、复用缓冲区、减少逃逸、避免热路径临时对象
RSS 高，`inuse_space` 高，`alloc` 不高	常驻数据量过大	时间换空间	压缩、分片、流式处理、更紧的数据结构、缩缓存或改淘汰策略
RSS 高 + 磁盘 IO 高 + 延迟尖刺	已经在用时间换空间，而且换亏了（抖动）	反向：空间换时间	加内存、缩工作集、降低并发度、分片
内存和 CPU 都涨，且增长相关	大概率是内存问题引发的 CPU 问题	先治内存	按上面两行分别处理，别碰 CPU

**最后一行请重点记：**当内存和 CPU 同时出问题，默认先治内存。因为内存问题是因、CPU 问题是果的概率，远大于反过来。

第四步：动手前最后三问

问 1：我有没有量化过”换”的收益？

别凭感觉。按子主题四那个判据算：重算成本 × 使用次数 vs 存储成本。缓存加上去之前，先看看命中率能到多少——命中率低于某个水平，缓存就是负收益（白占内存、增加维护成本、可能挤走热数据）。

问 2：我有没有一次只改一个变量？

最忌讳的是”同时加缓存 + 开压缩 + 调 GC 参数”。三个改动互相干扰，做完你根本不知道是哪一个起了作用，还是三个互相抵消后勉强持平。

**改一个，测一次，留一份前后对比的 profile。**这不只是方法论洁癖——在时空权衡里，这是唯一能让你学到东西的方式。

问 3：成本被我挪到哪一层去了？

这是本章的收尾之问，也是最高级的一问。

你加了缓存 → 成本挪到了”失效与一致性”上，挪到了运维复杂度上。你开了压缩 → 成本挪到了 CPU 上。你做了预计算 → 成本挪到了写路径和”数据新鲜度”上。你用了 JIT → 成本挪到了编译时间和 code cache 上。

优化从来不是让成本消失，而是给成本搬家。高手的差别不在于会多少优化技巧，而在于每次动手前，都能准确说出”这笔成本我打算搬到哪里去，那边扛不扛得住”。

想清楚这个，你才算真正懂了时空权衡。

演进脉络

早期（内存极贵时代）：一切以省空间为第一优先。程序用各种技巧压缩内存占用（位域、覆写内存、覆盖加载 overlay）。
中期（内存变便宜）：开始大规模用空间换时间——索引、缓存、预计算成为标配。数据库、操作系统大量引入缓存层。
现代（内存很大但数据更大）：权衡没有消失，而是转移到了新的层次——分布式缓存、多级存储、冷热分离、计算下推。问题的形态变了，本质没变。

本章思考题

【思考题】

为什么说时空权衡是”所有优化的第一性原理”？请举出三个你认为形态完全不同、但本质都是时空权衡的技术。
“把权衡转移到别处”是比”平衡权衡”更高级的解法。请举一个你见过的例子，说明它是怎么转移的、转移到了哪里。
什么时候”用空间换时间”会适得其反？请举一个具体场景。
如果内存无限大，时空权衡会消失吗？为什么？
“给递归函数加个哈希表”和”给一个远程接口加缓存”，看起来是同一招。它们的共同结构是什么？本质区别又在哪？
什么情况下你不该做预计算或建物化视图？请至少说出两类反例。
压缩明明是”时间换空间”，为什么在不少真实系统里它能让读写同时变快？请说出成立条件和失效条件。
列式存储的压缩率通常显著高于行存。请说出至少两条原因，并指出其中哪一条其实不属于”压缩”本身。
100GB 文件、8GB 内存的机器，请完整描述外部排序的过程，并说明”内存变大”会从哪两个地方让这个算法变快。
哪些运算可以流式做，哪些不行？请给出判据，并说明遇到”必须看到全量”的运算时有哪些出路。
近似算法（HyperLogLog、Bloom Filter）算不算时空权衡？请把它放进一个更大的框架里回答。
为什么说”分层”是时空权衡最优雅的工程解法？请说出至少三条理由，并说出它的代价。
内存气球（balloon driver）的设计巧在哪里？它和”宿主机直接把客户机的页换出到 swap”有什么本质差别？
你的服务 P99 从 80ms 涨到 400ms，内存从 2GB 涨到 6GB。请给出你用 pprof 定位并决策的完整思路：看哪些 profile、怎么区分”常驻内存过大”和”分配速率过高”、最后分别该往哪个方向换。

【参考答案】

因为几乎所有优化手段，本质都是”在’存’和’算’之间重新分配成本”。例子：数据库索引用额外存储换查询速度（空间换时间）；数据压缩用 CPU 解压时间换存储容量（时间换空间）；记忆化用数组空间换递归重算时间（空间换时间）。三者形态完全不同，但结构一致——都存在一个”中间结果”，你在”存着”和”重算”之间做选择。
典型例子：编译器优化把计算从”运行时”转移到”编译时”——模板展开、常量折叠、内联。再比如把计算从”在线”转移到”离线”（预计算报表）、从”服务端”转移到”客户端”（前端渲染）。它们没有消灭计算量，只是把计算挪到了成本更低、或者发生次数更少的地方。
当”缓存的数据访问频率很低、但占用空间很大”时会适得其反：缓存项一直不命中，白占内存，还增加了管理开销（维护缓存结构、淘汰策略、可能造成 GC 压力）。更糟的情况是缓存把热数据挤出去了（缓存污染）。所以”用空间换时间”的前提是访问频率足够高、局部性足够好，否则就是纯亏。
不会。因为时空权衡的根源不只是”内存不够”，更在于存储离计算的物理距离——即使内存无限大，离 CPU 远的内存访问依然慢（内存墙、冯诺依曼瓶颈），你依然要在”放在近处（贵、容量有限）“和”放在远处（便宜、但慢）“之间权衡。而且问题规模的增长快过硬件进步，所以这个结构性事实不会消失。
共同结构：都存在”参数 → 结果”的映射，都存在”重算”和”查表”两条路，都用空间换掉了重复计算的时间。本质区别在纯度：递归函数是纯函数，同样的输入永远同样的输出，存下来的结果永远有效；远程接口不纯，底层数据会被别人改，于是缓存多出一个记忆化完全没有的问题——失效。所以缓存必须额外付出 TTL、主动失效、一致性协议的成本。换句话说，记忆化买的只是字节，缓存买的除了字节还有”维护这些字节与真实世界一致”的债。此外，缓存还要面对命中率问题：记忆化的子问题空间是有限且必然会重复访问的，缓存的 key 空间可能近乎无限，命中率低时就是纯亏。
反例一：写密集而读稀疏的表。预计算把成本从读路径搬到写路径，如果这张表每秒写几万次、一天只查几次，预计算就是纯粹的负债——写放大拖慢写入，汇总结果还没人用。反例二：维度组合爆炸且查询模式分散。当需要支持的维度组合数远大于真正被查询的组合数时，全量预计算会让存储和维护成本失控；此时应该只预计算高频组合，其余现算。其他反例还包括：查询逻辑频繁变更（每次改口径都要重刷历史数据）、要求强实时一致性的场景（预计算必然带来延迟，T+1 的汇总回答不了”现在这一秒”的问题）、以及查询结果高度个性化（每个用户看的都不一样，预计算无从下手）。
成立条件：瓶颈在 IO 或带宽，而 CPU 有余。压缩后需要传输/读取的字节数大幅下降，如果”省下的 IO 时间”大于”新增的解压 CPU 时间”，总耗时就下降。内存里同理：现代系统的痛点常常是内存带宽和访存延迟而不是算力，数据压小后缓存能装下更多、一次访存能带回更多有效数据，访存次数减少反而更快。失效条件：①数据本身已压缩（图片、视频、已 gzip 的内容），再压几乎无收益；②CPU 已经打满，压缩是在已堵死的路面上加塞；③需要高频随机访问单条记录，而压缩是块级的，读一条要解压整块，反而放大了读放大；④压缩级别选得过高（追求极致压缩率），解压时间超过了省下的 IO 时间。
原因一：同列数据同质、熵低。一列里都是同类型同语义、值域相近的数据，重复度高；行存里一行的邻居是不同类型的字段，混合度高，压不动。原因二：同列数据适配专用编码。字典编码（几千个城市名变成字符串数组加一堆整数 id）、RLE 行程编码（有序列里连续相同值压成”值+次数”）、差值编码（时间戳存差值，数字变小）、位图，这些招数在行存里基本用不上。原因三：只读取需要的列，另外几十列根本不碰。严格说第三条不属于”压缩”，它是减少读取量——列存的三重收益是”少读 + 好压 + 向量化执行友好”叠加，把它们混为一谈会让你在调优时找错方向。
过程：①分块——每次读入一块（比如 1GB，留余量给归并缓冲和其他开销），在内存里内排；②写回——把每个有序块写成临时文件（run），得到约 100 个有序段；③多路归并——开 k 个读句柄，用小顶堆（或败者树）每次取 k 路当前最小值输出，每次比较 O(log k)，空间只需 O(k) 的输入缓冲加输出缓冲；④输出最终有序文件。内存变大从两处提速：一是每块能读得更大，初始 run 数量减少；二是归并路数 k 受内存限制（每路一份输入缓冲），内存越大 k 越大，归并趟数大致按 log_k(N/M) 下降，k 从 10 涨到 100 趟数直接砍半。本质上加内存没有让”装得下”发生质变，它买的是更少的 IO 趟数——内存买时间，又一次应验。
判据两条：①运算是否可结合（(a+b)+c == a+(b+c)）——可结合意味着你可以只持有一个部分结果往前走，这个部分结果就是常数级状态；②是否需要全局视野——排序要知道”全天下最小的那个是谁”，不看完不敢输出。能流式的：filter、map/投影、sum/count/min/max 这类可结合聚合、采样、限流。不能流式的：全局排序、精确去重（distinct）、精确中位数/分位数、基数极高的 group by、大表 join。出路有三条：①外部化——落盘，把”只能流一次的数据”变成”可重放的数据”，然后多趟处理（外部排序就是这么干的）；②分治/分片——按 key 切分，让每片的状态能装进内存；③放弃精确——用近似算法换 O(1) 或 O(k) 的空间，比如 HyperLogLog 估 UV、Count-Min Sketch 估频次、t-digest 估分位数、蓄水池抽样。
算，但它是时空权衡的推广。更准确的框架是一个资源三角：时间、空间、精度，三者你最多按下去两个。Bloom Filter 用一点点假阳性（精度）换巨大的空间节省；流式草图用精度换空间和时间；精确排序三个都不肯放手，于是只能吃多趟 IO 的苦。所以当你发现”存也存不下、算也算不完”时，正确的反应不是更努力地优化，而是问一句：**能不能不要那么准？**这是工程上被严重低估的一招，也是”把权衡转移到成本更低的维度”的典型——你没在时间和空间上妥协，你把矛盾挪到了精度这个通常更便宜的维度上。
理由：①把全局二选一拆成局部多选一——从”放内存还是放磁盘”变成”放哪一层”，选择从布尔值变成光谱，而且可以随时迁移；②自动利用局部性——时间局部性和空间局部性（后者直接解释了缓存行、磁盘预读、数据库按页读取、顺序写与批量拉取），并且层次结构正好是”缓存容量 vs 命中率”这条边际递减曲线被切成几段的结果；③每层可独立演进——换 SSD 不用改应用，加 Redis 不用改存储引擎，分层给系统装了可替换的关节。代价：一致性。多级缓存意味着多级失效难题，脏数据传播、失效顺序、时序窗口是无数线上事故的源头；此外还有缓存穿透/击穿/雪崩、观测困难（说不清慢请求卡在哪一层）、以及 N 层容量与降级策略的运维心智负担。一句话总结：分层把”存还是算”的二选一变成了”存在哪一层”的多选一，代价是换来了一个”什么时候失效”的 N 选难题。
巧在只下指标、不下指令，把淘汰决策权交给拥有局部知识的一方。宿主机只告诉气球驱动”我要回收 1GB”，气球驱动在客户机内部申请并锁住这批页，触发客户机自己的内存回收逻辑——由客户机决定换出哪些页、回收哪些文件缓存。客户机比宿主机清楚得多：哪些是文件缓存（扔了没事）、哪些是关键进程的堆（扔了要命）。如果宿主机直接把客户机的页换出到自己的 swap，它看到的只是一堆物理页，分不清冷热，很可能把最热的数据换出去，导致抖动。类比：房东只说”腾出 20 平米”，而不亲自去扔你的家具，因为你比他清楚该扔什么。这个原则普适——写 LRU 缓存、连接池、线程池时都一样：回收资源时提数量要求，把淘汰策略留给最懂数据的一方。
思路分四步。第一步先分大类：看 CPU 使用率、RSS 走势、磁盘 IO、延迟形态四个信号。原则是先看内存再看 CPU，因为内存压力会伪装成 CPU 问题（GC 频繁、换页、分配器竞争都会让 CPU 看起来很忙）。第二步抓三类 profile：①CPU profile 看火焰图，找”宽平顶”——宽且在栈顶说明函数自己烧 CPU（序列化、正则、加解密、反射），宽但不在栈顶就往下找最宽的子调用，窄而高的塔看是否递归过深；②堆 profile 必须区分两个视角——inuse_space/inuse_objects 是当前活着的对象，代表空间压力，alloc_space/alloc_objects 是历史累计分配，代表时间压力（分配速率、GC 工作量）；③goroutine/block/mutex 看协程泄漏和锁竞争（这类是”等太久”而非”算太慢”）。第三步对照诊断：inuse 高而 alloc 低＝真持有着一大坨数据（缓存过大、大结果集、泄漏），走时间换空间（压缩、分片、流式、更紧的数据结构、缩缓存改淘汰）；inuse 低而 alloc 极高＝疯狂制造短命垃圾，走空间换时间（对象池、复用缓冲区、减少逃逸、避免热路径临时对象）；RSS 高且磁盘 IO 高且有延迟尖刺＝已经在用时间换空间而且换亏了（抖动），要反向加内存/缩工作集/分片。总原则：内存和 CPU 同时出问题时，默认先治内存，因为”内存是因、CPU 是果”的概率远大于反过来。第四步动手前三问：量化过收益没有（按”重算成本×使用次数 vs 存储成本”算，命中率过低就是负收益）？一次只改一个变量没有（同时加缓存+开压缩+调 GC 参数，做完你不知道谁起了作用）？成本被我挪到哪一层去了（加缓存挪到失效与运维、开压缩挪到 CPU、预计算挪到写路径与新鲜度、JIT 挪到编译时间与 code cache）——优化从来不是让成本消失，而是给成本搬家。

徐术挺-漫思录

探索

01-时间与空间的权衡