基于HBase的多維索引查詢機制的優化

徐江峰，譚玉龍

（鄭州大學信息工程學院，鄭州450001）

0 引言

隨著無線和移動技術的進展，對移動性的需求日益增加，基于位置的服務（Location-Based Service，LBS）利用移動設備的能力，通過移動網絡提供用戶當前的地理位置。它們允許移動用戶搜索他們的環境，并使他們能夠立即訪問個性化和本地化的內容。目前，移動用戶可以使用各種各樣的LBS，包括路由映射應用程序、交互式城市指南、位置感知營銷、對象跟蹤和監控，以及基于鄰近［1］查找對象。LBS對底層支持平臺提出了廣泛的需求，包括對多維數據建模、處理數百萬用戶的高速更新以及對大量數據進行實時分析。

通過利用內置的索引功能和豐富的查詢處理語言，傳統關系數據庫管理系統（Relational Database Management System，RDBMS）可以在多維數據上提供高效和快速的復雜查詢處理。這些索引功能是通過在關系存儲之上創建額外的索引層來提供的。例如，Oracle spatial 支持基于R-tree［2］和四叉樹［3］的索引。然而，這些集中的系統會產生單一的故障點，實現起來成本很高，而且隨著數據量和用戶數量的增長，會遇到可伸縮性瓶頸。

分布式鍵值存儲成為一種提供彈性數據管理服務的新范式，可以根據不同應用程序的需求進行伸縮。當前的鍵值存儲（BigTable［4］、HBase［5］和Cassandra［6］）被設計成高可用性、高容錯性和保持高更新吞吐量支持數百萬用戶；但是，這些鍵值存儲只能處理單個屬性的高效精確匹配查詢，因為它們缺乏訪問多個屬性的內置索引機制。對于查詢多個屬性，有兩個設計選項可用：第一種選擇是為每個屬性創建單獨的索引，但是，在管理大量數據時，創建多個索引表會給系統帶來巨大的額外負載；第二種選擇是使用MapReduce［7］范式的并行處理來掃描整個數據集，然而，LBS 需要實時的查詢處理，因此，對整個數據集進行并行掃描并不是很有用。

本文提出了一種新的數據分布和多維索引框架New-grid來支持云平臺上的LBS。由于鍵值存儲的優點，使用它們作為存儲后端是很自然的選擇。然而，在鍵值存儲之上開發這樣的索引框架的關鍵挑戰是：如何對多維數據進行有效建模，并為其提供高效處理復雜多維查詢的能力。New-grid 采用基于Hilbert 曲線［8］的線性化技術解決前一個問題，然后將其與改進的覆蓋網絡P-Grid［9］進行集成。優化的New-grid 通過預先計算并將子空間分配給網絡中的節點，成為一個靜態網絡。Hilbert 曲線在保持數據局部性的同時，將多維屬性映射到一維。另一方面，P-Grid 以虛擬二進制形式呈現的節點進行排列，并將多維搜索空間劃分為子空間。前綴結構充當底層鍵值存儲之上的靜態路由索引層，并充當多維搜索的入口點。因此，本文主要工作之一就是建立這個P-Grid覆蓋網絡，然后由New-grid 根據P-Grid 前綴的路由機制在集群中進行分布復雜的查詢。綜上所述，本文的主要工作如下：

1）提出一種新的數據分布和多維索引框架New-grid，它可以有效地索引和處理點、范圍和K 最近鄰（K-Nearest Neighbors，KNN）查詢。

2）利用基于Hilbert 空間填充曲線的線性化技術將多維數據轉換為一維數據，同時保持了數據的局部性。

3）提出一種利用改進的P-Grid 前綴路由機制動態處理線性化值上的點、范圍和KNN 查詢的算法，以消除創建和維護單獨索引表的開銷。

4）在Amazon EC2 上進行實驗來測量insert 吞吐量以及點、范圍和KNN 查詢，以展示本文的框架相比MD-Hbase 的有效性。

1 相關技術

1.1 空間填充曲線的線性化

