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

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

式压缩存储,根据定义的维度,实时预聚合数据.在减少数据存储量的同时,支持高效的聚合查询.时序数据库
Gorilla [28] 结合时序数据的热点性,将最近一天产生的数据在内存中缓存来提高查询性能,对于历史数据,则通过
压缩、预聚合的方式减少存储量.预聚合的方式导致了其查询场景具有局限性.
索引技术是数据流实时存储的关键.高效的索引能支撑数据的实时存储,并提供高效的查询服务.常见的索
引有树形索引和哈希索引 [29−31] .AVL [32] 树和 B [33] 树都属于平衡树,AVL 树的节点只保存两个子节点指针,B 树能
根据定义的阶数保存多个子节点指针,在大数量场景下树高较小,在外存中广泛使用.B+树对 B 树优化,使其具
有更好的范围查询性能,有时也被用作内存索引.T [34] 树和 T* [35] 树兼具 AVL 树和 B 树的特点,常用于内存索引,
但比起 B+ [36] 树,T树的查询性能略差.哈希索引通过哈希函数将键值直接映射到具体的存取位置,平均复杂度为
O(1),但其不支持范围查询.
海量数据下,集中式架构无法完整地存储索引结构,也限制了索引的搜索性能.研究者提出了分布式索引,
根据存储、查询场景的不同,可分为主从结构和对等结构.CG-Index [37] 属于典型的主从结构,其在每个从节点上
构建本地 B+索引,并根据本地索引的部分节点构建全局索引.查询时,需根据全局索引路由到对应的本地索引
查询.文献[38]采用一致性 Hash 作为全局索引,将数据分块存储到不同的节点,并构建相应分块的 B+树索引.由
于一致性 Hash 只能支持点查询,该索引无法应用于水平范围切分的场景;且一致性 Hash 的分发机制在数据块
较大或存在数据热点时,各存储节点无法达到负载均衡.何龙 [39] 和李斌 [40] 等人分别提出了面向 HDFS 和面向
HBase 的多层索引技术和二级索引结构,主要考虑大数据存储和查询.Cassandra [19] 是第 2 类对等索引结构的典
型代表,其利用一致性 Hash [41] 对数据分区存储,集群内部采用 gossip [42] 协议广播路由信息,使每个节点都能处
理、转发查询请求,并能保证数据的多副本一致性.Aguilera 等人 [43] 提出一种分布式 B 树,其核心思想是,将 B 树
中的节点拆分存储到不同的存储节点上.然而该索引结构在更新时,若触发树节点分裂,会导致集群节点间的协
同更新,性能较差.为了提高更新性能,文献[44]通过将多次更新合并来降低更新频率,但其只能保证数据的最终
一致性.文献[45]根据节点分裂日志动态调整节点容量,避免节点频繁分裂.
海量数据场景下,可通过批量装载技术 [46] 加速索引构建.基于抽样的批量装载方法 [47] 利用采样数据集构建
索引框架,但采样数据存在数据不均的局限性,难以保证索引的平衡性.基于排序的批量装载方法 [48−50] 先对数据
集排序,然后自底向上批量构建索引,该方法会损失一定的实时性.基于缓存的批量装载方法 [51,52] 的核心思想
是:将新写入的记录存储在节点对应的缓存中,等写入量达到阈值后,再批量更新到具体的索引节点上.Jermaine
等人 [53] 提出的 Y 树索引就采用了这种思想,但其实现的复杂度较高.分布式场景下,Barbuzzi [54] 利用 MapReduce
框架,在数据分区的前提下并行地插入数据,提高了存储效率.Wang 等人 [55] 为了解决现实应用中对新数据和历
史数据的实时检索问题,提出一种数据分片策略和基于模板的索引结构,以减少索引调整代价.上述的分布式索
引以及构建方法适用于静态数据,在高速数据流场景下存在性能瓶颈.数据流往往是无状态的流水型数据,写入
后就不再更新.基于 LSM 存储模型的分布式索引具有很高的写入性能,但查询需要串行地搜索磁盘和缓存数
据,效率较低.本文针对带有时间属性的数据流,设计了主从结构的分布式索引,能够支持高效的实时数据流写
入以及流数据查询.

2 分布式索引 WB-Index 结构和架构

2.1 WB-Index索引结构
对于带时间属性的数据流,每条数据流记录被称为流元组,形如〈t,d〉,其中,t 为流元组生成时间,d 为具体的
流元组内容.流元组 d 可用〈k,v〉表示,k 表示流元组的码值,v 表示具体的流元组内容.数据流具有无限性,本文依据
时间维度切分数据流,将数据流划分为连续的时间窗口.对于第 i 个时间窗口 W i ,用〈t i ,W i 〉表示,其中:t i 表示对应时
间窗口的起始时间;W i 则为时间窗口内的流元组集合,形如 W i ={〈t m ,d m 〉|m=1,2,...,n},n 为 W i 窗口内具体的流元组
数量.
对于每个时间窗口 W i ,本文利用流元组码值 k 构建相应的下层索引.下层索引由一棵 B+树索引、布隆过滤
器、统计信息构成:B+树索引用于检索窗口内流元组;布隆过滤器用于过滤掉不存在码值的查询请求;统计信息