23.6 happened-before 关系

一句话

happened-before 是分布式系统里最基础的那个不依赖物理时钟的“先后”定义：a → b 当且仅当存在一条从 a 到 b 的消息链（含同进程内的程序顺序）；它是偏序而不是全序，两个事件不可比就是并发——并发不是“同时发生”，而是“无法从因果上排序”。

定义：三条规则，一个传递闭包

Lamport 在 1978 年的《Time, Clocks, and the Ordering of Events in a Distributed System》里给出的定义只有三条：

#	规则	记法
1	同一进程内，先执行的事件先于后执行的事件（程序顺序）	`a ≺_p b ⇒ a → b`
2	消息的发送先于该消息的接收	`send(m) → recv(m)`
3	传递性：`a → b` 且 `b → c`，则 `a → c`	`→` 是传递关系

关键在于：没有第四条。→ 是满足上面三条规则的最小关系（传递闭包），凡是不能靠这三条推出来的先后，一律不算。

进程 P1:   a1 ──▶ a2 ── send(m) ──▶ a3
                       │
                       ▼
进程 P2:   b1 ──▶ b2 ─ recv(m) ──▶ b3 ── send(n) ──▶ b4
                                                      │
                                                      ▼
进程 P3:   c1 ─────────────────────────────── recv(n) ──▶ c2

由规则可得：a2 → b2 → b3 → c2，再由传递性：a2 → c2
但：a3 与 b2 不可比 —— a3 虽然在 a2 之后，却没有一条边通向 b2

🔑 “不可比”不是“同时发生”，也不是“谁先谁后都行”：它是没有任何因果依据。两个不可比的事件在物理时间上可能差几秒，也可能真的同时。

六条性质，决定了它能干什么、不能干什么

性质	含义	工程后果
严格偏序	非自反（`a → a` 不成立）、反对称（不能互达）、传递	不能拿来给事件“打分排序”，只能比“有没有路”
不是全序	并发事件之间没有先后	需要一个全序时，必须人为加决胜规则（如进程 ID）
并发 = 不可比	`a ∥ b` 定义为 `¬(a→b) ∧ ¬(b→a)`	冲突检测的唯一严谨判据：只有并发写才需要合并
不依赖时钟	定义里没有任何物理时间	时钟漂移、NTP 误差都不影响结论
蕴含物理先后	消息传播需要时间，所以 `a → b` 意味着 a 在物理时间上不晚于 b	它给出的顺序不会与“真实发生顺序”矛盾
不等于实时顺序	两个进程各干各的、没有消息往来，实时上分先后也仍然不可比	线性一致比“尊重 HB”更强（见下节）

最后一条最容易反直觉：HB 是实时顺序的子集，不是超集。a → b 一定意味着 a 在实时上不晚于 b；但“a 在实时上早于 b”推不出 a → b——没有消息链，就没有因果关系。

与四个一致性模型的关系

这是它最实用的地方：不同的一致性模型，对 → 的要求不同。

模型	是否必须尊重 HB	还额外要求什么	主场
线性一致	是	还要与实时顺序一致（全序是 HB 的线性扩展）	16.2 线性一致性
顺序一致	是	所有进程共享一个全序，且保程序顺序	16.3 顺序一致性
因果一致	只要求尊重 HB	不要求全序，并发事件可各看各的	16.4 因果一致性
最终一致	不要求	只要求最终收敛，允许出现“因果气泡”	16.5 最终一致性

💡 一句话记住：线性一致 = HB + 实时；因果一致 = 只有 HB；最终一致 = 连 HB 都不管。

完整的一致性谱系、四个模型之间的包含关系与判定方法，见 16.7 一致性模型谱系图。

怎么判定：两种时钟，两种结论

关系定义好了，剩下的问题是“我怎么知道 a → b”。这需要元数据：

手段	能判定什么	每个事件的空间	主场
Lamport 时钟	`a → b ⇒ C(a) < C(b)`（必要不充分）	8 字节	23.3 Lamport 逻辑时钟
向量时钟	`a → b ⇔ V(a) < V(b)`（充分必要）	N 个计数（N 个节点）	23.4 向量时钟
矩阵时钟	还能知道“别人知道我知道什么”	N² 个计数	用于垃圾回收、因果投递
混合逻辑时钟（HLC）	保因果（同 Lamport），但判不了并发；数值贴近物理时间	8–16 字节	23.5 混合逻辑时钟 (HLC)

