基于日志結(jié)構(gòu)合并樹的輕量級(jí)分布式索引實(shí)現(xiàn)方法

（哈爾濱工業(yè)大學(xué)計(jì)算學(xué)部，哈爾濱 150001）

0 引言

如今，隨著移動(dòng)互聯(lián)網(wǎng)等技術(shù)的普及，數(shù)據(jù)量呈爆炸式增長(zhǎng)。大規(guī)模數(shù)據(jù)對(duì)數(shù)據(jù)管理提出了迫切的需求，傳統(tǒng)的數(shù)據(jù)庫(kù)對(duì)于超大規(guī)模數(shù)據(jù)存取的效率低，難以支持高并發(fā)訪問(wèn)。為此，分布式數(shù)據(jù)庫(kù)應(yīng)運(yùn)而生。但是這類數(shù)據(jù)庫(kù)也存在著對(duì)數(shù)據(jù)查詢?cè)L問(wèn)不夠靈活的缺點(diǎn)。分布式數(shù)據(jù)庫(kù)系統(tǒng)通常根據(jù)主鍵按照一定規(guī)則將數(shù)據(jù)進(jìn)行劃分，將數(shù)據(jù)片段冗余地存儲(chǔ)在集群中的計(jì)算節(jié)點(diǎn)上，同時(shí)在主鍵上構(gòu)建索引，來(lái)支持高效的主鍵查詢。而針對(duì)非主鍵屬性列的查詢，系統(tǒng)無(wú)法確定數(shù)據(jù)的分片信息具體存儲(chǔ)在哪個(gè)計(jì)算節(jié)點(diǎn)上，只能通過(guò)全表掃描進(jìn)行查詢，效率較低。所以，如何提升非主鍵查詢效率成為分布式數(shù)據(jù)庫(kù)系統(tǒng)的亟須解決的問(wèn)題。

現(xiàn)有的分布式索引方案都擁有各自獨(dú)特的構(gòu)建方式，大致可以分為三種類型：一是通過(guò)改造系統(tǒng)的源碼，重新設(shè)計(jì)交互邏輯，實(shí)現(xiàn)二級(jí)索引（SecondaryIndex，https：//github.com/Huawei-Hadoop/hindex）。這種方法對(duì)開發(fā)人員的要求很高，并且很難跟得上系統(tǒng)版本更新的速度，用戶在使用時(shí)需要將自己的數(shù)據(jù)重新導(dǎo)入到索引系統(tǒng)中，用戶體驗(yàn)性差；第二種是基于MapReduce 并行計(jì)算框架，為查詢數(shù)據(jù)創(chuàng)建map 映射表，并在客戶端實(shí)現(xiàn)對(duì)map 映射表的查詢［1］。由于NoSQL 數(shù)據(jù)庫(kù)在進(jìn)行跨行的事務(wù)時(shí)，無(wú)法保證原子性，當(dāng)系統(tǒng)寫入數(shù)據(jù)后，索引尚未更新成功前，系統(tǒng)發(fā)生任何錯(cuò)誤，都會(huì)造成索引和原始數(shù)據(jù)不一致的后果。但是現(xiàn)有的MapReduce方案沒(méi)有考慮數(shù)據(jù)的更新情況，所以這種方案只能適用到一些離線應(yīng)用中；第三種方案是預(yù)設(shè)好索引的結(jié)構(gòu)，將索引表和數(shù)據(jù)表同時(shí)創(chuàng)建［2］。由于后續(xù)無(wú)法添加索引，所以初始索引要對(duì)所有的非主鍵列建索引，這樣就會(huì)造成極大的空間開銷，使用起來(lái)很不靈活。

綜上，現(xiàn)有的方案無(wú)法同時(shí)滿足這三點(diǎn)要求：針對(duì)已有的海量數(shù)據(jù)高效地創(chuàng)建索引；用戶可以將方案快速地應(yīng)用在自己的集群中；兼顧磁盤中基線數(shù)據(jù)索引構(gòu)建和內(nèi)存中隨時(shí)發(fā)生的增量數(shù)據(jù)更新。

針對(duì)上述問(wèn)題，提出一種基于LSM-Tree（Log Structured Merge-Tree）的輕量級(jí)分布式索引實(shí)現(xiàn)方法SIBL（Secondary Index Based LSM-Tree），將MapReduce 并行計(jì)算框架和LSMTree思想相結(jié)合，對(duì)非主鍵屬性列建立索引，把復(fù)雜的非主鍵查詢問(wèn)題轉(zhuǎn)化為主鍵查詢問(wèn)題。從而提高非主鍵屬性的查詢效率。

