基于流式計算引擎的時空查詢中間件設(shè)計與實現(xiàn)

秦俊峰，熊 文

(云南師范大學(xué) 信息學(xué)院，云南 昆明 650000)

0 引言

傳統(tǒng)關(guān)系型數(shù)據(jù)庫已經(jīng)無法滿足大規(guī)?？臻g數(shù)據(jù)的存儲和分析需求。利用大數(shù)據(jù)組建進(jìn)行適當(dāng)擴展，以支持大規(guī)?？臻g數(shù)據(jù)的存儲、分析計算的方法逐步進(jìn)入人們的視野，代表性的成果有HadoopGIS[1]，GeoSpark等[2]，但是這些工具只支持批處理場景下的應(yīng)用分析，并不支持流式計算場景，因此本文參考GeoSpark的設(shè)計機制，擴展了Spark-Streaming功能，實現(xiàn)了一個中間件，這個中間件支持空間數(shù)據(jù)對象，空間分區(qū)和空間索引，并且實現(xiàn)了空間最近鄰域搜索，區(qū)域查詢這兩個空間查詢。

1 背景與動機

1.1 空間查詢介紹

常見的空間查詢有空間最近鄰域搜索、區(qū)域查詢等。KNN是用來查詢距限定范圍內(nèi)距離指定空間對象最近的k個空間對象。本文對KNN定義如下：給定一個空間對象集合S和一個查詢空間對象q，以及查詢距離r(r∈(0,+∞))，KNN就是從S中找出q半徑范圍r內(nèi)距離最近的k個空間對象，記作KNN(P,q,r,k)，其形式化的定義如公式(1)所示(pk為距離q第k遠(yuǎn)的點)。

KNN(P,q,r,k)={p|p∈P,dist(p,q)≤dist(pk,q)∩dist(p,q)≤r,p≠q}

(1)

RQ是用來查詢給定空間范圍內(nèi)的某一類、某幾類或者所有的空間對象。本文對RQ的定義如下：給定一個空間對象集合S和一個查詢范圍q，RQ就是從S中找出在范圍q內(nèi)的所有空間對象，記作Range(P,q)。其形式化的定義如公式(2)所示。

Range(P,q)={p|p∈P,pinsideq}

(2)

1.2 空間分區(qū)和空間索引

空間分區(qū)按照一定的規(guī)則將空間對象劃分為多個不同的集合，是并行查詢或計算的基礎(chǔ)?？臻g索引對集合內(nèi)部的空間對象按規(guī)則進(jìn)行組織，減少搜索過程中的無效計算。常見的空間分區(qū)方式有網(wǎng)格分區(qū)和多級網(wǎng)格分區(qū)[3]，常見的空間索引方式有四叉樹索引、KDB樹、R樹等[4]。

2 空間查詢在流式場下的實現(xiàn)

本文主要在Spark-Streaming流式計算引擎上實現(xiàn)了KNN，RQ這兩種時空查詢算法。因為Spark-Streaming是一個微批原理的計算引擎，所以兩個查詢算法都是在被查詢數(shù)據(jù)集組成的RDD以及一個微批次查詢請求數(shù)據(jù)集組成的RDD上基于Join的原理實現(xiàn)的。

在Spark當(dāng)中Join是一個非常重量級的操作，因此本文著重對此進(jìn)行了優(yōu)化，先將被查詢的POI數(shù)據(jù)生成一個Spatial RDD，對此RDD進(jìn)行等網(wǎng)格分區(qū)，分區(qū)完成后對每個分區(qū)建立局部索引，并緩存至內(nèi)存當(dāng)中，以供后續(xù)查詢使用。接下來便是查詢請求數(shù)據(jù)，可以根據(jù)查詢請求對應(yīng)的參數(shù)，確定請求所涉及的網(wǎng)格分區(qū)，執(zhí)行查詢時只針對查詢所涉及的分區(qū)進(jìn)行計算，這樣多個查詢同時執(zhí)行，可以大大提高查詢的并行度。因此需要將查詢請求廣播到RDD對應(yīng)分區(qū)的每個節(jié)點。從而保證每個請求所涉及的分區(qū)都會有該請求的存在。

如圖1所示，KNN和RQ在Spark-Streaming中的DAG。因為一個查詢可能涉及多個分區(qū)，每個分區(qū)執(zhí)行Join的查詢后形成中間結(jié)果，最后將中間結(jié)果進(jìn)行一次聚合操作，使同一查詢請求在不同分區(qū)的中間查詢結(jié)果聚集到一起。在進(jìn)行聚合操作后，RQ便得到了最終的結(jié)果，KNN還需要進(jìn)行過濾和篩選才能得到最終結(jié)果。

