基于内存的HBase二级索引设计

崔 晨，郑林江，韩凤萍，何牧君

(1.重庆大学计算机学院，重庆400044; 2.重庆城市综合交通枢纽开发投资有限公司，重庆401121)(*通信作者电子邮箱15123034669@163.com)

0 引言

物联网和大数据的广泛应用，产生了海量的多类型实时数据。传统的数据存储与管理方法已难以适应当前大规模数据管理对效率的需求，因此非关系型数据库(Not Only SQL，NoSQL)［1］得以迅速发展。HBase作为NoSQL数据库的代表，已被广泛应用于各行各业的数据存储与管理中。索引是数据库中提高数据管理与查询效率的关键技术，HBase在行键(Rowkey)上建立了类B+树索引，可以高效地支持基于行键的快速数据查询［2］，但对非行键的列没有建立索引，故进行非行键的列的查询时，需要对全表进行扫描，这样的查询效率十分低下，极大限制了HBase在复杂条件下的查询性能。为解决这一问题，现有研究提出建立非行键的列与行键的索引，从而构建起二级索引方案，方案在对非行键的列进行查询时，先通过二级索引获取与其对应的行键，再通过行键到HBase中进行查找。

目前，国内部分企业和个人基于第三方开源软件进行索引设计，使用搜索服务器Solr［3］来构建HBase二级索引。Solr是一个基于Lucene［4］的企业级全文搜索服务器，用户可以通过超文本传输协议(HyperText Transfer Protocol，HTTP)请求向Solr提交HBase中的数据，建立非行键的列与行键的映射，生成索引;也可以通过HTTP Get操作提出查找请求返回索引中的行键。华为基于协处理器(Coprocessors)进行了HBase二级索引的实现，它利用HBase的原生代码即可获得索引，但这也带来插入数据速度变慢、升级维护困难以及索引无法动态修改等问题。葛微等［2］提出了名为HiBase的二级索引，它是一种基于分层式索引的设计方案，其将热点索引进行缓存，并建立高效的缓存替换策略来提高二级索引的查询速度。Zou等［5］提出了互补聚簇式索引(Complemental Clustering Index，CCIndex)，该方案把数据的详细信息也存放在索引表中，不需要通过获取的行键再到原表中去查找数据。

在索引实现方面，基于内存的索引相较于传统位于磁盘的索引在设计和架构上都大不相同，基于内存的索引在查询效率上得到了极大提升。广泛采用的内存索引有T树［6］、基于缓存敏感的CSS/CSB+树和改进的Hash索引等。T树，是针对B+树在内存中空间浪费的问题而提出的一种树型索引。T树所有节点都直接指引数据项，节省了中间节点所占空间。而针对Hash索引空间利用问题，提出了最小完美Hash索引［7］，其哈希函数不会产生冲突且函数的值域和参数域的大小完全相等，但这一哈希函数构造难度非常大。后来，研究发现CPU高速缓存对数据查询性能有着非常显著的影响［8］，所以研究者在B+树的基础上对缓存作了优化，提出了CSB+树［9］。在Hash索引的基础上，提出了可扩展Hash、桶链Hash等缓存敏感的索引结构。到了2007年，Ross［10］提出了基于现代处理器的Hash预取算法，将单指令多数据流(Single Instruction Multiple Data，SIMD)指令集融入到 Hash算法中，在内存环境中大大提高了索引的性能。文献［11］基于有界障碍(Bounded Disorder，BD)方法提出了一种BD树索引，其将树形结构与Hash表结构结合，上层是树结构，下层叶子节点是哈希表，每个哈希表中桶的大小等于CPU缓存块的大小。这样的索引结构既对缓存作了优化，又实现了针对Hash表的范围查找。文献［12］中根据BD树索引的思想，实现了B+树索引与Hash索引的结合并进行了实验，结果展现BD树索引具有较好的性能。

本文提出一种基于内存的HBase二级索引的设计方案。为HBase中非行键的列建立索引并存储在Spark集群中。Spark是一款基于内存的并行计算框架［13］，其将数据加载到内存中，然后在内存中完成计算，且Spark集群能构造一个大的内存环境。由于是将索引建立在内存中，所以在索引的选择上希望得到节约存储空间、查询效率较高的索引。本文根据要建索引的列的基数大小以及是否涉及范围查询构建了三种基于内存的索引，分别是位图索引、分段Hash索引以及BD森林索引，并利用Spark并行化的特点来提高索引的查询效率。

1 基于内存的HBase二级索引总体设计

1.1 二级索引结构

