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，做进一步的解析和压缩。
• 将采样获得的主键大致范围去分割成互不重叠的范围，一个独立的范围就是一个桶，将属于不同桶的行在压缩后分发到不同桶对应的无锁队列中。存在几个数据范围，也就是几个桶，就有几个无锁队列。

• 消费：
• 现在不同桶的无锁队列中会有源源不断的生产者向其中放入压缩后的行，每个数据范围对应一个桶，对应一个消费者线程，这些消费者线程从队列中取出数据，进入本范围对应的桶的排序流程：
• 内部排序
• 顺串写文件
• 顺串文件归并
• 计算以及写 sstable

实际上，每个桶对应的都是一个完整并且独立的外部排序。无论是内部排序填满了，启动快速排序；还是快排完成，顺串写文件；再或是归并以及写 sstable。都可以看做一个独立的流程，和其他线程无关。

在阐述完框架基本的流程后，我们现在给出具体对原本的单线程 Demo 程序的改进顺序。

第一步，单线程+压缩。改进从简单到复杂循序渐进。我们第一步做出的主要改进是实现单线程的压缩。在这一步中，我们具体做了如下的工作：

a. 实现压缩算法

实现 ObNewRow 类型到 CompressedRow 类型的压缩算法。

对排序类添加对 CompressedRow 的支持。

b. 在阶段一中，添加 压缩 阶段

替换旧的从 NewRow 到 ObLoadDatumRow 的类型转化阶段。

c. 在阶段二中，添加 解压缩 与 类型转化 阶段

替换旧的 ObLoadDatumRow 到 ObDatumRow 的类型转化阶段。

简单来说，这里用新设计的 CompressedRow 替换原本的 ObLoadDatumRow，减小了数据结构的内存占用量和磁盘使用量。

完成此步改进后，我们的分数大致为 15W 分左右。

第二步，多线程生产。在这一步中，我们首先做出了对压缩阶段做多线程改造的工作，具体来说便是：

a. 提供一个缓冲区队列，将解析文件阶段所生成的 NewRow 放入其中;

b.生产者每个线程都从缓冲队列中获取到 NewRow，对其进行压缩得到的 CompressedRow。

以单个 NewRow 的流程举例，这一阶段的改进可描述为：

第三步，多线程消费。这一步的具体工作主要涉及到对排序做出多线程改进。目的是达成多线程写 MacroBlock。为达成这个目的，我们需要对 Row 划分到对应的 range 。然后对每个 range 做独立的排序和生成 MacroBlock。

a. 为每个桶都准备一个缓冲队列。生产者根据 key 的值划分到不同的缓冲队列中。保证每一个缓冲队列中的 Row 都处于相同的range 中，这样做的目的是使最终生成的 MacroBlock 中的 key 都处于同一个 range。

b. 为每一个 range 都配备完整的内部排序、K 路归并、写宏块流程。

c. 每一个桶分别写 SSTable。

这一阶段的改进可用图描述为：

最后，两阶段的改进合并为：

完成此步改进后，在生产车与消费者都为 6 的情况下，我们的分数达到了 36w 分。

「阶段二」 解耦生产中的解析和压缩，深度加速生产。

(1) 优化原因

完成基本的多线程版本之后，经过一些测试，发现生产的速度远远跟不上消费，而我们生产的流程被这一步「由一个线程解析 csv，并将初步解析出的 obNewRow 统一放入一个无锁队列中」实质上卡住了，因为整个链路上只有一个线程去解析 csv，如果它的速度是整条链路上最慢的，那么它就会成为瓶颈，因此必须加速这一部分。

(2) 优化方式

我们想出的办法是冗余地生产多个文件 buffer，为了让第一步在生产时不再受后续解析 newrow 的速度制约，我们单独搞一个文件的 buffer 队列，专门起一个线程向 buffer 队列中不断地填入 buffer，单位为 2M。而生产者线程每次从 buffer 队列中获取一个完整 buffer，完整地使用该 buffer 去进行解析、压缩等生产工作，使用完毕之后再次从队列中获取下一个 buffer即可。

调整参数，保证当生产者想要获取文件缓冲区去做进一步解析和压缩时，这里总能够提供缓冲区供其使用。

(3) 困难

但这种方式实现存在一个难点：就是原本的文件在解析的时候以 2M 为单位，而该缓冲区结尾不一定是完整的行，在原本相当于单线程连续消费的情况下，就可以在获取下一个 2M 缓冲区时，将上一次最后一行的一部分与下半行拼接起来。但转换成 buffer 队列之后，获取到 buffer 时不能保证能够这样处理了。

(4) 解决方式

针对这个难点，我们解决的方式是挪动文件缓冲区结尾的指针（偏移量），一直向前检索，直到找到第一个换行符为止。让每一块缓冲区都以完整的行为结尾，这样就能解决前面的问题了。

(5) 具体实现

在具体的实现上，体现为以下两步：

a. 构造了两个 NewRowbuffer 的对象池，一个对象池中存放空 buffer 对象，一个对象池中存放满 buffer 对象。

b. 读取文件的线程不停地获取空 buffer 对象将其填满，生产者线程不停地获取满 buffer 对象按行解析压缩。

这一阶段的改进可用图简单描述为：

完成此步改进后，在对象池大小为12 *2M = 24M的情况下，我们的分数达到了 56w 分。且经过日志分析，io 已不再是整个流程的瓶颈。

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

(1) 优化原因

在完成第二个阶段后，速度又上了一个台阶。但在讨论中我们发现，当前的生产者消费者模型，消费者在进行它对应的外部排序时，一旦它对应的缓冲区满了，进入顺串排序以及写文件阶段，那么作为消费者线程它就会停止消费。因而的连锁反应是，该 range 对应的无锁队列会很快被生产者填满。而在一个队列被填满后，很快所有的生产者都会生产出该队列的 range 对应的行，因为无法继续向已被填满的队列中放入，因此所有的生产者都会被阻塞。

(2) 优化方式

而我们要解决这个问题，想出的办法就是令生产者每个线程对应的 buffer 一分为二。原本的设计中，被划分出来的单个桶对应的数据范围由一个线程从头到尾完全负责。而现在，我们单个桶对应的那一个消费者线程将只负责将压缩后的行放入缓冲区以及内存中的排序。

一旦排序完成，即将对应排好序的缓冲区 buffer0 封装成一个任务发送给它对应的线程池，该线程池负责生成一个线程来将该排序好的缓冲区写文件。而由于我们已经「令生产者每个线程对应的 buffer 一分为二」了，那么其中一个 buffer0 交给线程池去写文件，生产者主线程可以继续利用剩下的缓冲区 buffer1 继续去做 memcpy 以及内存排序，一旦满了就再次发送任务。

