基于HBase的多維索引查詢(xún)機(jī)制的優(yōu)化

徐江峰，譚玉龍

（鄭州大學(xué)信息工程學(xué)院，鄭州450001）

0 引言

隨著無(wú)線(xiàn)和移動(dòng)技術(shù)的進(jìn)展，對(duì)移動(dòng)性的需求日益增加，基于位置的服務(wù)（Location-Based Service，LBS）利用移動(dòng)設(shè)備的能力，通過(guò)移動(dòng)網(wǎng)絡(luò)提供用戶(hù)當(dāng)前的地理位置。它們?cè)试S移動(dòng)用戶(hù)搜索他們的環(huán)境，并使他們能夠立即訪(fǎng)問(wèn)個(gè)性化和本地化的內(nèi)容。目前，移動(dòng)用戶(hù)可以使用各種各樣的LBS，包括路由映射應(yīng)用程序、交互式城市指南、位置感知營(yíng)銷(xiāo)、對(duì)象跟蹤和監(jiān)控，以及基于鄰近［1］查找對(duì)象。LBS對(duì)底層支持平臺(tái)提出了廣泛的需求，包括對(duì)多維數(shù)據(jù)建模、處理數(shù)百萬(wàn)用戶(hù)的高速更新以及對(duì)大量數(shù)據(jù)進(jìn)行實(shí)時(shí)分析。

通過(guò)利用內(nèi)置的索引功能和豐富的查詢(xún)處理語(yǔ)言，傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)（Relational Database Management System，RDBMS）可以在多維數(shù)據(jù)上提供高效和快速的復(fù)雜查詢(xún)處理。這些索引功能是通過(guò)在關(guān)系存儲(chǔ)之上創(chuàng)建額外的索引層來(lái)提供的。例如，Oracle spatial 支持基于R-tree［2］和四叉樹(shù)［3］的索引。然而，這些集中的系統(tǒng)會(huì)產(chǎn)生單一的故障點(diǎn)，實(shí)現(xiàn)起來(lái)成本很高，而且隨著數(shù)據(jù)量和用戶(hù)數(shù)量的增長(zhǎng)，會(huì)遇到可伸縮性瓶頸。

分布式鍵值存儲(chǔ)成為一種提供彈性數(shù)據(jù)管理服務(wù)的新范式，可以根據(jù)不同應(yīng)用程序的需求進(jìn)行伸縮。當(dāng)前的鍵值存儲(chǔ)（BigTable［4］、HBase［5］和Cassandra［6］）被設(shè)計(jì)成高可用性、高容錯(cuò)性和保持高更新吞吐量支持?jǐn)?shù)百萬(wàn)用戶(hù)；但是，這些鍵值存儲(chǔ)只能處理單個(gè)屬性的高效精確匹配查詢(xún)，因?yàn)樗鼈內(nèi)狈υL(fǎng)問(wèn)多個(gè)屬性的內(nèi)置索引機(jī)制。對(duì)于查詢(xún)多個(gè)屬性，有兩個(gè)設(shè)計(jì)選項(xiàng)可用：第一種選擇是為每個(gè)屬性創(chuàng)建單獨(dú)的索引，但是，在管理大量數(shù)據(jù)時(shí)，創(chuàng)建多個(gè)索引表會(huì)給系統(tǒng)帶來(lái)巨大的額外負(fù)載；第二種選擇是使用MapReduce［7］范式的并行處理來(lái)掃描整個(gè)數(shù)據(jù)集，然而，LBS 需要實(shí)時(shí)的查詢(xún)處理，因此，對(duì)整個(gè)數(shù)據(jù)集進(jìn)行并行掃描并不是很有用。

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

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

2）利用基于Hilbert 空間填充曲線(xiàn)的線(xiàn)性化技術(shù)將多維數(shù)據(jù)轉(zhuǎn)換為一維數(shù)據(jù)，同時(shí)保持了數(shù)據(jù)的局部性。