首先，LSM-Tree是非常優(yōu)秀的數(shù)據(jù)檢索引擎，由一個(gè)駐存在內(nèi)存中的樹結(jié)構(gòu)和多個(gè)位于磁盤上的樹結(jié)構(gòu)組成。分布式數(shù)據(jù)庫(kù)采用這種分層的思想，將數(shù)據(jù)分成兩部分來(lái)存儲(chǔ)，內(nèi)存中的數(shù)據(jù)memStore 相當(dāng)于LSM-Tree 中的C0Tree，磁盤中的數(shù)據(jù)StoreFile 相當(dāng)于LSM-Tree 中的C1Tree 和C2Tree，當(dāng)內(nèi)存中的數(shù)據(jù)量到達(dá)閾值后順序?qū)懭氪疟P，數(shù)據(jù)更新只發(fā)生在內(nèi)存中；磁盤中的數(shù)據(jù)會(huì)定期地整合，避免不必要的I/O，可見基于LSM-Tree 的索引方法可以極大提高系統(tǒng)的寫入性能，同時(shí)讓索引更高效。

圖1 LSM-Tree與Store結(jié)構(gòu)對(duì)應(yīng)圖Fig.1 Structure correspondence between LSM-Tree and Store

SIBL 采用MapReduce 框架的并行計(jì)算快速地對(duì)數(shù)據(jù)進(jìn)行批量構(gòu)建。通過(guò)調(diào)用系統(tǒng)接口，創(chuàng)建索引表，將原數(shù)據(jù)表的非主鍵列映射到索引表的主鍵，查詢頻率較高的列附加在索引表的value 中，同時(shí)提供單列索引和聯(lián)合索引兩種構(gòu)建方式。用戶還可以根據(jù)需求自由選擇索引構(gòu)建方案：對(duì)已有數(shù)據(jù)構(gòu)建索引或者將索引和原數(shù)據(jù)表同時(shí)構(gòu)建。

本文的主要貢獻(xiàn)如下：

1）設(shè)計(jì)了通用的SIBL 索引結(jié)構(gòu)，及分布式索引構(gòu)建算法，在不侵入分布式系統(tǒng)源碼的前提下實(shí)現(xiàn)輕量級(jí)索引方案，滿足用戶既可以在生成用戶表的階段同時(shí)創(chuàng)建索引，又可以對(duì)現(xiàn)有用戶表構(gòu)建索引的需求。

2）針對(duì)分布式索引區(qū)間的劃分，提出基于等距取樣的索引區(qū)間劃分算法，實(shí)現(xiàn)索引的均勻分布；優(yōu)化了索引的查詢算法，避免回表查詢，支持多個(gè)非主鍵屬性列聯(lián)合查詢，提高查詢效率。

3）在HBase數(shù)據(jù)庫(kù)上與華為HIndex方案進(jìn)行多組對(duì)比實(shí)驗(yàn)，結(jié)合實(shí)驗(yàn)數(shù)據(jù)，驗(yàn)證了本文所有算法的有效性和正確性。

1 相關(guān)工作

為了使分布式數(shù)據(jù)庫(kù)支持更豐富的查詢功能，提高數(shù)據(jù)庫(kù)存儲(chǔ)數(shù)據(jù)的查詢效率，國(guó)內(nèi)外對(duì)分布式數(shù)據(jù)庫(kù)的索引技術(shù)開展了大量的研究。目前，絕大多數(shù)分布式數(shù)據(jù)庫(kù)是采用key-value 存儲(chǔ)模型來(lái)存儲(chǔ)數(shù)據(jù)，所以典型的分布式索引方式是以主鍵索引為主，常見的有Hash 索引、B+樹索引［3］等，為了提供更豐富的查詢能力，一些數(shù)據(jù)庫(kù)建有二級(jí)索引。

HIndex方案是2012年華為公司在HBTC2012上公布的二級(jí)索引方案。整套方案基于HBase-0.94.8 系統(tǒng)實(shí)現(xiàn)，對(duì)HBase 系統(tǒng)的源碼進(jìn)行改進(jìn)。由于版本的限制，用戶很難將HIndex 方案整合到自己的集群中，并且，HIndex 是在系統(tǒng)創(chuàng)建用戶表的同時(shí)創(chuàng)建索引表，故不支持動(dòng)態(tài)的添加或刪除索引，用戶無(wú)法為已經(jīng)存在的數(shù)據(jù)表創(chuàng)建索引。同時(shí)，為了確保索引和數(shù)據(jù)能夠始終存儲(chǔ)在同一個(gè)節(jié)點(diǎn)上，HIndex 禁止了局部索引文件的操作，因此，HIndex無(wú)法滿足整個(gè)系統(tǒng)的負(fù)載均衡策略，并且沒(méi)有良好的可擴(kuò)展性，而這些特性正是分布式系統(tǒng)所必須擁有的。在查詢數(shù)據(jù)時(shí)，系統(tǒng)需要訪問(wèn)所有的Region，耗費(fèi)資源，嚴(yán)重降低系統(tǒng)的查詢性能，而這正是本文在研究中考慮到的問(wèn)題。

