陳業(yè)斌　劉　娜　徐　宏　劉　敏

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　安徽 馬鞍山 243032)

0　引　言

近年來(lái)，隨著信息技術(shù)的不斷發(fā)展，空間數(shù)據(jù)增長(zhǎng)迅速，傳統(tǒng)的數(shù)據(jù)處理方式不能滿足大量數(shù)據(jù)的分析處理需求，為了滿足日益增長(zhǎng)的信息需求，選擇合適的大數(shù)據(jù)分析處理平臺(tái)尤其重要。傳統(tǒng)的數(shù)據(jù)處理系統(tǒng)將數(shù)據(jù)存儲(chǔ)于外存中，再進(jìn)行數(shù)據(jù)處理解決問(wèn)題，當(dāng)傳統(tǒng)數(shù)據(jù)處理平臺(tái)處理大數(shù)據(jù)時(shí)，其計(jì)算能力的不足會(huì)導(dǎo)致系統(tǒng)性能隨著數(shù)據(jù)量的增大而急劇下降，在實(shí)際應(yīng)用中并不適用。

Spark是分布式內(nèi)存計(jì)算框架，具有高效性、高可靠性與高性能的特征，適用于大數(shù)據(jù)的數(shù)據(jù)分析和分布式并行處理。依靠HBase的分布式處理能力將單個(gè)任務(wù)分解為多個(gè)任務(wù)，使用集群計(jì)算的方式將被分解的任務(wù)分配給每個(gè)節(jié)點(diǎn)在內(nèi)存中進(jìn)行數(shù)據(jù)的并行處理，保證高可靠、高并發(fā)、低延遲地處理空間數(shù)據(jù)。Spark在大數(shù)據(jù)處理領(lǐng)域提出了彈性分布式數(shù)據(jù)集(RDD[1])的概念，將部分RDD數(shù)據(jù)集緩存于內(nèi)存中，在重用計(jì)算時(shí)具備一定程度的容錯(cuò)糾正機(jī)制[2]。因此，基于Spark的大數(shù)據(jù)處理平臺(tái)在計(jì)算處理數(shù)據(jù)時(shí)具有高可靠性與高性能。Spark中的Spark SQL組件使用SQL和DataFrame API兩類接口來(lái)處理結(jié)構(gòu)化數(shù)據(jù)，通過(guò)使用Spark SQL組件操作SQL語(yǔ)句處理數(shù)據(jù)能夠更方便地梳理數(shù)據(jù)間的關(guān)系[10]。

對(duì)于空間大數(shù)據(jù)的研究不斷發(fā)展，技術(shù)逐漸成熟。2004年，Google公司發(fā)表了其內(nèi)部設(shè)計(jì)的大數(shù)據(jù)處理平臺(tái)MapReduce[7,12]分布式計(jì)算模型、GFS[8]分布式文件系統(tǒng)、BigTable[9]分布式數(shù)據(jù)庫(kù)的論文，奠定了大數(shù)據(jù)處理框架的核心技術(shù)基礎(chǔ)[3,13-14]。

斯坦福大學(xué)Chu等在2006年NIPS會(huì)議發(fā)表的論文，對(duì)常用機(jī)器學(xué)習(xí)算法的形式進(jìn)行分析，基于簡(jiǎn)單通用具有自動(dòng)容錯(cuò)機(jī)制的MapReduce抽象提出了適用于海量數(shù)據(jù)的機(jī)器學(xué)習(xí)算法通用計(jì)算框架[4]。然而分布式數(shù)據(jù)處理框架可能存在著單點(diǎn)故障和磁盤(pán)IO效率低的情況，從而影響數(shù)據(jù)處理的效率。

2013年加州大學(xué)伯克利大學(xué)AMPLab實(shí)驗(yàn)室發(fā)布了新一代基于內(nèi)存計(jì)算模型的Spark分布式框架。該計(jì)算框架在開(kāi)源社區(qū)的共同努力下，形成了和Hadoop相互促進(jìn)的Spark生態(tài)圈，該生態(tài)圈包括Hadoop的HDFS分布式文件系統(tǒng)、實(shí)時(shí)計(jì)算框Streaming、機(jī)器學(xué)習(xí)包MLlib、圖計(jì)算GraphX、Spark SQL等，同時(shí)和Hadoop一樣支持HBase分布式數(shù)據(jù)庫(kù)[5]?；赟park框架能夠高效處理實(shí)時(shí)數(shù)據(jù)[11]。