3）提出一種利用改進(jìn)的P-Grid 前綴路由機(jī)制動(dòng)態(tài)處理線(xiàn)性化值上的點(diǎn)、范圍和KNN 查詢(xún)的算法，以消除創(chuàng)建和維護(hù)單獨(dú)索引表的開(kāi)銷(xiāo)。

4）在Amazon EC2 上進(jìn)行實(shí)驗(yàn)來(lái)測(cè)量insert 吞吐量以及點(diǎn)、范圍和KNN 查詢(xún)，以展示本文的框架相比MD-Hbase 的有效性。

1 相關(guān)技術(shù)

1.1 空間填充曲線(xiàn)的線(xiàn)性化

線(xiàn)性化是一種將多維屬性映射到一維空間上的降維方法?？臻g填充曲線(xiàn)是一種線(xiàn)性化技術(shù)，它是在不重疊的情況下，通過(guò)訪(fǎng)問(wèn)n 維超立方體中的每個(gè)點(diǎn)來(lái)構(gòu)造連續(xù)曲線(xiàn)。它們的優(yōu)勢(shì)是：在映射之后，在n 維空間中的相鄰點(diǎn)在一維空間中也保持鄰近。因此，空間填充曲線(xiàn)在圖像處理［10］、科學(xué)計(jì)算［11］、地理信息系統(tǒng)［12］等需要順序訪(fǎng)問(wèn)數(shù)據(jù)集的應(yīng)用中得到了廣泛的應(yīng)用。在New-grid 中，本文使用Hilbert 空間填充曲線(xiàn)索引底層一維鍵值存儲(chǔ)中的多維點(diǎn)，以提高查詢(xún)效率。

Hilbert 曲線(xiàn)是一種連續(xù)的空間填充曲線(xiàn)，它在多維數(shù)據(jù)點(diǎn)上產(chǎn)生順序排列。形式上，希爾伯特曲線(xiàn)是一個(gè)一對(duì)一的函數(shù)：

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

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

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

圖2 二維二階Hilbert曲線(xiàn)Fig.2 Two-dimensional second-order Hilbert curve

圖3 二維二階Hilbert曲線(xiàn)的樹(shù)表示Fig.3 Tree representation of two-dimensional second order Hilbert curve

1.2 P-Grid

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

圖4 P-Grid字典樹(shù)示例Fig.4 Example of P-Grid trie

P-Grid 采用一種完全分散并行的構(gòu)造算法，可以構(gòu)造出延時(shí)較短的覆蓋網(wǎng)絡(luò)。構(gòu)建過(guò)程嚴(yán)格基于本地對(duì)等交互，這種交互是通過(guò)在已有的非結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)上發(fā)起隨機(jī)遍歷來(lái)完成的。P-Grid 中的每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)路由表，該表存儲(chǔ)關(guān)于網(wǎng)絡(luò)中其他節(jié)點(diǎn)的路徑的信息。具體地說(shuō)，對(duì)于每個(gè)位置，它維護(hù)至少一個(gè)節(jié)點(diǎn)的地址，而且該節(jié)點(diǎn)的路徑在該位置上具有相反的位。該信息以[path(n)，F(xiàn)QDN(n)]的形式存儲(chǔ)在路由表中，其中FQDN(n)是節(jié)點(diǎn)的全限定域名。具體構(gòu)造算法見(jiàn)文獻(xiàn)［17］。

2 New-grid數(shù)據(jù)分布和索引框架