向量时钟的账单：N 个节点、每个计数 8 字节，单事件元数据 8N 字节。100 个节点 = 800 字节/事件；1 亿事件 = 80GB 的因果元数据。这就是为什么大规模系统要么限制副本数（N 小），要么用 HLC 之类的近似方案，要么干脆只保留“最近 K 个版本”。

从定义直接算：HB 就是图上的可达性

抛开时钟，→ 的定义本身就是一张有向图上的可达性：程序顺序连边、消息传递连边，然后求传递闭包。下面这段程序完全按定义实现，不依赖任何时钟：

package main

import "fmt"

type event struct {
	id      string
	edges   []string // 直接前驱（程序顺序 + 消息传递）
	lamport int
}

func main() {
	evs := []*event{
		{id: "e1"}, {id: "e2"}, {id: "e3"}, // 进程 P1
		{id: "f1"}, {id: "f2"}, {id: "f3"}, // 进程 P2
		{id: "g1"}, {id: "g2"},             // 进程 P3
	}
	byID := map[string]*event{}
	for _, e := range evs {
		byID[e.id] = e
	}
	link := func(a, b string) { byID[b].edges = append(byID[b].edges, a) }

	// 规则 1：程序顺序
	link("e1", "e2"); link("e2", "e3")
	link("f1", "f2"); link("f2", "f3")
	link("g1", "g2")
	// 规则 2：消息传递（e2→f2、f3→g2）
	link("e2", "f2"); link("f3", "g2")

	// 规则 3：传递闭包 —— 对每个事件做一次 BFS，看它能到达谁
	reach := map[string]map[string]bool{}
	for _, e := range evs {
		seen := map[string]bool{}
		stack := []string{e.id}
		for len(stack) > 0 {
			cur := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			for _, nxt := range evs {
				if seen[nxt.id] {
					continue
				}
				for _, pre := range nxt.edges {
					if pre == cur {
						seen[nxt.id] = true
						stack = append(stack, nxt.id)
						break
					}
				}
			}
		}
		reach[e.id] = seen
	}

	// 顺便算一遍 Lamport 时钟（按拓扑序：P1、P2、P3 的事件交错但前驱在前）
	for _, id := range []string{"e1", "f1", "g1", "e2", "f2", "e3", "f3", "g2"} {
		m := 0
		for _, pre := range byID[id].edges {
			if byID[pre].lamport > m {
				m = byID[pre].lamport
			}
		}
		byID[id].lamport = m + 1
	}

	// 关系表：→ 因果先于，← 因果后于，∥ 并发，= 自身
	fmt.Println("=== 由定义（可达性）算出的 happened-before 关系 ===")
	fmt.Printf("%4s", "")
	for _, e := range evs {
		fmt.Printf("%4s", e.id)
	}
	fmt.Println()
	for _, a := range evs {
		fmt.Printf("%4s", a.id)
		for _, b := range evs {
			switch {
			case a.id == b.id:
				fmt.Printf("%4s", "=")
			case reach[a.id][b.id]:
				fmt.Printf("%4s", "→")
			case reach[b.id][a.id]:
				fmt.Printf("%4s", "←")
			default:
				fmt.Printf("%4s", "∥")
			}
		}
		fmt.Println()
	}

	// 并发对：无序对里既非 a→b 也非 b→a
	conc := 0
	for i := 0; i < len(evs); i++ {
		for j := i + 1; j < len(evs); j++ {
			a, b := evs[i].id, evs[j].id
			if !reach[a][b] && !reach[b][a] {
				conc++
			}
		}
	}
	total := len(evs) * (len(evs) - 1) / 2
	fmt.Printf("\n并发对：%d / %d（%.0f%%）\n", conc, total, 100*float64(conc)/float64(total))

	// Lamport 时钟只给必要条件：比较时钟大小，看能不能判定因果
	fmt.Println("\n=== Lamport 时钟的局限（C(a) < C(b) 不代表 a → b）===")
	fmt.Printf("%-4s %-4s %-6s %-6s %-8s\n", "a", "b", "C(a)", "C(b)", "真实关系")
	for _, pair := range [][2]string{{"f1", "e3"}, {"e3", "f2"}, {"e1", "f3"}} {
		a, b := byID[pair[0]], byID[pair[1]]
		rel := "并发 ∥"
		if reach[a.id][b.id] {
			rel = "a → b"
		} else if reach[b.id][a.id] {
			rel = "b → a"
		}
		fmt.Printf("%-4s %-4s %-6d %-6d %-8s\n", a.id, b.id, a.lamport, b.lamport, rel)
	}
}

