二級(jí)索引與索引Join是多數(shù)業(yè)務(wù)系統(tǒng)要求存儲(chǔ)引擎提供的基本特性，RDBMS早已支持，NOSQL陣營(yíng)也在摸索著符合自身特點(diǎn)的最佳解決方案。
這篇文章會(huì)以HBase做為對(duì)象來(lái)討論如何基于Hbase構(gòu)建二級(jí)索引與實(shí)現(xiàn)索引join。文末同時(shí)會(huì)列出目前已知的包括0.19.3版secondary index,ITHbase, Facebook方案和官方Coprocessor的介紹。

理論目標(biāo)
在HBase中實(shí)現(xiàn)二級(jí)索引與索引Join需要考慮三個(gè)目標(biāo)：
1，高性能的范圍檢索。
2，數(shù)據(jù)的低冗余（存儲(chǔ)所占的數(shù)據(jù)量）。
3，數(shù)據(jù)的一致性。

性能與數(shù)據(jù)冗余，一致性是相互制約的關(guān)系。
如果你實(shí)現(xiàn)了高性能地范圍檢索，必然需要靠冗余索引數(shù)據(jù)來(lái)提升性能，而數(shù)據(jù)冗余會(huì)導(dǎo)致更新數(shù)據(jù)時(shí)難以實(shí)現(xiàn)一致性，特別是分布式場(chǎng)景下。
如果你不要求高效地范圍檢索，那么可以不考慮產(chǎn)生冗余數(shù)據(jù)，一致性問(wèn)題也可以間接避免，畢竟share nothing是公認(rèn)的最簡(jiǎn)單有效的解決方案。

理論結(jié)合實(shí)際，下文會(huì)以實(shí)例的方式來(lái)闡述各個(gè)方案是如何選擇偏重點(diǎn)。
這些方案是經(jīng)過(guò)筆者資料查閱和同事的不斷交流后得出的結(jié)論，如有錯(cuò)誤，歡迎指正：

1，按索引建表
每一個(gè)索引建立一個(gè)表，然后依靠表的row key來(lái)實(shí)現(xiàn)范圍檢索。row key在HBase中是以B+ tree結(jié)構(gòu)化有序存儲(chǔ)的，所以scan起來(lái)會(huì)比較效率。
單表以row key存儲(chǔ)索引，column value存儲(chǔ)id值或其他數(shù)據(jù) ，這就是Hbase索引表的結(jié)構(gòu)。

如何Join？
多索引（多表）的join場(chǎng)景中，主要有兩種參考方案：

1，按索引的種類(lèi)掃描各自獨(dú)立的單索引表，最后將掃描結(jié)果merge。
這個(gè)方案的特點(diǎn)是簡(jiǎn)單，但是如果多個(gè)索引掃描結(jié)果數(shù)據(jù)量比較大的話，merge就會(huì)遇到瓶頸。

比如，現(xiàn)在有一張1億的用戶信息表，建有出生地和年齡兩個(gè)索引，我想得到一個(gè)條件是在杭州出生，年齡為20歲的按用戶id正序排列前10個(gè)的用戶列表。
有一種方案是，系統(tǒng)先掃描出生地為杭州的索引，得到一個(gè)用戶id結(jié)果集，這個(gè)集合的規(guī)模假設(shè)是10萬(wàn)。
然后掃描年齡，規(guī)模是5萬(wàn)，最后merge這些用戶id，去重，排序得到結(jié)果。

這明顯有問(wèn)題，如何改良？
保證出生地和年齡的結(jié)果是排過(guò)序的，可以減少merge的數(shù)據(jù)量？但Hbase是按row key排序，value是不能排序的。
變通一下 – 將用戶id冗余到row key里？OK，這是一種解決方案了，這個(gè)方案的圖示如下：

merge時(shí)提取交集就是所需要的列表，順序是靠索引增加了_id，以字典序保證的。

2， 按索引查詢種類(lèi)建立組合索引。
在方案1的場(chǎng)景中，想象一下，如果單索引數(shù)量多達(dá)10個(gè)會(huì)怎么樣？10個(gè)索引，就要merge 10次，性能可想而知。

解決這個(gè)問(wèn)題需要參考RDBMS的組合索引實(shí)現(xiàn)。
比如出生地和年齡需要同時(shí)查詢，此時(shí)如果建立一個(gè)出生地和年齡的組合索引，查詢時(shí)效率會(huì)高出merge很多。
當(dāng)然，這個(gè)索引也需要冗余用戶id，目的是讓結(jié)果自然有序。結(jié)構(gòu)圖示如下：

