如何理解 F1 的 schema change

背景

F1 的 DDL 论文是 TiDB 的 DDL 实现的基础，F1 的论文主体有两篇，一篇总体介绍 F1 的 DDL ，另一篇专门介绍 DDL 的 schema change 方法。个人认为，第二篇才是关键，也是我看的比较糊涂的。 这里有一篇对于其第二篇论文的介绍，贴在这里有助于理解。

理解

在线 DDL 概念

这里讲的 DDL 都是指的在线的 DDL 。在线 DDL 的概念来自于 MySQL ，PostgreSQL 之类的数据库应该是不支持的。这一概念也非常的模糊，区分就在于在做 DDL 的时候是不是要加排他锁，来阻塞住事务。所以，所有的数据库都可以做在线 DDL ，就看是否愿意花力气去做了。对于传统业务，由于不是那么强调 7*24 也就可以挑个夜深人静，甚至就是维护的时间去做 DDL ，就算有几个用户在使用服务，大不了他们稍卡一下。而现代互联网对维护时间卡得很严，也就对这种不阻塞的 DDL 有更高的需求，最最互联网式的数据库 MySQL 就率先支持了这类操作。实现方式大多是采用复制一份新的 schema 的表，然后，期间对表的操作同时发到新旧两个表上去。

MySQL 支持的在线 DDL 可以看这个网页。基本就是两类，对索引的操作和对列的操作。这里解答了我的一个疑惑，为什么 TiDB 里实现的解释总是拿添加索引来举例？

F1 的方法

以之前做类似 Aurora 的经验，这一块问题非常多，如果只做离线的 DDL 大可不必这么麻烦。按照 F1 的论文，它通过

                                    (reorganization)
absent -> delete only -> write only ---------------> public

这样一系列状态变化来完成一个 DDL ，其中的约定是，每个节点都通过这四个状态，节点通过接受命令来进入下一状态。每个状态在所有节点里出现的时间最长不超过两个租约时间，怎么保证呢？通过下面这个规则，如果节点接收到上个状态转换的命令后太长时间没收到下个命令，也就是某个状态超过了两个租约时间，意味着自己接受指令太迟了，该节点就拒绝提供服务挂掉。

这四个状态里，absent 相当于节点还没收到指令的状态，public 相当于 DDL 做完的状态，那中间的两个状态呢？背景介绍里的链接给出了如下解释：

• A delete-only table or column can be modified only by delete operations.
• A delete-only index, can be modified only by delete and update operations. Update operations can delete key-value pairs corresponding to updated index keys, but they cannot create any new ones.
• A write-only column or index can have their key-value pairs modified by insert, delete, and update operations, but none of their pairs can be read by user transactions.
• A write-only constraint is applied for all new insert, delete, and update operations, but it is not guaranteed to hold over all existing data.

整理成表格后：

第一个状态就非常奇葩，第二个更是奇葩，直接叫 can not read 多好。 据说这样设计的原因是为了让同时存在的两个状态能行为一致，也就是（ absent 和 delete only ），（ delete only 和 write only ），（ write only 和 public ）。

举例：

给表 t 添加索引 idx ，部署环境是同时有两台数据库 a 和 b 。

1. a 进入 delete only ，添加完索引。b 还没接到任何消息。
   • 有对 a b 的插入操作，a 的 idx 忽略，b 没有感知也忽略。
   • 读操作，a b idx 都忽略。
   • 删除和更新，a idx 响应，b 忽略。
2. a 进入 write only ，b 进入 delete only ，添加完索引。
   • 有对 a b 的插入操作，a 的 idx 响应，b 忽略。（ b 丢失了索引数据？）
   • 读操作，a b idx 都忽略。
   • 删除和更新，a b idx 都响应。
3. a 进入 public 状态，b 进入 write only 状态。
   • 有对 a b 的插入操作，a b 的 idx 都响应。
   • 读操作，a idx 响应 b 忽略。
   • 删除和更新，a b idx 都响应。

给表 t 删除索引 idx ，部署环境也是有两台数据库 a 和 b 。

1. a 进入 delete only ，删除完索引。b 还没接到任何消息。
   • 有对 a b 的插入操作，a 的 idx 忽略，b 有索引 idx ，插入索引。
   • 读操作，a idx 忽略，b 使用索引 idx 。
   • 删除和更新，a idx 响应，b 也响应。（ a 的索引已经没了，所以响应也是空操作？）
2. a 进入 write only ，b 进入 delete only ，添加完索引。
   • 有对 a b 的插入操作，a 的 idx 响应，b 忽略。（ a 空操作？）
   • 读操作，a b idx 都忽略。
   • 删除和更新，a b idx 都响应。（索引事实上已经删掉了，找不到索引数据，空操作？）
3. a 进入 public 状态，b 进入 write only 状态。
   • 有对 a b 的插入操作，a b 的 idx 都响应。（ a 已经没有这个索引了，b 空操作？）
   • 读操作，a idx 响应 b 忽略。
   • 删除和更新，a b idx 都响应。（ b 空操作？）