基于Hadoop的空間科學(xué)大數(shù)據(jù)的區(qū)域檢索算法

王廣鈺，李英玉

（1.中國(guó)科學(xué)院大學(xué)北京100190；2.中國(guó)科學(xué)院國(guó)家空間科學(xué)中心北京100190）

我國(guó)天基信息基礎(chǔ)設(shè)施的高速發(fā)展使得探測(cè)到的空間科學(xué)數(shù)據(jù)呈現(xiàn)出海量化、多源化等特征，現(xiàn)階段對(duì)空間科學(xué)大數(shù)據(jù)的組織方式采用的仍是基于傳統(tǒng)數(shù)據(jù)庫(kù)的單機(jī)集中式處理模式，這種模式的數(shù)據(jù)查詢時(shí)間過(guò)長(zhǎng)。國(guó)內(nèi)外對(duì)時(shí)空數(shù)據(jù)[1-2]的組織方法的研究成果可分為3類：1）將時(shí)間作為2D位置信息的補(bǔ)充維：THEODORIDIS Y等人提出的3DR-tree[3-5]；2）重疊和多版本結(jié)構(gòu)[6]：TAO Y，PAPADIAS D等人提出 MV3R-tree[7]；3）面向軌跡[8-10]：Elias Frentzos提出的FNRB-tree[11-12]。上述3種組織方式是基于二維空間數(shù)據(jù)開(kāi)發(fā)的索引結(jié)構(gòu)，不支持對(duì)四維時(shí)空數(shù)據(jù)的檢索，并且只適用于單機(jī)環(huán)境下。用Hadoop處理空間數(shù)據(jù)的研究也都是基于二維空間數(shù)據(jù)，例如HQ-Tree[13]和 M-Quadtree[14]和 Spatial Hbase[15]。

因此，文中基于提出了分布式區(qū)域檢索算法，并基于Hadoop開(kāi)發(fā)了NSSC-Hadoop分布式系統(tǒng)框架，通過(guò)多組實(shí)驗(yàn)驗(yàn)證了算法的高效性。

1 分布式區(qū)域檢索算法

區(qū)域檢索算法是利用建立的時(shí)空索引結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行索引，通過(guò)時(shí)間區(qū)域檢索算法和空間網(wǎng)格檢索算法快速計(jì)算出指定時(shí)間范圍內(nèi)的空間區(qū)域所包含的網(wǎng)格，完成對(duì)時(shí)空數(shù)據(jù)的查詢。

1.1 四維空間科學(xué)數(shù)據(jù)的索引方法

采用時(shí)間優(yōu)先的存儲(chǔ)策略，按照KTS的存儲(chǔ)結(jié)構(gòu)將原始數(shù)據(jù)文件存儲(chǔ)在分布式文件系（Hadoop Data Filesystem，HDFS）中，數(shù)據(jù)處理步驟如下：

1）原始數(shù)據(jù)文件根據(jù)數(shù)據(jù)源信息分組存儲(chǔ)，并以數(shù)據(jù)源信息命名。

2）按照數(shù)據(jù)文件所在的時(shí)間域?qū)?shù)據(jù)分區(qū)存儲(chǔ)，并以時(shí)間域命名。

3）將每個(gè)時(shí)間范圍下的數(shù)據(jù)按照數(shù)據(jù)塊大小對(duì)文件進(jìn)行物理分塊存儲(chǔ)。最后對(duì)文件塊中的數(shù)據(jù)建立空間索引結(jié)構(gòu)。

本文在傳統(tǒng)空間剖分思想的基礎(chǔ)上，結(jié)合Hadoop的特點(diǎn)，提出了一種基于立方體的Block-Grid三維網(wǎng)格剖分方法。

基于立方體的Block-Grid三維網(wǎng)格剖分方法的過(guò)程包括3個(gè)階段：

1）分區(qū)：即將輸入文件劃分成若干個(gè)小分區(qū)。小分區(qū)需要滿足3個(gè)條件：①匹配數(shù)據(jù)塊大小；②空間鄰近；③負(fù)載均衡。分區(qū)步驟如下：

①確定分區(qū)個(gè)數(shù)：計(jì)算出所有輸入文件的分區(qū)個(gè)數(shù)，計(jì)算方法如下：

