基于Hadoop的分布式SQL數(shù)據(jù)庫索引設計與實踐?

陳 紅

（昌吉職業(yè)技術(shù)學院 昌吉 831100）

1 引言

隨著數(shù)據(jù)規(guī)模的增長，傳統(tǒng)的SQL數(shù)據(jù)庫管理模式已經(jīng)無法有效地管理海量的數(shù)據(jù)庫數(shù)據(jù)［1］。隨著云計算等技術(shù)在信息系統(tǒng)等技術(shù)領(lǐng)域的應用，分布式系統(tǒng)為處理海量數(shù)據(jù)提供了一個全新的方案［2］，如何將分布式系統(tǒng)應用到數(shù)據(jù)管理當中已經(jīng)成為了一個研究的熱點。SQL數(shù)據(jù)庫索引是海量數(shù)據(jù)管理與檢索的關(guān)鍵問題。樹形索引［3］是當前流行的SQL數(shù)據(jù)庫索引結(jié)構(gòu)，其中以R樹家族［4］最為突出。隨著分布式系統(tǒng)研究的深入，分布式索引逐漸成為SQL數(shù)據(jù)庫索引的研究熱點［5］，文獻［6～7］研究了MR-tree、R樹和多級R-tree的并行化實現(xiàn)，文獻［8］對四叉樹進行面向列式存儲擴展改進，文獻［9］將VoR-Tree、雙層倒排網(wǎng)格索引、SQL數(shù)據(jù)庫的k近鄰查詢與MapReduce編程模型相結(jié)合進行分布式改造。

針對海量數(shù)據(jù)的索引需求，本文將SQL數(shù)據(jù)庫索引與云計算技術(shù)相結(jié)合，提出了基于Hadoop平臺的分布式SQL數(shù)據(jù)庫索引，并從架構(gòu)設計、數(shù)據(jù)劃分和局部索引和全局索引構(gòu)建等方面出發(fā)，在Hadoop下設計并實現(xiàn)了分布式SQL數(shù)據(jù)庫索引。同時。最后本文搭建了Hadoop環(huán)境并進行實驗證明了改進后的算法可以有效減少數(shù)據(jù)檢索時間，提高整體性能，高并發(fā)、低成本、高可靠的完成數(shù)據(jù)檢索任務。

2 索引結(jié)構(gòu)設計

本文設計的基于HDFS的分布式SQL數(shù)據(jù)庫索引采用分層的分布式索引結(jié)構(gòu)，分層式分布式索引結(jié)構(gòu)首先將數(shù)據(jù)庫數(shù)據(jù)按照SQL數(shù)據(jù)庫分布進行劃分，將SQL數(shù)據(jù)庫上臨近的數(shù)據(jù)劃分到一個分區(qū)當中，再對每一個分區(qū)當中的數(shù)據(jù)構(gòu)建一個局部索引，并將局部索引以及該分區(qū)數(shù)據(jù)存儲到數(shù)據(jù)節(jié)點當中。當所有數(shù)據(jù)劃分完畢并且所有局部索引構(gòu)建完成以后，在主節(jié)點中依據(jù)各個局部索引的根節(jié)點構(gòu)建一個全局索引，存在主節(jié)點當中。由于主節(jié)點中的全局索引只保存了局部索引的根節(jié)點的信息，全局索引的大小得到了限制，減輕了主節(jié)點存儲與計算的負擔［10］，同時，由于全局索引的大小較小，在程序運行時可以將全局索引一次性加載到內(nèi)存中，對全局索引進行檢索時避免了磁盤的IO，提升了數(shù)據(jù)檢索效率［11］。分層式SQL數(shù)據(jù)庫索引結(jié)構(gòu)如圖1所示。

圖1 分層式分布式索引

本文索引由全局索引、局部索引、數(shù)據(jù)分片三層構(gòu)成，索引構(gòu)建主要分為如下三個步驟：

