Online DDL 是分布式数据库领域的重要基础，可以说与事务模型、共识协议一样重要。最近重读F1的Online Schema Change这篇 paper [1]，也希望能用通俗易懂的方式帮助更多人理解它。因此有了这篇短文，实际上是个人的 Paper 阅读笔记。

理解这篇文章的原理的关键点： 每个状态能正确运行的前提条件是什么；每个状态的DML能保证什么。然后就能理解状态之间的兼容性：所谓不兼容，就是违背了某个状态的前提条件。

这里没有覆盖文章中所有章节，着重在于说明上述的关键点。如果想知道所有细节，还需要读原文。

Ch1 大致介绍了下问题的背景以及状态间兼容性的概念；Ch2 以添加一个二级索引为例，介绍 F1 的 Online DDL 的一些关键点和流程；Ch3 简述了删除一个二级索引的过程；Ch4 简略描述了下 Optional 对象的操作简化。

1. 解决什么问题

Online DDL这篇文章，针对分布式数据库中，如何在不破坏数据完整性、不禁止DML的前提下，低开销地完成DDL 的问题，提出了一种软着陆方法。这个方法不涉及任何大范围锁，能保证数据的完整性，且对应用性能影响小，可以认为是在飞行过程中完成了自身的软变身。

这篇文章对应的是 F1 的模型，即系统由分布式KV存储 +多个无状态的 Server 组成，这个模型也是现在分布式数据库的主流架构。Server是指SQL运算节点：可动态伸缩、状态无需持久化，Server之间独立，也没有强的成员状态管理。

F1 采取的 K/V 模型简述如下：

• 表必须有主键；
• 每行数据，至少有一个以主键为Key的KV (这里称为Row KV)。假设某行主键为x，我们用​ 表示这行的Row KV；
• 如果表有 Index E，那么每一行都会有一个 Index E 对应的KV。相应地，E中对应主键为x的IndexKV，这里记为​： ；
• 如果有N个二级索引，那么每行有N个IndexKV。

1.1 Schema变更：同步完成从 0 的 1切换？

举个例子，考虑一个已经存在的表，如果要给这个表加一个二级索引。那么直观方法是：

• 原子地完成所有既存数据的 Index的补全；
• 原子地让所有 Server 把 Schema 切换到新版本。

上述过程实际上要禁止 DML，让所有的 Server 都暂停服务。但是对于 Google F1 这种大规模分布式数据库，基本没法做到。因为：

• 系统有很多无状态的Server(SQL计算节点)，它们获取 Schema 元数据的时机不是同步的。难以让所有的Server在同一时刻做状态变更，系统甚至不能保证某个时刻有多少个Server在运行。
• 补全既存数据的Index，没法瞬间完成。禁止DML对用户影响大，而 F1 背后的服务需要 24小时随时在线。

1.2 异步完成从 "0" 到 "1" 的切换的问题

这里说的异步，是指多个 Server 间异步地做状态变更。假设一个表之前没有二级索引，现在新添加新的索引 E。Index E 创建前后的状态，可以理解为"0"和"1"两个状态。

考虑两个 Server S0 和 S1。S0 的 Schema 在 “0” 状态，S1 的Schema在"1"状态。假设按照下面步骤执行操作：

1. S1 添加一行数据，主键为y，由于它按照 Index 已经创建完成的Schema （状态"1"）执行，生成了对应的两个 KV ： ​ 以及 ​；
2. S0 执行删除 y 的操作，由于它看到的 Schema 处于"0"状态，只会删除 ​，不会删除 ​​。

那么上面的 ​​​ 就成了一个孤儿 Index，破坏了数据的完整性。

1.3 状态间的兼容性

上面的状态 "0" 和 "1" 实际上不兼容的，所以它们不能共存。所谓状态间兼容，是指两个或者多个 Server 分别按照Schema对象的不同状态并发执行DML，也不会破坏数据一致性。

以索引为例，可能破坏数据一致性的异象包括：

• 孤儿索引: ​ ​ ​ 存在，对应的​却不存在，IndexKV成了垃圾数据；
• 索引不完整：​存在，但是没有对应的​ ​ ​。导致用户查不到数据。

不同的Schema 对象，有不同的异象，这里不一一列举。

1.4 OnlineDDL一文大致思路

文章的思路：把从“0”到“1”的突变，替换为一系列相互兼容的小状态变化，实现软着陆。

