大規(guī)模空間矢量數(shù)據(jù)分布式存儲與計算優(yōu)化①

張 嘉,白曉飛,陶 超,張小桐

1(中國國土勘測規(guī)劃院,北京 100035)

2(廣東南方數(shù)碼科技股份有限公司,廣州 510665)

Foundation item：National Key Research and Development Program of China (2018YFD1100103-05)；Program of Ministry of Natural Resources of the People’s Republic of China (1902-033-14)

1 引言

國土數(shù)據(jù)類型多樣、結(jié)構(gòu)復(fù)雜、變化頻繁,具有很強的空間化、圖形化特征.近年來,隨著空間信息技術(shù)與資源環(huán)境管理工作普遍、深度交融,地表基質(zhì)、地表覆蓋、地下空間、業(yè)務(wù)信息等各類國土空間數(shù)據(jù)日趨復(fù)雜,涉及“山水林田湖草”及地質(zhì)、礦產(chǎn)等數(shù)百類自然資源要素,在地理空間上彼此映射、關(guān)聯(lián),且數(shù)據(jù)規(guī)模迅速增長.以全國土地調(diào)查矢量數(shù)據(jù)為例,年度更新數(shù)據(jù)超過2TB,累計要素數(shù)已達41 億.自然資源政務(wù)審批和業(yè)務(wù)管理,需要高效分析上述海量數(shù)據(jù)間的位置和語義關(guān)系以輔助決策,這一過程往往需要進行大量復(fù)雜空間運算.面向大規(guī)模空間數(shù)據(jù)分析,傳統(tǒng)關(guān)系型數(shù)據(jù)庫的空間數(shù)據(jù)存儲與計算框架愈發(fā)難以滿足實際需要.

隨著大數(shù)據(jù)技術(shù)快速發(fā)展,以云計算為代表的分布式計算技術(shù)以其高性能和高可靠性,特別是彈性擴展的數(shù)據(jù)存儲與處理能力,為大規(guī)?？臻g數(shù)據(jù)高效存儲與計算提供了可靠路徑[1-3].其中,Apache Hadoop 項目作為普遍流行的開源分布式大數(shù)據(jù)應(yīng)用框架,實現(xiàn)了MapReduce 分布式數(shù)據(jù)計算模型和HBase 分布式數(shù)據(jù)庫等核心應(yīng)用,支持基于集群的海量數(shù)據(jù)分布式存儲和運算,在超大規(guī)模數(shù)據(jù)管理中得到廣泛運用[4].近年來,為解決矢量數(shù)據(jù)空間分析的基本難題,基于Hadoop 應(yīng)用生態(tài)構(gòu)建了SpatialHadoop、Hadoop-GIS、Spatial-Spark、GeoSpark 等擴展框架,為矢量數(shù)據(jù)存儲、索引和計算提供了基礎(chǔ)支持[5].

數(shù)據(jù)組織作為處理和操作的基石,其結(jié)構(gòu)和性能深刻影響統(tǒng)計、分析與服務(wù)效率,成為海量時空數(shù)據(jù)管理、應(yīng)用的關(guān)鍵問題之一.針對Hadoop 空間數(shù)據(jù)存儲與計算,相關(guān)學(xué)者在數(shù)據(jù)組織、索引構(gòu)建等方面進行了研究.王凱等提出了基于Hadoop 的地理信息大數(shù)據(jù)處理模型,設(shè)計了矢量數(shù)據(jù)的格式轉(zhuǎn)換方法[6]；范建永等利用HBase 進行矢量空間數(shù)據(jù)管理,基于Map-Reduce 構(gòu)建了并行空間索引[7]；李振舉等提出了一種四叉樹-Hilbert 結(jié)合的索引設(shè)計方法[8]；朱進等提出了一種基于內(nèi)存數(shù)據(jù)庫Redis 的輕量級矢量地理組織方法[9].但當(dāng)前研究主要集中在分布式數(shù)據(jù)存儲的負載均衡,未對索引、分區(qū)和計算進行一體化考慮.

本文基于HBase 數(shù)據(jù)存儲與訪問的特性,使用四叉樹多級格網(wǎng)編碼算法進行矢量要素編碼,構(gòu)建分布式空間數(shù)據(jù)索引；針對HBase 缺乏對矢量數(shù)據(jù)模型有效支持的問題,提出了一種通過行鍵編碼鏈接索引、分區(qū)與計算的數(shù)據(jù)組織模型和分布式處理機制,并設(shè)計了分布式計算的優(yōu)化流程,為大規(guī)?？臻g數(shù)據(jù)存儲與處理提供了一種解決方案.

