摘要： 在多路归并的排序中，比较次数对全体排序的耗时影响很大。本文首要介绍在 Paimon SortMergeReader 的多路归并完结中，运用 LoserTree 替换堆排序算法，削减多路归并比较次数的规划思路以及取得的功能收益。首要包括以下几个方面：

1. 布景介绍：介绍 Paimon 中读取数据的原理及优化思路；
2. 多路归并算法：介绍堆排序和 LoserTree 的完结原理，并对算法复杂度进行剖析和比照；
3. 计划规划：剖析在 Paimon 中运用 LoserTree 存在的问题，并提出一个基于 LoserTree 的优化完结；
4. 算法证明：对新的完结算法进行了正确性剖析和证明；
5. 功能收益：介绍在全体完结落地后经过基准测试取得的功能收益。

一、布景

在 Paimon 的 SortMergeReader 中，会对多个 RecordReader 回来的 Key-Value 进行读取，并将相同的 Key 运用 MergeFunction 进行兼并，其中每个 RecordReader 的数据是有序的。整个读取进程实际上是对多个 RecordReader 的数据进行多路归并。在归并进程中，数据之间的比较次数越多，全体排序耗时越高。

多路归并的算法首要有堆排序、胜者树和败者树等。在这三种算法中，堆排序每次进行堆调整都需求和左右子节点进行比较，比较次数为 2logN，而胜者树和败者树调整时的比较次数都是 logN，区别是胜者树需求和兄弟节点进行比较并更新父节点，而败者树只需求和父节点进行比较，访存次数更少。目前在 Paimon 中默认运用堆排序完结 SortMergeReader，因而考虑运用 LoserTree 削减比较次数，在进行很多数据的读取时削减比较次数，然后进步功能。

二、多路归并算法介绍

多路归并算法首要用于外排序，首要依照排序-归并的策略进行。当需求处理的数据量非常大，内存无法全量装入时，会将这些数据先组织为多个有序的子文件，然后再对这些子文件进行归并。在 Paimon 中，每个 RecordReader 现已是有序的，因而咱们只需求进行归并流程操作。下面会首要对堆排序和 LoserTree 算法进行介绍，并对两者间的功能进行剖析比照。

2.1 堆排序

堆排序是以堆作为排序的数据结构规划的算法。堆是一棵彻底二叉树，依据父节点中存储的值是否都大于或小于子节点的值，又分为大根堆和小根堆。以小根堆为例，排序进程分为建堆和堆调整两个进程。在整个排序进程中，如果父子节点进行比较后发生了数据交流，那么会发生自顶向下的调整，这种调整每次都需求和两个子节点一起进行比较。

1. 建堆

假定有 5 个待排序列，第一步需求将这 5 个待排序列的依照头元素的大小调整为小根堆，调整的次序为自底向上。

1）首先调整 Node4 节点；

2）然后调整 Node3 节点；

3）调整 Node2 节点时，因为比父节点 Node0 大，因而不需求调整；

4）持续调整 Node1 节点，因为 Node1 比 Node0 节点小，首先需求和 Node0 交流，然后再持续向下调整。至此，小根堆构建完结。

2. 堆调整

每次排序时会从头节点取出当时最小的数据，将对应序列的下一个元素放到头结点，然后再自顶向下不断进行调整。每次向下调整时需求和左右两个子节点一起进行比较，选出最小值。

3. 复杂度剖析

假定待排序列数为 N，待排元素总个数为 n，则：

1）空间复杂度为 O(N)；

2）全体排序完结的时刻复杂度为 O(nlogN)；

3）单次调整的时刻复杂度为 O(logN)，因为需求和两个子节点都进行比较，因而单次调整的比较次数为 2logN。

2.2 LoserTree

LoserTree 也是一种常用于归并排序算法中的数据结构，它也是一棵彻底二叉树。在这棵彻底二叉树中，叶子节点代表待排序列，非叶子节点代表两个子节点中的败者。关于 Node0，代表大局 Winner。相比堆排序，LoserTree 能够简化树的调整进程，因为中间节点中记载的是上次比较的败者，这个败者也等价于该节点到对应叶子节点子树的局部胜者，这样每次从头调整时只需求自底向上不断和父节点比较即可获得新的大局 Winner。和堆排序相似，LoserTree 的排序进程分为树初始化和树调整两个进程。

1. 树初始化

LoserTree 的初始化进程也是从底向上，从后往前进行，失败者成为中间节点，胜者持续向上进行比较。

1）调整叶子节点 Leaf4，因为父节点当时还没有败者，因而设置为 Leaf4；

2）调整叶子节点 Leaf3，和父节点中记载的败者 Leaf4 进行比较，Leaf3 取胜，持续向上。因为节点 Node2 暂时没有败者，因而设置为 Leaf3。

3）调整叶子节点 Leaf2，和叶子节点 Leaf4 相似，将父节点的败者设置为 Leaf2；

