可擴(kuò)展的分布式矢量空間數(shù)據(jù)庫(kù)集群原型系統(tǒng)研究

彭 瑾，熊 偉，吳 燁，陳 犖

(國(guó)防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院， 湖南 長(zhǎng)沙 410073)

0 引 言

隨著空間數(shù)據(jù)的獲取手段的不斷豐富，基于海量空間數(shù)據(jù)的分析計(jì)算變得可行，時(shí)空大數(shù)據(jù)的時(shí)代已經(jīng)到來(lái)[1-2]。針對(duì)每天以PB級(jí)速度在增長(zhǎng)的地理數(shù)據(jù)集，傳統(tǒng)的基于單節(jié)點(diǎn)的空間數(shù)據(jù)庫(kù)服務(wù)模式已經(jīng)不能滿(mǎn)足大數(shù)據(jù)集的存儲(chǔ)和查詢(xún)處理需求，為此需要引入分布式系統(tǒng)對(duì)空間數(shù)據(jù)集進(jìn)行存儲(chǔ)和處理[3-5]。

如何對(duì)時(shí)空大數(shù)據(jù)集進(jìn)行劃分、存儲(chǔ)，成為提高分布式空間數(shù)據(jù)庫(kù)查詢(xún)處理性能的關(guān)鍵問(wèn)題。SpatialHadoop[6]使用的是HDFS的存儲(chǔ)系統(tǒng)，它是將輸入的數(shù)據(jù)或者文件默認(rèn)的劃分成64M的數(shù)據(jù)塊，雖然這對(duì)于存儲(chǔ)大量需批量處理的數(shù)據(jù)是一種好的解決辦法，但是若對(duì)于文件大小不固定且小文件數(shù)量很多的情況增加了一定的開(kāi)銷(xiāo)，Hadoop-GIS[7]中，對(duì)這一方法進(jìn)行了改進(jìn)，首先它將矢量數(shù)據(jù)的點(diǎn)、線(xiàn)、面分開(kāi)存儲(chǔ)，并將其用均勻網(wǎng)格的方式劃分，再計(jì)算每個(gè)網(wǎng)格中的密度，選定一個(gè)閾值，大于此閾值的數(shù)據(jù)再按照x或者y軸進(jìn)行分割，但是該方法中網(wǎng)格大小需要根據(jù)數(shù)據(jù)集具體情況來(lái)確定。而在MongDB[8-9]中，是從數(shù)據(jù)集中選擇一個(gè)鍵值（屬性）對(duì)數(shù)據(jù)進(jìn)行分片，利用這個(gè)鍵值來(lái)分割數(shù)據(jù)。但是這樣的劃分只考慮到了數(shù)據(jù)量大小的問(wèn)題，并沒(méi)有考慮到數(shù)據(jù)的空間特性，不能適應(yīng)復(fù)雜的查詢(xún)問(wèn)題，沒(méi)有很好的擴(kuò)展性。中國(guó)科學(xué)院大學(xué)陳達(dá)倫采用數(shù)據(jù)庫(kù)中間件方式實(shí)現(xiàn)分布式空間查詢(xún)集群原型系統(tǒng)GeoMPP空間數(shù)據(jù)庫(kù)，但是其查詢(xún)性能通過(guò)中間件層有所消耗。

本文基于Share-Nothing的開(kāi)源數(shù)據(jù)庫(kù)Postgresql集群體系結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)了基于Geohash的矢量空間數(shù)據(jù)分片存儲(chǔ)方法，基于該分片方法實(shí)現(xiàn)了空間數(shù)據(jù)的并行導(dǎo)入，最后實(shí)現(xiàn)了分布式矢量空間查詢(xún)處理。實(shí)驗(yàn)表明，并行導(dǎo)入大數(shù)據(jù)集至分布式數(shù)據(jù)庫(kù)能提高其導(dǎo)入數(shù)據(jù)的性能，同時(shí)基于Geohash 劃分方法進(jìn)行分布式存儲(chǔ)的空間數(shù)據(jù)庫(kù)能夠提升空間查詢(xún)性能和并發(fā)訪(fǎng)問(wèn)性能。

1 擴(kuò)展的集群體系結(jié)構(gòu)