• 任意两个相邻的小状态(版本)都是兼容的；
• 只有一个Server负责DDL的执行，其他Server只是定期刷新状态(拉取 Schema)即可；
• 任意两个Server，虽然不能在同一时间点切换Schema 版本，但是却可以保证它们的误差范围。比如，任意一个Server使用的 Schema 版本，与最新版的延迟都不超过一个 Lease 时间(Lease一般为分钟级)。
• 只要每次 Schema 版本变化间隔不小于一个 Lease 时间，就可以保证任意两个Server的Schema 状态差异不超过1，也就是说所有 Server 使用的 Schema 状态都是兼容的。
• 如果每次小状态变更都保证全兼容，那么经过一些列变更，就可以到达最终的期望的状态，即从 "0" 逐渐演变到 “1”。

2. 增加二级索引的状态变更过程

表、表的某个Column、二级索引等，都可以称为 Schema 对象。这里用新增二级索引 E为例，说明一下具体有哪些小状态。增加其他 Schema 对象类似。

2.1 四个状态概述

对于新增 Index 这种 Schema 变更，状态变更如下图所示。注意，Absent 和 Public 都是理论上可以长期存在的；Delete Only 的存在时间一般是一个 Lease 长度。而 Write Only 的存在时间，则是一个 Lease 长度 + Reorg 的时间；Reorg 的执行时间取决于既存数据的量(后面有说明 Reorg)。

DDL 只有一个执行者，它的状态按照下面的顺序变更。而其他 Server 会定期(按照Lease)刷新schema 状态，因此最多落后一步。在同一时刻，最多有两个共存的状态，二者之间必须能够兼容。

1. Absent 状态

• 对应上面的 "0"；
• 完全不感知E的状态，任何DML都不会涉及E。

2. Delete Only 状态

• Select语句不能使用E；
• Delete语句在删除行​​时，如果​ ​存在，要一并删除；
• Insert语句，插入​​时，不允许插入​​ ；
• Update语句，在修改​​时，只允许删除既存的​​ ，但不能插入新的​ 。

3. Write Only 状态

• Select语句不能使用E(同上)；
• 其他DML正常使用和修改E的IndexKV。

4. Public 状态

• 对应上面的 "1"；
• E 正常工作，所有 DML都正常使用E。

其中的 Delete Only 状态，看起来好像比较诡异，却是必须的。因为它能跟 Absent 兼容。

2.2 各个状态隐含的前提和保证

这几个状态，实际上都隐含了自己能运行的前提条件，以及自己在运行中能保证什么。

我们用下面的表来表示。其中：

• "Delete Only" 和 "Write Only" 没啥前提条件要求，可以说是无所谓；
• "Absent" 能运行的前提条件是：完全没有 索引 E 的任何 IndexKV；
• "Public" 的前提条件是：索引 E的 IndexKV是完整的。

2.3 状态间如何兼容

2.3.1 为什么 "Absent" 和 "Delete Only"能够兼容？

Delete Only 本身没啥要求，只要满足Absent的前提条件即可。

• 由于 Delete Only 的上一个状态是Absent，进入Delete Only状态时没有E的任何ndexKV存在。
• Delete Only 状态的 Server 在执行过程中，不会产生 E 的 IndexKV。
• Absent 状态的 Server 也不会产生 E 的 IndexKV。
• 所以 Delete Only 和 Absent 是兼容的。

2.3.2 为什么 "Delete Only" 和 "Write Only" 能够兼容？

• 由于"Delete Only" 和 "Write Only"都没啥要求，本来就能兼容。

2.3.3 为什么 "Absent" 和 "Write Only" 不兼容？

• 因为 Write Only 会产生新的 IndexKV，破坏了Absent需要的前提条件。
• 假设在 Add Index E的过程中，有如下执行顺序： 1）Server A 按照"Write Only"插入一行x，它需要插入了两个KV; 2) Server B 按照 Absent 删除了行x，它只会删除 RowKV。那么这一行的IndexKV就成了孤儿数据。

2.3.4 "Write Only" 能否与 "Public" 兼容？

• 在 E 的 IndexKV 已经完整的情况下，可以与 Public 兼容;
• 但是只有IndexKV完整后，才可能切换到 Public 状态。

如何使得 E 的 IndexKV完整呢？表里面可能有历史既存数据，它们并没有对应 IndexKV；而 Delete Only, Write Only 都没有解决历史数据问题。答案是下面的 Reorg。

2.4 从 "Write Only" 到 "Public"：Reorg 搞定历史问题

