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

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

下层索引构建过程中,构建树型结构的时延可表示为 t para +t skltn +t preLoad +t assignKey ,其中,t para 和 t skltn 的计算公式
参考文献[56].下层索引预装载环节,需计算所有节点 key 值偏移,则
⎛ N N ⎞ (m + 1)T N
t preLoad = T M ⎜ W × m + W × m = ⎟ M W (9)
⎝ m 2 m ⎠ m
最后的赋值环节,在 P assignKey 个并行度下,时间开销为
⎛ N N ⎞ 1 2(m + 1)T N
t = 2T M ⎜ W × m + W × m × ⎟ = M W (10)
assignKey 2
⎝ m m ⎠ P assignKey mP assignKey
结合公式(5)~公式(10)可得:排序时延远大于下层索引框架构建时延(t para 和 t skltn 的计算公式参考文献[56]),
且 t para ,t skltn ,t preLoad 与排序并行,因此总的下层索引构建开销为
t buildLower =t sortDelay +t mergeDelay +t assignKey ≈t sortDelay +t mergeDelay (11)
其中,赋值阶段的时间开销远小于排序阶段,排序性能直接影响下层索引构建性能,故分片数 N S 直接决定了下层
索引的构建性能.
4.2 下层索引发布性能评估

下层索引发布的时间开销主要来自节点间的数据传输和树结构的恢复开销,可表示为
t releaseLower =t serialize +t send +t deserialize +t recover (12)
索引发布阶段,发送方需先将其结构数据序列化.根据序列化方式的不同,过程中会写入标识字符,以便于
反序列化相应结构.为了便于理论评估,分析过程中忽略这些字符,并将反序列化和序列化两者的时间开销近似
等价,即
⎛ N N N N N ⎞ 5T N (m + 2 4m + 1)
t ≈ t = 5T M ⎜ W × m + W × 2 + W + W × m + W × m = ⎟ M W (13)
⎝ deserialize serialize m m m 2 m 2 m 2 ⎠ m 2
下层索引传输阶段,若每个树节点序列化后的大小为 S(通过预实验得,子节点数 m=3000 时,S=17KB),则数
据传输开销为
⎛ N N W ⎞
S ⎜ W + 2 ⎟
t send = ⎝ m m ⎠ (14)
810 N× 6 B
查询节点收到索引节点后,并行地将内节点以及叶节点与流元组之间的偏移量关系转换成相应的引用关
系,从而恢复下层索引,耗时为
2
⎛ N N ⎞ 1 2T N (m + 3m + 1)
t recover = 2T M ⎜ W × (m + 1) + W × (m + 2) × ⎟ = M W (15)
2
⎝ m 2 m ⎠ P recover m P recover
结合公式(12)~公式(15)可得:索引发布的时间开销主要来自数据传输,节点间的带宽直接决定了分布式索
引的构建效率.
4.3 上层索引更新性能评估
下层索引构建完成后,需要更新上层索引.上层索引更新在最坏的情况下,时间复杂度为 O(n height ),时间开
销为
t updateUpper =log(n height )T M (16)
由公式(16)可得,上层索引的更新开销相比下层索引构建和发布开销可忽略不计.
4.4 WB-Index整体性能分析

由以上分析可知,WB-Index 构建性能主要取决于下层 B+树索引的构建和发布性能.一个时间窗口的分布
式索引构建总时间开销 t delay =t buildLower +t releaseLower +t updateUpper .为了确保 WB-Index 能够平稳的构建,有如下限制:
t delay <T W (17)
若不满足该限制,流数据将会不断堆积,影响索引构建,对应的查询结果也失去准确性,整个分布式索引将