HBase对行键建立了索引，对非行键的列未建立索引，这严重影响了条件查询的效率。为此，针对HBase在进行非行键的列的查询和组合条件查询时效率较低的问题，本文对需要查询的列建立与行键对应的二级索引，建立的二级索引结构如图1所示。图1中对HBase的簇(Column Family，CF)的NAME列和ADDR.列在Spark上建立了非行键的列的索引，索引可以通过 NAME列或 ADDR.列中的属性值映射到HBase中对应的行键。有时会对NAME列与ADDR.列进行组合条件查询，故针对这两列建立了组合条件的索引，可以通过索引映射到满足这一组合条件的行键。

图1 HBase二级索引结构Fig.1 Secondary index structure in HBase

查询非行键的列或组合条件时，可以先通过位于Spark内存环境中的索引获取对应的行键，再利用行键在HBase中查询符合条件的记录。这样的二级索引能极大提高条件查询的效率。

1.2 二级索引查询框架

面对非行键的列或组合条件的查询，可以先建立上述结构的二级索引。该索引以弹性分布式数据集(Resilient Distributed Dataset，RDD)的形式存储在Spark的内存环境中，RDD是Spark内存计算中一种弹性分布式数据集，且在Spark上有许多内置操作，可以将其并行化地转换。为了防止断电内存数据的丢失，对主要的RDD进行磁盘持久化，也可从磁盘中读取历史数据的RDD。查询时在Spark中对索引的RDD进行操作，获取对应的行键，再用行键在HBase中查找对应的记录并返回给查询的客户端。图2展示了二级索引的查询框架。

图2 二级索引查询框架Fig.2 Secondary index query framework

这样的查询框架可以充分发挥HBase中行键的作用，同时利用了Spark内存计算和并行化的优势。为了提高框架的查询效率，本文要构建合适的内存索引用于该查询框架中，这将在第2章节具体讨论。

1.3 表和二级索引的构造

使用上述的二级索引，首先要在HBase中构造存储数据的表，其中行键设计是构造表的关键。由于HBase是无模式的，事先不需要定义列限定符和数据类型，只需利用数据中的相关字段构建每条数据的行键。在构建行键时，要选择反映数据重要特征的字段组合成行键，并且这样的行键要具有唯一性。例如在后面的实验中针对基于射频识别(Radio Frequency IDentification，RFID)的机动车电子车牌数据，本文选择采集点IP和通行时间这两个重要的字段来建立行键，同时在其基础上加入随机数，使行键更加唯一和分散，避免热点问题。如果行键过长，为了在读写以及存储时具有好的性能，可以对行键进行压缩处理。

在二级索引的构造过程中，建立一个辅助的记录表。对HBase表中新插入的数据存储到辅助的记录表中，每当记录表中的数据个数达到一定的阈值时，就对记录表中的数据建立对应的索引并以RDD的形式存储(具体的索引构建过程见第二章)，故所建的索引都是分段的索引，这样有利于Spark的并行操作。与此同时清空辅助的记录表，用于记录下一批新插入的数据，从而对这部分新的数据建立二级索引。由于HBase中更新操作实际上是插入新的数据，而本文在行键的构造中加入随机数使其唯一化，不存在行键相同根据时间戳来更新数据的情况，故本文中二级索引不进行更新。当在HBase的表中删除数据时，则要将RDD形式的索引全部删除，重新分批读取HBase中的数据，每读取一定数量的数据就建立分段的索引，以保证索引内容的正确性。

2 内存索引构建

列的基数是指该列拥有的不重复数值的个数。例如:员工信息表中性别这列的基数是2，只有“男”和“女”两个值。列的基数的大小直接影响索引的选择与构造。同时，是否涉及范围查询也决定了索引方法的选择。为此，根据各列基数大小以及是否涉及范围查询，本文构建了不同的内存索引。针对基数较小列，构建位图索引;针对基数较大但不涉及范围查询的列，构建分段Hash索引;针对基数较大且涉及范围查询的列，构建BD森林索引。整个索引构建的步骤流程如图3所示。

2.1 对基数较小列的索引

一般认为列基数小于100且小于HBase中的总列数的0.1%时，该列即为基数较小列。针对基数较小列，由于字段重复值较多，建立树形索引不能带来快速的查询响应，还会带来索引空间冗余，达不到“空间换取时间”的目的。因此，针对基数较小列，采用位图索引进行二级索引的构建。

位图索引是用二进制位0、1组成的位向量表示数据的索引信息，并通过将检索条件映射为二进制位的逻辑运算来实现高效的查询。设有一组数据，数据的总记录数为N，数据中有一列为基数较小列。对基数较小列建立索引，针对基数较小列的每一属性值a建立一个位向量X，X的长度为N，判断X的第j位Xj表示第j条记录在该列中的值是否为属性值a，若是a，则Xj=1;若不是a，则Xj=0。员工信息表中性别这一列建立的位图索引示例如图4所示。