線性化是一種將多維屬性映射到一維空間上的降維方法。空間填充曲線是一種線性化技術，它是在不重疊的情況下，通過訪問n 維超立方體中的每個點來構造連續曲線。它們的優勢是：在映射之后，在n 維空間中的相鄰點在一維空間中也保持鄰近。因此，空間填充曲線在圖像處理［10］、科學計算［11］、地理信息系統［12］等需要順序訪問數據集的應用中得到了廣泛的應用。在New-grid 中，本文使用Hilbert 空間填充曲線索引底層一維鍵值存儲中的多維點，以提高查詢效率。

Hilbert 曲線是一種連續的空間填充曲線，它在多維數據點上產生順序排列。形式上，希爾伯特曲線是一個一對一的函數：

其中n 是2m×2m 空間維度的數量，n ≥2，m ＞1。這個函數決定了Hilbert 值（H 值）的原始坐標空間中的每個點的H值∈(0，2mn-1)。圖1 展示了二維空間中的坐標及其一階等效Hilbert 曲線。遞歸構造階數i ＞1 曲線，將一階曲線的每個頂點旋轉或反射后，替換為i-1階曲線，以適應新的曲線［13］。

遞歸構造過程也可以表示為一個樹形結構（圖3），用二進制符號［14］表示坐標點n 與H 值的對應關系。樹的深度等于曲線的階數，根節點對應圖1 的一階曲線。同時，任意樹級的節點集合i 描述了i 階曲線，以點（10，11）為例，用圖3 所示的樹結構來演示二維二階H 值的計算。在第一步中，將點（10，11）坐標的頂端位串聯起來，形成n點11。在根節點上，這個n點對應于子空間10。在下一步中，沿著根的子空間10，從樹的第1 層下降到第2 層。把這個點坐標的后兩位連起來形成n 點01。在樹的第2 層，n 點對應于子空間01。由于沒有更多的層可以下降，H 值的計算就結束了。點（10，11）的最終H 值由在每個步驟中從根節點開始的子空間的值串聯而成，即1001。使用樹結構生成點的H 值需要每個屬性的基數相等。然而，在LBS 中，屬性的基數可能是不相等的。因此，在Newgrid 中，使用文獻［15］中給出的算法計算H 值，該算法使用邏輯運算高效地計算Hilbert 曲線上屬性不相等的點的直接映射和逆映射。

圖1 二維空間及其等效一階希爾伯特曲線Fig.1 Two-dimensional space and its equivalent first order Hilbert curve

圖2 二維二階Hilbert曲線Fig.2 Two-dimensional second-order Hilbert curve

圖3 二維二階Hilbert曲線的樹表示Fig.3 Tree representation of two-dimensional second order Hilbert curve

1.2 P-Grid

P-Grid［16］是一種基于分布式散列表的可伸縮自組織結構化覆蓋網絡，它的訪問結構是基于虛擬二叉樹的。二叉樹結構用于為精確匹配和范圍查詢實現基于前綴的路由策略。P-Grid 為每個節點n 分配一個二進制位串，表示其在整個字典樹中的位置，稱為節點的路徑（n），該路徑包含從葉子到根的序列。圖4 為P-Grid 二叉樹的示意圖。存儲一個數據項，P-Grid 使用保哈希函數將數據項的標識符轉換成一個二進制關鍵key(key ∈[0，1])。數據項被路由到該節點的路徑與key最長公共前綴。例如，圖4 中節點2 的路徑為01，因此它存儲了所有鍵值以01開頭的數據項。

圖4 P-Grid字典樹示例Fig.4 Example of P-Grid trie

P-Grid 采用一種完全分散并行的構造算法，可以構造出延時較短的覆蓋網絡。構建過程嚴格基于本地對等交互，這種交互是通過在已有的非結構化覆蓋網絡上發起隨機遍歷來完成的。P-Grid 中的每個節點都維護一個路由表，該表存儲關于網絡中其他節點的路徑的信息。具體地說，對于每個位置，它維護至少一個節點的地址，而且該節點的路徑在該位置上具有相反的位。該信息以[path(n)，FQDN(n)]的形式存儲在路由表中，其中FQDN(n)是節點的全限定域名。具體構造算法見文獻［17］。

2 New-grid數據分布和索引框架