仔细看下前面的状态变化图，在进入Write Only状态后，不是等待一个 Lease 就可以自然切换到 Public，而是在等待一个 Lease后，启动 Reorg，然后等待 Reorg 完成，才能切换到 Public。

对于 Add Index 这种操作，Reorg 就是为某个时间点(T3)前写的数据，补上 IndexKV。

2.4.1 为什么 Reorg 完成后，可以切换到 Public ？

• T3 之后，已经没有处于 Delete Only 或者 Absent 状态的 Server，全部都是 Write Only 状态；
• T3之前既存的数据，IndexKV 全部由 Reorg 补全；
• T3之后被 DML 修改的数据，由 DML(Write Only状态) 保证 IndexKV 完整。

所以，从T4(Reorg完成)，所有的Index都是完整的，可以切换到 Public。此后Write Only 和 Public状态的Server共存没有问题。

2.4.2 为什么"Reorg" 与"Delete Only" 的 DML 不能并存？

• Reorg的假设是：T3之后所有被修改的数据，IndexKV都是完整的。
• 而 “Delete Only"会让有些新修改的数据，没有对应的IndexKV。

在具体实现中，Reorg是按照快照时间戳干活的，所以需要底层KV能支持多版本。这里不展开了。

3. 删除 Schema 对象过程

删除Schema对象与新增Schema对象相比，状态变更是反方向的，但是要注意执行 Reorg 的阶段不同。例如，删除一个二级索引：

• 状态变更(与新增索引的过程正好相反)： Public => Write Only => Delete Only => Absent；
• Reorg 是在进入 “Delete Only” 状态之后，且过了一个lease；
• 在 Reorg 删除了所有既存的 IndexKV 后，执行者既可从 “Delete Only” 进入 Absent 状态。

这几个状态的前提条件不变，兼容性的原理也相同。例如："Delete Only" 仍然与 "Absent" 相邻、相互兼容；"Public" 仍然与 "Write Only" 兼容。"Delete Only" 仍然不会与 "Public" 兼容。

4. Optional的Schema对象的简化

如果新增的对象(比如新增一个 Column)，它的值允许为Null，即它的值是可选的(Optional)的。那么它的 Public 状态不要求所有行都有该 Column 的数据。既然 Public 状态不要求数据完整，那么前提条件也就变成了"无所谓"。

一旦是无所谓，就简单多了。 Public状态 可以直接跟 "Delete Only" 兼容，可以省掉 "Write Only" 和 Reorg。

如果新增的一个Column不允许为Null，则不能省略中间状态或步骤。

5. 两个不兼容的状态共存，必然导致异象么？

在前面讨论为什么 "Absent" 和 "Write Only" 不兼容时，我们举了个例子，说明会产生孤儿IndexKV(异象)。那么，异象产生的本质是什么？

事实上，在DDL的状态变化中，"Delete Only", "Write Only"都是向前兼容的，它们对历史数据没有任何假设。

既然它们向前兼容，为什么在Add Index的例子中，"Absent" 和 "Write Only"共存，会产生异象呢？是因为后面提到的逆序修改。

还是以Add Index为例，考虑下面的场景(Server A状态领先，进入"Write Only" 状态; Server B还在 Absent 状态）：

场景1：

1) Server B 按照 Absent 插入行x；

2) Server A 按照“Write Only" 修改行x。

场景2：

1) Server B 按照 Absent 插入行x；

2) Server A 按照“Write Only" 删除行x。

场景3：

1) Server A 按照 "Write Only" 插入行x；

2) Server B 按照 Absent 修改行x (可能正好修改了E索引的列，但是Server B不知道E)。

场景4：

1) Server A 按照 "Write Only" 插入行x；

2) Server B 按照 Absent 删除行x。

场景1 、2并没有产生问题；

场景3可能导致IndexKV(E, x)无效，因为Server B并没有去更新IndexKV(E, x)；

场景4则会导致IndexKV(E, x)变成了孤儿。

所以，真正导致上述两个不兼容状态共存时异象的，是因为同一行先按照 "Write Only" 修改，后按照 Absent 修改，而Absent 状态对既存的历史数据是有要求的，所以产生了异象。

两个不兼容的状态共存时，只有出现不兼容状态间的逆序修改，才会产生异象。

参考文献：

[1] Ian Rae, Eric Rollins, Jeff Shute, Sukhdeep Sodhi and Radek Vingralek, Online, Asynchronous Schema Change in F1, VLDB 2013