為了提高數(shù)據(jù)索引的效率，本文提出了基于Spark數(shù)據(jù)處理框架結(jié)合SIMBA的思路對(duì)數(shù)據(jù)索引進(jìn)行優(yōu)化?；赗DD機(jī)制實(shí)現(xiàn)數(shù)據(jù)的自動(dòng)容錯(cuò)機(jī)制，使用現(xiàn)有的分布式內(nèi)存查詢分析引擎Spark SQL執(zhí)行查詢操作，基于Spark的優(yōu)化機(jī)制處理大數(shù)據(jù)下的查詢操作，高效準(zhǔn)確地完成查詢操作。

1　相關(guān)工作

本文基于Spark分布式計(jì)算處理框架與分布式空間數(shù)據(jù)分析系統(tǒng)SIMBA[6](Spatial In-Memory Big data Analytics)的思想優(yōu)化數(shù)據(jù)索引。Spark通過(guò)啟用內(nèi)存分布數(shù)據(jù)集，構(gòu)建了提供交互式查詢和優(yōu)化迭代工作負(fù)載的計(jì)算框架。Spark基于RDD的實(shí)現(xiàn)將分析處理產(chǎn)生的中間結(jié)果顯式地留在內(nèi)存中，改變了Hadoop大數(shù)據(jù)處理框架中出現(xiàn)的磁盤(pán)IO效率低的情況。

使用現(xiàn)有的Spark SQL查詢引擎中DataFrame數(shù)據(jù)組織處理結(jié)構(gòu)化大數(shù)據(jù)的模塊，Spark DataFrame以RDD為基礎(chǔ)，同時(shí)具有Schema信息，處理分布式大數(shù)據(jù)時(shí)通過(guò)將數(shù)據(jù)庫(kù)對(duì)象分類的方式，提高了數(shù)據(jù)批處理的效率。

對(duì)數(shù)據(jù)通過(guò)采用分區(qū)策略優(yōu)化數(shù)據(jù)分布，基于DataFrame將數(shù)據(jù)庫(kù)對(duì)象分類，提供完備的操作符用于處理數(shù)據(jù)集的方式，能夠提高查詢效率與改善查詢性能。

為了優(yōu)化在大數(shù)據(jù)下的數(shù)據(jù)索引，依據(jù)SIMBA的思想基礎(chǔ)，在RDD數(shù)據(jù)集中采取了過(guò)濾優(yōu)化和局部索引的策略，對(duì)Spark的內(nèi)核不作任何修改，以保證系統(tǒng)能夠無(wú)縫嵌入新版本的Spark生態(tài)系統(tǒng)。在基于Spark的大數(shù)據(jù)處理框架下展開(kāi)索引，能夠高效地確定數(shù)據(jù)集范圍內(nèi)的候選點(diǎn)。對(duì)計(jì)算機(jī)應(yīng)用與研究領(lǐng)域的大規(guī)模數(shù)據(jù)與復(fù)雜計(jì)算有極大的研究?jī)r(jià)值。

2　解決方案

在大數(shù)據(jù)索引中，為了改善系統(tǒng)性能，提出來(lái)索引優(yōu)化策略，采用SIMBA項(xiàng)目的思路在Spark中提出優(yōu)化策略，基于SQL創(chuàng)建索引并保存到內(nèi)存中，從而提高查詢性能和查詢吞吐量。在大數(shù)據(jù)研究領(lǐng)域，基于Spark系統(tǒng)存取數(shù)據(jù)能夠有效查找數(shù)據(jù)集中的數(shù)據(jù)。在空間范圍中展開(kāi)索引，為了提升索引效率和查詢性能，使用Spark SQL解析器執(zhí)行空間查詢操作，并吸納SIMBA開(kāi)源項(xiàng)目的思路，將空間進(jìn)行分區(qū)，提出全局過(guò)濾和局部空間索引兩種優(yōu)化策略，基于這些優(yōu)化策略提升了索引性能。