圖1顯示了由許多獨(dú)立的計(jì)算機(jī)組成的Postgresql集群體系結(jié)構(gòu)，這種結(jié)構(gòu)具有高度可擴(kuò)展性，可以在任意時(shí)間內(nèi)增加集群的數(shù)量以提高查詢(xún)的性能。同時(shí)，主節(jié)點(diǎn)保存從節(jié)點(diǎn)的元數(shù)據(jù)信息，當(dāng)在主節(jié)點(diǎn)執(zhí)行相關(guān)查詢(xún)命令后，可以獲得各個(gè)從節(jié)點(diǎn)的活動(dòng)狀態(tài)以及其存儲(chǔ)的表信息。因此，當(dāng)用戶(hù)進(jìn)行一個(gè)查詢(xún)時(shí)，主節(jié)點(diǎn)將查詢(xún)劃分成若干查詢(xún)片段，每一個(gè)查詢(xún)片段能夠獨(dú)立地運(yùn)行在從節(jié)點(diǎn)的相關(guān)表碎片上，利用相關(guān)從節(jié)點(diǎn)的處理能力來(lái)進(jìn)行分布式查詢(xún)。同時(shí)由于從節(jié)點(diǎn)是以表的形式存儲(chǔ)數(shù)據(jù)碎片，因此，每個(gè)從節(jié)點(diǎn)均支持局部索引來(lái)提高其查詢(xún)效率。最終，當(dāng)從節(jié)點(diǎn)結(jié)束查詢(xún)后將結(jié)果提交給主節(jié)點(diǎn)，由主節(jié)點(diǎn)進(jìn)行合并并返回給用戶(hù)完成一次查詢(xún)。

圖1 Postgresql集群體系結(jié)構(gòu)Fig.1 Postgresql cluster architecture

2 分布式空間數(shù)據(jù)庫(kù)集群關(guān)鍵技術(shù)

2.1 空間數(shù)據(jù)分片策略

空間數(shù)據(jù)分片策略是根據(jù)Geohash算法對(duì)大數(shù)據(jù)集進(jìn)行空間劃分，利用集群對(duì)分片數(shù)據(jù)進(jìn)行存儲(chǔ)管理，當(dāng)客戶(hù)端向集群發(fā)送查詢(xún)請(qǐng)求時(shí)，主節(jié)點(diǎn)將用戶(hù)的請(qǐng)求分發(fā)到各個(gè)從節(jié)點(diǎn)上進(jìn)行并行查詢(xún)，從節(jié)點(diǎn)再將查詢(xún)結(jié)果傳回主節(jié)點(diǎn)，主節(jié)點(diǎn)接收返回的結(jié)果合并后提交給用戶(hù)。

數(shù)據(jù)分片又稱(chēng)數(shù)據(jù)劃分，是利用一定策略將較大的數(shù)據(jù)分割成n個(gè)不相交的數(shù)據(jù)塊，為數(shù)據(jù)的分布式存儲(chǔ)及并行傳輸提供基礎(chǔ)。良好的空間數(shù)據(jù)劃分策略應(yīng)滿(mǎn)足兩個(gè)基本原則：邏輯的無(wú)縫保持性和空間對(duì)象的不分割性[10-11]。典型的空間數(shù)據(jù)分割方法主要是將整個(gè)空間區(qū)域分割成網(wǎng)格，并將空間對(duì)象根據(jù)其位置分配到不同的節(jié)點(diǎn)中。但是，由于空間對(duì)象不均勻分布的現(xiàn)象非常普遍，單個(gè)空間對(duì)象可能與多個(gè)網(wǎng)格相交，造成了分配方式的復(fù)雜性[12]。因此，本文主要是先根據(jù)單個(gè)空間對(duì)象的最小包圍框求出其質(zhì)心，再對(duì)其質(zhì)心使用了Geohash算法得到其編碼，對(duì)數(shù)據(jù)進(jìn)行分片。Geohash是一種地理編碼，它可以把二維的經(jīng)緯度坐標(biāo)按照精度要求對(duì)其編碼成字符串。通過(guò)Geohash編碼后的數(shù)據(jù)，空間上相鄰的位置在編碼上有相同的前綴，使之在解決區(qū)域搜索的問(wèn)題上具有明顯優(yōu)勢(shì)[13]。其過(guò)程如下：首先將經(jīng)度范圍[-180，180]平分成兩個(gè)區(qū)間，如果經(jīng)度坐標(biāo)位于前一個(gè)區(qū)間則編碼為0，否則編碼為1，之后按照所要求的精度將區(qū)間進(jìn)行若干次劃分并更改其編碼值，對(duì)緯度進(jìn)行同樣的算法進(jìn)行編碼。對(duì)于分別得到的經(jīng)緯度編碼進(jìn)行合并，奇數(shù)位是緯度，偶數(shù)位是經(jīng)度，最后用0～9、b～z（去掉a,i,o）這32個(gè)字母進(jìn)行base32編碼得到目標(biāo)對(duì)象的Geohash值[14]，然后對(duì)Geohash進(jìn)行排序，得到預(yù)處理后的數(shù)據(jù)集。

