ozine's book library

主题

分布式理论基础：先说清“什么结果算对” ​

两台服务器都存着库存 1。网络断开后，一边刚确认卖出，另一边又收到了购买请求。后者等多久？能否直接用本地库存？恢复连接后，两个订单怎么处理？CAP、一致性模型和共识理论，讨论的就是这种具体选择。

读完这篇，应当能给一个接口写清三件事：允许看到哪些结果，在哪些故障下仍要完成，以及判断先后顺序靠什么。文末有一个 Go 小模型，实际检查“可以排成某个顺序”和“尊重已经发生的先后”为什么不一样。它只检查很短的单寄存器历史，不模拟真实集群，也不证明某个数据库的正确性。

先把故障和时间假设摆出来 ​

“节点坏了”至少包含三类不同的事。进程退出后不再发送消息，是崩溃；进程重启后从持久化记录恢复，是崩溃恢复；节点可能伪造内容、给不同人发送矛盾回答，是拜占庭故障。Raft 这类崩溃容错协议并不自动处理第三类。[1][2]

网络故障又有自己的表现：消息丢失、重复、乱序、延迟，或者一部分节点之间长期不通。客户端超时只说明“在我的等待预算内没收到结果”。服务端可能没收到请求，也可能已经完成，只是响应没回来。因此写接口通常还需要请求标识、状态查询或幂等处理；换一个节点重试不能消除结果未知。

时间模型能假设什么对工程设计的影响
同步模型处理时间、通信延迟等有协议可依赖的已知上界可以用足够长的超时支持故障判断，但真实部署必须满足这些界限
完全异步模型不对处理速度和消息延迟给出上界有限时间内无法仅凭没收到消息区分“很慢”和“已死”
部分同步模型例如系统最终进入有界延迟阶段，但进入时间未知可以保持安全，同时在网络与调度恢复稳定后取得进展

这里的“同步”指系统模型，和业务代码里“同步调用一个 HTTP 接口”不是同一概念。FLP 的限制落在完全异步模型；实际共识系统的活性通常需要更强的时间条件。[3][4]

还要分清两种目标：安全性是不发生错误结果，活性是最终能推进。 网络完全隔离时暂缓写入，可能是在保安全；不能因为请求没有成功，就断言协议产生了错误结果。反过来，所有请求都很快返回，也不能证明结果满足业务约束。

一致性模型：约束的是“别人会看到什么” ​

假设一个初值为 0 的寄存器，支持 Write(v) 和 Read()。一次操作有调用、返回两个事件；多个客户端的这些事件组成一段历史。模型的任务是规定哪些历史允许出现。[5]

名称对观察结果的约束仍然没有自动得到什么
线性一致性，linearizability每次操作看起来在调用与返回之间某个瞬间生效；已完成操作与之后才开始的操作必须保持实际先后多个业务动作合成一个事务、跨对象隔离、无限故障下仍完成
顺序一致性，sequential consistency存在一个合法的全局串行顺序，并保留每个进程自己的操作顺序不要求保留不同进程之间的实际时间先后
因果一致性有因果依赖的操作保持顺序；互不依赖的并发操作可被不同观察者按不同顺序看见所有客户端看见相同总顺序
最终一致性停止新增更新且满足传播、恢复、冲突处理等条件后，副本最终趋于一致收敛期限、读取自己刚写的值、业务冲突自动解决
“强一致”工程材料常用的概括词，必须回到产品或接口的具体定义仅凭这三个字无法知道承诺的是哪一种模型

线性一致性与顺序一致性的定义分别来自 Herlihy/Wing 和 Lamport；最终一致性及常见会话保证可参看 Vogels 对实际系统的说明。[5][6][7] “读己之写”“单调读”是有用的会话保证，但不能仅从“最终一致”推出来。例如用户更新头像后被负载均衡到旧副本，头像可能短暂变回去；固定会话、携带版本并等待副本追上，都是可以进一步讨论的实现方向。

写已经成功，另一个人还能读到旧值吗？ ​

下面这段历史中，A 写入 1 并收到成功，B 之后才发起读取，却读到 0。时间编号表示观察到的事件顺序，不依赖两台机器的墙上时钟对齐。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
sequenceDiagram
    participant A as 客户端 A
    participant S as 存储服务
    participant B as 客户端 B
    A->>S: 事件 1：Write(1)
    S-->>A: 事件 2：写成功
    B->>S: 事件 3：Read()
    S-->>B: 事件 4：返回 0
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
sequenceDiagram
    participant A as 客户端 A
    participant S as 存储服务
    participant B as 客户端 B
    A->>S: 事件 1：Write(1)
    S-->>A: 事件 2：写成功
    B->>S: 事件 3：Read()
    S-->>B: 事件 4：返回 0

