HBase 高性能复杂条件查询引擎

写在前面

在这次的审稿过程中有幸得到了 Ted Yu 和梁堰波先生的反馈，大家就一些感兴趣的内容进行了讨论。该方案由一个智能交通解决方案演变而来，设计之初仅寄希望于通过二级索引提升查询性能，由于在前期架构时充分考虑了通用性以及对复杂条件的支持，在后来的演变中逐渐被剥离出来形成了一个通用的查询引擎。Ted Yu 对“查询决策器”表示了关心，他指出类似的组件同时也是 Phoenix, Impala 用于支持 SQL 查询的核心组件，但是这类组件很难引入到 HBase 中，因为 HBase 专注于 byte[] 的操作。对此，方案在设计时避开了“SQL 解析”和“在各种数据类型与 byte[] 之间进行转化”的棘手问题，而是使用了一组可以描述查询的 Query API，这与 Hibernate 中提供 Criteria 接口的做法非常相似，在 Hibernate 中既支持 HQL 语句的查询又支持使用 Criteria 接口以编程方式描述的查询，对于我们来说选择类似后者的做法实现起来要快速和容易的多，而查询条件中的值在构造之初就以 byte[] 的形式传递，避免了决策器解析时的类型判定和转化问题。

题记

——索引的实质是另一种编排形式的数据冗余，高效的检索源自于面向查询特别设计的编排形式，如果再辅以分布式的计算框架，就可以支撑起高性能的大数据查询。

正文

Apache HBase™是一个分布式、可伸缩的 NoSQL 数据库，它构建在 Hadoop 基础设施之上，依托于 Hadoop 的迅猛发展，HBase 在大数据领域的应用越来越广泛，成为目前 NoSQL 数据库中表现最耀眼，呼声最高的产品之一。像其他 NoSQL 数据库一样，HBase 也有其适用范围，就应对复杂条件的查询来说，一般认为它并不是非常适合，熟悉 HBase 的开发人员对此应该有一定的体会，但是基于普遍的需求，开发者们希望 HBase 在保持高性能优势的同时能对复杂条件的查询给予一定的支持，而本文将要介绍的正是一种在 HBase 现行机制下以非侵入式实现的基于二级多列索引的高性能复杂条件查询引擎。

问题

目前 HBase 主要应用在结构化和半结构化的大数据存储上，其在插入和读取上都具有极高的性能表现，这与它的数据组织方式有着密切的关系，在逻辑上，HBase 的表数据按 RowKey 进行字典排序， RowKey 实际上是数据表的一级索引（Primary Index），由于 HBase 本身没有二级索引（Secondary Index）机制，基于索引检索数据只能单纯地依靠 RowKey，为了能支持多条件查询，开发者需要将所有可能作为查询条件的字段一一拼接到 RowKey 中，这是 HBase 开发中极为常见的做法，但是无论怎样设计，单一 RowKey 固有的局限性决定了它不可能有效地支持多条件查询。通常来说，RowKey 只能针对条件中含有其首字段的查询给予令人满意的性能支持，在查询其他字段时，表现就差强人意了，在极端情况下某些字段的查询性能可能会退化为全表扫描的水平，这是因为字段在 RowKey 中的地位是不等价的，它们在 RowKey 中的排位决定了它们被检索时的性能表现，排序越靠前的字段在查询中越具有优势，特别是首位字段具有特别的先发优势，如果查询中包含首位字段，检索时就可以通过首位字段的值确定 RowKey 的前缀部分，从而大幅度地收窄检索区间，如果不包含则只能在全体数据的 RowKey 上逐一查找，由此可以想见两者在性能上的差距。

受限于单一 RowKey 在复杂查询上的局限性，基于二级索引（Secondary Index）的解决方案成为最受关注的研究方向，并且开源社区已经在这方面已经取得了一定的成果，像 ITHBase、IHBase 以及华为的 hindex 项目，这些产品和框架都按照自己的方式实现了二级索引，各自具有不同的优势，同时也都有一定局限性，本文阐述的方案借鉴了它们的一些优点，在确保非侵入的前提下，以高性能为首要目标，通过建立二级多列索引实现了对复杂条件查询的支持，同时通过提供通用的查询 API，以及完全基于配置的索引结构，完全封装了索引的创建和使用细节，使之成为一种通用的查询引擎。

原理

