基于日志結構合并樹的輕量級分布式索引實現方法

（哈爾濱工業大學計算學部，哈爾濱 150001）

0 引言

如今，隨著移動互聯網等技術的普及，數據量呈爆炸式增長。大規模數據對數據管理提出了迫切的需求，傳統的數據庫對于超大規模數據存取的效率低，難以支持高并發訪問。為此，分布式數據庫應運而生。但是這類數據庫也存在著對數據查詢訪問不夠靈活的缺點。分布式數據庫系統通常根據主鍵按照一定規則將數據進行劃分，將數據片段冗余地存儲在集群中的計算節點上，同時在主鍵上構建索引，來支持高效的主鍵查詢。而針對非主鍵屬性列的查詢，系統無法確定數據的分片信息具體存儲在哪個計算節點上，只能通過全表掃描進行查詢，效率較低。所以，如何提升非主鍵查詢效率成為分布式數據庫系統的亟須解決的問題。

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

綜上，現有的方案無法同時滿足這三點要求：針對已有的海量數據高效地創建索引；用戶可以將方案快速地應用在自己的集群中；兼顧磁盤中基線數據索引構建和內存中隨時發生的增量數據更新。

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

首先，LSM-Tree是非常優秀的數據檢索引擎，由一個駐存在內存中的樹結構和多個位于磁盤上的樹結構組成。分布式數據庫采用這種分層的思想，將數據分成兩部分來存儲，內存中的數據memStore 相當于LSM-Tree 中的C0Tree，磁盤中的數據StoreFile 相當于LSM-Tree 中的C1Tree 和C2Tree，當內存中的數據量到達閾值后順序寫入磁盤，數據更新只發生在內存中；磁盤中的數據會定期地整合，避免不必要的I/O，可見基于LSM-Tree 的索引方法可以極大提高系統的寫入性能，同時讓索引更高效。

圖1 LSM-Tree與Store結構對應圖Fig.1 Structure correspondence between LSM-Tree and Store

SIBL 采用MapReduce 框架的并行計算快速地對數據進行批量構建。通過調用系統接口，創建索引表，將原數據表的非主鍵列映射到索引表的主鍵，查詢頻率較高的列附加在索引表的value 中，同時提供單列索引和聯合索引兩種構建方式。用戶還可以根據需求自由選擇索引構建方案：對已有數據構建索引或者將索引和原數據表同時構建。

本文的主要貢獻如下：

1）設計了通用的SIBL 索引結構，及分布式索引構建算法，在不侵入分布式系統源碼的前提下實現輕量級索引方案，滿足用戶既可以在生成用戶表的階段同時創建索引，又可以對現有用戶表構建索引的需求。

2）針對分布式索引區間的劃分，提出基于等距取樣的索引區間劃分算法，實現索引的均勻分布；優化了索引的查詢算法，避免回表查詢，支持多個非主鍵屬性列聯合查詢，提高查詢效率。

3）在HBase數據庫上與華為HIndex方案進行多組對比實驗，結合實驗數據，驗證了本文所有算法的有效性和正確性。

1 相關工作

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

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

分片位圖索引方案［4］利用局部索引來簡化索引的維護，提高查詢效率。實現方式是將過濾條件生成為條件位圖，與所有計算節點維護的局部位圖進行位運算，但由于查詢時需要訪問所有節點，也會造成了一定的資源浪費。用戶在使用時需要為局部索引生成局部位圖，大大增加了任務量。

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

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

王文賢等［1］針對海量矢量空間數據的存儲和查詢問題，提出了一種利用MapReduce和壓縮Hilbert R 樹算法并行建立Hilbert R 樹索引的方法，提高了空間矢量數據的檢索效率。但這種方案僅在全文檢索這種時效性要求不高的情況下適用，沒有辦法滿足索引的實時構建。

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

2014 年，Alsubaiee 等［7］提出的基于LSM-Tree 的混合異構索引通過bulk-loading 方式可以兼顧基線數據和增量數據更新的問題，但是只能用于AsterixDB［8］系統，并且bulk-loading方式的索引組件由多種數據結構組成，大大增加了索引維護和系統負載均衡的難度。

2 基于LSM-Tree的分布式索引的構建

2.1 索引的結構