当然这里应该效仿第二阶段的优化，用池化的方式进行优化，但是由于此时已经接近比赛尾端，并且 ob 的 ObTmpFile 并不支持多个线程同时写一个临时文件的不同偏移位置，因此只能为了实现方便，每个桶对应的数据范围只有两个 buffer。可以说如果也实现一个队列一定是比两个 buffer 性能要更好的。

(3) 具体实现

落在实现上，可以简单地概括为：

a. 现在每一个消费者又内嵌了由两个线程组成的线程池。其中一个线程负责拷贝数据以及排序，一个线程负责落盘。

b. 在完成该桶的内部排序后，线程池关闭，进行外部排序。

这一阶段的改进可用图简单描述为：

在完成这一步及其余改进后，我们的分数达到了 61w 分。

调整中的迷思

此处在观察和计算微观时间之后做了一个小调整，但宏观上变成了负优化，原因目前仍未知。介绍如下：

1G文件中一个桶对应的各种操作时间为：

据分析，针对同一批数据，完成一次 memcpy 花费的时间：排序时间：写文件时间 = 3：1：6。可以看出即使是 memcpy+内存排序 的全部时间依然小于写顺串文件的时间。为了尽量让两个线程工作的重叠程度变高，因此尝试将排序前置，由主线程完成。也就是原本的主线程只做 memcpy + 辅助线程做排序以及写文件 变成了主线程做 memcpy 以及排序 + 辅助线程只做写文件。

理论上来说该 range 消费主线程与线程池中的重叠程度会变高，在主线程完成第二次排序的时候，辅助线程的写文件应该基本完成，也就不需要主线程等待太长时间。如果不将排序交给主线程，那么辅助线程做的事情更多，相当于主线程在这个基础上要等待更久的时间才能将任务分发出去，进行下一次工作。

但经过实际平台的多次测试，这却是一个负优化，原因目前还没有想通。有可能是其他部分慢下来了，多线程的工作由于环节复杂、线程之间互相影响，因此有时难以得到直接的原因。

9.1.2 线程池

我们想在 ob 内部用上多线程，一开始的尝试是用一些很简单的第三方线程池。我们基本调研了所有的公开线程池，但是较为复杂的线程池想要将其容纳进 ob 的框架对比赛而言有些麻烦，所以选择了一个很简单的实现。但无论是内存池还是线程池，第三方的框架想在 ob 中使用都需要一些调整，比如设置线程局部变量等。

官方指导的时候推荐我们直接用 ob 的线程池，改一下他的 run1 函数，直接用就行。ob 本身还有一个 DAG 框架，但是整体看起来很复杂，他的简单线程池也足够我们使用，所以最终用的是他的 ObThreadPool。

9.2 压缩

压缩是除了多线程优化外对外部排序最有效的优化方式。

在压缩的最开始，我们必须要强调，压缩确实为我们的整体流程带来了巨大的收益。但即便是相同的压缩算法，我们前后不同的实现在效率上也有着数量级上的差异。因此我们必须极其重视我们实现本身的技巧和原则，重视优化，才能保证效率。

9.2.1 实现原则

首先，减少内存分配的次数。尽可能不去做内存分配，使用内存池，尽量复用内存。由于内存申请本身耗时是比较大的，并且 ob 没有采用 TCMalloc 等效率较高的方式，它的默认的 obmalloc 分配比流行的这些要慢一个数量级，而如果采取它提供的较为快速的 ArenaAllocator，它的问题又在于释放的时候不能够部分释放，只能够将一个整个分配器分配出去的空间一次性完全回收。也就是说用它确实快，但会存在内存空间的浪费，而我们的内存空间相当有限。在我们较小内存总量的限制下，不得不减少内存分配的次数，精打细算同时节约内存的分配。尽一切可能去减少内存的分配，比如我们多个列属性假设会存在13次内存分配，那么我们 估算出分配总大小可能的上界 后，直接申请估算上界大小的空间作为简要内存池，一个游标标记当前指向的位置，这样就可以将13次分配简化为一次分配。降低分配的开销。

其次，减少标准库容器的使用。在原本的压缩流程中，我们使用了大量的标准库容器，如 string、vector、bitmap。但实现完成后发现他们对应的开销都非常大，大到不能接受的程度，其中最主要的开销往往在他们的 [ ] 运算符、push_back 以及析构函数，析构函数是其中开销最大的。这时候回看 ob 的代码风格，ob 本身不去使用全部的标准库，最主要就是内存的管理标准库往往不可控。我们也在这里上了一课，就此在后续全部编码过程中，也基本完全舍弃了标准库容器的使用，采取 ob 提供的容器以及一些自定义的数据结构等，来规避标准库巨大的析构开销。

然后，减少未知逻辑函数的调用。在关键路径上调用任何函数时必须了解其相应开销与底层大致实现。

例：sscanf (input.c_str(), "%d-%d-%d", &y, &m, &d);diff_day = difftime (mktime(&t2), mktime(&t1)) / 86400;

最后，尽量使用位运算。

9.2.2 主要参考资料

关于压缩对于外部排序的意义不再赘述，其目的都是在较快的压缩解压情况下，尽一切可能减小磁盘 io 的数量。而我们的压缩方法主要参考的部分资料如下：

• OB 本身的压缩方式
• DUCKDB 的压缩方式
• 《字典压缩以及 Quadgram 等方法的比较》https://sdhz5n014f.feishu.cn/wiki/wikcn1P0MgViVXSvI9bVMH8rNvb#T0EQdAukQoyu86xMFWJc5Z7vnkd
• 《轻量级压缩》https://sdhz5n014f.feishu.cn/wiki/wikcn1P0MgViVXSvI9bVMH8rNvb#DmWcdWGCaoSAqIxc6PUcrn0Unib
• 《FSST》https://github.com/cwida/fsst/raw/master/fsstcompression.pdf

简要介绍一下 OB 的压缩方式（来源：https://xie.infoq.cn/article/4ae24d7810358770461290462）：

OceanBase 中同时支持不感知数据特征的通用压缩 (compression) 和感知数据特征并按列进行压缩的数据编码 (encoding)。这两种压缩方式是正交的，也就是说我们可以对一个数据块先进行编码，然后再进行通用压缩，来实现更高的压缩率。OceanBase 中的通用压缩是在不感知微块内部数据格式的前提下，将整个微块通过通用压缩算法进行压缩，依赖通用压缩算法来检测并消除微块中的数据冗余。通用压缩的优点是对被压缩的数据没有任何假设，任何数据都可能找到模式并压缩。但对于关系型数据库来说系统对数据库内存储的结构化数据有着更多的先验知识，OceanBase 认为利用这些先验知识可以对数据进行更高效的压缩。OB 实现了单列数据的 bit-packing 编码、字符串 HEX 编码、字典编码、RLE 编码、常量编码、数值差值编码、定长字符串差值编码，同时也创新地引入了列间等值编码和列间子串编码，能够分别对数据库中一列数据或几列数据间可能产生的不同类型数据冗余进行压缩。

