李斌 郭景维 彭骞

摘   要：针对HBase缺乏二级索引的功能，导致在非行键列上的查询需要使用过滤器并配合全表扫描完来完成。在大数据的场景下性能较差的问题，结合HBase表行键的索引结构与关系型数据库的二级索引结构提出了索引列值聚集的二级索引解决方案。此外，还提出二级索引机制的支持联合索引与特殊的索引列值的处理，提高了二级索引的性能并拓宽了二级索引的适用场景。最后，通过构建系统测试证明了二级索引极大地提高了HBase的查询效率。

关键词：计算机软件;HBase;二级索引;聚集;转义

中图分类号： TP311.1                                                文献标识码：A

Design of HBase Secondary indexes for big Data Storage

LI Bin？覮，GUO Jing-wei，PENG Qian

（State Grid Ningxia Electric Power Co. Ltd.，Yinchuan，Ningxia 750011，China）

Abstract： Due to the lack of secondary indexes in HBase，queries on non-row key columns need to use filters and complete the scan in the full table. In the scenario of massive data，the performance is poor. relational database proposes combining the indexes of HBase table row keys. With the secondary index structure of the structure a secondary index solution for index column value aggregation is proposed. In addition，this paper studies that the secondary index mechanism supports the processing of joint indexes and special index column values，improves the performance of the secondary index and broadens the application of the secondary index. Finally，this paper proves that the secondary index greatly improves the HBase query efficiency by building system tests.

Key words： computer software;HBase;secondary index;aggregation;escape

随着Web2.0时代的蓬勃发展和移动互联网的快速普及，互联网的数量呈现爆炸增长的趋势。根据IDC的预测，截止到2021年，互联网上的数据将增加到90ZB[1]。在大数据的场景下，单机的数据库无法满足存储的要求，而关系型数据库的架构导致其水平扩展能力不足[2]，实现分布式存储较为困难。在此场景下，分布式的非关系型数据库通过摒弃关系型数据库的部分关系模型特性[3]，实现了易于扩展和高性能读写的特点，解决了关系型数据库难以处理大数据存储的问题。其中HBase是雅虎公司牵头，根据Google的BigTable模型[4]实现的一个开源列式存储数据库，拥有良好的扩展性并且适合大规模数据的读写。此外，列存储相比于行存储来说，同一列的数据在磁盘上是聚集存储的。数据分析往往只会使用表的若干列，所以列存储的方式可以通过磁盘顺序读取的优势使用较少量的磁盘IO完成数据的读取，而行存储的方式则会因为读取整行而读入过多的无用的列，导致大量的磁盘IO开销[5]，所以HBase更适合数据分析型的业务。

虽然HBase拥有良好的扩展性并且适合大规模数据的读写，但是也存在以一些缺陷，其中最主要的是不支持二級索引[6]。虽然HBase表的行键上拥有索引结构，但是在列上不支持创建二级索引[7]，对于非行键列的条件查询必须使用过滤器配合全表扫描的方式来完成，在数据量极大的情况下全表扫描的效率极低[8]，无法满足实时查询的要求。

针对该问题，在深入研究关系型数据库B+tree索引结构与HBase行键索引结构的基础上提出了索引列值聚集形式的二级索引结构，通过将索引列值聚集在对应索引表的行键上来构建二级索引的结构，从整体上提高HBase整体的查询性能。此外，实现的二级索引结构支持除了支持单列索引之外还支持联合索引，且能处理索引列为空值等特殊情况。

1   二级索引的现有解决方案

本小节主要介绍HBase二级索引的现有解决方案，包括Solr和IHBase。

1.1   Solr

Solr是一个开源的全文搜索引擎，能够支持文本的高效搜索[9]。当创建HBase索引时，可以使用Solr来保存对应的索引列值并创建倒排索引。当基于索引列进行查询时通过Solr中维护的索引结构来过滤出符合条件的行，然后再查询HBase。

上面的方案的缺点是客户端需要同时使用Solr以及HBase的API才能完成创建索引、查询，增加了使用上的复杂性，且引入的Solr系统大大增加了系统的维护成本。此外，由于Solr使用的协议为HTTP，网络通信性能相对较低[10]。

1.2   IHBase

IHBase方案通过拦截HBase中缓存MemStore写满时的刷盘事件，然后将该MemStore中的数据构建索引并存在数据表的另一个列中，之后查询的时候IHBase会根据索引列中的数据进行加速查询。其优点是直接在HBase内部进行索引的创建，减少了网络IO传输[11]。缺点是需要对HBase进行重构，且当MemStore没有写满时，其中的数据无法创建索引，可能导致数据的不一致。

2   HBase二级索引结构设计

