oceanbase 2022 比赛复盘

oceanbase 2022 比赛复盘

初赛

初赛在 miniob 上进行

决赛

决赛场景针对数据库的数据导入功能，及将csv文件中的数据导入到oceanbase中存储。业界常见的两种导入方式主要有两种，一种是逻辑导入，就是将csv文件要导入的数据编码成sql语句，然后运行这些sql语句完成导入。第二种方法更为高效，称为物理导入，也叫旁路导入，就是不经过sql接口，直接将数据编码成底层存储的kv格式，直接写入db文件，也就是SSTable，更为高效。而oceanbase目前只实现了第一种逻辑导入，决赛的内容就是实现物理导入的功能，然后尽可能从算法逻辑、cpu、内存、磁盘io各方面进行性能优化，最后根据性能进行排名。

baseline实现

baseline是一个单线程异步导入的实现，主要包括四个阶段：

• CSV文件解析：就是根据csv文件的分隔符一行一行读取数据文件，然后存入buffer中

• ob内部数据结构转化：转为ob内部一种临时的数据格式DatmRow，比如对数据的列进行组，主键数据放在前面，用来方便后续的操作。

• 外部排序：获取转化后的DatumRow，进行外部排序，存储在临时文件

• SSTable文件写入：读取外部排序的结果，写入SSTable

整体上是一个单线程异步io的框架。

优化点

整体多线程框架

首先是利用多线程的优势，充分压榨CPU的性能，整个执行过程分为两个阶段：一是外部排序阶段，二是数据持久化阶段。

整个流程如下：

1. 首先对需要导入的数据文件分段；
2. 多个线程分别对数据的不同段利用 ObLoadSequentialFileReader 并行读取到缓存 ObLoadDataBuffer ；
3. 由于读取的文件格式是 CSV 格式，需要对读取的每一行字符串通过 ObLoadCSVPaser 进行解析；
4. 对于解析完成的数据需要通过 ObLoadRowCaster 转化为 ob 的内部表示 ObLoadDatumRow （涉及数据类型转化等）；
5. 然后根据主键的值，将读取的 ObLoadDatumRow 经过 ObLoadDispatcher 分发到对应的排序线程；
6. 排序线程读取对应的 ObLoadDatumRow 然后通过 ObLoadExternalSort 进行外部排序；
7. 各个 ObLoadSSTableWriter 分别读取对应排序完成的数据并完成写入，它们需要共用一个 ObSSTableIndexBuilder 来构建宏块。

多阶段线程池+dispatcher分发器+sort_queue排序队列（seda架构）

多阶段线程池

将整个流程分成了三个线程池处理，使用ob提供的TaskQueue实现。

线程池一：负责(do_process)解析CSV文件和datumRow转化，然后将转化后的datum_row提交给dispatcher分发器

线程池二：负责从dispatcher中的获取datum_row，然后做外部排序，排序后的结果提交给sort_queue

线程池三：负责从sort_queue中获取排序后的结果，然后提交给sstable_writer写入底层存储

预处理优化

csv文件读取。使用aio prefetch。每次处理数据之前，先发起prefetch请求

get_next_item: wait() + prefetch + process

异步读取可以表示为一个 pipeline()，它包含 prefetch() 以及 wait() 两个阶段。首先，在打开文件的时候发送一个 prefetch() 请求，然后后续每次调用 pipeline() 获取对应的数据，将会首先调用 wait() 等待上一次发送的异步读取请求完成，然后调用 prefetch() 发送下一次读取请求。这样可以很大程度地减少 I/O 等待的事件。这个过程中交替使用两个 file_io_handlers.

异步写入会首先等待下一次写入操作完成，然后发送本次写请求之后直接返回。

外排优化

外排的基本思路是，将数据分块，每个块的数据load进内存，内存排序后写入临时文件，然后取每个临时文件的第一个未处理的元素建堆，做整体的排序。

根据dispatcher的数据分发，每个桶之间是有序的，然后每个线程处理一个桶，对桶内的数据进行排序，持久化。然后写sstable。sstable的写入接口可以传入index参数，这要保证每个写入线程的index和数据顺序一致就可以达到sstable写入并行化。排序后的结果会写入到sortbuffer中，写入线程池再并行写入。

外排分为 ObMemorySortRound 和 ObExternalSortRound，分别是内存排序以及外部排序。

待排序的数据会被不断放入 ObMemorySortRound 的缓存中，每次当待排序的数据到达一个阈值时，将会触发一次排序，然后将排序的结果写入临时文件，并返回一个对该临时文件进行读取的 reader。

由于我们需要排序的数据是一个 int64_t 类型和一个 int32_t 类型的组合，因此内存排序的算法使用基数排序来加快排序速度。

