二級索引與索引Join是多數業務系統要求存儲引擎提供的基本特性，RDBMS早已支持，NOSQL陣營也在摸索著符合自身特點的最佳解決方案。
這篇文章會以HBase做為對象來討論如何基于Hbase構建二級索引與實現索引join。文末同時會列出目前已知的包括0.19.3版secondary index,ITHbase, Facebook方案和官方Coprocessor的介紹。
理論目標
在HBase中實現二級索引與索引Join需要考慮三個目標：
1，高性能的范圍檢索。
2，數據的低冗余（存儲所占的數據量）。
3，數據的一致性。
性能與數據冗余，一致性是相互制約的關系。
如果你實現了高性能地范圍檢索，必然需要靠冗余索引數據來提升性能，而數據冗余會導致更新數據時難以實現一致性，特別是分布式場景下。
如果你不要求高效地范圍檢索，那么可以不考慮產生冗余數據，一致性問題也可以間接避免，畢竟share nothing是公認的最簡單有效的解決方案。
理論結合實際，下文會以實例的方式來闡述各個方案是如何選擇偏重點。
這些方案是經過筆者資料查閱和同事的不斷交流后得出的結論，如有錯誤，歡迎指正：
1，按索引建表
每一個索引建立一個表，然后依靠表的row key來實現范圍檢索。row key在HBase中是以B+ tree結構化有序存儲的，所以scan起來會比較效率。
單表以row key存儲索引，column value存儲id值或其他數據 ，這就是Hbase索引表的結構。
如何Join？
多索引（多表）的join場景中，主要有兩種參考方案：
1，按索引的種類掃描各自獨立的單索引表，最后將掃描結果merge。
這個方案的特點是簡單，但是如果多個索引掃描結果數據量比較大的話，merge就會遇到瓶頸。
比如，現在有一張1億的用戶信息表，建有出生地和年齡兩個索引，我想得到一個條件是在杭州出生，年齡為20歲的按用戶id正序排列前10個的用戶列表。
有一種方案是，系統先掃描出生地為杭州的索引，得到一個用戶id結果集，這個集合的規模假設是10萬。
然后掃描年齡，規模是5萬，最后merge這些用戶id，去重，排序得到結果。
這明顯有問題，如何改良？
保證出生地和年齡的結果是排過序的，可以減少merge的數據量？但Hbase是按row key排序，value是不能排序的。
變通一下 – 將用戶id冗余到row key里？OK，這是一種解決方案了，這個方案的圖示如下：
merge時提取交集就是所需要的列表，順序是靠索引增加了_id，以字典序保證的。
2， 按索引查詢種類建立組合索引。
在方案1的場景中，想象一下，如果單索引數量多達10個會怎么樣？10個索引，就要merge 10次，性能可想而知。
解決這個問題需要參考RDBMS的組合索引實現。
比如出生地和年齡需要同時查詢，此時如果建立一個出生地和年齡的組合索引，查詢時效率會高出merge很多。
當然，這個索引也需要冗余用戶id，目的是讓結果自然有序。結構圖示如下：
這個方案的優點是查詢速度非常快，根據查詢條件，只需要到一張表中檢索即可得到結果list。缺點是如果有多個索引，就要建立多個與查詢條件一一對應的組合索引，存儲壓力會增大。
在制定Schema設計方案時，設計人員需要充分考慮場景的特點，結合方案一和二來使用。下面是一個簡單的對比：
| 單索引 | 組合索引 | |
| 檢索性能 | 優異 | 優異 |
| 存儲 | 數據不冗余，節省存儲。 | 數據冗余，存儲比較浪費。 |
| 事務性 | 多個索引保證事務性比較困難。 | 多個索引保證事務性比較困難。 |
| join | 性能較差 | 性能優異 |
| count,sum,avg,etc | 符合條件的結果集全表掃描 | 符合條件的結果集全表掃描 |
從上表中可以得知，方案1,2都存在更新時事務性保證比較困難的問題。如果業務系統可以接受最終一致性的話，事務性會稍微好做一些。否則只能借助于復雜的分布式事務，比如JTA，Chubby等技術。
count, sum, avg, max, min等聚合功能，Hbase只能通過硬掃的方式，并且很悲劇，你可能需要做一些hack操作（比如加一個CF,value為null），否則你在掃描時可能需要往客戶端傳回所有數據。
當然你可以在這個場景上做一些優化，比如增加狀態表等，但復雜性帶來的風險會更高。
還有一種終極解決方案就是在業務上只提供上一頁和下一頁，這或許是最簡單有效的方案了。
2，單張表多個列族，索引基于列
Hbase提供了列族Column Family特性。
列索引是將Column Family做為index，多個index值散落到Qualifier，多個column值依據version排列（CF, Qualifer, Version Hbase會保證有序，其中CF和Qualifier正序，Version倒序）。
舉個典型的例子，就是用戶賣了很多商品，這些商品的標題title需要支持like %title%查詢。傳統基于RDMBS就是模糊查詢，基于search engine就是分詞+倒排表。
在HBase中，模糊查詢顯然不滿足我們的要求，接下來只能通過分詞+倒排的方式來存儲。基于CF的倒排表索引結構見下圖：
取數據的時候，只需要根據用戶id（row key）定位到一個row，然后根據分詞定位到qualifier，再通過version的有序list，取top n條記錄即可。不過大家可能會發現個問題，version list的總數量是需要scan全version list才能知道的，這里需要業務系統本身做一些改進。
如何join？
實現方式同方案1里的join，多個CF列索引掃描結果后，需要走merge，將多個索引的查詢結果conjunction。
兩個方案的對比似乎變化就是一個表，一個列，但其實這個方案有個最大的好處，就是解決了事務性的問題，因為所有的索引都是跟單個row key綁定的，我們知道單個row的更新，在hbase中是保證原子更新的，這就是這個方案的天然優勢。當你在考慮單索引時，使用基于列的索引會比單表索引有更好的適用性。
而組合索引在以列為存儲粒度的方案里，也同樣可以折中實現。理解這種存儲模式的同學可能已經猜到了，就是基于qualifier。
下表對比了表索引和列索引的優缺點：
| 列索引 | 表索引 | |
| 檢索性能 | 檢索數據需要走多次scan，第一次scan row key，第二次scan qualifier，第三次scan version。 | 只需要走一次row key的scan即可。 |
| 存儲 | 在沒有組合索引時，存儲較節省 | 在沒有組合索引時，存儲較節省 |
| 事務性 | 容易保證 | 保證事務性比較困難 |
| join | 性能較差，只有在建立組合條件Qualifier的時候性能會有所改善 | 性能較差，只有在建立組合表索引的時候性能會有所改善 |
| 額外的問題 |
1，同一個row里每個qualifier的version是有大小限制的，不能超過Int的最大值。（別以為這個值很大，對于海量數據存儲，上億很平常）
2，version的count總數需要額外做處理獲取。 3，單個row數據超過split大小時，會導致不能compaction或compaction內存吃緊，增加風險。 |
|
| count,sum,avg,etc | 符合條件的結果集全表掃描 | 符合條件的結果集全表掃描 |
雖然列索引缺點這么多，但是存儲節省帶來的成本優勢有時還是值得我們去這么做的，何況它還解決了事務性問題，需要用戶自己去權衡。
值得一提的是，Facebook的消息應用服務器就是基于類似的方案來實現的。
3，ITHBase
方案一中的多表，解決了性能問題，同時帶來了存儲冗余和數據一致性問題。這兩個問題中，只要解決其中一項，其實也就滿足了大多數業務場景。
本方案中，著重關注的是數據一致性。ITHbase的全稱是 Indexed Transactional HBase，從名字中就能看出，事務性是它的重要特性。
ITHBase的事務原理簡介
建一張事務表__GLOBAL_TRX_LOG__，每次開啟事務時，在表中記錄狀態。因為是基于Hbase的HTable，事務表同樣會寫WAL用于恢復，不過這個日志格式被ITHbase改造過，它稱之為THLog。
客戶端對多張表更新時，先啟動事務，然后每次PUT，將事務id傳遞給HRegionServer。
ITHbase通過繼承HRegionServer和HReogin類，重寫了大多數操作接口方法，比如put, update, delete, 用于獲取transactionalId和狀態。
當server收到操作和事務id后，先確認服務端收到，標記當前事務為待寫入狀態（需要再發起一次PUT）。當所有表的操作完成后，由客戶端統一做commit寫入，做二階段提交。
4，Map-reduce
這個方案沒什么好說的，存儲節省，也不需要建索引表，只需要靠強大的集群計算能力即可導出結果。但一般不適合online業務。
5，Coprocessor協處理器
官方0.92.0新版正在開發中的新功能-
Coprocessor
，支持region級別索引。詳見:
https://issues.apache.org/jira/browse/HBASE-2038
協處理器的機制可以理解為，server端添加了一些回調函數。這些回調函數如下：
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可以實現region級二級索引，實現count, sum, avg, max, min等聚合操作而不需要返回所有的數據，詳見 https://issues.apache.org/jira/browse/HBASE-1512 。
二級索引的原理猜測
因為coprocessor的最終方案還未公布，就提供的這些hooks來說，二級索引的實現應該是攔截同一個region的put, get, scan, delete等操作。與此同時在同一個reigon里維護一個索引CF，建立對應的索引表。
基于region的索引表其實有很多局限性，比如全局排序就很難做。
不過我覺得Coprocessor最大的好處在于其提供了server端的完全擴展能力，這對于Hbase來說是一個大的躍進。
如何join？
目前還未發布，不過就了解很難從本質上有所突破。解決方案無非就是merge和composite index，同樣事務性是需要解決的難題之一。
業界已經公開的二級索引方案羅列：
0.19.3版Secondary Index
一直關注HBase的同學，或許知道，早在HBase 0.19.3版發布時，曾經加入過secondary index的功能，Issue詳見
這里
。
它的使用例子也很簡單：
http://blog.rajeevsharma.in/2009/06/secondary-indexes-in-hbase.html
0.19.3版Secondary Index通過將列值以row key方法存儲，提供索引scan。
但HBase早期的需求主要來自Hadoop。事務的復雜性以及當時發現hadoop-core里有個很難解決的與ITHBase兼容的問題，致使官方在0.20.0版將其核心代碼移出了hbase-core，改為contrib第三方擴展，Issue詳見
這里
。
Transactional tableindexed- ITHBase
這個方案就是在0.19.3版被官方剝離出核心的第三方擴展，它的方案上面已經介紹過了。目前支持最新的Hbase 0.90。
是否具備工業強度的穩定性是用戶選擇它的主要障礙。
https://github.com/hbase-trx/hbase-transactional-tableindexed
Facebook方案
facebook采用的是單表多列索引的解決方案，上面已經提到過了。很完美地解決了數據一致性問題，這主要跟他們的使用場景有關。
感興趣的同學可以看下這篇blog，本文不作詳述：
HBase官方方案 0.92.0 版開發中 – Coprocessor協處理器
還未發布，不過hbase官方blog有篇介紹： http://hbaseblog.com/2010/11/30/hbase-coprocessors
Lily Hbase indexing Library
這是一個索引構建，查詢，管理的框架。結構上，就是通過一張indexmeta表管理多張indexdata索引表。
特點是，有一套非常完善的針對int, string, utf-8, decimal等類型的row key排序機制。這個機制在這篇博文中有詳細介紹：
此外，框架針對join場景（原理=merge），提供了封裝好的conjunction和disjunction工具類。
針對索引構建場景，Hbase indexing library也提供了很方便的接口。
IHbase
| global ordering | yes | no | IHBase has an index for each region. The flip side of not having global ordering is compatibility with the good old HRegion: results are coming back in row order (and not value order as in ITHBase) |
| Full table scan? | no | no | THbase does a partial scan on the index table. ITHBase supports specifying start/end rows to limit the number of scanned regions |
| Multiple Index Usage | no | yes | IHBase can take advantage of multiple indexes in the same scan. IHBase IdxScan object accepts an Expression which allows intersection/unison of several indexed column criteria |
| Extra disk storage | yes | no | IHBase indexes are created when the region starts/flushes and do not require any extra storage |
| Extra RAM | yes | yes | IHBase indexes are in memory and hence increase the memory overhead. THBbase indexes increase the number of regions each region server has to support thus costing memory too |
| Parallel scanning support | no | yes | In ITHBase the index table needs to be consulted and then GETs are issued for each matching row. The behavior of IHBase (as perceived by the client) is no different than a regular scan and hence supports parallel scanning seamlessly. parallel GET can be implemented to speedup THbase scans |
scan的時候，IHBase會結合索引列中的標記，來加速scan。
歡迎訪問我的 個人博客 ，獲取其他相關資料！
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
