2022 OceanBase数据库大赛决赛经历分享

1. 开篇

我是参赛队伍824445721的队长黄朴凡，队友是范乾一、冯惠，在2022 OceanBase数据库大赛中获得了季军的成绩。

在前两天刚刚完成答辩并得到了最终的名次，这是我第一次参加数据库相关比赛，从数据库知识、编程经验再到复杂系统分析、团队组织都收获颇丰。于是写下这篇总结文章，梳理一下这段时间的收获，记录下这段和队友一起努力的时光。

文章整体梳理了基于多线程去实现和优化一个具体功能点需要考虑的大部分脉络，即使是对比赛本身不感兴趣的同学，应该也能从中得到一些启发。

我们在初复赛的过程中，去年选手写的一些科普性质的文章，无论是环境配置还是一些基本信息的介绍都给了我们不小帮助，非常感谢他们，对以后的同学也肯定有很大的参考价值。罗列如下：

1. OceanBase大赛 | 手摸手带你玩转 OceanBase

https://zhuanlan.zhihu.com/p/445201899

2. OceanBase数据库大赛复赛 NestedInnerJoin 赛题

https://zhuanlan.zhihu.com/p/459185153

3. 2021 OceanBase 数据库大赛初赛 miniob 赛题攻略

https://zhuanlan.zhihu.com/p/455956866

4. OceanBase比赛总结 | OceanBase 内核初探

https://zhuanlan.zhihu.com/p/508331407

初赛的简单介绍：初赛比较重要的一点就是我们舍弃了官方代码里提供的火山模型框架，彻底使用物化模型作为我们的整体框架。在比赛到中途的时候，我觉得必须要重构 miniob 的一部分框架。

重构原因：第一，当前的火山模型框架不是非常清晰。因为去年的 miniob 代码并非是火山模型，今年的改动并没有完全地改完，导致两年的框架有些重叠和融合，并不纯粹，所以写起来稍微有些别扭。而测试数据量完全是在内存中的，所以可以放心地传递全量数据。第二，提供的部分数据结构的内存空间管理，其构造和赋值方式是杂糅的：既存在自己 new 的部分，也存在直接指向其余已存在的 char* 的赋值函数。在这种情况下它的空间释放以及数据结构之间后续的再次赋值就令人有点头疼，因为无法确定每一条数据的空间（char*）是否由自己管理。

重构方面：主要做了两方面的重构，首先，从效率上而言，对作为教学型系统的 miniob，单条数据为单位的火山模型在这里意义不大。所以直接用自上而下的物化模型，一次就将本层的全部数据处理完全再传递给下一个层次，从 pull 改成了 push。其次，将原本杂糅的数据结构拆分，分成完全只由自己管理空间的数据结构与完全不自己管理空间，只指向由其他地方申请空间的数据结构。将二者彻底分开我觉得在写代码的时候思维负担更轻一些。后续决赛时看 ob 源码的时候，发现它的 ObString 等也是纯粹作为容器，从来不自己申请释放空间，完全手动管理。

物化模型的搭建：大致按照不同的查询内容，按照顺序去调用各个层次的 operator 的 build 函数。最顶层不需要考虑某一层次是否需要被调用，完全由该 operator 的 builder 根据传入的信息进行判断是否需要 build。每层将最后一个建立的 operator 指针放到链路的尾部，以此向后不断延伸。build 完成后该链路即建立完成，从首部开始沿链路进行后续操作即可。

2. 决赛题目简介

今天分享的重头戏还是决赛，决赛的题目：《OceanBase 2022 决赛赛题》👇

https://open.oceanbase.com/train/TopicDetails?questionId=600003&subQesitonId=800003&subQuestionName=OceanBase-2022

简要介绍一下决赛赛题：

当前 OceanBase 导入数据的方案是将文本文件转换成batch insert语句执行插入，执行路径长，需要经过 SQL、事务、转储等。在很多传统的数据库当中，提供 "direct path load" 方式，这种方式是一种可以"走捷径"的方案，跳过 SQL 与事务，直接将数据存储在 SSTable 中，因此称这种方案为"旁路导入"，这种方式相对过去batch insert方式，更底层、更直接，性能上也会有量级提升，是我们解决导入问题最佳方式之一。目前 OceanBase 还未包含旁路导入的功能，选手们可以参考我们提供的 demo 工程实现指定场景的旁路导入功能，同时优化导入的性能。优化链路包含解析 CSV 文件、转换为 OceanBase 内部数据结构、写入 SSTable 存储等。