2.1　分　區(qū)

在Spark集群計(jì)算系統(tǒng)中，采用數(shù)據(jù)分區(qū)的方式優(yōu)化數(shù)據(jù)分布并采用操作符的方式處理數(shù)據(jù)，從而提高查詢效率，改善查詢性能。

對(duì)于分布式計(jì)算，采用Spark中Partitioner抽象類的RangePartitioner分區(qū)策略進(jìn)行分區(qū)，如圖1所示，使用分區(qū)的方式處理數(shù)據(jù)需要滿足分區(qū)大小、數(shù)據(jù)局部性、負(fù)載均衡三個(gè)條件[11]。首先采用RangePartitioner方式接受RDD數(shù)據(jù)集和數(shù)據(jù)集的范圍邊界傳值。接下來(lái)，基于調(diào)用預(yù)定義采樣率的采樣方法大致估算出數(shù)據(jù)分布。隨后將原始的RDD數(shù)據(jù)集劃分為多個(gè)分區(qū)，當(dāng)分區(qū)所包含的數(shù)據(jù)項(xiàng)超過(guò)了平均數(shù)量時(shí)，RangePartitioner將對(duì)當(dāng)前分區(qū)進(jìn)行重采樣?；赗angePartitioner分區(qū)能夠盡量保證分區(qū)中數(shù)據(jù)量分布均衡，分區(qū)之間排列有序?；谶@種采樣分區(qū)的方式進(jìn)行數(shù)據(jù)集分區(qū)，可以滿足系統(tǒng)分區(qū)的負(fù)載均衡，同時(shí)將空間位置相近的數(shù)據(jù)盡量相鄰，滿足數(shù)據(jù)分區(qū)的局部性。

圖1　數(shù)據(jù)分區(qū)策略

2.2　全局過(guò)濾

對(duì)數(shù)據(jù)集采用數(shù)據(jù)分區(qū)的方式將數(shù)據(jù)集分為多個(gè)大小相近的分區(qū)，雖然能夠改善查詢效率，然而在空間查詢時(shí)依然需要采用全局掃描的方式對(duì)數(shù)據(jù)進(jìn)行篩選。為了能夠更大程度地改善查詢性能，提高查詢效率，使用全局過(guò)濾的方式過(guò)濾數(shù)據(jù)，減少需要掃描的分區(qū)數(shù)量。使用RangePartitioner分區(qū)函數(shù)計(jì)算每個(gè)分區(qū)的邊界，并將每個(gè)分區(qū)的上界保存在一個(gè)邊界數(shù)組中，在空間查詢時(shí)，通過(guò)判斷查詢點(diǎn)所落在的分區(qū)邊界進(jìn)行分區(qū)剪枝，通過(guò)這種全局過(guò)濾的方式大幅度地降低掃描分區(qū)的數(shù)量，從而減少索引時(shí)間提升查詢效率。

2.3　局部索引

在空間查詢時(shí)，Spark數(shù)據(jù)處理框架通過(guò)在各分區(qū)數(shù)據(jù)集中建立線段樹(shù)的方式進(jìn)行空間索引，基于線段樹(shù)壓縮空間，快速查找到空間數(shù)據(jù)[14]。

使用線段樹(shù)索引，線段樹(shù)作為一種二叉搜索樹(shù)，其索引方式如圖2所示，首先依據(jù)分區(qū)中的邊界值根據(jù)上下界端點(diǎn)的特征計(jì)算出中間值，將其作為根節(jié)點(diǎn)，再根據(jù)中間值可以將空間范圍分為三部分：第一部分為左集合，包含右邊界小于中間值的空間范圍間隔；第二類為右集合，包含左邊界大小中間值的空間范圍間隔；第三類為中間集合，包含中間值落在其邊界內(nèi)的空間范圍間隔。使用線段樹(shù)進(jìn)行范圍查詢，通過(guò)對(duì)節(jié)點(diǎn)值進(jìn)行比較，小于節(jié)點(diǎn)值則進(jìn)入左子樹(shù)中進(jìn)行查找，大于節(jié)點(diǎn)值則進(jìn)入右子樹(shù)中查找，依次迭代比較，直到匹配到對(duì)應(yīng)的節(jié)點(diǎn)值。在定位到對(duì)應(yīng)葉節(jié)點(diǎn)后，線性遍歷葉節(jié)點(diǎn)中的RDD數(shù)據(jù)集，相較于全局線性遍歷提高了查詢效率，降低了時(shí)間復(fù)雜度。