综合这些轻量级压缩方式对字符串采取哈夫曼压缩等字典压缩算法的尝试以及一些其他的思考，就组成了我们最终压缩的实现。

9.2.3 压缩具体实现

具体而言，我们综合了 OceanBase 与 DuckDB 的方式，在数据采样的时候采取一些统计对数据进行先验分析，一旦达到了某个指标即对某列数据做与数据分布有关的压缩。如果没有匹配到任何一种单列的轻量级压缩，则不对该列进行压缩。

9.2.4 采样压缩流程

（1）首先针对数据进行采样，由于数据本身已经 shuffle 过，因此不需要手动打乱。

（2）采样过程中记录每一列的特征，进行指标统计。

（3）一旦达到轻量级压缩算法对应的预设条件，则令该列选择该方式进行压缩。

（4）一旦后续的数据不符合前面预设的估计，就必须全部数据打倒重来。因此采样的预估范围必须留下余地。

我们采取的轻量级方式有以下几种。

9.2.5 轻量级压缩 / 数据编码

9.2.5.1 差值编码

我们会对一行数据中出现的日期列，计算出它到 1970-01-01 的差值，将这个非负整数作为它的压缩结果。数值差值编码主要用来对值域较小的数值类数据类型进行压缩。对于日期，时间戳等数据，或其他临近数据差值较小的数值类数据，可以只存储最小值，每行存储原数据与最小值的差值，这些差值通常也可以通过 bit-packing 压缩。

9.2.5.2 bit-packing / hex

我们同时也用到了 bitpacking。bit-packing 和 HEX 编码类似，都是在压缩数据的基数较小时，通过更小位宽的编码来表示原数据。

「bit-packing」比如对一列 int64 类型的数据，数据的值域在 [0, 7] 之间，这时我们可以通过存储低 3 位数据来表示元数据，减小不必要的全 '0' 高位数据的存储。

「HEX」或者对一列字符串类型的数据，如果所有字符的基数小于 17，那么可以将出现过的每个字符映射到[0x0, 0xF]内的一个 16 进制数上，这样可以用一个 4 位的 16 进制数来表示原字符，减小每个字符编码后的存储空间。

而且这两种编码可以与其他编码叠加，对于其他编码产生的数值或字符串数据，都可以再通过 bit-packing 或 HEX 编码进一步去除冗余。

我们会探测数字类型的值域/基数范围，从而使用 bitpacking。同时对于字符串的压缩也结合了 hex 编码与变长编码，对 l_comment 列本身进行压缩。但对字符串的压缩效果并不显著。

9.2.5.3 字典编码

这里指的不是字符串中的字典编码。

而是对于任何一列数据，如果在采样统计的时候发现它只有小于某个常数值的可能性，就会采取字典编码的方式，将采样数据中所有的可能性作为枚举，只存储对应的数字即可。

其中有些压缩因为速度太慢、优化效果不明显最终被舍弃掉，后面会继续讲一讲。

9.2.6 字符串压缩

a. 哈夫曼压缩

b. 变长编码

c. smaz

d. shoco

e. unisox2

f. FSST

而这些字符串压缩优化效果都不明显，均会在后面做介绍。

10. 其余优化

10.1. 减少归并路数 「对 demo 直接优化」

最初的时候看到大家几天就有分数了心里还挺焦虑的，后面尝试调整了一下内部排序的时候 membuffer 的大小，发现这样就直接有一些提升，我们也有成绩了。

优化原因是，直接扩大 membuffer 的大小即能提高成绩的原因分析如下，根据观察及粗略的计算：csv 中数据在膨胀率大约 4.3 倍。

测试平台使用的 37G csv 文件在进入内存后经过解析和转换，在内存中的 ObLoadDatumRow 膨胀到 160G 大小左右。经过序列化落盘到磁盘上的文件甚至将超过 160G。Demo 中一趟排序的的缓冲区大小被设置为 1G，因此 160G 的数据将会生成160个顺串，在外部排序环节需要 160 路的归并排序。增加排序缓冲区大小，相当于减少了归并路数。如将缓冲区大小调整为 8G 则只需要 20 个顺串，这将在常数级别上优化外部排序所需时间。在单线程的情况下，这种参数的调整从结果看起来影响是很大的。但后续在有效压缩以及多线程生产消费的情况下，这一点的影响就不是很明显了。

在分数方面，在简单的改变内部排序缓冲区大小后，我们的分数分数由最初的 7W 分变为了 9w 分。

10.2  排序优化

10.2.1 比较器的优化

这里我们参考 DuckDB 的实现。DuckDB 的使用场景是将子句中的所有列编码 ORDER BY 为一个二进制序列，通过简化比较器来提高排序性能：直接使用 memcmp。二进制字符串是固定大小的，因为这使得它在排序过程中更容易移动。编译器将为单个函数调用生成高效的汇编，甚至自动生成SIMD 指令。这解决了使用复杂比较器时的函数调用开销。因此我们将主键拼接就使用了这种做法，令两个主键拼接到一起，使用 memcmp 来作为比较器。

10.2.2 最后一次排序不写出文件

在外部排序中，对于最后一趟的数据我们实际上不需要将其写出到文件中，让它保留在内存中即可，和其他的顺串文件一起再用堆去排序，这样就可以少一趟顺串的读写文件。

10.2.3 指针排序

Pointer算法: 为每条数据记录生成一个指针，在排序的过程中，我们只修改指针的指向，数据本身不会被挪动。

Key/Pointer 算法: 为每条数据记录生成一个Key + Pointer的Pair，排序的时候只根据Key进行排序就好了，数据本身不会被挪动。

Key-Prefix/Pointer 算法: 为每条数据记录生成一个Key的前缀 + Pointer的Pair，之所以说是Key的前缀是因为这里只会提取Key的一部分，因此在比较的过程当中如果两个Key-Prefix是一样的话，我们不能认为Key真的一样，还需要去数据里面把完整的Key读出来进行比较，可能会产生额外的开销。

Record算法: 直接对原始数据进行比较/挪动。

这几种算法的性能对比如下表:

总结来说如果要比较的Record很小(小于16 Bytes), 那么推荐使用Record算法，否则的话如果 Key-Prefix 的区分度很高，并且Key-Prefix + Pointer是Cache Line对其的，那么使用Key-Prefix/Pointer算法。

