HBase高性能復雜條件查詢引擎

Patagonia

　　




寫在前面

在這次的審稿過程中有幸得到了Ted Yu和梁堰波先生的反饋，大家就一些感興趣的內(nèi)容進行了討論。該方案由一個智能交通解決方案演變而來，設計之初僅寄希望于通過二級索引提升查詢性能，由于在前期架構時充分考慮了通用性以及對復雜條件的支持，在后來的演變中逐漸被剝離出來形成了一個通用的查詢引擎。Ted Yu對“查詢決策器”表示了關心，他指出類似的組件同時也是Phoenix, Impala用于支持SQL查詢的核心組件，但是這類組件很難引入到HBase中，因為HBase專注于byte[]的操作。對此，方案在設計時避開了“SQL解析”和“在各種數(shù)據(jù)類型與byte[]之間進行轉化”的棘手問題，而是使用了一組可以描述查詢的Query API，這與Hibernate中提供Criteria接口的做法非常相似，在Hibernate中既支持HQL語句的查詢又支持使用Criteria接口以編程方式描述的查詢，對于我們來說選擇類似后者的做法實現(xiàn)起來要快速和容易的多，而查詢條件中的值在構造之初就以byte[]的形式傳遞，避免了決策器解析時的類型判定和轉化問題。
題記
——索引的實質是另一種編排形式的數(shù)據(jù)冗余，高效的檢索源自于面向查詢特別設計的編排形式，如果再輔以分布式的計算框架，就可以支撐起高性能的大數(shù)據(jù)查詢。

正文
Apache HBase™是一個分布式、可伸縮的NoSQL數(shù)據(jù)庫，它構建在Hadoop基礎設施之上，依托于Hadoop的迅猛發(fā)展，HBase在大數(shù)據(jù)領域的應用越來越廣泛，成為目前NoSQL數(shù)據(jù)庫中表現(xiàn)最耀眼，呼聲最高的產(chǎn)品之一。像其他NoSQL數(shù)據(jù)庫一樣，HBase也有其適用范圍，就應對復雜條件的查詢來說，一般認為它并不是非常適合，熟悉HBase的開發(fā)人員對此應該有一定的體會，但是基于普遍的需求，開發(fā)者們希望HBase在保持高性能優(yōu)勢的同時能對復雜條件的查詢給予一定的支持，而本文將要介紹的正是一種在HBase現(xiàn)行機制下以非侵入式實現(xiàn)的基于二級多列索引的高性能復雜條件查詢引擎。


問題
目前HBase主要應用在結構化和半結構化的大數(shù)據(jù)存儲上，其在插入和讀取上都具有極高的性能表現(xiàn)，這與它的數(shù)據(jù)組織方式有著密切的關系，在邏輯上，HBase的表數(shù)據(jù)按RowKey進行字典排序， RowKey實際上是數(shù)據(jù)表的一級索引（Primary Index），由于HBase本身沒有二級索引（Secondary Index）機制，基于索引檢索數(shù)據(jù)只能單純地依靠RowKey，為了能支持多條件查詢，開發(fā)者需要將所有可能作為查詢條件的字段一一拼接到RowKey中，這是HBase開發(fā)中極為常見的做法，但是無論怎樣設計，單一RowKey固有的局限性決定了它不可能有效地支持多條件查詢。通常來說，RowKey只能針對條件中含有其首字段的查詢給予令人滿意的性能支持，在查詢其他字段時，表現(xiàn)就差強人意了，在極端情況下某些字段的查詢性能可能會退化為全表掃描的水平，這是因為字段在RowKey中的地位是不等價的，它們在RowKey中的排位決定了它們被檢索時的性能表現(xiàn)，排序越靠前的字段在查詢中越具有優(yōu)勢，特別是首位字段具有特別的先發(fā)優(yōu)勢，如果查詢中包含首位字段，檢索時就可以通過首位字段的值確定RowKey的前綴部分，從而大幅度地收窄檢索區(qū)間，如果不包含則只能在全體數(shù)據(jù)的RowKey上逐一查找，由此可以想見兩者在性能上的差距。

受限于單一RowKey在復雜查詢上的局限性，基于二級索引（Secondary Index）的解決方案成為最受關注的研究方向，并且開源社區(qū)已經(jīng)在這方面已經(jīng)取得了一定的成果，像ITHBase、IHBase以及華為的hindex項目，這些產(chǎn)品和框架都按照自己的方式實現(xiàn)了二級索引，各自具有不同的優(yōu)勢，同時也都有一定局限性，本文闡述的方案借鑒了它們的一些優(yōu)點，在確保非侵入的前提下，以高性能為首要目標，通過建立二級多列索引實現(xiàn)了對復雜條件查詢的支持，同時通過提供通用的查詢API，以及完全基于配置的索引結構，完全封裝了索引的創(chuàng)建和使用細節(jié)，使之成為一種通用的查詢引擎。

