， ,b

(河南大學 a.計算機與信息工程學院; b.數(shù)據(jù)與知識工程研究所, 河南 開封 475001)

隨著現(xiàn)代科學的發(fā)展，要求大量空間數(shù)據(jù)的高性能查詢被用于越來越多的學科領(lǐng)域。數(shù)據(jù)和計算密集型的大規(guī)?？臻g數(shù)據(jù)的出現(xiàn)對管理和查詢海量空間數(shù)據(jù)提出了挑戰(zhàn)。本文以Hadoop為基礎(chǔ)提出了一種Hadoop Spatial的空間數(shù)據(jù)管理和查詢系統(tǒng)的設(shè)計思想，用于在Hadoop上運行的高性能空間查詢的可擴展的分布式空間數(shù)據(jù)倉庫系統(tǒng)。Hadoop Spatial的中心是Hadoop框架。Hadoop由一個數(shù)據(jù)存儲層或Hadoop分布式文件系統(tǒng)(HDFS)和一個數(shù)據(jù)處理層或MapReduce的框架組成[1-2]，通過支持多種類型的空間分區(qū)，以Hadoop的數(shù)據(jù)倉庫檢索工具在MapReduce的隱式并行空間執(zhí)行查詢。它采用全局分區(qū)索引與可自定義的按需局部空間索引相結(jié)合的方式來實現(xiàn)高效的查詢處理[3]。

傳統(tǒng)的空間數(shù)據(jù)庫管理系統(tǒng)(Spatial DataBase Manager System,SDBMS)雖然采用并行RDBMS架構(gòu)，具有可擴展性，但是并不能管理和查詢大量的空間數(shù)據(jù)。并行SDBMS一般通過多個并行磁盤數(shù)據(jù)來分區(qū)，以減少I/O瓶頸和計算密集型操作步驟。對于多個數(shù)據(jù)庫分區(qū)的平衡數(shù)據(jù)和任務負載來說，并行SDBMS架構(gòu)缺乏有效的空間分割機制。高數(shù)據(jù)負載的開銷是SDBMS解決方案的一大瓶頸。通過并行數(shù)據(jù)庫向外擴展的空間查詢研究雖然可行，但其代價昂貴，需要復雜調(diào)整，以獲得最佳性能。因此，用廉價的硬件設(shè)備通過高速的網(wǎng)路連接取代傳統(tǒng)的空間數(shù)據(jù)庫管理系統(tǒng)是大數(shù)據(jù)研究與應用的發(fā)展趨勢。本文將具有查詢高響應和高可擴展性的Hadoop Spatial與并行SDBMS系統(tǒng)進行對比來證明Hadoop Spatial的可行性。

1 Hadoop Spatial設(shè)計

Hadoop Spatial的主要目標是開發(fā)一個高可擴展、高性價比、高效率和表現(xiàn)力的綜合空間查詢處理的數(shù)據(jù)和計算密集型應用的空間查詢系統(tǒng)，以便將基于大數(shù)據(jù)查找的任務在Hadoop Spatial上借助MapReduce的優(yōu)勢化解成分布式任務運算。為了實現(xiàn)這樣的系統(tǒng)，本文將其分解成小的任務且并行處理這些任務。將空間數(shù)據(jù)按照經(jīng)緯度方格劃分成區(qū)域(Area)，并行處理這些區(qū)域，生成的區(qū)域成為單元，可用于查詢處理。查詢處理的問題就變成了設(shè)計一個以區(qū)域為單元查找的可以并行運行的任務?；诖耍疚奶岢鲆粋€基于MapReduce的典型空間查詢步驟：①將空間數(shù)據(jù)和圖片數(shù)據(jù)按經(jīng)緯度進行劃分，按照經(jīng)緯度方格劃分為Area區(qū)域；②將數(shù)據(jù)按照空間數(shù)據(jù)模型進行處理，將數(shù)據(jù)存儲在HDFS中；③在執(zhí)行查詢時，將空間查詢語句解析成MapReduce任務；④執(zhí)行MapReduce任務并將執(zhí)行結(jié)果存儲到HDFS中，然后輸出。

