基于HBase的内存数据库索引设计成果

（一）HBaset概述

HBase是一个开源数据库，是面向列分布的。这一数据库的设计理念来源于一篇论文——《Bigtable：一个结构化数据的分布式存储系统》。从这篇论文可以发现，在Hadoop平台上，Bigtable可以进行开源实现。HBase与传统的关系数据库是不同的，这是因为它适合于非结构化的数据存储。HBase还有另一个特点：它不是基于行的，而是基于列的。HBase作为一种非结构化的数据库，它是在Hadoop上运行的，HDFS在MapReduce分布式计算模式和分布式存储系统上能够得到充分利用。这就说明，HBase可以对很多数据进行处理，这些数据可以在一个很大的计算集群中，同时在列数上几乎是没有上限的。不仅Hadoop有一定的优势，HBase这一分布式数据本身的能力也很强。对于key-value^[3]存储模式而言，它在实施查询上的能力是比较强的，HBase能够进行融合，并对离线数据进行相应处理，同时对这些数据也能进行批处理。总体来说，HBase非常适合处理和存储海量数据，利用较低的成本就可以实现其性能和处理结果。

1.HBase数据模型

HBase数据模型与传统的关系数据模型不太相同。传统的关系数据模型主要涉及列、表和数据类型，在规则上是比较复杂、严格的，并以此对数据间的关系进行约束，而解决这些复杂、严格的关系的方式就是结构化数据。在HBase的数据存储上，这些数据关系都是不太严格的。HBase中，在表与表之间建立复杂的关联关系的做法是不被提倡的，很多数据都被放置于一张大表上，表中的行和列都是不确定的。这样的关联关系其实是不太复杂的，同时数据在形态上也是不确定的。这说明这些数据是半结构化的或是非结构化的。对于数据而言，其在逻辑模型上的设计不同于在物理模型上的设计。对于关系型数据库而言，其数据在表中进行存储的记录一般情况下都是结构化的。因此，关系型数据库本身的物理模型对于结构化数据在硬盘和内存上的存储是适应的。HBase因其非结构化数据在存储上的特点，导致对其进行设计时有相应的物理模型。同时，存储硬件的发展是很快的，为了适应硬件结构，应提供相应的物理模型，以保证该模型的实现，并对其逻辑进行一定程度的修改。这种修改有着双向的影响，若要保持优化数据库系统的合理性，就需要对数据在逻辑模型和物理模型上都进行更深层次的了解。

HBase的特点除了存储非结构化的数据之外，其本身在可扩展性上也是比较强的。在非结构化的逻辑模型中，其复杂关系是不存在的。这就导致数据在存储硬盘中处于分散状态，从而非常方便存储，同时对逻辑模型的建立也产生一定的影响。除此之外，对于这样的物理模型，这种设计使得HBase对传统的关系型数据库不具备优势。例如，HBase数据之间的关系约束是不能实施的，同时也不支持多行事物。正是因为它们在关系上的不同，才导致在以下两个方面产生一定的影响。

（1）逻辑模型：有序映射的映射集合。

HBase在逻辑数据模型上的描述方法是多种多样的，我们对其进行探讨时，主要探讨的是关于有序映射的内容。有序映射是映射的一种，HBase可以将其视为一种在映射中进行嵌套的、实体化的和无限的版本。HBase在进行存储数据的标识时可以利用坐标系统来实现。

（2）物理模型：面向列族。

与关系数据模型相同，HBase在数据表中的组成也是包括行和列的，其中列的分组是按照列族进行的。这样的分组由HBase数据逻辑模型决定。列族在物理模型上进行表示时，其在数据表上的每个列都是在一个HFile中独立存储的。在数据量不断增加的同时，一个File文件会向着多个HFile文件进行分裂。可以这样说，一个列可以实现对多个连续存储的HFile文件，但每个HFile只能属于一个列。每个列组都是由多个列构成的，在硬盘上都对HFile集合进行保存。在物理存储上，对文件进行隔离，使得在列组的底层上方便对数据进行管理。

