HBase高性能復(fù)雜條件查詢引擎

Patagonia

　　




寫在前面

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

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


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

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

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


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

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

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

架構(gòu)
在了解了引擎的工作原理之后來(lái)我們來(lái)看一下它的整體架構(gòu)：

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

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

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

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

• N個(gè)字段組合的查詢只需要建立一個(gè)包含該N個(gè)字段的索引，建立按這個(gè)N字段其他順序排列的索引是沒(méi)有意義的。因此，以N個(gè)字段組合為條件的查詢只需要C(n, n)=1個(gè)索引。
• 一個(gè)包含N個(gè)字段的索引同時(shí)是以從第1到第N-1個(gè)字段為條件的查詢索引，以及從第1到第N-2個(gè)字段為條件的查詢索引，依此類推，也是僅以第1個(gè)字段為條件的查詢索引。因此，包含N個(gè)字段的索引總計(jì)可以支持C(n,1)=n種查詢組合。
• 基于上述兩點(diǎn)，任意一個(gè)索引的字段組合不應(yīng)該是另一個(gè)索引字段組合的前綴部分，這樣設(shè)計(jì)的索引才會(huì)有較高的復(fù)用率。
  

假如某表有A、B、C、D四個(gè)字段，在不考慮排序的前提下，如果要用索引支持以任意字段或字段組合為條件的查詢，則索引的設(shè)計(jì)方法如下：四字段索引只需要一個(gè)，假定取ABCD（它將同時(shí)支持ABCD、ABC、AB和A四種查詢）。三字段索引分別以A、B、C、D開(kāi)頭向后循環(huán)取足三個(gè)字段，得到：ABC、BCD（它將同時(shí)支持BCD、BC和B三種查詢）、CDA（它將同時(shí)支持CDA、CD和C三種查詢）和DAB（它將同時(shí)支持DAB、DA和D三種查詢），其中ABC是ABCD的前綴，故舍棄。按照同樣的方法，兩字段索引要分別從保留下來(lái)的三個(gè)三字段索引中依次以每一個(gè)字段開(kāi)頭取足兩個(gè)字段，然后去除重復(fù)和前綴重疊的索引，最終得到DB（它將同時(shí)支持DB和D兩種查詢）和AC（它將同時(shí)支持AC和A兩種查詢），總計(jì)是6個(gè)索引，最后可以再根據(jù)實(shí)際需求剪裁掉不需要的索引。

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

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

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

   非侵入性：引擎構(gòu)建在HBase之上，既沒(méi)有對(duì)HBase進(jìn)行任何改動(dòng)，也不需要上層應(yīng)用做任何妥協(xié)

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

   通用性：引擎的前端查詢接口和后端索引處理都是基于通用目標(biāo)設(shè)計(jì)的，不依賴于任何具體表

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

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

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

關(guān)于作者

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

來(lái)源:InfoQ

本文來(lái)自ChinaUnix新聞?lì)l道，如果查看原文請(qǐng)點(diǎn)：http://news.chinaunix.net/opensource/2014/0723/3187491.shtml