New-grid 索引框架由從云端租用的無共享節點集群組成。New-grid 的主要目標是通過一個真正分散的P2P 架構來支持LBS，該架構可以相應地進行擴展。New-grid通過采用簡單的兩層架構來實現。上層是基于P-Grid 的覆蓋網絡，該網絡負責路由查詢并為計算節點分配子空間，而下層則根據數據模型的類型使用底層鍵值存儲（HBase）來維護數據。Newgrid 中的節點有兩個用途：一個節點是P-Grid 中的節點，因為它維護其路由表中所有其他節點的子空間信息；另一個節點是HBase 集群的一部分，它存儲實際數據。New-grid 的體系結構將查詢處理分為兩個階段：在第一階段中，通過搜索路由表來確定存儲子空間的節點。路由表包含所有其他節點的引用，這是通過將節點安排在一個虛擬二進制樹結構中來實現的。在第二階段，查詢被轉發到本地處理它的負責節點上。

New-grid 系統架構如圖5 所示。本文使用自底向上的方法構造New-grid，其中節點首先被安排在HBase 集群中，然后加入覆蓋網絡。建設是在一個離線的過程中完成，并有一個小的一次性設置成本。數據插入可以在任何節點上完成。為了插入數據，首先計算多維點的H值，并根據給出的數據模型進行插入，底層使用Apache HBase［5］來存儲多維點的H 值，將其用作唯一的行鍵。

2.1 數據插入和點查詢

數據插入和點查詢可以通過使用P-Grid的搜索機制來執行，將插入或查詢請求轉發到負責節點。本文的算法（算法1和算法2）利用鍵值存儲提供直接數據訪問的能力，各自高效地插入數據和處理點查詢。在算法1 中，插入一個點，首先計算該點（第1）行）的二進制H 值（rowkey）。然后，對于每個節點模型的表，插入操作分為兩個階段：在第一階段，搜索路由表ρ，找到名稱為（FQDN）節點的路徑的最長公共前綴行鍵（第2）行）。此模型將數據存儲在一個表中，該表的名稱設置為節點的名稱，此步驟足以找到負責存儲該點的表的名稱。在第二階段，按照標準的insert 操作在表中插入rowkey（第3）行），對于表共享模型，可以很容易地在預定義的共享表中插入rowkey（第5）行）。

Algorithm 1：Data Insert（point p，value v）

1） rowkey←compute H-value（p）

//Table per Node//

2） n.Table=PrefixMatchingBinarySearch(ρ，rowkey)

3） n.Table.insert（rowkey，value v）

4） return true

//Table Share//

5） sharedTable.insert（rowkey，value v）

6） return true

圖5 New-grid系統架構Fig.5 New-grid system architecture

算法2 是查詢處理算法，對于每個節點模型的表，查詢處理分為兩個階段。給定d 維點p=(p1，p2，…)，點查詢策略試圖識別與p 關聯的值v。為了處理查詢，首先計算該點的H 值來計算行鍵（第1）行）。在第一階段，搜索路由表ρ，找到名稱為（FQDN）的節點，這個節點路徑與rowkey是最長的公共前綴（第2）行）。在第二個階段，通過檢索到v，在表上實現鍵查找操作。

Algorithm 2：Point Query Processing(p)

Input：query point p

Output：value v associated with p

1） rowkey←compute H-value（p）

//Table per Node//

2） n.Table=PrefixMatchingBinarySearch(ρ，rowkey)

3） return（v←lookup(rowkey，n.Table))

//Table Share//

4） return（v←lookup（rowkey，sharedTable））

2.2 范圍查詢處理

范圍查詢是檢索某個屬性位于上下邊界之間的所有記錄的查詢類型，在形式上分為兩種類型。范圍查詢是由上下邊界坐標(l1，l2，…，ln)和(u1，u2，…，un)構成的超矩形區域，其中min ≤li≤ui≤max。LBS 中的另一個形式是“獲取z 半徑內（x經度，y緯度）附近的所有值”。P-Grid基于二叉樹的分區將線性化后的空間劃分為大小相等的子空間，并根據節點的路徑將子空間分配給節點。范圍查詢區域與一個或多個子空間相交。一個簡單的范圍查詢策略將通過在查詢下限和上限相交的子空間之間搜索來檢索查詢區域中包含的所有點。本文算法將范圍查詢處理分為以下兩個階段：