HBase在HFile中的记录是按照键值存储的。HFile只是二进制文件，不能直接读取。HFile可以在多条记录中进行使用，但在不同的时间版本和列限定符上，其记录都是不同的。除此之外，在文件中不存在空记录。如果其中没有数据，HBase就不会对任何东西进行存储。列族在存储上也是以列为单位的，同一行中，其在一个列族上的数据不会在同一个HFile中进行存放。

2.HBase检索原理

HBase与传统的关系型数据库之间具有一定的相同点。HBase对于不同行的区分是通过标识符实现的，也就是每行数据在其行键上是不同的。HBase对数据进行检索时使用的方式都是行键，主要通过三种方式实现对数据的检索。首先，对单个rowkey进行访问，将这一数值在HBase上进行相应的get操作，可以获得其中的唯一记录。其次，对rowkey进行扫描，并在startrowkey和endRowkey上进行设置。通过对这一范围进行相应的行扫描，可以获取一批必需的记录。最后，当rowkey这一数值不存在时，就需要对全表进行扫描，即在HBase表上进行相应的扫描。也就是说，在这张表中的所有记录都要进行数据的获取，但这种方式在效率上相对比较低。

3.行扫描操作（Scan）

对于主键来说，其存储需要按照字典字节进行，对其中一定范围的记录要通过Scan来实现，主要由HBase来提供。例如，当用户需要查询表T1中所有编号大于或等于“00010”的记录时，可以按照字典字节的顺序进行排序，即0001＜00010。也就是说，满足条件的编号中的最小编号的前缀是“0001”，这样就可以指定Scan的开始行为“0001”，然后Scan将会依次返回“00010”“00011”“00012”这三条记录。HBase通过这种方式给用户提供了一种高效的范围查询方法。

（二）索引构建流程

1.流式数据索引构建方法

在很多应用中，数据的流向是向HBase中的结点进行的。对于面向流式数据的索引构建而言，它是HBase在索引构建上的重要方式。流式数据索引构建的方法就是利用Coprocessor接口实现索引构建，其接口的提供者就是HBase。

C o p r o c e s s o r指代的就是在H B a s e上的R e g i o n服务器中运行的代码，通过加载Coprocessor中的用户所制定的代码，Region的功能得到实现。为了保证Coprocessor本身是灵活的，HBase提供了两种Coprocessor，即Observer和Endpoint。Observer与传统的数据库中的触发器是相似的，当发生相关的操作时，会触发Observer中的用户代码；Endpoint与数据库中的存储功能是相似的，通过代码，它实现了对一段已经被优化的数据的访问。

我们所提出的索引建构模块主要是对Coprocessor进行建构，从而完成索引工作的。其类型就是Observer。更具体地说，RegionObserver接口是由HBase所提供的，实现这一接口需要以下的回调函数来提供：prePut，在客户端存储一条记录之前会被触发调用；preDelete，在客户端删除一条记录之前会被触发调用。

prePut主要是根据索引元在信息上与用户所进行的Put操作对其进行相应分析的。Put操作的数据包中是包含索引列的，这就需要包含对其进行索引的数据。索引数据要分别在索引缓存层和持久储存层上进行更新，同时对索引范围表进行更新。

preDelete主要根据用户所发起的Delete操作获取被删除记录的主键的，而主键要从Region中实现对信息的全部获取。对于索引信息元来说，要对记录进行相应的分析，如果这一记录中含有索引列，那么这一记录就可以在索引数据上实现持久存储层与索引缓存层的生成。通过索引数据对其主键的索引，从而实现对其中历史数据的删除。

2.静态数据索引构建方法

为了让HBase中已经存在的用户表数据实现对索引的建构，人们提出了一种静态数据索引建构的方法。由于静态数据一般是比较大的，所以为了保证其索引建构速度的增加，静态数据索引在行化的构建过程利用了HadoopMapReduce程序。MapReduce的构造索引过程如下：

（1）Map输入。输入＜Row，Result＞，其中Row为用户表的主键，Result为通过Row获得的 HBase记录。

