基于“分治網格”的空間大數據快速分析方法

賈文玨，安 瓊

（1.國土資源部信息中心，北京100812；2.中國農業(yè)大學 信息與電氣工程學院，北京100083）

0 引 言

如何能夠實現TB 級空間數據的快速分析，是當前海量空間數據分析面臨的重要問題［1－3］。學術界對大數據的管理和分析已經進行了深入研究，企業(yè)界也提出和研發(fā)了各類創(chuàng)新技術。如Google針對文件類大數據應用需求，設計開發(fā)了GFS （Google file system）［4］分布式文件系統(tǒng)和Bigtable［5］數據庫，提出了Dremel［6］計算模型；微軟提出了Dryad［7］的數據處理模型，用來構建支持有向無環(huán)圖類型數據流的并行程序；Facebook 針對海量小文件的文件系統(tǒng)，推出了Haystack［8］，通過多個邏輯文件共享同一個物理文件、增加緩存層、部分元數據加載到內存等方式有效地實現了海量圖片的存儲；Amazon針對大數據時代的數據存儲，推出了Dynamo［9］，通過綜合鍵／值存儲、改進的分布式哈希表、向量時鐘等技術實現了一個完全分布式、去中心化的高可用系統(tǒng)；開源界提出了類似Google 的Hadoop［10］技術框架體系，并在各個行業(yè)得到廣泛應用。雖然目前已經形成了大量的大數據存儲、管理和分析技術，但是這些技術大多數是針對文本數據、屬性數據、圖像圖形數據的，在空間大數據的處理方面往往不能夠直接應用。本文從空間數據的特點出發(fā)，結合空間數據分析的具體需求，提出基于 “分治網格”的空間大數據并行快速分析思路，并基于此思路搭建了基于Hadoop框架的分析原型系統(tǒng)，對關鍵技術進行驗證，驗證結果表明，利用該技術路線可以極大提升空間大數據的處理分析速度。

1 基于 “分治網格”的并行分析技術框架

1.1 總體思路

考慮空間數據海量，多圖層疊加分析計算需求普遍，傳統(tǒng)的單機計算模式難以滿足時效性要求的情況，本文提出基于 “分而治之”理念的空間數據并行化分析技術。其核心是按照一定的規(guī)則，將不同空間圖層數據劃分為不同的分治網格區(qū)域。在此基礎上，利用集群處理技術，對需要進行分析的空間圖層，按照各個分治網格進行分配調度，利用多臺計算資源進行并行計算，之后進行匯總，形成統(tǒng)一的結果，實現分析速度的大幅度提升，總體思路如圖1所示。

圖1 基于 “分治網格”的集群空間計算流程

1.2 分治網格劃分

在網格劃分方面，一般來說，網格劃分的越小，可以并行計算的基本單元也越小，可以并行的程度也越高。但同時，網格越少，網格數量就越大，繼而導致整體數據存儲量和前期切分工作量的大幅上升。在實際工作中，一般來說，對于局部范圍的分析，可以采用較小的網格，對于大面積的分析，可以采用較大的網格。為方便分析，可以將網格劃分為正方形格式。為方便不同比例尺網格的聚合和匯總，可以將網格體系設計為多級體系，上一級的網格可以由下一級別網格聚合而成。網格的劃分可以根據不同的需求進行定制，比如采用平面坐標形式，可以基于公里網格進行向下拆分和向上聚合，見表1。

表1 基于平面坐標的多級分治網格劃分

分治網格劃分也可以結合計算機中二進制計算特點，采用四分方式，下級網格面積為上級網格面積的1／4，方便多級網格的定位。

1.3 網格大小選取

網格劃分后，在并行計算時，首先需要確定分治網格的大小。分治網格的大小直接影響著并行計算的性能。如果將全國劃分為一個網格，則無法并行，計算模式退回為單機運行模式；如果網格劃分到像素級別，則并行程度可以極大提升，但是計算任務數量又過大，導致運行額外開銷增高。根據集群計算的特點，一般可以考慮按照一個分治網格內的要素數量進行網格大小的選取。如根據計算機性能，如果總要素數量為300 百萬，有10 個并行處理節(jié)點，則平均每個節(jié)點需要處理30萬個要素分析。另外一種方式就是劃分為10個左右的網格，每個任務負責一個網格的處理。但這種方式中，如果某一網格運算量較少，任務結束后就會造成資源的浪費。因此應該適當加大網格數量，如可以讓每個節(jié)點每次處理1萬個左右的要素，也就是網格數量大約在300個左右。這種模式下，10個節(jié)點并行進行300左右的并行任務。總體上看，網格大小的選取是一個和數據特點密切相關的工作，在具體工作中可以根據實際情況進行動態(tài)的優(yōu)化。

