文/俞志宏 栗國(guó)保 李少白

1 引言

地理信息技術(shù)的快速發(fā)展，使其信息化水平越來(lái)越高，隨之而來(lái)的是數(shù)據(jù)的爆炸式增長(zhǎng)，使得海量空間數(shù)據(jù)的存儲(chǔ)與查詢時(shí)效性面臨巨大挑戰(zhàn)。由于空間數(shù)據(jù)的特殊性，在存儲(chǔ)和管理方面也存在諸多的限制，而分布式技術(shù)的迅速發(fā)展，無(wú)疑為空間數(shù)據(jù)的存儲(chǔ)與管理提供了解決方法。ElasticSearch 作為一個(gè)分布式可擴(kuò)展的實(shí)時(shí)搜索和分析引擎，在海量數(shù)據(jù)的存儲(chǔ)與搜索方面得到廣泛應(yīng)用。由于ElasticSearch面向文檔的特性，使得它在海量空間數(shù)據(jù)的存儲(chǔ)方面也有很好的表現(xiàn)，但如何實(shí)現(xiàn)空間數(shù)據(jù)的高效查詢是業(yè)界研究的一個(gè)熱點(diǎn)問(wèn)題。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)大多建立樹(shù)的索引實(shí)現(xiàn)空間查詢，在面臨大數(shù)據(jù)量的查詢時(shí)其性能很難滿足實(shí)際需求，而傳統(tǒng)的空間索引很難應(yīng)用于非關(guān)系型數(shù)據(jù)庫(kù)中，所以需要對(duì)空間數(shù)據(jù)進(jìn)行轉(zhuǎn)換，將轉(zhuǎn)換后的數(shù)據(jù)作為索引字段以用于查詢。因此，本文依據(jù)ElasticSearch 的存儲(chǔ)特性，結(jié)合四叉樹(shù)網(wǎng)格編碼算法，將矢量數(shù)據(jù)進(jìn)行轉(zhuǎn)換，并構(gòu)建空間索引，以提升空間數(shù)據(jù)的查詢效率。在此基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了基于Spark 的空間數(shù)據(jù)分析的優(yōu)化方案，為海量空間數(shù)據(jù)的存儲(chǔ)與查詢分析提供了一種快速有效的解決方案。

2 四叉樹(shù)網(wǎng)格編碼算法

圖1：四叉樹(shù)網(wǎng)格編碼原理圖

由于四叉樹(shù)編碼算法原理較簡(jiǎn)單且容易實(shí)現(xiàn)，已被廣泛應(yīng)用于地理信息系統(tǒng)的業(yè)務(wù)處理中。該算法的基本思想是將一個(gè)已知范圍的空間劃分成四個(gè)相等的子空間，并按照此方式遞歸執(zhí)行，直到樹(shù)的層次達(dá)到指定的深度或滿足某種終止條件時(shí)則停止劃分。本文依據(jù)四叉樹(shù)編碼算法的思想，實(shí)現(xiàn)了利用平面直角坐標(biāo)系所劃分的四個(gè)象限作為編號(hào)的四叉樹(shù)編碼算法。該算法以全球矩形范圍（-180,90,180,-90）為基準(zhǔn)網(wǎng)格（可根據(jù)具體應(yīng)用場(chǎng)景調(diào)整矩形范圍），逐級(jí)四分，通過(guò)單個(gè)要素的最小外接矩形，計(jì)算落在各級(jí)網(wǎng)格的象限編號(hào)，將各級(jí)的象限編號(hào)按順序組合形成網(wǎng)格編碼，其編碼原理如圖1所示。

從圖1中可以看出該算法基于各級(jí)象限進(jìn)行編碼，計(jì)算出來(lái)的編碼值能夠表達(dá)圖形在每一級(jí)的格網(wǎng)位置。四叉樹(shù)編碼算法的處理流程可描述為：首先，算法根據(jù)輸入的幾何對(duì)象計(jì)算該對(duì)象的最小外接矩形；其次，根據(jù)最小外接矩形的頂點(diǎn)坐標(biāo)信息對(duì)其進(jìn)行遞歸編碼；最后，輸出幾何對(duì)象的編碼集合。在使用該算法對(duì)要素類進(jìn)行遞歸編碼的過(guò)程中，會(huì)存在一些線狀要素或面狀要素所跨范圍較大的情況，針對(duì)該情況算法會(huì)根據(jù)要素投射在當(dāng)前級(jí)別四叉樹(shù)格網(wǎng)中的位置，產(chǎn)生相應(yīng)的多個(gè)編碼值。當(dāng)網(wǎng)格劃分到一定的級(jí)別后，單個(gè)面狀要素和線狀要素生成的編碼個(gè)數(shù)也會(huì)增加，編碼數(shù)的增多會(huì)導(dǎo)致存儲(chǔ)的冗余數(shù)據(jù)增多。因此，所采用的格網(wǎng)編碼的長(zhǎng)度應(yīng)根據(jù)實(shí)際數(shù)據(jù)的特點(diǎn)進(jìn)行權(quán)衡，其遵循的原則是確保大部分圖形擁有一個(gè)編碼，允許少量的圖形擁有多個(gè)編碼。