針對非主鍵屬性查詢效率低的問題，構建輔助索引［9］是一個很好的解決方案。因而，本文基于LSM-Tree 架構的索引方法SIBL，通過建立輔助索引，并將索引數據表看作普通的數據表存儲在數據庫中，從而實現高可用性和高擴展性的目標。將需要查詢的非主鍵屬性列和原數據表的主鍵作為索引表的聯合索引，同時可以添加一些附加列信息。

SIBL 索引信息和存儲的原數據一樣都是基于LSM-Tree存儲架構的，所以當Mem-SI 的數量達到閾值時，會flush 到磁盤中的SST-SI進行保存，如圖2所示。

圖2 SIBL索引存儲結構Fig.2 SIBL index storage structure

之所以采用這種索引組織方式，因為其有以下三點優勢：

1）繼承分布式數據庫的讀寫分離特性。在基線數據sst1…ssti構建SST-SI的過程中，原數據更新引發索引更新的操作維護在內存中的Mem-SI上，進而更好地維護數據和索引的一致性。

2）當數據發生更新時，只需要在內存中維護索引的增量，減少了更新索引造成的系統I/O。

3）索引數據和原數據表數據的存儲管理保持一致，分布式數據庫可以用原來管理原數據的方式來管理索引數據，使得索引的高可用性得以保證。

定義1通用的SIBL索引結構：

SIBL 索引由內存中的增量索引Mem-SI 和磁盤中的基線索引SST-SI 組成，增量索引和基線索引的主鍵是需要查詢的列和原數據表的主鍵相結合的聯合主鍵。Value 存儲的是查詢頻率較高的列值。這樣的結構可以將不同列的索引存放在HBase的同一張表中，減少了表的數量。

由于提出的算法最終要在HBase數據庫上實現并驗證其有效性，這里通過一個商品信息示例來分析SIBL索引結構的優勢。

表1 描述的是一個商品信息的HBase 數據表，主鍵為Item Key，表2 給出了HBase 索引表示例，當需要根據商品名稱查詢價格時，可以將“name”列和原數據表的主鍵“Item Key”作為輔助索引表的聯合主鍵。在實際應用的過程中，還可以將列名“name”映射到單個字母“n”。將需要查詢的“price”作為附加信息存儲在Value。

表1 HBase原數據表示例Tab.1 Example of HBase original data table

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

1）將列名“name”映射到單個字母“n”，可以大大減少系統存儲索引表的主鍵的空間開銷，實現輕量級的索引。

2）將Item key 存儲到索引表的主鍵中有兩個作用：一是保證了索引表主鍵的唯一性原則，避免因為主鍵重復而丟失數據；二是為用戶提供了被索引記錄的地址信息，方便用戶獲取被索引列的整條記錄。

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

2.2 索引構建算法

LSM-Tree［9］的顯著特點就是讀寫分離、批量更新?；谶@種思想，本文將分布式系統中的數據劃分為兩部分：存儲在內存中的增量數據和存儲在磁盤中的基線數據。提出一種先合并數據后構建索引的策略。內存中的數據增量會批量地寫入磁盤中，與基線數據合并。在基線數據和增量數據合并完成后，再構建基線數據的索引。在數據合并的時間段內，在內存中對數據的增量構建索引。輕量級的分布式索引構建采用了MapReduce 框架，將原數據表的信息作為map輸入，接下來為每個輸入按照SIBL 索引結構格式生成對應的索引數據，將索引數據存儲在系統中。為了提高創建速度，可以同時創建多個線程并發的執行。

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

算法1 SIBL索引——整個構建過程的算法。

輸入：表T的數據集S；

輸出：索引I。

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

算法2 SIBL索引——構建局部索引過程的算法。

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

索引區間的劃分決定著索引在系統中分布是否均勻，影響著整個系統的負載均衡和查詢效率。劃分索引區間的首要條件是要獲取到全部的索引信息，一個直接的方法是將索引數據全部存在一個節點上進行排序，再將排序結果平均分配到其他節點，來保證每個索引分片的大小基本相等。但是在實際應用中，索引的數據量十分龐大，單單靠一個計算節點是無法完成排序工作。可見，索引區間劃分的難點在于無法獲取全部的索引信息。為了解決這個問題，本文提出了一種基于等距取樣的索引區間劃分算法，來計算索引表劃分的范圍區間。

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

定理1記數據分片數量N，索引的分片數量N′，每個數據區間長度為L，當參數Q←N′-1 時，取樣的距離也為d←N′-1。

下面展示推導過程：

第一次等距取樣后得到的結果個數為：

第二次等距取樣后得到的結果個數為：