全局索引：全局索引是指針對整個數(shù)據(jù)集建立一個統(tǒng)一的索引，每一個索引指向一個節(jié)點或一個數(shù)據(jù)塊，實現(xiàn)算法相對比較簡單。全局索引可以看做是局部索引的緩存，基于全局索引的查詢操作，只需要訪問相關(guān)的節(jié)點或數(shù)據(jù)塊即可，能夠減少數(shù)據(jù)讀取時間，提高檢索效率。

局部索引：局部索引是指針對每一個數(shù)據(jù)分區(qū)所建立的獨立索引，數(shù)據(jù)塊之間的檢索也相互獨立，具有良好的容錯能力；同時也有利于數(shù)據(jù)塊的局部更新和索引重建。

數(shù)據(jù)分片：文件上傳到HDFS上會被分成若干文件塊并存儲到Datanode上。每個文件塊的大小應小于HDFS文件塊的大小，如果文件塊的大小大于HDFS文件塊大小，那么單個數(shù)據(jù)分片就可能會被存到多個不同的Datanode當中，這樣導致在進行檢索時需要通過網(wǎng)絡從不同的Datanode上獲取數(shù)據(jù)，這樣會降低數(shù)據(jù)檢索的效率。因此，應控制數(shù)據(jù)分片與其對應的索引大小和小于HDFS的文件塊大小。

數(shù)據(jù)集劃分成若干個數(shù)據(jù)分片：

局部索引構(gòu)建：根據(jù)每一個數(shù)據(jù)分片的數(shù)據(jù)，構(gòu)建局部索引，并將構(gòu)建的索引存儲到對應的Datanode中。

全局索引構(gòu)建：根據(jù)數(shù)據(jù)劃分以及局部索引構(gòu)建的結(jié)果，在Namenode上構(gòu)建一個全局索引。

3 SQL數(shù)據(jù)庫劃分

其中，S為待劃分數(shù)據(jù)庫數(shù)據(jù)大小，一般是128M，α表示膨脹系數(shù)，膨脹系數(shù)主要的考慮因素為數(shù)據(jù)庫數(shù)據(jù)與其局部索引的大小差距，一般采用0.2～

本文基于海量SQL數(shù)據(jù)庫數(shù)量，直接建立索引將會使索引太龐大，嚴重影響數(shù)據(jù)檢索效率［12］，需要將整個數(shù)據(jù)庫數(shù)據(jù)按照一定規(guī)則進行劃分后建立局部索引，這樣可以避免上述狀況，選取一個合適的SQL數(shù)據(jù)庫劃分方案十分重要。

3.1 SQL數(shù)據(jù)庫劃分規(guī)則

SQL數(shù)據(jù)庫劃分是構(gòu)造分布式索引的關(guān)鍵環(huán)節(jié)，劃分規(guī)則的好壞直接決定了索引的檢索效率，在進行數(shù)據(jù)劃分時，應盡量遵循如下兩個原則：

1）生成若干個大小基本相等的分區(qū)，且分區(qū)大小不超過HDFS數(shù)據(jù)塊大小。如果劃分分區(qū)超過HDFS數(shù)據(jù)塊大小可能導致該分區(qū)數(shù)據(jù)存儲到不同的HDFS上，影響查詢效率。如果分區(qū)大小差距過大，部分分區(qū)數(shù)據(jù)量太少，會導致索引節(jié)點數(shù)增加，索引層數(shù)高度增加，同時會導致熱區(qū)問題，影響查詢效率。

2）生成的數(shù)據(jù)分區(qū)要保證SQL數(shù)據(jù)庫局部性。在進行范圍查詢時，應當盡量減少IO操作，減少讀寫磁盤的次數(shù)。如當e1和e2SQL數(shù)據(jù)庫上距離較近，則e1和e2應當分配到同一個分區(qū)當中。劃分結(jié)果以及其局部索引需要存儲到同一個HDFS塊中，所以劃分的數(shù)據(jù)分區(qū)以及該分區(qū)的局部索引大小之和應小于HDFS塊大小。確定劃分區(qū)域數(shù)量為0.3即可［13］。

