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

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

(1) 第 1 层缓存,用于缓存公共查询结果.本文中数据流存储的最小单元一个时间窗口对应的数据量,数据
流属于流水型数据,存储后就不再更新.所以对于包含相同查询条件的查询请求,查询结果是固定的.
故可将其结果缓存,减少不必要的重复查询开销.
(2) 第 2 层缓存,用于缓存热点数据.数据流存在热点性,热点数据会被频繁访问.本文将一次查询加载到
的流元组缓存到查询节点,后续查询涉及相关元组即可从内存加载.缓存过程中,会将其所在下层索
引叶节点对应的全部元组一并缓存,以保持适中的缓存粒度.第 2 层缓存由对应的下层索引维护,在具
有数据热点的场景下,能有效减少跨节点数据加载产生的 IO 开销.
(3) 第 3 层缓存,用于缓存较新数据流.数据流的时效性强,新数据属于分析、处理过程中的热点.本文针对
较新的数据流,在完成下层索引构建后,直接将其缓存在构建节点,相应的查询请求从构建节点的内
存中加载数据,减少磁盘 IO,提高数据加载性能.
受内存空间限制,每层缓存均采用 LRU 淘汰算法.3 层缓存方案结合了流数据和索引结构的特点,层次分明,
能有效提高查询效率.

查询

数据流 W i 查询节点 第1层缓存
构建节点 1 2 ... ... k 查询结果
缓存
较新流
元组缓存 查询节点 第2层缓存
第3层缓存 叶节点 WB-Index索引结构
缓存
流元组存储 存储节点 存储节点 存储节点 索引存储

Fig.4 Three-tier stream tuple caches
图 4 3 层流元组缓存
3 分布式索引构建

图 5 描述了分布式索引的构建流程,图中 W 1 ,W 2 ,…,W i 表示起始时间为 t i 、时长为 T W 的时间窗口.如图中的
a,b,c 所示,一个窗口对应的索引构建过程包括下层索引构建、下层索引发布以及上层索引更新,其总耗时为
t build .基于时间窗口的数据流处理模式需要保证窗口 W i 结束前,完成窗口 W i−1 的处理任务,即一个窗口任务的处
理耗时要小于窗口时长;反之,则表明数据流的流速大于处理速率,处理任务将会积压.因此,为了保证分布式索
引平稳构建,需保证 t build <T W .

Fig.5 Process of building WB-Index
图 5 WB-Index 构建流程
3.1 下层索引构建
文献[56−58]针对数据流提出了一种多次微批量排序单次批量装载的 B+树构建方法,本文在此基础上将批
量排序并行化,并在排序过程中预先装载 B+树,进一步提高构建性能.下层索引构建过程如图 6 所示,包括排序
(S 1 )、B+树框架搭建(S 2 )、B+树预装载(S 3 )、B+树赋码值(S 4 )这 4 个步骤.其中,B+树框架搭建(S 2 )和赋值(S 4 )与文
献[56]相同,故本部分不再赘述,以下仅描述优化后的排序(S 1 )和预装载(S 3 )部分.