由式（1）和（2）：

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

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

3 分布式索引SIBL的應用

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

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

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

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

4 實驗與結果

4.1 實驗環境和數據集

實驗環境搭建在三臺本地電腦的虛擬機中，通過ssh 通信，完成HBase分布式系統的搭建［14-15］。

硬件配置：本地電腦CPU Intel Core i7-8565U 1.8 GHz；內存8.00 GB。在環境搭建的過程中要充分考慮軟件版本的兼容性。軟件版本的選擇如下：虛擬機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、實驗的數據集采用某電商網站對不同年齡不同職業等因素對的購買力影響程度脫敏后的調查數據。整個數據集共有1 040 000 條，包含10 個不同的屬性，ID（脫敏過的用戶編號）、Name（姓名）、Gender（性別）、Age（年齡）、Occupation（職業）、City_level（生活的城市水平）、Consumption_level（消費檔次）、Shopping_level（購物深度）、cms_segid（電商網站的微群ID），其中ID為主鍵。系統構建索引分兩種情況。一種是單列索引，另一種是組合索引。該數據集主要用來評估這兩種情況下索引的查詢性能。同樣與華為HIndex 二級索引方案進行多組對比實驗，得出實驗數據，進行分析。

4.2 結果與分析

4.2.1 索引構建性能

本文提出的SIBL方法實現了兩種構建索引的途徑：第一種是在用戶表創建時，針對相應的非主鍵屬性列構建對應的索引表；另一種，是對已經存在的用戶表，后續增加相應的索引表，即運行IndexBuilderFromFile 類為已經存在的用戶表創建索引表。這里對索引的構建性能進行評估，即評估索引構建需要的時間開銷和空間開銷。這里采用YCSB測試工具，在集群上運行如下指令，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行測試數據，數據集大小為0.9 GB。每條數據由非主鍵列field0～field9組成。然后采用IndexBuilderFromFile 類為非主鍵屬性列field4構建索引，并導入HBase 的索引表test_idx_field4 中，記錄導入時間。重復以上操作，將recordcount更改為11 000 000行和12 400 000行，構建對應的非主鍵屬性列field4索引表，分別記錄數據集的大小、用戶表導入HBase的時間與構建索引時，索引表和用戶表同時導入HBase中的時間。

表4 構建索引前后導入時間對比Tab.4 Comparison of importing time before and after index construction

分析表中數據可以得出，索引表和用戶表同時導入時間分別是單獨用戶表導入時間的1.47 倍，1.28 倍和1.60 倍。因為在構建索引時采用了MapReduce 框架來并行執行，并行地將索引數據插入到索引表中，通過該實驗結果表明，SIBL方法構建索引的時間開銷是可接受的。

索引的空間開銷評估即是對HBase系統內存占用情況的評估，通過對原始用戶表在HBase上占用的內存和構建索引后，用戶表和索引表占用的總內存進行比較。實驗結果如表5所示。

表5 構建索引前后空間開銷對比Tab.5 Comparison of space overhead before and after index construction

4.2.2 索引查詢性能

索引的查詢性能就是對非主鍵進行查詢時的響應時間，本文使用三種系統來對數據集的四種查詢進行評估。這三種系統依次為華為HIndex系統、本文提出的SIBL方法以及原始的HBase系統。圖3給出的是4組測試用例、三種系統的非主鍵索引查詢性能對比情況。圖中以查詢所得的記錄條數為橫坐標，查詢響應時間為縱坐標。

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

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

4.2.3 負載均衡和可擴展性

索引構建完畢后，通過HBase 的Web-UI 可以查看到索引文件在HRegionServer 中的分布情況。索引文件的51.57%存儲在hbase02 服務器上，48.43%存儲在hbase03 服務器上，滿足系統的負載均衡策略。

采用YCSB 測試工具進行測試，根據不同數據規模下單點查詢和范圍查詢的查詢響應時間來判斷索引是否具有可擴展性。從實驗數據圖4可以看出，數據規模從500萬條擴展到3 500 萬條時，單點查詢的查詢響應時間保持著線性增長；長度為10 的范圍查詢也保持著線性增長。這表明SIBL 方法具有良好的可擴展性。隨著數據規模的不斷增大，索引數據的規模也隨之增大，查詢響應時間和數據規模成正比。

圖4 在數據規模增大時SIBL方法的查詢響應時間對比Fig.4 Query response time comparison of SIBL method when data size increases

5 結語

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