1.1 空間數(shù)據(jù)庫結(jié)構(gòu)設(shè)計

由于Hadoop Spatial是一個基于Hadoop的數(shù)據(jù)存儲和計算的查詢系統(tǒng)，因此其數(shù)據(jù)庫架構(gòu)模式和普通數(shù)據(jù)庫的大致結(jié)構(gòu)沒有太大的區(qū)別，都有自己的查詢語言、編譯器，以及圍繞查詢語言編譯器的查詢語言解析器和優(yōu)化工具。只不過Hadoop Spatial是基于Hadoop進行數(shù)據(jù)存儲，并采用基于MapReduce的Hive查詢工具擴展實現(xiàn)的分布式空間數(shù)據(jù)庫系統(tǒng)。具體的數(shù)據(jù)庫架構(gòu)模式如圖1所示。

(1)空間數(shù)據(jù)的錄入：空間數(shù)據(jù)的錄入主要功能是將空間數(shù)據(jù)整理并錄入，包括圖片數(shù)據(jù)的錄入。圖片數(shù)據(jù)的錄入主要是對圖片數(shù)據(jù)進行編號整理以及圖片數(shù)據(jù)的壓縮存儲功能。

圖1 Hadoop Spatial空間數(shù)據(jù)庫基本架構(gòu)

(2)空間數(shù)據(jù)的存儲：空間數(shù)據(jù)的存儲主要是以Hadoop平臺為基礎(chǔ)，將數(shù)據(jù)分布式的儲存在各個不同的數(shù)據(jù)節(jié)點中。數(shù)據(jù)的存儲和讀取依賴于HDFS系統(tǒng)。只需要按照Hadoop進行配置即可。

(3)HQL查詢語言分析器：作為空間數(shù)據(jù)庫的查詢語句分析器，實現(xiàn)了查詢語句的編輯功能。

(4)HQL編譯器：以Hadoop的一個數(shù)據(jù)倉庫工具Hive為基礎(chǔ)實現(xiàn)。由于Hive不支持空間查詢，因此需擴充Hive功能，以支持空間查詢分析。其中的解釋器、編譯器、優(yōu)化器完成 HQL 查詢語句從詞法分析、語法分析、編譯、優(yōu)化以及查詢計劃的生成。生成的查詢計劃存儲在 HDFS 中，隨后由MapReduce調(diào)用執(zhí)行。

(5)空間索引生成器：進行空間查詢的一個基本要求就是快速響應，使用空間索引來支持空間查詢是大多數(shù)并行空間數(shù)據(jù)庫的方法。分布式的數(shù)據(jù)庫不同于并行空間數(shù)據(jù)庫，分布式索引強調(diào)如何實現(xiàn)索引數(shù)據(jù)的分布式查找。

(6)文件數(shù)據(jù)索引生成器：這是根據(jù)圖片數(shù)據(jù)的需要構(gòu)建的索引。在本系統(tǒng)中，圖片數(shù)據(jù)的索引建立在通過文件名稱的索引機制上。

(7)空間查詢處理器：作為空間查詢引擎的關(guān)鍵，通過條件過濾掉的數(shù)據(jù)，進行空間邏輯運算。

1.2 空間數(shù)據(jù)模型建立

空間數(shù)據(jù)模型是描述GIS空間數(shù)據(jù)組織和進行空間數(shù)據(jù)庫設(shè)計的理論基礎(chǔ)[4]。本文在Hadoop Spatial中采用了最新的、以Geodatabase數(shù)據(jù)模型為基礎(chǔ)設(shè)計的面向?qū)ο蟮目臻g數(shù)據(jù)模型。Geodatabase是將空間對象的屬性和行為結(jié)合起來的智能化地理數(shù)據(jù)模型。它以關(guān)系數(shù)據(jù)庫為基礎(chǔ),利用關(guān)系數(shù)據(jù)庫的數(shù)據(jù)處理能力對空間數(shù)據(jù)和非空間數(shù)據(jù)進行統(tǒng)一管理[4]。地理數(shù)據(jù)庫對空間數(shù)據(jù)的存儲、管理和應用功能是通過SDE(Spatial Database Engine 空間數(shù)據(jù)庫引擎)來具體實現(xiàn)的。