本小節首先介绍关系型数据库使用的单列二级索引结构和联合二级索引结构，在此基础上介绍HBase 索引列聚集的二级索引结构。

2.1   关系型数据库索引结构

2.1.1   单列索引结构

关系型数据库的二级索引结构一般使用B+tree来实现[12]，结构如图1所示：

在图1所示B+tree结构二级索引中，叶子节点保存的是数据表行记录的索引列值（如name）和对应行记录的数据表的主键（如id），非叶子节点保存索引值（索引值不一定是真实表中的数据）和对应的指针。根据该索引结构查询时，每次根据查询的值和非叶子节点的索引值进行比较，根据指针对应的值范围选择其中一个指针进入到更深层的节点（例如查询条件为name=“Eric”时，根据Root节点的信息计算出“Alice” < “Eric” < “Sally”，因此选择P2指针进入到N2节点中）。最后遍历到叶子节点后获得对应的记录的列值以及主键，如果筛选的列不在索引结构中，则需要根据主键id去原始的数据表中查询筛选的列。

在B+tree索引结构中，每次遍历到深层的节点后，可以将剩余的节点剪枝，由于B+tree是平衡的多叉树，因此图1中每次进入到深层的节点后可以剪枝其余2/3的节点，最后的时间复杂度为3O（logN），相比于全表遍历的O（N）时间复杂度，查询性能提升较大。

2.1.2   联合索引结构

联合索引是指一个索引结构中有多个索引列的索引，在多条件查询时联合索引只需要遍历一个索引树结构，因此磁盘IO开销比使用多个单列索引进行查询的磁盘IO开销少[13]。

索引的结构和单列索引类似，结构如图2所示：

图2是非主键列（age和salary）的联合索引结构，叶子节点保存的是索引列值的元组和数据表的主键。非叶子节点保存的是索引列的列值元组（索引值不一定是真实表中的数据，例如图2中Root节点的元组（18，3）和（35，8）不是真实的数据）和对应的指针。元组之间的大小由索引列从左到右优先级依次降低的方式确定（优先按照左边的列值进行比较，相等再按后续列值比较）。图2的索引结构中，索引值的大小为（18，3） < （21，5） < （32，3）。

根据联合索引查询结构进行查询的过程和单列索引类似，每次根据查询条件和非叶子节点中的元组值进行比较，然后选择对应的指针进入深层次的节点，直到获取叶子节点中的数据，图2所示的联合索引结构的查询时间复杂度也为3O（logN）。

2.2   HBase二级索引结构

根据关系型数据库的二级索引结构，提出了索引列聚集的二级索引结构，通过将索引列的列值聚集索引表的行键上来构建HBase的二级索引。原始数据表如表1所示。

表2所示的单列索引使用“列值_数据表行键”的形式（“_”为分隔符）进行构建。由于HBase表的行键上自带有类似于B+tree的LSM-tree索引结构[14]，因此构建之后的索引表行键索引结构如图3所示：

根据图3，二级索引结构以聚集的方式将Col1列相同的的列值聚集在一起，并根据HBase表行键来自动构建索引。当基于索引列查询时，通过查询条件构建索引表的行键前缀即可利用索引来实现查询效率的提高（例如查询“Col1=‘B”时，构建前缀“B”即可以使用图3所示的二级索引结构进行数据的剪枝和高效查询）。

表3所示的联合索引使用“列值1_列值2_..._列值n_数据表行键”的形式构造。当基于联合索引进行查询时，也是根据查询条件构建索引表行键的前缀，使用索引进行数据的过滤。由于联合索引是按照索引列从左到右优先级降低的顺序排序的，因此当某个索引列的列值确定后，该索引列的后继索引列是有序的（例如在表3中，当Col1列的列值确定为B后，对应范围内的Col2列的列值有序），因此除了基于完整的联合索引结构的查询之外，还可以基于联合索引的前缀索引进行查询（例如查询条件为“Col1=‘A”也可以使用表3所示的联合索引，因为Col1列整体在索引结构中有序）。

3   空列值与分隔符预处理、解析

表2和表3展示了一般情况下HBase二级索引的结构，但是当列值为空或者列值中存在分隔符“_”时，直接根据构造索引表行键可能会导致后续出现解析错误。例如索引列为（Col1，Col2，Col3，Col4），数据行中对应的列值分别为“v1”，“v2”，空值，以及“v＼”，行键为“001”。

如果直接构建索引表行键，则构造的结果为“v1_v2__v＼_001”，后续基于该行键查询时会出现解析错误。

基于以上的问题，本文提出了转义和替换的方案，使用转义符（单个字符，记为“＼”）和空值替换符（单个字符，记为“N”）的方案来处理上述的问题。

