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

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

用以记录窗口流元组码值特征,如最小值、最大值.对于连续时间窗口,形如{W 1 ,W 2 ,…,W i ,W i+1 },从时间维度构建
上层 B+树索引,其 key 值为窗口 W i 的时间戳 t i ,value 值为下层索引引用.提供基于时间的查询.图 1 为整个索引
结构图.

Fig.1 Index structure
图 1 索引结构

WB-Index 索引结构中,上层索引由窗口时间 t i 及其下层索引的元数据构成,数据量较小,可在单机中存储;
下层索引由流元组码值构成,存储开销大,无法在单机中维护,且各窗口对应的下层索引相互独立,因此,
WB-Index 根据负载均衡原则,将各个下层索引分发到不同的节点维护,从而减轻索引的更新、存储负载.上层索
引 value 值中,对下层索引的引用可表示为(t i ,host).t i 表示对应时间窗口时间戳,host 表示该时间窗口下层索引所
在的主机信息.查询时,与传统的主从索引结构查询类似,首先搜索上层索引,再搜索对应的下层索引获取结果.
由于各个下层索引相互独立且存储在不同的节点上,因此下层索引支持并行化搜索.
2.2 WB-Index系统架构
如图 2 所示,WB-Index 集群由多个协调节点、一个构建节点、多个查询节点、多个存储节点和多个控制
节点构成,集群中节点间的通信效率直接影响索引的构建和查询性能.系统实现中,将所有主机部署在同一机房
以降低数据传输时延.主机间使用自定义 TCP 协议通信,其格式由定长包头和具体消息体构成.传输层采用
Protocol Buffers 数据结构,其能减少数据包大小,并具有良好的解析性能.

查询模块
集群管理
模块
上层索引 处理查询
WB-Index结构 更新 请求 控 协
制 调
节 节
查询节点 查询节点 查询节点 节点信息 点 点
维护
索引构建模块 下层索引 控 协
发布 制 调
下层索引 索引 节 节
数据流 构建 持久化 点 点
构建节点
流元组 索引元数据
持久化 维护 控 协
制
调
节 节
存储模块 存储节点 存储节点 存储节点 点 点

Fig.2 WB-Index architecture
图 2 WB-Index 架构