S表示輸入文件大小，B是HDFS中數(shù)據(jù)塊大小為128 MB，α是開(kāi)銷比，默認(rèn)等于0.2。

②確定分區(qū)邊界：計(jì)算每個(gè)小分區(qū)覆蓋的立方體網(wǎng)格區(qū)域，均勻計(jì)算網(wǎng)格邊界，計(jì)算方法如下：

剖分結(jié)果如圖1所示。

圖1 立方體分割

物理分區(qū)：根據(jù)第二步中確定的分區(qū)邊界對(duì)輸入文件物理分區(qū)，給每個(gè)數(shù)據(jù)記錄r唯一指定一個(gè)分區(qū)p，格式為＜r，p＞。

2）建立局部索引：根據(jù)數(shù)據(jù)的物理分區(qū)將每個(gè)分區(qū)中數(shù)據(jù)覆蓋的空間區(qū)域?qū)懭胍粋€(gè)單獨(dú)的局部索引文件中。局部索引用于檢索與查詢區(qū)域相重疊的分區(qū)。

3）建立全局索引：初始化HDFS的連接命令，將所有局部索引文件連接成一個(gè)全局索引文件。全局索引用于判斷分布式系統(tǒng)中哪些存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)滿足查詢條件，用于檢索數(shù)據(jù)分區(qū)所在的節(jié)點(diǎn)。

1.2 四維空間科學(xué)數(shù)據(jù)的分布式索引架構(gòu)

1）索引在主從節(jié)點(diǎn)的分布策略

在分布式環(huán)境下，為了能夠?qū)崿F(xiàn)數(shù)據(jù)的快速檢索，需要將建立的兩級(jí)索引結(jié)構(gòu)存儲(chǔ)在分布式系統(tǒng)的不同節(jié)點(diǎn)中。將數(shù)據(jù)源索引信息、時(shí)間索引信息、全局索引文件存儲(chǔ)在主節(jié)點(diǎn)的內(nèi)存中，將局部索引文件存儲(chǔ)在分布式系統(tǒng)的從節(jié)點(diǎn)中。這樣的分布策略不僅能夠使得MapReduce可以直接訪問(wèn)索引信息，而且能夠有效地減少M(fèi)ap任務(wù)的數(shù)量。

2）數(shù)據(jù)在分布式環(huán)境下的容錯(cuò)機(jī)制

當(dāng)分布式系統(tǒng)出現(xiàn)故障時(shí)，為了維護(hù)數(shù)據(jù)的完整性，需要建立分布式系統(tǒng)主從節(jié)點(diǎn)的容錯(cuò)機(jī)制。將主節(jié)點(diǎn)中存儲(chǔ)的節(jié)點(diǎn)信息以及索引信息定時(shí)地備份在另一個(gè)獨(dú)立的分布式節(jié)點(diǎn)中，稱為主節(jié)點(diǎn)備份節(jié)點(diǎn)，用于恢復(fù)現(xiàn)場(chǎng)。從節(jié)點(diǎn)中采用Block備份的機(jī)制，每個(gè)從節(jié)點(diǎn)中包含的所有數(shù)據(jù)塊都在另外的兩個(gè)分布式從節(jié)點(diǎn)中有一個(gè)完全相同的備份，這樣的容錯(cuò)機(jī)制雖然占有了大量的存儲(chǔ)空間，但是能夠有效地維護(hù)數(shù)據(jù)的完整性。

2 NSSC-Hadoop系統(tǒng)架構(gòu)設(shè)計(jì)

NSSC-Hadoop是在Hadoop基礎(chǔ)上設(shè)計(jì)的能夠處理帶有時(shí)空屬性的結(jié)構(gòu)化的空間科學(xué)數(shù)據(jù)的系統(tǒng)架構(gòu)。NSSC-Hadoop由4個(gè)層次構(gòu)成：

1）語(yǔ)言層：在建立數(shù)據(jù)源索引信息和時(shí)間索引信息部分引入了Hive組件，支持HQL語(yǔ)言，它是一種類似于SQL的語(yǔ)言，其他部分使用的是Java語(yǔ)言。

2）存儲(chǔ)層：NSSC-Hadoop采用兩級(jí)索引結(jié)構(gòu)，對(duì)Hadoop增加了索引部分。