3.1   索引表行键预处理

预处理在构建索引表行键之前先通过“N”和“＼”对数据进行处理，避免后续可能发生的解析错误问题。此处转义和替换的策略为：

1.使用“N”替换空值。

2.使用“＼”将列值中已有的“＼”和“_”转义为“＼＼”和“＼_”，并将单独的“N”转义为“＼N”。

其中使用“＼”来将单独的“N”进行转义的原因是可能存在列值和“N”相同（非空），不额外处理会和代表空值的“N”混淆，故此处加上'＼”来进行转义。如果原先的字节值为“＼N”，则会根据策略2 转换为“＼＼N”。

使用“＼”来转义列值中的“＼”和“_”是将列值中作为实际数据的“＼”和“_”进行特殊的标记，防止和真正的转义符“＼”或者分隔符“_”混淆。

当完成了上面的流程后，使用拼接的策略将索引列进行拼接得到索引表的行键。本小节开头的例子经过预处理和拼接后，得到的结果为“v1_v＼2_N_v＼＼_001”。

3.2   行键解析

当通过索引表查询获得行键后，需要将之前转义和替换的特殊字符去除以便进行列值的解析，以便后续的进一步查询。此处解析的流程为：

1. 当遍历遇到转义符“＼”时，说明是真正的转义符。如果后一个字符是“N”，则保留“N”以及该转义符，并一起拷贝到临时缓冲区中;如果后一个字符不是“N”可以丢弃该转义符并拷贝后一个字符到临时缓冲区中（例如“＼＼”和“＼_”都丢弃第一个“＼”并拷贝后面的字符，而“＼N”的情况不丢弃“＼”完整拷贝）。通过对真正转义符的处理，将被转义的字符作为真实的数据字符处理，避免了解析错误。

2.当遇到分隔符“_”时，说明是真正的分隔符（如果是数据中的分隔符则已经根据第1步将其拷贝到临时缓冲区），可以直接跳过并将之前拷贝的临时缓冲区对应到具体的列值上。如果临时缓冲区是“N”则设置对应的列值为空（原先列值为“N”根据条件1可以推出对应临时缓冲区中为“＼N”，不会和空值混淆），其他的内容直接转换。

3.遇到其他字符时，说明是具体的数据，直接拷贝到临时缓冲区中。

当根据上面的步骤处理完一个索引表行键后，就可以得到分隔的索引列值以及最后的数据表行键，用于后面的进一步查询。

4   基于二级索引结构的查询流程

当查询的列为行键列时，直接使用HBase原有的查询功能即可实现，不需要经过专门的二级索引表进行数据过滤。

当查询的列为非行键列时，需要根据二级索引进行数据的过滤，二级索引功能在单独的索引服务端中实现（索引表仍然保存在HBase中）。基于非行键列的查询过程如图4所示：

在图4所示的查询过程中，客户端首先将查询请求发送给二级索引服务端，服务端根据查询条件和维护的表索引信息计算出命中的索引，然后根据预处理过程處理查询条件并构建索引表行键前缀，然后使用HBase查询的API去索引表中查询符合客户端查询条件的行键。

如果查询请求中筛选的列已经在索引结构中，则直接构建结果返回（例如客户端查询的列为Col1，查询条件为“Col1 >= ‘A”，且该列有索引，则直接根据索引表的行键构建结果）。

如果查询请求中筛选的列不在索引结构中（例如查询的列为Col3，索引结构包含的列为Col2），则需要提取出索引表行键中的数据表行键去数据表中查询对应行的待筛选列信息（如图4的alt可选部分）。由于数据表的查询是基于有索引的行键，因此效率很高。

当完成了所有的查询步骤之后，服务端构建完整的结果返回给客户端。

5   实   验

本小节主要介绍HBase二级索引的实验，包括数据与环境、实验的设计以及结果与分析。

5.1   实验的数据与环境

该系统使用阿里妈妈在天池开放的广告数据集作为实验数据。其中广告的点击数据包含了8天内共计114万用户的1600万次广告展示或者点击的日志记录。其中包括的信息有user_id（用户的ID），adgroup_id（广告单元ID），time_stamp（时间戳），clk（是否点击）。

实验的环境包括3台CentOS 6.6虚拟机，每个虚拟机为单核单线程、2.1GHZ主频的CPU，4G内存。在每台虚拟机上上安装Hadoop2.6.0，HBase1.0.1以及Zookeeper 3.4.6组成HBase集群。二级索引的服务端和客户端均运行在另一台虚拟机上，配置相同。

5.2   实验的设计