2.2 空間數(shù)據(jù)并行導(dǎo)入方法

對(duì)于單個(gè)較大的空間數(shù)據(jù)，相較于普通數(shù)據(jù)，其導(dǎo)入性能往往較低。為了解決這一問(wèn)題，主要是把按照一定策略分成邏輯片段的數(shù)據(jù)，通過(guò)傳統(tǒng)的輪詢(xún)、哈希、范圍等方法將分片合并，并行地傳輸至不同的物理節(jié)點(diǎn)上。輪詢(xún)方法首先將分片按行編號(hào)，然后使用輪詢(xún)算法將分片映射到不同的物理節(jié)點(diǎn)，哈希方法與輪詢(xún)方法一樣，先進(jìn)行按行編號(hào)，再用哈希算法將分片映射到不同的節(jié)點(diǎn)上。但是，對(duì)于空間數(shù)據(jù)，使用輪詢(xún)方法和哈希方法可能將處于地理鄰近的分片映射到不同的節(jié)點(diǎn)中，不利于保持?jǐn)?shù)據(jù)的空間鄰近性。而范圍劃分，是先對(duì)記錄進(jìn)行排序，然后按照排序碼將其劃分成n個(gè)區(qū)域，并使得每個(gè)區(qū)域大致含有相同數(shù)目的記錄。這能較好地保證在某一屬性上，值相近的數(shù)據(jù)能處于同一節(jié)點(diǎn)中[15]。利用范圍劃分方法的這一特點(diǎn)，本文通過(guò)對(duì)數(shù)據(jù)進(jìn)行Geohash編碼后，按照其值進(jìn)行排序，根據(jù)范圍劃分的方法，通過(guò)程序?qū)?shù)據(jù)并行地分發(fā)至不同的物理節(jié)點(diǎn)，以提高大數(shù)據(jù)集的導(dǎo)入效率。上述方法保持了空間數(shù)據(jù)的地理特性，使得相近的空間數(shù)據(jù)盡可能地分布在同一個(gè)物理節(jié)點(diǎn)中。而最終的分片個(gè)數(shù)主要是由CPU的核數(shù)所確定，高效的算法應(yīng)保證節(jié)點(diǎn)中每個(gè)CPU都發(fā)揮其作用。因此，區(qū)域的數(shù)目可估計(jì)為CPU核數(shù)的2～4倍。圖2展示了對(duì)中國(guó)各省的面矢量進(jìn)行數(shù)據(jù)劃分、導(dǎo)入數(shù)據(jù)庫(kù)的過(guò)程。

圖2 數(shù)據(jù)劃分、導(dǎo)入總體流程Fig.2 Overall process of data partitioning and import

2.3 分布式空間查詢(xún)處理算法

對(duì)于分布式的空間數(shù)據(jù)庫(kù)而言，它是由N臺(tái)高性能計(jì)算機(jī)所構(gòu)成N個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)，這些數(shù)據(jù)庫(kù)節(jié)點(diǎn)構(gòu)成并行的數(shù)據(jù)庫(kù)服務(wù)器集群。但是對(duì)于客戶(hù)端而言，則是作為一個(gè)整體提供空間數(shù)據(jù)庫(kù)查詢(xún)服務(wù)[16]。以空間范圍查詢(xún)?yōu)槔?，它是給定多邊形查詢(xún)區(qū)域R和空間對(duì)象集M，進(jìn)行查詢(xún)時(shí)就是查找M中所有與R相交或者被R包含的空間對(duì)象[17]，其遍歷算法偽代碼，利用空間索引范圍查詢(xún)偽代碼分別見(jiàn)表1，表2。