圖2　線段樹(shù)索引示意圖

2.4　優(yōu)化策略

基于Spark處理框架的空間范圍查詢，如圖3流程所示。首先輸入查詢語(yǔ)句，使用DataFrames查詢引擎將查詢語(yǔ)句轉(zhuǎn)化為抽象語(yǔ)法樹(shù)。再使用Catalyst組件自帶規(guī)則解析查詢語(yǔ)句中對(duì)應(yīng)的表屬性及其查詢條件，從而追蹤到查詢數(shù)據(jù)源，并生成分析后的邏輯計(jì)劃。通過(guò)緩存管理機(jī)制Cache Manager和索引管理機(jī)制Index Manager檢查內(nèi)存中是否存在數(shù)據(jù)和索引，如果存在已經(jīng)建立好的索引則讀入，最后獲得滿足條件的查詢結(jié)果集。

圖3　查詢步驟

本系統(tǒng)基于Spark數(shù)據(jù)處理框架，將創(chuàng)建的索引容器均封裝為RDD抽象，所以具備RDD的容錯(cuò)機(jī)制，因此該系統(tǒng)在進(jìn)行空間查詢時(shí)具備一定的容錯(cuò)性。

3　查詢方法設(shè)計(jì)

3.1　集群計(jì)算

本系統(tǒng)基于Spark分布式計(jì)算框架，基于時(shí)空數(shù)據(jù)庫(kù)進(jìn)行參數(shù)化查詢，系統(tǒng)利用通用編程語(yǔ)言，通過(guò)集群內(nèi)存計(jì)算實(shí)現(xiàn)高效的數(shù)據(jù)處理及分析應(yīng)用。

本系統(tǒng)基于Spark的實(shí)現(xiàn)數(shù)據(jù)索引，能將處理分析產(chǎn)生的中間結(jié)果顯式地駐留在內(nèi)存中，通過(guò)分區(qū)策略來(lái)優(yōu)化數(shù)據(jù)分布，采用全局過(guò)濾與局部索引的方式完成數(shù)據(jù)索引。在空間范圍查詢時(shí)，對(duì)查詢進(jìn)行分析，嵌入空間索引優(yōu)化策略，利用系統(tǒng)的分布式計(jì)算方法處理時(shí)空數(shù)據(jù)庫(kù)，提高查詢的性能與效率。

3.2　系統(tǒng)架構(gòu)

本系統(tǒng)基于Spark 系統(tǒng)，依據(jù)Spark SQL執(zhí)行范圍查詢，具有高吞吐量和低延遲特性。

在本系統(tǒng)中通過(guò)使用Spark應(yīng)用程序的方式執(zhí)行空間范圍查詢，具體系統(tǒng)架構(gòu)如圖4所示，在Spark框架下使用Spark SQL解析器將查詢語(yǔ)句解析為抽象語(yǔ)法樹(shù)，使用Spark Catalyst優(yōu)化器執(zhí)行邏輯計(jì)劃生成。

圖4　Spark系統(tǒng)架構(gòu)

在物理計(jì)劃執(zhí)行階段，新建索引管理模塊Cache Manager和Index Manager用于執(zhí)行內(nèi)存和磁盤(pán)索引，對(duì)完成分區(qū)優(yōu)化的數(shù)據(jù)執(zhí)行查詢操作。本系統(tǒng)基于Spark中的Spark Catalyst和Spark SQL組件完成邏輯計(jì)劃，基于數(shù)據(jù)分區(qū)與索引管理模塊完成物理計(jì)劃，能夠更加高效、高性能地完成空間查詢。