3. 对 demo 思路的分析

旁路导入demo程序：旁路导入 github pull request

https://github.com/oceanbase/oceanbase/pull/1107

比赛方提供了一个简单的 demo 做参考，demo 分为几个部分，下面一一介绍思路。

3.1 解析文件

将文件以 2M 为单位读入文件缓冲区，将 csv 文件按照行列格式解析。行数据通过 '\n' 分割，列数据通过 '|' 分割，无行前缀，无引用字符，无转义字符，最后存成原始行格式 ObNewRow 类型。

3.2 列值转换

将原始类型转换为 OceanBase 内部支持相对进一步复杂处理的 datum_row 类型。细分为三点：

a. 字符集转换：将数据源的字符集转换成数据表设置的字符集

b. 类型转换：将解析出来的字符串列值转换成数据表定义的列值

c. 顺序转换：将每行的列值按照数据库存储序列格式排序（主键列排到前面，其余后置）

3.3 排序

数据源无序，但是 OceanBase 要求数据有序存放，所以需要基于临时文件系统读写磁盘，进行外部排序。以行为单位，把每一行放入当前顺串的内存缓冲区。

a. 当放入之后该内存缓冲区未满时，则继续放入下一行数据。

b. 当放入之后缓冲区已满，则启动该缓冲区的内部排序，排序完毕之后将有序缓冲区作为一个顺串写入磁盘中，并且记录写出文件对应的信息。以便能够在之后再次访问到该数据文件。写出文件后将原本放入失败的数据再次放入内存缓冲区。

c. 在所有的内部排序结束之后，对所有写出的文件均分配一个缓冲区，归并时从每个缓冲区取出当前最小的数据放入小顶堆中，然后从堆的顶端取出堆中的最小值，同时从该最小值对应的文件缓冲区中再取出下一条数据放入堆中。以此流程循环，取出全部数据。

3.4 生成 sstable

从堆中取出的全部有序数据依旧以行为单位，传递给 OceanBase 的 sstable_writer。该部分的处理逻辑是 OceanBase 本身已实现的，大致流程为以行为单位向缓冲区中写 2M 大小的宏块，宏块被写满就刷盘。由微块组成宏块，宏块组成 sstable 本身，宏块微块是 OceanBase 独有的概念。

这里只需要按照流程调用 append_row，即可完成整个 sstable 的写出。想要完全理解整体流程的话需要搞明白 sstable 这种格式以及 OceanBase 的底层存储设计。

a. OceanBase 的存储结构设计可以参考：http://www.oceanbase.wiki/concept/storage-architecture/overview-of-storage-architecture

b. OceanBase 生成 sstable 流程：OceanBase 是基于增量＋存量的存储KV引擎架构，实现过程包括：

• 使用 macro_block_writer 将有序数据编码成宏块
• 使用 sstable_index_builder 构造宏块索引
• 获取结果，构造一个 SSTable
• 将 SSTable 加入数据表的存储中
• 最终生成一个基线 SSTable
• demo 程序的整个流程如下图

4. 优化方向

官方提供的优化方向有如下三点：

• 「文件解析」根据限定的格式简化文件解析逻辑，结合多线程实现并行解析；
• 「多线程」充分利用 CPU 资源；
• 「外排序」合理利用 CPU、内存、磁盘资源，提升排序性能

5. 调优工具

6. 破题思考

经过对于 demo 的分析和一些思考，不难发现决赛真正的要求和实现难点实际是外部排序本身。换句话说，本次赛题就是要在对于 OceanBase 内部数据结构以及框架深刻的理解下，在一个磁盘速度很慢的环境下实现一个针对巨量数据尽可能快的外部排序。当然，我们需要优化文件解析、sstable 的部分，但相对而言，外部排序才是真正的主体。

意识到这一点之后，我们就需要对外部排序的经典论文以及实现做一些调研和通读，从理论方面为优化提供一些支撑。

7. 外部排序调研

罗列一下搜集到的一些重要资料：

（1）《External Sorting Algorithm: State-of-the-Art and Future Directions》https://iopscience.iop.org/article/10.1088/1757-899X/806/1/012040/pdf

这是一篇很新的综述，里面提到了一些如 AlphaSort 等外排方面的经典论文，还有压缩算法，给我们打开了眼界。让我们对外部排序本身的研究情况有了一定了解。可以看到外部排序本身是分为多个研究阶段的，最古早的阶段就是使用传统的 hdd，磁盘速度非常慢的情况下，尽一切可能增加内存处理时间占比，减少磁盘 io，基本上是这个阶段的共同追求。而后续的使用闪存和 SSD 方式对应的外部排序论文与我们关系不大，不考虑。

