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

3586 Journal of Software 软件学报 Vol.32, No.11, November 2021

Table 2 Parameters used in WB-Index construction
表 2 WB-Index 构建中用到的参数列表
参数 描述
T W 单个时间窗口长度
T M 一次内存访问时间
T S 时间窗口内单个分片的时长
N S 时间窗口分片数量
N B 集群网络带宽(Mb/s)
N W 时间窗口内的元组数量
N m 下层 B+树阶数
P assignKey 下层 B+树赋值并行度
P recover 查询节点连接 B+树节点恢复下层 B+树的并行度
t buildLower 下层索引构建时间
t releaseLower 下层索引发布时间
t updateUpper 上层索引更新时间
t sort 构建下层 B+树时分片排序时间
t merge 构建下层 B+树时最终归并排序时间
t para 构建下层 B+树时计算 B+树参数时间
t skltn 构建下层 B+树时 B+树骨架构建时间
t preLoad 构建下层 B+树时预装载时间
t assignKey 构建下层 B+树时赋值时间
t serialize 序列化一个 Node 所需时间
t deserialize 反序列化一个 Node 所需时间
t transfer 下层索引传输开销
t recover 查询节点连接 B+树节点恢复下层 B+树的耗时
n height 上层索引树高
t delay 对于一个时间窗口分布式索引的总构建时间
理论分析中,流元组码值按整型数据评估,并忽略构建过程中的 CPU 计算时间开销.

4.1 下层索引构建性能评估
t buildLower 表示从接收一个完整的窗口数据流到完成对应的下层索引构建的时间开销,主要包括排序和树装
载开销.分片排序阶段,若分片排序时长小于分片时长(T S <t sort ),则分片排序延迟 t sortDelay 为最后一个分片排序耗
时,即
t sortDelay =t sort (4)
若分片排序时长大于分片时长(T S >t sort ),此时,数据流速大于排序速度,将会产生任务积压,增加额外的排序
延迟,可表示为
TN − 1)
(
t = t + (N − 1) t× − W S (5)
sortDelay sort S sort N
S
归并排序中,分片间的归并任务串行执行,总耗时为
t merge =2N S T M N W (6)
归并排序并行于数据流接收和分片排序,当前 N slice −1 个分片的归并时间开销小于 T W (N S −2)/N S ,则总的归并
时延 t mergeDelay 由最后分片的归并时间决定,即
t mergeDelay =4T M N W (7)
若数据流流速大,前 N Se −1 个分片的归并时间开销大于 T W (N S −2)/N S ,则
T N − 2)
(
t mergeDelay = 2T N N − M S W W S (8)
N S
一个窗口数据的排序时延由分片排序时延和归并时延构成,结合公式(5)~公式(8)可得:随着分片数 T S 增加,
分片排序耗时降低,但对应的归并排序耗时会随之增加.如果将前 N S −1 个分片的归并耗时控制在 T W (N S −2)/N S
内,分片数 T S 的增加不影响归并时延.由此可得:存在一个最优分片数 N S ,使得窗口元组排序性能最佳.系统运行
时,可根据数据流速动态调整分片数,以保持较好的排序性能.