DDL实现与优化
F1/Spanner
F1[1]是基于Spanner实现的一套异步Schema变更协议，该协适用于「共享存储 + 无状态节点 + 节点间无感知」 的分布式数据库管理系统。F1要解决的问题是在多个对等的无状态计算节点的架构下，每个计算节点都会缓存一份Schema，如果对schema进行变更，则会导致整个集群中可能存在多个不同版本的Schema进入导致数据的一致性。为了保证此类型架构下数据的一致性，则引入了Schema租期和两个Schema变更的中间状态，通过多步往前推进从而确保最终数据的一致性。
在F1协议下，每个计算节点，如下左图的F1 servers，对Schema维护一个租约，租约过期后会重新去获取当前最新版本的Schema，通过租约的机制，能够保证在有限的时间内计算节点一定能获取到最新的Schema，并且同一时刻集群中最多存在两个版本的Schema。Schema变更状态转移过程为
absent->delete_only->write_only->public。其中delete-only 指的是 Schema 元素的存在性只对删除操作可见；write-only 指的是 Schema 元素对写操作可见，对读操作不可见。状态转换过程中如何保证数据的一致性，论文[1]给出了完整的形式化证明，这里不再赘述。以创建索引为例，从
absent-> delete-only不会对新索引做任何操作，等待一个lease周期后能够确保所有节点都能够进入到delete-only状态，然后delete_only->write_only状态，在wirte_only状态下，所以对数据的更新操作(insert、delete和update)都会应用到索引上，但是该索引对读操作是不可见的，待所有节点都处于write_only状态后，会进行reorg操作，获取当前数据的快照然后填充索引，填充完后能够确保数据是一致的，然后将状态往前推进到public状态，对外所有操作可见。
TiDB
TiDB以及我们内部的ByteSQL都是Spanner的效仿者，其DDL(Schema change)的实现也都参考了F1协议。下图来自[5]，是TiDB实现的DDL架构。TiDB对于DDL的变更将其实现为异步任务，每个计算节点(TiDB Server)按照F1协议会周期性的去元数据中心(PD Cluster)获取最新的Schema，同时启动一批后台worker线程负责处理DDL Job。当任意一个计算节点收到用户的DDL的请求时，做一些基础检查后会将其打包为一个DDL Job，根据Job类型并写入到TiKV集群的相应的Job队列内。通过PD，多个计算节点会选出来一个Owner处理专门处理DDL Job，每个计算节点的worker都会周期性的去检查自己是否是owner，如果是owner则会去TiKV的Job队列获取是否有可以执行的DDL Job，获取到后再本地多线程并行执行Job，执行完成后再讲Job从任务队列移除，放到history队列，而生产DDL Job的worker也会不断地查询Finish队列是否有生成的Job，以此判断是否完成，如果完成则获取执行状态返回客户端。
同样以创建索引为例，在该架构下流程如下：
- 客户端发送添加索引请求到 TiDB ，TiDB 会检查表、索引等是否符合规范
- 将添加索引请求转化成 Job 发送到添加索引的队列中 (add index job queue)
- TiDB 会启动 Worker ，将 Job 从添加索引的队列中取出，并且写入到对应表信息中
- 这时候 Worker 从 PD 中获取需要添加表的所有 region 范围，并且默认分成 256 个子 Job ，并发的去扫 region 中的所有数据，生成索引信息
- 当所有子 Job 都完成之后，会将该 Job 放入历史队列中 (history ddl job)
PolarDB-X
PolarDB-X也是存算分离，多写的架构，其实现也是基于F1协议，其实现架构如下图所示，和TiDB的实现是比较类似的，同样地每个计算节点收到DDL请求后，将其打包为DDL Job写入到GMS，Owner获取到该Job后进行执行，执行过程就是F1的状态变更过程，这里不再赘述，具体可以参考[6,7,8]。
除此之外PloarDB PolarDB-X针对DDL也做了很多其他的优化，比如针对DDL执行时如果有大事务正在运行可能阻塞后续的读事务[9]，利用F1同一时刻可以存在两个版本的假设可以做到不阻塞后续的读事务，具体参考[10]。
CockroachDB
CockroachDB的DDL方案也是F1的实现，其实现方式和TiDB以及PolarDB-X类似，这里就不再赘述了，感兴趣的可以参考文章[16]
Amazon Aurora
Aurora官方文档[13,14]介绍了其对DDL做的一些优化Fast DDL，但是只是针对MySQL 5.6/5.7版本的，核心思路是，Schema变更的时候直接同步更新
INFORMATION_SCHEMA系统表，并将Old Schema记录到Schema Version Table表内，然后将其更新同步给备几点，就完成了变更操作。再后续的DML操作中会检查该数据Page是否有正在进行的Schema Update，如果存在则比较Page LSN和Schema update LSN，然后再DML对Page更新前应用新的Schema，官方将这种方式称为piggybacking this change on top of other DML (and associated I/O)。作者觉得再实现的时候应该还是比较复杂的，还有考虑redo page、备机的Buffer pool等，而且Fast DDL只适用于在表最后面添加一个nullable的列。随着MySQL 8.0的发布，官方已经支持了Instant DDL，所以使用Aurora 3(MySQL 8.0)的用户则可以直接使用Instant DDL。对于创建索引，目前还没有公开资料表明Aurora 3做了什么特殊优化，目前应该还是MySQL 8.0的方式。但是设计FastDDL时，设计者其实也考虑到其他DDL也可以采用类似的方式优化，并且认为对于影响前端DML的长DDL操作，将他们并行化，异步化以及移到后台执行对稳定性和性能应该有较大提升[13]。
There are obviously lots of other DDL operations for us to improve, but we’re pretty sure that most can be approached the same way. This stuff matters—even if the database is up by normal definitions of availability, application usage is impaired on these long operations. Moving them to parallel, background, and asynchronous execution makes a difference.
GaussDB(for MySQL)
如下图左所示，GaussDB for MySQL版本采用的也是计算存储分离架构，计算层分为读写、只读节点，并且完全兼容MySQL 8.0[1]。对于创建索引操作，文章[2]展示了其在创建索引过程中做的并行优化，从扫描、merge以及创建B+Tree三个阶段均将其并行处理，相比MySQL 8.0.27官方版本的Parallel DDL[3]，官方版本只对扫描、Merge阶段做了并行处理，在创建B+Tree的阶段依然是单线程处理。
实施效果如下图所示，对于一个1亿条数据的表，打开并行创建索引相比单线程创建索引性能性能提升了3.79倍。不过文章[2]并没有与MySQL 8.0的并行DDL进行对比，但是GaussDB的并行是全链路的并行，对最后阶段填充B+Tree也做了并行化处理，所以理论上性能是要优于MySQL 8.0的官方实现的。
PolarDB
PolarDB也是存算分离的架构，不同于PolarDB-X系列，其架构和Aurora更加类似一些，通过RedoLog同步主从节点，数据则采用共享存储只存储一份数据。文章[10]则详细描述了PolarDB在DDL上所做的工作，通过
Instant DDL + Parallel DDL + 物理复制链路优化的整体解决方案提升了DDL的性能和稳定性，其中Instant DDL和Parallel DDL也是MySQL官方优化DDL的思路，尤其是MySQL 8.0.27[4]之后提供了官方的DDL并行方案，但是不同于官方版本，PolarDB对DDL的并行做了更多的优化。以创建索引为例，其核心耗时的操作主要是扫主表对数据排序和用排序后的数据重建B+Tree，如下图右，官方只对扫表排序做了并行处理，创建索引依然采用单线程从底向上构建所以，PolarDB在对B+Tree的构建也进行了并行化的处理，进一步缩短了创建索引DDL的耗时。
Socrates
We are currently working on implementing bulk operations such as bulk loading, index creation, DB reorgs, deep page repair, and table scans in Page Servers to further offload Compute nodes as described in Section 4.1.5.4.1.5 Pushdown Storage Functions. One advantage of the shared-disk architecture is that it makes it possible to offload functions from the compute tier onto the storage tier, thereby moving the functions to the data. This way, Socrates can achieve significant performance improvements. Most importantly, every database function that can be offloaded to storage (whether backup, checkpoint, IO filtering, etc.) relieves the Primary Compute node and the log, the two bottlenecks of the system.
下图来自[12]是Socrates的架构，类似Aurora也是
Log is Database的实现，整体也是存算分离架构，计算层读写分离，采用一主多备的模式。作者并没有找到太多关于Socrates关于DDL/Schema Change相关的公开资料，但是从原始论文[12]描述中，论文作者又提到他们正在实现Bulk操作，其中包含了索引的创建，以及扫表操作也会下推到PageServer(存储层)中。计算节点和xLog Service是整个系统的瓶颈，论文作者也提到他们也在尽量将计算层一些功能下推到存储层尽可能的降低计算层的压力。所以可以猜测对于DDL操作尤其是DDL中创建索引涉及到消耗大量CPU和IO资源会对计算节点带来很大压力，所以其中一些操作如果能够下推到存储层则会很大程度降低计算层的压力。
其他
小结
分布式数据库当前基本都是存算分离的架构，当时在具体实现架构上大致分为了两大派系，分别为F1/Spanner和Aurora两个派系。其中TiDB、ByteSQL、PolarDB-X、CockroachDB属于Spanner系列，其计算节点完全对等，所以在实现DDL的时候更多的考虑不同计算节点间Schema的一致性，F1协议将Schema变为多步操作，最终保证了不同节点数据以及Schema的一致性，但是在DDL真正执行尤其是涉及到数据回填索引(reorg/backfill)操作的时候依然是在一个计算节点并行操作，需要消耗大量的CPU资源，不同于MySQL的是其底层数据本身是Partition的，所以扫描粒度以Partition为单位，相比BTree做子树划分可能数据的局部性以及IO的连续性会更好一些，但是目前没有看到更多对计算节点CPU优化的或者加速DDL操作的优化，所以这几个系统依然存在DDL操作期间计算节点资源占用率过高的情况，TiDB社区也有如此反馈[17]；GaussDB(for MySQL)、PolarDB、Socrates等类Aurora系统则以完全兼容MySQL为卖点，基本也都是基于MySQL内核改造，所以其DDL操作基本和官方保持一致，只有GaussDB、PolarDB在创建索引流程中对回填索引也做了并行化的优化，从而进一步降低了DDL耗时，但是并行化一定程度上是会拿资源换时间，也就是并行化会消耗更多的资源，最好也是在业务低峰期进行。
总的来说，DDL对用户来说确实存在较多问题，比如阻塞DML请求，消耗太多计算节点资源，各个厂商也都做了或多或少的优化，但是更多的还是集中在降低DDL操作时间以及解决阻塞DML等方面，对于占用计算节点太多的资源进带来DML操作延迟抖动方面目前没有看到太多的优化工作，基本都是推荐业务在低峰期进行操作。