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

• • 通过查看时间戳冲突的影响，了解为什么 Hudi 规范指示使用单调时间戳。
• • 在写入端使用其本地时钟作为时间戳源的多写入端方案中发生冲突的概率。
• • 避免碰撞的各种选项。

同样 v5 Hudi 规范说，确保时间戳是单调的实现是实现者的责任。非单调时间戳违反了规范。即便如此，也需要了解多个写入端之间时间戳冲突的影响。

时间戳冲突的影响

当两个单独的操作使用相同的时间戳时，会发生时间戳冲突。如果不受控制的时间戳冲突，则会导致时间线和文件组文件被覆盖。如果文件/对象存储支持 PutIfAbsent 操作，则在存储层完全防止时间戳冲突。S3 不支持 PutIfAbsent（在撰写本文时），因此必须通过获取非冲突时间戳来避免冲突。

以下是两个未经检查的碰撞造成麻烦的例子。

覆盖时间线中已完成的瞬间

操作 1 成功完成，但操作 2 使用相同的时间戳。然后它继续写入映射到不同文件组的不同键，并通过覆盖操作 1 的已完成瞬间来完成，该瞬间现在指向文件组 2 中的文件切片。操作 1 的原始提交文件片段现在不可读，并留下一个孤立文件，稍后由表服务清理。

覆盖文件切片（乐观锁定）

在此方案中，操作 2 再次使用与操作 1 相同的时间戳。这一次，它写入与操作 1 相同的文件组。它会覆盖文件切片，但随后无法通过并发控制检查。虽然它从未写入完成的即时，但我们仍然存在一致性冲突。操作 1 的已完成瞬间现在指向失败操作 2 的未提交数据。

PutIfAbsent 通过无法写入已存在的具有相同文件名的文件来避免这些问题。

注意！PutIfAbsent 防护栏中的一个潜在间隙与文件切片有关。文件切片的文件名包括 Write Token（到目前为止，我已经省略了它），并构成其唯一标识的一部分。Write Token 是一个计数器，它构成文件名的一部分，在编写器每次尝试写入文件时递增。每次重试都会递增写入令牌。如果第一次写入由于连接失败而失败，则写入器将尝试使用 WriteToken=2 进行第二次写入。即使同时另一个写入器写入了具有相同原始文件名（写入令牌为 1）的文件，第二次写入也可能成功。

时间戳冲突的概率

当写入端使用其本地操作系统时钟作为时间戳源（这违反了 v5 Hudi 规范）时，在多写入端场景中发生时间戳冲突的可能性有多大？我们可以从生日悖论中寻找直觉。

在概率论中，生日问题要求在一组随机选择的n个人中，至少有两个人会分享一个生日。生日悖论指的是一个违反直觉的事实，即只需要23个人就可以超过50%的概率

生日悖论是一个真实的悖论：乍一看似乎是错误的，但实际上是真实的。虽然只需要 23 个人就可以达到 50% 的共享生日概率，这似乎令人惊讶，但考虑到将在每对可能的个体之间进行生日比较，这个结果变得更加直观。有 23 个人，有 23 × 22/2 = 253 对需要考虑，远远超过一年中天数的一半。

同样的原则也适用于使用本地时钟作为时间戳源的多个写入器之间的时间戳冲突。为了理解概率，简单编写了一个简单的 Python 脚本。对于每个写入端，它会根据请求的写入间隔（具有少量抖动）在一段时间内生成一系列时间戳。接下来它对所有写入端序列进行集合并集，以计算碰撞次数。运行了以下实验，每个组合运行了 1000 次，计算了平均、最小和最大碰撞，以及 1 次或多次碰撞的概率：

1. 1. 2-20 个写入器，1 分钟的写入间隔，持续 24 小时。
2. 2. 2-20 个写入器，5 分钟的写入间隔，持续 24 小时。
3. 3. 5 个写入器，1-20 分钟的写入间隔，持续 24 小时。
4. 4. 5 位写入者，1-20 分钟的写入间隔，为期 7 天。

请注意没有一个图表显示完全平滑的曲线，因为结果基于模拟运行 1000 次（足以显示趋势，但不足以创建完美的曲线）。

2-20 个写入端，1 分钟的写入间隔，持续 24 小时

2-20 个写入端，5 分钟的写入间隔，持续 24 小时

5 个写入端，1-20 分钟的写入间隔，持续 24 小时

5 位写入端，1-20 分钟的写入间隔，持续 7 天

从这些图表中可以清楚地看出，时间戳冲突比最初预期的更常见，因此避免碰撞至关重要。

避免碰撞

在多写入端方案中，有许多方法可以避免时间戳冲突。我们并不缺乏选择。

1. 1. 使用支持 PutIfAbsent 的存储系统（在撰写本文时 S3 不提供此功能）。
2. 2. 使用单调时间戳源，例如 OLTP 数据库、DynamoDB 甚至 Apache ZooKeeper 计数器。有许多数据库能够生成单调数。
3. 3. 在所有即时和文件切片文件名中使用 salt，例如 UUID（Delta Lake 采用此技术以避免检查点冲突）。

Hudi PMC 成员告诉我salt的想法，我立即在 TLA+ 规范中添加了盐支持。当两个瞬间或文件切片在时间戳上发生冲突时，它们会被识别并按salt进行排序。如果使用单个写入端，则只有在使用本地非单调时钟时才会发生冲突，并且有两个快速连续发生的串行操作，并且时钟在第二个操作导致冲突之前倒退。使用 Linux 中的单调时钟可以避免这种情况。

与Delta Lake的相似之处

Delta Lake 日志记录 ID 与 Hudi 时间戳一样，必须是单调的。Delta Lake VLDB 白皮书 Delta Lake：High-Performance ACID Table Storage over Cloud Object Stores 讨论了避免日志 ID 冲突的必要性。

Amazon S3 没有原子“不putIfAbsent”或”rename“操作。在 Databricks 服务部署中使用单独的轻型协调服务来确保只有一个客户端可以使用每个日志 ID 添加记录。此服务仅用于日志写入（不是读取，也不是数据操作），因此其负载较低。

此轻量级协调服务使用锁（或一些等效的锁来生成关键部分）来确保两个写入端不能同时执行乐观并发检查，并且都使用相同的记录 ID 将提交记录写入日志。在其他存储系统（例如 Azure Data Lake Storage）上，不需要此类服务，就像 Apache Hudi 一样。

后续步骤

到目前为止我们已经回顾了 Apache Hudi COW 表的简化逻辑模型，并理解了为什么时间戳需要单调。TLA+ 规范已准备就绪。模型检查将告诉我们关于 Hudi 声称的 ACID 保证的什么？此外，它是否会回答第一部分中关于单调发行的时间戳的问题，其操作执行顺序不正常？第三部分将介绍这些内容，我们将查看模型检查 TLA+ 规范的结果。