图3 索引构建步骤流程Fig.3 Flowchart of index building step

图4 员工信息表的性别位图索引Fig.4 Bitmap index of employee information about sex

位图索引采用0、1来存储信息，在内存中所占空间很小。内存中一个字节的空间可以存储8条某个属性值的取值情况，例如800万条员工信息对性别为“男”的情况建立索引，则只需消耗不到1 MB内存空间。位图索引的另一优势就是可以将组合查询转为高性能的位运算。例如已经得到N条记录其A列中属性值a的位向量X和B列中属性值b的位向量W。若要查询的组合条件为A列中值为a且B列中值为b的记录时，只需将X与W进行按位与的运算得到位向量Z，若Zj=1，则第j条记录符合本文的查询条件。

在本文中，用字节数组来存储位图索引并将其建立在Spark构成的内存空间中。为了方便构造和提高构造速度，取每N条记录为一组构建分段的位图索引。每段位图索引在Spark内存中用parallelize方法转为RDD形式，RDD在Spark的环境中可以被缓存且支持并行操作。为了防止断电内存数据丢失，将这些RDD进行RDD.saveAsObjectFile执行操作，从而把数据持久化到硬盘中。在查询时，由于需要利用数组下标和数组中字节数值转为对应记录的取值情况，故将这些分段的位图索引按记录顺序进行整合，用Spark中RDD.collect执行操作转为一个整体的位于本地的有序数组。对位图索引进行查询就是对这一内存中的数组进行遍历，内存中连续空间遍历的速度我们是可以接受的，故针对基数较少的列建立位图索引是有效的。位图索引在Spark中的操作如图5所示。

图5 位图索引在Spark中操作过程Fig.5 Operation process of bitmap index in Spark

2.2 对基数较大但不涉及范围查询的列的索引

当HBase中某列的基数较大时，就可以使用Hash索引或树形索引。当该列不涉及范围查询时，即根据一个确定的值进行等值查询，选择能在O(1)的时间复杂度下准确查找的Hash索引。

本文中对基数较大但不涉及范围查询的列构建链接桶哈希，其结构如图6所示。在构建Hash索引时，仍将数据分段，建立分段Hash索引，这样不仅能方便后面的并行化查找，同时可以根据分段的大小事先确定桶的数目，以防桶的数目过小带来查询效率下降以及桶的数目过大带来空间浪费的问题。为了减少哈希表所占用的内存空间，提高负载因子，通常的负载因子为0.75，这里选用0.8，即要对 N条数据建立Hash索引，则先产生桶的数目为1.25*N的哈希表。虽然提高负载因子会增加桶中链的长度从而增加查询数据的时间开销，但这是时间成本和空间成本上的一种折中，是可以接受的。

图6 链接桶哈希结构Fig.6 Hash structure of link bucket

在查询时，对分段Hash索引进行并行的查找［14］，这些索引转为RDD的形式存储在内存中，在硬盘上也有备份。利用Spark中RDD.map转化操作算子对每个分段Hash索引进行时间复杂度为O(1)的快速查找。这样的查询速度非常理想，不会因数据量的增大产生巨大变化，这也是本文愿意提高负载因子的原因。索引在Spark中的操作如图7所示。

图7 分段哈希索引在Spark中操作过程Fig.7 Operation process of segmented hash index in Spark

2.3 对基数较大且涉及范围查询的列的索引

2.3.1 BD 树索引的结构

Hash索引不能进行范围查询，故面对HBase中某列基数较大且涉及范围查询时，本文采用BD树索引的思想，构建由多棵BD树索引组成的BD森林索引。其中BD树索引由B+树与哈希表结合得到，即索引的树结构是B+树，B+树的叶子节点由n个哈希桶组成，且每个哈希桶的大小等于CPU缓存块的大小，故哈希桶中存放数据是固定的。同时为了能进行范围查找，各叶子节点按顺序连接起来，可以通过指针进行查询。图8是BD树索引的结构。

图8 BD树索引结构Fig.8 Index structure of BD tree

在构造BD树索引时，使用递归的方法将关键字不断插入。先查找关键字所在的哈希表，然后定位到其所在的桶中，若桶未满则插入关键字;若桶已满则需分裂该节点，将原哈希表中所有关键字分配到两个新的哈希表中，分界可选原哈希表关键字的最大值和最小值的均值，同时对上层B+树进行修改，产生指向新的哈希表节点的指针。详细过程可以参考文献［11－12］。

