不会编译的数据竞争

# 一个编译不过的数据竞争 来源：https://corentin-core.github.io/posts/ruxe-type-level-disjointness/ *我是如何让 Rust 的类型系统拒绝我自己的并行 Redux 数据竞争的——经历了一次错误起步和一次思维转变。* --- 有一类错误，我为之熬过的夜晚多得自己都不愿记起。只在负载下出现，一挂上调试器就消失，需要三个工程师花一个周末才能定位。数据竞争。 Rust 的借用检查器能在值层级阻止大部分数据竞争。但不是全部，而且肯定解决不了我在这里感兴趣的问题：编译器能否拒绝构建一个*并行归约流水线*，其中两个归约器可能写入同一份状态？答案是能。 本文讲述了我如何在 `ruxe`（https://github.com/corentin-core/ruxe）——我那个 Redux 风格的 Rust 学习库——中实现这一点的故事。 ## 什么是 Redux？ Redux 是一种状态管理模式。它在前端 JavaScript 世界广为人知，但其形态更通用：任何通过离散事件改变状态的系统都符合这个模型。 ``mermaid flowchart LR User([用户代码]) -->|dispatch 事件| Store Store -->|state + 事件| Reducer Reducer -->|新 state| Store Store -->|读取| User `` Redux 之所以是 Redux，依赖于三条规则。第一：单一数据源。状态由 store 拥有，别无二处。第二：状态从外部不可变。你不能直接修改它，而是分发*事件*（JS 世界称之为“action”）来描述发生了什么。第三：状态转换通过一个纯*归约器*（reducer）完成，它是一个函数 `(state, event) → new state`。相同输入，相同输出，没有副作用。 正是第三条规则让 Redux 以易于调试著称。记录事件流，重放，每次都能得到相同的最终状态。时间旅行调试。从生产 traces 中诊断崩溃。可重现的 bug。任何曾经在缺乏该属性的有状态 UI 上调试过的人，都能理解为什么人们不断在重造 Redux。 ## 我为什么在意 在日常工作中，我负责运行在工业场站上的能源管理系统。技术栈中的一块在 Python 里使用了类似 Redux 的模式：控制层，多个控制器并发运行，需要共享且一致的场站状态视图。事件流入，一个归约器流水线计算出新状态，控制器从中读取。数据量增长的速度比你想象的要快。一个典型的场站有数十台设备，每个设备按自己的周期轮询，有些周期低至 50 毫秒。每台设备每次读取可以发布几十个寄存器。这是一个连续、高容量的事件流，而纯 Python Redux 难以跟上。 我们通过缓存读取并以比底层遥测更粗的频率触发归约来绕过这个问题。这样是可行的，但模式变得不再纯粹：状态不再与最新遥测保持同步，我们牺牲了 Redux 最初吸引人的一部分特性。 性能分析告诉我们时间到底花在哪里：归约阶段。场站有许多独立的子系统：太阳能、电池、电表、电网控制器等等。每个子系统持有全局状态的一个*切片*（slice），并且每个子系统有自己的归约器，只操作自己的切片。 ``mermaid flowchart LR Event[事件] --> R1[太阳能归约器] --> S1[太阳能切片] Event --> R2[电池归约器] --> S2[电池切片] Event --> R3[电表归约器] --> S3[电表切片] `` 以下是一切开始的观察：归约器之间是独立的。太阳能归约器从不触碰电池切片。电池归约器从不触碰电表切片。每个事件都要经过所有归约器一次。顺序执行会带来 N 倍的延迟。并行执行则只有 max(latency_i)。所以：将归约器并行化。从外部看事件流相同，结果确定性相同，只是每次分发的墙上时间减少了 N 倍。 有一个问题。并行加上共享状态等于数据竞争。如果一个归约器意外写入了另一个切片，你就得到了典型的并发 bug。非确定性的输出，生产环境中的流氓 bug，以及那些你临死前还会记起的调试会话。在大多数语言中，这就是类型系统放弃的地方。C++ 给你互斥锁和原子操作，然后祝你好运。更高级的语言提供同步原语和内存模型，但避免竞争的责任仍在开发者身上；编译器不强制任何事情，靠的是团队的纪律。 Rust 的类型系统可以直接编码这个属性。编译器本身可以拒绝构建会导致竞争的代码。这就是我在 ruxe 中想要证明的。 ## 思维模型：切片与互不相交性 两个概念支撑了后续所有内容。在继续之前，值得明确定义。 **切片**是状态的一个子字段。如果你的状态包含 `counter`、`user` 和 `notifications` 字段，这三个就是切片。 **切片归约器**是一个只看到自己切片的归约器。它不能触碰其他切片。类型系统禁止这样做：函数签名只暴露 `&Slice`，别无其他。 ``mermaid flowchart LR subgraph State SA[counter] SB[user] SC[notifications] end R1[CounterReducer] -.touches.-> SA R2[UserReducer] -.touches.-> SB R3[NotificationsReducer] -.touches.-> SC `` 我们想要的属性是**互不相交性**：在设置中的任意一对切片归约器，它们针对不同的切片。没有两个归约器会触碰同一个切片。 ``mermaid flowchart LR subgraph Disjoint["✅ 互不相交 —— 可安全并行"] D1[归约器 A] -.-> SA1[切片 A] D2[归约器 B] -.-> SB1[切片 B] end subgraph NotDisjoint["❌ 重叠 —— 可能数据竞争"] N1[归约器 A] -.-> SX[切片 X] N2[归约器 B] -.-> SX end `` 互不相交性是安全并行执行的充分必要条件。如果成立，并行就是可靠的。如果不成立，并行就会产生竞争。工程问题变成了：我能否让编译器拒绝一个违反互不相交性的并行根归约器？ ## 第一个想法：AllDistinct 以下是我开始时脑海中的想法，以及我为什么认为它会奏效。我从 C++ 转来 Rust。在 C++ 中，这种检查是模板元编程的日常操作。`std::is_same_v` 在编译时提供类型相等性。`!std::is_same_v` 提供不相等性。将其包装在 `static_assert`（或 C++20 的 concept）中，编译器完成其余工作。这个模式自然适用于任何足够丰富的类型系统。 Rust 表面上看起来足够相似。递归 trait 实现随处可见。`Vec` 在 `T: Clone` 时是 `Clone`。`Option` 在 `T: Send` 时是 `Send`。“如果它的部分具有属性 P，则该类型具有属性 P”这一模式内建于语言中。 所以，如果我写一个归约器类型列表，比如元组 `(R1, R2, R3)`，我应该能定义一个 trait `AllDistinct`，当没有两个 `Ri::Slice` 类型相同时成立。递归地遍历元组。每一步，检查头部的切片是否与尾部中的每个切片都不同。递归。 我头脑中的形状，用伪 Rust 表示（真正的元组不能这样递归遍历；我在遍历部分做了手势，而否定墙最终使得这一切无关紧要）： ```rust trait AllDistinct {} impl AllDistinct for () {} // 空元组显然是互异的 impl AllDistinct for (H, Tail) where Tail: AllDistinct, H: NotIn, // 并且 H 不在尾部中 {} ``` 看起来合理。递归在空元组处终止。每一步要求剩余部分互异，且头部不在剩余部分中。标准的结构递归。 我构建了它。到了 `NotIn`。卡住了。 `NotIn` 要求说“对于尾部中的每个元素 X，H ≠ X”。在 Rust 语法中，这会是类似这样的东西： ```rust trait NotIn {} impl NotIn for (H, Tail) where Tail: NotIn, H != T, // ← 这不是一个有效的东西 {} ``` 编译器： ``` error: expected one of `!`, `(`, `+`, `::`, `:`, `<`, `==`, or `=`, found `!=` ``` 稳定的 Rust 没有用于在 bound 中表达类型不相等性的语法。没有 `H != T`。没有办法写“如果其他 trait 是*未实现*的，则该 trait 被实现”。不稳定的特性 `negative_impls` 已经存在多年，但一直停留在连贯性问题的后面。别抱太大希望。 这不仅仅是缺少一个运算符。trait 系统*单调地*推理 impl：在代码库中添加更多的 impl 只会使更多代码能够编译，而永远不会使现有代码无法编译。否定推理（“这个 trait 是*未实现*的”）会破坏这一性质：有人添加了一个新的正面 impl 可能会使其他地方依赖该缺失的代码被废止。Rust 通过从一开始就不允许这种推理来避开整个问题类别。 这是 Rust 与 C++ 大相径庭的地方。在 C++ 中，`!std::is_same_v` 是一个你可以计算并在 `static_assert` 中使用的值。在 Rust 中，等价物没有表面语法，其原因并非粗心——而是设计选择。 在稳定 Rust 中，`AllDistinct` 是不可表达的。至少不是我所勾勒的形状。 ## 转折点 我对此纠结了一段时间。墙是真实存在的。但有时一堵墙只是走错了门。 我试图证明一个*否定*（没有重复）。Rust 说的是正面。如果我从另一个方向重新表述同一个属性会怎样？ | 表述 | 形式 | 在稳定 Rust 中 | |------|------|----------------| | “没有两个归约器针对同一个切片” | 否定 | 不可能（需要否定） | | “每个状态切片恰好有一个匹配的归约器” | 正面（双射） | 可实现（因 impl 的存在性） | 这两者在逻辑上是等价的：切片和归约器之间的双射意味着每个切片恰好有一个匹配，*并且*没有两个归约器共享一个切片。第二个条件由第一个推出。 所以，与其问“是否有重复？”，我应该问“是否存在完美匹配？”。第一个问题需要不可能的否定。第二个问题只要求某些 trait impl 的*存在性*，这正是 Rust 的拿手好戏。 具体来说：遍历状态的切片列表（由用户显式声明），对于每个切片类型，在归约器元组中找到其 `Slice` 关联类型与之匹配的归约器。三种结果： | 查找结果 | 行为 | 编译时结果 | |----------|------|------------| | 恰好一个归约器匹配 | 使用它，继续 | OK | | 两个或更多匹配 | — | 歧义 impl 错误 | | 零匹配 | — | trait bound 未满足 | 这些错误来自 Rust 的 trait 连贯性规则。我不需要编写显式的检查；trait 解析器在每个查找执行时都会强制执行它们。 为了在编译时遍历切片列表，我需要一个编译器可以递归遍历的结构。元组不合格：每个元数都是不同的类型，你需要为 `(A,)`、`(A, B)`、`(A, B, C)` 等分别编写单独的 impl。我想要的是一个递归结构*是其类型的一部分*的列表，这样 trait 解析可以自行下降。 这个结构在 Rust 生态系统中存在。它叫做 HList，是一个已知的模式。异构列表正如其名。一个链表，每个单元可以保存不同类型的一个值。形状： ```rust struct HCons<H, T> { head: H, tail: T } struct HNil; ``` 如果你眯起眼睛看，这是一个 Lisp cons 单元，但带有类型且在类型层面。一个三元素的 HList 看起来像： ```rust HCons<i32, HCons<String, HCons<f64, HNil>>> // ^ ^ ^ ^ // head 嵌套 cons 嵌套 cons 终止符 ``` 一个宏可以让你不那么痛苦地写： ```rust HList!(i32, String, f64) // 展开为： // HCons<i32, HCons<String, HCons<f64, HNil>>> ``` 视觉上它是一个嵌套的套娃： ``mermaid flowchart LR L1[HCons] --> H1[i32] & T1[HCons] T1 --> H2[String] & T2[HCons] T2 --> H3[f64] & T3[HNil] `` 这个结构是元组做不到的。编译器可以通过递归 trait impl 遍历它。为什么？每个 HList 要么是 `HNil`（终止符，匹配基本情况），要么是 `HCons`，其中 `T` 本身是一个 HList（匹配递归步骤）。你编写两个 impl，每种情况一个。你处理了任何元数。元组需要为你想要支持的每个元数编写单独的 impl，通常通过宏限定为 12 个。 crate `frunk`（https://crates.io/crates/frunk）是 Rust 的权威 HList 库。我借用了结构和模式。在 ruxe 内部重新实现了一个最小版本，以避免为了一个最终是内部细节的东西而引入传递依赖。接下来使用的词汇（HCons、HNil、Sculptor、位置见证者）都来自那里。 现在我有了一个编译器可以遍历的列表。是时候应用它了。 ## 突破口：用于切片归约器的 Sculptor frunk 有一个叫做 **Sculptor** 的模式。接受一个 HList，按类型提取某些元素，返回匹配的元素加上剩余的部分。 ```rust let list = hlist![1i32, "hello", 3.14f64]; let (matched, leftover) = list.sculpt::<(f64, i32)>(); // matched : HList!(3.14f64, 1i32) // leftover : HList!("hello") ``` 编译器遍历源 HList，通过递归直到找到匹配来选取每个请求的类型，构建匹配的元组，返回剩下的。解析器自动捕获两种失败模式。请求一个源中不存在的类型：编译错误。请求一个出现多次的类型：编译错误（歧义）。 将其应用到我遇到的问题。我有一个状态的切片列表（由用户声明，像 `HList!(CounterSlice, UserSlice, NotificationSlice)`）和一个归约器 HList（从用户传入的元组派生）。我遍历切片列表。对于每个切片，我在归约器 HList 中查找其 `Slice` 关联类型与该切片匹配的归约器。Sculptor 风格的查找，但匹配的是关联类型而不是具体类型。 ``mermaid flowchart LR subgraph Slices S1[CounterSlice] S2[UserSlice] S3[NotificationSlice] end subgraph Reducers R1[CounterReducer] R2[UserReducer] R3[NotificationReducer] end S1 -.match.-> R1 S2 -.match.-> R2 S3 -.match.-> R3 `` 我想要的失败模式自然地由解析器产生。 ``mermaid flowchart TB subgraph Happy["✅ 快乐路径 —— 唯一匹配"] direction LR H1[切片 A] --> H2[找到位置 0 的归约器] end subgraph Duplicate["❌ 两个归约器针对同一个切片"] direction LR D1[切片 A] --> D2{归约器 for A?} D2 --> D3[位置 0 匹配] D2 --> D4[位置 2 匹配] D3 & D4 --> D5[歧义：编译错误] end subgraph Missing["❌ 状态切片没有归约器"] direction LR M1[切片 B] --> M2{归约器 for B?} M2 --> M3[任何地方都不匹配] M3 --> M4[无 impl：编译错误] end Happy ~~~ Duplicate Duplicate ~~~ Missing `` 我从未编写过任何显式检查，如“是否有重复？”或“是否所有切片都被覆盖？”。解析器自己完成了这一切，因为它对每个其他查找都这样做。我只需要以它能回答的方式提出问题。 ## 位置见证者：类型系统中的 Peano 数 实现时有一个重要的细节。用于“找到目标切片 T 的归约器”的递归 trait 有两个 impl： ```rust // 基本情况：头部匹配目标 impl<HeadReducer, Tail> FindReducerBySlice<...> for HCons<HeadReducer, Tail> where HeadReducer: SliceReducer<Slice = T>, { ... } // 递归情况：头部不匹配，在尾部中查找 impl<HeadReducer, Tail> FindReducerBySlice<...> for HCons<HeadReducer, Tail> where Tail: FindReducerBySlice<T>, { ... } ``` 如果没有区分符，这两个 impl 会重叠。两者的签名都是 `impl ... for HCons<...>`。Rust 的连贯性规则不允许这样。 frunk 的解决方案：向 trait 添加一个位置见证者。 ```rust struct Here; struct There<I> { _marker: PhantomData<I> } trait FindReducerBySlice<Slice, Index> { ... } impl ... for HCons<...> where Index = Here { ... } // 在此层级匹配 impl ... for HCons<...> where Index = There<I> { ... } // 递归，内部索引为 I ``` `Here` 和 `There` 在类型层面是 Peano 数。 > **Peano 数**：一种仅通过两种成分定义自然数的方式——*零*和*后继*函数。数字 0 就是“零”。1 是“零的后继”。2 是“后继的后继”。3 是再深一层的 `successor`，以此类推。整个正整数序列是通过在零之上堆叠后继构建的。在数学中很有用（这就是 Peano 在 1889 年形式化自然数的方式），在类型级编程中，每当需要在不使用运行时值的情况下编码一个计数时也很有用。在我们的例子中：`Here` 扮演零的角色。`There` 扮演后继的角色，包裹内部一个更小的数。`There<Here>` 是 1，`There<There<Here>>` 是 2，依此类推。它们编码了编译器找到匹配所走的路径——在头部匹配之前，它进行了多少次 `tail` 跳跃。 ## 实现骨架 现在我们有所有部件，实现大致呈现出这种形状。细节在 [r