超硬核解析Apache Hudi 的一致性模型（第三部分）

在第 1 部分中，我们构建了一个逻辑模型，用于说明写入时复制表在 Apache Hudi 中的工作方式，并提出了许多关于并发控制类型、时间戳单调性等方面的一致性问题。在第 2 部分中，我们研究了时间戳冲突、它们的概率以及如何避免它们（并符合 Hudi 规范）。在第 3 部分中，我们将重点介绍模型检查 TLA+ 规范的结果，并回答这些问题。

此 TLA+ 规范仅对我到目前为止解释的逻辑进行建模：

• • 仅提交操作类型。
• • COW表
• • 使用固定大小的文件组池，并进行延迟分配
• • 没有表服务（清理、压缩、聚簇等）。
• • 只有单个主键操作。数据模型基于简单的 KV 对，而不是行，其中键表示主键，值表示非 PK 列值。

该规范具有以下参数：

• • Writer。例如：{w1， w2}。
• • 键。例如：{k1， k2}
• • 值。例如：{A， B}
• • 单调Ts
  • • True = 单调 ts 提供程序：例如 ZK。
  • • False = 非确定性本地时钟：发出介于 1 和单调值之间的值。
• • 并发控制
  • • 0 = 无
  • • 1 = 乐观
  • • 2 = 悲观
• • PutIfAbsentSupport
  • • True = 无法覆盖即时文件和文件切片文件（并且将导致写入器在尝试时中止）。
  • • False = 即时文件，文件切片文件可以静默覆盖。
• • 主键冲突检查
  • • True = 在索引更新时（提交之前）检测到会导致重复的主键冲突。
  • • False = 不执行主键冲突检测。
• • 盐
  • • 是。所有即时标识符和文件切片标识符都包含唯一的盐，以避免文件覆盖。
  • • 否

该规范有一个重要的不变量 ConsistentRead，它检查每个提交的 KV 对操作（插入/更新/删除）是否永远可读，其值与该提交相关联（在兼容的时间戳处）。将结果总结为两类：

• • 符合 V5 规范的配置
• • V5 规范不符合要求的配置

Hudi v5 规范符合配置

Hudi 规范明确指出时间戳必须是单调的，因此下面的所有配置都使用单调时间戳。对于多写入器方案，建议使用锁定，因此配置包括乐观和悲观的并发控制。最后避免重复的主键冲突检测是可选的，因此有带和不带它的配置。

Id     Locking     Timestamps   PK conflict check     Consistent    
  ---- ------------- ------------ ------------------- ---------------- 
   1   Optimistic    Monotonic    YES                 OK              
   2   Optimistic    Monotonic    NO                  Duplicate rows  
   3   Pessimistic   Monotonic    YES                 OK              
   4   Pessimistic   Monotonic    NO                  Duplicate rows

这些结果与 Hudi 文档中列出的保证相关：

ACID保证合规实施

正如我们在第 1 部分中介绍的那样，原子性和持久性是微不足道的。模型检查现在为我们提供了结果，以确定 Hudi 是否也支持一致性和隔离性。

当实现并启用可选的主键冲突检测时，将提供完整的 ACID 保证。但是，如果没有主键冲突检测，我们会遇到隔离失败，从而导致跨文件组的主键重复。仅当两个或多个并发操作在不同的文件组中插入相同的主键时，才会发生这种情况。对主键到文件组映射索引的最后一次写入获胜。在 OLTP 系统中，这种隔离问题可能只会导致写入/更新丢失，但在 Hudi 中，它会导致一致性问题，因为孤立的行仍然可以在错误的文件组中读取。在多写入器方案中使用主键冲突检查可解决问题。

Hudi v5 规范不符合要求的配置

以下配置不符合 Hudi v5 规范。但是存在一些可以使不符合要求的配置安全的对策，即 PutIfAbsent 存储支持以及在即时文件名和文件切片文件名中使用盐。为了完整起见，我们将查看安全和不安全的不符合项配置。

Id   PutIfAbsent   Salt       CC         Timestamps     PK check              Consistent             
 ---- ------------- ------ ------------- --------------- ---------- ---------------------------------- 
   5   Any           Any    No locking    Any             Any        Fail (lost write)                 
   6   NO            NO     Optimistic    Non-monotonic   YES        Fail (lost write - ts collision)  
   7   NO            NO     Pessimistic   Non-monotonic   YES        Fail (lost write - ts collision)  
   8   YES           NO     Optimistic    Non-monotonic   YES        OK                                
   9   YES           NO     Pessimistic   Non-monotonic   YES        OK                                
  10   NO            YES    Optimistic    Non-monotonic   YES        OK                                
  11   NO            YES    Pessimistic   Non-monotonic   YES        OK

数据丢失的唯一情况与不符合要求的配置有关。我们还看到如果使用支持 PutIfAbsent 的存储或使用盐，我们可以摆脱非单调时间戳。但是，不对多个写入器进行并发控制从来都不安全。让我们深入了解其中的一些场景，以了解为什么每种场景都是安全的或不安全的。