2 空間數(shù)據(jù)組織與優(yōu)化

2.1 四叉樹格網(wǎng)索引

本文使用四叉樹多級格網(wǎng)算法對矢量數(shù)據(jù)進行編碼構(gòu)建索引.該算法基于平面直角坐標(biāo)系劃分象限編碼,基本思想是將全域空間范圍劃分為4 個相等的區(qū)域并遞歸執(zhí)行,直到剖分層次達到指定深度[10,11].其處理流程可簡單描述為：第一,確定矢量要素集合的矩形空間范圍作為基準(zhǔn)格網(wǎng)并逐級剖分；第二,對剖分后的各級格網(wǎng)進行編碼；第三,計算每個矢量要素的最小外接矩形；第四,根據(jù)最小外接矩形空間上映射的格網(wǎng),使用格網(wǎng)編碼對其遞歸賦值；第五,存儲每個矢量要素的編碼集合.可見,通過計算矢量要素外接矩形所在的格網(wǎng)編碼,可快速獲取該要素在相應(yīng)格網(wǎng)層級的空間位置,如圖1所示.格網(wǎng)的劃分層級與要素的編碼長度正相關(guān),過多層級會導(dǎo)致要素的編碼復(fù)雜性增大,并產(chǎn)生數(shù)據(jù)冗余.因此,格網(wǎng)編碼的深度應(yīng)根據(jù)數(shù)據(jù)特點進行設(shè)計,遵循的基本原則是確保大部分要素擁有一個編碼,允許少部分的要素擁有多個編碼.

圖1 四叉樹編碼示意圖

2.2 HBase 預(yù)分區(qū)設(shè)計

將數(shù)據(jù)均衡分布到集群計算節(jié)點,是充分利用分布式計算資源的必要條件.HBase 以region 作為數(shù)據(jù)擴展和負載均衡的基本操作單元,分配到不同的計算服務(wù)器.HBase 表中的數(shù)據(jù)按照行鍵(RowKey) 排序,每個region 通過記錄起止行鍵管理表中的某些行數(shù)據(jù)[12].表首次創(chuàng)建時,默認只分配一個region,此時所有的讀寫操作都集中于這個region 所在的服務(wù)器,從而產(chǎn)生“熱點”(hot spotting)問題,導(dǎo)致該服務(wù)器負載急劇上升、性能下降；同時,region 中導(dǎo)入的數(shù)據(jù)量達到一定閾值會觸發(fā)分裂(region-split),即找到一個中間行鍵(MidKey)將其拆分為兩個region,當(dāng)輸入大規(guī)模數(shù)據(jù)時,分裂次數(shù)快速增加將大量占用磁盤I/O 資源,降低集群性能.針對上述問題,本文根據(jù)矢量數(shù)據(jù)的格網(wǎng)索引機制設(shè)計預(yù)分區(qū)策略,分區(qū)格網(wǎng)采用四叉樹剖分,當(dāng)預(yù)設(shè)4n(n≥1,n為剖分層級)個分區(qū)時,以第n級格網(wǎng)編碼作為預(yù)分區(qū)號,如圖2.預(yù)分區(qū)號作為行鍵編碼的前綴,數(shù)據(jù)入庫時可自動根據(jù)該編碼將要素均衡地向多個region 劃分.

使用MapReduce 框架進行并行計算時,分區(qū)數(shù)量決定了Map 函數(shù)的數(shù)量,即每個分區(qū)將啟動一個Map 函數(shù)進行計算,為保證計算和負載均衡,需合理預(yù)設(shè)分區(qū)數(shù)量,并考慮將相鄰空間要素聚集.分區(qū)個數(shù)過小,會造成單個分區(qū)的數(shù)據(jù)量過大,不利于負載均衡；分區(qū)個數(shù)過多,會導(dǎo)致單個分區(qū)內(nèi)數(shù)據(jù)量不足,不利于集中處理.實踐中,應(yīng)根據(jù)計算資源和數(shù)據(jù)量采用適當(dāng)?shù)姆謪^(qū)數(shù),原則上是充分利用集群的分布式特性,進行大范圍空間計算時,盡可能減少節(jié)點間數(shù)據(jù)傳輸,并使局部范圍計算在單個節(jié)點完成,以節(jié)約I/O 資源.一般而言,可以以集群中region server 數(shù)量的倍數(shù)作為參考值.

2.3 空間數(shù)據(jù)分布式存儲設(shè)計

2.3.1 行鍵編碼方法