3.2.1查詢方式

本系統(tǒng)基于Spark Catalyst展開(kāi)空間查詢，并通過(guò)索引管理機(jī)制對(duì)Spark SQL內(nèi)核的解析器執(zhí)行空間查詢，使得本系統(tǒng)在空間索引時(shí)能夠支持必要的關(guān)鍵字查詢。

索引時(shí)通過(guò)使用關(guān)鍵字確定數(shù)據(jù)集中的查詢對(duì)象，將查詢拓展為空間點(diǎn)查詢與空間范圍查詢，通過(guò)建立線段樹(shù)的方式提高查詢性能與查詢效率。

3.2.2關(guān)鍵字接口

在空間范圍查詢時(shí)，使用空間范圍關(guān)鍵字選擇結(jié)構(gòu)化表中查詢語(yǔ)言，使用空間點(diǎn)關(guān)鍵字表達(dá)空間對(duì)象，在查詢通過(guò)空間范圍的表達(dá)形式，在WHERE語(yǔ)句中優(yōu)先匹配進(jìn)行查詢。對(duì)于空間范圍查詢的表達(dá)形式如下所示：

POINT(point1,round1)

在系統(tǒng)中開(kāi)展的空間范圍查詢操作，空間范圍查詢?yōu)椴樵償?shù)據(jù)集中空間屬性落在指定空間范圍內(nèi)的所有記錄，具體索引表達(dá)形式如下：

SELECT * from locations

WHERE POINT(locations.point)

IN POINT({34,23},40)

3.2.3復(fù)合索引查詢

本系統(tǒng)空間范圍查詢基于Spark SQL的語(yǔ)法，通過(guò)索引管理機(jī)制在時(shí)空數(shù)據(jù)集上建立空間范圍索引，不但能夠執(zhí)行空間查詢還能夠執(zhí)行包含關(guān)鍵字的復(fù)合查詢。在執(zhí)行空間查詢中為了能夠提高查詢性能與查詢吞吐量，提出來(lái)建立線段樹(shù)的方式完成索引，具體查詢表達(dá)形式如下：

CREATE INDEX pointIndex ON locations(point)

USER INTERVALTREE

在復(fù)合查詢時(shí)，本系統(tǒng)基于空間關(guān)鍵字進(jìn)行查詢，能夠查詢時(shí)空數(shù)據(jù)集中落在空間范圍內(nèi)的所有記錄，并對(duì)結(jié)果集基于屬性id做GROUP操作，復(fù)合查詢表達(dá)形式如下：

SELECT locations.point from locations

WHERE POINT(locations.point)

IN POINT(point1,round)

GROUP BY locations.point

3.3　索引機(jī)制

本系統(tǒng)通過(guò)提供索引管理機(jī)制提升索引效率。基于索引管理模塊在時(shí)空數(shù)據(jù)集上建立空間索引，創(chuàng)建索引并保存在內(nèi)存中，建立包含空間查詢與空間查詢建立所依賴的RDD數(shù)據(jù)集。基于索引管理機(jī)制進(jìn)行空間索引，能夠快速定位數(shù)據(jù)集位置，從而實(shí)現(xiàn)較高的查詢吞吐量與較低的查詢延遲。

采用線段樹(shù)的思想設(shè)計(jì)索引。通過(guò)二分法構(gòu)造相應(yīng)區(qū)間，并構(gòu)造區(qū)間內(nèi)的子區(qū)間，將其存儲(chǔ)為新的節(jié)點(diǎn)。通過(guò)上下界的兩個(gè)端點(diǎn)能夠?qū)⒚總€(gè)節(jié)點(diǎn)區(qū)間定位到數(shù)據(jù)集中，通過(guò)SQL接口在各個(gè)分區(qū)數(shù)據(jù)集中建立對(duì)應(yīng)的空間索引?；诰€段樹(shù)進(jìn)行空間索引，能夠高效查詢到所有覆蓋在給定空間范圍的數(shù)據(jù)。

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