3 空間數(shù)據(jù)存儲(chǔ)

Elasticsearch 是一個(gè)分布式、可擴(kuò)展、實(shí)時(shí)的搜索與數(shù)據(jù)分析引擎，能夠?yàn)楹Ａ繑?shù)據(jù)提供分布式存儲(chǔ)、搜索和快速分析的服務(wù)。因其強(qiáng)大的搜索與分析能力，已被成功用于很多海量數(shù)據(jù)的處理中，如新浪過(guò)億條的日志數(shù)據(jù)的實(shí)時(shí)分析。Elasticsearch 除能夠提供傳統(tǒng)數(shù)據(jù)庫(kù)很難實(shí)現(xiàn)的全文搜索功能外，還具備結(jié)構(gòu)化搜索、數(shù)據(jù)分析及復(fù)雜的語(yǔ)言處理等功能。

鑒于此，本文使用Elasticsearch 存儲(chǔ)空間數(shù)據(jù)，以充分利用Elasticsearch 強(qiáng)大的索引搜索功能，達(dá)到快速查詢指定數(shù)據(jù)的效果。雖然Elasticsearch 提供的搜索功能，能夠滿足空間數(shù)據(jù)基本屬性的快速查詢，但由于圖形數(shù)據(jù)是一組坐標(biāo)點(diǎn)的集合，直接對(duì)該字段進(jìn)行索引，并不能滿足圖形數(shù)據(jù)的查詢需求。因此，本文結(jié)合空間數(shù)據(jù)的特點(diǎn)及Elasticsearch 索引機(jī)制，提出基于四叉樹(shù)的網(wǎng)格編碼算法，根據(jù)圖形數(shù)據(jù)計(jì)算其網(wǎng)格編碼值，使用網(wǎng)格編碼值對(duì)圖形數(shù)據(jù)進(jìn)行索引?；谝陨显O(shè)計(jì)思想，空間數(shù)據(jù)在Elasticsearch 中的存儲(chǔ)形式如表1所示。表1表示的是一條空間數(shù)據(jù)在Elasticsearch 中的表示形式，在保留了空間數(shù)據(jù)原有屬性字段的基礎(chǔ)上添加了codes 字段，用于存儲(chǔ)圖形數(shù)據(jù)轉(zhuǎn)化成的編碼值集合，并指定該字段為索引字段。

4 基于Spark的空間數(shù)據(jù)分析方法

針對(duì)海量空間數(shù)據(jù)存儲(chǔ)問(wèn)題，上文中提出基于四叉樹(shù)網(wǎng)格編碼算法，并結(jié)合Elasticsearch 強(qiáng)大的搜索能力，解決了多應(yīng)用場(chǎng)景下空間數(shù)據(jù)的查詢性能問(wèn)題。但空間數(shù)據(jù)在執(zhí)行空間分析操作時(shí)，計(jì)算耗時(shí)較長(zhǎng)，尤其是參與計(jì)算的空間數(shù)據(jù)量較大時(shí)，空間分析操作需等待的時(shí)間更久，已不能滿足實(shí)際的生產(chǎn)需要。因此，本節(jié)在基于上文中提出的基于四叉樹(shù)網(wǎng)格編碼索引方案的基礎(chǔ)上，探討利用基于內(nèi)存的分布式計(jì)算引擎Spark 解決傳統(tǒng)模式下計(jì)算能力不足的問(wèn)題，并以空間分析中的空間裁切操作為例，驗(yàn)證基于Spark 的分布式空間分析的處理性能。

4.1 建立外部空間數(shù)據(jù)連接

上文中根據(jù)實(shí)際應(yīng)用需求提出基于四叉樹(shù)網(wǎng)格編碼的索引方案，用以提升多場(chǎng)景下的空間數(shù)據(jù)查詢效率。同樣的，也可以使用該索引方案提升空間數(shù)據(jù)分布式處理的效率，即從底圖數(shù)據(jù)檢索和外部空間數(shù)據(jù)預(yù)加載兩個(gè)方面著手，來(lái)減少參與計(jì)算的數(shù)據(jù)量，從而提升分布式處理的效率。在底圖數(shù)據(jù)檢索方面，對(duì)外部空間數(shù)據(jù)使用四叉樹(shù)編碼算法計(jì)算其編碼值，并根據(jù)編碼值從Elasticsearch 中檢索出與codes 字段前綴相同的數(shù)據(jù)，從而減少Spark分發(fā)數(shù)據(jù)時(shí)的數(shù)據(jù)量；在外部空間數(shù)據(jù)預(yù)加載方面，對(duì)外部空間數(shù)據(jù)進(jìn)行編碼，并建立編碼與外部要素的對(duì)應(yīng)關(guān)系集合，以便在Spark 開(kāi)始分布式計(jì)算時(shí)，能夠根據(jù)讀取的底圖要素的編碼值直接找到與其空間上相關(guān)的外部要素，減少程序遍歷計(jì)算的次數(shù)，從而提升空間數(shù)據(jù)分布式計(jì)算的性能。

表1：空間數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

表2：兩種方案處理空間裁切任務(wù)耗時(shí)情況表