1）在第一階段中，將原始的范圍查詢劃分為更小的子查詢，每個子查詢區域與之相交的子空間都有一個子查詢，通過計算查詢區域內每個子空間中點的最小H值來實現。將該點稱為下一個匹配點，并將其計算為calculate-next-match（）的函數。

2）在第二階段中，根據P-Grid 的搜索機制處理每個子查詢，該搜索機制將子查詢轉發給路徑與子查詢的上下界相交的所有節點。

例如，考慮圖6 所示的范圍查詢Q1。它的下界和上界坐標是A（01，01）和F（11，10）。等效H 值范圍這個查詢的值是［0010，1011］。二進制樹將空間劃分為大小相等的四個象限，即00、01、10 和11。要搜索的第一個子空間由下界H 值確定，下界H 值為00。為了得到范圍查詢中包含的點，需要搜索位于上下子空間之間的所有后續子空間。例如，簡單查詢策略將搜索00、01 和10 個子空間。子空間11 雖然與查詢相交，但是將被跳過。

圖6 映射到二維Hilbert曲線的二階點的范圍查詢示例Fig.6 Example of a range query on points mapped to two-dimensional second order Hilbert curve

該算法迭代地確定在樹的任意節點上與當前查詢區域相交的最小子空間。在每次迭代中，將丟棄一半的子空間，并沿著樹的正確分支下行，直到在葉級找到下一個匹配。同樣，這種下降是一個迭代過程，在每次迭代中，都用搜索子空間的邊界來限制用戶定義的搜索空間。

Algorithm 3：Range Query Processing

Input：query lower point ql，query higher point qh

Output：result set Rq

1） Rq←?

2） Sr←?

3） Hl←compute

4） Hh←compute H-value（qh）

5） Sr←calculateSubRanges

6） for each s ∈Srdo

7） Rq←PGrid.Search(s)

8） end for each

9） return Rq

2.3 KNN查詢處理

在一個d 維空間S，給定一組點N，根據一個距離函數，查詢處理算法返回一組k ∈N 的點，這些點鄰近于q。由于之前的結構對節點間的數據分布是不可伸縮的，而且基于MapReduce 框架對大量數據進行KNN 查詢的解決方案會導致很高的查詢延遲。為了緩解這些問題，提出了一個簡單的查詢處理策略。KNN 查詢處理算法以遞增的搜索區域迭代執行范圍搜索，直到檢索到k 個點為止。算法4 給出了KNN查詢算法的步驟。在第2）行中，首先構造一個范圍r，集中在查詢點和初始半徑δ=Dk/k，Dk表示查詢點q 和它的K 最近鄰點的估計距離。Dk可以用式（1）［18］估計：

其中：Γ(x+1)=xΓ(x)，Γ(1)=1，Γ(1/2)=π/2，d 是維度，N 是基數。

Algorithm 4：K Nearest Neighbors(q，k)

Input：query point q，number of nearest neighbors k

Output：k nearest neighbors

1） Qresult←?

2） δ ←estimateRadius(k)

3） r ←δ

4） while true do

5） ql←q-r

6） qh←q+r

7） Qresult←RangeSearch

8） if|Qresult|≥k then

9） return top k results of Qresult

10） else

11） r ←r+δ

12） end if

13）end while

3 性能分析

在Amazon EC2 上實現了New-grid，集群大小為4、8 和16個節點。每個節點都是EC2 的一個中型實例，由4 個虛擬內核、15.7 GB 內存、配置為1 TB 硬盤和Centos 6.4 OS 組成；節點通過1 GB 的網絡鏈路連接。數據存儲層使用Hadoop 1.2.1和HBase 0.94.10實現。點、范圍和KNN查詢的實驗是在一個包含4 億個點的合成數據集上進行的。該數據集是使用基于網絡的移動對象生成器生成的，該生成器模擬了舊金山灣區地圖上40 000 個對象的移動。每個對象移動10 000步，并在連續的時間戳上報告其位置（經度、緯度）。該數據集遵循一個傾斜分布，因為模擬器使用真實世界的公路網。本文運行一個簡單的MapReduce（MR）作業來計算數據集中點的最小值和最大值（區域邊界），并根據這些點的H 值的公共前綴設置節點的路徑。這有助于通過匹配預定義的子空間，使用行鍵在節點之間高效地分布數據集。行鍵將使用匹配的預定義子空間插入到正確的節點中。