分片位圖索引方案［4］利用局部索引來(lái)簡(jiǎn)化索引的維護(hù)，提高查詢效率。實(shí)現(xiàn)方式是將過(guò)濾條件生成為條件位圖，與所有計(jì)算節(jié)點(diǎn)維護(hù)的局部位圖進(jìn)行位運(yùn)算，但由于查詢時(shí)需要訪問(wèn)所有節(jié)點(diǎn)，也會(huì)造成了一定的資源浪費(fèi)。用戶在使用時(shí)需要為局部索引生成局部位圖，大大增加了任務(wù)量。

CCIndex［5］是由中科院科研團(tuán)隊(duì)提出的全局索引方案。該方案將需要查詢的數(shù)據(jù)的詳細(xì)信息一同存入全局索引中，從而實(shí)現(xiàn)基于非主鍵屬性列多維度范圍查詢索引。主要思想是設(shè)置數(shù)據(jù)的多個(gè)副本，根據(jù)每個(gè)副本上的不同非主鍵列建立聚簇索引，并將大量非主鍵查詢中的隨機(jī)讀取轉(zhuǎn)換為基于索引的順序掃描，優(yōu)勢(shì)是可以極大提高數(shù)據(jù)的查詢效率，缺點(diǎn)是多個(gè)副本的數(shù)據(jù)存儲(chǔ)會(huì)造成很大的空間開銷。

Diff-Index［6］是一種全局索引方案，致力于解決索引與數(shù)據(jù)一致性問(wèn)題。作者認(rèn)為在不同應(yīng)用中對(duì)索引和數(shù)據(jù)的一致性的要求也不盡相同，應(yīng)該允許索引和數(shù)據(jù)異步更新的情況存在。針對(duì)不同的一致性需求，Diff-Index 在HBase 上實(shí)現(xiàn)了不同級(jí)別的索引一致性維護(hù)方法。該方案忽略了對(duì)提升非主鍵屬性列的查詢性能的研究。

王文賢等［1］針對(duì)海量矢量空間數(shù)據(jù)的存儲(chǔ)和查詢問(wèn)題，提出了一種利用MapReduce和壓縮Hilbert R 樹算法并行建立Hilbert R 樹索引的方法，提高了空間矢量數(shù)據(jù)的檢索效率。但這種方案僅在全文檢索這種時(shí)效性要求不高的情況下適用，沒(méi)有辦法滿足索引的實(shí)時(shí)構(gòu)建。

Zhang 等［2］使用MapReduce 并行計(jì)算框架，對(duì)海量數(shù)據(jù)的KNN join 進(jìn)行高效處理，在reduce 階段利用R 樹對(duì)局部數(shù)據(jù)構(gòu)建索引，從而提高了KNN 連接的速度，但這種方法由于沒(méi)有全局索引，檢索時(shí)會(huì)消耗部分搜索局部索引的時(shí)間。

2014 年，Alsubaiee 等［7］提出的基于LSM-Tree 的混合異構(gòu)索引通過(guò)bulk-loading 方式可以兼顧基線數(shù)據(jù)和增量數(shù)據(jù)更新的問(wèn)題，但是只能用于AsterixDB［8］系統(tǒng)，并且bulk-loading方式的索引組件由多種數(shù)據(jù)結(jié)構(gòu)組成，大大增加了索引維護(hù)和系統(tǒng)負(fù)載均衡的難度。

2 基于LSM-Tree的分布式索引的構(gòu)建

2.1 索引的結(jié)構(gòu)

針對(duì)非主鍵屬性查詢效率低的問(wèn)題，構(gòu)建輔助索引［9］是一個(gè)很好的解決方案。因而，本文基于LSM-Tree 架構(gòu)的索引方法SIBL，通過(guò)建立輔助索引，并將索引數(shù)據(jù)表看作普通的數(shù)據(jù)表存儲(chǔ)在數(shù)據(jù)庫(kù)中，從而實(shí)現(xiàn)高可用性和高擴(kuò)展性的目標(biāo)。將需要查詢的非主鍵屬性列和原數(shù)據(jù)表的主鍵作為索引表的聯(lián)合索引，同時(shí)可以添加一些附加列信息。