New-grid 索引框架由從云端租用的無(wú)共享節(jié)點(diǎn)集群組成。New-grid 的主要目標(biāo)是通過(guò)一個(gè)真正分散的P2P 架構(gòu)來(lái)支持LBS，該架構(gòu)可以相應(yīng)地進(jìn)行擴(kuò)展。New-grid通過(guò)采用簡(jiǎn)單的兩層架構(gòu)來(lái)實(shí)現(xiàn)。上層是基于P-Grid 的覆蓋網(wǎng)絡(luò)，該網(wǎng)絡(luò)負(fù)責(zé)路由查詢(xún)并為計(jì)算節(jié)點(diǎn)分配子空間，而下層則根據(jù)數(shù)據(jù)模型的類(lèi)型使用底層鍵值存儲(chǔ)（HBase）來(lái)維護(hù)數(shù)據(jù)。Newgrid 中的節(jié)點(diǎn)有兩個(gè)用途：一個(gè)節(jié)點(diǎn)是P-Grid 中的節(jié)點(diǎn)，因?yàn)樗S護(hù)其路由表中所有其他節(jié)點(diǎn)的子空間信息；另一個(gè)節(jié)點(diǎn)是HBase 集群的一部分，它存儲(chǔ)實(shí)際數(shù)據(jù)。New-grid 的體系結(jié)構(gòu)將查詢(xún)處理分為兩個(gè)階段：在第一階段中，通過(guò)搜索路由表來(lái)確定存儲(chǔ)子空間的節(jié)點(diǎn)。路由表包含所有其他節(jié)點(diǎn)的引用，這是通過(guò)將節(jié)點(diǎn)安排在一個(gè)虛擬二進(jìn)制樹(shù)結(jié)構(gòu)中來(lái)實(shí)現(xiàn)的。在第二階段，查詢(xún)被轉(zhuǎn)發(fā)到本地處理它的負(fù)責(zé)節(jié)點(diǎn)上。

New-grid 系統(tǒng)架構(gòu)如圖5 所示。本文使用自底向上的方法構(gòu)造New-grid，其中節(jié)點(diǎn)首先被安排在HBase 集群中，然后加入覆蓋網(wǎng)絡(luò)。建設(shè)是在一個(gè)離線(xiàn)的過(guò)程中完成，并有一個(gè)小的一次性設(shè)置成本。數(shù)據(jù)插入可以在任何節(jié)點(diǎn)上完成。為了插入數(shù)據(jù)，首先計(jì)算多維點(diǎn)的H值，并根據(jù)給出的數(shù)據(jù)模型進(jìn)行插入，底層使用Apache HBase［5］來(lái)存儲(chǔ)多維點(diǎn)的H 值，將其用作唯一的行鍵。

2.1 數(shù)據(jù)插入和點(diǎn)查詢(xún)

數(shù)據(jù)插入和點(diǎn)查詢(xún)可以通過(guò)使用P-Grid的搜索機(jī)制來(lái)執(zhí)行，將插入或查詢(xún)請(qǐng)求轉(zhuǎn)發(fā)到負(fù)責(zé)節(jié)點(diǎn)。本文的算法（算法1和算法2）利用鍵值存儲(chǔ)提供直接數(shù)據(jù)訪(fǎng)問(wèn)的能力，各自高效地插入數(shù)據(jù)和處理點(diǎn)查詢(xún)。在算法1 中，插入一個(gè)點(diǎn)，首先計(jì)算該點(diǎn)（第1）行）的二進(jìn)制H 值（rowkey）。然后，對(duì)于每個(gè)節(jié)點(diǎn)模型的表，插入操作分為兩個(gè)階段：在第一階段，搜索路由表ρ，找到名稱(chēng)為（FQDN）節(jié)點(diǎn)的路徑的最長(zhǎng)公共前綴行鍵（第2）行）。此模型將數(shù)據(jù)存儲(chǔ)在一個(gè)表中，該表的名稱(chēng)設(shè)置為節(jié)點(diǎn)的名稱(chēng)，此步驟足以找到負(fù)責(zé)存儲(chǔ)該點(diǎn)的表的名稱(chēng)。在第二階段，按照標(biāo)準(zhǔn)的insert 操作在表中插入rowkey（第3）行），對(duì)于表共享模型，可以很容易地在預(yù)定義的共享表中插入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系統(tǒng)架構(gòu)Fig.5 New-grid system architecture