3）執(zhí)行層：NSSC-Hadoop允許MapReduce程序直接訪問(wèn)時(shí)空索引結(jié)構(gòu)。

4）業(yè)務(wù)層：將傳統(tǒng)的空間區(qū)域查詢操作以MapReduce的方式執(zhí)行在分布式系統(tǒng)框架上。

NSSC-Hadoop系統(tǒng)架構(gòu)如圖2所示，下面主要詳細(xì)介紹存儲(chǔ)層和執(zhí)行層兩個(gè)層次。

圖2 NSSC-Hadoop系統(tǒng)架構(gòu)圖

2.1 存儲(chǔ)層

在Hadoop中，輸入文件以無(wú)索引的堆數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在HDFS中，而在NSSC-Hadoop中，存儲(chǔ)層中不僅包含原始數(shù)據(jù)文件，同時(shí)也包含索引信息文件。原始數(shù)據(jù)文件以Block的形式存儲(chǔ)在從節(jié)點(diǎn)中大小為128 MB，并按照上文中介紹的容錯(cuò)機(jī)制進(jìn)行備份處理。局部索引文件與數(shù)據(jù)塊一同存儲(chǔ)在從節(jié)點(diǎn)的磁盤(pán)中，而數(shù)據(jù)源索引文件、時(shí)間索引文件以及全局索引文件存儲(chǔ)在主節(jié)點(diǎn)的內(nèi)存中，主節(jié)點(diǎn)定期向主節(jié)點(diǎn)備份節(jié)點(diǎn)發(fā)送備份信息。

2.2 執(zhí)行層

與Hadoop類似，NSSC-Hadoop的執(zhí)行層中執(zhí)行的是MapReduce程序。但是，Hadoop中的輸入文件是無(wú)索引的堆數(shù)據(jù)結(jié)構(gòu)，而NSSC-Hadoop支持帶有索引信息的輸入文件。在Hadoop中，首先FileSplitter組件將輸入文件邏輯分割成若干個(gè)分片Split，然后RecordReader組件從分片Split中根據(jù)數(shù)據(jù)在文件中的偏移量提取記錄，傳遞給map函數(shù)處理，如圖3所示。這種處理方式使得全部文件都要被遍歷一次，增加了數(shù)據(jù)查詢的時(shí)間。

圖3 Hadoop的MapReduce執(zhí)行部分

文中為了有效地提高數(shù)據(jù)檢索的效率，對(duì)輸入數(shù)據(jù)增加了索引信息，原本的組件無(wú)法滿足處理索引文件的需求。NSSC-Hadoop系統(tǒng)對(duì)原本的組件進(jìn)行改進(jìn)得到了_3D-SpatialFileSplitter，該組件基于主節(jié)點(diǎn)內(nèi)存中存儲(chǔ)的全局索引，通過(guò)過(guò)濾函數(shù)得到從節(jié)點(diǎn)中滿足查詢條件的所有文件塊的數(shù)據(jù)節(jié)點(diǎn)信息并為每個(gè)滿足條件的文件創(chuàng)建一個(gè)邏輯分片Split。對(duì)原本的RecordReader組件進(jìn)行改進(jìn)得到了_3DSpatialRecordReader，該組件從分片中提取局部索引信息，將滿足查詢條件的文件塊傳遞給map函數(shù)處理，如圖4所示。

圖4 NSSC-Hadoop的MapReduce執(zhí)行部分

3 試驗(yàn)結(jié)果與分析

3.1 試驗(yàn)數(shù)據(jù)及測(cè)試環(huán)境

試驗(yàn)數(shù)據(jù)集用隨機(jī)生成的多組數(shù)據(jù)，數(shù)據(jù)所在空間區(qū)域可在有效數(shù)字內(nèi)任意指定，本實(shí)驗(yàn)中使用的數(shù)據(jù)覆蓋空間范圍為[0，10 000]×[0，10 000]×[0，10 000]。測(cè)試環(huán)境如表1所示。

表1 測(cè)試環(huán)境