在BD树索引的查询中，面对精确查询，根据关键字在B+树中找到对应的叶子节点，即哈希表，接着则是在哈希表中进行查询。BD树索引关键在于可以进行范围查询，当查询的关键字范围为［ks，ke］时，找到关键字ks所在的哈希表记为U，找到关键字ke所在的哈希表记为V，则U、V之间的哈希表的所有值(哈希表按顺序用指针串联在一起)、U中关键字大于ks对应的值和V中关键字小于ke对应的值是范围查询的结果。

2.3.2 BD 森树索引的结构

本文对基数较大且涉及范围查询的列构建BD森林索引，即多棵BD树索引，其结构如图9所示。

仍然将数据分段，对每一段建立BD树索引，并转为RDD的形式存储在内存中，利用Spark中操作对每个BD树索引进行查询，操作过程同图7的分段Hash索引。但这样在面对范围查询时，要对每棵BD树进行查询，最后将查询结果进行汇总，算法1描述了BD森林索引范围查询算法的过程。

算法1 BD森林索引范围查询算法。

输入 查询范围［ks，ke］的关键字 ks，ke。

输出 行键集合RQ。

RQ← //结果集合设为空

for each tree T in Tsdo //遍历每棵BD树索引

Hs← T.GetHash(ks) //通过树形索引查找ks所在的哈希表

He← T.GetHash(ke)

H←Hs

while next［H］≠ Hsdo

H ← next［H］

RQ∪allValue［H］ //将哈希表中所有值并入结果集合中

end while

for each map M in Hsdo //遍历哈希表

if key［M］ ＞ ksthen

//当遍历映射的键大于范围开始的关键字时

RQ∪value［M］ //将映射的值并入结果集合中

end if

end for

for each map M in Hedo

if key［M］ ＜ kethen//当遍历映射的键小于范围结束的关键字时

RQ ∪ value［M］

end if

end for

end for

构建BD森林索引是因为一次性将所有数据构造成BD树索引，在转化RDD时会因为树的递归构造次数［15］太多带来StackOverflowError问题，无法转为RDD存储在Spark内存环境中。构建BD森林索引，降低每棵树的高度，减少树的递归构造深度，将其成功转为RDD。范围查询时虽然要对森林中的每棵树进行操作，但可以利用Spark中 RDD.map转化操作算子进行并行操作，故效果是可以接受的。

3 实验与结果分析

图9 BD森林索引结构Fig.9 Index structure of BD forest

3.1 实验环境与数据

本文的实验环境是在三台虚拟机下搭建的HBase集群与Spark集群，为了进行对比实验还搭建了Solr集群。每台虚拟机的环境是1核CPU，2 GB内存，60 GB硬盘，操作系统是CentOS7。

本文的实验数据是基于RFID电子车牌的交通数据，其来源于重庆市智能交通系统，其数据模型如表1所示。数据模型中各字段的含义分别是:记录在表中的id号、采集点名称、行驶方向、采集点的IP标识、车辆的电子车牌号、车辆通过时间、车辆类型、号牌的种类以及车辆使用性质。数据存入HBase中，用01到99之间的随机数加上采集点IP标识加上通行时间的月日时分秒构成每条原始记录的行键(Rowkey)，例如表1中的第一条记录的行键为“19101112010229012445”(产生的随机数是19)。这样的行键具有唯一性和分散性。

在后面的实验中，主要对三种索引的检索效率进行了实验对比，期望基于这样的二级索引能在数据查询上带来效率的提高。另外对索引的大小也十分关注，期望索引所占空间合理，以便能在内存中存储，故在实验中对索引所占的空间大小也进行了实验测试。

表1 原始数据模型Tab.1 Original data model

3.2 结果分析

3.2.1 二级索引实验

在HBase中进行查询时通常需要利用行键，在不知道行键的情况下或通过过滤器扫描进行查找，但这样的查询速度非常慢。在本实验中分别从1000万、2000万、3000万和5000万数量级的数据中查找行键为“34101079500229080703”，内容为“金开大道，两路方向，10.10.79.50，1410080，2016-02-29 08:07:03，K33，02，D”的记录，分别使用行键查询和过滤器扫描两种方法进行查找，实验结果如图10所示。由图10可以看出，通过行键进行数据查询的时间是毫秒级的，而利用过滤器进行扫描查询的时间是秒级的，所以建立二级索引，在查询前事先获取行键是十分有必要的。后面将分别讨论前面的三种索引获取行键的性能，根据列的基数大小以及是否涉及范围查询选择位图索引、分段Hash索引和BD森林索引进行实验，并将实验结果与基于Solr建立的二级索引获取行键的性能进行对比。