4）持续调整叶子节点 Leaf1，和父节点中记载的败者 Leaf2 进行比较，Leaf1 取胜，持续向上，将节点 Node1 的败者设置为 Leaf1。

5）最终调整叶子节点 Leaf0，和父节点中记载的败者 Leaf3 进行比较，Leaf3 取胜，将节点的败者设置为 Leaf0。Leaf3 持续向上和 Node1 中的败者 Leaf1 比较，最终 Leaf3 取胜，更新 Node0 中的大局胜者为 Leaf3。至此，LoserTree 的初始化进程完毕。

2. 树调整

和堆排序相似，每次都会从头节点取出一个数据，区别是堆排序是自顶向下进行调整，LoserTree 是自底向上进行调整。将对应的叶子节点待排序列元素后移一个，然后自底向上不断进行比较，直到到达头结点，得出新的大局胜者。

3. 复杂度剖析

假定待排序列数为 N，待排元素总个数为 n，则：

1）空间复杂度为 O(N)；

2）全体排序完结的时刻复杂度为 O(nlogN)；

3）单次调整的时刻复杂度为 O(logN)，每次调整只需求和父节点进行比较，单次树调整的比较次数为 logN。

2.3 算法比照

依据前面介绍的两种算法的复杂度剖析来看，两种算法的空间复杂度和时刻复杂度相同，区别是比较次数的差异，在进行树调整时，LoserTree 的调整进程更加简略，理论上 LoserTree 能够比堆排序削减一半的比较次数。在元素比较的开支比较大时，经过削减比较次数带来的收益是很明显的。因而在后续的优化计划完结中，咱们选择了 LoserTree 作为排序的基本数据结构。

三、LoserTree 优化计划

在惯例的 LoserTree 完结中，只需求初始化 LoserTree 之后，不断从树顶取出大局 Winner 后，再自底向上对树进行调整即可。在 Paimon 中，SortMergeReader 需求对相同的 UserKey 彻底 Merge 之后才能回来，但同一个 RecordReader 将会复用 Java 目标进行数据回来，而且在 MergeFunction 中也有或许会缓存之前回来的目标，因而咱们在进行树调整时，不能直接将 RecordReader 迭代到下一个数据，这会影响到之前回来的目标。虽然采用深拷贝等办法能够解决该问题，但是拷贝的开支太大，乃至发生负面作用。

因而需求供给一个 LoserTree 的变种完结：在每轮相同 UserKey 兼并完结之后，再对 RecordReader 进行数据迭代。

3.1 前置条件

1. 在 Paimon 中每个 Key 由两部分组成：UserKey + SequenceNumber；
2. 每个 RecordReader 中的数据是有序的，且单个 RecordReader 中不包括相同的 UserKey。

3.2 初始化

和惯例 LoserTree 的初始化方法一起，由底向上构建 LoserTree，失败者成为中间节点，胜者持续向上比较。

3.3 排序

在进行树的调整时，因为目标复用的问题，咱们不能直接将 RecordReader 迭代到下一个数据，需求先对数据进行标记，相似于将 SequenceNumber 置为无限大，再自底向上进行调整，这样具有相同 UserKey 的节点最终都能够被访问到。每次进行树调整时，UserKey 比较的开支比较大，咱们在之前调整 LoserTree 的进程中，与待调整节点 UserKey 相同的节点现已进行过比较，能够直接复用之前的比较成果，因而在节点比较时引入了状况机来做状况转化，避免重复比较。

• 状况界说

总共界说了 6 种状况代表处于不同状况的节点。

1. WINNER_WITH_NEW_KEY：与上一次的大局 Winner 运用不同的 UserKey；
2. WINNER_WITH_SAME_KEY：与上一次的大局 Winner 运用相同的 UserKey，但 SequenceNumber 更大；
3. WINNER_POPPED：大局 Winner 现已被取出处理了，也用于判断在树中是否还有未处理的相同 UserKey 节点；
4. LOSER_WITH_NEW_KEY：和最近一个打败它的 Local Winner 不具有相同的 UserKey；
5. LOSER_WITH_SAME_KEY：和最近一个打败它的 Local Winner 具有相同的 UserKey；
6. LOSER_POPPED：和最近一个大局 Winner 具有相同的 UserKey，而且现已被取出处理了；

• 状况转化

两个节点在进行比较并进行状况转化时，依照以下规矩进行：

1. 每个叶子节点迭代发生的新 Key，状况初始化为 WINNER_WITH_NEW_KEY；

2. 当树的头结点被取出时，对应的叶子节点状况切换为 WINNER_POPPED，能够看作 UserKey 不变，但将 SequenceNumber 设置为无限大；

