大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流,根据其时间属性,将数据流划分为连续的时间窗口,提出了基于双层B+树的分布式索引结构WB-Index.下层B+树索引基于窗口内流数据构建,索引构建过程结合基于排序的批量构建技术,进一步对时间窗口分片,将数据流接收、分片数据排序以及B+树构建并行化,提高了构建性能.上层B+树索引基于各时间窗口构建,结合时间窗口时间戳的递增性和无限性,提出了避免节点分裂的构建方法,减少了B+树分裂移动开销,提高了空间利用率和更新效率.WB-Index架构中,将流数据和索引分离,同时利用内存缓存尽可能多的双层B+索引和热点数据来提高查询性能.理论和实验结果表明,该分布式索引架构能够支持高效的实时数据流写入以及流数据查询,能够很好地应用于具有时间属性的数据流场景.
Efficient storage and indexing of big data streams are challenging issues in the database field. By segmenting the temporal data stream into continuous time windows, a distributed master-slave index structure is proposed based on double-layer B+ tree called WB-Index. Lower B+ tree index is built on stream tuples in each time window. Upper B+ tree index is built on each successive time window. Lower B+ tree index is constructed by combining both batch loading and parallel sorting techniques. The core idea of the construction method is to slice the time window and isolate the parallelable operations from others in the time window. Sorting and data stream receiving between slices work in parallel, while the B+ tree skeleton (a B+ tree without value) construction for the time window and the merge-sorting operation are parallelized as well. These techniques effectively expedite the B+ tree construction. Due to the monotonous increasement of timestamps of time windows, a split-less method for upper B+ tree index construction is adopted to avoid the node splitting and memory movement overhead, and improve the space utilization and update efficiency. In WB-Index, data stream tuples and index are separated, and index and hotspot data are cached as much as possible to improve query efficiency. Finally, theoretic analysis and experiments have both demonstrated that WB-Index can support efficient real-time data stream writing and stream data querying.
近年来, 数据流在各个领域被广泛应用, 如IOT场景下的感知数据、智慧交通场景下的的监测数据以及互联网应用中的用户行为数据等[
为了克服这个困难, 早期的研究者设计出一系列的数据流管理系统, 如STREAM[
数据流场景下, 存储系统需保证高效的存储性能.目前, 有基于抽样存储[
本文根据现有工作的不足, 面向带有时间属性的数据流, 提出一种基于B+树的双层分布式索引, 在保证存储性能的同时, 支持高效查询, 适用于体量大、维度多、速度快(数百万条/s)的大数据流场景.
本文贡献:
● 提出一种适用于数据流场景的分布式索引及其架构.分布式索引分为上下两层B+树索引, 由控制节点、协调节点、存储节点、查询节点、构建节点共同维护, 将对流数据的索引、查询、存储分离, 在有效地满足数据流特性的同时, 也保证了存储和查询的性能; 同时, 提出了查询节点负载均衡、上层索引冗余机制和三层缓存策略, 以保证系统的可用性和稳定性.
● 针对所提分布式索引, 提出一种高效的构建方法.对于每个时间窗口数据流构建的下层B+树索引, 采用基于并行排序的批量装载技术进行构建; 针对各个时间窗口构建的上层B+树索引, 采取不分裂的构建方法进行构建.上层和下层构建方法的结合, 使得分布式索引构建速度快、时延低;
● 通过理论、实验的分析对比, 验证分布式索引在数据流场景下的有效性.
早期的数据流管理系统, 如OpenCQ[
海量数据场景下, 集中式存储受限于存储空间, 数据存储量和更新性能存在瓶颈.研究者设计了分布式存储系统解决相应问题.GFS[
索引技术是数据流实时存储的关键.高效的索引能支撑数据的实时存储, 并提供高效的查询服务.常见的索引有树形索引和哈希索引[
海量数据下, 集中式架构无法完整地存储索引结构, 也限制了索引的搜索性能.研究者提出了分布式索引, 根据存储、查询场景的不同, 可分为主从结构和对等结构.CG-Index[
海量数据场景下, 可通过批量装载技术[
对于带时间属性的数据流, 每条数据流记录被称为流元组, 形如〈
对于每个时间窗口
索引结构
Index structure
WB-Index索引结构中, 上层索引由窗口时间
如
WB-Index架构
WB-Index architecture
分布式索引集群通过上述5类节点的相互协同, 保证了高效的索引构建、数据存储和查询响应.各类节点的作用如下:
(1) 构建节点实时接收数据流, 快速构建下层索引, 并选择合适的查询节点发布索引结构;
(2) 查询节点维护双层索引, 支持高效查询;
(3) 存储节点是集群中最底层的部分, 用于持久化数据流及其索引;
(4) 协调节点保存集群各节点状态数据和索引元数据;
(5) 控制节点是集群的核心, 负责合理的调度集群中的各类节点, 保证集群的稳定.
构建节点接收到数据流后, 将其缓存在当前的时间窗口中, 并在窗口结束后触发构建下层索引, 完成下层索引构建后, 构建节点选择合适的查询节点发布索引, 由查询节点提供查询服务.这种机制将索引构建和查询解耦, 同时保证了两个模块的高效.查询节点收到下层索引后, 以引用的方式将其插入上层索引, 并同步更新所有上层索引副本, 从而完成整个WB-Index的构建.窗口流元组一开始会缓存在构建节点中, 由构建节点异步的将流元组持久化到存储节点.同样, 受内存空间限制, 查询节点中的双层索引结构也将持久化到存储节点.
WB-Index上下两层索引都支持范围查询, 其结构限定查询条件需带有时间属性.上层索引冗余维护在每个查询节点, 故相应节点均能处理查询请求.分布式查询过程可分为上层索引搜索、下层索引搜索、流元组加载和数据整合.查询时, 首先根据查询条件中的时间属性搜索上层索引, 获取其叶节点中的引用值, 并定位查询涉及的下层索引, 再搜索下层索引加载对应流元组, 最后整合查询结果.数据流查询过程中充分利用了内存的缓存作用, 把公共查询结果(相同查询条件的流元组)、热点查询结果(热点流元组)和最新数据流元组分别缓存在查询节点和构建节点上, 最大限度提升查询性能.
WB-Index索引系统具有可扩展性, 借鉴当前典型的云计算系统(如Hadoop)来设计.WB-Index系统可以根据系统性能需要, 动态地增加查询节点与存储节点.WB-Index系统通过采用多副本冗余机制实现故障恢复.另一方面, 随着系统的运行, 存在“过期”数据的处理问题.不同的应用在这方面有不同的过期数据处理要求.由于所提WB-Index索引的上层索引是对窗口时间的索引, 过期数据位于上层B+树索引的左侧, 可以方便据此进行数据的生命周期管理: 增加查询节点或存储节点扩容, 或选择时间区域归档, 或销毁数据(删除上层B+树的某些叶节点).
构建节点将构建好的下层索引分发到查询节点, 由查询节点处理查询请求.数据流速具有波动性, 每个窗口中, 流元组数据量有较大差异; 另外, 流元组具有热点性, 热点数据的访问频次远高于其他数据, 需将热点数据尽可能地分散到不同的查询节点上, 避免查询请求堆积到个别查询节点, 从而保证查询效率.因此在分发下层索引时, 需保持各节点的负载均衡.传统的轮询、哈希负载均衡法没有结合数据流的特点, 无法适用于WB-Index.本文结合数据流的波动性、热点性以及集群节点间的性能差异, 基于加权轮询算法, 通过实时采集节点的性能指标、查询频次等信息, 动态调整查询节点分发权重, 实现较为精细的负载均衡.
负载均衡方法
Load balancing method
节点负载参数表
Node payload parameters
负载参数 | 描述 |
单位时间内下层索引查询频次 | |
单位时间内处理器平均负载 | |
当前空闲内存大小 |
(1) 查询节点实时采集、计算节点负载信息, 定时推送至协调节点, 由协调节点管理节点负载信息;
(2) 控制节点监听协调节点中节点负载信息变化, 调整各查询节点权重;
(3) 发布索引时, 根据各查询节点权重, 采用加权轮询算法, 选取合适的节点发布.
其中, 负载信息的采集、上报以及节点权重的更新频率应适中: 较高的频率虽能使得负载管理更加精细, 但会额外增加集群负载; 较小的频率则会导致负载信息更新不及时, 导致负载均衡不准确.负载均衡过程中涉及的节点权重计算方式如下.
(1) 上述的节点负载参数量级不同, 为了便于加权处理, 首先需进行归一化预处理:
(2) 针对每个节点
其中, 负载参数权重
WB-Index属于主从结构, 上层索引可以看成全局索引, 所有的查询请求都会先搜索上层索引.若集群中只维护一份上层索引, 会导致查询性能存在瓶颈.因此, 本文将上层索引同步至多个查询节点上, 并将索引副本元数据存储在协调节点.查询时, 多个查询节点共同提供上层索引的查询服务, 从而提高整体的查询性能.上层索引更新频率低、数据量小, 冗余机制不会增加过多的存储开销.另外, 索引副本间要保证数据一致, 每当上层索引更新后, 需要同步更新所有副本.在副本更新过程中, 对于已经更新成功的副本是可用的, 正在更新的副本则是不可用的.若一个副本在更新过程中更新失败, 首先会触发多次重试, 若超过重试次数后仍无法更新相应副本, 则先会将协调节点上相应的元数据置为失效状态, 确保不一致的索引数据对查询不可见; 然后会记录失败日志, 定时触发同步补偿, 确保副本数据最终一致.
WB-Index查询涉及多次磁盘、网络IO操作, 减少相应的IO操作频率能有效的提高查询效率.因此, 结合数据流特点及其查询的热点性, 本文设计了3层缓存来提高分布式查询的整体效率.缓存架构如
3层流元组缓存
Three-tier stream tuple caches
(1) 第1层缓存, 用于缓存公共查询结果.本文中数据流存储的最小单元一个时间窗口对应的数据量, 数据流属于流水型数据, 存储后就不再更新.所以对于包含相同查询条件的查询请求, 查询结果是固定的.故可将其结果缓存, 减少不必要的重复查询开销.
(2) 第2层缓存, 用于缓存热点数据.数据流存在热点性, 热点数据会被频繁访问.本文将一次查询加载到的流元组缓存到查询节点, 后续查询涉及相关元组即可从内存加载.缓存过程中, 会将其所在下层索引叶节点对应的全部元组一并缓存, 以保持适中的缓存粒度.第2层缓存由对应的下层索引维护, 在具有数据热点的场景下, 能有效减少跨节点数据加载产生的IO开销.
(3) 第3层缓存, 用于缓存较新数据流.数据流的时效性强, 新数据属于分析、处理过程中的热点.本文针对较新的数据流, 在完成下层索引构建后, 直接将其缓存在构建节点, 相应的查询请求从构建节点的内存中加载数据, 减少磁盘IO, 提高数据加载性能.
受内存空间限制, 每层缓存均采用LRU淘汰算法.3层缓存方案结合了流数据和索引结构的特点, 层次分明, 能有效提高查询效率.
WB-Index构建流程
Process of building WB-Index
文献[
下层B+树构建方法
Construction scheme of the lower B+ tree
(1) 排序
为了提升窗口数据排序性能, 本文进一步切分窗口, 将生成的连续分片作为最小排序单元(编号1所示).数据流接收过程中, 每接收到完整的分片数据, 就并行地触发分片内数据预排序(编号2所示).预排序完成后, 由专门的归并线程对有序分片作二路归并排序(编号3所示).当接收到完整数据流后, 等最后一个分片排序结束后, 就完成了对整个窗口数据的排序.如
当分片内数据量较大时, 可采用并行排序法加速排序, 从而避免排序任务积压.并行排序的核心思想是: 对数据分段, 先并行地对各分段排序, 最后通过多路归并方法完成全局排序.在数据量为
传统的快速排序时间复杂度为O(
(2) B+树预装载
在B+树框架搭建(
下层索引构建过程包含很多排序、计算任务, 会占用大量的机器资源, 而索引的查询过程也需要较多的计算资源.因此, 构建节点无法在构建索引的同时提供高效的查询服务, 需将下层索引发布到查询节点, 由查询节点提供查询服务.发布过程中, 利用第2.3节描述的负载均衡方法保证各查询节点负载均衡.查询节点接收到索引数据后, 需将内节点以及叶节点与流元组之间的偏移量关系转换成相应的引用关系, 从而恢复下层B+树索引.转换过程需要处理每个B+树节点, 时间复杂度为O(
查询节点接收并恢复窗口
上层索引更新过程中, 在B+树中维护全局插入点, 如
上层B+树更新
Upper B+ tree updates
上层索引详细更新过程如算法1所述.
输入:
输出:
符号说明:
1. 若上层索引为空, 则初始化索引:
1.1. 申请并初始化空间为
1.2. 初始化全局插入点和节点内部插入偏移值:
1.3. 更新树高:
2. 若上层索引不为空, 则更新上层索引:
2.1. 根据全局插入点
2.2. 若更新后
若当前节点
否则
将键值
}
2.3. 若更新后的
2.4. 完成更新.
异步任务:
1. 以
若
创建新节点作为新根节点;
返回
若
若
}
2. 以
若
否则执行:
创建容量为
设置新节点树高: 当前树高-1;
把
递归调用
}
上层索引更新过程中, 若插入点为非空节点, 索引更新时间复杂度为O(1);若插入点是空节点, 需额外初始化所有父节点
随着系统的运行, 上层索引不断增大.对于历史数据, 查询次数少, 可对其归档存储.本文采用分段存储的策略, 每过一个时间周期, 就生成一个全新的上层索引, 用于后续的更新写入, 如
上层B+树索引分段
Upper B+ tree index segmentation
本节对WB-Index索引构建性能做量化评估,
WB-Index构建中用到的参数列表
Parameters used in WB-Index construction
参数 | 描述 |
单个时间窗口长度 | |
一次内存访问时间 | |
时间窗口内单个分片的时长 | |
时间窗口分片数量 | |
集群网络带宽(Mb/s) | |
时间窗口内的元组数量 | |
下层B+树阶数 | |
下层B+树赋值并行度 | |
查询节点连接B+树节点恢复下层B+树的并行度 | |
下层索引构建时间 | |
下层索引发布时间 | |
上层索引更新时间 | |
构建下层B+树时分片排序时间 | |
构建下层B+树时最终归并排序时间 | |
构建下层B+树时计算B+树参数时间 | |
构建下层B+树时B+树骨架构建时间 | |
构建下层B+树时预装载时间 | |
构建下层B+树时赋值时间 | |
序列化一个 |
|
反序列化一个 |
|
下层索引传输开销 | |
查询节点连接B+树节点恢复下层B+树的耗时 | |
上层索引树高 | |
对于一个时间窗口分布式索引的总构建时间 |
理论分析中, 流元组码值按整型数据评估, 并忽略构建过程中的CPU计算时间开销.
若分片排序时长大于分片时长(
归并排序中, 分片间的归并任务串行执行, 总耗时为
归并排序并行于数据流接收和分片排序, 当前
若数据流流速大, 前
一个窗口数据的排序时延由分片排序时延和归并时延构成, 结合公式(5)~公式(8)可得: 随着分片数
下层索引构建过程中, 构建树型结构的时延可表示为
最后的赋值环节, 在
结合公式(5)~公式(10)可得: 排序时延远大于下层索引框架构建时延(
其中, 赋值阶段的时间开销远小于排序阶段, 排序性能直接影响下层索引构建性能, 故分片数
下层索引发布的时间开销主要来自节点间的数据传输和树结构的恢复开销, 可表示为
索引发布阶段, 发送方需先将其结构数据序列化.根据序列化方式的不同, 过程中会写入标识字符, 以便于反序列化相应结构.为了便于理论评估, 分析过程中忽略这些字符, 并将反序列化和序列化两者的时间开销近似等价, 即
下层索引传输阶段, 若每个树节点序列化后的大小为
查询节点收到索引节点后, 并行地将内节点以及叶节点与流元组之间的偏移量关系转换成相应的引用关系, 从而恢复下层索引, 耗时为
结合公式(12)~公式(15)可得: 索引发布的时间开销主要来自数据传输, 节点间的带宽直接决定了分布式索引的构建效率.
下层索引构建完成后, 需要更新上层索引.上层索引更新在最坏的情况下, 时间复杂度为O(
由公式(16)可得, 上层索引的更新开销相比下层索引构建和发布开销可忽略不计.
由以上分析可知, WB-Index构建性能主要取决于下层B+树索引的构建和发布性能.一个时间窗口的分布式索引构建总时间开销
若不满足该限制, 流数据将会不断堆积, 影响索引构建, 对应的查询结果也失去准确性, 整个分布式索引将会不可用.对于时长为
本次实验选用阿里云平台, 集群环境由20个ECS实例节点组成.分布式索引选用JAVA语言实现.
ECS实例软硬件配置
ECS instance's software/hardware configuration
类别 | 配置 |
系统 | Ubuntu 16.04, 64bit |
CPU | 4 cores Intel Xeon Platinum 8163@2.50GHz |
内存 | 32GB |
网络 | 1Gbps |
磁盘 | 100GB |
WB-Index集群节点构成
Types of nodes in WB-Index cluster
编号 | 类型 |
ECS01 | 构建节点 |
ECS02, ECS03 | 查询节点, 协调节点 |
ECS04 | 控制节点, 协调节点, 查询节点 |
ECS05~ECS14 | 查询节点 |
ECS15~ECS20 | 存储节点 |
实验使用TPC-H生成的1亿条Line Item数据集, 数据格式为〈
由第4.4节的理论分析可得, 下层索引构建性能是影响分布式索引构建性能的重要因素.下层索引构建中的分片排序阶段, 通过并行排序法加速排序.通过预实验得到:
● 当前机器配置下, 分片元组数量小于150万时, 传统快速排序性能更好.
● 超过该数据量时, 用2个线程并行排序性能较好.实验中, 按照此规则选用合适的排序方式.
由第4.1节的理论分析可得, 分片数
下层索引构建延迟与分片数的关系
Construction delay of the lower B+ tree vs. the number of slices
● 随着分片数的增加, 下层索引构建性能先升后降;
● 分片数量达到25个时, 构建性能趋于稳定, 并在35个时性能最优.
这与第4.1节的分析结论相符.实验对比了下层索引构建中各阶段耗时, 由
数据流流速存在波动性, 本实验在20s的时间窗口内, 通过模拟不同数据流速, 评估下层索引构建的稳定性, 实验设置窗口分片数
如
不同数据流速下, 下层索引的构建延迟
Construction delay of the lower B+ tree vs. the varying stream rates
针对上层索引, 本文根据场景中
上层索引更新次数与更新时间的关系
Update time vs. the number of the upper B+ tree updates
本实验在20s的时间窗口, 通过模拟不同数据流速来评估WB-Index构建性能, 并对比其包含的下层索引构建、下层索引发布、上层索引更新这3个阶段的耗时.实验设置窗口分片数
实验结果如
数据流流速与WB-Index构建时延的关系
Construction delay of WB-Index vs. the varying stream rates
如上文所述, CG-Index和LSM-树模型均能应用于分布式场景, 属于分布式索引结构.本实验模拟不同的数据流速, 对比LSM-树、CG-Index和WB-Index这三者的构建效率.为了保证实验具有可比性, 模拟的数据流持续时间为100s, CG-Index中分配10个节点用于存储, 设置LSM-树模型中触发转储的内存阈值为200万条数据. WB-Index窗口时长
WB-Index、CG-Index与LSM树索引的构建延迟对比
Construction delay comparisons between WB-Index, CG-Index and LSM tree
由第4.4节分析得出: 为了保证索引平稳构建, 需保证构建时延小于窗口时长.本实验在窗口时长
WB-Index构建时延与数据流速的关系
WB-Index construction delay vs. the varying stream rates
WB-Index中的上下两层索引均能支持范围查询, 本实验针对基本的取值查询, 通过改变窗口和元组查询范围评估查询总体性能.实验设置窗口元组数量
WB-Index查询时间与查询范围的关系
Query time vs. query scope on WB-Index
WB-Index查询过程包括上层索引搜索、下层索引搜索、流元组加载和数据整合.本实验限定1%的窗口流元组查询范围, 通过改变窗口查询范围, 对比分析各查询环节耗时.
WB-Index各查询阶段耗时对比
Time comparisons between each query stage on WB-Index
本文面向完整保存数据流的应用, 结合数据流的特点, 提出双层分布式索引: WB-Index.在保证索引构建效率的同时, 通过高效缓存保障查询效率; 通过负载均衡策略和上层索引冗余机制, 保证索引系统的可用性和稳定性.针对分布式索引构建: 采用时间窗口的方式切分数据流, 基于窗口内流元组构建下层索引, 采用高度并行化、批量化的方式加速构建性能; 上层索引基于所有时间窗口构建, 考虑到时间窗口时间戳的递增性, 提出避免分裂的B+树插入策略, 减少B+树分裂移动开销, 提高空间利用率, 并提出预分配策略提高数据插入的性能.通过实验验证分布式索引的构建性能, 相比起CG-index和LSM存储模型均有很大的性能优势, 适用于高速数据流场景.今后将进一步研究双层分布式索引的持久化方法.
感谢阿里巴巴数据库事业部为本文的研究提供了实验所需的软硬件资源, 感谢彭立勋先生为本研究提供诸多讨论和帮助.
Golab L, Özsu MT. Issues in data stream management. ACM SIGMOD Record, 2003, 32(2): 5-14.
Xie J, Yang J. A survey of join processing in data streams. In: Data Streams: Models and Algorithms. 2007. 209-236.
Acharya S, Gibbons PB, Poosala V, Ramaswamy S. Join synopses for approximate query answering. ACM SIGMOD Record, 1999, 28(2): 275-286.
Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data streams. In: Proc. of the PODS Conf. 2002. 1-16.
Arasu A, Babcock B, Babu S, Cieslewicz J, Datar M, Ito K, Motwani R, Srivastava U, Widom J. Stream: The Stanford data stream management system. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. 2003.
Carney D, Cetinternel U, Cherniack M, Convey C, Lee S, Seidman G, Stonebraker M, Tatbul N, Zdonik S. Monitoring streams: A new class of dbms applications. In: Proc. of the VLDB Conf. 2002. 215-226.
Krishnamurthy S, Chandrasekaran S, Cooper O, Deshpande A, Franklin MJ, Hellerstein JM, Hong W, Madden S, Reiss F, Shah MA. TelegraphCQ: An architectural status report. Data Engineering Bulletin, 2003, 26(1): 11-18.
Toshniwal A, Taneja S, Shukla A, Ramasamy K, Kulkarni S, Jackson J, Gade K, Fu MS, Donham J, Bhagat N, Mittal S, Ryaboy D. Storm@twitter. In: Proc. of the VLDB Int'l Conf. on Management of Data. 2014. 147-156.
Carbone P, Katsifodimos A, Ewen S, Markl V, Haridi S, Tzoumas K. Apache flink: Stream and batch processing in a single engine. Data Engineering Bulletin, 2015, 36(4): 28-38.
Zhang DD, Li JZ, Wang WP, Guo LJ. Algorithms for storing and aggregating historical streaming data. Ruan Jian Xue Bao/Journal of Software, 2005, 16(12): 2089-2098(in Chinese with English abstract). http://jos.org.cn/jos/article/abstract/20051207?st=article_issue [doi: 10.1360/jos162089]
张冬冬, 李建中, 王伟平, 郭龙江. 数据流历史数据的存储与聚集查询处理算法. 软件学报, 2005, 16(12): 2089-2098. http://jos.org.cn/jos/article/abstract/20051207?st=article_issue [doi: 10.1360/jos162089]
Ge JW, Gong PQ, Liu ZH. Method of storing and indexing historical streaming data. Application Research of Computers, 2007, 24(6): 104-106(in Chinese with English abstract).
葛君伟, 公丕强, 刘兆宏. 一种存储和索引历史数据流数据的方法. 计算机应用研究, 2007, 24(6): 104-106.
Lahiri T, Neimat MA, Folkman S. Oracle TimesTen: An in-memory database for enterprise applications. Data Engineering Bulletin, 2013, 36(2): 6-13.
Larson PÅ, Zwilling M, Farlee K. The Hekaton memory-optimized OLTP engine. Data Engineering Bulletin, 2013, 36(2): 34-40.
Lindström J, Raatikka V, Ruuth J, Soini P, Vakkila K. IBM solidDB: In-memory database optimized for extreme speed and availability. Data Engineering Bulletin, 2013, 36(2): 14-20.
O'Neil P, Cheng E, Gawlick D, O'Neil E. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33(4): 351-385.
Chang F, Dean J, Ghemawat S, Hsieh WC, Wallach DA, Burrows M, Gruber RE, Chandra T, Fikes A, Gruber RE. Bigtable: A distributed storage system for structured data. ACM Trans. on Computer Systems, 2008, 26(2): 1-26.
Antaris S, Rafailidis D. In-memory stream indexing of massive and fast incoming multimedia content. IEEE Trans. on Big Data, 2018, 4(1): 40-54.
Ghemawat S, Gobioff H, Leung ST. The Google file system. In: Proc. of the ACM Symp. on Operating Systems Principles. ACM, 2003. 20-43.
Lakshman A, Malik P. Cassandra: A decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010, 44(2): 35-40.
Fusco F, Vlachos M, Stoecklin MP. Real-time creation of bitmap indexes on streaming network data. The VLDB Journal, 2012, 21(3): 287-307.
Pu KQ, Zhu Y. Efficient indexing of heterogeneous data streams with automatic performance configurations. In: Proc. of the Scientific and Statistical Database Management. IEEE, 2007. 34-34.
Liu L, Pu C, Tang W. Continual queries for Internet scale event-driven information delivery. IEEE Trans. on Knowledge and Data Engineering, 1999, 11(4): 583-590.
Chen J, DeWitt DJ, Tian F, Wang Y. NiagraCQ: A scalable continuous query system for internet databases. In: Proc. of the SIGMOD Conf. 2000. 379-390.
Lin JC, Lee MC, Yu IC, Johnsen EB. Modeling and simulation of spark streaming. In: Proc. of the Int'l Conf. on Advanced Information Networking and Applications. 2018. 407-413.
Yan M, Wang L, Zomaya AY, Chen D, Ranjan R. Task-tree based large-scale mosaicking for massive remote sensed imageries with dynamic DAG scheduling. IEEE Trans. on Parallel & Distributed Systems, 2014, 25(8): 2126-2137.
http://opentsdb.net/]]>
Yang F, Tschetter E, Léauté X, Ray N, Merlino G, Ganguli D. Druid: A real-time analytical data store. In: Proc. of the ACM SIGMOD Conf. 2014. 157-168.
Pelkonen T, Franklin S, Teller J, Cavallaro P, Huang Q, Meza J, Veeraraghavan K. Gorilla: A fast, scalable, in-memory time series database. Proc. of the VLDB Endowment, 2015, 8(12): 1816-1827.
Knuth DE. The Art of Computer Programming. Pearson Education, 2005.
Fagin R, Nievergelt J, Pippenger N, Strong HR. Extendible hashing: A fast access method for dynamic files. ACM Trans. on Database Systems, 1979, 4(3): 315-344.
Litwin W. Linear Hashing: A new tool for file and table addressing. In: Proc. of the VLDB Conf. 1980. 1-3.
Aho AV, Hopcroft JE, Ullman JD. The Design and Analysis of Computer Algorithms. Pearson Education India, 1974.
Comer D. The ubiquitous B-tree. ACM Computing Surveys, 1979, 11(2): 121-137.
Lehman TJ, Carey MJ. A study of index structures for main memory database management systems. In: Proc. of the VLDB Conf. 1986. 294-303.
Choi KR, Kim KC. T*-tree: A main memory database index structure for real time applications. In: Proc. of the Real-time Computing Systems and Applications. 1996. 81-88.
Lu H, Ng YY, Tian Z. T-tree or B-tree: Main memory database index structure revisited. In: Proc. of the Australian Database Conf. 2000. 65-73.
Wu S, Jiang D, Ooi BC, Wu KL. Efficient B-tree based indexing for cloud data processing. Proc. of the VLDB Endowment, 2010, 3(1-2): 1207-1218.
Li X, Ren C, Yue M. A distributed real-time database index algorithm based on B+ tree and consistent hashing. Procedia Engineering, 2011, 24: 171-176.
He L, Chen JC, Du XY. Multi-layered index for HDFS-based system. Ruan Jian Xue Bao/Journal of Software, 2017, 28(3): 502-513(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5161.htm [doi: 10.13328/j.cnki.jos.005161]
何龙, 陈晋川, 杜小勇. 一种面向HDFS的多层索引技术. 软件学报, 2017, 28(3): 502-513. http://www.jos.org.cn/1000-9825/5161.htm [doi: 10.13328/j.cnki.jos.005161]
Li B, Guo JW, Peng Q. Design of HBase secondary indexes for big data storage. Computing Technology and Automation, 2019, 38(2): 124-129(in Chinese with English abstract).
李斌, 郭景维, 彭骞. 面向大数据存储的HBase二级索引设计. 计算技术与自动化, 2019, 38(2): 124-129.
Karger DR, Lehman E, Leighton T, Panigrahy R, Levine M, Lewin D. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In: Proc. of the Symp. on the Theory of Computing. 1997. 654-663.
Van RR, Dumitriu D, Gough V, Thomas C. Efficient reconciliation and flow control for anti-entropy protocols. In: Proc. of the 2nd Workshop on Large-scale Distributed Systems and Middleware. ACM, 2008. Article No. 6.
Aguilera MK, Golab W, Shah MA. A practical scalable distributed B-tree. In: Proc. of the VLDB Conf. 2008. 598-609.
Ahmed M, Singh SS, Lee MJ. Lazy updates to indexes in a database. U.S. Patent 20090089334, 2009.
Huang B, Peng YX. An efficient distributed B-tree index method in cloud computing. Open Cybernetics & Systemics Journal, 2014, 8: 302-308.
Bercken J, Seeger B. An evaluation of generic bulk loading techniques. In: Proc. of the VLDB Conf. 2001. 461-470.
Lo ML, Ravishankar CV. The design and implementation of seeded trees: An efficient method for spatial joins. IEEE Trans. on Knowledge and Data Engineering, 1998, 10(1): 136-152.
Ciaccia P, Patella M. Bulk loading the M-tree. In: Proc. of the Australian Database Conf. 1998. 15-26.
Kotidis Y, Roussopoulos N. An alternative storage organization for ROLAP aggregate views based on cubetrees. In: Proc. of the 1998 ACM SIGMOD Conf. 1998. 249-258.
Kondylakis H, Dayan N, Zoumpatianos K, Palpanas T. Coconut: Sortable summarizations for scalable indexes over static and streaming data series. The VLDB Journal, 2019, 28(6): 847-869
Bercken J, Seeger B, Widmayer P. A generic approach to bulk loading multidimensional index structures. In: Proc. of the VLDB Conf. 1997. 406-415.
Arge L, Hinrichs KH, Vahrenhold J, Vitter JS. Efficient bulk operations on dynamic R-trees. Algorithmica, 2002, 33(1): 104-128.
Jermaine C, Datta A, Omiecinski E. A novel index supporting high volume data warehouse insertion. In: Proc. of the VLDB Conf. 1999. 235-246.
Barbuzzi A, Michiardi P, Biersack E, Boggia G. Parallel bulk insertion for large-scale analytics applications. In: Proc of the Int'l Workshop on Large Scale Distributed Systems and Middleware. 2010. 27-31.
Wang L, Cai R, Fu ZJ, He J, Lu Z, Winslett M, Zhang Z. Waterwheel: Realtime indexing and temporal range query processing over massive data streams. In: Proc. of the ICDE Conf. 2018. 269-280.
Xiang JJ. Distributed in-memory hybrid index for big data stream[MS. Thesis]. Hangzhou: Zhejiang University of Technology, 2017(in Chinese with English abstract).
项俊健. 面向流数据的分布式混合内存索引[硕士学位论文]. 杭州: 浙江工业大学, 2017.
Yang LH, Xiang JJ, Xu W, Fan YL. In-memory B+tree construction methodology for big data stream. Computer Science, 2018, 45(3): 173-179, 214(in Chinese with English abstract).
杨良怀, 项俊腱, 徐卫, 范玉雷. 一种大数据流内存B+树构建方法. 计算机科学, 2018, 45(3): 173-179, 214.
Lu CX. A distributed B+ tree for big data stream[MS. Thesis]. Hangzhou: Zhejiang University of Technology, 2019(in Chinese with English abstract).
卢晨曦. 面向大数据流的分布式B+树索引构建[硕士学位论文]. 杭州: 浙江工业大学, 2019.