（2）Map处理过程。根据索引元信息，为每个索引元输入＜Row，Result＞，生成其对应的索引数据，并将索引数据更新到分层式索引存储系统中。在这一过程中，MapReduce程序不需要任何操作就能实现。而HBase在用户表记录中是相互独立的，所以MapReduce所具备的能力加速了索引构建的过程。

（三）索引系统的设计

1.HT树的操作(www.xing528.com)

对于HT树来说，其索引过程中需要完成三项工作，即查找、插入和删除。其中，查找是插入和删除的基础，HT树在结构上是通过插入和删除进行相应合并或分裂的。由于Hash存在着冲突，所以需要考虑如何解决这一冲突。同时对于HT树来说，原本的插入和删除需要相应地进行调整，而且要优化HT树在空间上的利用率。下面从算法上对这几种操作分别进行介绍。

（1）HT树的查找。

优秀的索引算法都会支持对指定值的精确查找和对一系列键值的范围查找。

HT树在查找上分为两个步骤：第一步，获得叶子结点的数值，也就是Hash表；第二步，在Hash表中提取数据。第一步是与B+树的查找相对应的，第二步相当于Hash表。HT树的查找在形式上是递归的，其查找的具体过程如下：

在当前查询结点中，如果是叶子结点，那么根据Hash算法实现Key对Hash表中桶的获取，同时根据顺序查找并确定Key的位置，实现对其在数值上的获取；如果不是叶子结点，则基于B+树本身具有的性质，这一结点中的关键字是根据从小到大来排序的，Key和关键字在其大小上进行的定位取决于B+树在其下一级结点的确定。这一子结点运用递归的方法实现了以上查找过程。

（2）HT树的插入。

通过对HT树的查找，确定了Key在HT树中的位置，也就是对叶子结点进行插入。然后在Hash表中也要进行相应的插入，对Key在Hash表中的桶进行计算，以及Key和其相应的value数值要在这一桶中进行插入。在插入后，Hash表在对其进行填装时，如果其在因子上比最大填装因子更小，就结束插入操作。如果Hash表在填装因子上比最大填装因子更大，就会导致结点出现分裂的情况（关于结点分裂的具体步骤，下文会进行相应的阐述）。在完成分裂后，HT树的插入操作也就完成了。

HT树在分裂上的操作可以看成是叶子结点和非叶子结点的分裂。对于非叶子结点的分裂来说，它在一般情况下都是由叶子结点发生分裂而导致的。

如果某个叶子结点N进行Hash表的插入，则对于当前的填装因子来说，比最大的填装因子更大，就导致叶子结点和Hash表出现分裂操作。Hash表在分裂时是根据Hash表中不同的Key数值实现其对的分段的，前半段的Key值要比后半段的Key值更小。这两个Hash表出现的散列导致数据虽已完成，但会出现表的断裂情况。随后，通过创建一个叶子结点实现Hash表的保存。由于B+树的有序性，新创建的这一结点与原本的结点是兄弟结点，其位置在原结点的右边。

叶子结点所导致的分裂可能使HT树出现一定的问题。当一个新的结点插入时，要相应地判断其在结构上的合理性。如果是合理的，就要完成分裂；如果是不合理的，就要在结构上对HT树进行调整，导致HT树在结点上出现分裂的情况。对于H树来说，其在上层结点上出现的分裂会导致B+树的分裂。

（3）HT树的删除。

HT树的所有数据都在其叶子结点中进行存储。对于删除操作，第一步是通过HT树，利用查找算法确定其在HT树中的对应位置。如果该Hash表在Key值上的数目是1，就可以对这一叶子结点直接进行删除。如果该Hash表在Key值上的数目大于1，就对其进行判断后予以删除。在对Hash表的因子进行填装时，需判断其因子是不是小于最小因子。如果大于最小填装因子，就要对Key进行删除，也就是说对value值进行相应的删除。如果小于最小填装因子，就要对这一结点和相邻结点在填装因子上的平均值与最大填装因子上的数值进行比较。如果其更小，就对两点进行相应的合并，这两个结点在Hash表中进行汇总后重新散列形成一个新的Hash表；如果其更大，就要对这两个Hash表在个数上进行平均操作，从而实现对两个Hash表的划分，最终求出这一关键字结点。完成以上操作后，对HT树中的Key要进行相应的删除。