本文采用STR樹葉節(jié)點生成算法［14］對數(shù)據(jù)進行劃分，圖2為STR樹葉節(jié)點劃分方式，假設有N個數(shù)據(jù)，首先將數(shù)據(jù)按照x坐標值的大小進行排序，平均生成[n]個分組，其中n為分區(qū)數(shù)量，這樣生成的分組中每個分組至少包含[N/n]個數(shù)據(jù)。然后在得到的分組結(jié)果中以y的坐標值大小進行排序，每[N/n]個數(shù)據(jù)被劃為一組，生成n個分組。如果數(shù)據(jù)結(jié)構(gòu)為多邊形，則按照其最小外包矩形中心點進行排序。根據(jù)以上算法可以得知，如果數(shù)據(jù)均勻分布在SQL數(shù)據(jù)庫區(qū)域上，那么這種劃分方式與網(wǎng)格分割［15］效果類似，但是如果數(shù)據(jù)分布極不均勻，那么這種劃分方式能夠更好地對數(shù)據(jù)進行劃分。

圖2 STR葉子節(jié)點分割示意圖

STR葉節(jié)點劃分方式依據(jù)數(shù)據(jù)的SQL數(shù)據(jù)庫臨近，對數(shù)據(jù)進行了聚類處理［16］，能夠有效地應對數(shù)據(jù)分布不均勻的情況，但是在劃分過程中，需要進行多次排序操作，處理海量數(shù)據(jù)的效率不高，因此，考慮首先對數(shù)據(jù)進行采樣處理，然后采用Ma?pReduce進行并行劃分，具體實現(xiàn)過程將在下一節(jié)詳細描述。

3.2 并行數(shù)據(jù)劃分

本文首先對SQL數(shù)據(jù)庫中的數(shù)據(jù)進行充足隨機采樣，因為足夠的采樣數(shù)據(jù)可以代表整體數(shù)據(jù)的分布趨勢及分布規(guī)律，通過MapReduce對任意采樣的數(shù)據(jù)塊實施數(shù)據(jù)排序，采樣的數(shù)據(jù)塊進行X排序后，將X分組中x坐標的最大值與下個相鄰分組的X最小值的平均值作為兩個分組直接的界線值，全部分組中的第一個分組與最后一個分組的界線值分別選擇起始X值與結(jié)束X值；同理可得到y(tǒng)坐標的界線值。最終得到一個劃分函數(shù)func確定一個分區(qū)

4 基于改進R樹的分布式索引構(gòu)建及存儲

通過數(shù)據(jù)劃分得到了劃分后的數(shù)據(jù)分區(qū)，將根據(jù)每一個數(shù)據(jù)分片的結(jié)果單獨構(gòu)建R樹索引，保證所有的數(shù)據(jù)都在索引范圍內(nèi)，采用一種改進的R樹生成方式構(gòu)建局部索引，提升在分區(qū)中查詢數(shù)據(jù)的效率。

4.1 局部索引構(gòu)建與存儲

假設經(jīng)過數(shù)據(jù)劃分的數(shù)據(jù)塊中有k個數(shù)據(jù)，相應則在數(shù)據(jù)劃分過程中建立了k個MBR，在本節(jié)使用一種改進的R樹生成算法Reduce過程中構(gòu)建數(shù)據(jù)的局部R樹索引。在map的階段已經(jīng)獲取了數(shù)據(jù)分片中所有數(shù)據(jù)的MBR，采用動態(tài)插入MBR的方式構(gòu)建R樹。在插入數(shù)據(jù)過程中，如果向一個飽和節(jié)點中插入數(shù)據(jù)，首先檢查溢出節(jié)點表中是否包含此節(jié)點，如果已經(jīng)包含且該節(jié)點的溢出節(jié)點沒有飽和則直接插入數(shù)據(jù)即可，如果溢出節(jié)點表中尚未包含該節(jié)點，則在溢出節(jié)點表中為該節(jié)點創(chuàng)建一個溢出節(jié)點，并向溢出節(jié)點中插入數(shù)據(jù)。若一個節(jié)點的溢出節(jié)點也飽和，則對該節(jié)點及其溢出節(jié)點進行歸并分裂操作，寫回到R樹種。當所有對象都訪問完，如果溢出節(jié)點表中還有數(shù)據(jù)，則進行一次強制寫回操作，最后將生成的R樹索引及分區(qū)數(shù)據(jù)序列化到HDFS上。

