03. 成本模型

0. 本章先解决什么问题

程序“能跑”只是最低要求。CSER 还要问:

数据量变大后还能跑吗?
一次操作要等多久?
单位时间能处理多少?
会占多少内存?
瓶颈在哪里?
优化哪个地方才真的有用?

这就是成本模型。

没有成本模型,就容易出现两种问题:

看见代码能运行,就误以为系统能承受真实规模。
盲目优化局部代码,却没有优化真正瓶颈。

先用一张图把成本拆开:复杂度只是入口,真正的瓶颈可能在等待、搬运、锁或队列。

成本模型与瓶颈

这张图怎么读

图里的核心不是“成本很多”,而是:

总耗时 = 真正干活的时间 + 等待资源的时间 + 搬运/切换/协调的时间

很多性能问题看上去都是“慢”,但慢的性质完全不同:

慢的类型	典型信号	优化方向
算得慢	CPU 忙,调用栈集中	降复杂度、减少重复计算、并行计算
等得慢	CPU 不忙,线程阻塞	减少 IO、缩短队列、异步化、增加资源
搬得慢	大量复制、序列化、反序列化	减少中间格式、复用 buffer、批量处理
抢得慢	锁等待、CAS 重试、上下文切换	降低共享状态、分片、无锁/细粒度锁
抖得慢	平均可接受,偶发特别慢	查 GC、扩容、冷启动、缓存失效、尾延迟

所以成本模型不是一道复杂度题,而是一种问法:这个系统的时间到底花在哪种资源上?

1. 成本有哪些

常见成本不止时间复杂度。

成本	含义	常见来源
计算成本	CPU 要执行多少工作	循环、递归、排序、加密、解析
空间成本	占多少内存或存储	数组、对象、索引、缓存、日志
等待成本	花多少时间等资源	磁盘、网络、锁、队列、定时器
复制成本	数据搬运多少次	buffer、序列化、用户态/内核态
切换成本	从一种上下文切到另一种	线程切换、系统调用、进程切换
维护成本	为保持结构合法额外做什么	树旋转、堆调整、重哈希
复杂性成本	人理解和维护有多难	状态太多、接口不清、异常路径多

真实系统里,慢常常不是因为“算法太差”这一种原因,而是多种成本叠加。

1.1 成本要带单位

成本模型如果没有单位,很容易变成口号。分析时至少要区分这些量:

指标	单位	说明
操作次数	次	循环、比较、哈希、函数调用
数据量	byte / KB / MB / GB	复制、传输、存储、序列化
延迟	ns / us / ms / s	单次操作等待多久
吞吐	ops/s、req/s、MB/s	单位时间完成多少
并发量	个	同时在系统里的任务数
队列长度	个	等待处理的任务积压
命中率	%	cache、索引、分支预测、连接复用是否有效
尾延迟	p95 / p99 / p999	最慢那部分请求的体验

比如“复制一个数组”必须问数组多大:

复制 100 个 int:通常不值得纠结
复制 1000 万个对象引用:可能造成明显 CPU/cache/GC 压力
复制 1GB buffer:已经是系统级成本

再比如“网络请求一次”必须问延迟尺度:

内存访问:纳秒级到百纳秒级
本机系统调用:微秒级附近
本机磁盘/网络/进程间通信:微秒到毫秒
跨地域网络:毫秒到百毫秒
人工操作:秒级以上

你不需要死背数字,但必须形成数量级直觉。数量级错了,架构判断就会错。

手推:一次远程等待可以抵掉多少本地操作

成本模型要有数量级直觉。假设一次本地简单内存级操作是纳秒到百纳秒量级,而一次跨网络等待是毫秒量级。

只做粗略数量级比较:

1 ms = 1,000,000 ns

如果一个本地操作约 100 ns,那么 1 ms 大约能做:

1,000,000 / 100 = 10,000

次本地操作。

这不是精确性能公式,而是提醒你:

误判	为什么错
为了少一次本地循环,增加一次远程请求	远程等待可能贵几个数量级
在 IO-bound 路径里微优化几行 CPU 代码	真正时间花在等待
把大量小请求拆得很碎	每次边界成本都要重复付
忽略批量和缓存	重复远程/磁盘等待会压倒本地计算

数量级判断能帮你先排除很多假优化:如果瓶颈是毫秒级等待,就别先纠结纳秒级表达式。

2. 时间复杂度是第一层

时间复杂度看的是增长趋势。

复杂度	直觉	例子
O(1)	数据量变大,步骤数基本不变	数组按下标访问
O(log n)	每次缩小一大块范围	二分查找、平衡树查找
O(n)	每个元素看一遍	遍历数组
O(n log n)	多层处理,每层处理 n 个	常见高效排序
O(n^2)	两两比较或双层全量组合	暴力配对
O(2^n)	每个选择都分裂	暴力枚举子集

比如 n 从 1000 变成 1,000,000:

复杂度	增长直觉
O(n)	大约增长 1000 倍
O(n^2)	大约增长 1,000,000 倍
O(log n)	只增加很少几步

所以复杂度不是考试符号,它是在预测规模变大后的命运。

2.1 复杂度要结合输入规模

复杂度不是越低越好,而是要看规模和常数。

场景	判断
n 永远小于 20	简单 O(n^2) 可能比复杂 O(n log n) 更好维护
n 可能到百万	O(n^2) 基本要警惕
n 可能到亿级	O(n) 也要考虑内存带宽、IO、分批
n 无界增长	要设计分页、索引、流式处理、背压

例如对 10 个元素排序,纠结快排、归并、堆排意义不大;对 10 亿条日志做查询,不建索引、不分区、不流式处理,O(n) 也可能无法接受。

复杂度回答的是:

当 n 变大时,趋势会不会杀死系统?

常数和硬件回答的是:

在当前规模下,真实耗时是否可接受?

两者都要看。

3. 但复杂度不是全部

两个 O(n) 程序,真实速度可能差很多。

原因包括:

因素	解释
常数成本	每一步内部做的工作不同
内存局部性	连续访问比随机跳转更容易命中 cache
分支预测	分支规律越清晰,CPU 越容易预测
数据复制	每轮是否复制大块数据
系统调用	是否频繁进入内核
IO 等待	是否需要等磁盘或网络
并发竞争	是否大量等待锁或共享资源

比如数组和链表都可以 O(n) 遍历,但数组通常更快,因为连续内存带来更好的空间局部性。

数组:
[a0][a1][a2][a3][a4]
连续,cache 友好

链表:
[node] -> [node] -> [node]
分散,容易 cache miss

3.1 CPU 不是按源码一行一行“均匀执行”

现代 CPU 的性能来自流水线、缓存、分支预测、乱序执行、SIMD 等机制。源码里看起来都是一步,底层成本可能完全不同。

写法/访问模式	底层差异
顺序遍历数组	cache line 连续加载,预取友好
随机访问链表	指针跳转,容易 cache miss
规律分支	分支预测容易命中
随机分支	分支预测失败,流水线冲刷
小对象很多	分配、指针、GC、cache 压力都增加
大块连续数据	更适合批处理和向量化

所以数据结构选择不是只看 Big-O。你要问数据在内存里怎么放、访问顺序是什么、CPU 能不能提前猜到下一步。

一个典型误区:

链表插入 O(1),数组插入 O(n),所以链表更快。

这只在“已经拿到要插入位置的节点指针”时成立。真实场景里你往往还要查找位置,链表查找 O(n) 且 cache 不友好;数组虽然搬移元素,但连续内存可能很快。结论必须结合访问模式。

4. 延迟和吞吐

延迟是一次任务完成要多久。

吞吐是单位时间完成多少任务。

延迟:一个人从排队到办完业务要 5 分钟
吞吐:一个窗口每小时能办 30 个人

两者不同。