本文的測(cè)試平臺(tái)為十個(gè)節(jié)點(diǎn)構(gòu)建的集群運(yùn)行環(huán)境，在集群上運(yùn)行對(duì)比實(shí)驗(yàn)，其中的8Xeon E5-2620，2.00 GHz處理器，96 GB內(nèi)存。在這十個(gè)節(jié)點(diǎn)中均使用Ubuntu系統(tǒng)，在Ubuntu 14.04.2 LOS系統(tǒng)下搭建Apache Hadoop 2.4.1大數(shù)據(jù)處理框架，建立Apache Spark 1.5.2集群計(jì)算平臺(tái)，選擇具有2.00 GHz處理器和96 GB內(nèi)存的2臺(tái)機(jī)器中的一臺(tái)作為主節(jié)點(diǎn)，剩余機(jī)器作為從節(jié)點(diǎn)。構(gòu)建的Spark集群將以Standalone模式運(yùn)行，并配置所有的從節(jié)點(diǎn)最高可以使用15 GB內(nèi)存。

實(shí)驗(yàn)使用的真實(shí)數(shù)據(jù)集采用紐約出租車(chē)接單數(shù)據(jù)集為測(cè)試數(shù)據(jù)，包括2013年全年紐約市所有出租車(chē)的接單數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行去重處理和數(shù)據(jù)格式檢測(cè)，獲得包含1.7億條出租車(chē)接單記錄元組的有效實(shí)驗(yàn)數(shù)據(jù)集，每一條元組包含，出租車(chē)接單ID、接單開(kāi)始時(shí)間和接單結(jié)束時(shí)間。在實(shí)驗(yàn)中測(cè)試系統(tǒng)的空間點(diǎn)查詢和空間范圍查詢兩種查詢操作的效率，在本文中使用OS(Optimized Spark)表示優(yōu)化之后的Spark，將OS與對(duì)應(yīng)原生Spark(未被優(yōu)化的Spark)的基準(zhǔn)查詢效率進(jìn)行比較，通過(guò)比較查詢時(shí)的吞吐量和查詢延遲來(lái)評(píng)價(jià)優(yōu)化后的系統(tǒng)對(duì)數(shù)據(jù)索引性能的改善。每個(gè)測(cè)試基于500次實(shí)驗(yàn)進(jìn)行查詢，查詢效率按照吞吐量和查詢延遲進(jìn)行衡量：吞吐量=查詢數(shù)量/總執(zhí)行時(shí)間(min)；查詢延遲=總執(zhí)行時(shí)間(s)/查詢數(shù)量。

通過(guò)比較在數(shù)據(jù)集大小不同的情況下，原生Spark系統(tǒng)與OS系統(tǒng)進(jìn)行空間查詢時(shí)的查詢延遲與吞吐量的變化，對(duì)兩個(gè)系統(tǒng)進(jìn)行性能與效率的評(píng)價(jià)。如圖5所示，原生Spark系統(tǒng)與OS系統(tǒng)在數(shù)據(jù)集大小不斷增加的時(shí)候，查詢延遲的時(shí)間也不斷增加，相比于OS系統(tǒng)，原生Spark系統(tǒng)的延遲時(shí)間增長(zhǎng)率要遠(yuǎn)遠(yuǎn)高于OS系統(tǒng)。如圖6所示，是在不同數(shù)據(jù)集大小的情況下吞吐量的變化，隨著數(shù)據(jù)量的增長(zhǎng)，兩個(gè)系統(tǒng)的吞吐量都發(fā)生了一定程度的下降，然而OS系統(tǒng)依舊優(yōu)異于原生Spark系統(tǒng)。在空間點(diǎn)查詢時(shí)，OS系統(tǒng)的查詢操作包含全局過(guò)濾和分區(qū)查詢兩部分優(yōu)化，因此OS系統(tǒng)在查詢性能與效率上優(yōu)于原生Spark系統(tǒng)。

圖5　數(shù)據(jù)集大小對(duì)于查詢延遲的影響

圖6　數(shù)據(jù)集大小對(duì)于吞吐量的影響