SIBL 索引信息和存儲(chǔ)的原數(shù)據(jù)一樣都是基于LSM-Tree存儲(chǔ)架構(gòu)的，所以當(dāng)Mem-SI 的數(shù)量達(dá)到閾值時(shí)，會(huì)flush 到磁盤中的SST-SI進(jìn)行保存，如圖2所示。

圖2 SIBL索引存儲(chǔ)結(jié)構(gòu)Fig.2 SIBL index storage structure

之所以采用這種索引組織方式，因?yàn)槠溆幸韵氯c(diǎn)優(yōu)勢(shì)：

1）繼承分布式數(shù)據(jù)庫(kù)的讀寫分離特性。在基線數(shù)據(jù)sst1…ssti構(gòu)建SST-SI的過(guò)程中，原數(shù)據(jù)更新引發(fā)索引更新的操作維護(hù)在內(nèi)存中的Mem-SI上，進(jìn)而更好地維護(hù)數(shù)據(jù)和索引的一致性。

2）當(dāng)數(shù)據(jù)發(fā)生更新時(shí)，只需要在內(nèi)存中維護(hù)索引的增量，減少了更新索引造成的系統(tǒng)I/O。

3）索引數(shù)據(jù)和原數(shù)據(jù)表數(shù)據(jù)的存儲(chǔ)管理保持一致，分布式數(shù)據(jù)庫(kù)可以用原來(lái)管理原數(shù)據(jù)的方式來(lái)管理索引數(shù)據(jù)，使得索引的高可用性得以保證。

定義1通用的SIBL索引結(jié)構(gòu)：

SIBL 索引由內(nèi)存中的增量索引Mem-SI 和磁盤中的基線索引SST-SI 組成，增量索引和基線索引的主鍵是需要查詢的列和原數(shù)據(jù)表的主鍵相結(jié)合的聯(lián)合主鍵。Value 存儲(chǔ)的是查詢頻率較高的列值。這樣的結(jié)構(gòu)可以將不同列的索引存放在HBase的同一張表中，減少了表的數(shù)量。

由于提出的算法最終要在HBase數(shù)據(jù)庫(kù)上實(shí)現(xiàn)并驗(yàn)證其有效性，這里通過(guò)一個(gè)商品信息示例來(lái)分析SIBL索引結(jié)構(gòu)的優(yōu)勢(shì)。

表1 描述的是一個(gè)商品信息的HBase 數(shù)據(jù)表，主鍵為Item Key，表2 給出了HBase 索引表示例，當(dāng)需要根據(jù)商品名稱查詢價(jià)格時(shí)，可以將“name”列和原數(shù)據(jù)表的主鍵“Item Key”作為輔助索引表的聯(lián)合主鍵。在實(shí)際應(yīng)用的過(guò)程中，還可以將列名“name”映射到單個(gè)字母“n”。將需要查詢的“price”作為附加信息存儲(chǔ)在Value。

表1 HBase原數(shù)據(jù)表示例Tab.1 Example of HBase original data table

表2 HBase索引表示例Tab.2 Example of HBase index table

1）將列名“name”映射到單個(gè)字母“n”，可以大大減少系統(tǒng)存儲(chǔ)索引表的主鍵的空間開銷，實(shí)現(xiàn)輕量級(jí)的索引。

2）將Item key 存儲(chǔ)到索引表的主鍵中有兩個(gè)作用：一是保證了索引表主鍵的唯一性原則，避免因?yàn)橹麈I重復(fù)而丟失數(shù)據(jù)；二是為用戶提供了被索引記錄的地址信息，方便用戶獲取被索引列的整條記錄。

3）用戶在查詢“price”時(shí)，可以在輔助列中直接獲取信息，進(jìn)一步提高了輔助索引的查詢性能。

2.2 索引構(gòu)建算法

LSM-Tree［9］的顯著特點(diǎn)就是讀寫分離、批量更新。基于這種思想，本文將分布式系統(tǒng)中的數(shù)據(jù)劃分為兩部分：存儲(chǔ)在內(nèi)存中的增量數(shù)據(jù)和存儲(chǔ)在磁盤中的基線數(shù)據(jù)。提出一種先合并數(shù)據(jù)后構(gòu)建索引的策略。內(nèi)存中的數(shù)據(jù)增量會(huì)批量地寫入磁盤中，與基線數(shù)據(jù)合并。在基線數(shù)據(jù)和增量數(shù)據(jù)合并完成后，再構(gòu)建基線數(shù)據(jù)的索引。在數(shù)據(jù)合并的時(shí)間段內(nèi)，在內(nèi)存中對(duì)數(shù)據(jù)的增量構(gòu)建索引。輕量級(jí)的分布式索引構(gòu)建采用了MapReduce 框架，將原數(shù)據(jù)表的信息作為map輸入，接下來(lái)為每個(gè)輸入按照SIBL 索引結(jié)構(gòu)格式生成對(duì)應(yīng)的索引數(shù)據(jù)，將索引數(shù)據(jù)存儲(chǔ)在系統(tǒng)中。為了提高創(chuàng)建速度，可以同時(shí)創(chuàng)建多個(gè)線程并發(fā)的執(zhí)行。