HBase 作為面向列存儲的數(shù)據(jù)庫,通過行鍵檢索數(shù)據(jù)的效率較高,每秒鐘可獲取1000～2000 條記錄,而檢索非Key 列時效率相對偏低.因此,建立空間數(shù)據(jù)格網(wǎng)編碼與行鍵編碼的關(guān)聯(lián),使行鍵編碼集成空間信息,是提高空間檢索效率的關(guān)鍵環(huán)節(jié).本文提出以預(yù)分區(qū)號、要素格網(wǎng)編碼和隨機碼組合構(gòu)建行鍵編碼的方法,該編碼集成了集群和要素空間信息,便于分布式處理.

GridCode為格網(wǎng)編碼,使用2.1 節(jié)中通過格網(wǎng)編碼算法生成的定長字符碼；Random為隨機碼,根據(jù)實際應(yīng)用中數(shù)據(jù)集的大小確定,用于保證行鍵編碼的唯一性；預(yù)分區(qū)號(Num)根據(jù)2.2 節(jié)確定的方法獲取,并根據(jù)格網(wǎng)剖分后空間相鄰矢量要素編碼通常前綴相同的特點進行優(yōu)化：僅有一個編碼的要素,直接以其編碼值的后兩位作為預(yù)分區(qū)號；有多個編碼的要素,采用多個編碼共同前綴的后兩位作為預(yù)分區(qū)號.這種方法實現(xiàn)了索引、分區(qū)、計算的一體化設(shè)計(如圖3),使地理空間臨近的數(shù)據(jù)相對聚集,整體數(shù)據(jù)較均衡分布到各數(shù)據(jù)節(jié)點,有助于提升空間分析的計算效率,同時便于索引的動態(tài)更新維護.

圖3 行鍵編碼與數(shù)據(jù)存儲計算

2.3.2 矢量數(shù)據(jù)表存儲

基于上述行鍵編碼方法,空間矢量數(shù)據(jù)在HBase中的表存儲設(shè)計如表1.其中,num[i]+gridCode[i]+random[i]構(gòu)成行鍵(“+”表示連接,行鍵字符串中不含該符號)唯一標(biāo)識表中的一條記錄.矢量要素存儲表設(shè)計了一個Column Family(列族)矢量信息,該列族下按照要素字段定義Qualifier(列限定符),列限定符與原矢量數(shù)據(jù)屬性名稱保持一致,存儲圖斑編號、地類、權(quán)屬等信息,其中SHAPE 存放JSON 格式的坐標(biāo)數(shù)據(jù).至此,實現(xiàn)了土地空間矢量數(shù)據(jù)從關(guān)系型數(shù)據(jù)組織向分布式數(shù)據(jù)存儲的轉(zhuǎn)換.

表1 空間數(shù)據(jù)存儲表結(jié)構(gòu)設(shè)計

3 空間數(shù)據(jù)分布式計算

3.1 預(yù)處理與計算優(yōu)化

(1)重復(fù)計算規(guī)避.基于格網(wǎng)的空間數(shù)據(jù)存儲本質(zhì)上是一種以空間換時間的設(shè)計模式.矢量要素空間大小不同,格網(wǎng)編碼算法生成的編碼值個數(shù)也隨之不盡相同,導(dǎo)致存入HBase 表中的同一要素可能存在多個記錄,不利于MapReduce 并行計算[13].為降低重復(fù)數(shù)據(jù)對計算性能的影響,本文將同一要素的多個記錄存儲在同一分區(qū),通過矢量要素標(biāo)識信息,在Map 函數(shù)計算階段構(gòu)建緩存記錄參與計算的要素,進行去重操作,避免了數(shù)據(jù)重復(fù)計算和傳輸.

(2)空間數(shù)據(jù)關(guān)聯(lián)映射.針對參與空間計算的多元矢量數(shù)據(jù)集,按照格網(wǎng)編碼方法進行統(tǒng)一編碼,矢量要素采用本文提出的行鍵編碼算法構(gòu)建數(shù)據(jù)對象間的編碼映射.計算時對無編碼映射關(guān)系的空間數(shù)據(jù)進行過濾,可有效降低計算數(shù)據(jù)的規(guī)模.同時,通過要素編碼可快速查找關(guān)聯(lián)要素,避免全表要素掃描,從而大幅減少程序遍歷次數(shù),提升了分布式計算的性能.

3.2 分布式計算流程