這個(gè)方案的優(yōu)點(diǎn)是查詢速度非常快，根據(jù)查詢條件，只需要到一張表中檢索即可得到結(jié)果list。缺點(diǎn)是如果有多個(gè)索引，就要建立多個(gè)與查詢條件一一對(duì)應(yīng)的組合索引，存儲(chǔ)壓力會(huì)增大。

在制定Schema設(shè)計(jì)方案時(shí)，設(shè)計(jì)人員需要充分考慮場(chǎng)景的特點(diǎn)，結(jié)合方案一和二來(lái)使用。下面是一個(gè)簡(jiǎn)單的對(duì)比：

	單索引	組合索引
檢索性能	優(yōu)異	優(yōu)異
存儲(chǔ)	數(shù)據(jù)不冗余，節(jié)省存儲(chǔ)。	數(shù)據(jù)冗余，存儲(chǔ)比較浪費(fèi)。
事務(wù)性	多個(gè)索引保證事務(wù)性比較困難。	多個(gè)索引保證事務(wù)性比較困難。
join	性能較差	性能優(yōu)異
count,sum,avg,etc	符合條件的結(jié)果集全表掃描	符合條件的結(jié)果集全表掃描

從上表中可以得知，方案1,2都存在更新時(shí)事務(wù)性保證比較困難的問(wèn)題。如果業(yè)務(wù)系統(tǒng)可以接受最終一致性的話，事務(wù)性會(huì)稍微好做一些。否則只能借助于復(fù)雜的分布式事務(wù)，比如JTA，Chubby等技術(shù)。
count, sum, avg, max, min等聚合功能，Hbase只能通過(guò)硬掃的方式，并且很悲劇，你可能需要做一些hack操作（比如加一個(gè)CF,value為null），否則你在掃描時(shí)可能需要往客戶端傳回所有數(shù)據(jù)。
當(dāng)然你可以在這個(gè)場(chǎng)景上做一些優(yōu)化，比如增加狀態(tài)表等，但復(fù)雜性帶來(lái)的風(fēng)險(xiǎn)會(huì)更高。
還有一種終極解決方案就是在業(yè)務(wù)上只提供上一頁(yè)和下一頁(yè)，這或許是最簡(jiǎn)單有效的方案了。

2，單張表多個(gè)列族，索引基于列
Hbase提供了列族Column Family特性。
列索引是將Column Family做為index，多個(gè)index值散落到Qualifier，多個(gè)column值依據(jù)version排列（CF, Qualifer, Version Hbase會(huì)保證有序，其中CF和Qualifier正序，Version倒序）。

舉個(gè)典型的例子，就是用戶賣(mài)了很多商品，這些商品的標(biāo)題title需要支持like %title%查詢。傳統(tǒng)基于RDMBS就是模糊查詢，基于search engine就是分詞+倒排表。
在HBase中，模糊查詢顯然不滿足我們的要求，接下來(lái)只能通過(guò)分詞+倒排的方式來(lái)存儲(chǔ)。基于CF的倒排表索引結(jié)構(gòu)見(jiàn)下圖：

取數(shù)據(jù)的時(shí)候，只需要根據(jù)用戶id（row key）定位到一個(gè)row，然后根據(jù)分詞定位到qualifier，再通過(guò)version的有序list，取top n條記錄即可。不過(guò)大家可能會(huì)發(fā)現(xiàn)個(gè)問(wèn)題，version list的總數(shù)量是需要scan全version list才能知道的，這里需要業(yè)務(wù)系統(tǒng)本身做一些改進(jìn)。

如何join？
實(shí)現(xiàn)方式同方案1里的join，多個(gè)CF列索引掃描結(jié)果后，需要走merge，將多個(gè)索引的查詢結(jié)果conjunction。

兩個(gè)方案的對(duì)比似乎變化就是一個(gè)表，一個(gè)列，但其實(shí)這個(gè)方案有個(gè)最大的好處，就是解決了事務(wù)性的問(wèn)題，因?yàn)樗械乃饕际歉鷨蝹€(gè)row key綁定的，我們知道單個(gè)row的更新，在hbase中是保證原子更新的，這就是這個(gè)方案的天然優(yōu)勢(shì)。當(dāng)你在考慮單索引時(shí)，使用基于列的索引會(huì)比單表索引有更好的適用性。
而組合索引在以列為存儲(chǔ)粒度的方案里，也同樣可以折中實(shí)現(xiàn)。理解這種存儲(chǔ)模式的同學(xué)可能已經(jīng)猜到了，就是基于qualifier。

下表對(duì)比了表索引和列索引的優(yōu)缺點(diǎn)：

	列索引	表索引