如算法1 所示，SIBL 索引構(gòu)建算法可以劃分為3 個(gè)步驟：數(shù)據(jù)批量更新、局部索引構(gòu)建和索引區(qū)間劃分。首先啟動(dòng)批量更新過(guò)程（第1）～4）行），內(nèi)存中的增量數(shù)據(jù)不斷地合并到磁盤中，生成新的基線數(shù)據(jù)sst（S，V1）。需要注意的是，增量索引不做批量更新。數(shù)據(jù)批量更新結(jié)束后，反饋給主節(jié)點(diǎn)，數(shù)據(jù)更新后的版本記為V1。然后進(jìn)行局部索引構(gòu)建階段（第5）～8）行），同樣將信息反饋給主節(jié)點(diǎn)。生成的索引集合記為：F′(I) →{I1，I2，…，IK}。最后是索引區(qū)間的劃分階段（第9）行），將在2.3節(jié)詳細(xì)討論。

算法1 SIBL索引——整個(gè)構(gòu)建過(guò)程的算法。

輸入：表T的數(shù)據(jù)集S；

輸出：索引I。

算法2 描述了局部索引的構(gòu)建過(guò)程。對(duì)sst（S，V1）中的每一行數(shù)據(jù)執(zhí)行一次map 操作（第3）行），將原數(shù)據(jù)表的主鍵映射成由非主鍵屬性列和原數(shù)據(jù)表主鍵相結(jié)合在一起的新主鍵。即(k1，k2，…，ki，r1，r2，…，rj)，i=1，2，…，j=1，2，…映射成(rm，k1，k2，…，ki)，i=1，2，…，1 ≤m≤j。然后對(duì)索引主鍵進(jìn)行排序（第4）行），最后將排序好的索引寫入磁盤，成為局部索引local_index（第6）行）。

算法2 SIBL索引——構(gòu)建局部索引過(guò)程的算法。

2.3 基于等距取樣的索引區(qū)間劃分算法

索引區(qū)間的劃分決定著索引在系統(tǒng)中分布是否均勻，影響著整個(gè)系統(tǒng)的負(fù)載均衡和查詢效率。劃分索引區(qū)間的首要條件是要獲取到全部的索引信息，一個(gè)直接的方法是將索引數(shù)據(jù)全部存在一個(gè)節(jié)點(diǎn)上進(jìn)行排序，再將排序結(jié)果平均分配到其他節(jié)點(diǎn)，來(lái)保證每個(gè)索引分片的大小基本相等。但是在實(shí)際應(yīng)用中，索引的數(shù)據(jù)量十分龐大，單單靠一個(gè)計(jì)算節(jié)點(diǎn)是無(wú)法完成排序工作?？梢?，索引區(qū)間劃分的難點(diǎn)在于無(wú)法獲取全部的索引信息。為了解決這個(gè)問(wèn)題，本文提出了一種基于等距取樣的索引區(qū)間劃分算法，來(lái)計(jì)算索引表劃分的范圍區(qū)間。

等距取樣的思想是對(duì)于已經(jīng)排好序的局部索引數(shù)據(jù)，每間隔一定的距離d，就執(zhí)行取樣操作，把取樣結(jié)果寫入結(jié)果集?；诘染嗳拥乃饕齾^(qū)間劃分算法一共有兩次取樣過(guò)程。第一次在索引數(shù)據(jù)上進(jìn)行取樣，并將結(jié)果返回給主節(jié)點(diǎn)，經(jīng)主節(jié)點(diǎn)排序后，對(duì)排序結(jié)果執(zhí)行第二次取樣操作，得到劃分區(qū)間的序列并生成索引區(qū)間，然后根據(jù)局部索引和劃分區(qū)間序列的交集盡可能多的規(guī)則，將索引數(shù)據(jù)分配給合適的節(jié)點(diǎn)。這樣做代替了將索引數(shù)據(jù)全部存在一個(gè)節(jié)點(diǎn)上進(jìn)行排序再劃分的方法，即使數(shù)據(jù)量非常大，也可以高效地實(shí)現(xiàn)索引區(qū)間的劃分，使索引數(shù)據(jù)均勻分布，滿足系統(tǒng)的負(fù)載均衡策略。