1.4 空間數據的預處理

由于很多空間數據當前往往采用數據庫形式存儲，但是如果直接在集群環(huán)境下由各個任務讀取數據庫數據并進行分析，會導致數據庫成為整個分析的瓶頸。因此有必要對數據庫中的數據進行處理。預處理工作包括基于分治網格的圖層分格、分格圖層的分區(qū)存儲、分格圖層的索引建立等多個工作。分格主要是將網格和圖層進行空間疊加，將原圖層拆分為每個網格一個圖層的格式。分區(qū)存儲是指將分格后的圖層進行格式轉換，導入到分布式的分區(qū)行式或者列式存儲系統(tǒng)中。索引建立是指在分區(qū)存儲的基礎上，利用空間四分樹及其它索引方式，建立空間數據的索引，提升后續(xù)分析效率。

1.5 集群式空間計算方式

為應對海量數據的處理計算能力的需求，可以采用集群化計算技術，將不同圖層和網格的疊加分析任務并行化，利用多個節(jié)點的計算能力并行處理，解決計算能力不足。在集群化處理方面，可以采用當前大數據技術體系中的Map Reduce計算模式，即：將大的計算任務分解為小的三類任務，總體分解任務、單個執(zhí)行任務、數據匯總任務。總體分解任務負責將大的任務計算的環(huán)境、數據進行拆解分發(fā)，具體任務可以在多個節(jié)點上進行執(zhí)行，數據匯總任務負責將各個子任務的數據進行匯總形成最終結果，并進行其它的清理工作。通過此類Map Reduce計算方式的應用，可以突破以往單機計算能力不足的缺陷。

2 初步實現及性能評價

2.1 初步實現

基于上述框架，本文搭建了原型系統(tǒng)，對本文提出的關鍵技術進行驗證。原型系統(tǒng)總體結構和采用的具體技術如圖2所示。

圖2 原型系統(tǒng)技術架構

通過數據抽取工具，將兩年空間土地利用變更調查Shapefile文件數據導入的Oracle空間數據庫中，之后利用數據轉換工具，將關系數據庫表數據轉換為CSV 文件，并將文件存儲到HDFS分布式文件系統(tǒng)之中。之后基于ESRI GisTool for Hadoop，開發(fā)基于格網的并行空間數據疊加分析工具，分析結果通過并行程序存儲到結果數據庫，供其它分析引擎和顯示引擎進行分析和展示。

2.2 性能評價

2.2.1 空間疊加運行時間比較

本研究中選取某試點區(qū)域兩年的土地利用變更調查數據樣本數據。每年的利用變更調查數據包含約70萬圖斑數據。原始Shape矢量數據每個約324MB，轉換為CSV 文件后每個文件大小約740 MB。本研究中，基于Hadoop 搭建1個主節(jié)點、3個數據節(jié)點的Hadoop集群環(huán)境，選取缺省的HDFS文件塊大小為64 MB。每個數據節(jié)點配置1顆4核CPU、8G 內存、1TB 硬盤和千兆網卡。在分析中，選取10公里網格作為分析單元。在設計Map Reduce程序實例中，兩年土地利用空間數據按照所相交10公里網格進行分配，凡是與同一網格相交的圖斑，所相交部分統(tǒng)一被分發(fā)至某一Reducer任務進行疊加計算。

本研究中，分別在單機環(huán)境、2個數據節(jié)點和3個計算節(jié)點環(huán)境下 （12個Mapper任務和24個Reducer任務），對上述土地利用數據進行分析，運行時間比較如圖3所示。

圖3 不同環(huán)境下土地利用變更數據疊加分析時間比較