算法2 是查詢(xún)處理算法，對(duì)于每個(gè)節(jié)點(diǎn)模型的表，查詢(xún)處理分為兩個(gè)階段。給定d 維點(diǎn)p=(p1，p2，…)，點(diǎn)查詢(xún)策略試圖識(shí)別與p 關(guān)聯(lián)的值v。為了處理查詢(xún)，首先計(jì)算該點(diǎn)的H 值來(lái)計(jì)算行鍵（第1）行）。在第一階段，搜索路由表ρ，找到名稱(chēng)為（FQDN）的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)路徑與rowkey是最長(zhǎng)的公共前綴（第2）行）。在第二個(gè)階段，通過(guò)檢索到v，在表上實(shí)現(xiàn)鍵查找操作。

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 范圍查詢(xún)處理

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

1）在第一階段中，將原始的范圍查詢(xún)劃分為更小的子查詢(xún)，每個(gè)子查詢(xún)區(qū)域與之相交的子空間都有一個(gè)子查詢(xún)，通過(guò)計(jì)算查詢(xún)區(qū)域內(nèi)每個(gè)子空間中點(diǎn)的最小H值來(lái)實(shí)現(xiàn)。將該點(diǎn)稱(chēng)為下一個(gè)匹配點(diǎn)，并將其計(jì)算為calculate-next-match（）的函數(shù)。

2）在第二階段中，根據(jù)P-Grid 的搜索機(jī)制處理每個(gè)子查詢(xún)，該搜索機(jī)制將子查詢(xún)轉(zhuǎn)發(fā)給路徑與子查詢(xún)的上下界相交的所有節(jié)點(diǎn)。

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

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

該算法迭代地確定在樹(shù)的任意節(jié)點(diǎn)上與當(dāng)前查詢(xún)區(qū)域相交的最小子空間。在每次迭代中，將丟棄一半的子空間，并沿著樹(shù)的正確分支下行，直到在葉級(jí)找到下一個(gè)匹配。同樣，這種下降是一個(gè)迭代過(guò)程，在每次迭代中，都用搜索子空間的邊界來(lái)限制用戶(hù)定義的搜索空間。

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查詢(xún)處理

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

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

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 上實(shí)現(xiàn)了New-grid，集群大小為4、8 和16個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都是EC2 的一個(gè)中型實(shí)例，由4 個(gè)虛擬內(nèi)核、15.7 GB 內(nèi)存、配置為1 TB 硬盤(pán)和Centos 6.4 OS 組成；節(jié)點(diǎn)通過(guò)1 GB 的網(wǎng)絡(luò)鏈路連接。數(shù)據(jù)存儲(chǔ)層使用Hadoop 1.2.1和HBase 0.94.10實(shí)現(xiàn)。點(diǎn)、范圍和KNN查詢(xún)的實(shí)驗(yàn)是在一個(gè)包含4 億個(gè)點(diǎn)的合成數(shù)據(jù)集上進(jìn)行的。該數(shù)據(jù)集是使用基于網(wǎng)絡(luò)的移動(dòng)對(duì)象生成器生成的，該生成器模擬了舊金山灣區(qū)地圖上40 000 個(gè)對(duì)象的移動(dòng)。每個(gè)對(duì)象移動(dòng)10 000步，并在連續(xù)的時(shí)間戳上報(bào)告其位置（經(jīng)度、緯度）。該數(shù)據(jù)集遵循一個(gè)傾斜分布，因?yàn)槟M器使用真實(shí)世界的公路網(wǎng)。本文運(yùn)行一個(gè)簡(jiǎn)單的MapReduce（MR）作業(yè)來(lái)計(jì)算數(shù)據(jù)集中點(diǎn)的最小值和最大值（區(qū)域邊界），并根據(jù)這些點(diǎn)的H 值的公共前綴設(shè)置節(jié)點(diǎn)的路徑。這有助于通過(guò)匹配預(yù)定義的子空間，使用行鍵在節(jié)點(diǎn)之間高效地分布數(shù)據(jù)集。行鍵將使用匹配的預(yù)定義子空間插入到正確的節(jié)點(diǎn)中。

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

3.1 插入的性能

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

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

3.2 點(diǎn)查詢(xún)和范圍查詢(xún)的性能