demo 本身已经采取了 Pointer 算法，我们尝试了 Key/Pointer 算法，能够省下一次指针访存的时间，直接排序。

10.2.4 调研更快的单线程排序

针对内存排序，由于 memsort 在图上也是相当大的一部分，大约 3%，所以也有探索是否存在比标准库的 std::sort 更快速的排序。

经过一些调研，GridSort 以及多元素比较下的基数排序都进入了考虑范围，可惜 gridsort 在常规的真随机情况外才基本优于快排，尤其是部分有序的情况表现更好，但我们刚好是随机分布的情况，因此没什么用。

10.3. 优化采样估计，保证非负优化的负载均衡

10.3.1 优化原因

在划分 range 的时候，如果我们根据采样取得的数据范围直接均匀地分给每个消费者线程，那么如果边界估算不准确，最后一个线程实际分配了比其余线程更多的任务，那么它就会成为整体的瓶颈和短板。

与其让不明确的边界对应的最后一个线程多做一点，不如让他少做一些。

10.3.2 优化方式

只要我们令估计的总体数据范围大于实际的数据范围，那么相当于最后一个线程对应的实际负责的数据就会变少，它少做的任务会分给其他线程们，这样整体而言由于总线程数量较多，其他线程不会增加太多负载，而又能保证最后一个线程的负载较小，不会成为短板。这也是一个比较重要的考虑。

10.4. 保证磁头顺序读，利用系统预读机制

10.4.1 优化原因

我们在优化了生产之后（将 buffer 放入 buffer 队列中），保证了每个 buffer 都以完整的行为结尾。但对于磁头而言，由于我们调整了磁头偏移（将上次读完的偏移量移动到了行终止符的位置），导致每次不再是顺序读了，也就是说每次的预读不再有效。

因为预读都是为顺序读预备的。虽然磁头仅仅是移动了几个字节的位置，但这样就会浪费掉系统每次向后连续预读的 2M 数据。

10.4.2 优化方式

我们的处理方式是依旧找到从后向前的第一个行分隔符，将从那开始直到当前磁头位置的字符串 memcpy 到一个专门的 char 数组中，而保持磁头偏移量不变。在下次从文件中获取下一个 buffer 的时候先 memcpy 该半截字符串到下一个缓冲区开头即可，就能保证可以利用预读的空间。结果来看有较大提升。

改进前：

改进后：

10.5. 尽量减少中间数据结构的产生和销毁

10.5.1 优化原因

整个旁路导入的过程中会有多个阶段间的数据流转，每个阶段会将数据包装成一种数据结构，多种数据结构之间的转换十分耗时，我们最终几乎只依赖压缩后的 CompressedRow 类型和写入 sstable 需要的 ObDatumRow 类型，尽可能地减少其余数据结构的产生和转换，相对减少了开销。

例如，解析 csv 文件，从数据 buffer 中解析出 ObNewRow 的过程中，是先将一行数据的每列信息根据列分隔符 '|' 解析成一个个字符串，存储在 FieldValue 数组中，再将 FieldValue 数组中的每个字符串（即该行数据某一列的信息）构造为 ObObj 类型，多个 ObObj 数据最终组成一个 ObNewRow。后续可以利用 ObNewRow 进行压缩、类型转换等工作。

10.5.2 优化方式

其实从中可以发现，构造 ObObj 的过程实属冗余，FieldValue 数组已经存储了我们需要的全部数据，可以直接利用 FieldValue 数组做压缩生成我们需要的 CompressedRow，这样就去掉了 ObNewRow 的生成和销毁过程。

当然，从设计上来看，生成 ObNewRow 无疑会使得代码的可读性更高、代码风格更好，但是毕竟是比赛，能做的优化都要做到。

10.6. 自定义内存池和定长的内存分配器

10.6.1 优化需求

具体而言，我们有两个需求：

需求一：函数内部由本次函数调用使用的小内存池，空间小，不需要长期存在。

需求二：存放桶中对应的分发数据的内存池。需要空间大，需要在内存中驻留时间长。

10.6.2 优化原因

OceanBase 本身的 ArenaAllocator 最小申请单位是 8K，而且不能做释放一小块内存，他只提供 reuse 和 reset 两个方式，逻辑释放掉某一小块是没有真正释放空间的。只能够将整块 8K 空间一次性全部释放掉，不符合我们的使用场景。因此我们需要实现自定义的高效内存池。

同时，直到最后我们也没有掌握 ob 定长分配的 ObSmallAllocator 如何使用，用到我们的项目里都会导致项目直接崩溃。因此不得不自己实现一个定长的内存分配器。

10.6.3 优化方式

针对函数内的内存池：我们选择在函数中直接利用 char[ ] 数组的方式做预估空间的申请。因为我们能预估出需要空间的上界，由于使用的是小空间，而同时栈分配比堆分配快得多，所以选择了使用 char 数组的方式，而非 char* 去申请空间。由一个游标去记录下一块分配的内存首地址，连续分配即可。

针对存放桶数据的内存池：由于 obMalloc 里面有锁，并且经过测试发现直接使用 malloc 会被 ob 劫持（同名函数劫持），会自动将 malloc 替换为 obMalloc，所以我们绕过了 ob 的劫持，自己申请了一块内存做内存池，用于定长的块分配，相对于原生的 malloc free 有相当大优化。

10.7. 短字符串压缩

先给结论：使用调研得到的成熟短字符串算法进行压缩优化，全部失败。因此我们后面继续实现了 基于字典的哈夫曼压缩 和 变长字符编码压缩。

10.7.1 优化原因

通用压缩算法往往不能压缩短字符串，对于大部分短字符串而言，用通用压缩算法压缩后反而还可能超过压缩之前的长度。因为通用压缩算法维护了用于压缩解压的专门相关数据结构，而这些数据结构的长度超过了被压缩短字符串的自身长度。

10.7.2 优化方式

因此，除了哈夫曼压缩之外，我们同样调研了许多专门针对短字符串的压缩算法，如 smaz、shoco、unisox2 算法，以及 FSST 算法。

这些均是在比赛的最后阶段做的尝试，但使用过后基本上整体并无效率的提升，简单介绍一下。

smaz：是不能修改字典的针对通用 ASC 码的短字符串压缩，一般对英文文本有比较好的压缩性能，压缩性能在每秒十万，解压在每秒百万量级。

shoco：是能够训练字典的，压缩率很烂的算法。他的优点是压缩解压在每秒百万量级，快速压缩，是三者中最快的。

unisox2：是专门对时间消耗不敏感的短字符串压缩需求提供的算法。压缩性能在每秒万条数据的量级，解压在十万量级。