通過分析，可以看出利用ArcGIS10.0，對兩年土地利用圖斑數據進行空間相交分析 （Join），在單臺PC 計算機，1顆4核主頻3.1GHZ CPU，8GB內存，1TB SATA 7.2K rpm 硬盤，Windows 7 64 位環(huán)境下，運行時間約15 min，運行期間CPU 使用率最高約76%，內存使用率約30%。利用Hadoop的Map Reduce技術，在單機 （單節(jié)點－偽分布式）環(huán)境下，完成同樣分析，需要時間約為35min。可見，Hadoop在單機環(huán)境下 （偽分布式環(huán)境，namenode和datanode均在該改服務器上）的性能比傳統(tǒng)的ArcGIS 分析更慢。這主要是由于Hadoop的Map Reduce技術主要是利用并行來實現效率的提升，但為實現并行，本身引入一定的額外處理負擔，導致單機環(huán)境性能明顯低于傳統(tǒng)技術方式。當將分析程序在2個數據節(jié)點的環(huán)境下時，可以實現性能的提升，Hadoop雙節(jié)點環(huán)境下，同樣的分析任務可以在9 min左右完成，性能超過單機環(huán)境下的ArcGIS。這主要是由于兩個節(jié)點上，通過Map Reduce，生成了12個Reducer任務，這12個Reducer任務被分配到兩臺數據節(jié)點的8個CPU 內核上進行預算，實現了同時多個任務并行計算，從而縮減了運行時間。繼而，將任務提交到3 個數據節(jié)點，啟用24 個Reducer后，運行任務可以在5 min左右完成，單機運行時間縮短為ArcGIS的1／3。由此可見，利用Hadoop的并行處理，可以將大空間圖層的分析效率大幅提升，滿足海量數據的分析需求。

2.2.2 網格劃分對運行時間的影響分析

在實際分析中，網格大小劃分同運行時間有直接的關系。一般來說，網格數量的多少應根據計算集群的節(jié)點數量進行。圖4顯示了在3個Hadoop集群節(jié)點、12個Mapper任務、24個Reducer任務配置下，不同網格大小劃分對應的土地利用圖層數據相交操作所需的時間。不同大小的網格數量見表2。

圖4 不同環(huán)境下土地利用變更數據疊加分析時間比較

表2 不同大小的網格數量

由圖4可以看出，網格數量和運行時間不是簡單的線性關系。當網格是10公里網格時，運行時間最小。更小的網格劃分時，運行時間有所延長，但延長量不大。當網格劃分更大時，運行時間也會延長，而且延長量較大。這主要是由于網格主要是用于拆分數據，使得同一網格內的要素可以獨立進行處理。正常情況下，當網格數量低于Reducer任務數量時，會造成部分Reducer任務沒有需要處理的數據，導致資源浪費。當網格數量高于Reducer任務時，每個網格由一個獨立的Reducer任務對其進行處理。為了保障網格數量高于Reducer任務數量時的Reducer任務處理量相對均衡，一般可以考慮網格數量是Reducer任務的整數倍數。同時，由于網格內的要素數量不同，為了避免一個Reducer任務處理的網格數量相同，但網格內要素量差別較大的問題，可以使用隨機算法分配網格到不同的Reducer任務上，并且使網格數量級是Reducer任務數量的10倍左右，這樣統(tǒng)計上看，負載不平衡程度可以控制在10%以下。同時，網格也不應該太小，過小的網格會導致按網格數據分發(fā)任務到Reducer任務時排序工作量加大，導致系統(tǒng)運行時間加長。一般來說，每個網格內的要素數量最好高于1萬，但低于10萬，這樣Reducer任務可以利用內存空間索引技術，快速進行空間疊加操作。

2.2.3 Mapper任務數量對運行時間的影響

在Hadoop環(huán)境中，Mapper和Reducer任務數量對于任務的執(zhí)行時間有直接影響。本研究中，Mapper任務主要負責將原始數據按照網格范圍，分發(fā)到不同的Reducer任務上；Reducer任務主要負責將某一網格內的兩年的土地利用圖斑進行疊加計算。圖5顯示了在3個數據節(jié)點、固定Reducer為24的情況下，不同數量的Mapper任務對運行時間的影響。

圖5 不同數量的Mapper任務對運行時間的影響／s

由于本研究中選取的文件塊大小為64 MB，輸入文件為740 MB左右，每個文件大約被拆分為12 個大小為64 MB的文件塊。對于沒有文件塊，Hadoop缺省啟用至少1個Mapper任務。缺省的12 個Mapper任務下 （24 個Reducer），系統(tǒng)運行時間為311s。實驗中也可以增加Mapper數量，為每一個文件塊配置2個Mapper任務，總Mapper任務為24個時，系統(tǒng)運行時間為435s。通過以上分析，可以看出，Mapper任務數量對系統(tǒng)運行性能影響不大。這主要是由于Mapper任務負責讀取輸入的數據文件，并將數據文件進行分發(fā)。分發(fā)階段的主要時間消耗為文件讀取和網絡通信，計算量小，加大Mapper數量并不會減少文件讀取的網絡時間，反而會加大Mapper的管理負擔，延長系統(tǒng)運行時間。因此，在實際圖層疊加工作中，可以考慮按照文件塊數量，每個文件塊配置一個Mapper任務，這個也是Hadoop中的缺省配置。