圖3 局部索引存儲格式

在進行數(shù)據(jù)劃分時，已經(jīng)在每個數(shù)據(jù)分區(qū)中為局部索引預留了SQL數(shù)據(jù)庫，所以可以直接將局部索引和數(shù)據(jù)存儲在同一個HDFS塊中。數(shù)據(jù)及其局部索引的存儲格式如圖3所示，分為索引元數(shù)據(jù)部分、局部索引部分和數(shù)據(jù)部分。其中，第一部分為樹結(jié)構(gòu)區(qū)存儲R樹的結(jié)構(gòu)信息，包括索引的大小即樹結(jié)點數(shù)據(jù)區(qū)域的大小、樹的高度、樹中每個結(jié)點的容量以及SQL數(shù)據(jù)庫對象的個數(shù)。根據(jù)樹的高度以及結(jié)點容量可以計算出結(jié)點對象的個數(shù)。中間區(qū)域為樹結(jié)點數(shù)據(jù)區(qū)域，該區(qū)域存放的是樹結(jié)點信息，每個結(jié)點對象存放其子節(jié)點的信息（子節(jié)點的位置指針及子節(jié)點的MBR），最后一個區(qū)域為數(shù)據(jù)區(qū)域記錄每一個屬于該區(qū)域的數(shù)據(jù)。在信息查詢時一般不會加載數(shù)據(jù)，而是只把R樹的結(jié)構(gòu)信息加載到內(nèi)存中，當只需要進一步查詢時才加載具體的數(shù)據(jù)。

4.2 全局索引構(gòu)建與存儲

本文的設計思想是用戶在每一次對數(shù)據(jù)的操作都會先經(jīng)過全局索引的檢索，然后根據(jù)全局索引的檢索情況在對局部索引進行檢索。本節(jié)將介紹全局索引的構(gòu)建和存儲。由于全局索引使用的頻率高且數(shù)據(jù)量很小，因此，全局索引構(gòu)建完成后可以將其常駐于Namenode節(jié)點的內(nèi)存中。

全局索引的存儲結(jié)構(gòu)與局部索引類似，具有樹結(jié)構(gòu)信息以及樹結(jié)點信息兩個部分組成，不同之處為在全局索引的樹葉子結(jié)點數(shù)據(jù)中存放的不是具體的數(shù)據(jù)的指針與外包矩形，而是存放的相應的HDFS文件路徑以及局部索引根結(jié)點的MBR信息。從而實現(xiàn)全局索引與局部索引的關(guān)聯(lián)。全局索引的構(gòu)建在所有局部索引構(gòu)建完成之后進行。由于分區(qū)數(shù)量不會過多。因此全局索引的大小不會過大，不需要分布式執(zhí)行。全局索引采用常規(guī)的R樹生成方式即可。

5 實驗分析

5.1 實驗環(huán)境

本實驗借助虛擬機搭建了具有6個節(jié)點的Ha?doop集群，每個節(jié)點分配4G內(nèi)存和一定SQL數(shù)據(jù)庫的硬盤，節(jié)點上運行Ununtu14.0操作系統(tǒng)以及Hadoop2.6.4，并支持Linux下Java8的操作環(huán)境Ha?doop集群中包括1個Master和5個Slave，Master主要負責數(shù)據(jù)的整體調(diào)度，Slave作為具體的執(zhí)行者負責存儲數(shù)據(jù)和處理數(shù)據(jù)。

