X-Engine · 引擎特性 · 并行DDL
Author: 柒沐
概述
X-Engine是阿里基于LSM-tree的自研存储引擎，作为MySQL生态的存储引擎，目前MySQL(XEngine)已经完整支持所有的DDL类型，对于OnlineDDL的特性，XEngine引擎也具备了与InnoDB引擎同样的能力，包括instant-Online DDL，Inplace-OnlineDDL等。OnlineDDL特性解决了DDL过程堵塞写的问题，但是目前DDL过程仍然还是比较慢。这主要是因为新建索引/修改主键这类DDL需要扫描全表数据，是一个常规且耗时的操作，一个大表的DDL完成时间甚至可能要以天计。
PolarDB最近发布的并行DDL特性就是为了解决这个问题，目前PolarDB同时支持InnoDB和X-Engine两种存储引擎，而且两种引擎都支持并行DDL。本文重点XEngine引擎如何通过并行来加速DDL执行。X-Engine的DDL主要包括两个部分：基线数据的新建索引构造，增量数据的双写（写入旧表的同时构造要新建的索引），具体可参考X-Engine OnlineDDL。本文所做工作是并行化基线数据索引构造过程，基于X-Engine现有的并行扫描功能实现并行DDL，X-Engine的并行扫描功能可以参考X-Engine并行扫描。
串行DDL
串行DDL本质上是一个串行外部排序的过程。首先根据主键扫描所有record，构造新索引的record。每扫描生成一段，排序后输出为一个run，最后将所有run(s)归并排序后输出。当然如果run(s)个数过多，即归并排序路数过多，无法容纳于内存工作区，则需要多轮归并。
就第一个步骤生成run(s)，目前典型有两种方式：
- 内部排序，如快排
- 选择-置换排序
选择-置换排序是一种树形排序算法，平均和最差时间复杂度均为O(nlogw)，w为树的大小。快排的平均时间复杂度为O(nlogn)，最差时间复杂度为O(n^2)。当用于排序的内存工作区大小相同时，两者的平均时间复杂度可以视为相同。虽然快排的最差时间复杂度等同于O(nw)，但其cache友好性更强，排序效率更高。选择-置换排序算法的优点在于能产生大于工作区内存大小的run（平均为两倍工作区内存大小），run的size更大，则run个数更少，则第二步的merge sort的路数更少，merge sort速度更快。
就第二个步骤merge sort而言，目前通常使用tournament tree，tournament tree分为两种：winner tree和looser tree。winner tree也就是我们普遍使用的堆排算法，looser tree是winner tree的优化版本，两者在时间复杂度上是一样的，都为O(nlogw)，但looser tree叶子节点上浮时除第一次需要和兄弟节点对比外，之后只需要和父节点做对比，效率更高。
考虑到实现新的数据结构的效果可能不如STL库内现有数据结构，同时可能会引入一些内存分配问题，目前X-Engine中使用STL中的sort算法（混合内存排序）排序生成run，用STL的优先队列实现第二步merge sort。
并行DDL
并行DDL本质上就是并行外部排序的过程。
步骤一生成runs(s)的并行化比较直接，通过并行扫描排序生成run，X-Engine的并行扫描以extent为粒度，粒度较小，分割数据分片很均匀。因此步骤一的性能基本可以随并行度得到线性提升。
步骤二merge sort run(s)的并行化会稍微复杂一些。第一种方案是两两并行merge，假设有m个run(s)，总records个数为n，这种方式的内存会放大(m-1)倍，如果中间结果是以输出到临时文件的方式，那么IO也会放大(m-1)倍。该方案的时间复杂度为O(nlog2)。当然为减少内存和IO放大，也可以用并行n-way merge。
如果最终需要merge一次全量数据的话，第一种方案已经是速度最快的方案（假设资源充分）。第二种思路就是基于partition和redistribution，典型代表为sample sort算法。sample sort的核心思想是通过采样选取出splitters，然后根据splitters将数据分配到子区间内，此时子区间间互相有序，子区间内部无序，这是每个子区间单独排序，最后就可以做到全局有序。这里我们借鉴了Polardb(Innodb)将sample sort应用于外部排序的做法。具体步骤如下（以并行扫描和merge sort并发度等于4为例）：
- Scan：并行扫描全表，构造生成内部有序的run(s)，每个run会等距采样一些点。
- Local merge: 对所有选出的采样点排序，最终等距选出三个splitters。每个线程做一次local merge，并根据splitters将输出结果分成4片。
- Global merge: 同一子区间的分片做一次global merge，完成排序，全局数据有序。
非unique二级索引优化
对于不需要判重的二级索引，不同于innodb需要保证数据完全有序，X-Engine的LSM分层架构中，某一层的extent的数据范围可以存在overlap。X-Engine的OnlineDDL实现中，基线数据构建完毕后会写入L2，因此对于不需要判重的二级索引，只需要完成第一个步骤，并行扫描生成内部有序的run(s)(此时需要直接以extent形式组织这个run)，然后就可以直接输出到L2中。这可以极大地提高DDL的响应时间，但带来的tradeoff是在L2中访问数据时可能会访问多个extent，但后续L2触发compaction会不断归并overlap的extent，从而减少overlap对读的影响。由于X-Engine目前的现有设计是只允许L0层存在overlap，L1，L2设定为严格有序，因此本方案对系统的整体改动比较大，目前暂时还未实际应用。
性能测试
测试环境
硬件：96core，768G内存
操作系统：linux centos7
数据库：MySQL8.0.17
sysbench导入一亿条数据，分别设置并发线程数（三个步骤的并发度相同）为1，2，4，8，16，32，64，测试添加一个二级索引的时间开销。统一各层的压缩方式，这里选择关闭压缩，这样每个extent中分布的kv个数接近，并行扫描的分片粒度会更加均匀。所有主键数据都load到内存中，并行扫描是纯内存操作。
测试结果
XEngine并行DDL效果非常不错，对比串行ddl，2线程得到1.7倍性能提升，4线程提升3.38倍，8线程提升5.84倍，16线程提升8.72倍。在32线程并发下，1亿条记录的表，添加一个二级索引只需要15.63s。
结果分析
- 并行扫描构建索引速度随线程呈线程增长，这是因为X-Engine并行扫描分片粒度很小，分片效果很好。
- Local merge时间开销先减小后增大，原因是随着线程数增加，数据分片增加，某些子区间可能数据量很少，则少量数据就写出去一个block，IO请求增多。
- Global merge时间开销在1-32线程速度基本是成倍提升，但64线程时未得到成倍提升。这是因为global merge的归并路数为local merge的线程数，则64线程时，global merge的归并路数显著增加，单条数据排序速度减慢的负向影响超过了数据分片增加的正向影响。
总结与展望
目前X-Engine的并行DDL已在RDS-XEngine中完成开发并上线，之后这项功能会移植到PolarDB-XEngine历史库中，并根据Polarfs进行优化，希望能给更多的X-Engine用户带来更好的使用体验。