表1 遍歷范圍查詢(xún)算法偽代碼Tab.1 Traversing range query pseudo code

表2 范圍查詢(xún)算法偽代碼Tab.2 Range query pseudo code

在分布式空間數(shù)據(jù)庫(kù)中的并行處理空間范圍查詢(xún)主要是將集群分成一個(gè)主節(jié)點(diǎn)和若干個(gè)從節(jié)點(diǎn)，主節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)只是用來(lái)存儲(chǔ)數(shù)據(jù)的元數(shù)據(jù)信息，當(dāng)主節(jié)點(diǎn)接收到命令后，并行的分發(fā)到從節(jié)點(diǎn)中，從節(jié)點(diǎn)在各自的數(shù)據(jù)庫(kù)中執(zhí)行主節(jié)點(diǎn)分發(fā)的命令，并將結(jié)果返回至主節(jié)點(diǎn)，由主節(jié)點(diǎn)將結(jié)果匯總后返回給用戶(hù)[18]，圖3展示了集群對(duì)于用戶(hù)所給定查詢(xún)的處理過(guò)程。

圖3 查詢(xún)處理過(guò)程Fig.3 Query processing

3 實(shí)驗(yàn)結(jié)果

為檢驗(yàn)集群在處理空間數(shù)據(jù)集，尤其是范圍查詢(xún)方面的性能，實(shí)驗(yàn)針對(duì)兩種不同的環(huán)境，即分別配置有5個(gè)節(jié)點(diǎn)的集群數(shù)據(jù)庫(kù)和單節(jié)點(diǎn)的數(shù)據(jù)庫(kù)，對(duì)比分析了上述兩者在真實(shí)數(shù)據(jù)集以及虛擬數(shù)據(jù)集下的數(shù)據(jù)導(dǎo)入、空間范圍查詢(xún)、并發(fā)查詢(xún)的性能。

3.1 測(cè)試環(huán)境與測(cè)試數(shù)據(jù)集

測(cè)試平臺(tái)的集群機(jī)器是由4個(gè)從節(jié)點(diǎn)1個(gè)主節(jié)點(diǎn)組成，所有節(jié)點(diǎn)都在Centos7.1操作系統(tǒng)下運(yùn)行。每個(gè)節(jié)點(diǎn)分別部署了Postgresql以及PostGIS空間數(shù)據(jù)庫(kù)。實(shí)驗(yàn)采用了兩個(gè)數(shù)據(jù)集：分別是某地區(qū)的面矢量數(shù)據(jù)集以及隨機(jī)生成的點(diǎn)數(shù)據(jù)集，具體的硬件配置以及數(shù)據(jù)集具體參數(shù)分別參見(jiàn)表3及表4。

表3 測(cè)試環(huán)境Tab.3 Testing environment

表4 實(shí)驗(yàn)數(shù)據(jù)集Tab.4 Experimental data sets

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

3.2.1 空間數(shù)據(jù)并行導(dǎo)入性能比較

矢量數(shù)據(jù)的并行導(dǎo)入是利用單客戶(hù)端多線(xiàn)程并發(fā)讀取空間數(shù)據(jù)片段到從節(jié)點(diǎn)空間數(shù)據(jù)庫(kù)中，對(duì)面數(shù)據(jù)集和點(diǎn)數(shù)據(jù)集使用不同的導(dǎo)入方法的性能比較如圖4所示。

圖4 數(shù)據(jù)導(dǎo)入性能Fig.4 Data import performance

圖4 中，是串行導(dǎo)入和并行導(dǎo)入方法性能對(duì)比。從圖中可以看出，兩個(gè)數(shù)據(jù)集，并行導(dǎo)入性能提升約是串行導(dǎo)入方法的3倍，所以通過(guò)將大數(shù)據(jù)集分割后直接導(dǎo)入子節(jié)點(diǎn)中，可以降低數(shù)據(jù)導(dǎo)入的時(shí)間，提高數(shù)據(jù)加載的效率。

