information - state - transition
01. 信息、状态与状态转移
0. 本章先解决什么问题
初学计算机时,你会看到很多词:变量、对象、数组、文件、连接、缓存、进程、线程、协议、数据库记录。它们看起来来自不同课程,但底层都绕不开同一个问题:
系统在某一刻保存了什么信息?
下一步操作会怎样改变这些信息?
哪些条件必须始终保持正确?
这就是“信息、状态、状态转移”的核心。
如果你只把程序理解成一行行语句,就很容易停在表面;如果你把程序理解成状态变化,就能解释 bug、并发、协议、文件损坏、缓存不一致这些更真实的问题。
先把本章的根模型画出来:
这张图怎么读
这张图不要当成装饰图看。它表达的是一个很硬的分析路径:
输入/事件
-> 操作规则
-> 状态变化
-> 不变量检查
-> 输出/副作用
也就是说,当你看到一个系统行为时,先不要急着贴标签。比如“请求失败”“文件损坏”“线程卡死”“缓存脏了”,这些词只是现象。真正要追的是:
| 问题 | 追问方式 |
|---|---|
| 输入是什么 | 哪个事件触发了变化?用户请求、定时任务、网络包、线程调度、崩溃恢复? |
| 旧状态是什么 | 变化发生前,内存、文件、连接、队列、锁、缓存分别处在什么状态? |
| 操作规则是什么 | 这一步应该怎样改状态?有没有前置条件?有没有顺序要求? |
| 新状态是什么 | 执行后哪些字段、资源、指针、计数器、副本被改了? |
| 不变量是否还成立 | 有没有越界、重复、丢失、顺序错乱、状态互斥被打破? |
| 副作用在哪里 | 是否写盘、发包、释放锁、提交事务、通知其他模块? |
这套问法很朴素,但它是贯穿四大件的底层通用语言。CPU 执行指令是状态转移,数组扩容是状态转移,进程调度是状态转移,TCP 建连和挥手是状态转移,数据库事务提交也是状态转移。
1. 信息是什么
计算机内部只保存和处理 bit。
bit = 0 或 1
byte = 8 个 bit
但是 bit 自己没有意义。意义来自解释规则。
01000001
它可能表示:
| 解释规则 | 含义 |
|---|---|
| 无符号整数 | 65 |
| ASCII 字符 | A |
| 机器指令的一部分 | 某个 opcode 或字段 |
| 文件格式中的字段 | 取决于格式规范 |
| 网络报文中的字段 | 取决于协议规范 |
所以计算机里大量“高级概念”,本质都是解释 bit 的规则。
| 概念 | 本质 |
|---|---|
| 数据类型 | 规定一段 bit 如何解释成数值、字符、地址 |
| 字符编码 | 规定字符和数字之间如何映射 |
| 文件格式 | 规定字节序列如何解释成图片、音频、文档 |
| 网络协议 | 规定字节序列如何解释成请求、响应、控制信息 |
| 指令集 | 规定 bit 模式如何解释成 CPU 操作 |
这也是为什么“乱码”“溢出”“协议解析错误”“文件打不开”经常不是数据不存在,而是解释规则不一致。
2. 状态是什么
状态是某一刻系统保存的信息。
你可以把状态理解成系统的“当前快照”。
| 系统 | 状态包含什么 |
|---|---|
| 一个变量 | 当前值 |
| 一个数组 | 长度、容量、每个位置的元素 |
| 一个栈 | 栈底到栈顶的元素、栈顶位置 |
| 一个文件 | 内容、大小、权限、修改时间、所在目录 |
| 一个进程 | 寄存器、虚拟内存、打开文件、线程、权限 |
| 一个 TCP 连接 | 双方地址和端口、序号、确认号、窗口、缓冲区 |
| 一个缓存 | key-value 内容、过期时间、淘汰顺序 |
学习任何结构,都先问:
它保存了哪些状态?
这些状态谁能读?
这些状态谁能改?
这些状态什么时候失效?
这比先背定义更有用。
2.1 状态有三种粒度
初学时容易把状态只理解成“变量的值”。这太窄。真实系统至少有三层状态:
| 粒度 | 看什么 | 例子 |
|---|---|---|
| 值状态 | 某个字段当前是多少 | count = 10、flag = true、balance = 100 |
| 结构状态 | 多个值之间的关系是否正确 | 数组长度和容量、树的左右关系、链表指针是否成环 |
| 资源状态 | 系统资源是否被占用、释放、等待 | 文件句柄、锁、socket、内存页、线程、事务 |
很多 bug 难查,是因为值看起来对,但结构状态或资源状态已经错了。
例如一个动态数组:
data = [A, B, C, _, _]
size = 3
capacity = 5
这里不只是 data 里的元素是状态,size <= capacity 也是状态关系。如果某次删除后只清了元素,没有更新 size,数组表面上还有空间,结构状态却已经不可信。
再看一个文件写入:
用户态 buffer 有数据
内核页缓存有数据
磁盘上可能还没有数据
目录项可能已经更新,也可能还没落盘
如果程序只盯着“write 返回成功”,就会误以为状态已经持久化。实际上它只是从用户态推进到了内核态,未必推进到了磁盘持久状态。
3. 程序是状态转移
程序执行可以看成:
旧状态 + 操作 -> 新状态
简单例子:
x = 1
x = x + 2
状态变化:
x: 1 -> 3
更底层一点:
内存/寄存器中的旧值
-> CPU 执行指令
-> 内存/寄存器中的新值
再看数组插入:
原状态:
index: 0 1 2 3
value: A B C D
在 index=1 插入 X:
index: 0 1 2 3 4
value: A X B C D
这个操作不只是“插入 X”,它实际改变了很多状态:
- 数组长度从 4 变 5。
- index=1 的旧元素 B 移到 index=2。
- C、D 也后移。
- 如果容量不够,还会分配新数组并复制旧元素。
很多复杂度和 bug 都藏在这些状态变化里。
3.1 一行代码背后可能有多层状态转移
把程序理解成状态转移,关键是不要停在源码层。源码只是最上层表达。
以“追加一段内容到文件”为例,上层看起来可能只是:
append(file, bytes)
但拆开以后至少有这些状态变化:
- 应用层:待写入数据 -> 调用写入接口
- 运行时:用户态 buffer -> 系统调用参数
- 操作系统:文件偏移、页缓存、文件元数据被更新
- 文件系统:脏页、inode、目录项、日志状态变化
- 块设备:请求进入 IO 队列
- 硬件:控制器把数据写到存储介质
这里任何一层都可能失败或延迟:
| 层 | 典型问题 |
|---|---|
| 应用层 | 重复写、漏写、编码错 |
| 运行时 | buffer 没 flush、异常路径没 close |
| OS | 系统调用被中断、权限不足、磁盘满 |
| 文件系统 | 元数据和数据落盘顺序问题 |
| 块设备 | IO 排队、写入失败、掉电 |
所以“写文件”不是一个动作,而是一串状态推进。越靠近底层,越能看见抽象隐藏的风险。
再看“发出一个网络请求”:
应用请求状态: created -> serialized
DNS 状态: unknown -> resolved
TCP 状态: closed -> syn-sent -> established
TLS 状态: handshake -> secure
HTTP 状态: headers-sent -> body-sent -> response-reading -> done
如果请求慢,你不能只说“网络慢”。慢可能卡在 DNS、TCP 握手、TLS、服务端排队、响应体读取、客户端解码。状态分层越清楚,定位越快。
4. 状态转移必须满足规则
不是所有状态变化都合法。
比如栈的规则是后进先出:
push A
push B
pop -> 必须得到 B
如果 pop 得到 A,说明状态转移破坏了栈的规则。
再比如银行账户:
balance = 100
withdraw(30)
balance = 70
如果规则要求余额不能为负,那么下面这个状态转移就是非法的:
balance = 20
withdraw(30)
balance = -10
这引出一个关键概念:不变量。
5. 不变量是什么
不变量是任何合法操作之后都必须保持成立的条件。
| 结构/系统 | 不变量 |
|---|---|
| 栈 | 只能从栈顶插入和删除 |
| 队列 | 先进入的元素先离开 |
| 二叉搜索树 | 左子树小于根,右子树大于根 |
| 堆 | 父节点优先级不低于或不高于子节点 |
| 文件系统 | 目录项必须能指向合法文件元数据 |
| TCP 连接 | 序号和确认号必须能对应字节流位置 |
| 缓存 | 过期或被淘汰的数据不能继续当作新数据使用 |
很多算法设计,本质是在维护不变量。
5.1 前置条件、后置条件、不变量
只说“不变量”还不够。分析一个操作时,最好同时写三件事:
| 名称 | 问题 | 例子:栈的 pop() |
|---|---|---|
| 前置条件 | 操作开始前必须满足什么 | 栈不能为空 |
| 后置条件 | 操作结束后必须变成什么 | 返回原来的栈顶元素,栈大小减 1 |
| 不变量 | 操作前后都必须一直成立什么 | 栈内元素顺序仍保持后进先出 |
这三个概念能把“代码感觉对不对”变成可检查的规则。
再看一个队列:
enqueue(x)
前置条件: 队列未超过容量,或允许扩容
后置条件: x 位于队尾,size 增加 1
不变量: 队头到队尾的顺序仍然代表入队顺序
如果你实现循环队列,最容易错的不是“数组下标加一”,而是这些关系:
0 <= head < capacity
0 <= tail < capacity
0 <= size <= capacity
tail = (head + size) mod capacity
这些关系才是结构的灵魂。代码只是维护它们的手段。
比如二叉搜索树插入一个节点,不能只考虑“把节点放进去”,还要保证插入后仍满足:
左边都更小,右边都更大
如果这个规则被破坏,后续查找就可能走错方向。
机制深挖:原子状态转移为什么重要
很多操作看起来是一步,实际要改多个状态。如果这些状态只改了一半,系统就会进入“半完成状态”。
例子:从队列里取一个任务执行。
- 从 pending 队列移除 task
- 把 task 标记为 running
- 记录 worker_id
- 设置开始时间和超时时间
如果第 1 步成功,第 2 步失败,任务可能既不在 pending,也不是 running。它消失了。
这类操作需要原子性思维:
| 策略 | 思路 |
|---|---|
| 单个原子提交 | 多个状态一起成功或一起失败 |
| 先写意图 | 先记录“准备执行”,崩溃后可恢复 |
| 状态机保护 | 只允许 PENDING -> RUNNING 这种合法转移 |
| 幂等重试 | 重复执行同一转移不会制造第二份副作用 |
| 补偿/恢复 | 发现半完成状态后能修正回合法状态 |
原子状态转移不只属于数据库。数组扩容、文件替换、任务调度、连接状态切换、缓存更新都需要同样的思维:要么所有相关状态一起推进,要么留下足够证据让系统恢复。
6. bug 常常是状态偏离预期
调试时不要只问“哪行代码错了”,更好的问法是:
状态从哪一步开始偏离预期?
哪个不变量被破坏了?
| 现象 | 状态视角 |
|---|---|
| 数组越界 | 下标状态超出合法范围 |
| 死锁 | 多个执行流持有和等待资源的状态形成环 |
| TCP 重传 | 某段字节迟迟没有进入“已确认”状态 |
| 缓存不一致 | 多份副本状态不同 |
| 文件损坏 | 写入过程被中断,持久化状态只完成了一部分 |
| 内存泄漏 | 某些对象长期保持“可达”状态,不能释放 |
| UI 卡住 | 事件队列、渲染状态或任务状态没有继续推进 |
如果你能找到第一次状态异常的位置,问题通常已经解决一半。
6.1 真实案例:重复扣库存不是“多扣了一次”这么简单
假设一个下单流程:
检查库存 -> 创建订单 -> 扣库存 -> 支付 -> 发货
如果用户重复点击,或者网络超时后客户端重试,系统可能收到两次“创建订单”请求。表面现象是库存被扣了两次。状态视角会把问题拆细:
| 状态对象 | 应该是什么 | 出错时可能怎样 |
|---|---|---|
| 请求 | 同一个业务请求只能生效一次 | 重试请求被当成新请求 |
| 订单 | 一个订单号只能对应一次创建 | 生成了两个订单 |
| 库存 | 扣减必须和订单创建绑定 | 订单失败但库存已扣 |
| 支付 | 支付成功只能推进一次状态 | 回调重复导致二次推进 |
| 事务 | 创建订单和扣库存要么都成功,要么都失败 | 中间失败留下半完成状态 |
这时真正要设计的不是“按钮禁用一下”,而是让状态机具备幂等性:
same request id + same operation
-> 第一次执行状态转移
-> 后续重复请求返回同一个结果,不再重复改变核心状态
这就是从“修一个前端小 bug”上升到“维护系统状态不变量”。
6.2 调试时如何找第一次错误状态
一个实用做法是写状态追踪表:
| 时间点 | 观察到的状态 | 期望状态 | 第一次偏离了吗 |
|---|---|---|---|
| 输入到达 | 参数、用户、请求 ID | 请求 ID 唯一 | 否 |
| 校验后 | 参数合法性、权限 | 非法请求被拒绝 | 否 |
| 写入前 | 旧库存、旧订单状态 | 库存足够、订单不存在 | 否 |
| 写入后 | 新库存、新订单状态 | 库存少 1、订单创建 | 是/否 |
| 异常后 | 事务是否回滚 | 无半完成状态 | 是/否 |
调试不是把所有代码看一遍,而是缩小“状态第一次偏离”的区间。这个区间越小,原因越清楚。
7. 状态太多为什么危险
状态越多,组合越多。
两个布尔状态有 $2^2 = 4$ 种组合:
00 01 10 11
十个布尔状态有 $2^{10}=1024$ 种组合。
这解释了为什么很多东西难:
| 领域 | 难点 |
|---|---|
| 并发 | 多个执行流的状态交错太多 |
| 协议 | 连接状态、超时、重传、关闭路径很多 |
| 文件系统 | 写入过程中任意一步都可能崩溃 |
| 缓存 | 原始数据和副本状态可能不同 |
| 大型程序 | 模块状态互相影响,组合爆炸 |
减少状态、约束状态变化、明确状态机,是系统设计的重要手段。
7.1 降低状态复杂度的几种手段
状态爆炸不是只能硬测。工程上常见的控制手段包括:
| 手段 | 思路 | 例子 |
|---|---|---|
| 减少可变状态 | 能不保存就不保存,能计算就计算 | 不同时保存 total 和 items,除非能保证同步 |
| 单一事实来源 | 同一事实只由一个地方负责 | 用户余额只以账本或账户表为准,不到处复制 |
| 显式状态枚举 | 不用多个布尔值拼状态 | 用 PENDING/RUNNING/SUCCESS/FAILED 代替 isRunning/isDone/isError |
| 限制合法转移 | 不是任意状态都能跳任意状态 | 订单不能从 CANCELLED 回到 PAID |
| 原子提交 | 多个状态要么一起变,要么都不变 | 事务、临时文件 + rename、CAS |
| 幂等操作 | 重复事件不重复改变核心状态 | 重试请求带 request id |
尤其要警惕多个布尔字段表达状态:
isRunning = true
isFinished = true
isCancelled = true
这三个值同时为 true 时,系统到底处于什么状态?如果你说不清,说明状态设计已经失控。用一个枚举状态通常更清楚:
CREATED -> RUNNING -> SUCCESS
-> FAILED
-> CANCELLED
8. 状态机:把状态变化画出来
状态机由三部分组成:
状态集合 + 事件/输入 + 转移规则
以一个任务为例:
created -> running -> success
-> failed
running -> cancelled
可以画成:
实际系统里,状态机无处不在:
- TCP 连接有建立、传输、关闭状态。
- 进程有运行、等待、终止状态。
- 文件写入有打开、写入、刷新、关闭状态。
- 缓存条目有新鲜、过期、淘汰状态。
- 编译器词法分析会在不同 token 状态之间转移。
状态机能让你看清楚:当前状态下,哪些事件是合法的,哪些是不合法的。
8.1 状态机不是流程图
很多人画的“状态机”其实只是流程图。两者的重点不同:
| 图 | 关注点 |
|---|---|
| 流程图 | 先做什么,再做什么 |
| 状态机 | 当前处于什么状态,哪些事件能触发合法转移 |
流程图容易把 happy path 画得很好看,但漏掉异常路径。状态机必须回答:
如果当前是 FAILED,还能不能 finish?
如果已经 CANCELLED,又收到 success 回调怎么办?
如果 RUNNING 超时,是转 FAILED 还是 RETRYING?
如果重复收到 start,忽略、报错还是重新开始?
这也是为什么协议、并发、事务、任务调度都离不开状态机。它们真正难的不是正常路径,而是重试、超时、中断、重复事件、乱序事件。
8.2 状态机设计检查表
设计一个状态机时,至少检查这些问题:
| 检查项 | 说明 |
|---|---|
| 初始状态是什么 | 系统从哪里开始 |
| 终止状态有哪些 | 哪些状态不再允许继续推进 |
| 每个事件在哪些状态合法 | 不能让任何事件在任何状态都能执行 |
| 非法事件怎么处理 | 忽略、报错、记录审计、触发恢复 |
| 是否允许重试 | 重试是否幂等,是否会重复副作用 |
| 是否允许超时 | 超时后资源如何释放 |
| 是否允许回滚 | 回滚能恢复哪些状态,不能恢复哪些副作用 |
| 状态如何持久化 | 崩溃重启后如何知道上次走到哪里 |
如果一个状态机只存在脑子里,没有写成表或代码约束,后续维护的人大概率会加入非法转移。
9. 联系实际:怎么用这个模型读代码或排查问题
以后你看到一段代码,不要只看语句,要把它翻译成状态变化。
例子:一个简化的队列消费流程:
while queue not empty:
item = queue.pop()
process(item)
你应该问:
| 问题 | 为什么要问 |
|---|---|
queue 的状态是什么? | 元素集合、头尾位置、长度 |
pop() 改了什么? | 队头元素、长度、头指针 |
process() 失败怎么办? | item 是否丢失、是否重试 |
| 多个消费者能同时 pop 吗? | 是否破坏队列状态 |
| 队列为空时怎么办? | 等待、返回、阻塞还是报错 |
这样读代码,会比“看懂每行语法”更接近系统本质。
建模卡:把一个现象写成状态转移表
选一个简单过程,例如“订单从创建到完成”或“文件从打开到关闭”。不要先写实现,先写状态表:
| 当前状态 | 事件 | 下一个状态 | 必须保持的不变量 |
|---|---|---|---|
| 初始 | 创建 | 已创建 | 必须有唯一标识 |
| 已创建 | 确认 | 已确认 | 不能重复确认 |
| 已确认 | 完成 | 已完成 | 完成后不能再修改关键字段 |
| 任意可取消状态 | 取消 | 已取消 | 取消和完成不能同时成立 |
练习重点:给每个状态写“允许事件”和“禁止事件”。很多 bug 并不复杂,只是系统接受了一个不该在当前状态发生的操作。状态表能逼你把隐含规则变成显式规则。
问题:设计一个“可重试但不重复执行”的任务
学完本章,可以尝试解决一个很真实的问题:
后台任务可能因为网络、进程崩溃、超时而失败。
调度器会重试任务。
要求:任务可以被重试,但核心副作用不能重复执行。
先别写代码,先写状态机:
| 状态 | 允许事件 | 下一个状态 | 关键不变量 |
|---|---|---|---|
CREATED | start | RUNNING | 同一个 task_id 只能有一个运行实例 |
RUNNING | success | SUCCESS | 成功结果只提交一次 |
RUNNING | fail | RETRYABLE_FAILED 或 FAILED | 失败必须记录原因和尝试次数 |
RUNNING | timeout | RETRYABLE_FAILED | 超时后必须释放资源 |
RETRYABLE_FAILED | retry | RUNNING | retry_count 增加,不能丢历史 |
SUCCESS | retry/success/fail | SUCCESS | 终态不能被重复副作用改变 |
FAILED | retry | 视策略决定 | 超过重试次数不能无限重试 |
再给每个任务一个幂等键:
idempotency_key = task_id + operation_name
当重复事件到达时,系统先查这个键是否已经提交过结果。如果提交过,就返回已有结果;如果没提交,才允许推进状态。这样你解决的就不是“如何重试”,而是“如何让重试不破坏状态”。
10. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- 为什么同一段字节可以是数字、字符、图片或协议字段?
- 为什么 bug 经常不是“代码看着错”,而是某个状态被改坏?
- 为什么栈、队列、树、堆这些结构都有自己的“不变量”?
- 为什么并发、协议、文件写入很难测全?因为状态组合太多。
- 遇到程序异常时,如何追问“状态从哪一步开始偏离预期”。
- 如何把一个任务、连接、缓存项、文件写入过程画成状态机。
如果你以后排查问题时能先问“当前状态是什么、合法转移是什么、哪个不变量坏了”,你就已经开始用 CS 的方式思考了。