2.2.4 Reducer任務數量對運行時間的影響

圖6顯示了在3個節(jié)點，12個Mapper任務的情況下，不同數量的Reducer任務對運行時間的影響。

圖6 不同數量的Reducer任務對運行時間的影響／s

從圖6可以看出，Reducer任務的數量直接影響運行時間。當使用1 個Reducer任務的時候，網格內的疊加分析均由該Reducer任務完成。而一個Reducer任務只能運行在一臺數據節(jié)點，且無法完全利用多核計算資源，導致運行時間較長。當Reducer任務數量增加時，多個Reducer任務可以同時在多臺數據節(jié)點上運行，達到并行處理效果，縮短運算時間。由上圖可以看出，Reducer任務為3時，運行時間縮短為10 min左右。隨著Reducer任務數量的增加，并行程度加大，運行時間縮短。當Reducer任務達到24時，運行時間降為約5 min。這時的CPU 利用率基本達到飽和。如果進一步加大Reducer任務數量，發(fā)現處理時間反而延長，在Reducer任務數量為48個時，運行時間變?yōu)?min左右，這主要是由于CPU 利用飽和情況下，繼續(xù)增加Reducer任務數量，加大了任務分發(fā)管理和額外負擔，反而導致性能下降。一般來說，Reducer任務的數量配置應該結合CPU 數量和處理能力進行，要保證CPU 利用率相對飽和的情況下，減少Reducer任務數量。對于空間數據分析，缺省可以考慮1核CPU 對應2個Reducer任務。

3 結束語

傳統(tǒng)的空間數據分析技術非常成熟，對中小量空間數據分析較為實用，但是對空間大數據在數據存儲、計算方式、分析技術方面尚存在不足。針對這些問題，本文提出了基于 “分治網格”的空間大數據快速分析思路和技術框架，初步實現了原型系統(tǒng)，并基于原型系統(tǒng)以土地利用變更調查數據疊加分析為實例，對關鍵技術進行了驗證。實例驗證結果表明，利用本研究提出的技術路線和框架，可以極大提升海量空間數據的處理分析速度。本研究提出的基于 “分治網格”理念和空間大數據分析技術對海量空間數據的開發(fā)利用有著積極意義。

［1］ZHANG Xiaoxiang.Spatial analysis in the era of big data ［J］.Geomatics and Information Science of Wuhan University，2014，39（6）：655－659（in Chinese）.［張曉祥.大數據時代的空間分析［J］.武漢大學學報（信息科學版），2014，39 （6）：655－659.］

［2］Tong D，Murray AT.Spatial optimization in geography ［J］.Annals of the Association of American Geographers，2012，102（6）：1290－1309.

［3］YIN Fang，FENG Min，ZHU Yunqiang，et al.Research on vector spatial data distributed computing using Hadoop projects［J］.CEA，2013，49 （16）：25－29 （in Chinese）. ［尹芳，馮敏，諸云強，等.基于開源Hadoop的矢量空間數據分布式處理研究 ［J］.計算機工程與應用，2013，49 （16）：25－29.］

［4］Ghemawat S，Gobioff H，Leung ST.The Google file system ［J］.ACM SIGOPS Operating Systems Review，2003，37 （5）：29－43.

［5］Chang F，Dean J，Ghemawat S，et al.Bigtable：A distributed storage system for structured data［J］.ACM Transactions on Computer Systems，2008，26 （2）：4－5.

［6］Melnik S，Gubarev A，Long JJ，et al.Dremel：Interactive analysis of web－scale datasets ［J］.Proceedings of the VLDB Endowment，2010，3 （1－2）：330－339.

［7］Isard M，Budiu M，Yu Y，et al.Dryad：Distributed dataparallel programs from sequential building blocks ［J］.ACM SIGOPS Operating Systems Review，2007，41 （3）：59－72.

［8］Beaver Doug.Finding a needle in haystack：Facebook’s Photo Storage［C］／／OSDI，2010.

［9］DeCandia Giuseppe.Dynamo：Amazon’s highly available keyvalue store ［J］.ACM SIGOPS Operating Systems Review，2007，41 （6）：205－220.

［10］Shvachko Konstantin.The hadoop distributed file system［C］／／IEEE 26th Symposium on Mass Storage Systems and Technologies.IEEE，2010：15－16.