HiBase2.0:基于数据块的分层式索引查询系统
大数据时代，全球数据正以爆炸式的速度增长。为了有效存储和管理海量数据，出现了NoSQL数据库。HBase是一种典型的分布式、面向列的NoSQL数据库，可以对结构化、半结构化、甚至非结构化的海量数据进行实时的读写和随机访问。随着HBase被国内外企业、科研机构广泛使用，针对HBase的查询性能优化已经成为大数据存储管理研究中一个非常重要的研究问题。
HBase按照主键的字节字典序存储每一行记录，因此支持基于主键的快速查询，但在有些应用场景下可能需要对其他非主键字段进行查询。HBase目前并未对非主键建立索引机制，所以非主键的查询需要对HBase整张表进行扫描，查询效率很低。
图1 基于分层式索引的查询系统总体架构
基于数据块的分层式索引查询系统的总体架构如图1所示，系统由持久存储层、索引缓存层和全局索引管理模块组成。索引缓存层的功能由集群各节点上的内存索引服务进程实现，这些进程负责索引缓存层的热数据存储、缓存替换以及地址映射管理。由分布式协调系统ZooKeeper来管理和监控内存索引服务进程的加入和退出情况，实现索引缓存层的高可用性。持久存储层主要负责用户表和索引表的存储，其中Coprocessor实现了索引数据的生成、插入、删除和更新等功能。全局索引管理模块完成数据自适应分块和对数据块元信息的管理。跳表结构记录了所有索引数据块的元信息（是否在缓存、块范围、记录数、热度等信息），客户端只需将查询请求转发给跳表，就能快速获得查询范围内所有索引数据块的位置信息。
图2 分层式索引的数据存储框架
系统的分层式数据存储框架如图2所示。下层是基于磁盘的持久存储层，当用户在HBase中插入原始数据（Raw Data）时，系统会根据非主键属性建立索引表，并将同步生成的索引数据（Index Data）存入HBase。持久存储层存放着所有的原始数据和索引数据。
上层是基于内存的缓存层，本系统将管理所有索引数据块元信息的跳表结构存放在内存中，利用内存读取速度快的特点，快速查询和更新跳表结构。虽然持久存储层的索引数据是按照一条条的记录存储，但在跳表中逻辑上记录成一个个数据块。利用自适应调整方法使得数据块的划分尽可能地接近数据访问规律，然后根据数据块的热度值将频繁被访问的数据块缓存到索引缓存层。在索引缓存层使用分布式内存数据库Redis存储跳表中记录的热数据块。Redis是基于内存、可进行数据持久化的高性能key-value型存储系统，它能有效支持value为集合类型（Set）的数据存储，可以看到索引数据是以数据块的方式存入Redis的Set集合中的。本系统使用一致性哈希算法将热数据块分布到各节点的内存数据库Redis上，从而保证了索引缓存层的可扩展性。
4.1 非主键索引数据分块管理
对非主键属性建立索引，并将键（key）值连续的索引记录划分为一个个数据块，以数据块为单位对索引数据进行管理，来减少索引空间开销和查询时间开销。同时，采用跳表结构来管理索引数据块的元数据信息，利用跳表结构查询效率高等特点进一步加速非主键数据的范围查询。
图3 跳表存储数据块元信息示意图
4.2 数据块自适应调整方法
根据数据块中被访问数据所占比例（即数据块的热度），对数据块进行自适应地分裂与合并，最终将数据块的划分训练得符合查询访问规律。
4.3 基于跳表和分层式索引的范围查询
跳表查询过程如下：
- 根据查询范围对跳表进行搜索，获取数据块的位置信息。
- 根据被访问热数据块信息，并发地去缓存层相应节点获取数据。
- 根据被访问冷数据块信息，直接从持久存储层取出数据。
- 根据跳表中没有记录的数据范围，去持久存储层进一步查询。
在缓存层获取热数据时，通过并发地到各个节点获取数据和把同一节点的多次访问转化为一次批量访问等方法，进一步缩短查询的时间。
图4 跳表查询示意图（以查询范围41-80为例）
4.4 基于自适应分块的缓存替换策略AdaHotscore
对于每个数据块，定义了数据块的利用率Dutyrate和一段访问时间内数据块的热度Hotscore。AdaHotscore缓存替换策略的基本思想是将缓存中的所有热数据块按照Hotscore排序，优先选取Hotscore最小的数据块进行淘汰。
AdaHotscore替换策略使用数据块作为缓存粒度，它缓存的数据块采用（2）中介绍的方法，根据查询访问的规律对热数据块进行边界和跨度的调整，将更有可能被访问的数据块留在缓存中，从而提升系统的整体查询性能。
5.1 系统对比实验
本课题组先前已将研究实现的HiBase系统和同类型的HBase非主键索引系统进行了深入的实验对比，并且验证了其性能相对于其他系统提升了很多，所以这里通过和HiBase系统进行比较来说明HiBase2.0系统的性能提升。
图5 系统对比实验
为了充分说明HiBase2.0系统对于范围查询在性能上的优势，分别测试了在相同查询请求条件下，HBase系统、HiBase系统以及HiBase2.0系统的查询时间。为了能在可接受的时间内获得实验结果，将HBase系统的查询次数设置为5000次，而HiBase、HiBase2.0系统的查询次数设置为50000次。从图5可以看出，HiBase2.0系统性能最佳。与HBase相比，性能提升数百倍；与HiBase相比，性能提升3倍以上。
5.2 缓存替换策略对比实验
一般来说缓存粒度设置的越小，命中率就越高。HiBase2.0系统是以数据块为缓存粒度在缓存层进行缓存的。实验表明，通过数据块的自适应调整和新提出的缓存替换策略，本系统在缓存层的命中率和不分块处理的缓存替换策略基本接近，同时相比于不分块处理的缓存替换策略，本系统的缓存速度更快、空间开销更小。实验测试了四种缓存替换策略：AdaHotscore、FIFO、LRU和LFU在不同缓存比例下的命中率和查询时间。
图6 四种缓存替换策略的命中率对比
由图6可以看出，随着缓存比例增大，四种替换策略的命中率都在提高；相同缓存比例下，AdaHotscore和LFU命中率明显高于FIFO和LRU替换策略。
图7 四种缓存替换策略的查询时间对比
由图7可以看出，随着缓存比例增大，四种替换策略的查询时间都在减少；相同缓存比例下，AdaHotscore替换策略的查询时间最短。
5.3 可扩展性实验
数据可扩展性实验测试了不同规模数据集下，基于数据块的分层式索引查询系统的查询时间。由图8可以看出，随着数据集规模的扩大，系统的查询时间也呈线性增长，说明基于数据块的分层式索引查询系统在处理数据不断增长时仍保持着良好的可用性。
图8 数据扩展性实验
实验测试了基于数据块的分层式索引查询系统在不同节点规模下的查询时间，实验的节点数量由1逐渐增加到8。由图9可以看出，随着节点数量的增大，系统查询的时间逐渐减少并趋于平缓。
图9 节点扩展性实验
针对范围查询，本系统采用非主键索引数据分块管理的方法，并使用跳表结构管理数据块的元信息。为了使数据块的划分更加合理，本系统基于访问热度对数据块进行自适应调整。本系统通过跳表和分层式索引进行范围查询。同时，为了在缓存层获得较高的命中率，本系统使用基于自适应分块的缓存替换策略AdaHotscore。实验表明，与其他索引系统相比，本系统对非主键的范围查询性能有着显著地提升。