“二级多列索引”是针对目标记录的某个或某些列建立的“键 - 值”数据，以列的值为键，以记录的 RowKey 为值，当以这些列为条件进行查询时，引擎可以通过检索相应的“键 - 值”数据快速找到目标记录。由于 HBase 本身并没有索引机制，为了确保非侵入性，引擎将索引视为普通数据存放在数据表中，所以，如何解决索引与主数据的划分存储是引擎第一个需要处理的问题，为了能获得最佳的性能表现，我们并没有将主数据和索引分表储存，而是将它们存放在了同一张表里，通过给索引和主数据的 RowKey 添加特别设计的 Hash 前缀，实现了在 Region 切分时，索引能够跟随其主数据划归到同一 Region 上，即任意 Region 上的主数据其索引也必定驻留在同一 Region 上，这样我们就能把从索引抓取目标主数据的性能损失降低到最小。与此同时，特别设计的 Hash 前缀还在逻辑上把索引与主数据进行了自动的分离，当全体数据按 RowKey 排序时，排在前面的都是索引，我们称之为索引区，排在后面的均为主数据，我们称之为主数据区。最后，通过给索引和主数据分配不同的 Column Family，又在物理存储上把它们隔离了起来。逻辑和物理上的双重隔离避免了将两类数据存放在同一张表里带来的副作用，防止了它们之间的相互干扰，降低了数据维护的复杂性，可以说这是在性能和可维护性上达到的最佳平衡。

图 1：Sample 表 Region 1 的数据逻辑视图

让我们通过一个示例来详细了解一下二级多列索引表的结构，假定有一张 Sample 表，使用四位数字构成 Hash 前缀 [ii] ，范围从 0000 到 9999，规划切分 100 个 Region，则 100 个 Region 的 RowKey 区间分别为 [0000,0099]，[0100,0199]，……，[9900,9999]，以第一个 Region 为例，请看图 1，所有数据按 RowKey 进行字典排序，自动分成了索引区和主数据区两段，主数据区的 Column Family 是 d，下辖 q1,q2,q3 等 Qualifier，为了简单起见，我们假定 q1,q2,q3 的值都是由两位数字组成的字符串，索引区的 Column Family 是 i，它不含任何 Qualifier，这是一个典型的“Dummy Column Family“，作为区别于 d 的另一个 Column Family，它的作用就是让索引独立于主数据单独存储。接下来是最重要的部分，即索引和主数据的 RowKey，我们先看主数据的 RowKey，它由四位 Hash 前缀和原始 ID 两部分组成，其中 Hash 前缀是由引擎分配的一个范围在 0000 到 9999 之间的随机值，通过这个随机的 Hash 前缀可以让主数据均匀地散列到所有的 Region 上，我们看图 1，因为 Region 1 的 RowKey 区间是 [0000,0099]，所以没有任何例外，凡是且必须是前缀从 0000 到 0099 的主数据都被分配到了 Region 1 上。接下来看索引的 RowKey，它的结构要相对复杂一些，格式为：RegionStartKey- 索引名 - 索引键 - 索引值，与主数据不同，索引 RowKey 的前缀部分虽然也是由四位数字组成，但却不是随机分配的，而是固定为当前 Region 的 StartKey，这是非常重要而巧妙的设计，一方面，这个值处在 Region 的 RowKey 区间之内，它确保了索引必定跟随其主数据被划分到同一个 Region 里；另一方面，这个值是 RowKey 区间内的最小值，这保证了在同一 Region 里所有索引会集中排在主数据之前。接下来的部分是“索引名”，这是引擎给每类索引添加的一个标识，用于区分不同类型的索引，图 1 中展示了两种索引：a 和 b，索引 a 是为字段 q1 和 q2 设计的两列联合索引，索引 b 是为字段 q2 和 q3 设计的两列联合索引，依次类推，我们可以根据需要设计任意多列的联合索引。再接下来就是索引的键和值了，索引键是由目标记录各对应字段的值组成，而索引值就是这条记录的 RowKey。

现在，假定需要查询满足条件 q1=01 and q2=02 的 Sample 记录，分析查询字段和索引匹配情况可知应使用索引 a，也就是说我们首先确定了索引名，于是在 Region 1 上进行 scan 的区间将从主数据全集收窄至 [0000-a, 0000-b)，接着拼接查询字段的值，我们得到了索引键：0102，scan 区间又进一步收窄为 [0000-a-0102, 0000-a-0103)，于是我们可以很快地找到 0000-a-0102-0000|63af51b2 这条索引，进而得到了索引值，也就是目标数据的 RowKey：0000|63af51b2，通过在 Region 内执行 Get 操作，最终得到了目标数据。需要特别说明的是这个 Get 操作是在本 Region 上执行的，这和通过 HTable 发出的 Get 有很大的不同，它专门用于获取 Region 的本地数据，其执行效率是非常高的，这也是为什么我们一定要将索引和它的主数据放在同一张表的同一个 Region 上的原因。

架构

在了解了引擎的工作原理之后来我们来看一下它的整体架构：

图 2：引擎的整体架构

