Procedure 框架的设计和应用
单机数据库通常使用预写日志（Write-Ahead Logging）来保证操作的原子性、一致性和持久性。分布式数据库需要协调多台机器上的状态，因此将面临更加复杂的情况。在设计分布式系统时，我们通常会假设所有模块都是不可靠的，这种假设也被称为“容错假设”。在分布式系统中，各个模块都可能会出现故障、延迟、通信失败等问题，因此必须针对这些不可靠性设计系统。
为了支持分布式数据库内部事务，GreptimeDB 设计实现了 Procedure 框架，以确保数据库中多个状态数据的修改的原子性、一致性和持久性。此前的文章《GreptimeDB 如何提高多步操作的容错能力》介绍了 Procedure 框架的设计动机和实现方案，并留下了部分未来工作的引子。本文即从前文的未来工作出发，分享近期 GreptimeDB 在系统内部的分布式事务上取得的进展。
值得一提的是，这样的内部事务框架在绝大部分的分布式系统当中都存在，例如 Apache HBase 也有同名的Procedure V2 框架，Apache Accumulo 实现了 FATE (Fault-Tolerant Executor) 分布式多步操作框架。甚至，面向业务应用程序，还有秉持同样设计理念的 Temporal 持久化执行框架，它支撑起了一家估值 15 亿美元的明星公司。应该说，本文分享的技术对有志于投身数据处理领域的开发者是很有帮助的 :D
01 可回滚 Procedure
在 PR#3625 中，我们为 Procedure 引入了回滚机制，允许 Procedure 在遇到不可重试错误时进行回滚。
我们以支持回滚的 Drop Table DDL （PR#3692）为例，起初 Drop Table DDL 只包含以下四个步骤：
准备；
物理删除元数据；
通知 Datanode 删除 Region；
删除缓存。
这个流程里，如果执行到步骤 3 时发生不可重试的错误，整个 Procedure 是无法回滚的，因为元数据已经被删除。此时，失去元数据的 Region 将成为数据碎片，导致数据泄露或其他更严重的问题。
我们通过重构 Drop Table Procedure 的步骤来支持回滚，以保证这一操作失败时的原子性。支持回滚的 Drop Table Procedure 包括以下五个步骤：
准备；
逻辑删除元数据；
通知 Datanode 删除 Region；
删除缓存；
物理删除元数据。
图 1 中黄色路径即为回滚步骤。如果步骤 3 发生不可重试的错误，可以沿着黄色路径回滚，保证数据完整性。
02 Procedure 中的细粒度锁
为什么要引入细粒度锁
在引入细粒度锁（PR#3061）之前，我们在 Procedure 内只支持用互斥锁锁定以数据表（Table）为单位的资源，这导致了以下几个问题：
Drop Database 需要锁定所有数据表资源；
在执行 Drop Database 时，依然可以在正在被删除数据库下创建数据表；
对于操作比数据表单位小的资源时，Procedure 只能串行执行。
例如，Region Migration 不能并行执行，因为需要首先获取对应数据表资源的锁，即使 Region Migration 逻辑上应该支持 Region 级别的并行，无论这些 Region 是否属于同一个表。
聪明的同学可能要抢答了：这题我会，是不是用了本科生数据库必考题层级锁（Hierarchical Lock）？
如你所想，Procedure 细粒度锁的实现很大程度上启发自层级锁的设计理念。在设计之初，我们就调研了层级锁的实现，翻出了这篇发表于 1975 年的的论文（Granularity of Locks and Degrees of Consistency in a Shared Data Base）。
这篇关于 Hierarchical Lock 的论文可说是数据库领域的里程碑之作，其作者来自 IBM 的 System R 团队。他们同时期发表了一系列数据库主题的文章，如 The Notions of Consistency and Predicate Locks in a Database System[8]等。这些文章在过去十年中仍然被大量引用。另外值得一提的是，Predicate Lock 实际上并没有被时代淘汰，Rust Moka 库就有其变种的应用。这些工作奠定了今天关系型数据库中许多概念的基础，例如事务、一致性等。
在原论文中 Hierarchical Locks 的核心设计目标，是实现一种隐式锁定整颗子树的方式。除了隐式锁定子树外，还有一种显式锁定子树的方式，即从叶节点到根节点逐级获取锁。
GreptimeDB 的细粒度锁设计
从显式锁定子树的方式启发，在设计细粒度锁时，我们决定将这两种锁定子树的方法相结合。这意味着我们允许隐式锁定整颗子树的同时，也支持显式锁定子树。通过这种方式，我们能够更灵活地管理并发执行 Procedure，从而提高数据库的性能和效率。
此外，在原论文中，Hierarchical Locks 提供了多种锁定模式，以提供更灵活的并发控制。然而在我们的场景中并不需要这些特性。我们抛弃这些复杂的模式，只保留共享模式和独占模式以简化锁管理。
03 带细粒度锁的 Procedure 工作流程
举几个例子说明细 Procedure 中的颗粒度锁是如何帮助我们解决上述问题的：
DDL Procedure
对于变更数据库的 Procedure，以执行删除 greptime.foo 数据库的操作为例。首先，我们需要获取名为 greptime.foo 的数据库资源的独占锁。这个操作事实上允许我们隐式锁住 greptime.foo 数据库之下的整棵子树的资源，从而解决以下两个问题：
1. 我们不需要显式获取整颗子树，即可隐式锁定所有该数据库（Database）下的资源。
2. 在执行创建和删除数据库的 Procedure 时，对应数据库下的数据表的 DDL Procedure 以及 Region Migration Procedure （ISSUE#2700）并不会执行，因为无法获取 greptime.foo 数据库资源的共享锁。
Region Migration Procedure
对于 Region Migration Procedure 而言，我们需要显示地锁定整颗子树，即从叶节点到根节点逐级获取锁。从而满足我们的需求：
同数据表不同 Region 的 Region Migration Procedure 可以并行执行。
2. 在执行 Region Migration Procedure 时，同数据表的 DDL Procedure 并不会执行，因为无法获取 greptime.foo.baz 数据表资源的独占锁。
04 实现 Drop Database
在支持了细粒度锁后，我们得以更加优雅得实现 Drop Database Procedure（ISSUE#3516）。
Drop Database Procedure 状态机如下图所示：
简单来说，Drop Database Procedure 可以分为以下几个步骤：
获取被删除 Database 的独占锁；
Cursor 负责加载下一张需要删除数据表的元数据；
Executor 负责删除对应数据表的元信息，删除对应 Regions， 清除缓存；
以此往复，直至 Database 下所有数据表都被删除；
最后删除数据库的元信息，清除缓存。
05 Procedure 后续工作
目前，GreptimeDB 的 Procedure 框架已经支持回滚和细粒度锁。应该说，所有 GreptimeDB Procedure 需要的基础功能都已经实现了。未来，在 Procedure 框架的使用和优化上，我们会着重为 Procedure 增加更多的模糊测试以及混乱测试。
此外，目前还有许多 DDL 没有实现。它们的实现将进一步深入地使用 Procedure 框架，这可能会带来更多新的需求。
最近涉及到的 DDL 支持工作包括：
关于 Greptime
Greptime 格睿科技专注于为可观测、物联网及车联网等领域提供实时、高效的数据存储和分析服务，帮助客户挖掘数据的深层价值。目前基于云原生的时序数据库 GreptimeDB 已经衍生出多款适合不同用户的解决方案，更多信息或 demo 展示请联系下方小助手（微信号：greptime）。
欢迎对开源感兴趣的朋友们参与贡献和讨论，从带有 good first issue 标签的 issue 开始你的开源之旅吧～期待在开源社群里遇见你！添加小助手微信即可加入“技术交流群”与志同道合的朋友们面对面交流哦~
Star us on GitHub Now: https://github.com/GreptimeTeam/greptimedb
Twitter: https://twitter.com/Greptime
Slack: https://greptime.com/slack
专注于 Infra 技术分享 2022-09-23 加入
分布式、高性能、存储计算分离的开源云原生时序数据库
评论