如果只要求顺序一致，可以在抽象顺序里把 B 的读排在 A 的写之前。每个客户端都只有一次操作，自己的顺序没有被破坏。线性一致不允许这么排，因为 A 的写已在 B 开始读之前返回。

模型用同一份历史分别尝试两种约束：

go
h := []Op{{"A", 1, 2, true, 1}, {"B", 3, 4, false, 0}}
fmt.Println("sequential:", validHistory(h, false),
    "linearizable:", validHistory(h, true))

实际输出：

text
sequential: true linearizable: false

validHistory 枚举候选串行顺序。无论哪种模式，都检查同一客户端的顺序和读值是否合法；线性一致模式再禁止把一个已经结束的操作排到后来开始的操作后面。测试另有一组重叠历史：写尚未返回时读到旧值，可能仍然线性一致，因为可以把读的生效点放在写之前。

“线性一致读”也不意味着响应送达那一瞬间永远最新。 读取与后续写入可能重叠。它要求找到满足规范的生效顺序，不要求传输中的响应不断更新。

数据库事务里的 ACID 一致性，通常说的是事务保持约束和不变量；隔离性又讨论并发事务的相互影响。这些术语与副本读写的线性一致性不能互换。例如两次单独的线性一致操作“读取余额”“扣款”，中间仍可能插入另一个扣款，业务要的是条件更新或事务。

可串行化（serializability）把一整个事务当作排列单位，要求并发事务的效果等价于某个串行执行；它本身不要求保留事务之间的实际时间先后。严格可串行化（strict serializability）再加入这个实际时间约束。因此不能看到“存在串行顺序”就把顺序一致、线性一致与事务可串行化当成同一个保证。[5，§3.3]

CAP：发生分区时，哪些请求必须让步？ ​

CAP 论文讨论的 C 是原子一致性，也就是线性一致的读写对象；A 要求每个由未故障节点收到的请求最终获得满足对象规范的响应；P 允许节点间通信发生分区。A 不是月度 uptime，也不能用“马上返回一个错误”偷换成功完成操作。[8]

继续看库存例子。分区两侧不能交换消息：

  1. 左侧将库存从 1 改为 0，已经回复成功。
  2. 右侧之后收到读取请求，但还保留库存 1。
  3. 右侧若返回 1，就违背这里要求的线性一致性；若要确保正确，就不能在不知道左侧状态时无条件完成这次读。

这说明，在论文的假设下，允许任意网络分区时，不能同时保证所有这些请求都完成并保持线性一致性。它没有告诉你“每个系统固定挑任意两个字母”，也没有说“一个暂时没有分区的系统必须牺牲一致性”。

业务动作一种合理的故障策略要明确接受的代价
扣库存、发放唯一名额只有可确认权威状态的一侧接收写入；无法确认的一侧拒绝或等待分区期间一部分请求不能成功
浏览商品描述允许返回带版本或更新时间的缓存页面可能暂时过时
离线编辑草稿两边各自接受修改，恢复后检测并合并冲突必须定义合并规则；覆盖丢字不能被“最终一致”掩盖

这些是按业务假设给出的设计例子，并不是 CAP 论文替某个产品做的分类。一个服务里，不同接口也可能采用不同策略。真正有用的设计文档应写“库存写入在失去多数派时如何响应”，而不是只贴一个 CP 标签。

BASE：把收敛做成流程，不能只留一句承诺 ​

BASE 常展开为 Basically Available、Soft state、Eventually consistent。Pritchett 用它讨论把一部分跨系统一致性工作移到异步流程的方式。[9] 它更像设计取向，不能当成与 CAP 同样形式的不可兼得定理，也没有给出统一的“基本可用”百分比。

例如订单已创建，积分稍后到账。允许这段不一致窗口，可以缩短下单的同步依赖链，但欠下的工作必须有记录：订单与待发送事件在本地原子提交；发送失败重试；消费端去重；长期失败进入告警、对账和人工处理。缺了这些，状态可能永远不收敛。

必须回答的问题一个能落地的答案应包含什么
哪个状态可以暂时落后？积分到账可以延迟；支付是否已成功必须单独查询权威状态
谁负责补齐？持久化待办、明确的执行者和重试状态
怎样处理重复和乱序？事件 ID、业务版本、幂等更新或显式冲突判断
怎么知道没有收敛？最老未处理任务年龄、失败积压、对账差异与责任人
多久以内应当完成？业务制定的目标及超时处理；不能把“最终”解释为无需期限

最终一致可以保留本地 ACID 事务。放松跨服务立即一致，并不意味着每个服务内部也要接受任意中间状态。

FLP：安全地等待为什么不能总有上界 ​

FLP 证明的是：在完全异步、确定性协议、允许哪怕一个进程崩溃的模型里，不能保证所有允许的执行都在有限步骤内达成共识。即便通信可靠，消息仍可被延迟任意长时间。[3]