定理1記數(shù)據(jù)分片數(shù)量N，索引的分片數(shù)量N′，每個(gè)數(shù)據(jù)區(qū)間長(zhǎng)度為L(zhǎng)，當(dāng)參數(shù)Q←N′-1 時(shí)，取樣的距離也為d←N′-1。

下面展示推導(dǎo)過(guò)程：

第一次等距取樣后得到的結(jié)果個(gè)數(shù)為：

第二次等距取樣后得到的結(jié)果個(gè)數(shù)為：

由式（1）和（2）：

根據(jù)定理1，基于等距取樣的索引區(qū)間劃分算法的偽代碼如算法3 所示，4）～7）行描述的是第一次取樣階段，對(duì)于所有局部索引，按照間隔d取樣，將取樣結(jié)果返回到major 節(jié)點(diǎn)并排序；8）～12）行描述的是第二次取樣階段，對(duì)于主節(jié)點(diǎn)排序好的結(jié)果，按照參數(shù)Q進(jìn)行取樣，得到s1，s2，…，sP序列；第13）行使用s1，s2，…，sP序列將索引數(shù)據(jù)切分成索引區(qū)間；偽代碼第14）行將索引區(qū)間分配給合適的節(jié)點(diǎn)；15）～19）行描述的是分配策略，如果索引區(qū)間和節(jié)點(diǎn)保存的局部索引有交集，則把這個(gè)區(qū)間分配給該節(jié)點(diǎn)。

算法3 基于等距取樣的索引區(qū)間劃分算法。

3 分布式索引SIBL的應(yīng)用

用戶在使用索引SIBL 時(shí)只需要兩步即可配置完成：第一步將分布式集群的配置文件添加到index.properties 文件中，以HBase數(shù)據(jù)庫(kù)為例，從配置文件中獲取zookeeper地址，添加到index.properties 中；第二步將Maven 項(xiàng)目編譯打包上傳到集群中運(yùn)行，即可成功創(chuàng)建索引文件，執(zhí)行相應(yīng)的查詢操作。

在普通索引方案中，當(dāng)需要以非主鍵索引列sk 為查詢條件查詢記錄A時(shí)，如果該屬性列已經(jīng)建立過(guò)索引，則直接對(duì)相應(yīng)的索引表進(jìn)行的前綴查詢，得到對(duì)應(yīng)的pk，再根據(jù)pk返回到原數(shù)據(jù)表查找與之對(duì)應(yīng)的整條記錄A［10］。需要進(jìn)行兩次遠(yuǎn)程調(diào)用（Remote Procedure Call，RPC）協(xié)議通信，而本文提出的基于冗余列的查詢方法就是在建立索引文件時(shí)，可以將一些用戶自主設(shè)定的查詢比較頻繁的列附加在索引文件內(nèi)，稱作冗余列。在通過(guò)非主鍵屬性列sk 進(jìn)行查詢時(shí)，如果該屬性列已經(jīng)建立過(guò)索引，直接在對(duì)應(yīng)的索引文件中查詢到相應(yīng)的索引行，要查詢的信息如果直接在冗余列中，則直接讀取并返回結(jié)果集。雖然冗余列會(huì)占用存儲(chǔ)空間，但是對(duì)于高可擴(kuò)展性的分布式集群來(lái)說(shuō)，用存儲(chǔ)的開銷來(lái)?yè)Q取查詢性能的提升，是很值得的［11-12］。在實(shí)際應(yīng)用的過(guò)程中，可以根據(jù)具體情況來(lái)自主選擇冗余列［13］。

查詢處理算法的偽代碼如算法4 所示，第1）行描述的是通過(guò)在索引表查詢非主鍵屬性sk，將得到的一些結(jié)果保存為tmp_result；第2）行描述的是對(duì)tmp_result中的每一條數(shù)據(jù)執(zhí)行下面的if操作；第3）～6）行中，如果查詢的列在冗余列中，就把該列值添加到結(jié)果集result_set中，返回給客戶端。

算法4 基于冗余列的查詢算法。

4 實(shí)驗(yàn)與結(jié)果

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境搭建在三臺(tái)本地電腦的虛擬機(jī)中，通過(guò)ssh 通信，完成HBase分布式系統(tǒng)的搭建［14-15］。

