# Procedure 框架的设计和应用

Source: https://greptime.cn/blogs/2024-05-14-procedure

单机数据库通常使用**预写日志（Write-Ahead Logging）来保证操作的原子性、一致性和持久性**。[分布式数据库](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%88%86%E5%B8%83%E5%BC%8F%E6%95%B0%E6%8D%AE%E5%BA%93&zhida_source=entity)需要协调多台机器上的状态，因此将面临更加复杂的情况。**在设计[分布式系统](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F&zhida_source=entity)时，我们通常会假设所有模块都是不可靠的，这种假设也被称为“容错假设”**。在分布式系统中，各个模块都可能会出现故障、延迟、通信失败等问题，因此必须针对这些不可靠性设计系统。

为了支持分布式数据库内部事务，GreptimeDB 设计实现了 Procedure 框架，以确保数据库中多个状态数据的修改的原子性、一致性和持久性。此前的文章[《GreptimeDB 如何提高多步操作的容错能力》](http://mp.weixin.qq.com/s?__biz=Mzg3MTgxMzczNg==&mid=2247484375&idx=1&sn=a1fadf51e167f22b0856731db69efa4d&chksm=cef984d0f98e0dc6f65d22bf1fc9764b4c379058f9d22a4e827391f18006c3f652b27f0afea8&scene=21#wechat_redirect)介绍了 Procedure 框架的设计动机和实现方案，并留下了部分未来工作的引子。本文即从前文的未来工作出发，分享近期 GreptimeDB 在系统内部的[分布式事务](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%88%86%E5%B8%83%E5%BC%8F%E4%BA%8B%E5%8A%A1&zhida_source=entity)上取得的进展。

值得一提的是，这样的内部事务框架在绝大部分的分布式系统当中都存在，例如 Apache HBase 也有同名的[Procedure V2 框架](https://github.com/apache/hbase/blob/master/src/main/asciidoc/_chapters/pv2.adoc)，Apache Accumulo 实现了 [FATE (Fault-Tolerant Executor)](https://accumulo.apache.org/docs/2.x/administration/fate) 分布式多步操作框架。甚至，面向业务应用程序，还有秉持同样[设计理念](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E8%AE%BE%E8%AE%A1%E7%90%86%E5%BF%B5&zhida_source=entity)的 [Temporal](https://temporal.io/) 持久化执行框架，它支撑起了一家估值 15 亿美元的明星公司。应该说，本文分享的技术对有志于投身数据处理领域的开发者是很有帮助的 :D

## 01 可回滚 Procedure

在 [PR#3625](https://github.com/GreptimeTeam/greptimedb/pull/3625) 中，我们为 Procedure 引入了回滚机制，允许 Procedure 在遇到不可重试错误时进行回滚。

我们以支持回滚的 Drop Table DDL （[PR#3692](https://github.com/GreptimeTeam/greptimedb/pull/3692)）为例，起初 Drop Table DDL 只包含以下四个步骤：

1. 准备；

2. 物理删除元数据；

3. 通知 Datanode 删除 Region；

4. 删除缓存。

这个流程里，如果执行到步骤 3 时发生不可重试的错误，整个 Procedure 是无法回滚的，因为元数据已经被删除。此时，失去元数据的 Region 将成为数据碎片，导致数据泄露或其他更严重的问题。

我们通过重构 Drop Table Procedure 的步骤来支持回滚，以保证这一操作失败时的原子性。支持回滚的 Drop Table Procedure 包括以下五个步骤：

1. 准备；

2. [逻辑删除](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E9%80%BB%E8%BE%91%E5%88%A0%E9%99%A4&zhida_source=entity)元数据；

3. 通知 Datanode 删除 Region；

4. 删除缓存；

5. 物理删除元数据。

图 1 中黄色路径即为回滚步骤。如果步骤 3 发生不可重试的错误，可以沿着黄色路径回滚，保证[数据完整性](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E6%95%B0%E6%8D%AE%E5%AE%8C%E6%95%B4%E6%80%A7&zhida_source=entity)。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image1.png" alt="（图 1：Drop Table Procedure 状态机示意图）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 1：Drop Table Procedure 状态机示意图）</figcaption>
</figure>


## 02 Procedure中的[细粒度锁](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E7%BB%86%E7%B2%92%E5%BA%A6%E9%94%81&zhida_source=entity)

### 为什么要引入细粒度锁

在引入细粒度锁（[PR#3061](https://github.com/GreptimeTeam/greptimedb/pull/3061)）之前，我们在 Procedure 内只支持用[互斥锁](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E4%BA%92%E6%96%A5%E9%94%81&zhida_source=entity)锁定以数据表（Table）为单位的资源，这导致了以下几个问题：

1. Drop Database 需要锁定所有数据表资源；

2. 在执行 Drop Database 时，依然可以在正在被删除数据库下创建数据表；

3. 对于操作比数据表单位小的资源时，Procedure 只能串行执行。

例如，Region Migration 不能并行执行，因为需要首先获取对应数据表资源的锁，即使 Region Migration 逻辑上应该支持 Region 级别的并行，无论这些 Region 是否属于同一个表。

*聪明的同学可能要抢答了：这题我会，是不是用了本科生数据库必考题层级锁（Hierarchical Lock）？*

如你所想，Procedure 细粒度锁的实现很大程度上启发自层级锁的设计理念。在设计之初，我们就调研了层级锁的实现，翻出了这篇发表于 1975 年的的论文（[Granularity of Locks and Degrees of Consistency in a Shared Data Base](https://dl.acm.org/doi/pdf/10.1145/1282480.1282513)）。

这篇关于 Hierarchical Lock 的论文可说是数据库领域的里程碑之作，其作者来自 IBM 的 System R 团队。他们同时期发表了一系列数据库主题的文章，如The Notions of Consistency and Predicate Locks in a Database System\[8\]等。这些文章在过去十年中仍然被大量引用。另外值得一提的是，Predicate Lock 实际上并没有被时代淘汰，Rust Moka 库就有其变种的应用。这些工作奠定了今天[关系型数据库](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%85%B3%E7%B3%BB%E5%9E%8B%E6%95%B0%E6%8D%AE%E5%BA%93&zhida_source=entity)中许多概念的基础，例如事务、一致性等。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image2.png" alt="（图 2：Hierarchical Lock 的兼容性）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 2：Hierarchical Lock 的兼容性）</figcaption>
</figure>

在原论文中 Hierarchical Locks 的核心设计目标，是实现一种隐式锁定整颗子树的方式。**除了隐式锁定子树外，还有一种显式锁定子树的方式，即从叶节点到根节点逐级获取锁。**

### GreptimeDB 的细粒度锁设计

**从显式锁定子树的方式启发**，在设计细粒度锁时，我们决定将这两种锁定子树的方法相结合。这意味着我们**允许隐式锁定整颗子树的同时，也支持显式锁定子树**。通过这种方式，我们能够更灵活地管理并发执行 Procedure，从而提高数据库的性能和效率。

此外，在原论文中，Hierarchical Locks 提供了多种锁定模式，以提供更灵活的[并发控制](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%B9%B6%E5%8F%91%E6%8E%A7%E5%88%B6&zhida_source=entity)。然而在我们的场景中并不需要这些特性。我们抛弃这些复杂的模式，只保留共享模式和[独占模式](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E7%8B%AC%E5%8D%A0%E6%A8%A1%E5%BC%8F&zhida_source=entity)以简化锁管理。

## 03 带细粒度锁的 Procedure 工作流程

举几个例子说明细 Procedure 中的颗粒度锁是如何帮助我们解决上述问题的：

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image3.png" alt="（图 3：资源层级关系示意图）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 3：资源层级关系示意图）</figcaption>
</figure>

### DDL Procedure

对于变更数据库的 Procedure，以执行删除 `greptime.foo` 数据库的操作为例。首先，我们需要获取名为 `greptime.foo` 的数据库资源的独占锁。这个操作事实上允许我们隐式锁住 `greptime.foo` 数据库之下的整棵子树的资源，从而解决以下两个问题：

1\. 我们不需要显式获取整颗子树，即可隐式锁定所有该数据库（Database）下的资源。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image4.png" alt="（图 4：隐式锁定 “greptime.foo” Database 之下整棵子树资源）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 4：隐式锁定 “greptime.foo” Database 之下整棵子树资源）</figcaption>
</figure>


2\. 在执行创建和删除数据库的 Procedure 时，对应数据库下的数据表的 DDL Procedure 以及 Region Migration Procedure （[ISSUE#2700](https://github.com/GreptimeTeam/greptimedb/issues/2700)）并不会执行，因为无法获取greptime.foo数据库资源的[共享锁](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E5%85%B1%E4%BA%AB%E9%94%81&zhida_source=entity)。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image5.png" alt="（图 5：Procedure 间的互斥关系示意图）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 5：Procedure 间的互斥关系示意图）</figcaption>
</figure>


### Region Migration Procedure

对于 Region Migration Procedure 而言，我们需要显示地锁定整颗子树，即从叶节点到根节点逐级获取锁。从而满足我们的需求：

1. 同数据表不同 Region 的 Region Migration Procedure 可以并行执行。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image6.png" alt="（图 6：同数据表不同 Region 的 Region 迁移并行执行）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 6：同数据表不同 Region 的 Region 迁移并行执行）</figcaption>
</figure>


2\. 在执行 Region Migration Procedure 时，同数据表的 DDL Procedure 并不会执行，因为无法获取 `greptime.foo.baz` 数据表资源的独占锁。

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image7.png" alt="（图 7：Procedure 间的互斥关系示意图）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 7：Procedure 间的互斥关系示意图）</figcaption>
</figure>

### 04 实现 Drop Database

在支持了细粒度锁后，我们得以更加优雅得实现 Drop Database Procedure（[ISSUE#3516](https://github.com/GreptimeTeam/greptimedb/issues/3516)）。

Drop Database Procedure 状态机如下图所示：

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image8.png" alt="（图 8：Drop Database Procedure 状态机示意图）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 8：Drop Database Procedure 状态机示意图）</figcaption>
</figure>

简单来说，Drop Database Procedure 可以分为以下几个步骤：

1. 获取被删除 Database 的独占锁；

2. Cursor 负责加载下一张需要删除数据表的元数据；

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image9.png" alt="（图 9：步骤 2）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 9：步骤 2）</figcaption>
</figure>

3. Executor 负责删除对应数据表的元信息，删除对应 Regions， 清除缓存；

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image10.png" alt="（图 10：步骤 3）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 10：步骤 3）</figcaption>
</figure>

4. 以此往复，直至 Database 下所有数据表都被删除；

<figure>
<img src="/zh/blogs/2024-05-14-procedure/image11.png" alt="（图 11：步骤 4）" style="width: 40%; margin: 0 auto"/>
<figcaption>（图 11：步骤 4）</figcaption>
</figure>

5. 最后删除数据库的[元信息](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=2&q=%E5%85%83%E4%BF%A1%E6%81%AF&zhida_source=entity)，清除缓存。

## 05 Procedure 后续工作

目前，GreptimeDB 的 Procedure 框架已经支持回滚和细粒度锁。应该说，所有 GreptimeDB Procedure 需要的基础功能都已经实现了。未来，在 Procedure 框架的使用和优化上，我们会着重为 Procedure 增加更多的[模糊测试](https://zhida.zhihu.com/search?content_id=243177636&content_type=Article&match_order=1&q=%E6%A8%A1%E7%B3%8A%E6%B5%8B%E8%AF%95&zhida_source=entity)以及混乱测试。

此外，目前还有许多 DDL 没有实现。它们的实现将进一步深入地使用 Procedure 框架，这可能会带来更多新的需求。

最近涉及到的 DDL 支持工作包括：

- 支持更改表中列的类型（[PR#3796](https://github.com/GreptimeTeam/greptimedb/pull/3796)）
- 支持创建视图（VIEW）（[PR#3807](https://github.com/GreptimeTeam/greptimedb/pull/3807)）

## 关于 Greptime

[Greptime 格睿科技](https://greptime.cn/)专注于为可观测、物联网及车联网等领域提供实时、高效的数据存储和分析服务，帮助客户挖掘数据的深层价值。目前基于云原生的时序数据库 [GreptimeDB](https://github.com/GreptimeTeam/greptimedb) 已经衍生出多款适合不同用户的解决方案，更多信息或 demo 展示请联系下方小助手（微信号：greptime）。

欢迎对开源感兴趣的朋友们参与贡献和讨论，从带有 good first issue 标签的 issue 开始你的开源之旅吧～期待在开源社群里遇见你！添加小助手微信即可加入“技术交流群”与志同道合的朋友们面对面交流哦~

Star us on GitHub Now: https://github.com/GreptimeTeam/greptimedb

官网：https://greptime.cn/

文档：https://docs.greptime.cn/

Twitter: https://twitter.com/Greptime

Slack: https://greptime.com/slack

LinkedIn: https://www.linkedin.com/company/greptime/