（2）《AlphaSortSigmod》https://sdhz5n014f.feishu.cn/wiki/wikcn1P0MgViVXSvI9bVMH8rNvb

很老的考古论文

• 整体算法是一种缓存敏感的内存密集型排序算法：使用快排以及置换选择排序来生成和归并这些顺串。
• 使用 File Stripping 来获得高磁盘吞吐。
• 使用共享内存的多核处理器来把单个的排序任务拆分成多个子任务从而获得更高的并发。

（3）一些压缩算法

《字典压缩以及 Quadgram 等方法的比较》https://sdhz5n014f.feishu.cn/wiki/wikcn1P0MgViVXSvI9bVMH8rNvb#SMqOdsKkgo6A8Gxr4UPcSLS0nNR

《轻量级压缩》https://sdhz5n014f.feishu.cn/wiki/wikcn1P0MgViVXSvI9bVMH8rNvb#F6AodMWWWoUewux6t10ceU1nnif

《FSST》https://raw.githubusercontent.com/cwida/fsst/master/fsstcompression.pdf

这些论文和书讲解了数据库中压缩算法的作用以及外部排序中压缩算法的选择和重要意义。在使用机械磁盘的系统中，尽量减少磁盘 io 是优化关键，因此压缩非常重要。

（4） 以 STXXL 为代表的基于并行磁盘的外部排序等

https://stxxl.org/tags/1.4.1/design_algo_sorting.html

由于我们的环境为阿里云服务器，经测试不存在多个磁头，并发读没有收益，也就不存在并行磁盘这一前提，因此此类算法无法适用。

8. 对于外部排序实现的认识

8.1 多线程化外部排序的巨大意义

外部排序本身最大的收益一定是将整体流程多线程化，外部排序多线程化一般有两种方式：多线程桶排序以及多线程归并排序。二者各有优劣和适用的情况之分，比如后者的一般实现在最后一次归并的时候只能用上单线程，无法将 cpu 性能利用到极致。

8.2 压缩对外部排序的意义

因为机械磁盘的读写速度实在太慢，所以基于 hdd 的外部排序几乎最大的目的都是为了尽量减少磁盘 io。所以一旦压缩比例比较高，那么相当于用 cpu 的时间 [压缩解压] 换磁盘 io [顺串写入文件、归并] 的时间。压缩的时机往往就是读进来解析的同时就进行行压缩，后续在内存中和写文件都只用压缩后的格式来处理，这样内存中能够放下更多行的数据，而写入文件之后也会更小一些。而由于这种压缩是针对行进行的压缩，数据库中常用的技术往往是块压缩，所以在压缩技术调研的时候碰到了一些问题。虽然 ob 本身提供了一些压缩接口，但同样不包括对于短字符串、行数据等的压缩，以及不存在提供字典进行预训练的动态/半静态压缩接口。所以要尽可能自己探索各种短压缩的可能。

8.3 文件读写

并不是一次读取的数据越大，一次性写出的数据越多越好。如果每次读的时间较长，后置的线程会先处于阻塞状态，CPU 的利用率并不高。所以需要减少每次读的大小，尽可能保证流水线一直处于运行状态，提高 CPU 的利用率。保证 read 和 write 能够不间断的占用磁盘活动，提高IO速度是提高程序性能的关键。

8.4 尽量复用内存、线程

尽量采用零拷贝设计的思想。因为本身内存申请和释放就是比较大的开销，所以如果能一次申请，多次使用，一定能节省一大笔开销。线程同理，过度频繁地申请和销毁线程本就说明代码实现效率的低下。因此尽可能的复用，尽量减少空间的申请和释放。

不过对我们的场景而言，线程本身申请、销毁的频率相对来说很低，没有到影响性能的程度。主要还是着眼于针对内存的优化。和减少拷贝一样，都是在减少系统调用的出现，尽量使用用户态的函数，用更低的代价去做相同的事。

8.5 顺串的内部排序存在优化空间

• 比较器的简化：将主键拼接之后利用 memcpy 做为比较器
• 算法的优化：排序的时候使用 key 与指向数据的指针，保证排序单元在内存中是定长的，这样对于访存以及排序时在内存中挪动数据更友好。
• 是否存在比 STL 实现的快排更优秀的内存排序算法？是可能存在的，但是要注意到 STL 中的实现本身不是算法的朴素实现，而是综合考虑到缓存友好等一系列标准的很优秀的实现，即使是采取其他的排序算法也要考虑到实现本身的高效性。