對(duì)空間范圍查詢中，通過(guò)比較在不同數(shù)據(jù)量大小的情況下原生Spark系統(tǒng)與OS系統(tǒng)的查詢延遲時(shí)間與吞吐量判斷系統(tǒng)的性能差異。首先需要生成一個(gè)落在全局空間范圍的空間標(biāo)識(shí)，基于泰森多邊形將整個(gè)查詢空間劃分為多個(gè)多邊形區(qū)域?？臻g范圍查詢類似于空間點(diǎn)查詢，OS系統(tǒng)的查詢操作時(shí)依舊保證全局過(guò)濾和分區(qū)查詢兩部分優(yōu)化，如圖7、圖8所示，在執(zhí)行空間范圍查詢時(shí)，本系統(tǒng)的查詢效率依舊同樣優(yōu)于原生Spark SQL查詢策略。

圖7　數(shù)據(jù)集大小對(duì)于查詢延遲的影響

圖8　數(shù)據(jù)集大小對(duì)于吞吐量的影響

當(dāng)分區(qū)較大時(shí)，空間查詢的結(jié)果集可能覆蓋多個(gè)分區(qū)，可以通過(guò)固定數(shù)據(jù)集大小測(cè)試不同分區(qū)數(shù)量的情況下兩個(gè)系統(tǒng)的效率。如圖9、圖10所示，為不同分區(qū)下兩個(gè)系統(tǒng)的查詢延遲和吞吐量變化。由圖9、圖10可以觀察得出，OS系統(tǒng)在一定分區(qū)大小范圍內(nèi)，隨著分區(qū)數(shù)量的增大，查詢延遲呈現(xiàn)降低趨勢(shì)，吞吐量大小增長(zhǎng)。當(dāng)分區(qū)數(shù)量增大，分區(qū)大小過(guò)小時(shí)，空間范圍查詢覆蓋大量的分區(qū)，那么需要遍歷的數(shù)據(jù)量將會(huì)增多，因?yàn)閷?dǎo)致了查詢延遲的增長(zhǎng)，吞吐量下降，查詢性能的降低。原生Spark系統(tǒng)的查詢延遲和吞吐量的變化與分區(qū)數(shù)量無(wú)明顯關(guān)系，因?yàn)槭褂迷鶶park系統(tǒng)進(jìn)行查詢需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行遍歷，因此分區(qū)大小的改變不會(huì)對(duì)查詢性能產(chǎn)生影響。

圖9　分區(qū)大小對(duì)于查詢延遲的影響

圖10　分區(qū)大小對(duì)于吞吐量的影響

實(shí)驗(yàn)主要分為三組對(duì)比實(shí)驗(yàn)，第一組圖5、圖6，針對(duì)不同大小的數(shù)據(jù)集，在執(zhí)行空間查詢時(shí)OS系統(tǒng)與Spark SQL的執(zhí)行效率對(duì)比；第二組圖7、圖8，針對(duì)不同大小的數(shù)據(jù)集，在執(zhí)行空間范圍查詢時(shí)OS系統(tǒng)與原生Spark SQL程序的執(zhí)行效率對(duì)比；第三組圖9、圖10，針對(duì)不同大小的分區(qū)數(shù)量，在執(zhí)行空間查詢時(shí)本系統(tǒng)與原生Spark SQL程序的執(zhí)行效率對(duì)比。

5　結(jié)　語(yǔ)

本文提出了基于Spark的空間查詢擴(kuò)展系統(tǒng)OS，基于OS完成空間范圍查詢。使用Spark系統(tǒng)中的Spark Catalyst組件的SQL解析器的操作方式進(jìn)行查詢。在Spark 中嵌入索引管理機(jī)制，將其封裝在RDD內(nèi)，用于提高查詢效率。通過(guò)建立線段樹(shù)存儲(chǔ)數(shù)據(jù)的方式提高數(shù)據(jù)檢索的效率。對(duì)于數(shù)據(jù)預(yù)處理時(shí)采用RangePartitioner分區(qū)策略的方式對(duì)數(shù)據(jù)進(jìn)行分區(qū)，基于全局過(guò)濾和局部索引進(jìn)行查詢。保證該系統(tǒng)在進(jìn)行查詢操作時(shí)能夠保持高吞吐量和低延遲特性，提高查詢效率。