多維點(diǎn)查詢(xún)和范圍查詢(xún)是LBS 中最常見(jiàn)的查詢(xún)。Newgrid通過(guò)直接查詢(xún)HBase表來(lái)處理點(diǎn)查詢(xún)。另一方面，范圍查詢(xún)的處理方法是首先將其劃分為多個(gè)子查詢(xún)，然后使用覆蓋層將每個(gè)子查詢(xún)同時(shí)轉(zhuǎn)發(fā)到負(fù)責(zé)節(jié)點(diǎn)。圖8 顯示了改變節(jié)點(diǎn)數(shù)量會(huì)對(duì)TPN、TS和H階模型的三維點(diǎn)查詢(xún)性能產(chǎn)生的影響。當(dāng)增加節(jié)點(diǎn)數(shù)量時(shí)，所有模型的平均響應(yīng)時(shí)間都增加了，尤其是TPN 模型。TS 和H 階模型的響應(yīng)時(shí)間相同，因?yàn)樗鼈兌际褂孟嗤牟樵?xún)策略；但是，TPN 模型的響應(yīng)時(shí)間比其他模型要長(zhǎng)，這是因?yàn)樾枰ㄟ^(guò)搜索路由表并找到相關(guān)節(jié)點(diǎn)的成本較高。

圖8 點(diǎn)查詢(xún)性能(D=3)Fig.8 Performance of point query(D=3)

圖9 和圖10 分別顯示了不同選擇性和節(jié)點(diǎn)數(shù)量的TPN、TS、H 階和MR 模型的二維范圍查詢(xún)的性能。隨著節(jié)點(diǎn)數(shù)量的增加，TPN、TS 和H 階模型的查詢(xún)響應(yīng)時(shí)間幾乎線(xiàn)性增加（圖9）；相反，MR 在對(duì)數(shù)據(jù)集進(jìn)行全掃描以執(zhí)行查詢(xún)時(shí)，其響應(yīng)時(shí)間是恒定的，因此其響應(yīng)時(shí)間與選擇性無(wú)關(guān)。TS 和TPN模型的性能優(yōu)于其他模型，特別是對(duì)于選擇性較大的查詢(xún)，由于搜索區(qū)域較大的范圍查詢(xún)將與更多的子空間相交，從而產(chǎn)生多個(gè)子查詢(xún)。從圖10 中可以看出增加節(jié)點(diǎn)數(shù)量和同時(shí)保持10%的選擇性對(duì)平均范圍查詢(xún)響應(yīng)時(shí)間的影響。隨著節(jié)點(diǎn)數(shù)量的增加，平均查詢(xún)響應(yīng)時(shí)間會(huì)減少，因?yàn)楣?jié)點(diǎn)數(shù)量的增加會(huì)導(dǎo)致數(shù)據(jù)的有效分布。此外，TPN 模型的性能優(yōu)于TS 模型，因?yàn)門(mén)PN 模型將所有數(shù)據(jù)本地存儲(chǔ)在節(jié)點(diǎn)上，而TS 模型將數(shù)據(jù)分布在集群中。

圖9 范圍查詢(xún)的性能(節(jié)點(diǎn)數(shù)為4，D=2)Fig.9 Performance of range query（number of nodes is 4，D=2）

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

在三維數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)的結(jié)果如圖11 和圖12 所示。圖11顯示了在4個(gè)節(jié)點(diǎn)集群上作為選擇性函數(shù)三維范圍查詢(xún)的性能。當(dāng)增加選擇性時(shí)，TPN 和TS 模型的平均查詢(xún)響應(yīng)時(shí)間會(huì)增加。在本實(shí)驗(yàn)中，除了H 階模型和MR 模型外，還將TPN 和TS 模型的結(jié)果與MD-HBase 的TPB 和TS 數(shù)據(jù)模型進(jìn)行了比較。比較結(jié)果表明，即使在選擇性較大的情況下，TPN和TS 模型的性能也較好。這是因?yàn)?，在MD-HBase 中使用額外的索引層來(lái)修剪結(jié)果集，而在本文的方案中沒(méi)有這樣的開(kāi)銷(xiāo)。