原理
“二級多列索引”是針對目標記錄的某個或某些列建立的“鍵-值”數(shù)據(jù)，以列的值為鍵，以記錄的RowKey為值，當以這些列為條件進行查詢時，引擎可以通過檢索相應的“鍵-值”數(shù)據(jù)快速找到目標記錄。由于HBase本身并沒有索引機制，為了確保非侵入性，引擎將索引視為普通數(shù)據(jù)存放在數(shù)據(jù)表中，所以，如何解決索引與主數(shù)據(jù)的劃分存儲是引擎第一個需要處理的問題，為了能獲得最佳的性能表現(xiàn)，我們并沒有將主數(shù)據(jù)和索引分表儲存，而是將它們存放在了同一張表里，通過給索引和主數(shù)據(jù)的RowKey添加特別設計的Hash前綴，實現(xiàn)了在Region切分時，索引能夠跟隨其主數(shù)據(jù)劃歸到同一Region上，即任意Region上的主數(shù)據(jù)其索引也必定駐留在同一Region上，這樣我們就能把從索引抓取目標主數(shù)據(jù)的性能損失降低到最小。與此同時，特別設計的Hash前綴還在邏輯上把索引與主數(shù)據(jù)進行了自動的分離，當全體數(shù)據(jù)按RowKey排序時，排在前面的都是索引，我們稱之為索引區(qū)，排在后面的均為主數(shù)據(jù)，我們稱之為主數(shù)據(jù)區(qū)。最后，通過給索引和主數(shù)據(jù)分配不同的Column Family，又在物理存儲上把它們隔離了起來。邏輯和物理上的雙重隔離避免了將兩類數(shù)據(jù)存放在同一張表里帶來的副作用，防止了它們之間的相互干擾，降低了數(shù)據(jù)維護的復雜性，可以說這是在性能和可維護性上達到的最佳平衡。


圖1：Sample表Region 1的數(shù)據(jù)邏輯視圖

讓我們通過一個示例來詳細了解一下二級多列索引表的結構，假定有一張Sample表，使用四位數(shù)字構成Hash前綴[ii]，范圍從0000到9999，規(guī)劃切分100個Region，則100個Region的RowKey區(qū)間分別為[0000,0099]，[0100,0199]，……，[9900,9999]，以第一個Region為例，請看圖1，所有數(shù)據(jù)按RowKey進行字典排序，自動分成了索引區(qū)和主數(shù)據(jù)區(qū)兩段，主數(shù)據(jù)區(qū)的Column Family是d，下轄q1,q2,q3等Qualifier，為了簡單起見，我們假定q1,q2,q3的值都是由兩位數(shù)字組成的字符串，索引區(qū)的Column Family是i，它不含任何Qualifier，這是一個典型的“Dummy Column Family“，作為區(qū)別于d的另一個Column Family，它的作用就是讓索引獨立于主數(shù)據(jù)單獨存儲。接下來是最重要的部分，即索引和主數(shù)據(jù)的RowKey，我們先看主數(shù)據(jù)的RowKey，它由四位Hash前綴和原始ID兩部分組成，其中Hash前綴是由引擎分配的一個范圍在0000到9999之間的隨機值，通過這個隨機的Hash前綴可以讓主數(shù)據(jù)均勻地散列到所有的Region上，我們看圖1，因為Region 1的RowKey區(qū)間是[0000,0099]，所以沒有任何例外，凡是且必須是前綴從0000到0099的主數(shù)據(jù)都被分配到了Region 1上。接下來看索引的RowKey，它的結構要相對復雜一些，格式為：RegionStartKey-索引名-索引鍵-索引值，與主數(shù)據(jù)不同，索引RowKey的前綴部分雖然也是由四位數(shù)字組成，但卻不是隨機分配的，而是固定為當前Region的StartKey，這是非常重要而巧妙的設計，一方面，這個值處在Region的RowKey區(qū)間之內(nèi)，它確保了索引必定跟隨其主數(shù)據(jù)被劃分到同一個Region里；另一方面，這個值是RowKey區(qū)間內(nèi)的最小值，這保證了在同一Region里所有索引會集中排在主數(shù)據(jù)之前。接下來的部分是“索引名”，這是引擎給每類索引添加的一個標識，用于區(qū)分不同類型的索引，圖1中展示了兩種索引：a和b，索引a是為字段q1和q2設計的兩列聯(lián)合索引，索引b是為字段q2和q3設計的兩列聯(lián)合索引，依次類推，我們可以根據(jù)需要設計任意多列的聯(lián)合索引。再接下來就是索引的鍵和值了，索引鍵是由目標記錄各對應字段的值組成，而索引值就是這條記錄的RowKey。