4.2 空間數(shù)據(jù)分布式計(jì)算流程

圖2：基于Spark 空間數(shù)據(jù)裁切處理流程圖

本節(jié)以空間裁切的應(yīng)用場(chǎng)景為例，使用基于四叉樹(shù)網(wǎng)格編碼的索引方案，設(shè)計(jì)出基于Spark 的分布式空間數(shù)據(jù)處理方案。其處理流程為：

（1）程序讀取Kafka 隊(duì)列中監(jiān)測(cè)圖斑數(shù)據(jù)，并調(diào)用網(wǎng)格編碼算法計(jì)算出矢量數(shù)據(jù)中的網(wǎng)格編碼值，建立網(wǎng)格編碼值與外部圖斑數(shù)據(jù)的映射關(guān)系，存儲(chǔ)于Map 集合中；

（2）Elasticsearch 根據(jù)監(jiān)測(cè)圖斑編碼值集合，檢索出符合要求的底圖數(shù)據(jù)，并轉(zhuǎn)換成RDD，Spark 逐條讀取RDD 中的codes 字段的值，而后根據(jù)該編碼值從Map 集合中查找到與其有關(guān)聯(lián)的監(jiān)測(cè)圖斑，分別執(zhí)行空間裁切操作；

（3）輸出空間裁切后的相關(guān)數(shù)據(jù)?；赟park 空間數(shù)據(jù)裁切處理流程圖如圖2所示。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

本小節(jié)通過(guò)實(shí)驗(yàn)來(lái)測(cè)試本文提出的基于四叉樹(shù)網(wǎng)格編碼算法的空間數(shù)據(jù)存儲(chǔ)與分析方案在執(zhí)行效率上是否優(yōu)于傳統(tǒng)的空間數(shù)據(jù)存儲(chǔ)與分析方案?；贖adoop 2.7.3 搭建一個(gè)主節(jié)點(diǎn)，兩個(gè)數(shù)據(jù)節(jié)點(diǎn)的Hadoop 集群環(huán)境，并在該集群中部署Spark、Elasticsearch 環(huán)境，其中Spark 版本為2.3.0，Elasticsearch 版本為6.4.0。每個(gè)數(shù)據(jù)節(jié)點(diǎn)的配置信息為：1 顆8 核主頻1.70GHz 的CPU、125G 內(nèi)存、操作系統(tǒng)為CentOS7.3。測(cè)試數(shù)據(jù)使用了一個(gè)市的地類圖斑數(shù)據(jù)集作為底圖數(shù)據(jù)，其數(shù)據(jù)量為10 萬(wàn)條記錄，并按照本文提出的存儲(chǔ)方案，存儲(chǔ)于Elasticsearch 中。

5.2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文提出的空間數(shù)據(jù)處理方案的計(jì)算性能，所以本小節(jié)中設(shè)計(jì)了基于網(wǎng)格編碼索引的分布式處理方案與傳統(tǒng)的基于隨機(jī)散列的分布式處理方案的對(duì)比試驗(yàn)。為保證試驗(yàn)結(jié)果的可比性，底圖數(shù)據(jù)固定為一個(gè)市的地類圖斑數(shù)據(jù)，使用不同數(shù)據(jù)量的監(jiān)測(cè)圖斑對(duì)兩種方案進(jìn)行測(cè)試。兩種方案處理空間裁切任務(wù)的耗時(shí)情況如表2所示，其中基于隨機(jī)散列的分布式處理方案記作R-INDEX，基于網(wǎng)格編碼索引的分布式處理方案記作G-INDEX，花費(fèi)時(shí)間單位為毫秒。

從表中耗時(shí)情況可分析出當(dāng)選取的監(jiān)測(cè)圖斑逐漸增加時(shí)，兩套方案的處理時(shí)間都有所增加，但本文提出的G-INDEX 方案，在做空間數(shù)據(jù)裁切操作時(shí)所花費(fèi)的時(shí)間明顯低于R-INDEX 方案所花費(fèi)的時(shí)間，這表明本文提出基于四叉樹(shù)網(wǎng)格編碼空間索引方案要優(yōu)于傳統(tǒng)的基于隨機(jī)散列的處理方案。這是因?yàn)榛诰W(wǎng)格編碼的空間索引方案，在獲取到監(jiān)測(cè)圖斑后能夠根據(jù)生成的編碼值，從Elasticsearch 中快速檢索出與監(jiān)測(cè)圖斑數(shù)據(jù)相關(guān)的記錄，減少空間裁切操作時(shí)所處理的數(shù)據(jù)量，從而提升空間裁切處理效率。

6 結(jié)束語(yǔ)

本文在研究了Elasticsearch 基礎(chǔ)上，根據(jù)矢量數(shù)據(jù)的空間特性，提出基于四叉樹(shù)網(wǎng)格編碼索引方案；而后依據(jù)Spark 的分布式處理原理，設(shè)計(jì)出基于Spark 的空間數(shù)據(jù)處理優(yōu)化方案，并選取空間裁切作為應(yīng)用場(chǎng)景，驗(yàn)證了該優(yōu)化方案的有效性。