指标	问题
延迟 latency	单次操作多快完成?
吞吐 throughput	单位时间能完成多少操作?

提高并发可能提高吞吐,也可能让延迟变差。

原因:

队列变长。
锁竞争增加。
上下文切换变多。
cache 被不同任务互相冲刷。
IO 资源被打满。

所以系统不是“并发越高越好”,而是要看资源和瓶颈。

4.1 平均延迟会骗人,尾延迟决定体验

只看平均值很危险。

99 个请求 10ms 完成
1 个请求 5s 完成
平均值约 59.9ms

平均值看起来还行,但那个 5s 的请求对用户就是灾难。真实系统常看:

指标	含义
p50	一半请求低于这个延迟,中位数体验
p95	95% 请求低于这个延迟,较慢用户体验
p99	99% 请求低于这个延迟,尾部问题
max	极端情况,可能受偶发事件影响

尾延迟常见来源:

来源	例子
队列积压	突发流量超过处理能力
GC / stop-the-world	程序暂停一段时间
扩容 / rehash	某一次操作触发大规模复制
cache miss	冷数据、缓存失效、穿透
锁竞争	少数请求等很久
外部依赖抖动	DNS、数据库、远程服务偶发慢

这就是为什么“摊还 O(1)”的操作仍可能制造 p99 抖动。平均便宜,不代表每次都便宜。

5. 排队成本

资源有限,请求就会排队。

到达速度 > 处理速度
-> 队列变长
-> 等待时间增加
-> 延迟升高

队列可以吸收短期突发,但不能解决长期处理能力不足。

例子:

每秒到达 100 个任务
系统每秒只能处理 80 个任务

那么每秒都会多积压 20 个任务。队列再大,也只是晚一点爆。

这条规律在很多地方出现:

CPU 任务队列。
磁盘 IO 队列。
网络发送缓冲区。
消息队列。
请求队列。
打印任务队列。

5.1 队列不是缓冲借口,而是放大器

队列有两个作用:

吸收短期突发
暴露长期瓶颈

如果平均到达速度长期大于处理速度,队列只会把失败延后,并把延迟放大。

更可怕的是重试风暴:

服务处理变慢
-> 客户端超时
-> 客户端重试
-> 请求量变大
-> 队列更长
-> 更多超时

这时“加大队列长度”不一定是好事。它可能让系统更晚失败,但每个请求等得更久,占用更多内存,导致恢复更慢。

排队设计要同时考虑:

问题	设计手段
队列满了怎么办	拒绝、降级、丢弃低优先级、背压
谁能排队	限流、配额、优先级
等多久算失败	timeout、deadline
能否取消	请求取消后是否从队列移除
重试怎么做	指数退避、幂等键、最大重试次数

这就是成本模型和可靠性会交叉的地方。

6. 瓶颈

瓶颈是限制系统整体速度的最慢环节。

CPU 很快
内存一般
磁盘很慢
网络不稳定

如果瓶颈是磁盘 IO,优化 CPU 算法可能没效果。

如果瓶颈是锁竞争,增加线程可能更慢。

如果瓶颈是网络 RTT,减少本地循环次数可能不明显。

优化前先问:

现在到底是谁在忙?
CPU 在忙,还是在等?
内存在涨,还是磁盘在等?
网络在重传,还是应用在排队?

6.1 找瓶颈要看“忙”和“等”

性能排查第一步不是改代码,而是判断系统在忙什么、等什么。

资源状态	含义	可能方向
CPU 高、运行队列长	算不过来	降计算量、优化算法、扩容 CPU
CPU 低、延迟高	大量等待	查 IO、锁、网络、队列、外部服务
内存高、频繁 GC/换页	对象或数据太多	降对象数、流式处理、改善生命周期
磁盘队列长	IO 打满	批量、缓存、顺序写、索引优化
网络重传高	链路/拥塞问题	查丢包、窗口、超时、带宽
锁等待高	共享状态竞争	分片、缩小临界区、减少共享
连接池耗尽	并发外部请求太多	限流、池大小、超时、隔离

