超硬核解析Apache Hudi 的一致性模型（第一部分）
超硬核解析Apache Hudi 的一致性模型（第一部分）
Hudi 更复杂并不意味着 Iceberg 更好，只是需要更多的工作来内化设计。复杂性的一个关键原因是 Hudi 在核心规范中加入了更多功能。Iceberg 目前只是一种表格式，而 Hudi 是一种具有多种查询类型的完全成熟的托管表格式。如果精通 Delta Lake 内部结构，会发现 Hudi 的设计与 Delta Lake 的设计有许多相似之处。
分析范围
该分析不讨论性能，也不讨论 Hudi 如何支持不同的用例，例如批处理和流式处理。它只关注 Hudi 的一致性模型，特别强调多写入端场景。它目前也仅限于写入时复制 （COW） 表。我从 COW 开始，因为它比 Merge-On-Read 简单一些，因此是开始分析的更好地方。
- ? 第 1 部分 - 构建写入时复制表的逻辑模型。
- ? 第 2 部分 - 时间戳单调性。[1]
- ? 第 3 部分 - 对 TLA+ 规范进行建模检查。[2]
我可能会扩展分析以包括读时合并表以及同步和异步表服务（清理、压缩等）。
基础讨论
我们将探讨时间线和文件组的基础知识，以及写入端如何协同利用它们来执行读取和写入操作。这篇文章旨在构建用于执行读写的算法的逻辑心智模型。
图 1.编写器将有关数据文件的元数据写入时间线（预写日志）
时间线是一个预写日志，它包含有关已执行操作的元数据以及组成表的数据文件的位置。如果未从时间轴引用数据文件，则该文件不可读。Hudi 工作原理背后的基本思想是：
- ? 写入端写入数据文件（通常为 Parquet），并通过将文件位置写入时间线来提交这些文件。
- ? 读取端扫描时间线以查找现有数据文件的最新快照，然后读取这些文件以满足查询。
ACID事务保证
Hudi表示它支持ACID事务，该分析将对该声明进行测试。
看看时间线和文件组如何工作的基础知识，很明显原子性是轻而易举地实现的，就像Apache Iceberg一样。在 Hudi 中写入操作只能添加新文件，它们从不更新文件或删除文件。尽管写入两个位置，但 Hudi 写入操作是原子操作，因为对时间线的最终写入使文件组中的任何新文件可见。因为没有现有文件是突变的，而且单个文件的最终提交使所有新文件同时可见，所以我们得到了这种原子性。如果写入端中途失败，则不会对时间线进行最终写入，并且未提交的文件将保持不可见状态，以便稍后由表服务清理。这与 Apache Iceberg 的方法类似，从某种意义上说，如果 Iceberg 写入端在通过目录更新树根之前失败，那么更改是不可读的。
如果我们假设每个人都在云对象存储上使用这些表格式，那么持久性看起来也很安全。或其他类似的冗余高可用性存储系统。
这样一来，一致性和隔离性就成为想要理解和验证的 ACID 的剩余属性。在单写入端场景中，这是 Hudi 的主要使用模式，这两个也可能是微不足道的。但是想了解并发多写入端方案中的一致性和隔离性，这是本分析的其余部分所关注的。
主键
在 Apache Hudi 中每条记录都有一个主键，每个键都映射到单个分区和文件组（稍后会详细介绍）。Hudi 保证在大多数情况下主键行是唯一的，但是正如我们稍后将看到的，有几个边缘情况可能会导致重复。但是总的来说，记住 Hudi 主键设计是有帮助的，这使自己与 Apache Iceberg 和 Delta Lake 区分开来。在此分析中会将主键简单地称为键。
时间线
所有操作（包括表维护作业）都经过时间线。时间线不是仅追加日志，而是具有基于文件名的排序规则的文件目录。
每个操作都编码为一组“即时”对象，文件名格式为：[操作时间戳（以毫秒为单位）。[操作类型]。[操作状态]。此文件名构成即时的 ID。请注意，文档讨论了使用毫秒分辨率的时间戳，但也可以使用逻辑时间戳。
有许多操作类型，其中一些与表维护作业有关。在这篇文章中，我们将只看 Commit 操作类型，它用于对 COW 表执行插入、更新和删除操作。
有三种操作状态：
- ? Requested
- ? Inflight
- ? Completed
成功的提交操作将按上述顺序将每个操作状态作为单独的即时文件写入时间线。提交操作的“已完成”瞬间包含提交创建的文件的文件位置。读取端和写入端可以扫描时间线以查找已完成的提交时刻，以了解已提交的文件及其位置。时间线只是文件系统或对象存储中的一组文件，因此时间线的顺序基于文件名，使用以下优先级：
- ? 操作时间戳。
- ? 操作状态。
时间戳为 100 和 101 的两个成功的写入操作将创建按以下顺序排列的时间线（无论插入顺序如何）：
- 1. 100.commit.requested
- 2. 100.commit.inflight
- 3. 100.commit
- 4. 101.commit.requested
- 5. 101.commit.inflight
- 6. 101.commit
请注意即时文件名中省略了“已完成”操作状态。Hudi 规范指出，操作时间戳应单调增加。这在现实世界中意味着什么，起初我并不清楚。它可以解释为：
- ? 选项 1） 时间戳发行。当编写器获取时间戳时，它会获得一个（全局）单调递增的时间戳。
- ? 选项 2） 时间线插入。时间线的插入顺序基于单调递增的时间戳。换言之，插入顺序与写入端获取的时间戳匹配。例如，ts=1 的瞬间不会在 ts=2 的时刻之后添加到时间轴中。
我们还将假设这意味着两个写入端永远不会使用相同的时间戳 - 时间戳冲突。这就提出了一个问题，如果尝试每秒写入超过 1000 次（并且我们在一秒钟内用完了可用的毫秒），会发生什么。这不是当前适合任何这些表格式的工作负载。如果是这样，那么逻辑时间戳将是一个不错的选择。时间戳基本上是一个 int64，算法本身并不关心数字背后的含义。只有当需要基于挂钟时间的读取时，逻辑时间戳才会有问题。选项 1 可以通过多种方式实现，例如使用 OLTP 数据库、DynamoDB 甚至 Apache ZooKeeper 计数器。但是即使获得的时间戳是单调的，两个并发写入端也不一定以相同的顺序写入时间线。示例
- ? W1 从 ZK 获得 ts=100
- ? W2 从 ZK 获得 ts=101
- ? W2 放置 101.commit.requested
- ? W1 放置 100.commit.requested
- ? W2 放置 101.commit.inflight
- ? W2 放置 101.commit
- ? W1 放置 100.commit.inflight
- ? W1 放置 100.commit
请记住，时间线只是文件系统或对象存储上的一个目录（作为前缀），本身不能强加顺序。排序是通过在客户端读取时间线文件时进行排序来完成的。
图 2.时间轴排序是按时间戳排序的，而不是按插入顺序排序的
实现严格插入顺序（选项 2）的唯一方法是通过一种悲观锁定，该锁定将包装整组操作，包括获取时间戳。Hudi 不这样做，因此，我们必须得出结论，单调时间戳适用于发行时间，而不是写入时间。稍后我们将探讨单调时间戳与非单调时间戳的含义，以及锁定选项。虽然在此分析中讨论非单调时间戳和时间戳冲突的主题，但重要的是要记住，非单调时间戳违反了 Hudi v5 规范。目前我们还有更多的基本机制需要介绍。接下来，如何写入数据文件。
文件组
数据文件被组织成分区和文件组，其中任何给定的主键都映射到一个文件组。在这篇文章中，我主要忽略分区，以使事情尽可能简单，因为范围是一致性模型。
在 COW 表中，插入、更新或删除给定文件组的键将导致写入新版本的 Parquet 文件。写入端必须读取当前 Parquet 文件，合并新/更新/删除的行，然后将其写回为新文件。这些文件版本称为文件切片，其中时间戳充当一种版本号。为了找到要合并的正确文件切片，写入端会扫描时间轴以查找最近完成的瞬间的时间戳。此时间戳是合并提交时间戳，用于查找将合并以形成新文件切片的合并目标文件切片。合并目标是具有最高时间戳 <= 合并提交时间戳的已提交文件切片。提交的文件切片是在时间线中已完成的瞬间中引用的文件切片。完成内存中合并后，编写器会将新文件切片写入存储。
文件组由其文件 ID 标识，文件片由以下方式标识：
- ? 其文件组（文件 ID）
- ? 写入令牌（每次尝试写入文件时递增的计数器）
- ? 创建它的操作时间戳。
文件切片的文件名格式为：[file_id][write_token][timestamp].[file_extension] 现在将忽略文件写入重试，因此经常引用格式为 [file_id=N, ts=M] 的文件切片。
图 3.操作：将键 k1 更新为值 X。键 k1 映射到 FG1。编写器加载当前文件切片 [file_id=1， ts=3]，合并 k1 的新值并写入新的文件切片 [file_id=1， ts=4]
删除与 COW 表类似。
图 4.删除操作合并文件片 [file_id=1， ts=4] 并写入新文件片 [file_id=1， ts=5]
Hudi 提交操作从不覆盖文件组中的数据文件，它们只能添加新的文件。删除文件是表服务（如清理、压缩和聚簇）的工作。
时间线和文件组在一起
读取端和写入端使用时间线来了解给定时间戳下的哪些文件切片是相关的。
图 5.时间轴完成的瞬间指向不可变的数据文件
没有相应的已完成瞬间写入的文件切片不可读，并且不能用作 COW 操作的合并目标。
图 6.ts=150 处的操作在写入完成的瞬间之前失败，因此其文件切片仍然不可读
读取可以进行时间旅行，因为可以从与读取时间戳相对应的文件片中读取给定的键。
图 7.每个读取操作都在给定的时间戳上执行，这允许读取器时间旅行到较早的状态
写入路径的简单逻辑模型
“所有的模型都是错误的，有些是有用的。” 乔治·博克斯。
我们将尝试通过构建 Hudi 设计的简化模型来理解 Hudi 一致性和隔离性。写入端逻辑分解为多个步骤。这些步骤因选择的并发控制机制而异。并不总是需要并发控制，例如使用将表服务作业嵌入到编写器中的单个写入端设置。但是在多写入端方案中，需要并发控制。该模型由以下部分组成：
- ? 时间戳提供程序
- ? 锁提供程序
- ? 一个或多个写入端，每个写入端都有一些逻辑：
- ? 写入操作分为多个步骤。
- ? 并发控制（无、乐观、悲观）
- ? 存储
- ? Timeline 目录
- ? 文件组
- ? 指标
- ? 存储是否支持 PutIfAbsent。当存储支持 PutIfAbsent 时，写入端将在文件名已存在的任何时间线或文件组写入中止。否则，它将静默覆盖具有相同文件名/路径的现有文件。
- ? 操作基于 KV 对，具有更新插入或删除功能。每个键对应一个主键，值对应关联的非 PK 列值。
使用乐观并发控制 （OCC） 写入路径
我已使用 OCC 将逻辑写入路径建模为 9 个步骤。这可能看起来很多，但值得记住的是，Hudi 的主键设计增加了一些额外的工作。主键支持是该项目的目标之一。
图 8.简化模型的写入路径，具有乐观的并发控制
步骤：
- 1. 获取时间戳。写入端决定对主键执行操作并获取时间戳。
- 2. 立即追加请求。写入端将请求的即时写入时间线。
- 3. 键查找。写入端对键执行查找：
- ? 查看键是否存在（用于将更新插入标记为插入或更新）。
- ? 获取一个文件组，如果是插入文件，则分配一个文件组。将文件组分配给新键时，写入端会从固定池中选择一个，这是不确定的（在现实世界中，有许多文件组映射策略和实现）。
- 4. 读取合并目标文件切片。将合并目标文件切片读取到内存中（如果存在）
- ? 将时间线加载到内存中（首次加载时）。
- ? 扫描合并提交时间戳的时间线。这是最近完成的瞬间的操作时间戳。
- ? 扫描时间线，查找与目标文件 ID 接触且时间戳为 <= 合并提交时间戳的已完成时刻。如果该集为非空，则编写器将从该集中选择具有最高时间戳的瞬间作为合并目标文件切片。如果该集为空，请转到下一步。
- ? 检查合并目标文件切片的时间戳是否低于编写器自己的操作时间戳。可以找到要合并的文件切片，该文件片的时间戳高于编写器自己的操作时间戳（由于并发编写器），如果是这样，写入端现在应该中止。
- ? 将合并目标文件切片读取到内存中。
- 5. 写入文件切片。将操作与加载的文件切片（如果存在）合并，并写入为文件组的新文件切片。如果这是一个新文件组，则没有要合并的内容，只有新数据。
- 6. 获取表锁。
- 7. 更新索引。
- ? 如果这是插入，则必须将为此键分配的文件映射提交到文件映射索引。
- 8. 乐观并发控制检查
- 1. 加载时间线（第二次加载）
- 2. 扫描时间轴，查找与目标文件组接触的任何已完成时刻，其操作时间戳>合并目标文件切片时间戳（而不是合并提交时间戳）。
- 3. 如果存在这样的瞬间，则意味着另一个写入端提交了冲突的文件切片。因此，检查失败，写入器中止。如果不存在这样的即时，则检查通过。
- 9. 立即写入完成。将已完成的瞬间写入时间线，并包含写入的新文件切片的位置。
- ? 松开表锁
请注意，上面假设只有一个合并目标文件切片，因为此模型目前仅包含单个主键操作。如果并发控制不明确，我会在下面的并发控制部分更详细地介绍它。
使用悲观锁定的写入路径
与此方法的区别在于，在读取、合并任何文件切片，然后写入新文件切片之前，写入端会获取每个文件组的锁。然后以后就不需要检查了，就像 OCC 的情况一样。这些锁将一直保持到写入完成的瞬间或操作中止。
图 9.OCC 检查和表锁已替换为每文件组锁
悲观锁定并不常用，因为可能有数百、数千甚至数百万个文件组。大型操作需要获得大量锁，这并不理想。因此乐观并发控制是首选方法。
快速浏览 TLA+ Next 状态公式
TLA+ 规范的下一个状态公式反映了所描述的写入路径。
图 10.TLA+ 规范的下一个状态公式
上面告诉模型检查器，在每个步骤中，它应该非确定性地选择其中一个写入端，并在该时刻非确定性地执行一个可能的操作。例如如果写入端刚刚写入了 Requested 即时，则唯一可能发生的下一个操作是 KeyLookup 或 WriterFail。
并发控制
并发控制 （CC） 可确保多个操作不会相互踩踏，从而导致一致性问题。接触不相交的文件组集的两个操作不会相互干扰，因此它们的 CC 检查将通过。只有当两个操作共享一个或多个公共文件组时，才有可能发生冲突。
图 11.不相交的文件组提交没有冲突
这是 Hudi 的一个很好的属性，我认为它在每次写入都触及文件组的一小部分的多写入器场景中有所帮助。但是在每个写入端都执行大批量的情况下，我认为这种好处会有所减少，因为每个操作都可能涉及大量文件组。v5 规范提到了两种类型的并发控制：
- ? 乐观并发控制
- ? 悲观锁定
乐观并发控制 （OCC）
乐观并发检查的工作原理如下：
- 1. 两个写入器（W1 和 W2）必须将一些更改合并到文件组 1 中（w1 在 ts=100 时，w2 在 ts=101 时）。每个文件都标识要合并的文件组的现有文件片（合并目标）。在此示例中，两者都将文件切片 [file_id=1， ts=50] 标识为合并目标。
- 2. W1 乐观地写入文件片 [file_id=1， ts=100]
- 3. W2 乐观地写入文件切片 [file_id=1， ts=101]
- 4. 这两个文件切片都是未提交的，并且仍然不可读，因为它们在时间上没有相应的已完成瞬间。另请注意，如果两者都在不同的时间读取了时间线，则它们可能会识别不同的合并目标，从而导致它们对时间线的每个视图都不同。
- 5. W2 首先获取表锁。
- 6. W2 再次加载时间线。它通过扫描时间线以查找时间戳为 50 的已完成时刻，该时刻触及 file_id=1，>执行 CC 检查。它找不到任何内容，因此其 CC 检查成功并写入完成的瞬间。文件切片 [file_id=1， ts=101] 现已提交且可读。W1 释放表锁。
- 7. W1 获取表锁。W1 加载时间线。它通过扫描时间线以查找时间戳为 50 的已完成时刻，该时刻触及 file_id=1，>执行 CC 检查。它发现 ts=101，因此 CC 检查失败并中止，并释放表锁。
例如，在下面的场景中，w1 或 w2 现在可以获取表锁并成功完成操作。
图 11.w1 或 w2 现在可以获取表锁并成功完成操作
但是一旦一个写入器完成其操作，第二个写入器在执行其 OCC 检查时，将看到时间戳> 50 的已提交文件切片，因此它必须中止。
这就是我们在下图中看到的。W2 已经完成了。W1 接下来将进行 OCC 检查，它将扫描时间线以查找与 FG1 接触的已完成时刻，时间戳> 50。它将找到 101，因此中止。W1 现在应该清理未提交的文件切片 [file_id=1，ts=100]，否则表服务作业将在以后执行此操作。
图 12.ts=100 处的操作现在无法提交，因为它的 OCC 检查将失败
结果是文件切片只能按时间戳顺序提交。使用 OCC，无法提交时间戳低于现有已提交文件切片的文件切片。
悲观锁定
另一种策略是在开始读>-合并->写文件切片过程之前获取每个文件组的锁。这保证了在此过程中没有其他写入端可以对文件切片进行冲突更改。但正如我之前提到的，它可能涉及太多的锁，因此 OCC 通常是首选。
主键冲突检测
除了文件组冲突之外，还可以选择控制主键冲突。当不同写入端的并发插入导致将同一键分配给不同的文件组时，可能会发生主键冲突。在 TLA+ 规范中，编写器在将文件组分配给新键时会不确定地选择文件组。这可能会导致读取中出现重复项，如此处所述。在这个简单的模型中，主键冲突检查可确保在将映射添加到索引之前，其他文件组中不存在键到文件组的映射。
读取路径的简单逻辑模型
将逻辑读取路径建模为 3 个步骤。读取端首先从时间线中识别相关的文件切片，然后将这些文件切片读入内存，并将查询逻辑应用于这些行。在现实世界中，基于分区和文件统计信息（如元数据文件中的列最小/最大统计信息）的文件切片修剪将用于修剪实际必须读取的文件切片数。
请注意，此模型不包括时间线存档和文件清理，它假定时间线已完成。
图 13.此简化模型的读取路径
后续步骤
在查看模型检查结果之前，我想介绍一下时间戳冲突。v5 规范明确指出，时间戳应该是单调的，不这样做会违反规范。但是我想了解碰撞的影响，并了解在实践中发生此类碰撞的概率。在评估实现对规范的符合程度时，这些知识将很有用。这是第 2 部分的主题。