檢索性能	檢索數(shù)據(jù)需要走多次scan，第一次scan row key，第二次scan qualifier，第三次scan version。	只需要走一次row key的scan即可。
存儲(chǔ)	在沒(méi)有組合索引時(shí)，存儲(chǔ)較節(jié)省	在沒(méi)有組合索引時(shí)，存儲(chǔ)較節(jié)省
事務(wù)性	容易保證	保證事務(wù)性比較困難
join	性能較差，只有在建立組合條件Qualifier的時(shí)候性能會(huì)有所改善	性能較差，只有在建立組合表索引的時(shí)候性能會(huì)有所改善
額外的問(wèn)題	1，同一個(gè)row里每個(gè)qualifier的version是有大小限制的，不能超過(guò)Int的最大值。（別以為這個(gè)值很大，對(duì)于海量數(shù)據(jù)存儲(chǔ)，上億很平常） 2，version的count總數(shù)需要額外做處理獲取。 3，單個(gè)row數(shù)據(jù)超過(guò)split大小時(shí)，會(huì)導(dǎo)致不能compaction或compaction內(nèi)存吃緊，增加風(fēng)險(xiǎn)。
count,sum,avg,etc	符合條件的結(jié)果集全表掃描	符合條件的結(jié)果集全表掃描

雖然列索引缺點(diǎn)這么多，但是存儲(chǔ)節(jié)省帶來(lái)的成本優(yōu)勢(shì)有時(shí)還是值得我們?nèi)ミ@么做的，何況它還解決了事務(wù)性問(wèn)題，需要用戶自己去權(quán)衡。
值得一提的是，F(xiàn)acebook的消息應(yīng)用服務(wù)器就是基于類(lèi)似的方案來(lái)實(shí)現(xiàn)的。

3，ITHBase
方案一中的多表，解決了性能問(wèn)題，同時(shí)帶來(lái)了存儲(chǔ)冗余和數(shù)據(jù)一致性問(wèn)題。這兩個(gè)問(wèn)題中，只要解決其中一項(xiàng)，其實(shí)也就滿足了大多數(shù)業(yè)務(wù)場(chǎng)景。
本方案中，著重關(guān)注的是數(shù)據(jù)一致性。ITHbase的全稱(chēng)是 Indexed Transactional HBase，從名字中就能看出，事務(wù)性是它的重要特性。

ITHBase的事務(wù)原理簡(jiǎn)介
建一張事務(wù)表__GLOBAL_TRX_LOG__，每次開(kāi)啟事務(wù)時(shí)，在表中記錄狀態(tài)。因?yàn)槭腔贖base的HTable，事務(wù)表同樣會(huì)寫(xiě)WAL用于恢復(fù)，不過(guò)這個(gè)日志格式被ITHbase改造過(guò)，它稱(chēng)之為T(mén)HLog。
客戶端對(duì)多張表更新時(shí)，先啟動(dòng)事務(wù)，然后每次PUT，將事務(wù)id傳遞給HRegionServer。
ITHbase通過(guò)繼承HRegionServer和HReogin類(lèi)，重寫(xiě)了大多數(shù)操作接口方法，比如put, update, delete, 用于獲取transactionalId和狀態(tài)。
當(dāng)server收到操作和事務(wù)id后，先確認(rèn)服務(wù)端收到，標(biāo)記當(dāng)前事務(wù)為待寫(xiě)入狀態(tài)（需要再發(fā)起一次PUT）。當(dāng)所有表的操作完成后，由客戶端統(tǒng)一做commit寫(xiě)入，做二階段提交。

4，Map-reduce
這個(gè)方案沒(méi)什么好說(shuō)的，存儲(chǔ)節(jié)省，也不需要建索引表，只需要靠強(qiáng)大的集群計(jì)算能力即可導(dǎo)出結(jié)果。但一般不適合online業(yè)務(wù)。

5，Coprocessor協(xié)處理器
官方0.92.0新版正在開(kāi)發(fā)中的新功能- Coprocessor ，支持region級(jí)別索引。詳見(jiàn):
https://issues.apache.org/jira/browse/HBASE-2038

協(xié)處理器的機(jī)制可以理解為，server端添加了一些回調(diào)函數(shù)。這些回調(diào)函數(shù)如下：

The Coprocessor interface defines these hooks:

• preOpen, postOpen: Called before and after the region is reported as online to the master.

• preFlush, postFlush: Called before and after the memstore is flushed into a new store file.
• preCompact, postCompact: Called before and after compaction.
• preSplit, postSplit: Called after the region is split.
• preClose and postClose: Called before and after the region is reported as closed to the master.

The RegionObserver interface is defines these hooks:

• preGet, postGet: Called before and after a client makes a Get request.
• preExists, postExists: Called before and after the client tests for existence using a Get.
• prePut and postPut: Called before and after the client stores a value.
• preDelete and postDelete: Called before and after the client deletes a value.
• preScannerOpen postScannerOpen: Called before and after the client opens a new scanner.
• preScannerNext, postScannerNext: Called before and after the client asks for the next row on a scanner.
• preScannerClose, postScannerClose: Called before and after the client closes a scanner.
• preCheckAndPut, postCheckAndPut: Called before and after the client calls checkAndPut().
• preCheckAndDelete, postCheckAndDelete: Called before and after the client calls checkAndDelete().

利用這些hooks可以實(shí)現(xiàn)region級(jí)二級(jí)索引，實(shí)現(xiàn)count, sum, avg, max, min等聚合操作而不需要返回所有的數(shù)據(jù)，詳見(jiàn) https://issues.apache.org/jira/browse/HBASE-1512 。

二級(jí)索引的原理猜測(cè)
因?yàn)閏oprocessor的最終方案還未公布，就提供的這些hooks來(lái)說(shuō)，二級(jí)索引的實(shí)現(xiàn)應(yīng)該是攔截同一個(gè)region的put, get, scan, delete等操作。與此同時(shí)在同一個(gè)reigon里維護(hù)一個(gè)索引CF，建立對(duì)應(yīng)的索引表。
基于region的索引表其實(shí)有很多局限性，比如全局排序就很難做。

不過(guò)我覺(jué)得Coprocessor最大的好處在于其提供了server端的完全擴(kuò)展能力，這對(duì)于Hbase來(lái)說(shuō)是一個(gè)大的躍進(jìn)。

如何join？

目前還未發(fā)布，不過(guò)就了解很難從本質(zhì)上有所突破。解決方案無(wú)非就是merge和composite index，同樣事務(wù)性是需要解決的難題之一。

業(yè)界已經(jīng)公開(kāi)的二級(jí)索引方案羅列：

0.19.3版Secondary Index

一直關(guān)注HBase的同學(xué)，或許知道，早在HBase 0.19.3版發(fā)布時(shí)，曾經(jīng)加入過(guò)secondary index的功能，Issue詳見(jiàn) 這里 。
它的使用例子也很簡(jiǎn)單： http://blog.rajeevsharma.in/2009/06/secondary-indexes-in-hbase.html

0.19.3版Secondary Index通過(guò)將列值以row key方法存儲(chǔ)，提供索引scan。
但HBase早期的需求主要來(lái)自Hadoop。事務(wù)的復(fù)雜性以及當(dāng)時(shí)發(fā)現(xiàn)hadoop-core里有個(gè)很難解決的與ITHBase兼容的問(wèn)題，致使官方在0.20.0版將其核心代碼移出了hbase-core，改為contrib第三方擴(kuò)展，Issue詳見(jiàn) 這里 。

Transactional tableindexed- ITHBase

這個(gè)方案就是在0.19.3版被官方剝離出核心的第三方擴(kuò)展，它的方案上面已經(jīng)介紹過(guò)了。目前支持最新的Hbase 0.90。
是否具備工業(yè)強(qiáng)度的穩(wěn)定性是用戶選擇它的主要障礙。

https://github.com/hbase-trx/hbase-transactional-tableindexed

Facebook方案

facebook采用的是單表多列索引的解決方案，上面已經(jīng)提到過(guò)了。很完美地解決了數(shù)據(jù)一致性問(wèn)題，這主要跟他們的使用場(chǎng)景有關(guān)。

感興趣的同學(xué)可以看下這篇blog，本文不作詳述：

blog.huihoo.com/?p=688

HBase官方方案 0.92.0 版開(kāi)發(fā)中 – Coprocessor協(xié)處理器

還未發(fā)布，不過(guò)hbase官方blog有篇介紹： http://hbaseblog.com/2010/11/30/hbase-coprocessors

Lily Hbase indexing Library

這是一個(gè)索引構(gòu)建，查詢，管理的框架。結(jié)構(gòu)上，就是通過(guò)一張indexmeta表管理多張indexdata索引表。
特點(diǎn)是，有一套非常完善的針對(duì)int, string, utf-8, decimal等類(lèi)型的row key排序機(jī)制。這個(gè)機(jī)制在這篇博文中有詳細(xì)介紹：

http://brunodumon.wordpress.com/2010/02/17/building-indexes-using-hbase-mapping-strings-numbers-and-dates-onto-bytes/

此外，框架針對(duì)join場(chǎng)景（原理=merge），提供了封裝好的conjunction和disjunction工具類(lèi)。
針對(duì)索引構(gòu)建場(chǎng)景，Hbase indexing library也提供了很方便的接口。

IHbase

歡迎訪問(wèn)我的 個(gè)人博客 ，獲取其他相關(guān)資料！