現(xiàn)在，假定需要查詢滿足條件q1=01 and q2=02的Sample記錄，分析查詢字段和索引匹配情況可知應使用索引a，也就是說我們首先確定了索引名，于是在Region 1上進行scan的區(qū)間將從主數(shù)據(jù)全集收窄至[0000-a, 0000-b)，接著拼接查詢字段的值，我們得到了索引鍵：0102，scan區(qū)間又進一步收窄為[0000-a-0102, 0000-a-0103)，于是我們可以很快地找到0000-a-0102-0000|63af51b2這條索引，進而得到了索引值，也就是目標數(shù)據(jù)的RowKey：0000|63af51b2，通過在Region內(nèi)執(zhí)行Get操作，最終得到了目標數(shù)據(jù)。需要特別說明的是這個Get操作是在本Region上執(zhí)行的，這和通過HTable發(fā)出的Get有很大的不同，它專門用于獲取Region的本地數(shù)據(jù)，其執(zhí)行效率是非常高的，這也是為什么我們一定要將索引和它的主數(shù)據(jù)放在同一張表的同一個Region上的原因。

架構
在了解了引擎的工作原理之后來我們來看一下它的整體架構：

圖2：引擎的整體架構
引擎構建在HBase的Coprocessor機制之上，由Client端和Server端兩部分構成，對于查詢而言，查詢請求從Client端經(jīng)由HTable的coprocessorExec方法推送到所有的RegionServer上，RegionServer接收到查詢請求后使用“查詢決策器”分析查詢條件，比對索引元數(shù)據(jù)，在找到適合該查詢的最優(yōu)索引后，解析索引區(qū)間，然后委托“索引查詢器”基于給定的最優(yōu)索引和解析區(qū)間進行數(shù)據(jù)檢索，如果沒有找到合適的索引則委托“全表查詢器”進行全表掃描。當各RegionServer的局部查詢結果返回之后，引擎的Client端還負責對它們并進行合并匯總和排序，從而得到最終的結果集。對于插入而言，當主數(shù)據(jù)試圖寫入時會被Coprocessor攔截，委托“索引構造器”根據(jù)“索引配置文件”創(chuàng)建指向當前主數(shù)據(jù)的所有索引，然后一同插入到數(shù)據(jù)表中。

讓我們來深入了解一下引擎的幾個核心組件。對于引擎的客戶端來講，最重要的組件是一套用于表達復雜查詢請求的Query API，在這套API的設計上我們借鑒了IHBase的一些做法，通過對查詢條件（Condition）進行抽象和建模，得到一套典型的基于“復合模式”（Composite Pattern）的Class Hierarchy，使之能夠優(yōu)雅地表達基于AND和OR的多重復合條件。以圖1所示的Sample表為例，使用Query API構造一個查詢條件為“(q1=01 and q204)”的Java代碼如下：

圖3：引擎客戶端的Query API示意代碼
查詢請求到達Server端以后，由Coprocessor委派查詢決策器進行分析以確定使用何種查詢策略應對，這是查詢處理流程上的一個關鍵結點。查詢決策器需要分析查詢請求的各項細節(jié)，包括條件字段、排序字段和排序，然后和索引的元數(shù)據(jù)進行比對找出性能最優(yōu)的索引，有時候對于一個查詢請求可能會有多個適用索引，但是查詢性能卻有高下之分，因此需要對每一個候選索引進行性能評估，找出最優(yōu)者，性能評估的方法是看哪個索引能最大限度地收窄檢索區(qū)間。索引的元數(shù)據(jù)來自于索引配置文件，圖4展示了一份簡單的索引配置，配置中描述的正是圖1中使用的索引a和b的元數(shù)據(jù)，索引元數(shù)據(jù)主要是由索引名和一組field組成，filed描述的是索引針對的目標列（ColumnFamily:Qualifier）。實際的索引配置通常比我們看到的這份要復雜，因為在生成索引時有很多細節(jié)需要通過索引配置給出指引，比如如何處理不定長字段，目標列使用正序還是倒序（例如時間數(shù)據(jù)在HBase中經(jīng)常需要按補值進行倒序處理），是否需要使用自定義格式化器對目標列的值進行格式化等等,完全配置化的索引元數(shù)據(jù)使創(chuàng)建和維護索引的成本大大降低，為上層應用根據(jù)實際需求靈活設計索引提供了保障。