引擎构建在 HBase 的 Coprocessor 机制之上，由 Client 端和 Server 端两部分构成，对于查询而言，查询请求从 Client 端经由 HTable 的 coprocessorExec 方法推送到所有的 RegionServer 上，RegionServer 接收到查询请求后使用“查询决策器”分析查询条件，比对索引元数据，在找到适合该查询的最优索引后，解析索引区间，然后委托“索引查询器”基于给定的最优索引和解析区间进行数据检索，如果没有找到合适的索引则委托“全表查询器”进行全表扫描。当各 RegionServer 的局部查询结果返回之后，引擎的 Client 端还负责对它们并进行合并汇总和排序，从而得到最终的结果集。对于插入而言，当主数据试图写入时会被 Coprocessor 拦截，委托“索引构造器”根据“索引配置文件”创建指向当前主数据的所有索引，然后一同插入到数据表中。

让我们来深入了解一下引擎的几个核心组件。对于引擎的客户端来讲，最重要的组件是一套用于表达复杂查询请求的 Query API，在这套 API 的设计上我们借鉴了 IHBase 的一些做法，通过对查询条件（Condition）进行抽象和建模，得到一套典型的基于“复合模式”（Composite Pattern）的 Class Hierarchy，使之能够优雅地表达基于 AND 和 OR 的多重复合条件。以图 1 所示的 Sample 表为例，使用 Query API 构造一个查询条件为“(q1=01 and q2<02) or (q1=03 and q2>04)”的 Java 代码如下：

图 3：引擎客户端的 Query API 示意代码

查询请求到达 Server 端以后，由 Coprocessor 委派查询决策器进行分析以确定使用何种查询策略应对，这是查询处理流程上的一个关键结点。查询决策器需要分析查询请求的各项细节，包括条件字段、排序字段和排序，然后和索引的元数据进行比对找出性能最优的索引，有时候对于一个查询请求可能会有多个适用索引，但是查询性能却有高下之分，因此需要对每一个候选索引进行性能评估，找出最优者，性能评估的方法是看哪个索引能最大限度地收窄检索区间。索引的元数据来自于索引配置文件，图 4 展示了一份简单的索引配置，配置中描述的正是图 1 中使用的索引 a 和 b 的元数据，索引元数据主要是由索引名和一组 field 组成，filed 描述的是索引针对的目标列（ColumnFamily:Qualifier）。实际的索引配置通常比我们看到的这份要复杂，因为在生成索引时有很多细节需要通过索引配置给出指引，比如如何处理不定长字段，目标列使用正序还是倒序（例如时间数据在 HBase 中经常需要按补值进行倒序处理），是否需要使用自定义格式化器对目标列的值进行格式化等等, 完全配置化的索引元数据使创建和维护索引的成本大大降低，为上层应用根据实际需求灵活设计索引提供了保障。

图 4：一份简单的索引配置文件

在确定最优索引之后，查询决策器开始基于最优索引对查询条件进行解析，解析的结果是一组索引区间，区间内的数据未必都满足查询条件，但却是通过计算所能得到的最小区间，索引查询器就在这些区间上进行检索，通过配备的专用 Filter 对区间内的每一条数据进行最后的匹配判断。图 5 展示了一个条件为 q1=01 and 01<=q2<=03 的查询请求在 Sample 表 Region 1 上的解析和执行过程。

图 5 ：查询请求 q1=01 and 01<=q2<=03 在 Sample 表 Region 1 上的解析和执行过程示意

对于那些找不到索引的查询请求来说，查询决策器将委派全表查询器处理，全表查询器将跳过索引区，从主数据区开始通过配备的专用 Filter 进行全表扫描。显然，相对于索引查询，全表扫描的执行效率是很低的，它的存在是为了在所有索引都不适用的情况下起“托底”作用，以此保证任意复杂条件的查询都能得到处理，所以这里引出一个非常重要的问题，就是在索引查询和全表扫描之间的选择与权衡问题。通常人们总是希望所有的查询都越快越好，虽然从理论上讲建立覆盖任意条件查询的索引是可能的，但这是不现实的，因为创建索引是有代价的，除了占用大量的存储空间之外还会影响到数据插入的性能，所以不能无节制地创建索引，理性的做法是分析并筛选出最为常用的查询，针对这些查询建立相应的索引，优化查询性能，而对于那些较为“生僻”的查询则使用全表扫描的方式进行处理，以此在存储成本、插入性能和查询性能之间找到一种理想的平衡。最后要补充说明的是，不管是使用索引查询还是进行全表扫描，这些动作都是通过 Coprocessor 机制分发到所有 Region 上去并发执行的，即使是全表扫描其性能也将远超过 HBase 原生的 Scan 操作！

应用

由于引擎设计之初就以非侵入性为前提，所以引擎的部署与集成就与引入第三方类库无异，唯一需要上层应用提供的是面向数据表的索引配置文件。设计索引主要以业务需求为导向，先分析并梳理出常用的查询用例，然后针对查询用例所涉及的字段和排序要求按相似性进行分组，尽可能让单个索引同时支持多种相近的查询，减少索引的种类和数量，提升索引复用率。在这方面如下设计原则可供参考（注：以下原则均以“不考虑排序”为前提）：