前两者都是专门针对短字符串定制的压缩算法，压缩比都比较低，速度相对而言较快。而unisox2 本身也是针对短字符串的算法，压缩比例相对于前两者而言要高不少，但是因为速度要慢一个量级甚至更多，所以短暂尝试后只在代码框架里实现了前面两种算法。

至于压缩比低，这是不可避免的，短字符串原本就缺乏信息，无法像块一样有足够的重复信息、模式可供压缩。

我们有对 smaz 尝试去修改它内部的固定字典，不过由于作者没有放出来生成其内部快速哈希表的脚本，最后也没能成功根据 lineitem 的内容去训练它的字典。而 shoco 的预置字典倒是训练成功了，但二者实现后在测试端均无收益。

而 FSST 算法是一个很新的算法，他的全称是 Fast Static Symbol Table (FSST): fast text compression that allows random access ，性质非常诱人。

它不是基于块的，因此可以在不触及压缩块中周围数据的情况下解压缩单个字符串。与例如 LZ4（基于块）相比，FSST 进一步实现了相似的解压缩速度和压缩速度，以及更好的压缩比。

这意味着我们可能将所有数据先用现有的全部压缩之后再使用 FSST 算法进行压缩，将其作为通用压缩的方式进行两步压缩，进一步缩小压缩后的数据大小，而且解压不影响速度！

但这个算法比较复杂和庞大，最终没能把它融入到 ob 的代码框架中。

10.7.3 短字符串压缩算法对比

10.8. 实现哈夫曼压缩，速度过慢

关于压缩本身，由于 lineitem 表最后一列为 l_comment，长度相对长，而且文本重复率高，所以很自然地想到了使用哈夫曼等一类字典压缩去做关于这一列的压缩。而在完成后发现压缩比率非常高，单纯这一列能够压缩到压缩前大小的 20%，可惜它花费的时间太长了，即便能提供如此高的压缩比，额外花费的时间实际上更多。因此我们不得不放弃哈夫曼压缩。

• 哈夫曼压缩最主要缓慢的点在于字符串的哈希，我使用了 unordered_map，里面用字符串作为 key，而字符串作为哈希的 key，致命缺点就是速度太慢，它必须按照整个字符串去计算。使用其他的哈希算法也没能提升太多。
• 中间也尝试利用了 128位的整数将字符串整个做 memcpy 用作哈希值，然后字符串之间比较用 memcmp 来比较。觉得会比 murmurhash 快不少，但实际上还更慢了。也尝试了其他针对字符串的哈希算法，都不够快，调研没有找到达到在这里兼顾速度与压缩比需求的哈希算法。

当然，可能是我的哈夫曼实现效率太低导致的，如果有更高效的实现我认为字典压缩对重复度比较高的文本仍旧能够带来比较高的收益。而其他的字典压缩往往是通用压缩，速度较慢，同样放弃这些方式。

10.9. 字符编码压缩

依然是针对最后的 l_comment 进行压缩，采样统计观察到：所有字符的可能性只有26个小写字母加上8个标点符号，无法用5位直接压缩，但可以用变长的编码来将 asc 码进行压缩。

我们可以采取 5 / 7 位变长编码。总共有 34 个字符种类，我们将字符按照出现频率降序排序。

• 如果对应前31个字符的话，就去五位对应的编码数组里面取出来存入。而如果不是这31个之内的话，就存入11111 然后再存入接下来的两位，去标记本字符是哪个。
• 频率较低的字符使用 7 位编码，其余用 5 位。

这样的好处在于，虽然一共有34个字符，但我们不需要用 6 位编码去存每一个，在绝大多数情况下是 5 位，而只有少数情况下才是 7 位，节省下了很大空间。

针对原本 csv 一个字符占据8位的情况，基本上可以做到压缩后的大小是压缩前的 5/8，省下37.5%的存储空间。不过我们的几个压缩在服务器上效果有所体现，可提测环境下并没什么收益。

10.10. 有锁/无锁数据结构的调研和选择

最初我们使用的是自己实现的无锁队列，在低数据量低并发情况下性能良好。但无锁队列在高并发的情况下表现不如 ob 提供的 ObLightyQueue，我们自己的无锁队列仅仅是使用了固定的睡眠时间，而 LightyQueue 使用了条件变量来唤醒。这可能是性能差别的主要所在。

无锁的数据结构实际上是将内存中的锁竞争放到了总线上，实际上它的开销未必很小，无锁数据结构在某些场景下可能是一种性能陷阱，使用无锁数据结构必须深入了解它在各种情况下的表现才能放心使用。

10.11. 采用多次读文件，每次只读部分值域，让每个桶需要排序的数据能够完全放在内存中，不需要落盘中间文件。

这一条优化能够优化的「根本前提」是「读比写快很多的情况下，多读少写是有收益的」。

10.11.1优化原因

在给的服务器上，由于曾经申请了服务器升级，导致我们在升过级的服务器上测试出的读写速度有问题，我们得到了这样的错误信息：即在测试环境上，读磁盘的速度是写磁盘的五倍。

在压缩率较高的情况下，或者读速度是写速度几倍的情况下：可以实现读两或三次，而无需落盘中间文件的策略。在这个基础上，我做出了「多读几次文件，完全不写顺串文件」是一个大优化，这样的判断。

10.11.2 优化方式

简单来说，这个策略就是在压缩率较高的情况下，可以实现读两或三次，而无需落盘中间文件的策略。如：第一次读文件时，只留存 key 为前一半范围的行做处理。第二次读文件时，留存 key 为后一半范围的行做处理。

具体来说，多次读文件是指，依照我们的原本划分桶范围的方式，将每个桶对应的数据范围进一步缩小为原本的二分之一、三分之一等等。

这样因为数据本身相对均匀分布，所以我们将数据范围减小，那么一次读文件需要读取全部文件，但仅仅处理和分析整体的一部分数据（二分之一、三分之一），一旦检测到该行数据不应该本趟处理，则直接舍弃该条数据，继续处理下一行。

在压缩算法的支持下，这样读完一次能够保证对应范围的数据全部存到了内存中而不需要写中间的顺串文件，那么我们就可以直接开启 sstable 的计算与写入了，直接完成这部分数据的导入。然后接下来再读几次文件，去处理剩下部分的数据。

因为综合考虑压缩与读写的速度，在压缩比没有非常高的情况下，如果写的开销是读的数倍，那么意味着我们要尽量避免写中间文件，甚至极端一点，完全不去写中间的文件。只需要简单地考虑一下，如果读两次或者三次文件就可以将全部数据处理完，而不去写中间文件的话。写 1个单位的中间文件，相当于读 5个单位的源文件，即使我全部文件读个两次甚至三次，只要我不用写中间文件，都是正收益（简化了压缩等比例转换，仅为表意）。

这种情况下，多读几次一定是比写中间文件要来的开销更小的。