直觉上的困难是：一个决定所需的信息迟迟没来，协议不能判断它来自已经崩溃的节点，还是来自尚未被调度的健康节点。为了不让两个节点作出冲突决定，协议可能必须继续等待；存在能一直让决定推迟的允许执行。

这不表示“现实世界无法选主”，也不表示“大部分请求都会卡死”。Raft/Paxos 可以在任意延迟下保持其安全性，并在足够稳定的通信和领导条件下推进；随机化协议也可以改变终止保证的形式。工程里设选举超时，是用故障怀疑帮助推进，不能把超时本身当作旧节点已经停止的证明。[1][4]

拜占庭问题：为什么多数票不一定够 ​

崩溃节点通常只是不回答。拜占庭节点却能对 A 说“提交 X”，对 B 说“提交 Y”。两组投票集合即使相交，交集也可能正好是会撒谎的节点；仅有集合相交，未必有诚实节点把信息带过去。

Lamport、Shostak、Pease 的经典“口头消息”模型，在指定的通信和故障假设下需要多于 3f 个节点来容忍 f 个叛徒；带可验证签名的模型又有不同结果。[2] 所以不能把 Raft 常见的 2f+1 个投票节点套到所有拜占庭系统，也不能把 3f+1 脱离认证、同步性和协议类型写成通用定律。

对通常由同一组织管理的后端集群，崩溃容错是常见的起点；不可信成员共同参与决策时，应先建立威胁模型。TLS 能保护链路及识别对端，并不会把一个已经被攻陷的、持有合法身份的节点变成诚实节点。

三种时钟各能回答什么 ​

时钟记录什么适合的问题限制
物理时钟日期、时刻及其估计误差展示时间、计划任务、跨系统审计的时间线偏差、漂移、校时回拨；时间接近不能证明因果
Lamport 逻辑时钟随事件递增的标量为满足因果方向的事件排序；配合节点 ID 打破相等a → b 推出 L(a) < L(b)，反方向不成立
向量时钟每个参与者的逻辑进度区分已知因果先后和并发更新元数据随参与者增加；成员变化、截断和合并都需额外设计

物理时间方面，Go 的 time.Now() 通常同时带墙上时钟和进程内单调读数；time.Since 可利用后者算耗时。序列化时间不保留单调部分，另一台机器也不能据此比较本地单调计数。[10] 订单上的 created_at 对人有用，却不应单独充当跨节点互斥、版本裁决或绝对业务顺序。

Lamport 时钟的规则很短：每次本地事件递增；发送消息携带计数；接收端取本地值与消息值的最大值，再加一。这样一条消息的发送一定排在接收之前。两个从不通信的节点也可以产生计数 1 和 2，因此数值更大不能反推出收到过前者的信息。[11]

向量时钟为每个节点留一个分量。A 的事件是 [1,0]，B 连续两次本地事件是 [0,2]。逐分量比较时，一边大一边小，二者互不支配，表示并发。B 收到 A 的消息，先逐分量取最大，再增加自己的分量，得到 [1,3]；此时 [1,0] 才真正先于 [1,3]。[12]

go
a, b := Vector{1, 0}, Vector{0, 2}
fmt.Println("A before B:", before(a, b), "B before A:", before(b, a))
merged := receive(b, a, 1)
fmt.Println("B receives A:", merged, "A before receive:", before(a, merged))

实际输出：

text
A before B: false B before A: false
B receives A: [1 3] A before receive: true

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    A["A：本地事件 [1,0]"] -->|"携带向量的消息"| R["B：接收后 [1,3]"]
    B1["B：本地事件 [0,1]"] --> B2["B：本地事件 [0,2]"] --> R
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    A["A：本地事件 [1,0]"] -->|"携带向量的消息"| R["B：接收后 [1,3]"]
    B1["B：本地事件 [0,1]"] --> B2["B：本地事件 [0,2]"] --> R

图里 A 与 B2 没有可达路径，所以不能说谁导致谁。添加“节点 ID”可以把所有事件硬排成一个全序，但只是一个与因果兼容的排序规则，不会创造原本不存在的因果关系。

选择时钟之前，先问需要的是“几点发生”“谁依赖谁”还是“必须唯一确定一个先后”。三种问题对应的机制和代价并不相同。

