基于流式計算引擎的時空查詢中間件設計與實現

秦俊峰，熊 文

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

0 引言

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

1 背景與動機

1.1 空間查詢介紹

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

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

(1)

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

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

(2)

1.2 空間分區和空間索引

空間分區按照一定的規則將空間對象劃分為多個不同的集合，是并行查詢或計算的基礎。空間索引對集合內部的空間對象按規則進行組織，減少搜索過程中的無效計算。常見的空間分區方式有網格分區和多級網格分區[3]，常見的空間索引方式有四叉樹索引、KDB樹、R樹等[4]。

2 空間查詢在流式場下的實現

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

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

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

圖1 空間查詢 DAG

3 實驗

3.1 數據集

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

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

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

3.2 實驗結果與分析

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

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

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

圖2 空間最近鄰域搜索實驗結果

4 結語

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