“CPU 低但系统慢”是很重要的信号:代码可能不是在计算,而是在等。继续微优化循环没有意义。

6.2 局部优化可能让整体更差

瓶颈决定收益。看一个流水线:

解析 1ms -> 业务计算 2ms -> 数据库 80ms -> 序列化 2ms

你把业务计算从 2ms 优化到 1ms,总耗时从 85ms 变 84ms,收益很小。

如果你把数据库查询从 80ms 降到 20ms,总耗时从 85ms 变 25ms,收益巨大。

这叫整体视角。优化要问:

这个环节占总耗时多少?
它是不是当前瓶颈?
优化它会不会把瓶颈转移到别处?

7. 空间成本和时间成本可以互换

很多设计是在用空间换时间。

设计	用什么换什么
哈希表	用额外桶空间换快速查找
缓存	用内存换重复计算或重复 IO
索引	用额外存储和维护成本换查询速度
预计算	用存储结果换运行时计算
动态规划	用表保存子问题结果,减少重复递归

反过来也可以用时间换空间:

不缓存,每次重新计算。
流式处理,少保存中间结果。
压缩存储,读取时再解压。

没有绝对正确,只有约束下的取舍。

7.1 空间换时间也有维护成本

缓存、索引、预计算看起来很美,但它们都引入了“多份状态”。

方案	加速什么	新问题
缓存	重复读取	失效策略、一致性、脏数据
索引	查询	写入变慢、空间增加、索引维护
预计算	运行时计算	数据更新后如何刷新
冗余字段	避免 join 或聚合	多处更新必须同步
压缩	节省空间和 IO	CPU 解压成本、随机访问变差

所以“加缓存”不是免费优化。它把一次读取成本换成了状态一致性问题。

一个成熟判断是:

如果读多写少、数据可短暂过期,缓存可能值得。
如果写多读少、强一致要求高,缓存可能制造更多问题。

8. 局部性:性能的底层规律

局部性是很多系统优化的根。

局部性	含义	例子
时间局部性	最近用过的数据,之后可能还会用	循环变量、热点 key
空间局部性	用了某个地址,附近地址也可能会用	顺序遍历数组

CPU cache、OS 页缓存、应用缓存都依赖局部性。

如果访问模式完全随机,缓存效果就会变差。

所以分析性能时要问:

数据访问是连续的,还是跳来跳去?
同一份数据会反复用,还是只用一次?

8.1 局部性贯穿四大件

局部性不是组成原理里孤立的一节,它贯穿整个系统:

层	局部性如何体现
CPU cache	连续数组、热点变量更快
虚拟内存	最近访问的页更可能留在内存
文件系统	顺序读写比随机读写更友好
数据库索引	B+ 树节点按页组织,减少随机 IO
Web 缓存	热门资源重复访问,命中率高
CDN	地理位置近、热点内容缓存
算法	动态规划复用子问题结果

你会发现,“缓存”不是一个单独技术,而是局部性在不同层的实现。

反过来,如果你的访问模式破坏局部性,很多缓存都会失效:

随机 key 扫描
每次请求都查不同冷数据
对象分散在堆上到处跳
批处理被拆成大量小请求

这时加更多 cache 不一定有用,因为命中率本来就低。

9. 摊还成本

有些操作单次可能很贵,但平均下来很便宜。

动态数组尾部追加就是典型例子:

容量够:直接放入,O(1)
容量不够:扩容 + 复制旧元素,O(n)

如果连续追加很多次,扩容成本被摊到每次追加上,平均接近 O(1)。

这叫摊还分析。

但注意:摊还 O(1) 不代表每次都快。扩容发生的那一次仍然可能造成明显延迟。

9.1 摊还分析要关心峰值

摊还成本回答“长期平均”,峰值成本回答“这一次会不会卡住”。

动态数组扩容:

append 平时:写一个元素
append 扩容时:分配新数组 + 复制所有旧元素 + 写新元素

如果这是后台批处理,偶发扩容可能无所谓;如果这是实时请求路径,某一次扩容就可能造成尾延迟。

工程上常见处理:

问题	手段
已知大概大小	预分配容量
扩容造成暂停	分段数组、链式块、渐进式迁移
rehash 太重	提前扩容、增量 rehash
队列峰值太大	限流、背压、批处理
GC 峰值	减少临时对象、对象池、流式处理

所以复杂度学习不能停在“均摊 O(1)”。你还要问:最坏那一次发生在什么路径上,用户能不能接受?

10. 联系实际:如何判断该不该优化

优化前按这个顺序问:

现象是否明确?慢在哪里、数据多大、延迟多少?
瓶颈是哪种资源?CPU、内存、磁盘、网络、锁、队列?
当前算法复杂度是否会随规模爆炸?
数据访问模式是否 cache 友好?
是否有大量复制、序列化、系统调用?
是否能用空间换时间?
优化会不会增加复杂性和 bug 风险?

不要为了“看起来高级”优化。优化应该有证据、有瓶颈、有收益。

练习卡:优化前先写成本假设

每次想优化前,先填一张小表:

假设	证据	如果成立该怎么改	如果不成立怎么办
时间花在计算	CPU 忙、调用栈集中	减少计算、复用结果	转查 IO/锁/队列
时间花在等待	CPU 不忙、等待时间高	降低阻塞、并发化、缩短队列	转查数据规模
内存成为瓶颈	占用增长、换页、缓存 miss	降低对象数、改善局部性	转查算法路径
峰值导致抖动	平均正常、尾延迟高	摊平扩容/批处理/排队	转查外部依赖

练习要求:任何优化建议都必须绑定一个可验证假设。没有证据的优化只是改代码;有成本模型的优化才是工程判断。

问题:为什么接口平均 80ms,但偶尔 3 秒?

学完本章,可以分析一个真实得多的问题:

某接口平均延迟 80ms,看起来正常。
但线上偶尔有用户等待 3 秒。

不要直接说“服务器卡了”。按成本模型拆:

假设	证据	可能修复
队列积压	请求进入服务后等待时间长,线程池队列增长	限流、隔离慢任务、增加 worker、缩短处理时间
数据库慢查询	p99 SQL 时间高,慢查询日志命中	加索引、改查询、分页、预计算
GC 暂停	延迟尖峰和 GC 日志时间吻合	降对象分配、调堆、减少大对象
缓存失效	慢请求集中在 cache miss	预热、保护热点 key、避免击穿
外部服务抖动	下游调用 p99 高	timeout、熔断、降级、隔离连接池
扩容/rehash	延迟尖峰出现在集合变大时	预分配、分片、渐进迁移
锁竞争	线程 dump 显示等待同一把锁	缩小临界区、分片锁、减少共享

最终你要得到的不是“优化了代码”,而是一条证据链:

现象:p99 = 3s
证据:3s 请求里 2.7s 在等待数据库连接
根因:连接池被慢查询占满
修复:慢查询加索引 + 连接池隔离 + 请求超时
验证:p99 降到 200ms,连接池等待接近 0

这才是合格的成本模型思维。

11. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

为什么 O(n) 和 O(n) 的程序真实速度仍然可能差很多?
为什么数组遍历通常比链表遍历快?
为什么队列变长会导致延迟越来越高?
为什么增加并发不一定提高性能,甚至可能更慢?
为什么缓存、索引、动态规划都是“用空间换时间”?
为什么摊还 O(1) 不代表每一次操作都快?
遇到性能问题时,如何先找瓶颈,而不是盲目改代码。

如果你以后看到一个系统慢,能先拆成计算、内存、复制、切换、IO、排队、竞争这些成本,而不是只说“代码不够好”,你就已经具备了真正的 CS 成本意识。

cost - model