分布式計算一定程度上可以有效改善傳統(tǒng)模式下處理大規(guī)模空間數(shù)據(jù)計算能力不足的問題.以空間疊加操作為例,典型的業(yè)務(wù)場景為：針對存儲于分布式數(shù)據(jù)庫中的地類圖斑矢量要素,使用外部存儲的、對應(yīng)縣級行政區(qū)劃內(nèi)的監(jiān)測圖斑與之進行空間疊加,將疊加得到的裁切后矢量數(shù)據(jù)輸出,計算要素面積,并統(tǒng)計某類屬性下的土地面積匯總數(shù).以此為例,基于上述數(shù)據(jù)組織策略,本文設(shè)計了分布式計算方法,主要思路為：基于MapReduce 計算框架,結(jié)合Esri GIS Tools for Hadoop 工具,實現(xiàn)空間數(shù)據(jù)Map 函數(shù)計算,Reduce 函數(shù)執(zhí)行結(jié)果匯總并輸出.具體處理流程為：(1)將待疊加矢量要素轉(zhuǎn)換為JSON 文件,讀入HDFS 存儲,對其進行格網(wǎng)編碼；(2)建立與被疊加地類圖斑矢量要素的編碼映射,獲取關(guān)聯(lián)的要素集合；(3)將關(guān)聯(lián)集合加載到分布式緩存中；(4)Map 函數(shù)逐條讀取地類圖斑矢量數(shù)據(jù),根據(jù)要素編碼獲取分布式緩存中集合中的對應(yīng)要素,并執(zhí)行空間疊加操作；(5)輸出裁切后的數(shù)據(jù),并將過程數(shù)據(jù)傳送Reduce 函數(shù)處理；(6)Reduce 函數(shù)完成計算結(jié)果的匯總及輸出.總體流程如圖4.

圖4 空間數(shù)據(jù)裁切操作流程

4 測試與分析

針對本文提出的格網(wǎng)編碼索引、預(yù)分區(qū)及行鍵優(yōu)化設(shè)計的空間數(shù)據(jù)組織策略和計算流程,使用真實數(shù)據(jù),采用空間疊加與統(tǒng)計場景進行測試,驗證方案的有效性.

4.1 測試環(huán)境

基于Hadoop 2.7.3 搭建一個主節(jié)點,4 個數(shù)據(jù)節(jié)點的集群環(huán)境(圖5),在該集群部署HBase 1.3.1.數(shù)據(jù)節(jié)點服務(wù)器配置為：CPU Intel(R) Xeon(R) CPU E5-2609 v4 @ 1.70 GHz；內(nèi)存：128 GB；操作系統(tǒng)：CentOS7.3；網(wǎng)絡(luò)帶寬為1000 Mb/s.

4.2 測試過程與結(jié)果分析

4.2.1 測試數(shù)據(jù)

180個縣級行政區(qū)劃單位的地類圖斑(DLTB)和監(jiān)測圖斑(JCTB),兩類數(shù)據(jù)都是空間矢量要素.為便于對比,將其分為8 個測試組,每組所含要素和數(shù)據(jù)量如表2所示.

圖5 測試環(huán)境

表2 數(shù)據(jù)分組及要素數(shù)

4.2.2 測試內(nèi)容與流程

自然資源管理中,地類圖斑刻畫了土地利用的現(xiàn)狀情況,按照規(guī)定的時點更新.遙感監(jiān)測是維護土地現(xiàn)狀信息準(zhǔn)確性和現(xiàn)勢性的重要手段,通過對比、判讀不同時相的遙感影像,能夠識別發(fā)生變化的國土特征信息,這些變化信息經(jīng)矢量化形成監(jiān)測圖斑.業(yè)務(wù)實踐中,一種典型的應(yīng)用場景是獲取監(jiān)測圖斑空間范圍內(nèi)變更前的土地利用類型和面積等數(shù)據(jù),以輔助數(shù)據(jù)更新、變化分析和行政監(jiān)管.本文將監(jiān)測圖斑與地類圖斑進行空間疊加,獲取監(jiān)測圖斑的地類面積、權(quán)屬等信息,測試研究提出的分布式存儲與計算方案下空間數(shù)據(jù)分析和匯總統(tǒng)計的效率,主要流程如下：(1)將地類圖斑數(shù)據(jù)作為疊加底圖,創(chuàng)建格網(wǎng)索引,存儲在HBase 分布式數(shù)據(jù)庫；(2)以監(jiān)測圖斑作為外部疊加數(shù)據(jù),采用GIS Tools for Hadoop 插件工具集將其轉(zhuǎn)換為以縣級行政區(qū)為單位的JSON 文件,存儲于HDFS 分布式文件系統(tǒng)；(3)基于MapReduce 框架對監(jiān)測圖斑和地類圖斑進行疊加,提取地類信息并計算面積,匯總形成監(jiān)測圖斑地類面積匯總表,并輸出疊加后的圖形數(shù)據(jù),驗證其正確性.