圖4：一份簡單的索引配置文件
在確定最優(yōu)索引之后，查詢決策器開始基于最優(yōu)索引對查詢條件進行解析，解析的結果是一組索引區(qū)間，區(qū)間內(nèi)的數(shù)據(jù)未必都滿足查詢條件，但卻是通過計算所能得到的最小區(qū)間，索引查詢器就在這些區(qū)間上進行檢索，通過配備的專用Filter對區(qū)間內(nèi)的每一條數(shù)據(jù)進行最后的匹配判斷。圖5展示了一個條件為q1=01 and 01應用
由于引擎設計之初就以非侵入性為前提，所以引擎的部署與集成就與引入第三方類庫無異，唯一需要上層應用提供的是面向數(shù)據(jù)表的索引配置文件。設計索引主要以業(yè)務需求為導向，先分析并梳理出常用的查詢用例，然后針對查詢用例所涉及的字段和排序要求按相似性進行分組，盡可能讓單個索引同時支持多種相近的查詢，減少索引的種類和數(shù)量，提升索引復用率。在這方面如下設計原則可供參考（注：以下原則均以“不考慮排序”為前提）：

• 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開頭向后循環(huán)取足三個字段，得到：ABC、BCD（它將同時支持BCD、BC和B三種查詢）、CDA（它將同時支持CDA、CD和C三種查詢）和DAB（它將同時支持DAB、DA和D三種查詢），其中ABC是ABCD的前綴，故舍棄。按照同樣的方法，兩字段索引要分別從保留下來的三個三字段索引中依次以每一個字段開頭取足兩個字段，然后去除重復和前綴重疊的索引，最終得到DB（它將同時支持DB和D兩種查詢）和AC（它將同時支持AC和A兩種查詢），總計是6個索引，最后可以再根據(jù)實際需求剪裁掉不需要的索引。

在上述原則的表述中特別注明了“不考慮排序“這個前提，對于索引來說，”排序“是一個很“敏感”的要求，索引本身只有一種排序（即按索引首字段進行的字典排序），如果查詢請求的排序與索引排序不同，則索引直接出局，即使它們的字段完全匹配，也就是說排序會極大地消弱索引的復用度，對于我們的引擎來說，排序字段應該受到嚴格的控制。實際上，很多大數(shù)據(jù)系統(tǒng)都需要對排序進行限制，比如淘寶上的商品檢索，可供排序的字段只有人氣，銷量，信用和價格，因為排序需要針對數(shù)據(jù)全集進行計算，如果不是針對有限的排序字段建立索引或是離線計算并緩存結果，按任意字段排序的查詢是很難在線返回的。

小結
綜合前文所述，方案主要有如下幾個顯著的優(yōu)勢：

   高性能：引擎的高性能源自兩方面，一是二級多列索引，二是基于Coprocessor的并行計算

   非侵入性：引擎構建在HBase之上，既沒有對HBase進行任何改動，也不需要上層應用做任何妥協(xié)

   高度可配置：索引元數(shù)據(jù)是完全基于配置的，可以輕便靈活地創(chuàng)建和維護索引

   通用性：引擎的前端查詢接口和后端索引處理都是基于通用目標設計的，不依賴于任何具體表

限于HBase自身的特點，方案本身也有一定的局限性，一是它不能隨意地支持任意的條件查詢，這一點前文已經(jīng)給出了分析和建議，二是在插入主數(shù)據(jù)時需要伴隨插入多份索引從而對寫入性能產(chǎn)生了一定的影響，如何控制寫入和查詢的競爭關系需要根據(jù)系統(tǒng)的讀寫比進行權衡，對于數(shù)據(jù)寫入實時性要求不高或者數(shù)據(jù)是離線導入的系統(tǒng)來說，可以考慮使用批量導入工具，特別是以直接生成HFile的方式導入的話可以在很大程度上消除引入索引后的寫入壓力。

[1] 理論上基于HBase的 Filter機制可以實現(xiàn)任意復雜條件的查詢，但是那樣做就徹底放棄了RowKey作為索引的利用價值，大多數(shù)查詢的性能都將變得非常差。

[2] Hash前綴的長度和Region數(shù)量有著密切的關系，由于索引和主數(shù)據(jù)的分配高度依賴RowKey前綴和Region的RowKey區(qū)間，引擎嚴禁Region進行自動切分，開發(fā)人員需要在前期對Region數(shù)量和前綴長度進行規(guī)劃，本例中取四位前綴意味著最多可以支持10000個Region。

關于作者

耿立超，架構師，目前正從事大數(shù)據(jù)領域的研發(fā)工作，對企業(yè)級應用架構、SaaS、分布式存儲和領域驅動設計有豐富的實踐經(jīng)驗，喜歡攝影和旅行。

來源:InfoQ

本文來自ChinaUnix新聞頻道，如果查看原文請點：http://news.chinaunix.net/opensource/2014/0723/3187491.shtml