DDL 模块的设计和演化

DDL 是 Data definition language。数据库里面的建表，删库，加索引，添加删除列，等等这些都是 DDL 操作。这次聊一聊 TiDB 里面的 DDL 的演化。其实我指的是 DDL 这个模块实现相关的东西。不涉及到算法本身，纯粹聊分布式系统在工程上的话题。最近同事在做 DDL 的并行优化相关的事情，我思考了一下：如果换作是我在设计，我会怎么做。

这个模块一步一步变成现在这个样子，其实是有很多点需要考虑。

第一个点是，引入 leader。TiDB 是一个分布式数据库，节点是有许多个的。每个节点上，都有可能执行 DDL 语句。插入删除这种 DML 语言可以各自执行，但是像 DDL 这种修改 schema 的操作是不能在每个节点上各自执行的。各个分布式节点看到的 schema 必须是同一份，不然就乱套了。节点一给某列加了个索引，节点二直接这列删了，如果这两操作放在各自节点上去做，schema 就不统一了。所以 DDL 都是由一个 leader 节点去做的。普通节点上面收到 DDL 请求，只是把消息发送出去，等 leader 做完了说没问题，再给客户端返回。

第二个点是，必须全局持久化状态。DDL 的具体算法部分比较复杂，一次 schema 的变更要经历很多个阶段。想想分布式系统里面，任何节点都是不可靠的，可能随时就挂掉了。DDL 的 leader 节点可能就挂，但执行的进度不能丢。我们必须知道做到哪个阶段了，如何恢复，所以必须记状态。本地持久化不行，因为 leader 可以挂掉，每个节点都可以顶替充当 leader 的位置。所以 DDL 执行的状态必须是全局持久化的。

这个状态我们记录在 TiKV 里面的。毕竟 TiKV 本身就是很好的分布式持久化的存储，这里正好用上。有一个问题要注意，是取消操作。一旦 DDL 开始执行，并且执行进度都是持久化的，即使节点挂了再起来，还是会继续执行。做 DDL 的过程异步补数据会对正常使用时有一定影响。所以这里是要考虑取消操作的。实现取消也是要注意数据索引的一致性。TiDB 开始没支持 DDL 取消操作，后面实现了。

第三个点是，引入 worker 和任务分发模型。有些 DDL 操作做起来是比较耗时的，比如建索引，必须根据当前的数据列去补索引，补完索引才对外可见。表可能非常大，几千万上亿条记录，这个时候只由一个 leader 去干活，就太慢了。于是可以改一改模型，做成 leader 分发，worker 干活。worker 可以开启多个，加快处理速度。

索引变成 KV 以后是对应一块逻辑的范围，有可能很离散。要注意哪些 worker 该负责哪块区间。如果按区间范围写死了分配给 worker，可能有的闲有的忙，有的区间没数据，而有的区间要处理的数据很多。所以这里不要按逻辑区间分配范围，可以用 scan 做。这也是我们发现的问题并优化掉的一个点。

DDL 的作业队列，是利用 KV 抽象出一个类似 redis 的 List 的 API。包括早期的 leader 和 worker 的一些信息，都是直接利用 TiKV 来做的。后来的优化把 leader 和 worker 这一部分信息记到 etcd 里面去了。那个优化解决的是 schema lease 等待的问题，优化之后像删掉一列这种不需要补数据的 DDL 操作就能瞬间完成。

这里面也有几个工程上值得关注的地方。leader 和租约机制，在 etcd 里面记录信息，leader 不断更新自己的租约。如果 TiDB 的 leader 节点被 kill -9 之类的异常退出，就没机会去清掉自己写在 etcd 里面的信息，于是其它节点必须等待租约过期后才能去再竞选 leader。DDL 操作会被卡往，lease 设置的越长，这种情况下卡住的时间越久。

DDL job 队列的（分布式）全局锁。全局状态这种东西，有人读有人写，而底层是用的 TiKV 事务实现，冲突的代价还是挺大。因为大家都会访问到一个 key 上面，这里存在热点，冲突相对严重，会影响性能。还有 leader 要知道 worker 还是不是在干活，如果 worker 挂了，不能让整个 DDL 停了。必然涉及有一些全局状态的交互。

第四点是并行 DDL。也就是演化到现在，正在做的事情。早期为了设计简单，让 DDL 排队依次执行的，假定用户并不会频繁的执行 DDL 操作。只用了一个作业队列排队。然而这里有一个问题：排在前面任务的会阻塞后面的任务。比如，执行一个表A的添加索引，表A有一千万行，会执行很久，执行表B的添加一列，执行表C的添加一列，后两个操作本来是可以并行执行的，却被排队卡往了，这样用户体验挺不好。

如果我来设计这里，我会这样做。把状态和消息给分离。leader 和 worker 之间的协作，属于消息。而具体到某个 DDL job 执行到什么情况了，这个属于状态。消息可以通过 etcd 来交换，而状态则仍然持久化在 TiKV。

设计合理的数据结构。状态的数据结构，也就是所有当前 DDL job 的表示。可以构造一个依赖图，看哪些 DDL job 的操作是有依赖的，哪些是无冲突的。比如，一个 DDL 是为某列加索引，另一个 DDL 删除这一列，这两者显然相互冲突，无法并行。而如果一个 DDL 是在改表 A，另一个 DDL 在改表 B，这两者就是无冲突的。在单机里面，也就是 leader 节点的进程，我们可以弄一个图的数据据构，然后做一个拓扑排序，就可以决定 DDL 的操作次序了。

状态是要持久化的，我们可以把它做成一个数组，每一项就是一个 DDL job。持久化的时候变成顺序的 kv 就行了，key 是 DDL job 的 ID，value 是对应的 Job 的状态信息。获取全部的 DDL job 只需要 scan 一次。job的 ID依次递增不重用。加载到 leader 进程之后，解析成依赖图。也就是将之前的单个的作业队列，替换成一个图结构，消除掉后面阻塞住前面的情况。可以做成只让 leader 改状态，任务的分发全部走消息，任务完成也由 worker 走消息，而不是直接改状态。这样子不会出现任何读写冲突，之前存在的队列的热点冲突就解决了。

消息的设计，leader 和 worker 都在 etcd 上面注册自己。消息交互就通过往结点的路径里面添加事件。leader 的 lease 保证自己挂了会有 worker 顶上来。而 worker 的 lease，可以用于 leader 确认 worker 是否在干活。worker 活干到一个阶段，都可以通过消息告知 leader，由 leader 去改状态。

大致想法就是这个样子，这是理想情况。不过应该不会实现成这样，毕竟要考虑很多历史包袝，保持向下兼容。