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

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

近年来,数据流在各个领域被广泛应用,如 IOT 场景下的感知数据、智慧交通场景下的的监测数据以及互
联网应用中的用户行为数据等 [1−3] .数据流由无限个形如〈t,v〉的流元组构成,其中,t 为流元组产生的时间,v 为具
[4]
体的数据值.与静态关系型数据不同,数据流有流速快、实时性强、规模无限、易失等特点 .针对数据流规模
无限的特点,研究者提出了时间窗口概念,通过限定起止时间来限定处理范围,将数据流无限的处理规模切分成
小的处理模块.传统的数据库管理系统在存储稳定、有限的静态数据时性能良好,但在数据流场景下存在严重
的性能瓶颈.
[5]
[6]
为了克服这个困难,早期的研究者设计出一系列的数据流管理系统,如 STREAM ,Aurora ,TelegraphCQ [7]
[9]
[8]
等.近年来,分布式流计算平台大量涌现,像 Storm ,Flink 等,能提供高吞吐的流式计算.上述数据流处理系统主
要用于流式数据的聚合计算、近似计算、连续查询等,在存储层面只保存查询和计算结果,不存储完整数据流.
数据流的深度分析、计算场景需要依赖数据流的实时存储,上述系统无法适用.
数据流场景下,存储系统需保证高效的存储性能.目前,有基于抽样存储 [10,11] 和利用内存加速存储的系统,如
TimesTen [12] 、Hekaton [13] 、SolidDB [14] 以及基于 LSM [15] 存储模型的 BigTable [16] 等,海量流媒体索引 [17] 利用内存
组织多媒体流数据索引.无限数据规模下,单机无法支撑海量数据存储,从而衍生出分布式存储系统,如 GFS [18] 、
Cassandra [19] 等.数据流实时存储的一个关键是在不影响写入性能的前提下快速实时地构建索引,以实现高效查
询.目前,基于数据流实时存储的索引构建主要集中于位图索引构建方法 [20,21] ,但均缺乏通用性.大数据流场景
下,索引的更新频率高、存储开销大,具有很大的挑战.研究者根据数据存储形式,结合分布式思想,将索引结构按
照一定的组织方式分层、分片维护,但是目前索引结构并未考虑数据流连续、实时的特点.
本文根据现有工作的不足,面向带有时间属性的数据流,提出一种基于 B+树的双层分布式索引,在保证存
储性能的同时,支持高效查询,适用于体量大、维度多、速度快(数百万条/s)的大数据流场景.
本文贡献:
• 提出一种适用于数据流场景的分布式索引及其架构.分布式索引分为上下两层 B+树索引,由控制节
点、协调节点、存储节点、查询节点、构建节点共同维护,将对流数据的索引、查询、存储分离,在有
效地满足数据流特性的同时,也保证了存储和查询的性能;同时,提出了查询节点负载均衡、上层索引
冗余机制和三层缓存策略,以保证系统的可用性和稳定性.
• 针对所提分布式索引,提出一种高效的构建方法.对于每个时间窗口数据流构建的下层 B+树索引,采用
基于并行排序的批量装载技术进行构建;针对各个时间窗口构建的上层 B+树索引,采取不分裂的构建
方法进行构建.上层和下层构建方法的结合,使得分布式索引构建速度快、时延低;
• 通过理论、实验的分析对比,验证分布式索引在数据流场景下的有效性.

1 相关工作
[5]
[7]
[6]
早期的数据流管理系统,如 OpenCQ [22] 、STREAM 、Aurora 、NiagaraCQ [23] 、TelegraphCQ 等,都属于
集中式架构,通过合理的资源分配、调度和并行化设计,在有限的资源下提供连续查询、近似计算.随着数据流
[8]
[9]
的广泛应用,近些年涌现出一批分布式流计算平台,如 Storm ,Flink ,Spark Streaming [24] 等,将数据流计算抽象
成 DAG [25] 计算模型,定义多样的算子来进行实时计算,并支持机器学习、图计算等迭代计算场景.总体而言,上
述数据流管理平台重点关注于查询优化、实时计算、资源管理等方面,缺乏数据流实时存储能力.
海量数据场景下,集中式存储受限于存储空间,数据存储量和更新性能存在瓶颈.研究者设计了分布式存储
系统解决相应问题.GFS [18] 是典型的主从分布式存储系统,将数据以块为最小单元存储在不同的从节点上,同时
生成多个副本保证可用性.主节点管理数据块元数据,通过数据校验、版本控制等方式保证数据的完整性和一
致性.GFS 数据写入速度慢,适用于离线数据存储.Bigtable 是基于 GFS 的分布式 KV 存储系统,底层借鉴 LSM 存
储模型 [15] ,将新数据直接写入到内存中,内存存储量达到阈值后再写入磁盘,从而大幅提高数据写入速度.基于
分布式 KV 存储系统 HBase 的时序数据库 OpenTSDB [26] ,将时间戳和元组关键字等进行组装作为 key 值,但是
查询时只能按照前缀匹配进行查询,若前缀值是一个范围,搜索只能遍历查找.实时 OLAP 系统 Druid [27] 采用列