实验从整体上分为写入和查询共两种测试，测试指标分别为写入操作的系统响应时间和查询操作的系统响应时间。在每种测试内部，分别使用10万，100万和1000万的数据量以及无索引、单个单列索引，单个联合索引进行性能测试。

5.3   实验的结果与分析

数据的写入的实验分别在不同的数据量和不同的索引结构下进行数据写入，数据写入的实验结果如下表4所示：

表4中，在索引固定的情况下，随着写入数据量的增长，写入的耗时也随之增加，两者接近线性的关系。而在写入数据量固定时，随着索引的加入或者索引的结构变得复杂（如联合索引的结构比单列索引复杂），写入的时间也随之增加，这是因为服务端需要单独维护索引表信息，故增加了写入的时间。例如单个索引的加入使得写入的时间增加了大约在40%，而联合索引由于索引结构更加复杂，写入时间的增加也更明显，达到了60%。由于大批量写入的情况较少，而在小数据量写入的时候，写入开销增加40%至60%带来的延迟较小，因此该结果也在可接受的范围内。

数据查询的实验分别在不同的数据量下，使用不同的索引结构进行非行键列的等值查询（例如“user_id=1025”，无索引使用和单个索引相同的查询条件，联合索引使用完整的结构索引结构进行等值查询），实验结果如表5所示：

表5中，在索引结构固定的的情况下，数据的查询速度和数据量呈现线性的关系，这是因为在无索引的情况下，非行键列的查询需要通过全表扫描来实现。而在查询的列上建立的索引后，查询的效率有了极大的提高，这是因为根据本文的索引聚集的策略，索引列聚集在索引表的行键上，而HBase表的行键自带LSM-tree的索引结构，因此可以通过构建索引表的行键前缀来利用索引结构将查询的时间复杂度缩减到O（logN）级别。

6   结   论

提出了索引列值聚集形式的二级索引结构，通过将索引列值在索引表的行键上聚集实现了HBase的二级索引结构，并且能够支持单列索引以及联合索引，使得非行键列的查询能够利用已有的二级索引结构来加快查询的效率。此外，使用特殊的转移符“＼”和空值替换符“N”完成了索引列值包含分隔符以及索引列值为空两种特殊情况的处理，使得提出的二级索引结构适用的范围更加广阔。最后，通过对比实验证明了提出的索引结构极大地提升了HBase非行键列查询的效率。

参考文献

[1]    陈墨，程刚，王小娟.基于互联网海量数据的热点分析系统研究[J].互联网天地，2015（09）：30—35.

[2]    金澈清，钱卫宁，周敏奇，等.數据管理系统评测基准：从传统数据库到新兴大数据[J].计算机学报，2015，38（01）：18—34.

[3]    李绍俊，杨海军，黄耀欢，等.基于NoSQL数据库的空间大数据分布式存储策略[J].武汉大学学报：信息科学版，2017，42（02）：163—169.

[4]    魏玲，魏永江，高长元.基于Bigtable与MapReduce的Apriori算法改进[J].计算机科学，2015，42（10）：208-210+243.

[5]    余林琛，廖小飞.多虚拟机环境下磁盘写优化机制[J].计算机工程与科学，2012，34（10）：78—82.

[6]    崔丹，史金鑫.基于Redis实现HBase二级索引的方法[J].软件，2016，37（11）：64—67.

[7]    李聪颖，王瑞刚，于金良.大数据分布式全文检索系统的设计与实现[J].计算机与数字工程，2016，44（12）：2426—2430.

[8]    毕冉，李建中，高宏.无线传感器网络中最小化通信开销的近似监测算法[J].计算机学报，2015，38（10）：2092—2105.

[9]    王文贤，陈兴蜀，王海舟，等.一种基于Solr的HBase海量数据二级索引方案[J].信息网络安全，2017（08）：39—44.

[10]  许杰，冷冰，李明桂，等.大数据处理技术在安全审计系统中的应用[J].通信技术，2016，49（03）：346—351.

[11]  唐长城，杨峰，代栋，等.一种基于HBase的数据持久性和可用性研究[J].计算机系统应用，2013，22（10）： 175—180.

[12]  CIMERMANCIC P，MEDEMA M H，CLAESEN J，et al. Insights into secondary metabolism from a global analysis of prokaryotic biosynthetic gene clusters[J]. Cell，2014，158（2）： 412—421.

[13]  宋传鸣，陈规胜，何兴，等.调色板编码中双向预测的索引值优化分配[J].模式识别与人工智能，2017，30（05）：385—393.

[14]  YUE Y，HE B，LI Y，et al. Building an efficient put-intensive key-value store with skip-tree[J]. IEEE Transactions on Parallel and Distributed Systems，2017，28（4）： 961—973.