3.2.2 空間數(shù)據(jù)劃分方法性能比較

對(duì)空間數(shù)據(jù)劃分方法的性能比較，主要是比較了：按照地理坐標(biāo)進(jìn)行排序的范圍劃分，按照數(shù)據(jù)集本身的主鍵進(jìn)行排序后的劃分，對(duì)地理坐標(biāo)值進(jìn)行哈希劃分以及對(duì)主鍵進(jìn)行哈希劃分這4種方式。圖5(a)反映了對(duì)面數(shù)據(jù)集采用4種方法進(jìn)行的20次隨機(jī)大小的范圍查詢(xún)，圖5(b)顯示的是對(duì)點(diǎn)數(shù)據(jù)集進(jìn)行20次隨機(jī)范圍查詢(xún)所用的平均時(shí)間。為了減少其緩存的影響，對(duì)于每一個(gè)隨機(jī)范圍框查詢(xún)均做了6次，去掉第一次的結(jié)果對(duì)后5次結(jié)果取平均作為其最終的執(zhí)行時(shí)間。同時(shí)為了降低其他因素的影響，本次劃分只將數(shù)據(jù)集分成了4份并行的導(dǎo)入到四臺(tái)從節(jié)點(diǎn)的數(shù)據(jù)庫(kù)中。

圖5 數(shù)據(jù)分片方式對(duì)性能的影響Fig.5 Eあect of the data slice method on performance

根據(jù)圖5可知，就范圍查詢(xún)而言，根據(jù)范圍劃分的分片方式要優(yōu)于其他的分片方式。這是因?yàn)橐罁?jù)地理坐標(biāo)的范圍劃分保留了數(shù)據(jù)的空間鄰近性，所以當(dāng)進(jìn)行范圍查詢(xún)時(shí)，使得查詢(xún)框落在了較少的節(jié)點(diǎn)中，減少了需要與主節(jié)點(diǎn)進(jìn)行通信的從節(jié)點(diǎn)的數(shù)目，降低了其開(kāi)銷(xiāo)，使得其查詢(xún)性能較高。

3.2.3 空間數(shù)據(jù)分片大小性能比較

圖6反映了對(duì)面數(shù)據(jù)集以及點(diǎn)數(shù)據(jù)集使用范圍劃分的分割方法時(shí)，分片數(shù)目對(duì)其查詢(xún)性能的影響。

由圖6可知，對(duì)于面數(shù)據(jù)集而言，當(dāng)分片數(shù)目是40～60個(gè)時(shí)，即CPU核數(shù)的3倍左右時(shí)，其查詢(xún)性能最優(yōu)，而對(duì)于點(diǎn)數(shù)據(jù)集而言，其性能最優(yōu)處的分片數(shù)目可達(dá)CPU核數(shù)的4倍。這是因?yàn)閱蝹€(gè)CPU核可同時(shí)處理2～4個(gè)任務(wù)，所以，當(dāng)分片數(shù)目是CPU核數(shù)的2～4倍時(shí)能夠最大效率地利用CPU，使得其性能較優(yōu)。

圖6 數(shù)據(jù)分片數(shù)量對(duì)性能的影響Fig.6 Eあect of the data slice number on performance

3.2.4 空間范圍查詢(xún)性能

本實(shí)驗(yàn)旨在比較單機(jī)與集群在單個(gè)范圍查詢(xún)時(shí)的性能，因此將集群中的數(shù)據(jù)進(jìn)行最優(yōu)分配后，對(duì)單機(jī)以及集群中的數(shù)據(jù)集根據(jù)其地理坐標(biāo)列構(gòu)建了GIST索引，分別對(duì)單機(jī)無(wú)索引、集群無(wú)索引、單機(jī)有索引、集群有索引4種情況隨機(jī)選取不同大小、位置的20個(gè)查詢(xún)窗口，以驗(yàn)證其在空間范圍查詢(xún)上的性能表現(xiàn)。圖7是對(duì)兩個(gè)數(shù)據(jù)集進(jìn)行了隨機(jī)，不同大小、位置的查詢(xún)窗口采用count(*)聚合函數(shù)作為返回結(jié)果的查詢(xún)時(shí)間。