一些通过/失败方案

案例 1 - 无并发控制（不符合和不安全）

参数：

• • Writer={w1， w2}
• • 键={k1， k2}
• • 值={A， B}
• • 文件组计数 = 1
• • 单调Ts=真
• • ConcurrencyControl=0（无）
• • KeyConflictCheck=TRUE
• • PutIfAbsentSupported = any（设置为 TRUE 或 FALSE）

此配置可保证避免时间戳冲突，但会遇到写入丢失的情况。

图 1.问题在于，不同主键的并发操作映射到同一个文件组，并且两个写入器同时读取时间线，找不到任何现有的文件切片。这导致第二个操作没有合并第一个操作的内容，从而导致主键 k1 的写入丢失。

案例 2 - OCC，两个密钥，启用 PK 冲突检测（一致性和安全）

参数：

• • Writer={w1， w2}
• • 键={k1}
• • 值={A， B}
• • 文件组计数 = 1
• • 单调Ts=真
• • ConcurrencyControl=1（乐观）
• • KeyConflictCheck=TRUE
• • PutIfAbsentSupported = 任意

这与情况 1 相同，只是我们使用乐观并发控制。这一次按键操作被放在锁中，导致第二个操作无法通过其 OCC 检查。

图 2.w2 的并发控制检查扫描了时间线，发现了 w1 的完成瞬间，与 w2 的操作触及了同一个文件组。编写器 w2 的更新器没有合并目标，因此使用时间戳 0 进行检查。w1 的已完成时刻的时间戳高于 0，因此检测到冲突。

案例 3 - OCC，一个密钥，禁用 PK 冲突检测（符合 - 重复密钥）

参数

• • Writer={w1， w2}
• • 键={k1}
• • 值={A}
• • FileGroupCount=2
• • 单调Ts=真
• • ConcurrencyControl=1（乐观）
• • KeyConflictCheck=FALSE
• • PutIfAbsentSupported = 任意

如果没有 PK 冲突检测，不同写入器对同一密钥的两个并发插入可能会导致同一密钥被写入两个单独的文件组，尽管有 OCC。

图 3.如果使用了 PK 冲突检测，w2 将看到键 k1 现在存在映射，这与它自己的赋值冲突，并且它将无法通过检查并中止。因为它没有这样做，所以它覆盖了 w1 的映射，并孤立了文件组 1 中的行。

当主键的副本存在于与索引不对应的文件组中时，只要其文件切片仍从时间线引用，它仍然是可读的。有趣的是这样一个仍然可读的孤立行最终是如何被过滤掉的？据推测，将文件切片合并到新的文件切片中将保留该行。

案例 4 - OCC，非单调时间戳，PutIfAbsentSupport=false（不符合，不安全）

参数：

• • Writer={w1， w2}
• • 键={k1}
• • 值={A， B}
• • 文件组计数 = 1
• • 单调Ts=FALSE
• • ConcurrencyControl=1（乐观）
• • KeyConflictCheck=TRUE
• • PutIfAbsentSupported = FALSE

在 TLA+ 规范中，非单调时间戳是非确定性地发出的，其任何值介于 1 和单调值之间（包括会发生冲突的重复时间戳）。在进行暴力检查时，模型检查器实际上会探索每个操作的 1 和最低单调值之间的所有时间戳值。

图 4.两位写入端都选择了时间戳 ts=1。虽然 OCC 检查阻止了第二个操作的完成，但它并没有阻止第一个操作的文件切片被第二个操作的文件切片覆盖（因为文件名完全相同）。

案例 5 - OCC，非单调时间戳，PutIfAbsentSupport=true（不符合，安全）

参数：

• • Writer={w1， w2}
• • 键={k1}
• • 值={A， B}
• • 文件组计数 = 1
• • 单调Ts=FALSE
• • ConcurrencyControl=1（乐观）
• • KeyConflictCheck=TRUE
• • PutIfAbsentSupported = TRUE

对 1.commit.requested 的第二次写入失败，因为它已经存在，并且 w2 提前中止。

图 5.写入端 w2 在即时 1.commit.requested 的 put-if-absent 上中止。

在时间轴上，订单与插入订单不匹配

回到第 1 部分分析的开头，不确定 v5 Hudi 规范谈论单调时间戳是否意味着插入时间或发布时间。在经历了在 TLA+ 中对 Hudi 进行建模的过程后，从正确的角度来看，最重要的是时间戳不应该发生冲突，至少在使用不支持 PutIfAbsent 的存储服务时是这样。但是，如果两个写入器获得的时间戳在发出时是单调的，但操作是无序执行的，会发生什么情况？答案是只要选择了一种合规、安全的配置，一切都没问题。

示例：乱序，相同的主键 进行以下操作，注意插入顺序与ts顺序不匹配：

• • Op 1， k1=A， ts=1， 插入顺序=1
• • Op 2， k1=B， ts=2， 插入顺序=3
• • Op 3， k1=C， ts=3， 插入顺序=2

行为：