对叶子结点进行删除后，HT树在其结构上可能会遭到破坏，即上层关键字结点会被删除。关键字结点在删除上的算法可以参考对B+树的删除算法。

2.系统设计

HBase数据管理系统是根据rowkey在其顺序上实现对数据的组织的，从而进一步实现B+树在其索引结构上的建立。就目前来看，HBase数据管理系统对于rowkey是不能提供二级索引功能的。对于用户来说，其对HBase数据在非rowkey上进行查询时，可以对Scan表进行相应扫描，或者对MapReduce架构全表进行扫描，以满足其在条件上的获取。但是这两种方式在效率上是较低的，无法满足查询的需要。

我们虽然利用MapReduce技术实现了数据在访问上的并行化，并在一定程度上提高了查询的速度，但在数据量比较大且时间延迟比较长的情况下，进行全表扫描的时间是比较长的。因此，我们要通过其他方法实现对它的设计。二级索引不仅能提高查询的效率，而且能对系统结构的复杂性和其存在的困难进行相应的管理，是重要的研究目标。对于现存的一些方案，我们要进行借鉴和分析。考虑到系统的特性，最终采用的是基于Spark所建立的二级索引。

网络环境是在基本通信协议上建立的操作系统，通过相应的软件在运行、部署、管理和开发上进行支持。它是分布计算的中间件。分布计算的中间件起的是承上启下的作用，即同时在一体化网络计算中支持和支撑相应的软件，所以也被称为网络计算中间件或软件中间件，简称中间件。对于系统软件和服务程序而言，中间件是独立存在的，并借助分布式应用软件在不同的技术中实现资源上的共享。中间件独立于CAS操作系统，通过计算机在资源和网络通信上进行相应管理，可以对两个独立的应用程序进行相应的连接。虽然连接的系统接口是不同的，但是对于中间件而言，依旧可以实现它们之间信息的交互。中间件在执行过程中的一个重要途径就是信息的传递。同时，通过中间件，应用程序在多个平台和环境中都可以得到使用。

对于本系统来说，主要是在HBase与Spark上提供非入侵式中间件。对于中间件来说，非入侵式设计的优点是针对HBase和Spark平台的，但是在中间件的运行过程中，不需要对其原有的环境和数据进行修改。同时，中间件也可以在现有的数据库上运行。这样就可以选择性地实现中间件在接口上的供给，无论中间件出现何种问题，都不会造成数据丢失和环境的损伤。

3.对范围查询的优化

在进行查询时，如果查询范围比较大，则该范围中的索引列值是较大的，所以索引列值在按照顺序进行单值查询发起请求时，会大幅度增加其网络通信开销。除此之外，对于这样的顺序化请求，其在集群中整体上的并发能力并没有得到充分利用。

为了进一步提升查询效率，可以从三方面做出改变。首先，对于范围汇总的索引列值而言，其在进行查询时的管理工作是由同一结点实现的，应对这些索引列值进行相应合并，并对这一结点的批量查询发起请求。其次，对该结点所涉及的范围内发起查询请求。最后，对于索引缓存层而言，当出现数据未被命中的情况时，该结点在其内存的索引服务进程中未被命中的标志是无法返回的，所以查询请求需要向基于HBase的持久存储层转发，同时将查询所得的结果交还给客户端。对其进行优化时，其在范围查询上的具体过程如下：

（1）根据客户端在其范围内的不同查询条件，HBase在其索引范围表中获取该范围内的索引列值。

（2）如果存在索引列值，则这些索引列值是一致的。其存储结点的地址要利用Hash算法进行计算，并将索引列值和与其相关的结点地址进行对应。

（3）由相关结点发起的查询请求应该是并发的，同时对于一个结点而言，其发起的多个请求会发生合并，从而形成一个批量请求。

（4）各个结点在内存上所进行的索引服务，在进程上是对查询请求所做出的响应。如果查询内容在内存中，就要直接返回其中的数据；否则，服务进程就要对持久层发起查询请求，并返回相应的查询结果。

（5）客户端汇总从各服务结点返回的查询结果。