在临时文件的写入过程中，每当写入缓存中的数据到达一个阈值，将会首先对缓存中的数据进行压缩，然后写入压缩后的数据。由于比赛使用的磁盘的性能较差，因此对数据进行压缩，然后写入磁盘将很大程度上减少磁盘 I/O 的等待事件。

在所有数据都已经被放入到 ObLoadExternalSort 中之后，将会产生多个临时文件，每个临时文件内部有序，但彼此之间的顺序是不确定的。因此我们需要构建一个最小堆，每次读出一个临时文件头部的一条记录，然后将其放入最小堆中进行排序，然后输出一个最小堆的根节点。

对于临时文件的读取，由于前面进行了压缩的操作，因此读取之后需要进行解压。

ObLoadDispatcher

dispatcher是为了桶排序设计

• 首先会对数据进行采样划分范围，然后根据采样结果划分成不同的外排桶确定划分点

• 当线程池1解析完datum_row提交给dispatcher后，dispatcher会通过二分查找该条数据所属的桶id，然后将数据交付给对应id的分发队列(push_item)。

• 桶之间的数据大小是有序的，桶内部的数据还需要经过外排才能有序。

我们通过类似于生产者消费者队列的方式，解析线程将会不断把数据写入这个队列，后续外排线程会不断从这个队列中读取数据。队列采用无锁的设计，通过写入指针与读出指针是否重合来判断队列为空或者满。

另外，解析线程写入数据的时候需要对数据进行深拷贝，深拷贝需要重新分配内存，我们将分配内存与深拷贝的过程分开。分配内存需要使用内存配分器，由于 ob 的内存分配器不是线程安全的，因此分配的过程需要加锁；深拷贝直接对各自分配的内存进行操作，因此这一个部分不需要加锁。从而降低了锁的粒度。最后，通过在分配内存的第一个位增加一个标识为，来表示深拷贝是否已经完成。

最后，实际上我们为每个桶分配了两个队列，当写线程写满一个队列时，将会切换到另外一个队列进行写入。读线程读完一个队列，且这个队列已经满时，就会将这个队列的所有内存一次性全部释放。减少了反复内存释放的开销。

sort优化

std::sort 内存排序修改为基数排序

基数排序比基于排序的算法要快，但是需要额外的内存空间。内存换时间。

临时存储文件优化

压缩临时文件，cpu换磁盘io换时间。重新设计了临时文件的存储格式，列存格式，提升压缩率。

内存复用

减少内存使用，可以多开几个线程

写sstable优化

ObLoadSSTableWriter

最后第三个线程池从对应的桶中读取外排完成的数据，每个桶内的数据已经有序，并且桶之间也已经有序，然后分别进行写宏块的过程就行。

写宏块过程涉及数据的编码以及压缩的过程，同时还有对数据生成校验和，这个过程也将消耗大量 CPU 资源。

这个过程是读取一条记录，然后调用一次相应的写函数进行一次写入，实际上可以进行批量写入，读取多条然后进行写入，这样效率更高，更能够利用缓存。

测试环境

8core + 16G + 50G的导入数据

结果

比baseline提升了7倍左右

性能测量工具

整体使用情况

查看系统整体使用情况，各个进程的运行状态

1

top

CPU 使用情况

查看 CPU 利用率

1
2

top -p $(pidof ...)
htop -p $(pidof ...)

磁盘使用情况

查看磁盘读写延迟等情况

1

iostat -x

perf

perf 的大致工作原理是每隔一个固定的时间，在 CPU 的每个核上产生一个中断，在中断发生时，查看当前处理的进程的 PID 和函数，然后再给对应的 PID 和函数附加一个统计值。这是一种采样的模式，我们预期，运行时间越多的函数，被时钟中断击中的机会越大，从而推测，那个函数的 CPU 占用率就越高。

perf 中常用的指令如下：

1. list: 列出当前系统支持的所有性能事件。包括硬件性能事件、软件性能事件以及检查点；
2. record: 收集采样信息，并将其记录在数据文件，随后可通过其它工具对数据文件进行分析；
3. report: 读取 perf record 创建的数据文件，并给出热点分析结果；
4. stat: 执行某个命令，收集特定进程的性能概况，包括 CPI、缓存未命中等；
5. top: 类似于 linux 的 top 命令，对系统性能进行实时分析。

在虚拟机上是不支持硬件事件的，因此无法对硬件事件进行采样分析。

另外 perf record/stat/top 都可以通过 -p 和 -e 选项指定进程以及采样的事件。

分不清事件利用 cpu-clock/cpu-cycles/task-clock 之间的区别。

火焰图

通过火焰图观察程序各个函数的开销：
https://github.com/brendangregg/FlameGraph