本机实测（macOS，Apple M1，Go 1.27）：

=== 由定义（可达性）算出的 happened-before 关系 ===
      e1  e2  e3  f1  f2  f3  g1  g2
  e1   =   →   →   ∥   →   →   ∥   →
  e2   ←   =   →   ∥   →   →   ∥   →
  e3   ←   ←   =   ∥   ∥   ∥   ∥   ∥
  f1   ∥   ∥   ∥   =   →   →   ∥   →
  f2   ←   ←   ∥   ←   =   →   ∥   →
  f3   ←   ←   ∥   ←   ←   =   ∥   →
  g1   ∥   ∥   ∥   ∥   ∥   ∥   =   →
  g2   ←   ←   ∥   ←   ←   ←   ←   =

并发对：12 / 28（43%）

=== Lamport 时钟的局限（C(a) < C(b) 不代表 a → b）===
a    b    C(a)   C(b)   真实关系
f1   e3   1      3      并发 ∥
e3   f2   3      3      并发 ∥
e1   f3   1      4      a → b

三个读法，比结论本身重要：

现象	解释
`e3` 与 `f2` 都是 `e2` 的“后代”，却互不可比	HB 只沿程序顺序和消息边传播，不会因为“共享祖先”就横向连边
8 个事件里 12 对并发（43%）	并发是常态：只有一条消息链上的事件才可比
`f1` 的时钟（1）小于 `e3`（3），但两者并发	Lamport 时钟只保证“因果 ⇒ 时钟小”，不保证反过来

⚠️ 用可达性算闭包的复杂度是 O(V·E)；真实系统每秒百万事件，算不起。所以工程上不存图，而是增量维护时钟（23.3/23.4 的主场），把“判定”变成两次整数比较。

Go 的内存模型：同一个关系，另一个域

Go 1.19 起的内存模型（go.dev/ref/mem）用的就是这套结构，只是把“事件”换成了内存操作：

happens-before 定义为 sequenced before（同一 goroutine 内的程序顺序）与 synchronized before（同步操作建立的顺序）的并集的传递闭包。

结构完全同源：程序顺序 = 规则 1，同步操作 = 规则 2，传递闭包 = 规则 3。但域不同：Go 的 HB 管的是“对同一变量的读写有没有竞争”，分布式的 HB 管的是“跨进程事件的因果”。混用会出错，见后面的误解表。

Go 内存模型里的十条规则

动作	规则（Go 内存模型原文的浓缩）
包初始化	所有 `init` 完成 synchronized before `main.main` 开始
启动 goroutine	`go f()` 这条语句 synchronized before `f` 的执行开始
goroutine 退出	不保证 synchronized before 任何事件（这是最大的坑）
channel 发送 → 接收	发送 synchronized before 对应接收完成
关闭 channel	`close(c)` synchronized before 因关闭而返回零值的接收
无缓冲接收 → 发送	接收 synchronized before 对应发送完成（会合语义）
容量 C 的缓冲 channel	第 k 次接收 synchronized before 第 k+C 次发送完成
`sync.Mutex` / `RWMutex`	第 n 次 `Unlock` synchronized before 第 m 次 `Lock` 返回（n < m）
`sync.WaitGroup`	`Wait` 返回时，所有被等待的 `Done` 之前的写都可见（细节以 `sync` 包文档为准）
`sync.Once` / `sync/atomic`	`f` 完成 synchronized before 任何 `Do` 返回；原子操作 A 的效果被 B 观察到，则 A synchronized before B（原子操作整体是顺序一致的）