分布式系統(tǒng)采用主-從集成模式，其中，一臺(tái)機(jī)器作為主節(jié)點(diǎn)，另外4臺(tái)機(jī)器作為從節(jié)點(diǎn)，分布式系統(tǒng)完成網(wǎng)絡(luò)和環(huán)境配置后，用SSH通信協(xié)議實(shí)現(xiàn)無(wú)密碼登錄。為了保證集群的時(shí)間同步，將主節(jié)點(diǎn)作為時(shí)鐘服務(wù)器，其他幾臺(tái)機(jī)器均實(shí)現(xiàn)與主節(jié)點(diǎn)的時(shí)間校對(duì)。

3.2 實(shí)驗(yàn)結(jié)果和分析

文中為了驗(yàn)證算法的高效性，進(jìn)行了多組對(duì)比實(shí)驗(yàn)，多組數(shù)據(jù)分別運(yùn)行在無(wú)任何算法的分布式系統(tǒng)以及應(yīng)用本文提出的分布式區(qū)域檢索算法支持的分布式系統(tǒng)中。數(shù)據(jù)量為G數(shù)量級(jí)，時(shí)間單位為毫秒，由于時(shí)間數(shù)值較大，為了清晰地表示結(jié)果，對(duì)時(shí)間以10為底取對(duì)數(shù)如圖5所示。由實(shí)驗(yàn)結(jié)果可以看出，應(yīng)用本文提出的分布式區(qū)域檢索算法能夠有效地較少數(shù)據(jù)查詢的時(shí)間，當(dāng)數(shù)據(jù)量增大到500G時(shí)，數(shù)據(jù)檢索效率提高了將近50倍。并且由圖中可以看出，隨著數(shù)據(jù)量的增加，數(shù)據(jù)檢索時(shí)間呈現(xiàn)出收斂的趨勢(shì)，而使用Hadoop直接對(duì)數(shù)據(jù)進(jìn)行遍歷查詢時(shí)，當(dāng)數(shù)據(jù)量增加時(shí)數(shù)據(jù)檢索時(shí)間也隨著成倍增加，整體呈線性趨勢(shì)。

圖5 實(shí)驗(yàn)結(jié)果對(duì)比圖

表2是對(duì)500G數(shù)據(jù)下檢索不同空間區(qū)域下包含數(shù)據(jù)的時(shí)間結(jié)果的匯總。由表2可以看出，隨著檢索查詢區(qū)域的增大，數(shù)據(jù)檢索時(shí)間會(huì)成倍增加，原因在于當(dāng)檢索空間區(qū)域增大時(shí)，滿足查詢條件的數(shù)據(jù)塊數(shù)量就會(huì)增加。

表2 不同空間區(qū)域的數(shù)據(jù)檢索時(shí)間

當(dāng)分布式系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)減少時(shí)，對(duì)同一組輸入數(shù)據(jù)，大小為 500G，當(dāng)查詢區(qū)域?yàn)閇0，0，0，1000，1000，1000]時(shí)，檢索的時(shí)間結(jié)果匯總?cè)绫?所示，結(jié)果表明當(dāng)分布式系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)減少時(shí)數(shù)據(jù)檢索時(shí)間會(huì)增加，由此可以推斷，當(dāng)分布式系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)繼續(xù)增加時(shí)，由于MapReduce計(jì)算節(jié)點(diǎn)個(gè)數(shù)增加，因此數(shù)據(jù)檢索效率增大，檢索時(shí)間縮短。

雖然圖中結(jié)果表明數(shù)據(jù)檢索時(shí)間相對(duì)較大，但是該時(shí)間包含了分布式系統(tǒng)的啟動(dòng)時(shí)間，這個(gè)時(shí)間占用了全部時(shí)間的較大部分并且無(wú)法消除，當(dāng)分布式系統(tǒng)的節(jié)點(diǎn)數(shù)增加時(shí)，系統(tǒng)啟動(dòng)時(shí)間會(huì)繼續(xù)增加。

表3 不同空間區(qū)域的數(shù)據(jù)檢索時(shí)間

4 結(jié) 論