• N 个字段组合的查询只需要建立一个包含该 N 个字段的索引，建立按这个 N 字段其他顺序排列的索引是没有意义的。因此，以 N 个字段组合为条件的查询只需要 C(n, n)=1 个索引。
• 一个包含 N 个字段的索引同时是以从第 1 到第 N-1 个字段为条件的查询索引，以及从第 1 到第 N-2 个字段为条件的查询索引，依此类推，也是仅以第 1 个字段为条件的查询索引。因此，包含 N 个字段的索引总计可以支持 C(n,1)=n 种查询组合。
• 基于上述两点，任意一个索引的字段组合不应该是另一个索引字段组合的前缀部分，这样设计的索引才会有较高的复用率。

假如某表有 A、B、C、D 四个字段，在不考虑排序的前提下，如果要用索引支持以任意字段或字段组合为条件的查询，则索引的设计方法如下：四字段索引只需要一个，假定取 ABCD（它将同时支持 ABCD、ABC、AB 和 A 四种查询）。三字段索引分别以 A、B、C、D 开头向后循环取足三个字段，得到：ABC、BCD（它将同时支持 BCD、BC 和 B 三种查询）、CDA（它将同时支持 CDA、CD 和 C 三种查询）和 DAB（它将同时支持 DAB、DA 和 D 三种查询），其中 ABC 是 ABCD 的前缀，故舍弃。按照同样的方法，两字段索引要分别从保留下来的三个三字段索引中依次以每一个字段开头取足两个字段，然后去除重复和前缀重叠的索引，最终得到 DB（它将同时支持 DB 和 D 两种查询）和 AC（它将同时支持 AC 和 A 两种查询），总计是 6 个索引，最后可以再根据实际需求剪裁掉不需要的索引。

在上述原则的表述中特别注明了“不考虑排序“这个前提，对于索引来说，”排序“是一个很“敏感”的要求，索引本身只有一种排序（即按索引首字段进行的字典排序），如果查询请求的排序与索引排序不同，则索引直接出局，即使它们的字段完全匹配，也就是说排序会极大地消弱索引的复用度，对于我们的引擎来说，排序字段应该受到严格的控制。实际上，很多大数据系统都需要对排序进行限制，比如淘宝上的商品检索，可供排序的字段只有人气，销量，信用和价格，因为排序需要针对数据全集进行计算，如果不是针对有限的排序字段建立索引或是离线计算并缓存结果，按任意字段排序的查询是很难在线返回的。

小结

综合前文所述，方案主要有如下几个显著的优势：

1. 高性能：引擎的高性能源自两方面，一是二级多列索引，二是基于 Coprocessor 的并行计算
2. 非侵入性：引擎构建在 HBase 之上，既没有对 HBase 进行任何改动，也不需要上层应用做任何妥协
3. 高度可配置：索引元数据是完全基于配置的，可以轻便灵活地创建和维护索引
4. 通用性：引擎的前端查询接口和后端索引处理都是基于通用目标设计的，不依赖于任何具体表

限于 HBase 自身的特点，方案本身也有一定的局限性，一是它不能随意地支持任意的条件查询，这一点前文已经给出了分析和建议，二是在插入主数据时需要伴随插入多份索引从而对写入性能产生了一定的影响，如何控制写入和查询的竞争关系需要根据系统的读写比进行权衡，对于数据写入实时性要求不高或者数据是离线导入的系统来说，可以考虑使用批量导入工具，特别是以直接生成 HFile 的方式导入的话可以在很大程度上消除引入索引后的写入压力。

[1] 理论上基于 HBase 的 Filter 机制可以实现任意复杂条件的查询，但是那样做就彻底放弃了 RowKey 作为索引的利用价值，大多数查询的性能都将变得非常差。

[2] Hash 前缀的长度和 Region 数量有着密切的关系，由于索引和主数据的分配高度依赖 RowKey 前缀和 Region 的 RowKey 区间，引擎严禁 Region 进行自动切分，开发人员需要在前期对 Region 数量和前缀长度进行规划，本例中取四位前缀意味着最多可以支持 10000 个 Region。

关于作者

耿立超，架构师，CSDN 博客专家，博客 http://blog.csdn.net/bluishglc 目前正从事大数据领域的研发工作，对企业级应用架构、SaaS、分布式存储和领域驱动设计有丰富的实践经验，喜欢摄影和旅行。

感谢 Ted Yu 对本文的审校，包研对本文的策划。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ）或者腾讯微博（ @InfoQ ）关注我们，并与我们的编辑和其他读者朋友交流。