圖1 空間查詢 DAG

3 實驗

3.1 數(shù)據(jù)集

本文實驗數(shù)據(jù)采用深圳市POI數(shù)據(jù)約260萬條、4.97萬個站點(公交站和地鐵站)，這些數(shù)據(jù)均為經(jīng)緯度數(shù)據(jù)。其中深圳市POI數(shù)據(jù)是被查詢數(shù)據(jù)，深圳公交站地鐵站經(jīng)緯度數(shù)據(jù)用來生成查詢請求。

本文以某乘客在某站點查詢指定半徑范圍內(nèi)的k個POI，來模擬KNN查詢。每個查詢請求的參數(shù)為：KNN(point,r,k)。其中point是查詢中心點，采用深圳公交地鐵站點經(jīng)緯度點作為查詢中心點；r和k分別為最大查詢半徑長度和需要查詢POI點的個數(shù)，這兩個值都采用固定值，分別是1 km和10個。

以某乘客查詢公交或者地鐵站點附近指定矩形范圍內(nèi)所有的POI點這一應(yīng)用場景，來模擬RQ查詢。每個RQ查詢請求的具體參數(shù)為：Rangequery(point1,point2)，其中point1,point2分別為查詢矩形范圍的左下角和右上角。將深圳公交地鐵經(jīng)緯度點作為查詢矩形范圍的中心點，矩形的長和寬分別為1.1 km和1 km，從而計算出point1和point2。

3.2 實驗結(jié)果與分析

如圖2所示，KNN查詢在Spark-Streaming微批時間間隔分別為0.2 s，0.4 s和0.6 s時的實驗結(jié)果。其中橫坐標(biāo)為請求的提交速度，左邊的縱坐標(biāo)為系統(tǒng)的吞吐，右邊的縱坐標(biāo)為查詢對應(yīng)的時延。

這些實驗圖結(jié)果都呈現(xiàn)出一個相同的規(guī)律，即在數(shù)據(jù)流流速尚未達(dá)到一個臨界值的時候，吞吐隨著數(shù)據(jù)流流速的增加而上升，且滿足一個線性增長的規(guī)律，時延呈現(xiàn)出緩慢增長的趨勢，且在當(dāng)前微批時間間隔內(nèi)；當(dāng)數(shù)據(jù)流流速超出臨界值的時候，吞吐雖然還會繼續(xù)增長，但是增速會放緩，此時的時延會快速增加，且超出當(dāng)前的微批間隔。在工程應(yīng)用當(dāng)中，當(dāng)時延大量超過微批時間間隔時，便會導(dǎo)致程序變得不再“實時”，因此定義數(shù)據(jù)流流速達(dá)到臨界值時的吞吐為最佳吞吐。

從圖2可以看出，KNN的最佳吞吐都會隨著批處理間隔的增加而上升，分別是0.2 s時900 op/s、0.4 s時2 000 op/s、0.6 s時2 600 op/s。RQ也是呈現(xiàn)出相同趨勢，其最佳吞吐分別是0.2 s時400 op/s、0.4 s時500 op/s、0.6 s時700 op/s。在達(dá)到最佳吞吐時，這兩個空間查詢算法的平均時延和微批時間間隔也近似相等。盡管單個請求的查詢時延從批處理對應(yīng)的0.1 s增加到流式計算對應(yīng)的0.2 s。但是吞吐這個指標(biāo)與批處理環(huán)境下相比提升幾十倍甚至上百倍。具體來講，批處理場景下KNN和RQ的吞吐分別是9 op/s和10 op/s，流式場景下兩種查詢對應(yīng)的吞吐分別為900 op/s和400 op/s。可以得出初步的結(jié)論，在流式計算場景下以0.1 s的時間為代價換取了KNN查詢接近100倍的性能提升，RQ查詢近40倍的性能提升。

圖2 空間最近鄰域搜索實驗結(jié)果

4 結(jié)語

本文通過Spark-Streaming流式計算引擎實現(xiàn)了KNN和RQ這兩個空間查詢算法，其性能相比較于批處理環(huán)境下的空間查詢均有很大的提升。具體來講，批處理場景下吞吐為9 op/s,時延為0.1 s，流式計算場景下吞吐為900 op/s, 時延為0.2 s。以0.1 s的代價換取吞吐提升100倍，能夠解決大規(guī)模實時查詢的需求。在下一步的工作中，可以嘗試在Flink流式計算引擎上來實現(xiàn)空間查詢算法，進(jìn)一步提升查詢性能。