依据与验证范围 ​

  1. Raft 原论文，§2、§5：状态机复制、崩溃故障与安全性/活性。
  2. The Byzantine Generals Problem，§3–4：口头消息和签名消息模型。
  3. Fischer、Lynch、Paterson，1985，§1–4：完全异步系统的共识不可能性。
  4. Dwork、Lynch、Stockmeyer：Consensus in the Presence of Partial Synchrony：部分同步模型。
  5. Herlihy、Wing：Linearizability，§2–3：历史、线性一致性与实际时间顺序。
  6. Lamport：How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs：顺序一致性的原始定义。
  7. Vogels：Eventually Consistent—Revisited：最终一致与会话保证。
  8. Gilbert、Lynch：Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services：CAP 的模型和定义。采用正文可正常提取的原论文副本。
  9. Pritchett：BASE: An Acid Alternative，2008：BASE 术语来源；本次出版页正文访问失败，本文不引用其具体案例或原话。
  10. Go 1.27.2 time 文档：单调时钟与序列化边界。
  11. Lamport：Time, Clocks, and the Ordering of Events，§2–3：happened-before 与逻辑时钟。
  12. Mattern：Virtual Time and Global States of Distributed Systems：向量时间与因果关系。

本次使用 Go 1.27.2、Linux/amd64。go run .、go test -count=1 -v ./...、go test -race -count=1 ./...、go vet ./... 均实际通过。历史检查器只支持至多 8 个已完成、客户端内无重叠的单寄存器操作，初值固定为 0，所有事件编号互不相同，因此代码用严格小于判断先后；它没有处理未完成操作、多对象事务、真实网络和持久化恢复。向量示例固定两个参与者，没有处理成员变更。没有部署或验证分布式数据库。

完整可复现实验 ​

把以下三个文件放在同一空目录。只依赖标准库，不需要外部服务。

sh
go run .
go test -count=1 -v ./...
go test -race -count=1 ./...
go vet ./...

go.mod ​

mod
module example.com/distributed/theory

go 1.27.2

main.go ​

代码块 · 80 行 · 点击收起 / 展开
go
package main

import "fmt"

type Vector [2]int

func before(a, b Vector) bool {
	less := false
	for i := range a {
		if a[i] > b[i] {
			return false
		}
		less = less || a[i] < b[i]
	}
	return less
}
func receive(local, message Vector, node int) Vector {
	for i := range local {
		local[i] = max(local[i], message[i])
	}
	local[node]++
	return local
}

type Op struct {
	Client     string
	Start, End int
	Write      bool
	Value      int
}

// Only completed operations on one register, initially zero. Bounded to 8 operations.
func validHistory(h []Op, realtime bool) bool {
	if len(h) > 8 {
		panic("bounded checker: at most 8 operations")
	}
	var visit func([]bool, int, int) bool
	visit = func(used []bool, depth, value int) bool {
		if depth == len(h) {
			return true
		}
		for i, op := range h {
			if used[i] {
				continue
			}
			blocked := false
			for j, prior := range h {
				if i == j || used[j] {
					continue
				}
				if (prior.Client == op.Client && prior.Start < op.Start) || (realtime && prior.End < op.Start) {
					blocked = true
				}
			}
			if blocked || (!op.Write && op.Value != value) {
				continue
			}
			next := value
			if op.Write {
				next = op.Value
			}
			used[i] = true
			if visit(used, depth+1, next) {
				return true
			}
			used[i] = false
		}
		return false
	}
	return visit(make([]bool, len(h)), 0, 0)
}
func main() {
	a, b := Vector{1, 0}, Vector{0, 2}
	fmt.Println("Lamport 1 < 2:", 1 < 2)
	fmt.Println("A before B:", before(a, b), "B before A:", before(b, a))
	merged := receive(b, a, 1)
	fmt.Println("B receives A:", merged, "A before receive:", before(a, merged))
	h := []Op{{"A", 1, 2, true, 1}, {"B", 3, 4, false, 0}}
	fmt.Println("sequential:", validHistory(h, false), "linearizable:", validHistory(h, true))
}

main_test.go ​

go
package main

import "testing"

func TestClocks(t *testing.T) {
	a, b := Vector{1, 0}, Vector{0, 2}
	if before(a, b) || before(b, a) || before(a, a) {
		t.Fatal("concurrent/equal vectors ordered")
	}
	if !before(a, receive(b, a, 1)) {
		t.Fatal("lost causal edge")
	}
}
func TestHistories(t *testing.T) {
	cases := []struct {
		name     string
		h        []Op
		seq, lin bool
	}{
		{"stale after completion", []Op{{"A", 1, 2, true, 1}, {"B", 3, 4, false, 0}}, true, false},
		{"overlap may read old", []Op{{"A", 1, 4, true, 1}, {"B", 2, 3, false, 0}}, true, true},
		{"same client cannot go back", []Op{{"A", 1, 2, true, 1}, {"A", 3, 4, false, 0}}, false, false},
		{"fresh read", []Op{{"A", 1, 2, true, 1}, {"B", 3, 4, false, 1}}, true, true},
	}
	for _, c := range cases {
		t.Run(c.name, func(t *testing.T) {
			if validHistory(c.h, false) != c.seq || validHistory(c.h, true) != c.lin {
				t.Fatal(c.name)
			}
		})
	}
}

保留各书来源与许可 · 示例运行条件以正文为准