数据库内核月报 - 2021 / 01

X-Engine · 引擎特性 · 并行DDL

概述

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),目前典型有两种方式:

  1. 内部排序,如快排
  2. 选择-置换排序

选择-置换排序是一种树形排序算法,平均和最差时间复杂度均为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为例):

  1. Scan:并行扫描全表,构造生成内部有序的run(s),每个run会等距采样一些点。
  2. Local merge: 对所有选出的采样点排序,最终等距选出三个splitters。每个线程做一次local merge,并根据splitters将输出结果分成4片。
  3. Global merge: 同一子区间的分片做一次global merge,完成排序,全局数据有序。

pddl

非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到内存中,并行扫描是纯内存操作。

测试结果

test result XEngine并行DDL效果非常不错,对比串行ddl,2线程得到1.7倍性能提升,4线程提升3.38倍,8线程提升5.84倍,16线程提升8.72倍。在32线程并发下,1亿条记录的表,添加一个二级索引只需要15.63s。

结果分析

  1. 并行扫描构建索引速度随线程呈线程增长,这是因为X-Engine并行扫描分片粒度很小,分片效果很好。
  2. Local merge时间开销先减小后增大,原因是随着线程数增加,数据分片增加,某些子区间可能数据量很少,则少量数据就写出去一个block,IO请求增多。
  3. Global merge时间开销在1-32线程速度基本是成倍提升,但64线程时未得到成倍提升。这是因为global merge的归并路数为local merge的线程数,则64线程时,global merge的归并路数显著增加,单条数据排序速度减慢的负向影响超过了数据分片增加的正向影响。

总结与展望

目前X-Engine的并行DDL已在RDS-XEngine中完成开发并上线,之后这项功能会移植到PolarDB-XEngine历史库中,并根据Polarfs进行优化,希望能给更多的X-Engine用户带来更好的使用体验。