Page 257 - 《软件学报》2021年第11期

杨良怀 等:面向大数据流的分布式索引构建 3583

T W
T slice T slice T slice T slice
1 1 1 ... 1
2 2 2 2
... ... ... ...
2 2 2 2

t sort t sort t sort t sort
3 3 3 3
t merge t merge t merge t merge
4 5 6 7
S 1
7
S 2 S 3
S 4

t lower-build
Fig.6 Construction scheme of the lower B+ tree
图 6 下层 B+树构建方法
(1) 排序
为了提升窗口数据排序性能,本文进一步切分窗口,将生成的连续分片作为最小排序单元(编号 1 所示).数
据流接收过程中,每接收到完整的分片数据,就并行地触发分片内数据预排序(编号 2 所示).预排序完成后,由专
门的归并线程对有序分片作二路归并排序(编号 3 所示).当接收到完整数据流后,等最后一个分片排序结束后,
就完成了对整个窗口数据的排序.如图 6 所示,整个排序过程与数据流接收高度并行,理想情况下,排序时延迟仅
为最后一个分片的排序和归并时间之和.
当分片内数据量较大时,可采用并行排序法加速排序,从而避免排序任务积压.并行排序的核心思想是:对
数据分段,先并行地对各分段排序,最后通过多路归并方法完成全局排序.在数据量为 m、并行度为 n 的情况下,
其时间复杂度为
O((m/n)log(m/n)+mlogm) (3)
传统的快速排序时间复杂度为 O(mlogm),比较可得:在数据量大、机器 CPU 资源充裕的前提下,并行排序
能提高排序性能;相反,直接使用传统串行排序性能更佳.
(2) B+树预装载
在 B+树框架搭建(S 2 )阶段,B+树内部节点间的关系已完成关联,但是缺少叶节点与流元组之间的关联.流元
组排序阶段最后涉及到归并排序,有序流元组在连续数组空间中存储,故可以在窗口结束时,根据窗口数据量预
先创建数组,并根据码值在数组中的偏移值预装载 B+树叶节点中指向流元组的指针,建立叶节点与流元组之间
的关联,并预计算内部节点码值对应的数组偏移量,赋值阶段(S 4 )能直接根据偏移赋值.预装载完成后,B+树叶节
点与流元组之间的关联也装载完毕.对于 B+树节点的码值,需在数据排序完成后进行,这是最终赋值(S 4 )要完成
的任务.
3.2 下层索引发布

下层索引构建过程包含很多排序、计算任务,会占用大量的机器资源,而索引的查询过程也需要较多的计
算资源.因此,构建节点无法在构建索引的同时提供高效的查询服务,需将下层索引发布到查询节点,由查询节
点提供查询服务.发布过程中,利用第 2.3 节描述的负载均衡方法保证各查询节点负载均衡.查询节点接收到索
引数据后,需将内节点以及叶节点与流元组之间的偏移量关系转换成相应的引用关系,从而恢复下层 B+树索
引.转换过程需要处理每个 B+树节点,时间复杂度为 O(n).但节点间的不存在转换依赖,因此整个转换过程可以
并行化.

3.3 上层索引更新
查询节点接收并恢复窗口 W i 对应的下层索引后,将窗口 W i 的起始时间 t i 和下层索引的引用(t i ,host)构建一