5.2 區(qū)域查詢實驗

由于本文索引采用多級分布式索引結(jié)構(gòu)，因此在進行區(qū)域查詢時與普通單機SQL數(shù)據(jù)庫索引查詢操作不同。在區(qū)域查詢操作中首先通過全局索引將SQL數(shù)據(jù)庫查詢操作劃分到不同的數(shù)據(jù)節(jié)點中進行查詢，最終將數(shù)據(jù)節(jié)點中查詢到的數(shù)據(jù)聚合為最終的數(shù)據(jù)。

實驗使用谷歌地圖數(shù)據(jù)集［17］，大小約為9.3G，查詢范圍由0.0001%～1%變化，分別選取工作節(jié)點數(shù)目為2、4、6和單機狀態(tài)，測試節(jié)點個數(shù)的變化對查詢時間的影響。實驗數(shù)據(jù)如圖4所示。

圖4 區(qū)域查詢實驗結(jié)果

由圖4可得出，當查詢區(qū)域特別小時，單機狀態(tài)下查詢所需時間并沒有明顯劣勢，但是隨著查詢區(qū)域的擴大，查詢操作耗時呈指數(shù)型增長，這是因為單臺計算機本身性能有限。通過對比2、4、6個工作節(jié)點的查詢耗時，可看出相同數(shù)據(jù)量、相同查詢區(qū)域的情況下，數(shù)據(jù)查詢時間隨著工作節(jié)點的增多而減少，這是因為具體的查詢操作被分配到了數(shù)據(jù)節(jié)點中執(zhí)行，提高了檢索性能。由此得出，本文設計的分布式SQL數(shù)據(jù)庫索引提高了檢索性能，適用于處理海量數(shù)據(jù)。

5.3 k近鄰查詢實驗

k近鄰查詢的基本思想是，給定一個參考點的坐標，查詢離該點最近的k個數(shù)據(jù)。基于本文索引的k臨近查詢操作共分為3個步驟分別為全局knn操作，局部knn操作，局部knn結(jié)果檢查合并。其中全局knn操作由于計算量較小在Master節(jié)點執(zhí)行即可。局部knn操作和檢查在Map階執(zhí)行。結(jié)果合并階段在Reduce中執(zhí)行。

實驗同樣使用谷歌地圖數(shù)據(jù)集，大小約為9.3G，n的范圍從1～10000變化，實驗隨機選取若干點進行多次實驗，取最終的平均值，實驗分別選取工作節(jié)點數(shù)目為2、4、6和單機狀態(tài)，測試節(jié)點個數(shù)的變化對查詢時間的影響。實驗數(shù)據(jù)如圖5所示。

如圖5所示在k近鄰查詢實驗中隨著k值的增加，查詢耗時也在增加。這是因為k值越大，需要檢索的范圍越大，查詢操作耗費的時間也就越多，并且耗時增幅越明顯。這是由于在k值比較小時，集群并未發(fā)揮全部性能。因此小幅度增大k值，查詢所需時間增長幅度較小。然而當k值增大到一定程度，集群已經(jīng)發(fā)揮全部性能，此時繼續(xù)增長k值，查詢操作耗時就會出現(xiàn)線性增長的狀況。當k值較大時k近鄰查詢所需時間隨著工作節(jié)點數(shù)量的增加而減小，而當k值較小時，查詢操作的耗時幾乎不受節(jié)點數(shù)量的影響。這證實了n值較小時，k近鄰查詢只在比較少的節(jié)點中進行。而當k值較大時，k近鄰查詢將在集群所有節(jié)點中并行執(zhí)行。

圖5 k近鄰查詢實驗結(jié)果

6 結(jié)語