將在OS與Spark下進(jìn)行查詢實(shí)驗(yàn)的性能進(jìn)行比較，由實(shí)驗(yàn)結(jié)果分析，隨數(shù)據(jù)集大小的增加，基于該拓展系統(tǒng)(OS)完成的查詢操作在查詢延遲與吞吐量檢測(cè)上均優(yōu)于原生Spark系統(tǒng)，當(dāng)分區(qū)數(shù)量發(fā)生變化時(shí)，該拓展系統(tǒng)(OS)在性能上依舊優(yōu)于原生Spark系統(tǒng)。

雖然該拓展系統(tǒng)取得了初步的研究成果，但是在未來(lái)的工作當(dāng)中，本系統(tǒng)仍有較多需要拓展改進(jìn)的部分，在系統(tǒng)中可以增加時(shí)態(tài)查詢，時(shí)態(tài)查詢也是時(shí)空數(shù)據(jù)庫(kù)中的研究重點(diǎn)。與此同時(shí)，系統(tǒng)優(yōu)化也是未來(lái)的研究中不可或缺的部分，通過(guò)嵌入更多的優(yōu)化策略提高索引的效率與性能。

[1] Zaharia M,Chowdhury M,Das T,et al.Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2012:2-2.

[2] 高官濤,鄭小盈,宋應(yīng)文,等.基于Spark MapReduce框架的分布式渲染系統(tǒng)研究[J].軟件導(dǎo)刊,2013,12(12):26-29.

[3] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[C]//Conference on Symposium on Opearting Systems Design & Implementation.USENIX Association,2008:10-10.

[4] Chu C T,Kim S K,Lin Y A,et al.MapReduce for machine learning on multicore[C]//Conference and Workshop on Neural Information Processing Systems,NIPS,2006,6:281-288.

[5] Zaharia M,Das T,Li H,et al.Discretized streams:fault-tolerant streaming computation at scale[C]//Twenty-Fourth ACM Symposium on Operating Systems Principles.ACM,2013:423-438.

[6] Xie D,Li F,Yao B,et al.Simba:Efficient In-Memory Spatial Analytics[C]//International Conference on Management of Data.ACM,2016:1071-1085.

[7] 張宇,程久軍.基于MapReduce的矩陣分解推薦算法研究[J].計(jì)算機(jī)科學(xué),2013,40(1):19-21.

[8] Scott M L,Peterson L L.Proceedings of the 19th ACM Symposium on Operating Systems Principles 2003,SOSP 2003,Bolton Landing,NY,USA,October 19-22,2003[C]//Acm Symposium on Operating Systems Principles,2003(53):113-126.

[9] 趙宇蘭,柳欣.基于連接依賴信息的分布式連接查詢優(yōu)化算法[J].現(xiàn)代電子技術(shù),2016,39(460):28-32.

[10] 金澈清,錢(qián)衛(wèi)寧,周敏奇.數(shù)據(jù)管理系統(tǒng)評(píng)測(cè)基準(zhǔn):從傳統(tǒng)數(shù)據(jù)庫(kù)到新興大數(shù)據(jù)[J].計(jì)算機(jī)學(xué)報(bào),2015,38(1):18-34.

[11] Xin R S,Gonzalez J E,Franklin M J,et al.GraphX:a resilient distributed graph system on Spark[C]//International Workshop on Graph Data Management Experiences and Systems.ACM,2013:1-6.

[12] Armbrust M,Xin R S,Lian C,et al.Spark SQL:Relational Data Processing in Spark[C]//ACM SIGMOD International Conference on Management of Data.ACM,2015:1383-1394.

[13] Zhong Y,Zhu X,Fang J.Elastic and effective spatio-temporal query processing scheme on Hadoop[C]//ACM Sigspatial International Workshop on Analytics for Big Geospatial Data.ACM,2012:33-42.

[14] Tan H,Luo W,Ni L M.CloST:a hadoop-based storage system for big spatio-temporal data analytics[C]//ACM International Conference on Information and Knowledge Management.ACM,2012:2139-2143.