硬件配置：本地電腦CPU Intel Core i7-8565U 1.8 GHz；內(nèi)存8.00 GB。在環(huán)境搭建的過(guò)程中要充分考慮軟件版本的兼容性。軟件版本的選擇如下：虛擬機(jī)VMware workstation 15、Linux centos 7 64 位、Java 1.8.0_131、Hadoop-1.1.0、HBase-0.94.8、Zookeeper-3.4.10、連接工具-X shell 6、實(shí)驗(yàn)的數(shù)據(jù)集采用某電商網(wǎng)站對(duì)不同年齡不同職業(yè)等因素對(duì)的購(gòu)買力影響程度脫敏后的調(diào)查數(shù)據(jù)。整個(gè)數(shù)據(jù)集共有1 040 000 條，包含10 個(gè)不同的屬性，ID（脫敏過(guò)的用戶編號(hào)）、Name（姓名）、Gender（性別）、Age（年齡）、Occupation（職業(yè)）、City_level（生活的城市水平）、Consumption_level（消費(fèi)檔次）、Shopping_level（購(gòu)物深度）、cms_segid（電商網(wǎng)站的微群ID），其中ID為主鍵。系統(tǒng)構(gòu)建索引分兩種情況。一種是單列索引，另一種是組合索引。該數(shù)據(jù)集主要用來(lái)評(píng)估這兩種情況下索引的查詢性能。同樣與華為HIndex 二級(jí)索引方案進(jìn)行多組對(duì)比實(shí)驗(yàn)，得出實(shí)驗(yàn)數(shù)據(jù)，進(jìn)行分析。

4.2 結(jié)果與分析

4.2.1 索引構(gòu)建性能

本文提出的SIBL方法實(shí)現(xiàn)了兩種構(gòu)建索引的途徑：第一種是在用戶表創(chuàng)建時(shí)，針對(duì)相應(yīng)的非主鍵屬性列構(gòu)建對(duì)應(yīng)的索引表；另一種，是對(duì)已經(jīng)存在的用戶表，后續(xù)增加相應(yīng)的索引表，即運(yùn)行IndexBuilderFromFile 類為已經(jīng)存在的用戶表創(chuàng)建索引表。這里對(duì)索引的構(gòu)建性能進(jìn)行評(píng)估，即評(píng)估索引構(gòu)建需要的時(shí)間開銷和空間開銷。這里采用YCSB測(cè)試工具，在集群上運(yùn)行如下指令，bin/ycsb load hbase094-P workloads/workloada-p threads=10-p table=testtable-p columnfamily=family-p recordcount=7 000 000-s，生成7 000 000行測(cè)試數(shù)據(jù)，數(shù)據(jù)集大小為0.9 GB。每條數(shù)據(jù)由非主鍵列field0～field9組成。然后采用IndexBuilderFromFile 類為非主鍵屬性列field4構(gòu)建索引，并導(dǎo)入HBase 的索引表test_idx_field4 中，記錄導(dǎo)入時(shí)間。重復(fù)以上操作，將recordcount更改為11 000 000行和12 400 000行，構(gòu)建對(duì)應(yīng)的非主鍵屬性列field4索引表，分別記錄數(shù)據(jù)集的大小、用戶表導(dǎo)入HBase的時(shí)間與構(gòu)建索引時(shí)，索引表和用戶表同時(shí)導(dǎo)入HBase中的時(shí)間。

表4 構(gòu)建索引前后導(dǎo)入時(shí)間對(duì)比Tab.4 Comparison of importing time before and after index construction

分析表中數(shù)據(jù)可以得出，索引表和用戶表同時(shí)導(dǎo)入時(shí)間分別是單獨(dú)用戶表導(dǎo)入時(shí)間的1.47 倍，1.28 倍和1.60 倍。因?yàn)樵跇?gòu)建索引時(shí)采用了MapReduce 框架來(lái)并行執(zhí)行，并行地將索引數(shù)據(jù)插入到索引表中，通過(guò)該實(shí)驗(yàn)結(jié)果表明，SIBL方法構(gòu)建索引的時(shí)間開銷是可接受的。

索引的空間開銷評(píng)估即是對(duì)HBase系統(tǒng)內(nèi)存占用情況的評(píng)估，通過(guò)對(duì)原始用戶表在HBase上占用的內(nèi)存和構(gòu)建索引后，用戶表和索引表占用的總內(nèi)存進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表5所示。

表5 構(gòu)建索引前后空間開銷對(duì)比Tab.5 Comparison of space overhead before and after index construction

4.2.2 索引查詢性能