实测：有同步与没同步，差一条边

package main

import "fmt"

func main() {
	// 反面：读与写之间没有任何 HB 边
	x := 0
	go func() { x = 42 }()
	fmt.Println("读到:", x)

	// 正面：close(done) happens before <-done，之后读 y 才有保证
	y := 0
	done := make(chan struct{})
	go func() {
		y = 42
		close(done)
	}()
	<-done
	fmt.Println("读到:", y)
}

用 go run -race race.go 跑（Go 官方文档给出量级：耗时 2–20 倍、内存 5–10 倍）：

读到: 0
==================
WARNING: DATA RACE
Write at 0x00c000012178 by goroutine 6:
  main.main.func1()
      /tmp/hb/race.go:8 +0x2c

Previous read at 0x00c000012178 by main goroutine:
  main.main()
      /tmp/hb/race.go:9 +0xcc

Goroutine 6 (running) created at:
  main.main()
      /tmp/hb/race.go:8 +0x9c
==================
读到: 42
Found 1 data race(s)
exit status 66

报告插在哪一行、两行 读到 谁先谁后、地址是多少，每次都不同；固定的是 Found 1 data race(s) 与退出码 66。

第一段（x）被 race detector 判定为数据竞争：go func(){ x = 42 }() 与 fmt.Println(x) 之间没有 HB 边——goroutine 的退出不同步于任何事件，所以主 goroutine 完全可能先读到 0。第二段（y）靠 close(done) 与 <-done 建立了边，读到 42 是有保证的，不是运气。

💡 race detector 内部用的正是向量时钟一类的因果元数据（ThreadSanitizer）：靠记录每个内存访问的“因果时间”，判断两次访问是否不可比。Go 侧的调试工具和分布式侧的判定工具，是同一个数学对象的两套实现。

Go 里三个最常见的 HB 坑

坑	为什么错	正确做法
`go func(){ x = 1 }()` 之后 `time.Sleep` 再读 `x`	Sleep 不是同步操作，不建立任何 HB 边；优化器甚至可以删掉那个 goroutine	用 channel、`sync.WaitGroup` 或锁建立边
`wg.Add(1)` 写在 goroutine 内部	`Wait` 可能在 `Add` 之前返回（Add 与 Wait 之间没有顺序）	`Add` 必须在 `go` 之前，或在 Wait 之前
以为 `cancel()` 返回就代表处理函数已结束	`cancel` 只是关闭 `Done` 通道；子 goroutine 的退出没有 HB 保证	用 `WaitGroup` 等子任务真正退出，再释放资源

工程用途：HB 不是概念，是四类代码的骨架

用途	用 `→` 做什么	反例（不做会怎样）
冲突检测	只有 `a ∥ b` 才是真冲突，才需要合并规则	把顺序写也当冲突，合并逻辑复杂且会“合并掉”正常更新
因果投递	投递时保证“前驱已投递”，否则先缓冲	用户看到评论、看不到帖子（因果气泡，16.4）
幂等 / 去重	用 `(client_id, seq)` 或向量判断“这个前驱我处理过没有”	重试导致重复扣款（25.4 幂等设计与去重）
排障	trace 的 parent/child span 本质就是 HB 边	只按机器时间拼日志，跨机顺序全错（时钟漂移见 23.1 物理时钟与漂移）

🔑 判断“要不要协调”的第一问不是“强一致还是弱一致”，而是“这两个操作之间有没有 →”：有，就不需要特殊处理；没有，才需要选择合并规则或加协调（见 17.6 CAP 之后的补充理论）。

常见误解