對(duì)空間科學(xué)大數(shù)據(jù)的快速查詢已成為當(dāng)前對(duì)天基信息分布式組織方法研究的熱點(diǎn)，本文基于空間科學(xué)大數(shù)據(jù)的特點(diǎn)提出了分布式區(qū)域檢索算法，并將理論算法應(yīng)用到了開(kāi)發(fā)的分布式系統(tǒng)框架NSSCHadoop中，通過(guò)對(duì)多組實(shí)驗(yàn)結(jié)果的分析展現(xiàn)了算法的有效性和高效性。該算法主要包括以下幾方面的特點(diǎn)：1）基于立方體的Block-Grid三維網(wǎng)格剖分方法建立的局部索引方法與傳統(tǒng)的空間網(wǎng)格剖分算法相比，該算法能夠很好地運(yùn)行在Hadoop基礎(chǔ)架構(gòu)上，而傳統(tǒng)的空間網(wǎng)格剖分算法運(yùn)行在Hadoop上會(huì)增加Hadoop系統(tǒng)的啟動(dòng)時(shí)間以及任務(wù)執(zhí)行時(shí)間。2）兩級(jí)索引結(jié)構(gòu)與其他檢索算法相比，增加的節(jié)點(diǎn)間的全局索引部分能夠有效地縮短數(shù)據(jù)查詢的時(shí)間，提高檢索效率。3）數(shù)據(jù)在分布式環(huán)境下的容錯(cuò)機(jī)制，能夠保證數(shù)據(jù)的完整性，防止任何因系統(tǒng)節(jié)點(diǎn)故障導(dǎo)致的數(shù)據(jù)丟失問(wèn)題。

參考文獻(xiàn)：

[1]張林，湯大權(quán)，張翀.時(shí)空索引的演變與發(fā)展[J].計(jì)算機(jī)科學(xué)，2010，37（4）：15-20.

[2]葛斌，唐九陽(yáng)，張翀.戰(zhàn)場(chǎng)環(huán)境中基于對(duì)等計(jì)算的分布式時(shí)空索引技術(shù)[J].系統(tǒng)工程與電子技術(shù)，2011，33（9）：2019-2024.

[3]Diaz A J，Gutiérrez Retamal G A，Gagliardi E O.Algoritmo de reunión espacio-temporal usando estructura 3DR- tree podada[J].Spatiotemporal Join，2012，23（2）：237-247.

[4]Zhang Z T.Optimization of History Tree in 3DRTree Index Structure[J].Applied Mechanics &Materials，2013，347-350（6）：525-529.

[5]Zhang Z T.3DR-Tree Model Improvement Based on Enhance of Index Performance[J].Advanced Materials Research，2013（765-767）：1332-1335.

[6]孟學(xué)潮，葉少珍.一種基于實(shí)時(shí)數(shù)據(jù)和歷史查詢分布的時(shí)空索引新方法[J].計(jì)算機(jī)應(yīng)用，2017，37（3）：860-865.

[7]張翀，肖衛(wèi)東，楊曉亮.基于對(duì)等計(jì)算的分布式時(shí)空索引模型建立與整體框架研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：961-967.

[8]龔俊，柯勝男，朱慶.一種集成R樹(shù)、哈希表和B樹(shù)的高效軌跡數(shù)據(jù)索引方法[J].測(cè)繪學(xué)報(bào)，2015，44（5）：570-577.

[9]汪娜.面向室內(nèi)空間的時(shí)空數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2014.

[10]Tang L，Kan Z，Zhang X，et al.Travel time estimation at intersections based on low-frequency spatial-temporalGPS trajectory big data[J].Cartography&Geographic Information Science，2016，33（13）：1523-1545.

[11]Huang Z H，Dai J.FNRB-Tree：Based on SpatialtemporalCo-occurrenceMiningTechnique[J].Journal of Chinese Computer Systems，2012，33（12）：2636-2641.

[12]黃照鶴.基于時(shí)空同現(xiàn)挖掘技術(shù)的FNRB-Tree[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（12）：2636-2641.

[13]FENG，TANG，Zhixian，etal.HQ-Tree：A Distributed Spatial Index Based on Hadoop[J].中國(guó)通信（英文版），2014，11（7）：128-141.

[14]Zhongliang F U，Yulong H U，Weng B.M-Quadtree Index：A Spatial Index Method for Cloud Storage Environment Based on Modified Quadtree Coding Approach[J].Acta Geodaetica EtCartographica Sinica，2016，12（6）：256-259.

[15]EldawyA，AlarabiL，MokbelM F.Spatial partitioning techniques in SpatialHadoop[J].Proceedings of the Vldb Endowment，2015，8（12）：1602-1605.