导读：“关系”在数据库中的主要表现形式是表，包含表属性，列属性，索引以及约束等。通过“关系”来规范存储，使得用户通过SQL标准规范存取数据。借助SQL语句丰富的表达能力，在数据库层面就能搞定复杂的业务。
当然，为了做到这一点，“关系”定义（schema）的维护至关重要。当schema需要发生变更时，如何能做到Online(不影响业务的读写操作)？业内数据库Online schema变更的方案有哪些？X-DB是如何实现的，设计背后的原因是什么？本文将详细讨论。
作者 阿里数据库产品事业部技术专家 雁闲
MySQL Online DDL的演进
互联网业务发展迅速，应用模式频繁更改是常态。相应地，数据库访问模式和schema也随之变化。DDL（Data Definition Language）是SQL的一类，主要作用是创建和更改数据的schema信息，最常见的操作包括：加减列、更改列类型、加减索引等。
MySQL毫无疑问是最流行的开源单机数据库。熟悉MySQL的同学都知道，在5.5版本以前，MySQL不支持Online DDL。需要做schema变更时（例如：修改列、加索引等），要么锁表变更(禁写)，要么通过主备切换的方式来进行。第二种方式的缺陷在于：需要DBA人工介入，而且主备的schema变更先后生效，无法严格一致。
既然数据库内部搞不定，那就在数据库外部做。pt-online-schema-change, gh-ost等变更工具，通过建立目标schema的影子表，借助触发器双写或者拉取binlog双写，最终通过rename影子表操作来达到变更的效果。
5.6版本以后，MySQL内部开始支持Online DDL。主要原理是将数据分为基线和增量两部分，开启一个单独线程变更基线数据，同时增量实时记录到row-log里。基线变更结束后，通过回放row-log，实现增量同步。整个过程中有几个关键点：第一，开始变更时获取快照，这个阶段需要禁写，确保获取snapshot对应的基线，和后续增量(row-log)是一份完整的数据；第二，在基线变更完成后，开始回放row-log，由于row-log随着业务的写入在不断追加，因此这里基于一个前提：row-log的回放速度高于业务写入的速度，否则可能一直追不上，schema变更也就无法完成；第三，schema生效阶段同样需要禁写，确保不会有新的写进来，新的schema开始生效。
目前，MySQL8.0在对于部分加列等schema变更操作做了优化，支持instant ddl，有点类似X-DB Fast DDL。其余Online DDL的基本原理仍保持不变。对于MySQL的Online DDL方案，需要说明的是：MySQL主备副本之间通过binlog同步，主的schema变更成功后，才会写binlog同步给备库，然后备库才开始做ddl。假设一个ddl变更需要1个小时，那么备库最多可能会延迟2倍的变更时间。若变更期间，主库发生故障，备库数据还未追平，则无法提供服务的。
NewSQL的Online DDL
NewSQL时代，Online DDL依然是一个绕不过去的问题。以两个优秀的开源数据库CockroachDB和TiDB为例，它们的Online DDL实现均参考论文《Online, Asynchronous Schema Change in F1》。
F1-Server集群中每个server都是无状态的，多副本复制靠存储层Spanner保证。对于Spanner而言，F1-Server相当于一个客户端。数据库的schema通过Spanner持久化存储，每个F1-Server在本地维护一份schema的缓存，并通过lease机制保证缓存的时效性。任何一个F1-Server都可以接收读写请求，如果schema缓存不正确，就无法保证存取数据正确性。
DDL最简单的实现方法：执行变更过程中，所有F1-Server禁写，变更完成后，等待lease时间，确保所有F1-Server都拥有最新的Schema。但是，通常Schema变更都伴随着数据迁移，比如添加索引操作，需要依据主表build一份索引出来，这个时间可能很长，长时间禁写肯定是不可接受的。
既然禁写不可行，那么在DDL发生时，必然存在多个F1-Server存在多个不同版本的schema的情况。下面将以一个加索引的例子简单描述F1-Spanner架构下DDL执行过程，如为表Relation(Pk,C1)新加索引Index(C1)。首先选举一个F1-Servers作为Owner，记为F1-Server1，执行DDL后拥有了new-schema，同时假设F1-Server2仍然使用old-schema。
对于某个记录，F1-Server1会同时写入主表和索引数据；如果该记录后续被F1-Server2删除，那么只会删除主表记录，索引数据就会残留在系统中，这就产生了不一致。未解决这类问题，论文通过引入多个中间状态schema，并且证明如果任意两个相邻状态下，数据的一致性能得到保证，通过一系列中间状态变更，就最终能保证整个变更过程正确性。
Online DDL变更过程分为四个步骤：absent->delete-only->write-only->public，相应地，schema版本包括4个状态：
S1(absent): 变更之前的状态
S2(delete-only): 只允许删除新二级索引，忽略新二级索引写入，不允许读新二级索引
S3(write-only): 当所有F1-Server都达到S2状态后，开始进入这一阶段，允许删除/写入新二级索引进KV层，不允许读新二级索引，并开始扫描基线数据，构造新的二级索引到KV层
S4(public)：新二级索引对外可见(可读)
F1论文详细论述了经过这4个状态的转变，如何保证一致性，过程较为复杂，这里不做详述，感兴趣的朋友可以翻看原文。
数据库架构对Online-ddl影响
引入中间状态的目的是为了解决多个F1-Servers无法在schema变更期间，保证数据一致性。但这个前提是基于F1+Spanner框架（如图1）。
F1 架构
对于F1来说，Spanner是一个共享分布式存储层，而对Spanner来说，F1就是一个client。正在这种彻底的解耦、彻底的存储计算分离导致了schema-change的复杂性，当然架构的选择各有利弊的权衡，这里只是从Online DDL的角度考虑。
如果采用类似X-DB这种原生的Share-Nothing架构，对于每一个分片数据，都有三副本，并且有唯一的Leader，所有这个分片的写请求都会路由到这个Leader。因此不会存在对于一个分片，多个Server采用多个不同的schema来写的情况。
X-DB 架构
那么X-DB是如何实现Online DDL的呢？
X-DB Online DDL原理
X-DB是一个原生Shared-Nothing的分布式关系数据库，具备高性能、高可用、强一致、可全球部署、高可扩展特点。X-DB基于自研存储引擎X-Engine，采用类LSM的分层架构，数据按照时序逻辑分成多层，每一层数据有序，新数据在较高的层次，最老的历史数据在最底层。
对于X-Engine来说，每个主表和二级所有数据都是一颗分层的LSM-tree结构，总共分为4层，memtable，L0，L1和L2，每一层都保持有序，数据按新旧顺序依次往更高的层次迁移，其中memtable在内存中，其它几层按需可以在不同的存储介质上。
X-DB Online DDL充分利用X-Engine的特性来设计。我们将数据分为两部分，基线数据和增量数据。基线数据是指变更开始时，通过拿snapshot能遍历得到的数据。增量数据是指，变更开始后，用户写入的新数据。当然拿Snapshot过程需要禁写，因为我们强依赖这个一致性位点，确保基线+增量数据的完整性。
具体而言，Online DDL主要流程包括以下几步：
- 禁写，获取Snapshot，在schema中添加新索引元信息；
- 通过Snapshot遍历主表，构建二级索引的基线数据，数据直接写入到L2(不经过memtable)；
- 与步骤2同时进行，放开写，产生二级索引增量数据，这段时间禁止merge到L2；
- 待步骤2结束，合并新索引基线(L2)+增量数据(memtable,L0,L1)，禁写，变更结束。
- 放开禁止merge到L2的限制。
可以看到，虽然X-DB也需要一个一致性快照，但是并没有像MySQL一样，需要回放row-log，而是充分利用了X-Engine分层存储的特性，将所有基线数据产生的二级索引仍然作为基线直接写到L2。而所有增量数据产生的索引数据，则分布在memtable,L0,L1(通过禁止到L2的compaction逻辑实现)。由于数据之间有天然的分层时序关系，所有基线+增量就是一份完整的二级索引数据。通过这个方式，也避免写入量大的情况下和回放row-log追不上的问题。
下图分别描述了MySQL方案的二级索引build过程，X-DB方案二级索引build过程。t0时刻开始获取snapshot，build基线数据。t1时刻表示基线数据的二级索引build完成。
相比于X-DB，MySQL方案还有一个回放追row-log的过程，假设t2时间点能追上，t2以后新的schema生效，那么索引就build完成了。
MySQL Online build-index
X-DB中build索引并没有追row-log的过程，这主要是因为X-Engine是一个append-only的存储引擎，数据天然多版本存储。因此update并不需要像Innodb存储引擎一样在原地更新，增量可以实时维护。在基线build完成后，只需要将增量和基线合并在一起，并确保基线数据的version比增量数据version旧即可。如果基线中的数据有被更新的情况，也没有关系，因为最终增量中的新版本会覆盖老版本的数据。
X-DB Online build-index
至此，我们完成一个副本建索引的任务，那么其它副本如何构建呢？在步骤1禁写过程中，我们还会写一条ddl-start日志，然后在第4步禁写的时候，再写一条ddl-end日志。X-DB三副本通过同步X-Engine的redo日志来实现数据同步，ddl-start/ddl-end也是redo日志的一种类型。follower接收到ddl-start日志后，获取snapshot，并开始构建基线数据二级索引，然后接收到ddl-end日志后，则合并基线+增量数据，ddl完成。所以从用户的视角来看，leader和follower的ddl是同步进行的，避免了MySQL方案的主备延迟问题，任何时候三副本的多数派都是强一致的。
对比F1+Spanner的方案，一个重要区别在于：Spanner基本不感知DDL操作。对于Spanner来说，所有的操作都是PUT/GET/DELETE，所以副本间的变更也与普通DML没有差异。任何时候，只要底层Paxos协议能正常work，三副本高可用和强一致就能得到保证。这个方案虽然Schema变更比较麻烦，但对于存储层特别友好，不用感知DDL，共用一套机制保证高可用和强一致。
为什么X-DB需要引入ddl-start/ddl-end日志呢？一方面，可以使leader和follower同时做ddl操作。另一方面，基线数据build产生的二级索引并不会产生redo日志。而F1+Spanner方案，在Data-reorganization阶段，基线的每一条数据，都需要产生对应的redo日志同步到多副本，而且对于基线遍历的每条记录都需要重新check，来决定是否需要为这行数据执行变更。因此X-DB的Online DDL方案更简单，也更省成本。
总结
本文首先介绍了Online DDL的重要性和MySQL Online DDL方案的演进。然后介绍了F1+Spanner的Online DDL方案，相较于单机数据库，分布式数据库做DDL的同时需要保证三副本的高可用和强一致，不能出现类似MySQL主备延迟和主备schema不一致问题。
最后介绍了X-DB的Online DDL方案，通过对比，我们的方案简单清晰，也更节省成本。这个过程中，也间接说明了数据库整体架构和存储引擎的结构对Online DDL方案的影响。