如果要具体地计算，那么必须依托于能够使用的内存大小、实际的压缩比例以及其他一些具体数据。我们可以确定得到的结论是没什么问题的，但问题在于我们判断基于的信息错了。大概就是因为服务器中途升级导致的测试数据有误，后来重新要了一个服务器，再次测试发现读的速度甚至不到写的两倍，那多读几次就完全没意义了。因此放弃。

10.12. 利用 fadvise 调整系统预读大小

在阅读磁盘优化相关的资料时，我们发现 linux 系统在某个内核版本之后系统默认的每次预读大小为 2M，那么如果我们利用 fadvise、madvise 等方式去告诉内核我们要读的是个顺序大文件，直接提高预读的值，能否提升我们的读文件速度呢？

答案是没什么效果。猜想是系统原本预读调整算法也是类似指数级提升，很快就能提上去。

10.13. 函数内联化/匿名化

我们将短函数尽量实现为匿名函数和内联函数，降低函数调用的开销。部分流程中我们对于多次调用的短函数实现大量使用了匿名函数的方式。针对这部分，我通过简单的测试对于调用频繁的函数，比较使用内联函数与匿名函数的效率差异。最终没有测试出明显差异。

10.14. 优化编译器分支预测

在读 ob 的代码之前，从来没有用过 LIKELY 以及 UNLIKELY 这种宏，看到之后检索了一下作用，大概就是给编译器提示这个分支的可能性高低两极，在写代码的时候也尽量能用就用。

10.15. 压缩流程提前，放在生产者，减少深拷贝的次数

10.15.1 优化原因

我们本来的设计是生产者解析 csv 文件生成 ObNewRow，接着分配一块空间，拷贝 ObNewRow，再将指向这块空间的指针放进无锁队列中，消费者从该队列中获取指针，进行压缩 + 外部排序 + 解压 + 写入 sstable。

消费者需要做的事情太多，而生产者的工作相对比较少，同时 memcpy 太多，还存在一个额外的中间数据结构，这些都是可以被省下来的开销。

10.15.2 优化方式

将压缩从消费者负责变换成生产者负责，可以令我们能够避免消费者负载过重，令生产者消费者负载相对均衡一些。也可以减少深拷贝的次数，原本的 ObNewRow，每一列都要 memcpy 一次，而提前做压缩我们可以省下来十几次 memcpy。

这样我们就不需要分发 ObNewRow 了，只需要 CompressedRow，这也符合了「尽量减少中间数据结构的产生和销毁」这一原则。

10.16. 脚本工具的编写

在整个比赛流程中，对我们整体流程最大的加速和润滑剂就是编写的各种脚本了。将可能重复用到的流程自动化，减少重复劳动，节省了我们很多时间。而且由于本项目的某些配置文件和路径，要基于一些对于不同用户而不同的绝对/相对路径，队友写的示例也让我学到了怎么写这种脚本。

在决赛开始的前几周我们都在一直完善我们的各种脚本、探索 OceanBase 的代码到底应该怎么写。

这些脚本大致有：

• obd 集群的 start / restart / stop
• obd 镜像软链接的修改
• 针对不同大小的 csv 测试
• iostat 的查看
• debug / release 编译 / 部署
• 火焰图生成
• gdb attach
• 单元测试
• 查看 log
• 打印内存分配信息
• csv 解析与文件对比

但有些遗憾的是和 miniob 不同，OceanBase 的代码在格式化之后编译运行会出问题，最终也没有统一格式化，在大家 merge 代码的时候难免会增添不少麻烦。

10.17. 尝试写多个 mini sstable，利用 OceanBase 内部并行的 major merge 去合并，利用上多线程

在最开始阅读 OceanBase 文档的时候，看到内部多个 sstable 在合并的时候，major merge 是默认并行的。想着既然系统的默认行为如此，那我们就利用上。先去实现最简单的情况，直接写入多个 mini sstable，然后启动 OceanBase 的 major merge，先看看这种多线程能够提供多大程度的优化。

但后面去写多个 sstable 的时候，发现这件事对于 OceanBase 底层需要有比较深的理解，而且即便实现了后面在实现我们自己的多线程时又会实际上把做的这一步完全放弃掉，意义不大。因此在花了两天时间依然没有调通这里的代码后就放弃了这一步。

10.18. 进一步减少压缩后数据结构 CompressedRow 的大小

10.18.1 优化原因

CompressedRow 的数据结构的设计会影响深拷贝的时候为其分配的空间大小，以及影响同样的内存空间可以放置的 CompressedRow 的数量多少以及磁盘的总 io 数量。

在外部排序阶段，如果内存中能存放更多的数据先进行内部排序，理论上来说外排效率会提升。

一开始我们采用 char* 存放压缩后的数据，再使用额外的长度变量标识压缩后的数据长度。在 64位机器上，char* 指针占 8 字节，长度变量经过对齐后也占 8 字节，所以，这种设计模式下的 CompressedRow 需要 16 字节来存储（暂不考虑 char* 所指数据的存储大小）。

10.18.2 优化方式

我们使用了下面两种方式优化，两种方式均能够直接减小由于类内数据成员对齐而占用的空间。

方式一 长度变量编码进 char* 进一步减少空间

第一种方式综合一些其他的优化，在服务器上测试后总时间快了将近 20s，但提测的分数并没有明显升高。将长度变量编码进 char* 数据的开始，可以省掉对齐需要的冗余空间。

方式二 柔性数组

第二种方式在具体实现的时候代价是会使程序增加一次全部数据的 memcpy，而提测后的分数也没有明显升高。

结构中最后一个元素允许是未知大小的数组，这个数组就是柔性数组。但结构中的柔性数组前面必须至少一个其他成员，柔性数组成员允许结构中包含一个大小可变的数组。sizeof 返回的这种结构大小不包括柔性数组的内存。参考链接 柔型数组👇https://blog.csdn.net/qianqin_2014/article/details/51123583

CompressedRow 由长度变量 + char data[0]组成， data 只起到占位作用，不占据空间，数据直接存储到长度变量空间后面。

这样设计的好处有两点:其一是在访问压缩数据时可以减少一次指针访存；其二是进一步缩小了 CompressedRow 的大小，省去了 char* 指针存储需要的 8 个字节。

但是，外部排序会将内存排序后的顺串序列化后写出到文件，在合并阶段读入到内存 buffer 中，紧接着需要对 buffer 中的数据反序列化为 CompressedRow 数据结构。

在反序列化的过程中，如果 CompressedRow 是使用 char* 存储数据的，那么直接给 char* 赋值 buffer 中的数据地址即可，但如果 CompressedRow 是使用 char[0] 存储，这里就需要将 buffer 中的数据 memcpy 到 char[0] 占位的地址中，大量的 memcpy 反而降低了外排效率。