3.2.2 位图索引实验

在实验数据中，车辆使用性质这一列有“非运营”“租赁”“警用”“工程抢险”等值，其基数为16;车辆类型这一列有“大型普通客车”“大型卧铺客车”“轿车”“中型罐式货车”等值，其基数为52。故车辆使用性质和车辆类型这两列都属于基数较小的列，在这两列上进行组合条件查询时，可以使用位图索引。例如，要查询车辆类型为“H37”，车辆使用性质为“K”的记录，即查找类型为轻型自卸货车的工程抢险车辆的过车记录。对这两列建立位图索引，将属性值为“H37”的位向量与属性值为“K”的位向量进行按位与操作，得到这一组合条件查询的位图索引。对索引的位向量进行遍历得到所需的行键。在1000万、2000万、3 000万和5000万数量级的数据中利用位图索引查找类型为轻型自卸货车的工程抢险车辆的过车记录行键的时间和基于Solr获取行键的时间如图11所示。由图11可以发现，位图索引查找时间是毫秒级的且优于基于Solr的二级索引。得到这些行键后，就可以在HBase中快速查到相应的记录。

另外，位图索引所占的存储空间要远小于Solr中的索引，如图12所示，故位图索引适用于在内存中使用。

图10 使用行键查询和过滤器扫描查询效率比较Fig.10 Query efficiency comparison of rowkey query and filter scan

图11 位图索引和基于Solar索引查询行键时间比较Fig.11 Time comparison of querying rowkey by bitmap index and Solar-based index

图12 位图索引和基于Solar索引存储空间大小比较Fig.12 Storage space size comparison of bitmap index and Solar-based index

3.2.3 分段Hash索引实验

当要根据车辆的电子车牌号来查询表中的记录时，可以在该列建立分段Hash索引来获取相应的行键。在1 000万、2000万、3000万和5 000万数量级的数据中利用分段Hash索引获取电子车牌号为“1410080”的过车记录行键的时间和基于Solr获取行键的时间如图13所示，可以发现分段Hash索引的效果是较好的。由于使用了分段Hash索引进行了并行化的查找，故查找时间并没有因为数据量的增加而发生陡增，基本维持在100 ms左右获取行键，大大提高了查询效率。

图13 分段Hash索引和基于Solar索引查询行键时间比较Fig.13 Time comparison of querying rowkey by segment Hash index and Solar-based index

3.2.4 BD 森林索引实验

有时要对某辆车查询其在一段时间内的记录，这时涉及到时间的范围查询，故选择将电子车牌号与通行时间这两列结合在一起建立BD森林索引。在1000万、2000万、3000万和5000万数量级的数据中利用BD森林索引获取电子车牌号为“1410080”在“2016-02-29 08:00:00”至“2016-02-29 12:00:00”期间的过车记录行键的时间和基于Solr获取行键的时间如图14所示。由图14可以看出，当数据量增大时，可以适当提高哈希表中桶的个数来维持树的高度，但桶的个数过大也会影响范围查询中首尾两哈希表的查找性能。BD森林索引由于数据结构的复杂性，故查询时间稍长但获取行键后进行查询的综合时间仍比通过HBase过滤器扫描的时间要短不少，获取行键的时间也少于基于Solr获取行键的时间。

图14 BD森林索引和基于Solar索引查询行键时间比较Fig.14 Time comparison of querying rowkey by BD forest index and Solar-based index

3.2.5 二级索引所占空间实验

整个二级索引以RDD的形式存储在Spark构建的内存环境中，故期望索引能够在内存中存储。在1 000万、2000万、3000万和5000万数量级的数据中建立整体的二级索引(包含关于车辆使用性质、车辆类型的位图索引、关于电子车牌号的分段Hash索引以及关于电子车牌号和通行时间的BD森林索引)的空间大小如图15所示。在当前的数据规模下索引可以在集群的2560 MB执行内存中存储。

图15 二级索引空间大小Fig.15 Space size of secondary index

4 结语

本文针对HBase无法在非行键的列上建立索引导致条件查询效率低下的问题建立了基于内存的二级索引。根据每列基数大小以及是否涉及范围查询构建不同类型的索引并进行改进，使其在Spark搭建的内存环境中进行高效的检索。实验结果表明这样的二级索引大大提高了查询效率，值得构建。对此下一步准备对索引的结构进行再次的改进，希望减小Hash索引的空间大小以及提高树形索引的并行度，并考虑分布式索引的改进，从而继续提高二级索引的整体性能并将其运用在实时数据处理中。