1.3 空間數(shù)據(jù)的分區(qū)

空間數(shù)據(jù)分區(qū)可提供數(shù)據(jù)分割，并生成一組瓦片用于查詢?nèi)蝿盏奶幚韱卧??？臻g分區(qū)實現(xiàn)了數(shù)據(jù)分區(qū)和計算的并行化?？臻g數(shù)據(jù)分區(qū)可減緩空間數(shù)據(jù)在進行分布式查詢時的數(shù)據(jù)傾斜問題。

由于MapReduce擁有自己的作業(yè)調(diào)度平衡方案，因此對空間數(shù)據(jù)的分區(qū)主要專注于突破密度區(qū)域，將空間數(shù)據(jù)分成若干小的區(qū)域并采取遞歸分割數(shù)據(jù)。每個切片的文件大小可能很小，比如幾MB，不能直接存儲到HDFS。這是由HDFS對大數(shù)據(jù)塊批量處理而優(yōu)化的特性決定的[5]。因此，數(shù)據(jù)暫存到HDFS中，需要將所有切片合并成大型文件，而不是將每個切片作為一個單獨的文件存儲。

1.4 Hive

Hive是一個開源的基于MapReduce[6]的Hadoop的數(shù)據(jù)倉庫工具。它可以將結(jié)構(gòu)化的數(shù)據(jù)文件映射為一張數(shù)據(jù)庫表，并提供完整的查詢功能，也可將查詢語句轉(zhuǎn)換為MapReduce任務來運行，極大地簡化了開發(fā)中的MapReduce應用程序[7]。其查詢語言類似于SQL，可命名為HQL，可以通過類SQL語句快速實現(xiàn)簡單的MapReduce任務，不必開發(fā)專門的MapReduce應用，十分適合用作數(shù)據(jù)倉庫工具。

2 系統(tǒng)擴展與空間數(shù)據(jù)庫查詢的實現(xiàn)

Hadoop Spatial在數(shù)據(jù)查詢方面借用了Hadoop的分布式計算，以加快數(shù)據(jù)查詢的速度。因此，為了實現(xiàn)Hadoop的空間查詢能力，給MapReduce提供一個集成的查詢語言，就要實現(xiàn)Hive查詢工具對空間查詢的支持，擴展Hive的翻譯器功能，實現(xiàn)翻譯器對一些空間查詢操作符、空間計算方法以及空間數(shù)據(jù)類型的支持，可命名為Hive for SP。

2.1 Hive支持空間查詢擴展的實現(xiàn)

在開發(fā)Hive for SP時，本文以當前流行的空間數(shù)據(jù)查詢方式對SQL進行擴展，以支持空間查詢。SQL作為發(fā)展成熟的結(jié)構(gòu)化查詢語言，具有面向問題和接近自然語言的良好特征，而空間數(shù)據(jù)中的查詢和分析是空間和屬性的雙重相關(guān)。SQL3是最新的SQL標準，不僅對SQL的語法規(guī)則做出了更加詳細和準確的定義，而且對空間數(shù)據(jù)庫的支持做了統(tǒng)一描述，使得長期以來令GIS開發(fā)者困擾的空間數(shù)據(jù)存儲問題得到了解決。在SQL的基礎(chǔ)上進行擴展將是管理和分析空間數(shù)據(jù)的一個趨勢[8]。

由于HQL是類似于SQL的基于Hadoop的分布式查詢語言，因此只要擴展HQL對空間查詢的支持即可。

Hive for SP支持以下基本的空間查詢：空間操作符、常用的空間計算方法、空間數(shù)據(jù)類型、空間關(guān)系的比較以及高效的查詢空間的訪問方法處理等。本文參考文獻[9]的相關(guān)理論對Hive進行了處理。這里不再具體描述。

