在 READ COMMITTED 隔离级别上构建可线性化日志

# 在 READ COMMITTED 隔离级别上构建可线性化日志 | Materialize 来源：https://materialize.com/blog/building-a-linearizable-log-on-read-committed/ Materialize 的存储层（`persist`）需要一个元数据存储，为每个持久化对象维护少量状态。六月，一个拥有大量此类对象的自部署实例经历了一次亚稳态故障（metastable failure）：元数据操作延迟从几毫秒飙升至三十秒，导致了一次事故。 Materialize 的自部署实例使用 PostgreSQL 数据库作为元数据存储，事故期间其大部分连接都处于等待状态。`SIRead` 锁的数量增长到了数十万，这表明在 `SERIALIZABLE` 隔离级别下运行查询的成本已成为瓶颈。 本文讲述了我们如何重新设计 `persist` 元数据存储的实现，使其能够在 `READ COMMITTED` 隔离级别下运行查询的同时构建可线性化日志。新实现能够承受三倍的写入吞吐量，并且即使在负载超出 PostgreSQL 数据库承载能力时也能优雅降级。此外，我们还描述了如何通过在 Lean 4 中对 PostgreSQL 的 `READ COMMITTED` 行为进行建模，并证明该设计是可线性化的，从而获得对其正确性的信心。 ## 将 Shard 视为状态差异的日志 Materialize 中的每个持久化对象（例如表或物化视图）都由 `persist` 以一个称为 shard 的单元来存储。Shard 的大部分数据存储在对象存储中，而元数据存储则保存 shard 的状态：当前哪些数据文件构成该 shard、其在时间维度上的进展程度，以及哪些读取器持有旧数据。 Shard 的状态可能因多种原因而改变，包括新数据提交、读取器推进其读取保持（read hold）等。在 Materialize 部署中，可以有多个独立进程同时持有同一个 shard ID 的 shard 句柄。为确保每个 shard 只有一份状态历史，我们以常规方式在进程之间协调状态变更操作： - 对于每个 shard，元数据存储维护一个带版本的状态差异日志。 - 每个进程尝试通过比较并交换（compare-and-set）操作来扩展此日志。 - 状态的每个版本被分配一个比前一个高一的序列号。 - 写入者读取最新版本，计算出下一个版本，然后请求数据库在条件——即其读取的版本仍为最新——成立时将其追加；若条件不成立，则重新读取并重试。 我们将提供此功能的组件称为"共识实现"，在 PostgreSQL 上它是一张表： ```sql CREATE TABLE consensus ( shard text NOT NULL, sequence_number bigint NOT NULL, data bytea NOT NULL, PRIMARY KEY (shard, sequence_number) ); ``` `persist` 在其上执行四种操作： - `head(shard)` 返回序列号最大的行。 - `scan(shard, from)` 按顺序返回序列号不小于 `from` 的所有行。 - `compare_and_set(shard, seqno, state_diff)` 在 `seqno` 恰好比当前头部高一时追加 `state_diff`，并返回 `Committed` 或 `ExpectationMismatch`。我们将其简称为 CaS，并将 `seqno - 1`（即写入者认为是头部的版本）称为 `expected`。Shard 的第一个版本的序列号为 0，因此 `expected` 未定义。该特殊情况将在下文单独说明。 - `truncate(shard, cut)` 删除所有序列号低于 `cut` 的行。它不得删除头部。 要使此方案正常工作，日志必须表现得如同操作按某种与发出时间一致的顺序逐一发生。它必须是可线性化的（linearizable）。两个写入者不能同时在同一个序列号上成功，任何写入者也不能在已被截断的序列号上成功，因为其写入的状态将基于系统其余部分已丢弃的版本构建，无论哪种结果都会导致 shard 产生分叉。 ## SERIALIZABLE 的代价 在这项工作之前，共识查询在 `SERIALIZABLE` 隔离级别下运行，这是在 PostgreSQL 中获得可线性化的最简单方式，因为如果每个事务都是可串行化的，那么任何交错执行都等同于某种串行顺序，SQL 只需在串行顺序下正确即可。我们使用的 CaS 查询会读取当前头部行，并在头部与 `expected` 匹配时插入下一行。Shard 的首次写入是一个由 `NOT EXISTS` 子句守卫的 `INSERT`，该子句断言该 shard 为空。这两个查询在逐一执行时都是正确的。 在 `SERIALIZABLE` 隔离级别下运行时，PostgreSQL 并不会真正逐个执行事务。为了提高性能，它尝试并发执行事务，并使用可串行化快照隔离（SSI）来检测可串行化冲突。其工作原理是：将事务的每次读取记录为其访问过的行和索引页上的 `SIRead` 锁，并让每次写入检查其触及页面上的 `SIRead` 锁，以检测事务间的读写冲突。 这些锁从事务提交之时起一直保留到与其重叠的所有事务都已完成为止，因为冲突仍可能与仍在运行的事务形成。在一个有数千个并发写入者的小型热表上，许多 shard 共享每个索引页，因此每次插入都需要遍历最近读取过同一页的每个事务的锁。 <!-- 图表说明 --> SERIALIZABLE 隔离级别下比较并交换吞吐量图表：上升至约每秒 4,300 次操作后崩溃 SERIALIZABLE 隔离级别下 SIRead 锁图表：随着吞吐量崩溃逼近 100,000 SERIALIZABLE 隔离级别下比较并交换 p50 和 p99 延迟图表：上升至约 30 秒并保持不变 这些图表来自在一台 `db.r6g.2xlarge` RDS 实例上的复现实验，负载为二十个 Materialize 集群，每个集群有六百个针对空表的简单物化视图，逐步上线。我们可以观察到，数据库能承受约每秒 4,300 次 CaS 的负载，但超过该点后，事务耗时变长导致保留的 `SIRead` 锁数量增长，这使得每次插入的冲突检查更加昂贵，进而使事务更加缓慢。延迟达到三十秒，吞吐量降至数据库此前所能承受水平的一小部分，直到我们移除负载后系统才恢复。 这就是 Bronson 等人所称的亚稳态故障 [1] 的失败模式：处于脆弱状态的系统被一个触发器推入不良状态，随后一个维持效应在触发器消失后仍将其锁定在该状态，因此恢复需要将负载降低到远低于引发故障的水平。 此案例中的触发器是事务处理的瞬时减速，导致 `SIRead` 锁数量增加，进而增加了每次写入的成本，使瞬时减速转变为持续效应。瞬时减速可能由负载的瞬时尖峰、数据库开始并发表维护（vacuuming）、进程暂停等引起。`SIRead` 锁计数就是论文中所说的特征度量（characteristic metric）——一个随触发器上升、只有在故障解决后才恢复正常的度量。论文建议处理维持效应而非触发器，因为许多不同的触发器会导致相同的故障状态。在我们的案例中，使用更大的数据库实例或减少 shard 数量只会将触发器转移到不同的阈值，而不依赖 `SERIALIZABLE` 则直接消除了维持效应。 避免 `SIRead` 锁的一种方法是在 `READ COMMITTED` 隔离级别下运行事务。然而，现有的查询在该模式下并不正确。在 `READ COMMITTED` 下，每条语句看到的是其开始时拍摄的快照，但 `INSERT` 对主键执行的唯一性检查是针对实时索引运行的，能看到在快照之后提交或删除的行，因此单条语句可能在 `WHERE` 子句中观察到一种状态，而当其 `INSERT` 执行时该状态已不再成立。事实证明，通过仔细调整查询，确实可以在 `READ COMMITTED` 下获得可线性化的日志行为。 ## Shard 日志的核心不变量 新设计依赖于表中每次操作后都维持的一个性质： > 某个 shard 存在的序列号总是形成一个连续区间 `[lo, head]`。 两个修改状态的操作是比较并交换和截断。比较并交换总是在顶部将区间扩展一。截断总是在排除头部的前提下移除一个前缀。其结果是，在连续日志中，条件"`expected` 存在且 `expected + 1` 不存在"等价于条件"`expected` 是头部"，后者正是 CaS 规范所要求的条件。因此，在日志是连续日志的假设下，我们可以使用 `SELECT` 和主键来实现规范中的条件。 <!-- 连续性不变量示意图：存在的序列号构成一个区间，只有当 expected 行存在且其后继行不存在时，比较并交换才能提交 --> 图 1. 连续性不变量以及 CaS 语句进行的两个局部检查。CTE 检查 `expected` 是否存在；主键检查 `expected + 1` 是否不存在。在连续日志中，两者合在一起等价于"`expected` 是头部"，这正是规范所要求的。低于 `lo` 的行已被截断；−1 处的标记永远不会被截断。 由此得出如下 CaS 查询： ```sql WITH expected_row AS ( SELECT sequence_number FROM consensus WHERE shard = $1 AND sequence_number = $expected FOR KEY SHARE ) INSERT INTO consensus (shard, sequence_number, data) SELECT $1, $expected + 1, $data FROM expected_row; ``` `expected_row` CTE（公共表表达式）检查写入者意图在其上构建的行是否存在，并对其获取共享锁；`INSERT` 则在主键允许的情况下添加 `expected + 1`。因此该语句仅在一种情况下插入行：前驱存在且其后继不存在——根据不变量，这意味着 `expected` 是头部。如果 CTE 未找到任何内容，`INSERT` 将影响零行；如果后继已存在，主键将拒绝插入。两种情况都报告为 `ExpectationMismatch`。 并发的 CaS 操作仅通过主键即可相互隔离。多个客户端可以同时对相同的 `expected` 运行该语句，此时它们都在各自的快照中看到 `expected + 1` 不存在，并且都尝试相同的 `INSERT`。主键只允许其中一个成功，其余的收到唯一性冲突，此时头部已经移动，`ExpectationMismatch` 对它们来说是正确的结果。`FOR KEY SHARE` 锁在此过程中不起作用，因为它是共享锁，并发的 CaS 操作在同一前驱上都能获取它而不会互相阻塞。它的作用是使 CaS 操作与截断操作之间保持有序，这将在本文后续部分讨论。 其他操作是单条语句。`head` 和 `scan` 各为一条 `SELECT`： ```sql -- head SELECT sequence_number, data FROM consensus WHERE shard = $1 ORDER BY sequence_number DESC LIMIT 1; -- scan SELECT sequence_number, data FROM consensus WHERE shard = $1 AND sequence_number >= $from ORDER BY sequence_number ASC LIMIT $limit; ``` 单条语句看到的是一个快照，因此每条语句都观察到日志在某一瞬间的状态。 最后，`truncate` 是一条带有 `EXISTS` 守卫的 `DELETE`： ```sql -- truncate DELETE FROM consensus WHERE shard = $1 AND sequence_number >= 0 AND sequence_number < $cut AND EXISTS ( SELECT * FROM consensus WHERE shard = $1 AND sequence_number >= $cut ); ``` 该守卫要求至少有一行在 `cut` 及以上得以保留，因此该语句永远不会删除头部，而删除一个区间的前缀仍然留下一个区间。`sequence_number >= 0` 子句保护序列号为 `-1` 的标记行，首次写入依赖于该标记行，详见下文。 ## 证明可线性化性 修改这样一个正确性至关重要的组件需要对可线性化保证具有极高的信心。因此，我们采用了形式化方法来获得对设计的额外信心：在 Lean 4 中对 `READ COMMITTED` 隔离级别下的系统进行建模，并证明任何执行都等价于一个可线性化的执行。 我们使用的技术称为精化（refinement），即关联两个系统的执行轨迹。在此背景下，系统由某个状态集和一组可在任意给定点执行的操作来描述。然后我们可以将系统的执行轨迹集合定义为从某些初始状态集出发的所有可能的操作序列。精化的目标是：对于系统 A 的所有执行轨迹，存在系统 B 的某个执行轨迹以某种方式与之等价。我们案例中的两个系统分别是一个理想化的抽象系统和 `READ COMMITTED` 隔离级别下的具体实现。由于不同的 shard 完全独立，且可线性化要求仅存在于单个 shard 的序列中，我们对两个系统都建模为管理单个 shard。 抽象系统通过尽可能简单来捕捉期望行为。其状态是一个从序列号到数据的映射，操作集合直接对应于共识实现所期望的四种操作，以原子方式执行。具体来说，`compare_and_set(seqno, state_diff)` 当且仅当 `seqno - 1` 是映射中的最大键、或者映射为空且 `seqno` 为 0 时成功；`truncate(cut)` 移除所有低于 `cut` 的键。 具体系统则捕捉了在 `READ COMMITTED` 下运行时产生的复杂情况。具体系统的状态是一张行表和一组在途语句。该系统的操作对应 PostgreSQL 可以采取的行动，例如通过拍摄快照开始一条语句、针对实时索引执行写入、检查行锁等。 主要的建模决策是：一条 CaS 语句不再是单个原子步骤，而是两个步骤——一个步骤针对快照评估 CTE，之后的一个步骤针对实时索引执行 `INSERT`。模型允许其他客户端在这两个步骤之间执行任意数量的操作。 ### 关联执行轨迹 关联执行轨迹的第一步是确定两个系统的一对状态何时等价。如上所述，具体系统的状态比理想化系统携带更多细节（如当前锁定的行），因此两个状态不可直接比较。我们通过使用抽象函数 `α` 来定义等价性，该函数可以将具体 PostgreSQL 状态的实例转换为理想化系统的实例。该函数回答的问题是："给定数据库的这个具体状态，shard 的抽象状态是什么？"在我们的案例中，函数 `α` 仅返回表的活跃行集合，忽略所有其他实现细节，如活跃锁集合或当前活跃事务集合。 有了这一点，我们现在需要证明一个前向模拟（forward simulation）：对于具体系统从任何可达状态可以执行的每一步，要么抽象系统可以执行一个具有相同结果的匹配步骤，要么具体步骤不改变任何可观察的状态，抽象系统保持不变。