圖7 空間范圍查詢(xún)Fig.7 Spatial extent query

通過(guò)上述實(shí)驗(yàn)可以看出在查詢(xún)窗口所包含的對(duì)象數(shù)目較小時(shí)（對(duì)于面數(shù)據(jù)集選擇率小于30%，對(duì)于點(diǎn)數(shù)據(jù)集則為小于25%時(shí)），在單機(jī)構(gòu)建索引后的查詢(xún)性能要略高于集群，選擇率越小，查詢(xún)性能差異越小。但是隨著選擇率增大，所返回點(diǎn)數(shù)的增多，并行查詢(xún)性能較串行查詢(xún)性能最多可提升接近10倍，而單機(jī)構(gòu)建索引后的查詢(xún)時(shí)間與未構(gòu)建索引的單機(jī)相比并沒(méi)有改善。

3.2.5 并發(fā)性能比較

本實(shí)驗(yàn)主要是編寫(xiě)程序來(lái)模擬多個(gè)用戶(hù)對(duì)數(shù)據(jù)庫(kù)進(jìn)行并發(fā)的隨機(jī)窗口查詢(xún)操作，圖8描述了兩個(gè)數(shù)據(jù)集中的數(shù)據(jù)在集群中未復(fù)制，復(fù)制1份，復(fù)制2份進(jìn)行分布后以及數(shù)據(jù)集在單機(jī)中分布后對(duì)并發(fā)查詢(xún)的性能比較。

圖8 并發(fā)性能Fig.8 Concurrent performance

從圖8可以看出，不論是在面數(shù)據(jù)集還是點(diǎn)數(shù)據(jù)集中，集群因?yàn)樵诓l(fā)查詢(xún)中分擔(dān)了數(shù)據(jù)庫(kù)的整體壓力，所以其并發(fā)性能都明顯優(yōu)于單機(jī)，在相同并發(fā)請(qǐng)求時(shí)，集群查詢(xún)響應(yīng)性能至少為單機(jī)響應(yīng)性能的2倍。但是為其創(chuàng)建副本后，并不會(huì)對(duì)并發(fā)性能帶來(lái)更多提升，因此對(duì)數(shù)據(jù)進(jìn)行副本復(fù)制操作，主要是提高了數(shù)據(jù)庫(kù)的容錯(cuò)能力。

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

在空間數(shù)據(jù)庫(kù)的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了基于Geohash劃分方法的分布式空間數(shù)據(jù)庫(kù)集群，基于該方法實(shí)現(xiàn)了空間數(shù)據(jù)在集群的并行導(dǎo)入。實(shí)驗(yàn)表明，并行導(dǎo)入方法具有良好的擴(kuò)展性，隨著集群節(jié)點(diǎn)數(shù)的增加，導(dǎo)入性能也相應(yīng)增加。當(dāng)選擇率大于30%時(shí)，該分布式空間數(shù)據(jù)庫(kù)集群的查詢(xún)處理能力較單機(jī)數(shù)據(jù)庫(kù)能夠提升10倍左右，滿(mǎn)足了在空間數(shù)據(jù)日益增長(zhǎng)情況下對(duì)查詢(xún)性能擴(kuò)展性的要求。此外，4個(gè)節(jié)點(diǎn)的空間數(shù)據(jù)庫(kù)集群的并發(fā)性能較單機(jī)數(shù)據(jù)庫(kù)提升2倍，表明采用空間數(shù)據(jù)劃分方法后有效提高了集群的擴(kuò)展性。

下一步將結(jié)合分布式內(nèi)存空間數(shù)據(jù)庫(kù)，進(jìn)一步提升集群的擴(kuò)展性。實(shí)現(xiàn)更豐富的查詢(xún)處理策略，以支持時(shí)空大數(shù)據(jù)背景下的高效空間分析。同時(shí)考慮合理的空間數(shù)據(jù)副本分布及部署策略，提高數(shù)據(jù)庫(kù)集群的可靠性。