2.2 空間數(shù)據(jù)查詢、訪問的實現(xiàn)

Hive中編譯器處理的HiveQL字符串可能是一條DDL、DML查詢語句。編譯器將字符串轉(zhuǎn)化為策略(plan)。策略僅由元數(shù)據(jù)操作和HDFS操作組成。元數(shù)據(jù)操作只包含DDL語句，HDFS操作只包含LOAD語句。對插入和查詢而言，策略由MapReduce任務中的具有方向的非循環(huán)圖(directedacyclic graph，DAG)組成[7]。因此，在對Hive進行擴展，實現(xiàn)控件查詢的支持時，只對編譯器進行擴展即可。

Hive采用傳統(tǒng)的plan-first, execute-next方法[10]進行查詢處理的步驟有3個：查詢翻譯、邏輯計劃生成和物理計劃生成。用SQL表達式查詢時，首先解析查詢并生成一個抽象語法樹。接著對由抽象語法樹轉(zhuǎn)換為運算符樹的邏輯方案以及諸如謂詞下推的查詢優(yōu)化技術(shù)進行應用；然后根據(jù)操作樹生成一系列MapReduce任務；最后將產(chǎn)生的MapReduce任務提交給Hive運行。因此，在對Hive擴展時，在查詢翻譯中增加對上文2.1中的查詢關(guān)鍵字的支持，并在邏輯計劃生成的步驟中生成對應的查詢?nèi)蝿占纯伞?/p>

由于空間連接是在最常用和昂貴的查詢中進行的，因此有必要討論空間連接查詢映射到MapReduce的計算模型。

以圖2的交叉查詢?yōu)槔?，詳細描述如何將HQL語句轉(zhuǎn)化為MapReduce任務。

圖2 一個空間交叉查詢的例子

首先在Map階段，輸入表進行掃描，按照where條件進行數(shù)據(jù)篩選。滿足條件的數(shù)據(jù)被篩選出來，生成下一步進行Reduce操作的key/value對。數(shù)據(jù)key為該對象所在的區(qū)域ID(AreaID)，value是SELECT子句中指定的列組合。

其次在Shuffle階段，Hadoop內(nèi)部執(zhí)行機將Map階段查到的數(shù)據(jù)按照Key進行分組。

最后在Reducer階段，對符合條件的記錄，通過調(diào)用Hive建立基于R *樹的索引，并執(zhí)行查詢，進行空間運算。

查詢轉(zhuǎn)換的具體偽代碼如圖3所示。

圖3 空間連接查詢的MapReduce偽代碼

在Hadoop Spatial中，數(shù)據(jù)按照劃分的區(qū)域被存儲。包含查詢以及聚集查詢的數(shù)據(jù)可以根據(jù)查詢進行過濾和篩選。這僅是一個簡單的數(shù)據(jù)查找過程，不在這里具體描述。

3 實驗與分析

為了驗證Hadoop Spatial數(shù)據(jù)庫的系統(tǒng)性能，本文針對空間數(shù)據(jù)庫的一些常用操作進行了性能測試,并與當前的商業(yè)用分布式數(shù)據(jù)庫系統(tǒng)進行對比。

3.1 實驗設(shè)備

使用10臺Hadoop Spatial方面的服務器搭建該系統(tǒng)。該系統(tǒng)硬件設(shè)備的主要配置如下：單服務器8核CPU、4 GB主存、500 GB的硬盤存儲空間、1 GB的互連網(wǎng)絡(luò)。操作系統(tǒng)為CentOS 5.6(64位)。以Hadoop 2.1.0作為MapReduce平臺，以Apache Hive 0.7.1為基礎(chǔ)開發(fā)的Hive for SP 1.0的大部分配置參數(shù)都被設(shè)為默認值。

為將Hadoop Spatial和并行SDBMS進行比較，實驗安裝了一個商業(yè)SDBMS(Oracle 10g spatial)。它具有4個節(jié)點的空間擴展和分區(qū)功能。每個節(jié)點都配備了8核、16 GB內(nèi)存、1T硬盤存儲空間的機架式服務器。實驗以1 GB的互連網(wǎng)絡(luò)用于節(jié)點間通信。