简而言之，虽然单条数据占据的空间减少了，压缩的比例更大，但增加的一次 memcpy 导致最终没有整体收益。

11. 调优方式
11.1. 火焰图的针对性优化

火焰图是性能调优的大杀器，它基本是我们本次比赛最重要的性能调优工具。我们通过火焰图不仅可以观察函数的预期表现、占用时间，也可以观察不同线程的负载是否均衡，分配数据是否均匀。从图上能够很直观地得到各种信息。

Perf

我们在使用火焰图的过程中，会发现偶尔出现 unknown 的情况。经过一些探索，发现修改火焰图的生成选项，dwarf 以及 lbr 都能够更加详细地解析函数来源，但弊端在于会修改火焰图原本的形态，图会看起来怪怪的。而直接从 perf 的数据中去检索对应的 unknown 函数也可以找到该函数的实际调用者，所以原生的 perf 数据也是很重要的。

基于火焰图的优化实在是太多了，我们在整体流程中叙述，而不在此特意阐述。

一个消费者对应的火焰图部分

6生产者，24消费者的全局火焰图

11.2. 使用 iostat dstat 以及其他 cpu、磁盘分析工具对流程做分析优化

除了火焰图能帮我们分析函数开销之外，我们仍然需要借助其他工具去帮助我们分析磁盘 io 的情况，cpu 在整体流程中的利用率、整体过程分为几个阶段，大概每个阶段是 cpu 利用率低还是 io 利用率低，瓶颈在何处。在这样分析的基础上去考虑进一步的优化点。而我们也初步领略到了这些工具对磁盘调优、整体流程、线程调优的妙用，但只是非常初步的入门。

11.2.1 分析举例  

16G测试文件  6生产者 12消费者

观察到刚刚启动时，存在一个读速度为 500 MB持续时间为 1S 的峰值。且每一次写小文件结束时，都会产生一个 500MB 的读的峰值。这个时候 CPU 占用率为 100%。推测造成 500MB 的峰值的原因可能是两个:一种情况是此时的 io 是内存拷贝的速度，另一种情况是真实 io 的速度。随后测试出，320MB/S的读速度是内部排序消耗数据的速度，同时也是测试环境读速度的上限。500MB/S 是内存拷贝数据的峰值速度。推测生产者的生成 compressed row 的速度大于内部排序消耗 compressed row 的速度（可能是 1.5 倍）。

最开始的前两秒
56 5 36 2 0 0| 458M 192k|1037B 3798B| 0 0 | 32k 47k
59 5 31 6 0 0| 392M 54k| 330B 3340B| 0 0 | 38k 52k

观察：

分析结果；以上图 dstat 生成的 io 日志与 htop 展示的 cpu 利用率为例：开始为 只读阶段，对应代码中读取 lineitem.csv 到缓冲区部分。该阶段瓶颈在读速度。CPU ( 50% ) 和写空闲 ( 0% )过程中存在 只写阶段，对应代码中写出临时文件部分。该阶段瓶颈在写速度。CPU 完全空闲 ( 10% )，读完全空闲 ( 0% )过程中存在 又读又写阶段，对应代码中同时进行排序和写部分。该阶段各方面都不存在瓶颈在最后 写 SSTable 阶段，瓶颈在于 CPU。读 ( 10% ) 和写空闲 ( 30% )

优化考虑：

a. 只读的时候 CPU 没有跑满（50%），考虑随机挑选一些行做哈夫曼压缩；

b. 只写的时候 CPU 完全没跑（10%），考虑将队列中的数据全部做哈夫曼。

但最终这里没有做一些别的优化，没有时间了。

11.2.2 崩溃举例

我们也通过分析工具来观察得到程序崩溃的原因和时间点帮助我们分析。

最后虚拟内存会上探到16G，在这种情况下，程序就会崩溃

11.2.3  iostat 举例

11.2.4 debug 和 release 差异

在对比 debug 编译的结果和 release 的结果时，我们发现同一份代码不仅运行效率大有差异，而且在运行模式上几乎天壤之别。当然优化后的结果大有不同才导致了运行效率的差异，但是一开始着实没有想到在这些 io 和磁盘的监控上也会有巨大的差异，差异大到用一个模式分析出的东西对另一个模式完全没有意义。

11.2.5 内存分析脚本

除此之外，我们为了探索内存的使用和具体的分配，也需要利用 ob 本身的命令去查询 500租户以及系统租户在各个时刻消耗的内存，去探索内存的固有分配，判断内存的使用分配情况是否符合预期。队友还写了以秒为单位分析的脚本画了图，来标记整个时间跨度上各个部分的内存使用情况，不过最后也没用上。

11.3.  使用运行时动态指定参数的形式加速调参

由于代码编译以及部署的巨大耗时，如果我们每次修改了一些参数，都要重新编译部署一遍的话，整体耗费时间是巨量的，这种情况下我们没有办法去进行尽可能多的测试。

因此我们使用了运行时读取 json 文件的方式，在 json 中指定我们需要调整的所有参数，令程序不需要重新编译即可在运行时指定参数来调整设置。因为程序执行是以 SQL 语句启动的，所以只需要在每次运行测试程序前，调整 json 文件中的参数即可。

涉及参数：生产者线程数量、消费者线程数量、外排的顺串大小、每次读文件时单个缓冲区的大小等。

12. 一些没有做的尝试

12.1. 写 sstable 本身的优化

图中是官方提供的 macro block writer 的优化方向。

这部分说起来很有些可惜，最后的阶段我们陷在了压缩的进一步优化，没有在这里投入足够的精力。由于直播答疑的时候说不建议优化这里，很多东西不让动，让动的地方说会非常难写，我们基本就完全没关注这边的优化。以为这里真的任何一个改动代价都非常大，没想到这里藏着一个逻辑上非常简单的巨大优化点。

冯惠分析出了这里可以减少一次 memcpy，但是其中涉及到一个并不优雅的实现，而这时已经到了到最后的时间关头，只剩下不到两天的时间，我们必须在这个优化和压缩的进一步优化之间二选一。由于这个优化还是有一些难度，而压缩看起来简单一些，因此我们选择了压缩路径，希望带来小的分数稳定收益。

但可惜，进一步压缩并没有带来分数进账。

12.2. Cascade 归并 「参考自 DuckDB」

 以下内容引自 DuckDB 文档：