圖11 范圍查詢(xún)的性能（節(jié)點(diǎn)數(shù)為4，D=3）Fig.11 Performance of range query（number of nodes is 4，D=3）

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

3.3 KNN查詢(xún)的性能

New-grid 迭代處理k 個(gè)最近鄰居（KNN）查詢(xún)。首先利用式（1）估計(jì)查詢(xún)點(diǎn)與其第k 個(gè)近鄰之間的距離，即初始搜索半徑；然后，執(zhí)行范圍搜索來(lái)檢索k個(gè)結(jié)果，如果k個(gè)結(jié)果沒(méi)有返回，通過(guò)增加搜索空間并再次執(zhí)行范圍搜索。圖13 顯示了通過(guò)在4 個(gè)節(jié)點(diǎn)集群中將k 的值從1 增加到10 000，KNN 查詢(xún)?cè)? 維數(shù)據(jù)集上對(duì)TPN、TS 和H 階模型的性能?？梢钥闯?，隨著k值的增加，所有模型的KNN 查詢(xún)平均響應(yīng)時(shí)間都在增加，因?yàn)殡S著k值的增加，查詢(xún)空間也在增加。

圖13 KNN查詢(xún)的性能（節(jié)點(diǎn)數(shù)為4，D=2）Fig.13 Performance of KNN query（number of nodes is 4，D=2）

當(dāng)然，這種平均響應(yīng)時(shí)間的增加并不是指數(shù)級(jí)的，因?yàn)榫哂懈笏阉骺臻g的范圍查詢(xún)會(huì)使用更多的節(jié)點(diǎn)進(jìn)行處理。將k 的值設(shè)置為10 000，節(jié)點(diǎn)數(shù)量從4 增加到16，得到的結(jié)果如圖14 所示。實(shí)驗(yàn)結(jié)果表明，隨著集群中節(jié)點(diǎn)數(shù)量的增加，平均查詢(xún)響應(yīng)時(shí)間會(huì)降低，因?yàn)楦蟮姆秶樵?xún)會(huì)與更多的子空間相交，從而涉及到更多的節(jié)點(diǎn)。在這兩個(gè)實(shí)驗(yàn)中，TPN 和TS 模型的性能都比H 階設(shè)計(jì)的性能提高了4 到5 倍。在三維數(shù)據(jù)集上進(jìn)行的一組實(shí)驗(yàn)的結(jié)果如圖15 和圖16 所示。圖15顯示了參數(shù)k 的變化對(duì)4 個(gè)節(jié)點(diǎn)簇的影響，與MD-HBase 和H階設(shè)計(jì)進(jìn)行對(duì)比，可以看出TPN 和TS模型的平均響應(yīng)時(shí)間隨著參數(shù)k的增大而增大。然而，與二維相比，三維KNN查詢(xún)需要更多的時(shí)間來(lái)處理，因?yàn)閳?zhí)行范圍查詢(xún)的復(fù)雜性隨著維數(shù)的增加而增加。

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

圖15 KNN查詢(xún)的性能（節(jié)點(diǎn)數(shù)為4，D=3）Fig.15 Performance of KNN query（number of nodes is 4，D=3）

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

4 結(jié)語(yǔ)

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

在未來(lái)，我們希望通過(guò)提供以動(dòng)態(tài)方式處理數(shù)據(jù)偏斜度的能力來(lái)擴(kuò)展該框架，并支持更廣泛的多維查詢(xún)，包括skyline和spatial-join；還希望開(kāi)發(fā)高效的子空間分裂算法來(lái)實(shí)現(xiàn)負(fù)載均衡，并開(kāi)發(fā)高效的數(shù)據(jù)復(fù)制算法來(lái)提高New-grid 的容錯(cuò)能力；同時(shí)還想評(píng)估P-Ring P2P網(wǎng)絡(luò)［21］，看看它是否能夠滿(mǎn)足我們模型的所有要求，或者如何進(jìn)行相應(yīng)的修改，以及它與P-Grid在性能上的比較。