• • 操作 1 完成，用 k1=A 写入文件切片 [file_id=1， ts=1]。
• • Op 2 得到 ts=2。
• • Op 3 得到 ts=3。
• • Op 2 停顿了一会儿。
• • Op 3 继续进行，操作成功，写入包含 k1=C 的文件切片 [file_id=1， ts=3]。
• • Op 2 恢复。它扫描时间线并确定合并提交时间戳为 3，高于其自己的时间戳，因此它会提前中止。如果操作以不同的方式交错，Op 3 仍然首先完成，则 Op 2 的 OCC 检查将检测到冲突并中止。

如果两个重叠的操作不按时间戳顺序执行，则只有一个操作成功。使用 OCC 时，文件切片只能按时间戳顺序提交。从性能角度来看，这意味着以单调时间戳顺序执行的操作由于冲突较少，将具有更好的性能。

示例：乱序，不同的主键映射到不同的文件组

• • Op 1， k1=A， ts=1， fg=1， 插入顺序=1
• • Op 2， k2=X， ts=2， fg=2， 插入顺序=2
• • Op 3， k1=B， ts=3， fg=1， 插入顺序=4
• • Op 4， k2=Y， ts=4， fg=2， 插入顺序=3

首先，op 1 和 op 2 执行 upserts：

• • k1=A 在 ts=1 到文件切片 [file_id=1， ts=1]
• • k2=X at ts=2 到文件切片 [file_id=2， ts=2]

然后执行 op3 和 op 4。

• • Op 3 得到 ts=3。
• • Op 4 得到 ts=4。
• • Op 3 停顿了一会儿。
• • Op 4 继续并成功，写入包含 k2=Y 的文件切片 [file_id=2，ts=4]。
• • Op 1 恢复。它扫描时间线并确定合并提交时间戳为 2。它查找时间戳 <= 2 的文件切片合并目标 file_id=1。它找到 [file_id=1，ts=1] 和 k1=A。它写入一个新的文件片 [file_id=1， ts=3] 和 k1=B。它的并发控制检查通过，因为时间线中没有完成的瞬间，该时刻与 ts > 1 接触同一文件组。Op 1 成功。

如果两个不相交的操作不按顺序执行，则两个操作都成功。但是，跨键的一致性呢？如果客户端在 ts=3 或 ts=4 时一直重复检索所有键，结果是否一致？在 ts=3 时，读取器在一遍又一遍地重复其查询时会看到以下结果：

• • k1=空，k2=空
• • k1=A， k2=空
• • k1=A，k2=X
• • k1=B，k2=X

在 ts=4 时，读取器在一遍又一遍地重复其查询时会看到以下结果：

• • k1=空，k2=空
• • k1=A， k2=空
• • k1=A，k2=X
• • k1=A， k2=Y <- 在 ts=3 的 k1=B 之前看到 ts=4 的 k2=Y
• • k1=B，k2=Y

在 ts=4 的情况下，读者在 k1=B 之前看到 k2=Y。这没关系，因为这两个操作是重叠的，因此任何选择的实现这些操作的总顺序都是有效的（这就是我们在这里看到的）。多个客户端在同一时间戳上读取将看到相同的总订单。

结论

这种分析的范围有限，但到目前为止，模型检查 TLA+ 规范的结果与 Apache Hudi 文档并发控制的多写入器部分中讨论的保证相对应。符合 Hudi 规范的配置以及在多写入器方案中使用主键冲突检测时，都支持 ACID。在这个分析中非常关注多写入器场景。然而单写入器设置是更常见的情况。

关于多写入器方案，Apache Hudi v5 规范明确指出时间戳应该是单调的。根据我的分析，最重要的是时间戳不应该发生冲突，并且有多种选择可以做到这一点。如果使用支持 PutIfAbsent 的存储服务，则这是一个已解决的问题。否则如果使用的是 S3，则需要单调时间戳的来源。鉴于分布式锁定对于多写入器设置的正确性肯定是必需的，因此像 DynamoDB 或 ZooKeeper 之类的东西可以执行锁和单调计数器。使用这种系统进行时间戳和锁定对性能的影响应该是最小的，因为每秒的操作数应该比 Kafka 主题或 OLTP 数据库表低得多。加载时间线、读取和写入 Parquet 文件的成本应大大超过获取时间戳和获取/释放锁的成本。

Delta Lake 和 Apache Hudi 在这一点上非常相似，它们都采用预写日志 （WAL） 方法，并且都要求 WAL 条目使用单调标识符。Databricks 在使用 S3 时使用轻量级协调（可能是锁定）服务来确保不会发生 id 冲突（因为它缺乏 PutIfAbsent 支持）。Databricks 指出，由于湖仓一体表的写入速率相对较低，因此此协调服务的负载较低。

如果花更多时间分析，接下来的步骤将是建模读后合并 （MOR） 表和表服务（压缩、聚簇、清理等）。关于这些附加功能如何安全工作肯定有更多的数据一致性问题。到目前为止我的结果与 Hudi 文档中的保证相关，因此没有理由会发现问题。即便如此，进一步了解 Hudi 内部结构将是一个有用的练习。