8.6 归并

• 归并分为  K-way 归并以及 Cascade 归并：一般使用 K 路归并更为常见。而 Cascade 归并利用二分搜索算法可以有效地计算出合并路径上的交叉点，如果我们知道交集在哪里，我们就可以独立地并行合并排序数据的分区。这允许我们在整个合并阶段有效地使用所有可用线程。
• K路归并阶段，败者树 > 胜者树 > 堆实现：虽然是常数意义上的优化，但是聊胜于无，并且是纯优化，无副作用。

9. 核心优化

9.1 多线程优化「绝对核心」

初步分析

观察 demo 的火焰图， 可以看到整个旁路导入的流程 do_load 分为几个最主要的部分：

• 行类型转化 ObLoadRowCaster
• 外部排序 ObLoadExternalSort
• 写sstable SSTableWriter

而三者之中，最为耗费时间的又是写 sstable。而这部分的工作并不是单纯的写文件，而包含了大量的计算，如压缩以及行校验等。有了这个共识，我们需要去探索如何分别用多线程以及重构代码去加速这三个主要矛盾。

而在具体探索多线程的使用方式之前，我们需要探讨对于外部排序而言，它的多线程实现的经典方式有几种，分别有什么特点，我们如何选择。

最为主流的利用多线程加速外部排序的两个方式是多线程归并排序以及多线程桶排序，介绍如下。

第一，多线程归并排序。

把需要排序的数据分成若干段，由不同的线程进行排序和归并，生成完顺串之后再归并。

问题：最后一步归并是单线程的，不能最大化利用 cpu

解法：利用 Cascade 归并。

第二，多线程桶排序。

• 采样原始数据生成若干个桶
• 读取原始数据按照桶的范围把数据分发给若干个桶
• 利用多线程分别对各个桶进行排序以及归并

9.1.1 方案选择

出于两方面的考虑，我们选择多线程桶排序。

一方面由于上面提到的 「最为耗费时间的写 sstable 包含了大量的计算」，因此我们的选择中必须要将这一步骤多线程化，而桶排序将数据按照范围进行划分成一个个 range 之后，range 之间就不互相重叠。而 ob 提供的写 sstable 的接口在能保证数据之间不重叠的情况下，才可以并写调用写 sstable 的接口。因此桶排序天然符合将这个阶段多线程化的需求。而多线程归并排序做不到这一点。

另一方面，多线程归并排序虽然是将数据连续地分段，将每一段分给一个线程去排序。但在读文件的时候，如果并行地读文件，会导致磁头跳跃式在多个划分出的文件段上移动。这样无法充分利用系统预读。如果串行地读文件，就会导致线程之间开始排序和写文件的时间有较大的差异，如果划分的顺串较大的话，最后一个写出的线程就会成为一个小瓶颈，拖慢整体的流程。

具体优化阶段

我们的多线程优化前后经历了三个阶段，分别是：

阶段一：基于多线程的桶排序进行解析文件、数据分发给对应的桶，进行外部排序和写文件的朴素实现；

阶段二：解耦生产中的解析和压缩，深度加速生产；

阶段三：解耦消费中的排序和落盘，深度加速消费。

在完成阶段三的同时，我们提炼出了一套通用的优化多线程链路的方式，就是无限解耦。下面将展开陈述。

「阶段一」 基于多线程的桶排序进行解析文件、数据分发给对应的桶，进行外部排序和写文件的朴素实现。

首先介绍我们第一个版本多线程的主体流程，接着分析如此实现的具体步骤和原因。我们这个版本是在选择了 使用多线程实现桶排序的基础上 增加了压缩 这个环节。

我们的初步主体流程设计为:

• 选取一定量数据进行采样，获取主键大致范围
• 生产：包含解析文件、数据压缩与分发
• 由一个线程解析 csv，并将初步解析出的 obNewRow 统一放入一个无锁队列中。
• 由 x 个生产者去取出 new row，做进一步的解析和压缩。
• 将采样获得的主键大致范围去分割成互不重叠的范围，一个独立的范围就是一个桶，将属于不同桶的行在压缩后分发到不同桶对应的无锁队列中。存在几个数据范围，也就是几个桶，就有几个无锁队列。