技巧一减少I/O的一个简单技巧是在级联归并排序中以z字形通过块对进行归并。通过以之字形通过块，我们通过合并上一个迭代中合并的最后一个块来开始迭代。这些块可能仍然在内存中，为我们节省了一些宝贵的读/写操作。技巧二在级联归并排序中，我们一次合并两个已排序的数据块，直到只剩下一个已排序的数据块。自然，我们希望使用所有可用的线程来计算合并。如果排序的块比线程多，我们可以分配每个线程合并两个块。然而，当块被合并时，我们将没有足够的块来保持所有线程繁忙。当最后两个块合并时，速度会特别慢:一个线程必须处理所有数据。为了完全并行化这个阶段，我们实现了Oded Green等人的合并路径。合并路径预先计算排序列表在合并时的相交点，如下图所示(摘自论文)。

利用二分搜索算法可以有效地计算出合并路径上的交叉点。如果我们知道交集在哪里，我们就可以独立地并行合并排序数据的分区。这允许我们在整个合并阶段有效地使用所有可用线程。但最后也没有去尝试。主要考虑我们的整体框架相当于每个数据范围对应的桶都在做自己外部排序的合并，只有两个线程可用，并非全局只有一个合并。而且 Cascade 的两个顺串合并内存中如果依然放不下，还要再读写文件，这个开销应该是不可接受的。

13.可能改进的方向

在参与答辩的过程中听其他团队的答辩也收获到了一些新的思路，将比较有效的陈列如下。

（一）SIMD 加速换行符定位

比赛方提示了我们可以使用 SIMD 进行加速，而我找了半天也没有找到具体能利用上的方式，再加上对于这个技术的不熟悉，没有在这个方案上探索下去。而有一个组选择了在行解析转换的阶段，将寻求换行符的操作使用 simd 加速，这确实是个非常好的使用场景。

另外在后续实习面试的过程中，在回答一个 bitset 复制问题的时候，我也意识到可以在这种大规模 memcpy 的地方使用 SIMD 进行加速。和队友讨论，其实比赛中的内存复制环节也可以使用这个技术。

（二）使用循环展开，以及尽可能给编译器提供信息

在比赛时，我没有意识到在 O2 优化的情况下循环展开也能得到收益，如果知道这一点，按照之前写 CUDA 的经验去写这种最朴素的循环展开是很容易的。根本原因是在头脑中缺乏这一块优化的版图，把 CUDA 优化和普通的 C++ 优化隔离开了，其实 C++ 常见优化里循环展开是很常见的。缺乏经验和意识导致我没意识到这个优化。

（三）使用批量操作 get_rows 代替单条操作

这个具体是指在 SSTable 相关的处理中将一个地方的按单条数据操作转换为一个隐藏的批量行操作。

在 OceanBase 的交流活动中，前辈陈述了这样一个观点：做数据库做的最好的人一定是对系统有最深认识的人。而我们没能做出这个优化的根本原因也就在这里，我们没能实际把整个涉及到的模块彻底通读一遍，没有把所有涉及的工具函数和接口都浏览和分析一遍，也就没办法找到这个至关重要的性能优化了。

这给我一个警钟，不能让自己停留在“似乎懂了，好像看完了”的阶段。必须把所有可能涉及到的内容遍历一遍，最好形成文档。

（四）对于顺串对应的中间数据做即时的压缩和解压

当时有考虑二次压缩，但因为我们的外部排序需要 K 路归并，所以觉得使用块压缩算法就不能归并了，因此放弃了这个尝试。现在看来就按照块进行压缩和解压，解压完了再对解压后的小块进行归并也行。

14. 总结

我们的优化不完全总结如下：

14.1. 收获

整个比赛，我们基于火焰图、dstat 等各种分析工具，主要针对外部排序，优化了排序方式以及比较器。优化主体流程中的每一部分，利用高性能的方式去实现压缩解压，尽量减少磁盘 io。做 cpu 以及磁盘调优，将 io 利用率拉满。综合底层的优化原则，以内存池和线程池的方式充分复用资源，做尽可能的优化。

我们针对预读、缓存、io、负载均衡、内存对齐、分支预测优化、无锁数据结构、内存复用等方面进行优化。

从开始对几乎任何一个工具都不了解，没有接触过这种量级的代码，对 ob 一无所知，到综合深入的思考，大量的调研并学习 ob 本身的代码结构和框架，反复设计和调优。我们的收获可以说是巨大的。

最突出的一个特点，我认为是我们多线程前后三个阶段优化的得到的收获。

数据链路多线程优化的根本方式！

综合看我们对于多线程链路的整体优化：

Stage 1 基于多线程的桶排序进行外部排序和写文件

Stage 2 解耦生产中的解析和压缩，深度加速生产

Stage 3 解耦消费中的排序和落盘，深度加速消费

在想到 阶段3 优化的瞬间，我意识到我们的多线程做的优化，每个阶段的根本性质都是相同的，当时我没有意识到这个相同之处究竟应该怎么表达。现在可以说，这个优化就是解耦本身。

我认为，只要存在数据传递，那么就存在生产者和消费者。提供数据方即为生产方，接受数据方即为消费方。

而我们的解耦就是把原本的同步的流程拆分为两个异步的阶段，让一条数据链路上的一个数据传递节点，两边不再产生相互的阻塞。让生产者尽可能地生产，消费者尽可能地消费。

在数据链路中，会存在无数个数据传递的节点，任何一个同步、阻塞式的传递节点都可以利用这种模式来解耦生产消费者，将整体流程进一步异步化，将一条绳子上的无数个绳结分割的同步的绳段全部转化为异步的操作，解放生产和消费速度。

14.2. 不足

整个过程中我们的不足，具体优化方面就是缺乏对于 sstable writer 的思考和优化尝试，而对于整体比赛安排而言也没有能再提高很多的地方了。每个阶段虽然没有做到尽善尽美，但人的局限性限制我们在那个阶段就只能做到那个样子，基本都尽力了。

14.3. 感想

参加比赛的初衷是希望多学习一些东西，如果能拿个名次就更好了。但是最后冲榜离前几名只有毫厘之差的时候，又会觉得不太甘心。

当我们最后时刻完成的，在服务器上一个稳定 20 秒的巨大优化在提测平台体现不出来的时候，感受非常的五味杂陈。因为服务器是和线上平台环境一致的，官方提供了服务器上的运行时间和分数的转换公式，基本上是准确的。

我们最后一个通宵做完的优化算出来应该是逼近 70W了，但线上提测环境没有体现。

来哥说测试机器是这样的，内存方面会有 10% 程度的性能波动，优化是没有办法完全体现出来，有些看运气，如果是独立的物理机就没有这个问题。没得办法，只能再整理其他一些微小的优化点，再利用完最后的提测机会，再尝试一下，度过最后一天。

最后答辩得到的结果与决赛分数名次完全一致，没能实现什么逆转，就此，这次参赛我们以季军身份告终。

那就继续向前吧，步履不停。