由于傳統(tǒng)的單機SQL數(shù)據(jù)庫索引技術(shù)面對大規(guī)模數(shù)據(jù)時計算能力不足，索引效率低，因此本文還將SQL數(shù)據(jù)庫索引技術(shù)與云計算技術(shù)相結(jié)合，提出了基于Hadoop平臺的分布式SQL數(shù)據(jù)庫索引。本文從索引結(jié)構(gòu)設計、數(shù)據(jù)劃分、局部和全局索引構(gòu)建和存儲等方面，詳細闡述了分布式SQL數(shù)據(jù)庫索引的實現(xiàn)，最后搭建Hadoop平臺進行了測試。在今后的研究工作中，重點會放在對R樹算法更好的優(yōu)化過程中。同時，本文主要是針對二維數(shù)據(jù)上的研究，日后的研究將不僅僅局限在二維數(shù)據(jù)上，將研究的目光擴展到更高維上。

［1］賀瑤，王文慶，薛飛.基于云計算的海量數(shù)據(jù)挖掘研究［J］. 計算機技術(shù)與發(fā)展，2013，23（02）：69-72.

［2］曲家朋，廖海.海量文件存儲技術(shù)研究［J］.機電工程技術(shù)，2016（08）：359-362.

［3］史曉楠，徐瀾，徐丹丹，等.一種改進的基于Hash算法及概率的k-mer索引方法［J］.通信電源技術(shù)，2017，34（03）：70-72，74.

［4］邵華，江南，胡斌，等.利用GPU的R樹細粒度并行STR方法批量構(gòu)建［J］.武漢大學學報（信息科學版），2014，39（09）：1068-1073.

［5］翁海星，宮學慶，朱燕超，等.集群環(huán)境下分布式索引的實現(xiàn)［J］. 計算機應用，2016，36（01）：1-7+12.

［6］劉義，景寧，陳犖，等.MapReduce框架下基于R-樹的k-近鄰連接算 法［J］. 軟 件學報，2013，24（08）：1836-1851.

［7］劉義，陳犖，景寧，等.基于R-樹索引的Map-Reduce空間連接聚集操作［J］.國防科技大學學報，2013，35（01）：136-141.

［8］楊建思.一種四叉樹與KD樹結(jié)合的海量機載LiDAR數(shù)據(jù)組織管理方法［J］.武漢大學學報（信息科學版），2014，39（08）：918-922.

［9］楊文奇，劉杰，陳飛輪.基于MapReduce的并行VoR-Tree索引［J］. 地理空間信息，2013，11（06）：109-111.

［10］陳潤健，王金鳳.并行計算和稀疏存儲在模糊積分上的應用［J］. 計算機應用研究，2017（01）：1-9.

［11］趙輝，楊樹強，陳志坤，等.基于MapReduce模型的范圍查詢分析優(yōu)化技術(shù)研究［J］.計算機研究與發(fā)展，2014，51（03）：606-617.

［12］杜朝暉，朱文耀.云存儲中利用屬性基加密技術(shù)的安全數(shù)據(jù)檢索方案［J］.計算機應用研究，2016，33（03）：860-865.

［13］王蛟龍，周潔，高慧，等.基于局部環(huán)境形狀特征識別的移動機器人避障方法［J］.信息與控制，2015，44（01）：91-98.

［14］昌春艷，王沁，田錕，等.優(yōu)化STR模型的實證研究［J］.武漢理工大學學報（信息與管理工程版），2013，35（04）：565-569.

［15］施逸飛，熊岳山，謝智歌，等.基于多核學習的快速網(wǎng)格分割算法［J］.計算機輔助設計與圖形學學報，2015，27（11）：2031-2038.

［16］黃良韜，趙志誠，趙亞群.基于隨機森林的密碼體制分層識別方案［J］. 計算機學報，2017（07）：1-19.

［17］李艷霞，劉學，黨壽江，等.網(wǎng)管系統(tǒng)中基于谷歌地圖的拓撲可視化實現(xiàn)［J］.計算機工程與設計，2013，34（02）：681-685.