在二維和三維數據集上進行了大量的實驗，以證明Newgrid的TPN和TS數據模型的有效性。以沒有覆蓋層的Hilbert曲線（H 階）作為索引層實現為基線。還針對MD-HBase［19］索引方案的TPB（MDH-TPB）和TS（MDH-TS）數據模型評估了New-grid 的性能。此外，還將范圍查詢的性能與MapReduce進行了比較。

3.1 插入的性能

LBS 不斷增長的趨勢，使其對可伸縮性的需求越來越明顯。使用YCSB［20］基準測試工具評估了New-grid的可伸縮性。圖7 將插入吞吐量的性能描述為包含4、8 和16 個節點的集群上的系統負載的函數。將工作負載生成器的數量從2 變化到96，其中每個工作負載根據Zipfian 分發版每秒生成10 000 個插入。在不同的節點上同時運行工作負載生成器并聚合結果。對于TS 模型，根據HBase 提供的水平可伸縮性，插入吞吐量幾乎隨工作負載生成器數量的增加而線性增長；但是，TPN 模型的插入吞吐量會隨著插入趨勢先增大后減小。對于位置更新60 s的間隔，TS模型達到峰值吞吐量約每秒840 000插入；然而，TPN 模型達到一個峰值吞吐量約每秒660 000 插入。兩種設計的性能都超過了MD-HBase，并且隨著節點數量的增加，差距也越來越大。

圖7 更改工作負載生成器數量的效果Fig.7 Effect of varying the number of workload generators

3.2 點查詢和范圍查詢的性能

多維點查詢和范圍查詢是LBS 中最常見的查詢。Newgrid通過直接查詢HBase表來處理點查詢。另一方面，范圍查詢的處理方法是首先將其劃分為多個子查詢，然后使用覆蓋層將每個子查詢同時轉發到負責節點。圖8 顯示了改變節點數量會對TPN、TS和H階模型的三維點查詢性能產生的影響。當增加節點數量時，所有模型的平均響應時間都增加了，尤其是TPN 模型。TS 和H 階模型的響應時間相同，因為它們都使用相同的查詢策略；但是，TPN 模型的響應時間比其他模型要長，這是因為需要通過搜索路由表并找到相關節點的成本較高。

圖8 點查詢性能(D=3)Fig.8 Performance of point query(D=3)

圖9 和圖10 分別顯示了不同選擇性和節點數量的TPN、TS、H 階和MR 模型的二維范圍查詢的性能。隨著節點數量的增加，TPN、TS 和H 階模型的查詢響應時間幾乎線性增加（圖9）；相反，MR 在對數據集進行全掃描以執行查詢時，其響應時間是恒定的，因此其響應時間與選擇性無關。TS 和TPN模型的性能優于其他模型，特別是對于選擇性較大的查詢，由于搜索區域較大的范圍查詢將與更多的子空間相交，從而產生多個子查詢。從圖10 中可以看出增加節點數量和同時保持10%的選擇性對平均范圍查詢響應時間的影響。隨著節點數量的增加，平均查詢響應時間會減少，因為節點數量的增加會導致數據的有效分布。此外，TPN 模型的性能優于TS 模型，因為TPN 模型將所有數據本地存儲在節點上，而TS 模型將數據分布在集群中。

圖9 范圍查詢的性能(節點數為4，D=2)Fig.9 Performance of range query（number of nodes is 4，D=2）

圖10 范圍查詢的性能（選擇性=10%，D=2）Fig.10 Performance of range query（selectivity=10%，D=2）