3. 依据 Local Winner 的状况，在遇到不同状况的父节点时，会进行不同的状况转化：

   1. Local Winner 的状况是 WINNER_WITH_NEW_KEY，父节点的状况是：

      • LOSER_WITH_NEW_KEY： 两个节点需求进行比较并核算出新的 Winner；如果两个节点的 UserKey 相同，败者节点的状况转化为 LOSER_WITH_SAME_KEY；
      • LOSER_WITH_SAME_KEY： 这是一个不或许发生的 Case，因为 WINNER_WITH_NEW_KEY 意味着敞开了新的一轮调整，因而一切和上一次大局 Winner 具有相同 UserKey 的节点都应该被处理了；
      • LOSER_POPPED： 无需比较，父节点取胜并切换为 WINNER_POPED，子节点切换为 LOSER_WITH_NEW_KEY。

        

   2. Local Winner 的状况是 WINNER_WITH_SAME_KEY，父节点的状况是：

      • LOSER_WITH_NEW_KEY：无需比较和转化状况，子节点取胜；
      • LOSER_WITH_SAME_KEY：两个节点的 UserKey 相同，只需求比较两个节点的 SequenceNumber，能够削减比较的开支。胜者切换为 WINNER_WITH_SAME_KEY，败者切换为 LOSER_WITH_SAME_KEY；
      • LOSER_POPPED：无需比较和转化状况，子节点取胜。

      

   3. Local Winner 的状况是 WINNER_POPPED，父节点的状况是:

      • LOSER_WITH_NEW_KEY：无需比较和转化状况，子节点取胜；
      • LOSER_WITH_SAME_KEY：无需比较，父节点取胜并将状况切换为 WINNER_WITH_SAME_KEY，子节点的状况切换为 LOSER_POPPED；
      • LOSER_POPPED: 无需比较和转化状况，子节点取胜。

      

3.4 优化

依照上述算法能够获得一个 LoserTree 的变种完结，但每次从头节点取出一个数据后，不管当时树中是否还有未取出的相同 UserKey 节点，这个节点都需求自底向上从头进行调整一次。极端情况下，当整个树中没有重复的 UserKey 节点时，咱们每取出一个大局 Winner 后，需求做两次树调整：1）将 SequenceNumber 置为无限大；2）将 RecordReader 的数据向后迭代一次。这样 LoserTree 功能反而或许会比堆排序更差。

经过在叶子节点中添加 F****irstSameKeyIndex 字段，用于记载咱们首次打败的相同 UserKey 的节点方位，这样咱们能够快速区分出树中是否有相同的未处理 UserKey 节点，如果有，咱们能够直接将这两个节点的状况进行替换，并从这个方位向上进行调整，然后削减调整的层数。

四、算法证明

在 Paimon 中，LoserTree 的每一轮迭代都会兼并一切相同的 UserKey，然后再迭代相应的 RecordReader。 因而，咱们只需求证明本轮同一个 UserKey 的一切数据都会被回来即可。

Theory：当大局 Winner 的 FirstSameKeyIndex 为 -1 时，树中没有与大局 Winner 具有相同 UserKey 的未处理节点。

Proof：依据 LoserTree 的界说，它的任何一个子树都是 LoserTree。假定当时的大局 Winner 来自叶子节点 A，而且在树中有一个叶子节点 B 和大局 Winner 的 userKey 相同但还没有被处理。A 和 B 的最近一起祖先是节点 C，分别来自 C 的左右子树。

已知节点 A 必定会参加节点 C 的比较，因为节点 B 和节点 A 具有相同的最小 UserKey，那么节点 B 要么成为右子树的 Winner，要么被具有相同 UserKey 的节点击败。最终节点 C 右子树的取胜者一定是与节点 A 具有相同 UserKey 的节点，所以节点 A 的 FirstSameKeyIndex 不能为 -1。 这证明了当大局 Winner 的 FirstSameKeyIndex 为 -1 时，树中不会存在与大局 Winner 的 UserKey 相同的未处理节点。

五、功能收益

基于 JMH 框架，咱们进行了 UserKey 分别为 Integer 和 128 位 String 类型，在不同数量的 RecordReader 和不同数据量上的读取功能基准测试，LoserTree 全体表现优于堆排序，UserKey 的类型越复杂，进行比较的开支越高，优化作用越明显。

• 测试环境：Docker 镜像运用 Apache/Flink:1.16.1-java8，CPU 装备 4 核，内存装备 8G，
• 测试成果：在 UserKey 为简略类型 Integer 时，优化作用大约 10%，在 UserKey 为 128 位 String 类型的情况下，功能能够提高 30% 到 50%。

Integer 类型 userKey

128位 String 类型 userKey

*引用

1. K-way_merge_algorithm：en.wikipedia.org/wiki/K-way_…
2. Github Pull Request：github.com/apache/incu…
3. Apache Paimon 官网：paimon.apache.org/
4. Apache Paimon Github：github.com/apache/incu…
5. Apache Paimon 钉钉交流群：10880001919

*作者信息

李明，字节跳动根底架构工程师，Apache Flink & Paimon Contributor