4.2.3 結(jié)果分析

按照測試流程對8 個測試組按照執(zhí)行數(shù)據(jù)操作,記錄數(shù)據(jù)上傳、數(shù)據(jù)轉(zhuǎn)換、空間疊加、統(tǒng)計輸出幾項主要處理環(huán)節(jié)的耗時情況,如表3.

表3 測試耗時結(jié)果記錄(單位：s)

對表3數(shù)據(jù)進行分析,結(jié)果表明：

(1)數(shù)據(jù)處理耗時與數(shù)據(jù)量正相關(guān),但隨著數(shù)據(jù)量的增加,計算效率呈現(xiàn)階段特征.在地類圖斑數(shù)由5000 向50 萬量級增長過程中,處理要素的平均耗時顯著下降,由平均0.29 秒/要素降為0.01 秒/要素,說明單位時間系統(tǒng)處理要素的能力在迅速提升,充分體現(xiàn)了分布式環(huán)境處理大規(guī)模數(shù)據(jù)的優(yōu)勢；當(dāng)要素數(shù)據(jù)超過50 萬后,單位時間處理要素的數(shù)量變化曲線基本平滑,這是由于服務(wù)器數(shù)量固定導(dǎo)致計算資源受限,可以預(yù)測增加計算節(jié)點,能夠進一步提高性能.

(2)空間疊加環(huán)節(jié)在總體分析流程中的耗時居支配地位,且遠高于其他環(huán)節(jié),占比區(qū)間為94.45% 至98.02%,這說明空間數(shù)據(jù)并行計算是數(shù)據(jù)分析的核心,也是計算優(yōu)化的重點.

根據(jù)上述分析結(jié)果,進一步測試本文提出的索引、預(yù)分區(qū)及行鍵編碼一體化設(shè)計的空間數(shù)據(jù)組織策略(記作GRID),與常規(guī)采用隨機散列構(gòu)建行鍵編碼方法(記作RHASH)的空間分析效率對比.為降低計算資源對數(shù)據(jù)處理效率的影響,測試數(shù)據(jù)選擇18 個縣級行政單元的地類圖斑和監(jiān)測圖斑矢量要素(共90 萬個要素),分為5 個測試組,記錄空間疊加的處理時間,如表4所示.

表4 空間疊加測試記錄

可見,GRID 優(yōu)化方法空間疊加的耗時在各測試組均顯著低于RHASH 方法,且隨著數(shù)據(jù)規(guī)模的增加,其效率優(yōu)勢進一步顯現(xiàn),測試要素數(shù)據(jù)量區(qū)間最大側(cè)的執(zhí)行效率提升了1 倍.這主要是由于未優(yōu)化方案不能根據(jù)疊加數(shù)據(jù)從HBase 表中快速過濾與其相關(guān)的信息,需進行全表掃描,并判斷每條數(shù)據(jù)與疊加數(shù)據(jù)的空間關(guān)系.本文提出的優(yōu)化策略彌補了這一不足,大幅降低了MapReduce 處理的數(shù)據(jù)量,從而有效提升了計算性能.

總體來看,分布式存儲與計算環(huán)境下,空間數(shù)據(jù)處理效率較關(guān)系型數(shù)據(jù)庫大幅增加.在硬件資源要求并不苛刻的條件下,近600 萬地類圖斑矢量要素的全流程疊加操作耗時僅20 分鐘,而關(guān)系型數(shù)據(jù)庫下的同量級相似數(shù)據(jù)處理需投入大量作業(yè)人員使用不同客戶端執(zhí)行操作,時間單位往往以工作日計.因此,在海量國土空間矢量數(shù)據(jù)管理與分析中,將分布式存儲、計算技術(shù)與空間數(shù)據(jù)特性充分優(yōu)化結(jié)合,能夠大幅提升工作效率.

5 結(jié)語

本文對空間矢量數(shù)據(jù)的分布式存儲與計算技術(shù)進行了探索,研究了基于四叉樹格網(wǎng)構(gòu)建空間索引的方法,結(jié)合矢量數(shù)據(jù)的特性,將其與HBase 預(yù)分區(qū)策略和分布式存儲設(shè)計有效融合.同時,基于Hadoop 處理模型,設(shè)計了與之銜接的分布式計算流程,形成了一種分布式場景下矢量數(shù)據(jù)組織與計算的優(yōu)化方法.后續(xù)工作中,擬擴大集群和數(shù)據(jù)規(guī)模,全面調(diào)試并進一步提升其實用性.