3.2 實驗數(shù)據(jù)集

本文數(shù)據(jù)從OpenStreetMap(OSM)中下載，包含了大量的地理信息數(shù)據(jù)，如湖泊、森林、建筑物和道路等。圖片數(shù)據(jù)使用的是開封市城區(qū)png格式的切片數(shù)據(jù)。以此為基本的實驗數(shù)據(jù)，格式化數(shù)據(jù)后，以文件的形式將圖片存儲到空間數(shù)據(jù)庫中，以文件名為檢索條件檢索圖片數(shù)據(jù)。

3.3 Hadoop Spatial的性能測試

通過系統(tǒng)搭建，在兩個系統(tǒng)參數(shù)設(shè)定大致一樣的情況下，對Hadoop Spatial與并行空間數(shù)據(jù)庫在查詢方面的性能以及Hadoop Spatial的擴展性進行實驗，并對實驗結(jié)果進行分析。

3.3.1 Hadoop Spatial與并行空間數(shù)據(jù)庫的比較

空間數(shù)據(jù)庫的操作對數(shù)據(jù)的編輯要求并不高，要求高的約半數(shù)集中在查詢方面。因此，更快、更好查詢才是高性能空間數(shù)據(jù)庫的標準。由于許多復雜的查詢都可以被分解成空間連接查詢、包含查詢和聚集查詢這3種典型的查詢，因此本文以這3種典型查詢?yōu)榛鶞蔬M行了性能實驗(見圖4)。

對于連接查詢來說，兩個系統(tǒng)都具有良好的可擴展性。但是，Hadoop Spatial總體上與已經(jīng)得到調(diào)整的SDBMS相比有更好的性能；在相同的CPU核數(shù)下，Hadoop Spatial的查詢速度比SDBMS快，如圖4(a)所示。分析可知，SDBMS可以智能存儲數(shù)據(jù)，并且可以使用索引記錄讀取來減少I/O開銷，因此對I/O繁重的任務會表現(xiàn)出更好的性能。然而，空間連接涉及繁雜的幾何計算，并且由數(shù)據(jù)庫管理系統(tǒng)生成的查詢計劃任務對SDBMS是不理想的。盡管SDBMS內(nèi)置的分區(qū)功能可平衡數(shù)據(jù)分發(fā)，但其處理計算偏移的能力有限。Hadoop具有按需任務調(diào)度機制，可以解決這種計算傾斜問題。

(a)連接查詢 (b)包含查詢 (c)聚集查詢

對于包含查詢來說，Hadoop Spatial優(yōu)于規(guī)模較小的SDBMS，在具有不同數(shù)量CPU的基礎(chǔ)上性能表現(xiàn)平穩(wěn)，如圖4(b)所示。然而，SDBMS具有更好的可擴展性，特別是擴展數(shù)量較大時。Hadoop Spatial的包含查詢被實現(xiàn)為只有MapReduce作業(yè)，并且查詢本身與連接查詢相比具有較小的計算量。因此，時間實際上是被用在了讀出文件分割、解析對象以及查詢該對象是否被包含在查詢區(qū)域內(nèi)。SDBMS可以發(fā)揮空間索引的優(yōu)勢，迅速過濾掉不相關(guān)的記錄。因此，SDBMS的包含查詢性能稍好。

在聚集查詢中，SDBMS的性能比Hadoop Spatial稍好，如圖4(c)所示。這主要是由于Hadoop Spatial具有記錄解析的。這兩種系統(tǒng)都具有類似的查詢計劃，都是對一個全表進行掃描后進行空間列的聚集操作，且有類似的I/O開銷聚合操作。然而，Hadoop Spatial中的記錄需要實時進行解析，而SDBMS的記錄只是預解析和存儲的二進制格式。因此，SDBMS在聚集查詢方面有更好的查詢性能。

3.3.2 Hadoop Spatial的擴展性

Hadoop Spatial系統(tǒng)的可擴展性能如圖5所示。