在三維數據集上進行實驗的結果如圖11 和圖12 所示。圖11顯示了在4個節點集群上作為選擇性函數三維范圍查詢的性能。當增加選擇性時，TPN 和TS 模型的平均查詢響應時間會增加。在本實驗中，除了H 階模型和MR 模型外，還將TPN 和TS 模型的結果與MD-HBase 的TPB 和TS 數據模型進行了比較。比較結果表明，即使在選擇性較大的情況下，TPN和TS 模型的性能也較好。這是因為，在MD-HBase 中使用額外的索引層來修剪結果集，而在本文的方案中沒有這樣的開銷。

圖11 范圍查詢的性能（節點數為4，D=3）Fig.11 Performance of range query（number of nodes is 4，D=3）

圖12 范圍查詢的性能（選擇性=10%，D=3）Fig.12 Performance of range query（selectivity=10%，D=3）

3.3 KNN查詢的性能

New-grid 迭代處理k 個最近鄰居（KNN）查詢。首先利用式（1）估計查詢點與其第k 個近鄰之間的距離，即初始搜索半徑；然后，執行范圍搜索來檢索k個結果，如果k個結果沒有返回，通過增加搜索空間并再次執行范圍搜索。圖13 顯示了通過在4 個節點集群中將k 的值從1 增加到10 000，KNN 查詢在2 維數據集上對TPN、TS 和H 階模型的性能。可以看出，隨著k值的增加，所有模型的KNN 查詢平均響應時間都在增加，因為隨著k值的增加，查詢空間也在增加。

圖13 KNN查詢的性能（節點數為4，D=2）Fig.13 Performance of KNN query（number of nodes is 4，D=2）

當然，這種平均響應時間的增加并不是指數級的，因為具有更大搜索空間的范圍查詢會使用更多的節點進行處理。將k 的值設置為10 000，節點數量從4 增加到16，得到的結果如圖14 所示。實驗結果表明，隨著集群中節點數量的增加，平均查詢響應時間會降低，因為更大的范圍查詢會與更多的子空間相交，從而涉及到更多的節點。在這兩個實驗中，TPN 和TS 模型的性能都比H 階設計的性能提高了4 到5 倍。在三維數據集上進行的一組實驗的結果如圖15 和圖16 所示。圖15顯示了參數k 的變化對4 個節點簇的影響，與MD-HBase 和H階設計進行對比，可以看出TPN 和TS模型的平均響應時間隨著參數k的增大而增大。然而，與二維相比，三維KNN查詢需要更多的時間來處理，因為執行范圍查詢的復雜性隨著維數的增加而增加。

圖14 KNN查詢性能（k=10 000，D=2）Fig.14 Performance of KNN query（k=10 000，D=2）

圖15 KNN查詢的性能（節點數為4，D=3）Fig.15 Performance of KNN query（number of nodes is 4，D=3）

圖16 KNN查詢性能（k=10 000，D=3）Fig.16 Performance of KNN query（k=10 000，D=3）

4 結語

本文提出并評估了一個面向云平臺上位置感知服務的多維數據分布和索引框架New-grid。New-grid是一個可伸縮的、完全分散的、獨立于平臺的索引框架，可以有效地處理點、范圍和KNN 查詢。New-grid首先在修改后的P-Grid覆蓋網絡中安排從云租用的節點，該網絡實際上以二叉樹結構劃分整個空間。其次，為了有效地存儲和檢索多維數據，利用基于Hilbert空間填充曲線的線性化技術將多維數據轉換為一維二進制鍵。這種技術允許我們根據對等點的路徑將鍵映射到它們，同時保留數據局部性。我們還設計并開發了算法來動態處理范圍和KNN 查詢，從而消除了創建和維護單獨索引表的限制。在Amazon EC2 上使用4、8 和16 個普通節點的集群進行了廣泛的實驗，結果表明，New-grid 的性能相比MD-Hbase更優。

在未來，我們希望通過提供以動態方式處理數據偏斜度的能力來擴展該框架，并支持更廣泛的多維查詢，包括skyline和spatial-join；還希望開發高效的子空間分裂算法來實現負載均衡，并開發高效的數據復制算法來提高New-grid 的容錯能力；同時還想評估P-Ring P2P網絡［21］，看看它是否能夠滿足我們模型的所有要求，或者如何進行相應的修改，以及它與P-Grid在性能上的比較。