误解	现实
“并发就是同时发生”	并发是不可比；两个差几秒的事件也可能并发，两个真正同时的事件也可能有因果边（同一进程内）
“时间戳小就是先发生”	Lamport 时钟只保证 `a→b ⇒ C(a)<C(b)`；反例见上面的 `f1(1)` 与 `e3(3)`
“时钟相同就是并发”	时钟相同只能说明“无法用这个时钟判定”，是否并发要用向量或图的定义
“HB 能给出全局顺序”	HB 是偏序；要全序必须额外加决胜规则（如比较进程 ID），而这个全序对并发事件是任意的
“Go 的 happens-before 就是分布式的 happened-before”	关系结构相同，域不同：一个管内存读写竞争，一个管跨进程因果；判定“数据竞争”和判定“业务冲突”是两件事
“用物理时间排序最省事”	时钟会漂移、会回拨；按物理时间给并发写排序就是 LWW，必然静默丢写（见 17.3 分区期间的取舍）

反模式

反模式	后果
用机器时间戳判断跨服务事件顺序	时钟漂移/回拨导致“结果早于原因”，排查被带偏
把 Lamport 时钟当因果判据	把并发写成“有先后”，冲突被静默吞掉
只给事件存“最新版本号”还声称能判并发	单个计数器无法区分“并发”与“因果”，必须向量（或图）
用 LWW 合并资金/库存	并发冲突被时间戳“解决”，丢写且不可追溯
在 Go 里用 Sleep 代替同步	数据竞争，race detector 一跑就报，线上表现为随机读到旧值
用 goroutine 退出隐式表示“写完了”	无 HB 保证，主流程可能先读后写
把因果一致当成“不用管顺序”	因果一致恰恰要求尊重 HB（16.4）

自检

Q1 已知 C(a) = 3、C(b) = 5（Lamport 时钟）。能推出 a → b 吗？能推出什么？

▸ 答案：不能推出 a → b。Lamport 时钟只保证 a → b ⇒ C(a) < C(b)；反过来不成立（实测里 f1(1) 与 e3(3) 就是并发）。能推出的是它的逆否命题：C(a) ≥ C(b) ⇒ ¬(a → b)，即 b 不可能在因果上先于 a。要判定并发与否，必须用向量时钟或直接算可达性。

Q2 实测里 8 个事件有 12 对并发。为什么 e3 与 f2 不可比——它们明明都发生在 e2 之后（e2 → e3、e2 → f2）？

▸ 答案：HB 是传递闭包，只能沿“程序顺序”和“消息传递”往前走，不会因为两个事件有共同祖先就产生横向的边。e2 → e3 与 e2 → f2 只说明二者都在 e2 之后，不说明它们之间的先后。要成为 e3 → f2，必须存在一条从 e3 到 f2 的路径（比如 e3 发消息给 P2），而图上没有。这也说明“共享祖先”不等于“有序”。

Q3 Go 里 go func(){ x = 1 }() 之后 time.Sleep(time.Second) 再读 x，为什么仍然可能读到 0？正确的写法是什么？

▸ 答案：Sleep 不是同步操作，不建立任何 happens-before 边；而 Go 内存模型明确说 goroutine 的退出不保证同步于任何事件，编译器甚至可能把这条 go 语句整个删掉。正确写法是用同步原语建立边：done := make(chan struct{}) + close(done) + <-done，或者 sync.WaitGroup 的 Add/Done/Wait，或者互斥锁。写了之后 go run -race 不再报竞争，才算真的对。

Q4 为什么说“只有并发写才需要合并”，而“有因果关系的写不需要特殊处理”？如果不管这个区别，会发生什么？

▸ 答案：如果 a → b，说明 b 的写入者已经看到了 a（消息链把它带过去了），所以“b 覆盖 a”是语义正确的最终状态，不需要合并。只有 a ∥ b 时，两边都不知道对方，才可能出现两个都“正确”的版本，需要 CRDT、业务规则或人工合并。若不管这个区别、一律按物理时间戳 LWW 合并，那么：① 本应被覆盖的旧写可能因时钟回拨反覆盖新写；② 真正的并发写被静默丢掉一条，且没有记录丢了什么（见 17.3 的 LWW 丢写量化）。

下游：23.4 向量时钟

Q5 为什么 “happened-before” 是偏序而不是全序？

▸ 答案：因为并发事件之间没有因果关系：既不是 a 先于 b，也不是 b 先于 a。偏序只定义 “能确定的先后”，剩下的并发对无法比较——这正是 Lamport 时钟只能保因果、向量时钟才能识别并发的原因（见 23.4 向量时钟）。