圖5 擴展性能測試性能圖

圖5顯示出了Hadoop Spatial系統(tǒng)具有良好的可擴展性能。實驗采用的數(shù)據(jù)包括1×、3×、5×、10×的數(shù)據(jù)集以及不同的CPU核數(shù)。當reducer的數(shù)量增加時，查詢時間連續(xù)下降，幾乎實現(xiàn)了線性加速。例如，當reducer的數(shù)量從20增加到40時，查詢時間對應減少了50%，1×數(shù)據(jù)集與10×數(shù)據(jù)集的平均查詢時間均有很大幅度的提高。這說明該系統(tǒng)具有良好的向上擴展性能。

4 結(jié) 語

通過對分布式空間數(shù)據(jù)庫的框架結(jié)構(gòu)和技術(shù)方案的研究, 提出和設(shè)計了基于Hadoop技術(shù)建立分布式空間數(shù)據(jù)庫的總體方案和技術(shù)路線。通過構(gòu)建空間數(shù)據(jù)庫引擎(Hadoop Spatial Engine)，將空間數(shù)據(jù)和屬性數(shù)據(jù)以統(tǒng)一的數(shù)據(jù)模型存儲在空間數(shù)據(jù)庫管理系統(tǒng)(Hadoop Spatial)中,對數(shù)據(jù)統(tǒng)一管理,可以直接利用DBMS的管理功能,充分利用關(guān)系數(shù)據(jù)庫查詢優(yōu)化的許多方法,提高數(shù)據(jù)的訪問速度。同時,Hadoop能有效地進行分布式處理,為基于C/S體系結(jié)構(gòu)空間數(shù)據(jù)庫的數(shù)據(jù)互操作和信息共享提供技術(shù)支持。

本文只是簡單構(gòu)建空間數(shù)據(jù)庫，在實際應用過程中還有許多需要優(yōu)化之處，比如數(shù)據(jù)的安全性、數(shù)據(jù)的完整性、監(jiān)控數(shù)據(jù)庫的使用和運行、數(shù)據(jù)安全策略和用戶安全策略、用戶的可操作性等還需要進一步的實踐驗證。下一步要進行探索的是分布式空間數(shù)據(jù)的索引研究與空間數(shù)據(jù)的時態(tài)研究。

參考文獻：

[1] The Apache Software Foundation.Hadoop [EB/OL].[2014-04-20].http://hadoop.apache.org.

[2] Konstantin S,Hairong K，Sanjay R.The Hadoop Distributed File System[C]//第26屆IEEE研討會海量存儲系統(tǒng)與技術(shù)(MSST'10)論文集.美國內(nèi)華達州：IEEE,2010:1-10.

[3] 章建濤.并行數(shù)據(jù)倉庫環(huán)境下基于B_樹的分布式索引研究[D].秦皇島:燕山大學,2010.

[4] 肖明.基于Geodatabase的空間數(shù)據(jù)庫系統(tǒng)設(shè)計與實現(xiàn)[D].武漢:武漢大學,2005.

[5] 蔡斌,陳湘平.Hadoop技術(shù)內(nèi)幕：深入解析Hadoop Common和HDFS架構(gòu)設(shè)計與實現(xiàn)原理[M].北京：機械工業(yè)出版社, 2013:236-362.

[6] Dean J, Ghemawat S.MapReduce: a flexible data processing tool[J].Communications of the ACM, 2010, 53(1): 72-77.

[7] Ashish T, Joydeep S, Narnit J, et al.Hive——A Warehousing Solution Over a MapReduce Framework[J].VLDB,2009(2):1626-1629.

[8] 吳信才.空間數(shù)據(jù)庫[M].北京:科學出版社, 2009:159-190.

[9] Ravi K, Albert G, Euro B.Oracle Spatial空間信息管理——Oracle Database 11g[M].管會生譯.北京:清華大學出版社,2009:257-320.

[10] 董西成.Hadoop技術(shù)內(nèi)幕：深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理[M].北京：科學出版社，2013：107-120.