索引的查詢性能就是對(duì)非主鍵進(jìn)行查詢時(shí)的響應(yīng)時(shí)間，本文使用三種系統(tǒng)來(lái)對(duì)數(shù)據(jù)集的四種查詢進(jìn)行評(píng)估。這三種系統(tǒng)依次為華為HIndex系統(tǒng)、本文提出的SIBL方法以及原始的HBase系統(tǒng)。圖3給出的是4組測(cè)試用例、三種系統(tǒng)的非主鍵索引查詢性能對(duì)比情況。圖中以查詢所得的記錄條數(shù)為橫坐標(biāo)，查詢響應(yīng)時(shí)間為縱坐標(biāo)。

圖3 非主鍵索引的查詢性能對(duì)比Fig.3 Non-primary key index query performance comparison

綜合上面的實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)，除了查詢所得記錄條數(shù)過(guò)少或過(guò)大的極端情況，一般而言，SIBL 方法的查詢性能相較于華為HIndex 提升了2 倍左右，隨著查詢結(jié)果規(guī)模的不斷增大，相較華為HIndex 的性能提升逐漸縮??；SIBL 方法的查詢性能相較于原始HBase 查詢，提升了50 倍左右。當(dāng)查詢結(jié)果集過(guò)小時(shí)，相較原始HBase查詢的性能提升效果最顯著，達(dá)到了200 倍。這是因?yàn)樵糎Base 只針對(duì)主鍵構(gòu)建索引，在進(jìn)行非主鍵查詢時(shí)，無(wú)論查詢結(jié)果集有多小，都需要全表掃描，遍歷所有的用戶表數(shù)據(jù)；而SIBL 方法則可以快速地定位到想查詢的非主鍵信息。從實(shí)驗(yàn)數(shù)據(jù)中還可以發(fā)現(xiàn)，無(wú)論是華為HIndex，還是本文提出的SIBL 方法，查詢響應(yīng)時(shí)間都隨著查詢結(jié)果集條數(shù)的增加而不斷增大。

4.2.3 負(fù)載均衡和可擴(kuò)展性

索引構(gòu)建完畢后，通過(guò)HBase 的Web-UI 可以查看到索引文件在HRegionServer 中的分布情況。索引文件的51.57%存儲(chǔ)在hbase02 服務(wù)器上，48.43%存儲(chǔ)在hbase03 服務(wù)器上，滿足系統(tǒng)的負(fù)載均衡策略。

采用YCSB 測(cè)試工具進(jìn)行測(cè)試，根據(jù)不同數(shù)據(jù)規(guī)模下單點(diǎn)查詢和范圍查詢的查詢響應(yīng)時(shí)間來(lái)判斷索引是否具有可擴(kuò)展性。從實(shí)驗(yàn)數(shù)據(jù)圖4可以看出，數(shù)據(jù)規(guī)模從500萬(wàn)條擴(kuò)展到3 500 萬(wàn)條時(shí)，單點(diǎn)查詢的查詢響應(yīng)時(shí)間保持著線性增長(zhǎng)；長(zhǎng)度為10 的范圍查詢也保持著線性增長(zhǎng)。這表明SIBL 方法具有良好的可擴(kuò)展性。隨著數(shù)據(jù)規(guī)模的不斷增大，索引數(shù)據(jù)的規(guī)模也隨之增大，查詢響應(yīng)時(shí)間和數(shù)據(jù)規(guī)模成正比。

圖4 在數(shù)據(jù)規(guī)模增大時(shí)SIBL方法的查詢響應(yīng)時(shí)間對(duì)比Fig.4 Query response time comparison of SIBL method when data size increases

5 結(jié)語(yǔ)

基于LSM-Tree 的輕量級(jí)分布式索引實(shí)現(xiàn)方法SIBL 采用MapReduce 框架并發(fā)地為磁盤和內(nèi)存中的基線數(shù)據(jù)和增量數(shù)據(jù)分別構(gòu)建索引，可以在不侵入分布式系統(tǒng)源碼的前提下，讓用戶輕松地集成到自己的集群中，極大地提高索引的構(gòu)建速度；設(shè)計(jì)的基于等距取樣的索引區(qū)間劃分算法，維護(hù)了系統(tǒng)的負(fù)載均衡。提出的基于冗余列查詢方法，進(jìn)一步提高了非主鍵索引的查詢效率。提出的算法都在HBase 中得到了驗(yàn)證，通過(guò)實(shí)驗(yàn)結(jié)果看出，本文提出的SIBL 方法對(duì)非主鍵查詢性能優(yōu)于華為HIndex和原始HBase查詢。分布式數(shù)據(jù)庫(kù)的種類繁多，不同數(shù)據(jù)庫(kù)的實(shí)現(xiàn)細(xì)節(jié)不盡相同，接下來(lái)計(jì)劃在不同的分布式數(shù)據(jù)庫(kù)上開展更多測(cè)試，不斷優(yōu)化索引的性能。