論文信息：The VLDB Journal (2021) 30:287–310
Ziquan Fang·Lu ChenYunjun Gao·Lu Pan·Christian S. Jensen
摘要
隨著具有g(shù)ps功能的設(shè)備的大量使用，越來越多的人和車輛的運(yùn)動(dòng)軌跡數(shù)據(jù)正在變得可用，這在許多應(yīng)用領(lǐng)域非常有用，如交通、交通管理和基于位置的服務(wù)。因此，出現(xiàn)了許多針對(duì)離線或在線設(shè)置的軌跡數(shù)據(jù)管理和分析系統(tǒng)。但是，有些應(yīng)用程序同時(shí)需要離線和在線分析。例如，在交通管理場(chǎng)景中，歷史軌跡數(shù)據(jù)的離線分析可用于交通規(guī)劃目的，而流軌跡的在線分析可用于擁堵監(jiān)測(cè)目的。現(xiàn)有的軌跡分析系統(tǒng)往往分別進(jìn)行離線和在線軌跡分析，效率低下。在本文中，我們提出了一個(gè)混合和高效的框架，稱為dragoon，基于Spark，以支持離線和在線大軌跡管理和分析。該框架具有一個(gè)可變的彈性分布式數(shù)據(jù)集模型，包括RDD共享、RDD 更新和RDD鏡像，它支持歷史和流軌跡的混合存儲(chǔ)。它還包含一個(gè)實(shí)時(shí)分配器，能夠有效地分發(fā)軌跡數(shù)據(jù)，并支持離線和在線分析。因此，Dragoon提供了一個(gè)混合分析管道。對(duì)幾個(gè)典型的軌跡查詢和挖掘任務(wù)的支持顯示了Dragoon的靈活性。一項(xiàng)使用真實(shí)和合成軌跡數(shù)據(jù)集的廣泛實(shí)驗(yàn)研究表明，dragonoon(1)與最先進(jìn)的系統(tǒng)UlTraMan具有類似的離線軌跡查詢性能;(2)在軌跡編輯過程中，與UlTraMan相比，可減少多達(dá)兩倍的存儲(chǔ)開銷;(3)與流行的流處理框架(如Flink和Spark streaming)相比，可擴(kuò)展性提高至少40%;(4)在線軌跡數(shù)據(jù)分析的性能平均提高了一倍。
關(guān)鍵詞
軌跡系統(tǒng)·數(shù)據(jù)管理·數(shù)據(jù)分析·分布式處理
1.介紹
現(xiàn)有的軌跡管理系統(tǒng)提供了次優(yōu)的支持，因?yàn)樗蕾囉诙鄠€(gè)系統(tǒng)來實(shí)現(xiàn)離線和在線分析，這迫使用戶不斷地在離線和在線系統(tǒng)之間切換，以完成上述混合分析場(chǎng)景。此外，它的效率也很低，因?yàn)?i)在提取、轉(zhuǎn)換和加載(ETL)歷史軌跡數(shù)據(jù)與流化軌跡數(shù)據(jù)時(shí)需要重復(fù)類似的軌跡預(yù)處理過程，(ii)在不同的離線或在線場(chǎng)景下會(huì)產(chǎn)生磁盤存儲(chǔ)復(fù)制。因此，我們的目標(biāo)是開發(fā)一個(gè)有效的混合軌跡管理和分析系統(tǒng)。
在本文中，我們介紹了一種新型的混合高效的大軌跡管理系統(tǒng)dragoon，用于離線和在線分析。如圖1所示，Dragoon被設(shè)計(jì)成一個(gè)整體解決方案，它支持歷史和流軌跡數(shù)據(jù)預(yù)處理、管理和分析在一個(gè)系統(tǒng)中完整的流水線。為了開發(fā)這樣一個(gè)系統(tǒng)，我們考慮了兩種方法。第一個(gè)是擴(kuò)展現(xiàn)有的離線或面向批處理系統(tǒng)(例如，Spark[54])，以增強(qiáng)其流軌跡的在線實(shí)時(shí)處理能力。第二種是擴(kuò)展現(xiàn)有的在線或面向流的系統(tǒng)(例如:Flink[3])，使其具有管理和處理大規(guī)模歷史軌跡數(shù)據(jù)的能力。盡管如此，我們觀察到在線系統(tǒng)或框架在處理數(shù)據(jù)更新[50]方面存在局限性，這在設(shè)計(jì)這樣的軌跡管理系統(tǒng)時(shí)是不能忽視的。更具體地說，在線系統(tǒng)的數(shù)據(jù)更新機(jī)制是流驅(qū)動(dòng)的和被動(dòng)的，這意味著只有當(dāng)新的數(shù)據(jù)到達(dá)時(shí)才觸發(fā)數(shù)據(jù)更新，而沒有任何傳入的數(shù)據(jù)時(shí)就不會(huì)發(fā)生更新。相比之下，許多現(xiàn)實(shí)世界的應(yīng)用程序需要軌跡編輯[49]或軌跡清理[22]，即使沒有傳入的軌跡數(shù)據(jù)，也會(huì)調(diào)用數(shù)據(jù)更新。為此，我們采用第一種方法，將第二種方法作為未來的研究方向。具體來說，我們選擇擴(kuò)展Spark平臺(tái)來實(shí)現(xiàn)Dragoon系統(tǒng)，因?yàn)镾park是一個(gè)在學(xué)術(shù)和工業(yè)領(lǐng)域都被廣泛使用和高效的離線分布式處理系統(tǒng)。注意，Spark Streaming也擴(kuò)展了Spark來處理流數(shù)據(jù)。然而，它只能以批處理的方式處理流軌跡，即采用微批處理策略，將流切割成幾個(gè)數(shù)據(jù)rdd，并分別管理這些rdd。相比之下，我們的目標(biāo)是開發(fā)一個(gè)單一系統(tǒng)，通過增強(qiáng)Spark core的存儲(chǔ)層，以混合方式管理歷史軌跡和流軌跡，在此基礎(chǔ)上，Spark core能夠進(jìn)行更好的混合軌跡分析。當(dāng)采用第一種方法時(shí)，存在以下兩個(gè)關(guān)鍵挑戰(zhàn)：
挑戰(zhàn)一:如何擴(kuò)展Spark以支持流軌跡數(shù)據(jù)的動(dòng)態(tài)統(tǒng)一存儲(chǔ)?現(xiàn)有的Spark Streaming通過將數(shù)據(jù)流切割成數(shù)據(jù)批量來存儲(chǔ)流數(shù)據(jù)，其中每個(gè)數(shù)據(jù)批量都可以被視為一個(gè)彈性分布式數(shù)據(jù)集(RDD)[54]。然而，這樣的rdd是不可變的和只讀的，并且任何對(duì)RDD的更新(例如，map或union操作)都會(huì)創(chuàng)建一個(gè)新數(shù)據(jù)的RDD。在流軌跡設(shè)置或軌跡數(shù)據(jù)編輯場(chǎng)景中，數(shù)據(jù)更新頻繁發(fā)生。因此，我們的目標(biāo)是提供動(dòng)態(tài)存儲(chǔ)，可以支持有效的數(shù)據(jù)更新，這可以避免不必要的數(shù)據(jù)復(fù)制和時(shí)間成本。為了解決這個(gè)問題，我們提出了一個(gè)可變RDD模型，稱為mRDD，它包括RDD共享、RDD更新和RDD鏡像。具體來說，RDD Share檢測(cè)RDD中可以共享的那些未改變的部分;RDD Update為不同的更新相關(guān)場(chǎng)景提供了三種更新策略;RDD Mirror支持有效的讀寫訪問控制，避免分布式環(huán)境下并發(fā)讀寫造成的數(shù)據(jù)沖突和不一致。mRDD模型是為了與spark的原始RDD模型兼容而設(shè)計(jì)的，因此Dragoon能夠通過混合方式在mRDD中存儲(chǔ)歷史和流軌跡數(shù)據(jù)。具體來說，在考慮系統(tǒng)數(shù)據(jù)平衡的同時(shí)，分區(qū)器可以根據(jù)不同的軌跡特征(例如軌跡的id、空間或時(shí)間信息)，將歷史軌跡和流軌跡切割到多個(gè)數(shù)據(jù)分區(qū)進(jìn)行并行處理。同時(shí)，將同一數(shù)據(jù)分區(qū)內(nèi)的歷史軌跡和流軌跡合并在一起，實(shí)現(xiàn)統(tǒng)一高效的存儲(chǔ)。
挑戰(zhàn)二:如何建立離線和在線軌跡數(shù)據(jù)分析的混合處理流水線?
用于離線和在線軌跡分析的技術(shù)是不同的。離線技術(shù)側(cè)重于歷史軌跡數(shù)據(jù)的管理和批處理，而在線技術(shù)則側(cè)重于軌跡流的實(shí)時(shí)處理。有鑒于此，Dragoon基于其混合存儲(chǔ)提供了一個(gè)混合數(shù)據(jù)分析流水線。此外，Dragoon還實(shí)現(xiàn)并支持包含軌跡編輯和ID/Range/kNN (ID/Range/kNN)查詢的離線分析案例，以及包含在線ID/Range/kNN查詢和實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式檢測(cè)的在線分析案例。
基于提出的mRDD模型，Dragoon能夠作為一個(gè)可擴(kuò)展、高效、靈活的混合平臺(tái)，用于離線和在線大軌跡數(shù)據(jù)管理和分析。綜上所述，本文的貢獻(xiàn)如下:
-我們提出了一種混合高效的系統(tǒng)，用于整合離線和在線可伸縮軌跡數(shù)據(jù)管理和分析。
-我們提供了一個(gè)可變的RDD模型，帶有實(shí)時(shí)分區(qū)，以混合方式管理底層存儲(chǔ)的歷史軌跡和流軌跡。
-我們?yōu)闅v史軌跡數(shù)據(jù)和流軌跡數(shù)據(jù)設(shè)計(jì)了一個(gè)混合分析管道，并通過顯示和支持典型的離線和在線軌跡查詢和挖掘任務(wù)來展示其實(shí)用性。
-在真實(shí)和合成軌跡數(shù)據(jù)集上進(jìn)行的大量實(shí)驗(yàn)，為Dragoon的效率和可擴(kuò)展性提供了見解，還包括與現(xiàn)有的最先進(jìn)的軌跡處理系統(tǒng)或框架進(jìn)行比較。
2.相關(guān)工作
在這一節(jié)中，我們繼續(xù)簡(jiǎn)要地調(diào)查相關(guān)的系統(tǒng)架構(gòu)，并澄清它們與dragoon之間的區(qū)別。
2.1離線/在線軌跡分析系統(tǒng)
首先，離線軌跡系統(tǒng)可以批量處理歷史軌跡數(shù)據(jù)，有集中式和分布式兩種類型。突出的軌跡存儲(chǔ)或分析集中系統(tǒng)包括BerlinMOD[21]、Tra-jStore[17]和SharkDB[42]，僅舉幾例。然而，由于單臺(tái)機(jī)器的能力有限，它們無法擴(kuò)展到大量的軌跡數(shù)據(jù)管理和分析。
分布式的MapReduce[18]框架和開源的Hadoop[1]和Spark[4]實(shí)現(xiàn)，使得多個(gè)分布式軌跡管理或分析系統(tǒng)得以存在。CloST[39]基于hadoop，對(duì)大軌跡數(shù)據(jù)提供分布式查詢處理。location - tionspark[40]、Simba[47]和Elite[48]是基于spark的，它們利用特定的分區(qū)和索引策略，利用創(chuàng)新的存儲(chǔ)方案來管理大軌跡數(shù)據(jù)。目前還存在幾種分布式大軌跡數(shù)據(jù)分析系統(tǒng)。Shang et al.[38]提出了DITA，它也是基于spark的，支持top-ktrajectory相似度連接。Xie等人提出了一個(gè)基于spark的分布式軌跡相似度搜索查詢框架。Yuan等人[52]在考慮路網(wǎng)的情況下，繼續(xù)研究Spark平臺(tái)上的軌跡相似度搜索和加入。此外，提供分布式存儲(chǔ)和處理的云和其他基于模式(例如，分布式NoSQL)的軌跡系統(tǒng)[10,28,29,36]也存在。
最近，一個(gè)名為UlTraMan[20]的高效平臺(tái)提出，為大軌跡數(shù)據(jù)的ETL、存儲(chǔ)、管理和分析提供統(tǒng)一的管道。通過提供操作界面，用戶可以在單個(gè)系統(tǒng)中完成各種脫機(jī)軌跡數(shù)據(jù)分析。上述系統(tǒng)都是為支持離線管理和分析靜態(tài)軌跡和歷史軌跡而設(shè)計(jì)的，因此無法支持流軌跡的實(shí)時(shí)處理。這是因?yàn)檐壽E數(shù)據(jù)流是無界的，是實(shí)時(shí)到達(dá)的，而上述軌跡系統(tǒng)的存儲(chǔ)和處理引擎都是為靜態(tài)歷史數(shù)據(jù)設(shè)計(jì)的。有鑒于此，我們提出的Dragoon采用了一個(gè)靈活的框架，用于離線和在線軌跡數(shù)據(jù)管理和分析。請(qǐng)注意，Dragoon的離線組件共享了最先進(jìn)的系統(tǒng)奧特曼的所有特性，包括可擴(kuò)展、高效和統(tǒng)一，因?yàn)镈ragoon使用的離線技術(shù)與UlTraMan類似。主要的區(qū)別是我們?cè)贒ragoon中提出了mRDD模型，它與Spark的原始RDD兼容，但可以在底層存儲(chǔ)中實(shí)現(xiàn)高效的數(shù)據(jù)更新。
隨著實(shí)時(shí)軌跡數(shù)據(jù)分析在現(xiàn)實(shí)生活中的應(yīng)用越來越重要。實(shí)時(shí)事件檢測(cè)[35])，在線軌跡系統(tǒng)正在開發(fā)中，用于流軌跡處理?，F(xiàn)有的在線軌跡數(shù)據(jù)系統(tǒng)旨在高效地存儲(chǔ)[10]、查詢[9,30,34,43]和挖掘[14,32]軌跡流。盡管如此，它們還是分別處理存儲(chǔ)、查詢和挖掘任務(wù)，目前還沒有像Dragoon這樣的統(tǒng)一系統(tǒng)來支持大流軌跡數(shù)據(jù)管理和分析的完整流程。隨著最近分布式流處理的出現(xiàn)，提出了幾種通用的分布式流處理平臺(tái)[2 - 5,16,25]。然而，它們并沒有充分利用軌跡數(shù)據(jù)的特性。相比之下，Dragoon充分考慮了軌跡的特征，如Id、空間和時(shí)間信息，支持對(duì)軌跡流的高效動(dòng)態(tài)管理。盡管基于流軌跡分析平臺(tái)的軌跡體系結(jié)構(gòu)已被研究[56,57]，但那些在線軌跡系統(tǒng)關(guān)注的是最新軌跡流的實(shí)時(shí)處理，這對(duì)于大規(guī)模、由于被動(dòng)更新的限制，離線軌跡數(shù)據(jù)管理和分析，正如我們?cè)诘?節(jié)中討論的。相比之下，我們提出了基于Spark擴(kuò)展的mRDD模型的Dragoon系統(tǒng)，該系統(tǒng)既支持在線流軌跡數(shù)據(jù)管理，也支持離線軌跡數(shù)據(jù)管理(如軌跡數(shù)據(jù)編輯)。
2.2通用的混合方法
混合系統(tǒng)能夠在單個(gè)系統(tǒng)中處理歷史數(shù)據(jù)和流數(shù)據(jù)，并且存在幾種通用的混合系統(tǒng)。Kumar等人對(duì)mapreduce進(jìn)行了在線擴(kuò)展，以支持批量數(shù)據(jù)處理，但仍面臨第1節(jié)中提到的被動(dòng)更新的局限性。隨著Lambda架構(gòu)[24]的出現(xiàn)，幾個(gè)混合系統(tǒng)[7,8,11,15,19,50]被開發(fā)出來，它們結(jié)合了兩個(gè)平臺(tái)來處理歷史數(shù)據(jù)和流數(shù)據(jù)。例如，Summingbird[11]結(jié)合了Hadoop和Storm，其中Hadoop用于離線處理，而Storm用于在線處理?；趌ambda的系統(tǒng)的想法很簡(jiǎn)單，但它們必須維護(hù)兩個(gè)獨(dú)立的系統(tǒng)或不同的運(yùn)營(yíng)商api，以支持混合分析，而我們的目標(biāo)是開發(fā)一個(gè)單一的系統(tǒng)，以支持離線和在線數(shù)據(jù)管理和分析。換句話說，我們的目標(biāo)是一個(gè)統(tǒng)一的系統(tǒng)，以支持歷史和流軌跡數(shù)據(jù)分析。此外，上述系統(tǒng)均未對(duì)目標(biāo)軌跡數(shù)據(jù)進(jìn)行處理。據(jù)我們所知，Dragoon是第一個(gè)以混合軌跡數(shù)據(jù)管理和分析為目標(biāo)的提案，其中包括對(duì)其實(shí)施的詳細(xì)描述。
雖然Spark可以通過其擴(kuò)展Spark Streaming或Structured streams以混合方式處理數(shù)據(jù)，但這些系統(tǒng)不支持高效和可伸縮的混合軌跡管理和分析。有兩個(gè)原因可以解釋這一點(diǎn)。首先，Spark Streaming是核心Spark API的擴(kuò)展，通過將數(shù)據(jù)流劃分為數(shù)據(jù)批處理，然后使用Spark引擎處理每個(gè)數(shù)據(jù)批處理，支持流處理，我們稱之為微批處理[4]。盡管如此，每批流軌跡數(shù)據(jù)仍然是基于不可變數(shù)據(jù)的，并且在Spark中是單獨(dú)管理的。因此，由于使用不可變r(jià)dd進(jìn)行更新會(huì)導(dǎo)致大量冗余數(shù)據(jù)存儲(chǔ)，Spark Streaming無法支持高效的離線分析。另一方面，結(jié)構(gòu)化流是Spark SQL引擎的一個(gè)擴(kuò)展，它通過在UnboundedTable中添加結(jié)構(gòu)化數(shù)據(jù)來支持流處理。然而，由于軌跡數(shù)據(jù)具有重要的時(shí)空特性，通常不能像結(jié)構(gòu)化數(shù)據(jù)那樣存儲(chǔ)在表中。例如，基于這種表的管理，不方便構(gòu)建空間STR樹[27]索引。值得注意的是，為了支持Spark SQL[47]中的索引，需要進(jìn)行重要的內(nèi)部修改，但由于[20]的結(jié)構(gòu)化存儲(chǔ)方案，這種靈活性受到了限制。相比之下，我們?cè)鰪?qiáng)了Spark Core的歷史和流軌跡數(shù)據(jù)的底層存儲(chǔ)機(jī)制。在此基礎(chǔ)上，我們開發(fā)了dragoon系統(tǒng)，這是一個(gè)混合的、高效的大軌跡管理系統(tǒng)，用于離線和在線分析。
3.背景
在本節(jié)中，我們繼續(xù)介紹Dragoon系統(tǒng)實(shí)現(xiàn)的相關(guān)背景，包括Spark中的彈性分布式數(shù)據(jù)集，以及軌跡的混合管理和分析。
3.1彈性分布式數(shù)據(jù)集
彈性分布式數(shù)據(jù)集(RDD)是Spark的核心概念。具體來說，數(shù)據(jù)RDD是一組數(shù)據(jù)，在分布式環(huán)境中可以邏輯地劃分為多個(gè)數(shù)據(jù)分區(qū)，每個(gè)數(shù)據(jù)分區(qū)是整個(gè)數(shù)據(jù)集的一個(gè)子集，對(duì)應(yīng)于底層存儲(chǔ)層中的一個(gè)物理數(shù)據(jù)塊。RDD的數(shù)據(jù)分區(qū)可以發(fā)送到分布式環(huán)境中的不同節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以管理RDD的多個(gè)分區(qū)。此外，每個(gè)節(jié)點(diǎn)都有一個(gè)塊管理器來控制發(fā)送給它的數(shù)據(jù)分區(qū)，因此計(jì)算可以在不同的節(jié)點(diǎn)上并行執(zhí)行。請(qǐng)注意，盡管Spark中最近提出的Dataset概念進(jìn)行了更深入的優(yōu)化，但它更適合于半結(jié)構(gòu)化和結(jié)構(gòu)化數(shù)據(jù)。相比之下，RDD可以提供更低層、更通用的數(shù)據(jù)管理和訪問。
但由于RDD的模型是不可變的(即RDD的分區(qū)是只讀的，不能直接修改)，因此在涉及軌跡數(shù)據(jù)管理場(chǎng)景(如軌跡編輯)時(shí)存在一定的局限性。這是因?yàn)镽DD上的任何數(shù)據(jù)更新都會(huì)創(chuàng)建一個(gè)新的RDD。例如，在Fig.2a中，原始RDD_o包含三個(gè)數(shù)據(jù)對(duì)象(o1,o2, 和o3)，其中o1為軌跡編輯時(shí)需要編輯的數(shù)據(jù)對(duì)象。在Spark的不可變RDD中進(jìn)行數(shù)據(jù)更新的一個(gè)簡(jiǎn)單解決方案如下:(i)使用filter對(duì)原始RDD_o進(jìn)行操作得到一個(gè)RDD_e和另一個(gè)RDD_u，其中RDD_e包含需要編輯的RDD_o的o1, RDD_u表示RDD_o中其余保持不變的數(shù)據(jù)對(duì)象;(ii)使用map操作更新RDD_e并得到RDD_r（即編輯后的RDD）;(iii)在RDD_u和RDD_r之間使用聯(lián)合操作來提供一個(gè)新的和“更新后”的RDD_n給用戶;（iv)為未來可能的軌跡編輯返回RDD_n。如圖2a所示，我們所需要的只是軌跡編輯的最終結(jié)果RDD_n，但在上述的編輯處理過程中，由于rdd的不變性，產(chǎn)生了幾個(gè)中間的、不必要的數(shù)據(jù)rdd(如RDD_e、RDD_r、RDD_u)，產(chǎn)生了大量的數(shù)據(jù)拷貝。存儲(chǔ)成本將進(jìn)一步加劇，因?yàn)閿?shù)據(jù)更新在軌跡管理場(chǎng)景中非常常見。因此，支持直接更新操作的可變數(shù)據(jù)RDD對(duì)于軌跡編輯場(chǎng)景是必要的。在此基礎(chǔ)上，我們可以執(zhí)行一個(gè)簡(jiǎn)單的數(shù)據(jù)更新操作，如圖2b所示。
此外，可變RDD不僅可以提供一種有效的方法來處理上述軌跡編輯場(chǎng)景，還可以實(shí)現(xiàn)高效的在線軌跡分析任務(wù)。雖然Spark Streaming可以用于流軌跡處理，但它只是將新到達(dá)的軌跡點(diǎn)轉(zhuǎn)換為數(shù)據(jù)批處理，并將其存儲(chǔ)在新創(chuàng)建的數(shù)據(jù)RDD中。然后，Spark Streaming將此新的RDD添加到歷史數(shù)據(jù)集的末尾。在這種情況下，對(duì)軌跡流的數(shù)據(jù)按時(shí)間信息分別進(jìn)行管理和排序，這對(duì)于某些軌跡分析來說效率很低。以在線范圍查詢?yōu)槔淠康氖菍ふ姨囟臻g區(qū)域的軌跡，Spark Streaming需要訪問每個(gè)數(shù)據(jù)批來得到最終的結(jié)果。而配備mRDD的Dragoon系統(tǒng)可以將相鄰的位置存儲(chǔ)在同一個(gè)RDD中，即新到達(dá)的位置根據(jù)空間信息插入到之前對(duì)應(yīng)的RDD中?；诖?，Dragoon只訪問少量(而不是全部)rdds，得到最終的在線范圍查詢結(jié)果?；诖?，我們?cè)赟park RDD下擴(kuò)展了歷史軌跡和流軌跡數(shù)據(jù)的底層存儲(chǔ)，在此基礎(chǔ)上，我們開發(fā)了一個(gè)用于離線和在線分析的混合大軌跡管理系統(tǒng)。
3.2混合管理和分析
運(yùn)動(dòng)物體(如人、車輛)產(chǎn)生的軌跡數(shù)據(jù)可分為歷史軌跡數(shù)據(jù)和流軌跡數(shù)據(jù)。這兩類數(shù)據(jù)的管理和分析是不同的。我們首先描述了軌跡管理階段，然后提出了軌跡分析階段。
在軌跡數(shù)據(jù)管理方面，歷史軌跡數(shù)據(jù)和流軌跡數(shù)據(jù)的存儲(chǔ)格式不同。歷史軌跡數(shù)據(jù)，也稱為靜態(tài)或批量軌跡數(shù)據(jù)，通常由軌跡點(diǎn)的序列表示，并存儲(chǔ)在文件塊中。相反，流軌跡數(shù)據(jù)，也被稱為動(dòng)態(tài)或無界軌跡數(shù)據(jù)，通常作為最新的軌跡點(diǎn)加載到主存儲(chǔ)器中，用于后續(xù)的實(shí)時(shí)處理。
在軌跡數(shù)據(jù)分析方面，歷史軌跡數(shù)據(jù)需要離線批處理，而流軌跡數(shù)據(jù)需要在線實(shí)時(shí)處理。對(duì)于歷史數(shù)據(jù)，現(xiàn)有的工作旨在通過使用各種優(yōu)化技術(shù)(如數(shù)據(jù)分區(qū)[20,47]和軌跡索引結(jié)構(gòu)[33])實(shí)現(xiàn)高可伸縮性和效率。對(duì)于流數(shù)據(jù)，現(xiàn)有工作[14]的目標(biāo)是實(shí)現(xiàn)高吞吐量和低響應(yīng)延遲的實(shí)時(shí)處理。然而，一些現(xiàn)實(shí)世界的應(yīng)用程序需要離線和在線分析，我們稱之為混合分析。例如，在交通管理應(yīng)用程序中，歷史軌跡的離線分析可以用于更好的交通規(guī)劃目的，而流軌跡的在線分析可以用于交通監(jiān)控，以實(shí)時(shí)檢測(cè)擁堵。現(xiàn)有的軌跡數(shù)據(jù)管理和分析的研究?jī)A向于分別解決這些問題，從而導(dǎo)致為用戶提供混合分析的方法效率低下。相比之下，dragon -goon提出了一種基于Spark的混合方法，在單個(gè)系統(tǒng)中同時(shí)支持離線的歷史軌跡分析和在線的流軌跡分析。
3.3Chronicle map
Chronicle map是一種流行的存儲(chǔ)技術(shù)，用于高頻交易(HFT)領(lǐng)域的低延遲和多進(jìn)程訪問，比如交易和金融市場(chǎng)應(yīng)用程序。對(duì)于Dragoon的實(shí)現(xiàn)Chronicle Map具有兩個(gè)關(guān)鍵特性，包括堆外內(nèi)存持久存儲(chǔ)和嵌入鍵值存儲(chǔ)，如下所述。(1)堆內(nèi)存持久化。為了支持更高的分布式數(shù)據(jù)計(jì)算和處理性能，原始的基于RDD的Spark選擇將數(shù)據(jù)緩存到堆上內(nèi)存，這可能會(huì)對(duì)GC (garbage collector)造成較大的開銷，特別是在大數(shù)據(jù)處理方面。相比之下，Chronicle Map采用了離堆內(nèi)存機(jī)制，不僅可以提供與Spark內(nèi)置內(nèi)存緩存相似的處理性能，而且可以顯著減輕GC壓力，提供更好的數(shù)據(jù)可伸縮性。換句話說，這一特性為dragoon大軌跡數(shù)據(jù)管理提供了基本保障。(2)嵌入式鍵值存儲(chǔ)?；叵胍幌拢覀兊哪繕?biāo)是一個(gè)混合和高效的大軌跡管理系統(tǒng)，用于離線和在線分析，因此，高效的數(shù)據(jù)訪問是必需的，特別是在線軌跡管理和分析。幸運(yùn)的是，Chronicle Map提供了一個(gè)嵌入式鍵值存儲(chǔ)，它支持對(duì)不同數(shù)據(jù)格式進(jìn)行高效和隨機(jī)的數(shù)據(jù)訪問。例如，鍵可以指向一個(gè)移動(dòng)對(duì)象的ID，而值可以表示它的各種軌跡格式。具體來說，這些格式可以表示一個(gè)觀測(cè)到的GPS點(diǎn)，一個(gè)由幾個(gè)GPS點(diǎn)組成的子軌跡，或者這個(gè)移動(dòng)物體的整個(gè)軌跡。而且，我們?cè)谥暗墓ぷ髦幸沧C實(shí)了它的有效性。通過將chronicle Map無縫集成到Spark作為底層存儲(chǔ)引擎，Dragoon可以為離線和在線軌跡數(shù)據(jù)分析提供高效、可伸縮、靈活的軌跡管理。
4.系統(tǒng)概述
在本節(jié)中，我們將對(duì)dragoon進(jìn)行概述，包括加載、預(yù)處理、混合管理和混合分析，如圖3所示。
加載：第一階段，dragoon從靜態(tài)軌跡數(shù)據(jù)源中獲取歷史軌跡數(shù)據(jù)，或從流態(tài)軌跡源中連續(xù)加載最新軌跡數(shù)據(jù)。
預(yù)處理：處理包括格式轉(zhuǎn)換、數(shù)據(jù)分區(qū)和索引構(gòu)造。首先，將原始軌跡數(shù)據(jù)表示為一個(gè)GPS記錄序列(id,l,t)， 其中id表示一個(gè)移動(dòng)對(duì)象的id, l表示包含經(jīng)緯度的位置，t表示該位置被觀測(cè)的時(shí)間。接下來，可以根據(jù)特定的分區(qū)規(guī)則將歷史軌跡和流軌跡劃分為幾個(gè)數(shù)據(jù)分區(qū)。如圖3所示，用數(shù)據(jù)分區(qū)p_i(1≤i≤n)對(duì)軌跡數(shù)據(jù)進(jìn)行分區(qū)。最后，索引的構(gòu)造包括每個(gè)數(shù)據(jù)分區(qū)上的本地索引構(gòu)造和所有數(shù)據(jù)分區(qū)上的全局索引構(gòu)造，詳細(xì)信息將在第6節(jié)中提供。
混合管理：為了同時(shí)管理歷史和流軌跡數(shù)據(jù)，我們?cè)O(shè)計(jì)了混合存儲(chǔ)，這是Dragoon的核心部分?；旌洗鎯?chǔ)在物理上基于Chronicle Map。為了存儲(chǔ)混合軌跡數(shù)據(jù)，我們需要合并流軌跡和歷史軌跡。合并過程不是Spark中實(shí)現(xiàn)的簡(jiǎn)單合并操作，而是需要能夠支持物理Chronicle Map層的數(shù)據(jù)更新。為了支持?jǐn)?shù)據(jù)更新，我們?cè)O(shè)計(jì)了mRDD模型，詳見第5節(jié)。此外，本地索引和全局索引也存儲(chǔ)在Chronicle Map中，在數(shù)據(jù)更新處理后需要更新。
混合分析：混合分析包括對(duì)歷史軌跡數(shù)據(jù)的離線分析和對(duì)流軌跡數(shù)據(jù)的在線分析。具體來說，dragoon支持兩種在線分析，如圖3所示。第一類在線分析稱為最新在線分析，主要關(guān)注觀測(cè)到的移動(dòng)物體的最新位置數(shù)據(jù)值。第二種類型的在線分析稱為周期在線分析，是對(duì)移動(dòng)物體的最新位置數(shù)據(jù)和以前的歷史軌跡數(shù)據(jù)(即與某一最近時(shí)間段相關(guān)的數(shù)據(jù))進(jìn)行的分析?；旌戏治龅募?xì)節(jié)在第6節(jié)中給出。
5.混合存儲(chǔ)
連續(xù)采集流軌跡數(shù)據(jù)。我們的系統(tǒng)Dragoon將傳入的數(shù)據(jù)附加到以前的數(shù)據(jù)分區(qū)中，這將導(dǎo)致底層存儲(chǔ)對(duì)每個(gè)到達(dá)的軌跡點(diǎn)進(jìn)行更新，而不是使用小批量策略，將傳入的數(shù)據(jù)分成小批量并單獨(dú)管理它們。但是，Spark原有的RDD是不可變的，任何對(duì)RDD的更新都會(huì)創(chuàng)建一個(gè)新的RDD，導(dǎo)致不必要的數(shù)據(jù)拷貝導(dǎo)致存儲(chǔ)成本很高。因此，如何支持流數(shù)據(jù)的頻繁RDD更新是實(shí)現(xiàn)混合存儲(chǔ)的關(guān)鍵。有鑒于此，我們提出了一個(gè)可變RDD(mRDD)模型，該模型旨在與Spark的原始RDD模型兼容。mRDD模型包括三個(gè)部分，即RDD共享、RDD更新和RDD鏡像，以支持歷史和流軌跡數(shù)據(jù)的混合存儲(chǔ)。在本節(jié)的下一個(gè)部分中，我們將按順序詳細(xì)說明這三個(gè)部分。為了區(qū)分，我們使用mRDDs來表示我們提出的Dragoon的mRDD模型，而我們使用RDDs來表示spark的原始RDD模型。
5.1RDD 共享
在Spark中，數(shù)據(jù)在邏輯上存儲(chǔ)在分布式的數(shù)據(jù)分區(qū)中，在物理上存儲(chǔ)在分布式的數(shù)據(jù)塊中。也就是說，每個(gè)數(shù)據(jù)分區(qū)對(duì)應(yīng)底層存儲(chǔ)層的一個(gè)數(shù)據(jù)塊。受多版本數(shù)據(jù)結(jié)構(gòu)[41]的啟發(fā)，我們開發(fā)了一種有效的跨不同rdd的數(shù)據(jù)共享機(jī)制，稱為rdd共享。當(dāng)RDD中有數(shù)據(jù)更新時(shí)，RDD Share首先識(shí)別出沒有數(shù)據(jù)更新的數(shù)據(jù)分區(qū)，然后在新創(chuàng)建的數(shù)據(jù)RDD中直接重用那些最近沒有更新的數(shù)據(jù)分區(qū)。這種機(jī)制可以避免大量不必要的數(shù)據(jù)拷貝用于數(shù)據(jù)更新處理。
在Spark中，一個(gè)RDD的數(shù)據(jù)分區(qū)被管理在一個(gè)RDD特定的空間中，因此不同的數(shù)據(jù)RDD被維護(hù)在不同的存儲(chǔ)空間中。為了支持不同RDD之間的RDD共享，我們?yōu)槊總€(gè)數(shù)據(jù)分區(qū)(即物理數(shù)據(jù)塊)分配一個(gè)唯一的ID，如圖4所示。為了為數(shù)據(jù)空間中的每個(gè)數(shù)據(jù)分區(qū)生成一個(gè)唯一的ID，我們將RDD的ID和該數(shù)據(jù)分區(qū)在其數(shù)據(jù)RDD中的序列號(hào)結(jié)合起來。例如，在圖4中，數(shù)據(jù)分區(qū)ID“rdd_1-p_1”是將RDD ID中“rdd1”和所屬數(shù)據(jù)RDD中的數(shù)據(jù)分區(qū)的序列號(hào)“p1”組合而成的。
在Spark的原始RDD設(shè)計(jì)中，每個(gè)數(shù)據(jù)分區(qū)只屬于一個(gè)特定的數(shù)據(jù)RDD，并且每個(gè)RDD只管理自己的數(shù)據(jù)分區(qū)。當(dāng)一個(gè)數(shù)據(jù)RDD被釋放時(shí)，它的數(shù)據(jù)分區(qū)也被釋放。然而，在我們的mRDD模型中，每個(gè)數(shù)據(jù)分區(qū)可以在多個(gè)mRDD之間共享。因此，需要對(duì)每個(gè)數(shù)據(jù)分區(qū)的生命周期進(jìn)行單獨(dú)維護(hù)，以支持一致性數(shù)據(jù)管理。換句話說，當(dāng)一個(gè)RDD被釋放時(shí)，如果它的數(shù)據(jù)分區(qū)與其他mrdd共享，那么它的數(shù)據(jù)分區(qū)就不能被釋放。如圖4所示，數(shù)據(jù)分區(qū)“rdd1-p2”由RDD1和RDD2共享。當(dāng)RDD1被系統(tǒng)釋放時(shí)，它的數(shù)據(jù)分區(qū)“rdd1-p2”不能被直接釋放，因?yàn)樗脖涣硪粋€(gè)rdd2共享。否則，可能會(huì)出現(xiàn)不一致的數(shù)據(jù)問題。為了避免數(shù)據(jù)分區(qū)的錯(cuò)誤釋放，我們?cè)诿總€(gè)節(jié)點(diǎn)中擴(kuò)展了塊管理器，引入了引用表，它為每個(gè)數(shù)據(jù)分區(qū)維護(hù)一個(gè)引用計(jì)數(shù)。data分區(qū)的引用計(jì)數(shù)表示共享該data分區(qū)的mrdds的個(gè)數(shù)。參考表的一個(gè)例子如圖4所示，其中數(shù)據(jù)分區(qū)rdd1-p1的參考計(jì)數(shù)為1，因?yàn)樗槐籱RDD1使用，而數(shù)據(jù)分區(qū)“rdd1-p2”的參考計(jì)數(shù)為2，因?yàn)樗籱RDD1和mRDD2共享。
當(dāng)RDD創(chuàng)建一個(gè)數(shù)據(jù)分區(qū)時(shí)，將該數(shù)據(jù)分區(qū)對(duì)應(yīng)的新行插入到引用表中，并將其引用計(jì)數(shù)初始化為1。當(dāng)一個(gè)新的RDD共享這個(gè)數(shù)據(jù)分區(qū)時(shí)，它的引用計(jì)數(shù)增加1。類似地，當(dāng)共享該數(shù)據(jù)分區(qū)的RDD被釋放時(shí)，該數(shù)據(jù)分區(qū)對(duì)應(yīng)的引用計(jì)數(shù)減1。最后，當(dāng)一個(gè)數(shù)據(jù)分區(qū)的引用計(jì)數(shù)等于0時(shí)，該數(shù)據(jù)分區(qū)及其物理數(shù)據(jù)塊可以被安全釋放。注意，參考表可以使用chronicles map實(shí)現(xiàn)。此外，Dragoon系統(tǒng)中的每個(gè)節(jié)點(diǎn)都由其塊管理器維護(hù)一個(gè)參考表。
RDD共享機(jī)制可以在不同的數(shù)據(jù)RDD之間共享數(shù)據(jù)分區(qū)，并將RDD的生命周期與其數(shù)據(jù)分區(qū)的生命周期解耦。假設(shè)有一個(gè)RDD，它有1000個(gè)數(shù)據(jù)分區(qū)，只有一個(gè)分區(qū)需要更新，這可能是由軌跡數(shù)據(jù)編輯或傳入的流軌跡管理引起的。為了支持這些類型的數(shù)據(jù)更新，Spark創(chuàng)建了一個(gè)新的RDD來維護(hù)一個(gè)更新后的分區(qū)，并復(fù)制其余的999個(gè)分區(qū)。相比之下，我們的系統(tǒng)dragoon創(chuàng)建了一個(gè)新的RDD，它維護(hù)更新的分區(qū)，但共享其余的999個(gè)分區(qū)。因此，RDD共享可以避免由于數(shù)據(jù)更新而產(chǎn)生的大量不必要的數(shù)據(jù)拷貝。
5.2 RDD 更新
在這個(gè)小節(jié)中，我們?cè)敿?xì)說明了如何更新那些由于軌跡編輯或軌跡流管理而需要更新的數(shù)據(jù)分區(qū)，我們稱之為RDD更新。RDD更新包含三種不同的數(shù)據(jù)更新策略，包括newest-only策略、share-append策略和share-update策略，在軌跡管理中提供了對(duì)不同相關(guān)更新場(chǎng)景的支持。為了展示如何使用這三種更新策略在我們的mrdd上執(zhí)行數(shù)據(jù)更新，我們使用如圖5所示的運(yùn)行示例，其中包括四個(gè)移動(dòng)物體o1,o2,o3, 和o4。在time0，它們的位置根據(jù)移動(dòng)物體的id信息分別存儲(chǔ)在四個(gè)數(shù)據(jù)分區(qū)(即P1、P2、P3和p4)中，其中o1(0)表示o1在時(shí)間0的位置。在time1時(shí)，移動(dòng)物體o1和o3分別生成新的位置o1(1)和do3(1)。因此，在這個(gè)運(yùn)行的例子中，Dragoon對(duì)于這兩個(gè)新的位置更新有三個(gè)更新策略。(i)以這兩個(gè)新地點(diǎn)取代舊值;(ii)將這兩個(gè)新地點(diǎn)附加在歷史數(shù)據(jù)的末尾;(iii)將這兩個(gè)新位置插入到相應(yīng)的歷史數(shù)據(jù)分區(qū)中。在本小節(jié)的下一部分，我們將繼續(xù)使用運(yùn)行的示例詳細(xì)介紹這三種更新策略的工作方式，并分析每種更新策略的優(yōu)勢(shì)、缺點(diǎn)和適應(yīng)的場(chǎng)景。
newest - only更新策略假設(shè)用戶只關(guān)注對(duì)象移動(dòng)時(shí)最新的位置數(shù)據(jù)值，這意味著移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)值可以直接忽略。這種場(chǎng)景在流設(shè)置中很常見，其中有狀態(tài)流和無狀態(tài)流計(jì)算都是基于最新數(shù)據(jù)的。此外，在編輯和清理軌跡數(shù)據(jù)時(shí)，通常只存儲(chǔ)最新的正確值，以節(jié)省存儲(chǔ)空間。newest - only策略不需要?jiǎng)?chuàng)建一個(gè)新的RDD來進(jìn)行更新，而是直接將舊mrdd中的舊值替換為新值。具體來說，為了執(zhí)行更新，我們首先確定數(shù)據(jù)分區(qū)的位置，然后，我們直接更新這個(gè)數(shù)據(jù)分區(qū)。這里，數(shù)據(jù)分區(qū)是可變的，因?yàn)樗怯蒀hronicle Map[20]實(shí)現(xiàn)的。但是，RDD及其數(shù)據(jù)分區(qū)不會(huì)在邏輯上發(fā)生改變。如圖5a所示，在兩次數(shù)據(jù)更新后，p1中的o1(0)被o1(1)取代，p3中的eo3(0)被o3(1)取代。newest - only更新策略是有用的，原因如下三。
——首先，Newest - only策略提供了使用Chronicle Map在rdd中進(jìn)行高效數(shù)據(jù)更新的可能性，這在許多應(yīng)用場(chǎng)景中都是必需的，比如軌跡編輯、軌跡清理和流軌跡處理。
——其次，Newest- only更新策略不會(huì)為數(shù)據(jù)更新操作創(chuàng)建新的RDD，與原始Spark相比，避免了數(shù)據(jù)復(fù)制相關(guān)的開銷。
——最后，當(dāng)數(shù)據(jù)更新時(shí)，最新策略總是在mrdd中保存最新的數(shù)據(jù)。因此，在連續(xù)實(shí)時(shí)提取數(shù)據(jù)時(shí)，可以不間斷地直接獲取最新的數(shù)據(jù)值，這在流軌跡處理設(shè)置中是有意義的。
然而，Newest- only更新策略有兩個(gè)局限性。首先，它用最新的新數(shù)據(jù)值替換以前的數(shù)據(jù)值，因此，歷史軌跡數(shù)據(jù)不再可用于進(jìn)一步的分析。因此，Newest-Only策略不能支持周期在線分析。其次，它更新了分布式環(huán)境中的數(shù)據(jù)，這可能會(huì)導(dǎo)致同時(shí)讀寫數(shù)據(jù)時(shí)數(shù)據(jù)不一致。因此，我們需要在讀取或?qū)懭雖rdd之前引入訪問權(quán)限，這會(huì)導(dǎo)致一些額外的時(shí)間成本，這將在“RDD鏡像”小節(jié)中詳細(xì)介紹。
share - append更新策略假設(shè)最新的數(shù)據(jù)值被追加到歷史數(shù)據(jù)值的末尾，其中歷史數(shù)據(jù)不需要更新。這個(gè)場(chǎng)景與歷史分析一致，其中包括流軌跡的最新位置和以前的位置。一個(gè)例子是找到在過去30分鐘[37]中一起移動(dòng)的移動(dòng)物體的軌跡。Share- append策略基于RDD Share，將新數(shù)據(jù)放在新創(chuàng)建的數(shù)據(jù)分區(qū)中。Share-Append的一個(gè)例子如圖5b所示，其中包含兩個(gè)更新的位置o1(1)和do3(1)的新數(shù)據(jù)分區(qū)p5和p6被追加到歷史存儲(chǔ)空間的末尾。使用Share-Appendupdate策略有三個(gè)優(yōu)勢(shì)。
——首先，Share-Append更新策略不會(huì)顯著影響數(shù)據(jù)分布。具體來說，當(dāng)歷史數(shù)據(jù)在系統(tǒng)中均勻分布時(shí)，share - append數(shù)據(jù)更新不會(huì)產(chǎn)生偏態(tài)分布。
——第二，Share-Append下的數(shù)據(jù)分區(qū)是根據(jù)軌跡的時(shí)間信息自然劃分的，有利于進(jìn)行時(shí)間濾波的軌跡分析。
——最新數(shù)據(jù)維護(hù)在新創(chuàng)建的數(shù)據(jù)分區(qū)中，對(duì)共享數(shù)據(jù)分區(qū)沒有影響。因此，使用Share-Append策略可以將共享的數(shù)據(jù)分區(qū)視為不可變的，從而避免了并發(fā)讀寫導(dǎo)致的數(shù)據(jù)不一致問題。
盡管Share-Append策略很簡(jiǎn)單，而且不會(huì)導(dǎo)致歷史軌跡數(shù)據(jù)的更新，但它有兩個(gè)缺點(diǎn)。首先，數(shù)據(jù)根據(jù)時(shí)間信息進(jìn)行分布。獲得不同的數(shù)據(jù)分布(例如:軌跡的空間信息)，歷史數(shù)據(jù)需要周期性的重新劃分和重建索引。第二，雖然一次更新不會(huì)對(duì)數(shù)據(jù)分布產(chǎn)生顯著影響，但連續(xù)的數(shù)據(jù)更新可能會(huì)導(dǎo)致查詢性能下降。
Share-Update更新策略假設(shè)每次只更新整個(gè)數(shù)據(jù)集的一小部分。這是因?yàn)橐苿?dòng)對(duì)象在特定時(shí)間生成的位置比整個(gè)數(shù)據(jù)集中所有存檔的歷史位置要少得多。Share- update策略基于RDD Share，即新創(chuàng)建的RDD共享數(shù)據(jù)分區(qū)而不改變數(shù)據(jù)，并通過插入新的傳入數(shù)據(jù)來復(fù)制其余的數(shù)據(jù)分區(qū)。注意，與neest - only策略不同，share - update中的更新是一個(gè)插入操作，而不是替換操作。Share-Update的一個(gè)例子如圖5c所示，其中p1中的數(shù)據(jù)被更新為o1(0,1)，而p3data被更新為o3(0,1)。Share- update將rdupdate機(jī)制與RDD共享相結(jié)合，具有以下優(yōu)點(diǎn)。
——首先，軌跡數(shù)據(jù)可以使用不同的數(shù)據(jù)分區(qū)策略進(jìn)行劃分，以支持靈活的數(shù)據(jù)平衡和高效的全局管理。
——第二，新的傳入數(shù)據(jù)可以均勻分布到不同的集群節(jié)點(diǎn)，以提高并行性和整體性能。
——最后，最新的軌跡數(shù)據(jù)保存在新復(fù)制的數(shù)據(jù)分區(qū)中，不會(huì)影響這些共享數(shù)據(jù)分區(qū)。
Share-Update策略可以有效地克服Newest- only和share -追加策略的缺點(diǎn)。盡管如此，它仍然需要額外的時(shí)間成本來應(yīng)用寫和讀權(quán)限，就像Newest-Only更新策略一樣。
綜上所述，dragoon系統(tǒng)提供了三種不同的數(shù)據(jù)更新策略，以形成針對(duì)不同軌跡相關(guān)更新場(chǎng)景的RDD更新。此外，每種更新策略都基于不同的假設(shè)，并有自己的優(yōu)勢(shì)和適應(yīng)場(chǎng)景。值得一提的是，Dragoon提出的mRDD模型與Spark原有的RDD模型是完全兼容的。因此，mrdd中現(xiàn)有的transformation和action操作與RDD支持的操作是一樣的。mRDD引入了更新機(jī)制來支持高效的數(shù)據(jù)更新，而數(shù)據(jù)更新屬于Spark惰性計(jì)算之后的一種轉(zhuǎn)換操作。
5.3RDD鏡像
在最初的RDD設(shè)計(jì)中，RDD是只讀的，不能直接更新;因此，不存在任何數(shù)據(jù)不一致。然而，正如前面所討論的，我們引入了mRDD模型來支持mRDD中的數(shù)據(jù)更新，這使得RDD是可寫可讀的。為了避免并發(fā)的數(shù)據(jù)讀寫導(dǎo)致的數(shù)據(jù)不一致，數(shù)據(jù)更新需要權(quán)限控制和鎖定機(jī)制來管理權(quán)限。由于可變RDD中的數(shù)據(jù)是在數(shù)據(jù)分區(qū)的粒度上存儲(chǔ)和管理的，讀寫權(quán)限也可以在數(shù)據(jù)分區(qū)的粒度上進(jìn)行控制。
在本小節(jié)中，我們將介紹RDD鏡像機(jī)制，該機(jī)制進(jìn)一步擴(kuò)展了塊管理器中的引用表，從而在分布式環(huán)境中實(shí)現(xiàn)讀寫權(quán)限和鎖。具體來說，RDD 鏡像記錄了每個(gè)數(shù)據(jù)分區(qū)的權(quán)限信息(即一個(gè)讀數(shù)和一個(gè)寫標(biāo)志)，如圖4所示。當(dāng)數(shù)據(jù)分區(qū)的寫標(biāo)志為0時(shí)，表示沒有任務(wù)在寫該數(shù)據(jù)分區(qū);否則，當(dāng)它的write標(biāo)志為1時(shí)，它表示一個(gè)任務(wù)正在寫這個(gè)數(shù)據(jù)分區(qū)。讀計(jì)數(shù)記錄并發(fā)運(yùn)行的次數(shù)。如圖4所示，假設(shè)數(shù)據(jù)分區(qū)rdd1-p2目前正在被兩個(gè)應(yīng)用程序讀取，其讀取計(jì)數(shù)為2。
當(dāng)任務(wù)向一個(gè)RDD申請(qǐng)讀寫權(quán)限時(shí)，會(huì)創(chuàng)建一個(gè)可用于恢復(fù)的RDD鏡像。RDD Mirror通過“RDD Share”共享所有未更改的分區(qū)，并更新更改后的數(shù)據(jù)分區(qū)的權(quán)限信息。在建立RDD鏡像之前，RDD鏡像需要檢查權(quán)限沖突。當(dāng)reference count和權(quán)限信息都更新成功后，RDD鏡像建立完全。RDD鏡像可以分為可讀RDD鏡像和可寫RDD鏡像。
可讀RDD鏡像當(dāng)應(yīng)用程序讀取一個(gè)RDD時(shí)，需要獲得讀權(quán)限才能為該RDD創(chuàng)建可讀鏡像?？勺xRDD鏡像與原始RDD共享所有的數(shù)據(jù)分區(qū)，并檢查每個(gè)數(shù)據(jù)分區(qū)的寫標(biāo)志。如果存在寫標(biāo)志為1的數(shù)據(jù)分區(qū)，則讀權(quán)限請(qǐng)求失敗;否則，如果數(shù)據(jù)分區(qū)的所有寫標(biāo)志為0，則其讀計(jì)數(shù)增加1。在讀取完成后，它們的讀取計(jì)數(shù)減少1。
可寫RDD mirror當(dāng)應(yīng)用程序更新RDD時(shí)，需要申請(qǐng)寫權(quán)限，并創(chuàng)建該RDD的可寫鏡像?？蓪慠DD鏡像要求其數(shù)據(jù)塊不被其他任務(wù)讀寫，即每個(gè)數(shù)據(jù)分區(qū)的讀次數(shù)和寫標(biāo)志都為0。在圖4中，如果應(yīng)用程序?qū)dd1-p2發(fā)出寫權(quán)限請(qǐng)求，由于rdd1-p2的讀次數(shù)為2，請(qǐng)求將失敗。如果這個(gè)寫權(quán)限請(qǐng)求沒有沖突，我們將RDD中所有數(shù)據(jù)分區(qū)的寫標(biāo)志設(shè)置為1。完成寫入后，寫入標(biāo)志設(shè)置為0。
5.4 容錯(cuò)
在這一小節(jié)中，我們將介紹與分布式處理過程和讀寫權(quán)限相關(guān)的Dragoon系統(tǒng)的容錯(cuò)機(jī)制。首先，Spark平臺(tái)提供了多個(gè)級(jí)別的數(shù)據(jù)持久性，包括任務(wù)和進(jìn)程級(jí)別。如果一個(gè)RDD沒有被緩存，它可以被認(rèn)為是在任務(wù)級(jí)被持久化了，這意味著如果任務(wù)失敗，數(shù)據(jù)將會(huì)丟失。當(dāng)緩存的RDD(內(nèi)存或磁盤)在進(jìn)程級(jí)被持久化時(shí)，這表示如果任務(wù)失敗，數(shù)據(jù)可以被恢復(fù)，但如果進(jìn)程崩潰，數(shù)據(jù)就會(huì)丟失。為了在更高的層次上持久化數(shù)據(jù)，用戶必須手動(dòng)和定期使用其他服務(wù)(例如HDFS)保存數(shù)據(jù)，這既不方便又耗時(shí)。
在Dragoon中，保存在Chronicle Map存儲(chǔ)中的軌跡數(shù)據(jù)在運(yùn)行時(shí)通過可靠的服務(wù)透明地保存。此外，這種持久性不會(huì)犧牲內(nèi)存中數(shù)據(jù)訪問的性能。為了實(shí)現(xiàn)這一點(diǎn)，一個(gè)Chronicle Map實(shí)例默認(rèn)是在共享內(nèi)存中的文件上創(chuàng)建的(例如，Linux下的/dev/shm)。該文件中的數(shù)據(jù)可以在任務(wù)失敗時(shí)保存，并且可以以內(nèi)存速度訪問。此外，為了作為一個(gè)可靠的分布式存儲(chǔ)，應(yīng)用了一些技術(shù)來防止歷史數(shù)據(jù)和流數(shù)據(jù)存儲(chǔ)的失敗。例如，dragoon會(huì)異步備份共享內(nèi)存或磁盤上的文件到一個(gè)可靠的文件系統(tǒng)(如HDFS)，這樣數(shù)據(jù)就可以在任務(wù)失敗或節(jié)點(diǎn)崩潰時(shí)存活下來。因此，丟失的數(shù)據(jù)可以在spark計(jì)算機(jī)制下自動(dòng)重新加載。此外，在Dragoon中更新數(shù)據(jù)mrdd時(shí)，將RDD 鏡像功能集成到每個(gè)節(jié)點(diǎn)的塊管理器中，實(shí)現(xiàn)讀寫權(quán)限和鎖。此外，在Chronicle Map中，每個(gè)更新請(qǐng)求都保存為一個(gè)日志文件，以確保按順序執(zhí)行數(shù)據(jù)更新。
6.混合分析
在本節(jié)中，我們將詳細(xì)介紹歷史和流軌跡數(shù)據(jù)的混合分析流水線。如第4節(jié)所述，流水線包含四個(gè)階段，即加載、預(yù)處理、管理和分析。因此，我們分別給出了離線和在線軌跡數(shù)據(jù)分析管道的四個(gè)階段的詳細(xì)信息。
6.1離線分析流水線
歷史軌跡數(shù)據(jù)的離線分析管道是簡(jiǎn)單的，因?yàn)檎麄€(gè)軌跡數(shù)據(jù)集是預(yù)先知道的，可以立即加載到Dragoon系統(tǒng)，以便后續(xù)處理。
加載：第一步是加載整個(gè)歷史軌跡數(shù)據(jù)集。歷史軌跡數(shù)據(jù)集通常存儲(chǔ)在HDFS系統(tǒng)中，因此可以并行加載到dragoon中。在這個(gè)階段，提供了一個(gè)可定制的數(shù)據(jù)加載器來支持不同的文件格式(例如，txt, csv，或xml)。
預(yù)處理：第二階段包括格式轉(zhuǎn)換(如軌跡指向段)、數(shù)據(jù)劃分和索引構(gòu)建?？啥ㄖ频臄?shù)據(jù)分區(qū)如下所示，該數(shù)據(jù)分區(qū)利用軌跡的不同特征(如id、空間或時(shí)間信息)對(duì)考慮軌跡不同特征的加載軌跡數(shù)據(jù)進(jìn)行分區(qū)。換句話說，具有相同或相似id/空間位置/時(shí)間特征的軌跡將被發(fā)送到相同的數(shù)據(jù)分區(qū)進(jìn)行并行處理。
——IDPartitioneris基于Spark的HashPartitioner，偽代碼如算法1所示。它需要輸入整個(gè)歷史軌跡數(shù)據(jù)和分區(qū)鍵值。對(duì)于S中的每個(gè)軌跡T，算法首先計(jì)算它所屬的數(shù)據(jù)分區(qū)的partitionidof(第2行)。ID表示生成此軌跡t的移動(dòng)對(duì)象的ID。接下來，它將T發(fā)送到這個(gè)數(shù)據(jù)分區(qū)，其中具有相同partitionids的軌跡將被分配到相同的數(shù)據(jù)分區(qū)(第3行)。
——GridPartitioneris受grid索引[44]的啟發(fā)，偽代碼見算法2。它以整個(gè)歷史軌跡數(shù)據(jù)集和網(wǎng)格寬度作為輸入。對(duì)于S中的每個(gè)軌跡T的每個(gè)位置，算法首先計(jì)算屬于(第3行)的空間網(wǎng)格單元格的網(wǎng)格。r.l是這個(gè)GPS記錄r的空間位置，包括r. l.s 和r.l.y。接下來，它將r發(fā)送到相應(yīng)的數(shù)據(jù)分區(qū)，其中相同空間網(wǎng)格單元中的位置被分配到相同的數(shù)據(jù)分區(qū)(第4行)。
———STRPartitioneris受到STR樹[27]的啟發(fā)，其偽代碼在算法3中給出。它以整個(gè)歷史軌跡數(shù)據(jù)集和r -樹的葉節(jié)點(diǎn)數(shù)作為輸入。算法首先對(duì)整個(gè)軌跡數(shù)據(jù)集S進(jìn)行隨機(jī)采樣(第2行)，得到一個(gè)采樣的數(shù)據(jù)集SampleDataset，然后利用樣本數(shù)據(jù)集，應(yīng)用STR算法[27]和n_nodes構(gòu)建一個(gè)r -樹(第3行)。它根據(jù)r樹將S劃分為幾個(gè)大小大致相等的不相交的數(shù)據(jù)分區(qū)(第4-7行)。與以前的GridPartitioner相比，STRPartitioner可以實(shí)現(xiàn)更好的負(fù)載平衡，因?yàn)樗鶕?jù)整個(gè)數(shù)據(jù)集的數(shù)據(jù)分布來劃分?jǐn)?shù)據(jù)集
——TimePartitioneris也是基于spark的HashPartitioner的，偽代碼見算法4。它還接受整個(gè)歷史軌跡數(shù)據(jù)集和一個(gè)分區(qū)鍵值作為輸入。對(duì)于每條軌跡的每條GPS記錄，算法首先根據(jù)GPS記錄的時(shí)間信息計(jì)算屬于(第3行)的數(shù)據(jù)分區(qū)的partitionid。值得一提的是。time表示生成該GPS記錄時(shí)的特定時(shí)間戳。接下來，TimePartitioner將把每個(gè)r發(fā)送到相應(yīng)的數(shù)據(jù)分區(qū)，表明具有類似時(shí)間戳的軌跡被分發(fā)到相同的數(shù)據(jù)分區(qū)(第4行)。
使用不同的軌跡數(shù)據(jù)分配器，Dragoon系統(tǒng)可以支持更靈活的數(shù)據(jù)平衡。在數(shù)據(jù)分區(qū)之后，Dragoon將構(gòu)建本地索引和全局索引，類似于在UlTra-Man[20]中完成的方式。具體來說，Dragoon在每個(gè)數(shù)據(jù)分區(qū)中建立一個(gè)本地索引，然后根據(jù)所有數(shù)據(jù)分區(qū)的特性建立一個(gè)全局索引。例如，為了構(gòu)建一個(gè)全局r-樹，Dragoon需要從每個(gè)數(shù)據(jù)分區(qū)收集pid和mbr，其中pid是分區(qū)ID, MBR是分區(qū)的空間最小邊界。
管理：歷史軌跡數(shù)據(jù)管理包括如何存儲(chǔ)數(shù)據(jù)和索引。Dragoon的存儲(chǔ)是基于Chronicle Map實(shí)現(xiàn)的，Chronicle Map是一種離堆內(nèi)存和嵌入式鍵值存儲(chǔ)，設(shè)計(jì)用于低延遲和多進(jìn)程訪問。我們之所以采用Chronicle Map來存儲(chǔ)軌跡數(shù)據(jù)，是因?yàn)樗峁┝烁咝У臄?shù)據(jù)更新，并且可以緩解Spark中的垃圾收集器的壓力。與Spark相比，我們基于Chronicle Map的系統(tǒng)具有更好的可伸縮性，這在第8節(jié)的實(shí)驗(yàn)中得到了證實(shí)。
分析：離線軌跡分析包含歷史軌跡數(shù)據(jù)的典型查詢和挖掘任務(wù)。利用全局索引對(duì)離線分析進(jìn)行全局過濾，從而加速離線分析的速度，然后利用每個(gè)數(shù)據(jù)分區(qū)的本地索引對(duì)離線分析結(jié)果進(jìn)行局部分析。關(guān)于我們?cè)诒竟ぷ髦嘘P(guān)注的歷史軌跡數(shù)據(jù)的離線分析任務(wù)的更多細(xì)節(jié)將在在Sect.7中討論。
6.2在線分析流水線
流式軌跡數(shù)據(jù)在線分析管道如圖6所示。流軌跡數(shù)據(jù)的在線分析不僅需要關(guān)注最新的軌跡數(shù)據(jù)值，還需要將最新的軌跡數(shù)據(jù)與歷史軌跡數(shù)據(jù)進(jìn)行融合。值得一提的是，最新的數(shù)據(jù)是在最近的時(shí)間點(diǎn)到達(dá)的數(shù)據(jù)。對(duì)于最新的在線分析，我們的目標(biāo)是所有移動(dòng)對(duì)象的最新空間數(shù)據(jù)值，而不是最新時(shí)間點(diǎn)的新傳入數(shù)據(jù)。這是因?yàn)椴皇撬幸苿?dòng)的物體都會(huì)在每個(gè)時(shí)間點(diǎn)更新它們的位置。例如，在圖5中，最新的(即新到達(dá)的)數(shù)據(jù)包括o_1(1)和o_3(1)，而四個(gè)移動(dòng)對(duì)象在t1時(shí)刻的最新數(shù)據(jù)值都是o1(1)、o2(0)、o3(1)和o4(0)，其中o2和o4在time1時(shí)刻不更新位置。另外，后者是我們重點(diǎn)關(guān)注的最新在線分析。相比之下，另一時(shí)期的在線分析，我們的目標(biāo)是最新和以前的數(shù)據(jù)值的移動(dòng)對(duì)象。
加載：在第一階段，dragoon不斷地從軌跡流讀取新到達(dá)的數(shù)據(jù)。系統(tǒng)讀取數(shù)據(jù)流的方式與Spark Streaming類似，Spark Streaming讀取最近幾秒(例如，每5秒)的數(shù)據(jù)流，每批流數(shù)據(jù)作為一個(gè)獨(dú)立的RDD處理。離線分析中使用的定制數(shù)據(jù)加載器也可以在這里使用。
預(yù)處理：雖然在線和離線軌跡預(yù)處理都需要基于軌跡id、空間位置或時(shí)間信息的數(shù)據(jù)劃分過程和索引構(gòu)建過程，但在線和離線預(yù)處理之間存在一些差異。首先，離線軌跡數(shù)據(jù)劃分以整個(gè)歷史軌跡數(shù)據(jù)集為輸入，只執(zhí)行一次數(shù)據(jù)劃分，而流軌跡數(shù)據(jù)由實(shí)時(shí)分塊器進(jìn)行劃分，實(shí)時(shí)分塊器以每次觀察到的運(yùn)動(dòng)對(duì)象的軌跡數(shù)據(jù)點(diǎn)為輸入，并實(shí)時(shí)執(zhí)行每次數(shù)據(jù)分區(qū)。其次，離線分析的索引構(gòu)造通常也只執(zhí)行一次，并且(本地和全局)索引通常不需要更新。然而，在流軌跡設(shè)置中，不僅數(shù)據(jù)分區(qū)中的軌跡數(shù)據(jù)需要在下一個(gè)合并過程階段更新，本地和全局索引也需要更新。
——在線IdPartitioner類似于離線軌跡預(yù)處理的IdPartitioner，偽代碼如算法5所示。不同的是，在線IdPartitioner將新到達(dá)的軌跡點(diǎn)的集合S_t和一個(gè)分區(qū)鍵值 k作為輸入。對(duì)于S_t中的每個(gè)GPS點(diǎn)r，算法首先計(jì)算該數(shù)據(jù)分區(qū)的partitionid(第2行)。接下來,它將r發(fā)送給相應(yīng)的數(shù)據(jù)分區(qū)(第3行)。請(qǐng)注意,mRDD更新過程,新到達(dá)的軌跡點(diǎn)的合并歷史軌跡數(shù)據(jù),將在第二階段執(zhí)行。與算法1不同，算法5每次都重復(fù)上述處理。
———在線GridPartitioner，偽代碼如算法6所示，該算法與算法2類似。唯一不同的是，在線方法以t時(shí)刻新到達(dá)的軌跡點(diǎn)集合St作為輸入，而離線方法以整個(gè)軌跡數(shù)據(jù)作為輸入。注意，后續(xù)的合并過程將通過將新數(shù)據(jù)與該數(shù)據(jù)分區(qū)中的歷史軌跡數(shù)據(jù)合并來執(zhí)行。但是，每次移動(dòng)對(duì)象生成的所有位置的網(wǎng)格單元都是固定的，這可能會(huì)導(dǎo)致傾斜分區(qū)。為了獲得更好的數(shù)據(jù)分區(qū)和數(shù)據(jù)平衡，還提供了Online STRPartitioner，如下所示。
———Online STRPartitioneris也類似于離線軌跡預(yù)處理的strpartitioner，其偽代碼見算法7。它以t時(shí)刻新到達(dá)的軌跡點(diǎn)的集合St作為輸入，而不是整個(gè)軌跡數(shù)據(jù)集。與在線GridPartitioner相比，在線STR-Partitioner能夠?qū)崿F(xiàn)更好的負(fù)載平衡，因?yàn)樗鶕?jù)每個(gè)St的數(shù)據(jù)分布實(shí)時(shí)劃分?jǐn)?shù)據(jù)集。
——在線TimePartitioner可以通過Dragoon的Share-Append策略輕松實(shí)現(xiàn)，因?yàn)檐壽E流是按照時(shí)間順序來實(shí)現(xiàn)的。因此，本文略述具體算法。
管理：在線軌跡管理包括將新到達(dá)的軌跡點(diǎn)與歷史軌跡數(shù)據(jù)進(jìn)行合并的過程。在前一個(gè)預(yù)處理階段的實(shí)時(shí)分區(qū)程序可以一直生成相同的分區(qū)(如IDPartitioner和gridpartitioner)，或者在不同的時(shí)間生成不同的分區(qū)（如 TimePartitioner和STRPartitioner)。在前一種情況下，我們使用基于mRDD模型的Newest - only或share - update策略直接將partitioned St分配到相應(yīng)的現(xiàn)有數(shù)據(jù)分區(qū)，如圖6中紅色的“Merge1”所示。在后一種情況下，我們使用Share-Append策略將新創(chuàng)建的數(shù)據(jù)分區(qū)添加到現(xiàn)有的分區(qū)中，以實(shí)現(xiàn)圖6中的“Merge2”。在合并過程中，可寫RDD鏡像和可讀RDD鏡像同時(shí)使用，避免了數(shù)據(jù)的不一致性:一個(gè)用于更新處理，另一個(gè)用于結(jié)果讀取處理。此外，本地索引和全局索引在數(shù)據(jù)合并后也需要更新。
分析:流式軌跡數(shù)據(jù)在線分析包括最新在線分析和周期在線分析，如圖6所示。最新的在線分析只考慮所有移動(dòng)對(duì)象的最新數(shù)據(jù)。而周期在線分析需要給定時(shí)間段內(nèi)的最新數(shù)據(jù)和歷史數(shù)據(jù)。關(guān)于軌跡流在線分析的更多細(xì)節(jié)將在第7節(jié)中討論。
7.分析案例研究
我們通過幾個(gè)典型的離線和在線軌跡數(shù)據(jù)分析案例研究展示了Dragoon的靈活性，包括(在線)ID查詢、(在線)范圍查詢、(在線)最近鄰(kNN)查詢、離線軌跡編輯和軌跡流上的實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式檢測(cè)。
首先，O= < o1,o2，…，om >是一個(gè)移動(dòng)物體的集合，其中每個(gè)oi∈O(1≤i≤m)是一個(gè)移動(dòng)物體，它可以產(chǎn)生如下定義的軌跡或流軌跡。
定義一(軌跡).由移動(dòng)的物體i(1≤i≤m)在地理空間中生成的軌跡Ti，通常用按時(shí)間順序排列的gps記錄序列表示，即Ti= < r1,r2，…，rn >。每個(gè)GPS recordrj(1≤j≤n)∈Tican表示為一個(gè)三元組(id,l,time)，其中是objectoid(id=i)在timestamp時(shí)間戳的空間位置。注意，它通常由年齡空間坐標(biāo)集(經(jīng)度、緯度)組成。
定義二(流軌跡).由移動(dòng)物體o_i(1≤i≤m)產(chǎn)生的流軌跡也是一個(gè)GPS記錄的時(shí)序序列，即STi= < r1,r2，…>。注意，不同于軌跡T_i，運(yùn)動(dòng)物體的流動(dòng)軌跡是無界的。
因此，一個(gè)靜態(tài)軌跡數(shù)據(jù)集(STD)包含了所有由o生成的軌跡，即STD= < T1,T2，…，Tm >。動(dòng)態(tài)軌跡數(shù)據(jù)集(DTD)包含由o生成的所有流軌跡，即DTD= < ST1,ST2，…，STm >。在續(xù)集中，我們分別介紹了基于歷史軌跡數(shù)據(jù)和流態(tài)軌跡數(shù)據(jù)的典型離線和在線軌跡分析案例。此外，對(duì)這些分析案例的實(shí)驗(yàn)評(píng)估將在第8節(jié)詳細(xì)介紹。
7.1軌跡編輯
給定一個(gè)靜態(tài)軌跡數(shù)據(jù)集STD，可能存在噪聲采樣點(diǎn)[57]。例如，當(dāng)GPS接收器在城市峽谷和衛(wèi)星能見度較差時(shí)，可能會(huì)發(fā)生不準(zhǔn)確的位置。為了消除這些軌跡噪聲點(diǎn)，采用了軌跡編輯操作。具體來說，軌跡編輯的目的是將有噪聲的軌跡點(diǎn)更新為正確的軌跡點(diǎn)。如圖2a所示，由于rdd的不變性，Spark中軌跡編輯會(huì)導(dǎo)致很多不必要的數(shù)據(jù)復(fù)制。相比之下，Dragoon提供了mRDD模型，可以直接更新數(shù)據(jù)rdds，如圖2b所示，為軌跡數(shù)據(jù)的管理和維護(hù)提供了更有效、更強(qiáng)大的機(jī)制。
7.2ID查詢和在線ID查詢
ID查詢和在線ID查詢的目的是根據(jù)ID信息找到一個(gè)特定的軌跡，這在軌跡監(jiān)控場(chǎng)景中非常有用，如下所述。
定義3(ID查詢和在線ID查詢).給定一個(gè)特定的ID, ID查詢和在線ID查詢分別查找由運(yùn)動(dòng)對(duì)象oi生成的STD中的軌跡T_i和DTD中的流軌跡ST_i?，其中i= ID。
對(duì)于離線ID查詢，IdPartitioner首先根據(jù)移動(dòng)對(duì)象的ID將整個(gè)軌跡數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)分區(qū)，從而實(shí)現(xiàn)后續(xù)的并行處理。如算法1所示，如果設(shè)置k= 10000，則IdPartitioner可以將id介于0 ~ 10000之間的移動(dòng)對(duì)象分配給數(shù)據(jù)分區(qū)p0，將id介于10001 ~ 20000之間的移動(dòng)對(duì)象分配給數(shù)據(jù)分區(qū)p1，以此類推。然后，我們?cè)诿總€(gè)分區(qū)中構(gòu)建一個(gè)本地Hash索引，其中對(duì)象ID作為鍵，軌跡點(diǎn)作為值。由于Chronicle Map 本身是一個(gè)哈希映射，因此可以基于Chronicle Map 存儲(chǔ)輕松地實(shí)現(xiàn)本地哈希索引。接下來，可以根據(jù)所有數(shù)據(jù)分區(qū)的特性構(gòu)建全局索引。分區(qū)的特性包括分區(qū)ID和該數(shù)據(jù)分區(qū)中的移動(dòng)對(duì)象ID范圍?？紤]到上面描述的例子，全局索引包含< (P0.ID，[0,10000])， (P1.ID，[10001,20000])，…>。最后，ID查詢可以使用全局索引根據(jù)給定ID過濾不必要的數(shù)據(jù)分區(qū)，并且可以使用局部Hash索引直接找到最終結(jié)果。
對(duì)于在線ID查詢，實(shí)時(shí)的IdPartitioner根據(jù)流軌跡的ID將在時(shí)間t(S_t)上新到達(dá)的軌跡點(diǎn)分配給幾個(gè)數(shù)據(jù)分區(qū)，然后將它們與每個(gè)數(shù)據(jù)分區(qū)中的歷史位置合并。在線ID查詢是最新的在線分析的一個(gè)實(shí)例，因?yàn)樗祷亓鬈壽E的當(dāng)前位置，其ID每次都等于給定的ID;因此，在線ID查詢是在每個(gè)時(shí)間點(diǎn)上對(duì)所有流軌跡的當(dāng)前位置進(jìn)行的。因此，第5節(jié)中介紹的三種不同的更新策略都可以用于合并處理。此外，我們還需要在軌跡合并后更新本地和全局索引。
7.3范圍查詢和在線范圍查詢
范圍查詢和在線范圍查詢的目的是在一定的空間范圍范圍內(nèi)查找軌跡，在流量監(jiān)控和熱點(diǎn)檢測(cè)[57]等應(yīng)用中非常有用，定義如下。
定義4(范圍和在線范圍查詢).給定特定的空間搜索區(qū)域Q、一個(gè)STD和一個(gè)DTD，范圍查詢查找STD中與Q相交的軌跡，而在線范圍查詢查找DTD中當(dāng)前空間位置位于q內(nèi)的流軌跡。注意，搜索區(qū)域Q通常表示為一個(gè)矩形< [minx,miny]，[maxx,maxy] >。
對(duì)于離線范圍查詢，我們采用GridPartitioner基于軌跡空間信息對(duì)STD進(jìn)行分區(qū)，在每個(gè)數(shù)據(jù)分區(qū)上建立一個(gè)局部的r樹，在整個(gè)軌跡數(shù)據(jù)集STD上建立一個(gè)全局的網(wǎng)格索引。全局網(wǎng)格索引可以過濾那些沒有與搜索區(qū)域Q相交的數(shù)據(jù)分區(qū)，然后利用局部r樹對(duì)候選分區(qū)進(jìn)行范圍查詢，得到最終結(jié)果。
對(duì)于在線范圍查詢，在線GridPartitioner首先用于從流軌跡中劃分新的傳入點(diǎn)(St)，然后將傳入點(diǎn)與相應(yīng)數(shù)據(jù)分區(qū)的歷史數(shù)據(jù)合并。在線范圍查詢也是最新的在線分析實(shí)例。它返回當(dāng)前位置包含在搜索區(qū)域q中的運(yùn)行軌跡，并對(duì)所有流軌跡的最新位置執(zhí)行查詢。因此，可以使用這三種更新策略來合并數(shù)據(jù)。同時(shí)，在數(shù)據(jù)合并后更新相應(yīng)的本地索引和全局索引。
7.4KNN查詢和在線KNN查詢
kNN查詢和在線kNN查詢旨在為特定的空間位置找到最精確的軌跡，這對(duì)于基于位置的服務(wù)非常有用，如軌跡分類和車輛共享[13]，如下所定義。
定義 5(kNN查詢和在線kNN查詢).給定某個(gè)位置l,一個(gè)STD，一個(gè)DTD和一個(gè)正整數(shù)k>=1,,k近鄰查詢找到在STD中和l最近的k條軌跡,即Rk = {Ti | 1≤i≤k d (Ti, l)≤d (Tj,l) (Tj /∈Rk)},和在線KNN查詢發(fā)現(xiàn)在DTD中的k條流軌跡,也就是說,工作= {STi | 1≤≤k d (STi.rt l)≤d (STj.rt l) (STj /∈工作)}。請(qǐng)注意，位置l到軌跡Ti或STi之間的距離計(jì)算(Ti,l)和d(STi,l)遵循工作[13]，盡管其他距離函數(shù)也可以在Dragoon系統(tǒng)中實(shí)現(xiàn)。
對(duì)于離線kNN查詢，我們采用strpartitioner[47]根據(jù)軌跡數(shù)據(jù)的空間信息對(duì)其進(jìn)行統(tǒng)一劃分。在這里，使用R-tree變體[20]來提高knn查詢效率，其中R-tree的每個(gè)節(jié)點(diǎn)保持最小邊界矩形(MBR)和包含在MBR中的不同軌跡的計(jì)數(shù)。在knn查詢期間，使用全局過濾來獲得具有相同軌跡計(jì)數(shù)的候選數(shù)據(jù)分區(qū)，然后，在候選分區(qū)中分別執(zhí)行l(wèi)ocalkNN查詢。最后，候選分區(qū)的局部結(jié)果按照它們到查詢位置的距離升序排序，然后返回全局top-k軌跡。
對(duì)于在線kNN查詢，我們?cè)谌謗 -樹索引中使用mbr而不是STRPartitioner來從流軌跡中劃分最新的位置。這是因?yàn)閟trpartitioner可能會(huì)為數(shù)據(jù)合并帶來額外的成本，如6.2節(jié)所述。接下來，我們合并數(shù)據(jù)并更新本地和全局索引。與在線ID和Range查詢類似，在線kNN查詢是最新在線分析的一個(gè)實(shí)例。在線kNN查詢每次返回k條軌跡，其當(dāng)前位置最接近查詢位置;因此，它是在所有流軌跡的最新位置上執(zhí)行的。因此，這三種更新策略都可以用于數(shù)據(jù)合并。
7.5協(xié)同運(yùn)動(dòng)模式檢測(cè)
協(xié)同運(yùn)動(dòng)模式檢測(cè)旨在發(fā)現(xiàn)滿足特定時(shí)空約束[14]的協(xié)同運(yùn)動(dòng)目標(biāo)，包括緊密度、顯著性M、持續(xù)時(shí)間K、連續(xù)性L和連接度g。這在許多應(yīng)用中都是有用的，比如未來運(yùn)動(dòng)預(yù)測(cè)。實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式檢測(cè)是周期在線分析的一個(gè)例子，因此，我們必須考慮每個(gè)流軌跡的最新位置和歷史位置。
我們直接采用最先進(jìn)的方法[14]進(jìn)行實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式挖掘。但是，Dragoon的底層系統(tǒng)與flink平臺(tái)不同，可以實(shí)現(xiàn)更好的可擴(kuò)展性。這是因?yàn)椋瑸榱藢?shí)現(xiàn)高性能，F(xiàn)link中的狀態(tài)存儲(chǔ)是基于堆上內(nèi)存的，這對(duì)垃圾收集器(GC)有很大的壓力，特別是對(duì)于大軌跡數(shù)據(jù)的維護(hù)和處理。相比之下，我們的系統(tǒng)使用Chronicle Map進(jìn)行物理存儲(chǔ)，它是離堆內(nèi)存，在保證效率的同時(shí)減輕了GC壓力。此外，F(xiàn)link中狀態(tài)維護(hù)的流軌跡數(shù)據(jù)在流分析完成后發(fā)布。相比之下，Dragoon提供了流軌跡數(shù)據(jù)的永久存儲(chǔ)，因此，這些數(shù)據(jù)可以用于未來的后續(xù)軌跡分析。
由于實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式檢測(cè)是周期在線分析的一個(gè)實(shí)例，因此不再采用newest - only更新策略。這是因?yàn)閚ewest- only策略直接丟棄了移動(dòng)對(duì)象之前的位置值。協(xié)同移動(dòng)模式檢測(cè)方法在查詢過程中更新索引，進(jìn)一步提高查詢效率。另外,中間結(jié)果(如。集群)也需要被存儲(chǔ)。該方法包含聚類和枚舉兩個(gè)階段。在聚類階段，可以使用Share-Append和Share-Update策略合并數(shù)據(jù);對(duì)于枚舉階段，只能使用Share-Update策略，因?yàn)槲覀冃枰鶕?jù)ID對(duì)數(shù)據(jù)進(jìn)行分區(qū)，以實(shí)現(xiàn)并行模式檢測(cè)(即，ID分區(qū)在方法[14]中使用)。
8 實(shí)驗(yàn)評(píng)估
在本節(jié)中，我們將用第7節(jié)中討論的典型軌跡分析案例來評(píng)估dragoon的性能，并將其與現(xiàn)有的最新型的離線軌跡管理系統(tǒng)UlTraMan以及包括spark Streaming和Flink在內(nèi)的通用在線處理系統(tǒng)進(jìn)行比較。回想一下，Dragoon的核心組件是mRDD模型，基于該模型，混合軌跡數(shù)據(jù)分析包括離線和在線分析可以被有效支持。因此，在后續(xù)的實(shí)驗(yàn)中，我們?cè)u(píng)估了dragoon的兩個(gè)組件，即mRDD模型和混合軌跡數(shù)據(jù)分析的性能。(i)為了驗(yàn)證mRDD模型的性能，我們首先報(bào)告基于mRDD模型的離線軌跡編輯的性能，然后，我們報(bào)告在線軌跡查詢期間的數(shù)據(jù)更新性能。這是因?yàn)椋趫?zhí)行在線ID/范圍/kNN查詢分析時(shí)，dragoon首先將新到達(dá)的軌跡點(diǎn)與底層存儲(chǔ)中的歷史軌跡數(shù)據(jù)合并。此合并過程主要基于mRDD模型，評(píng)估了dragoon提供的三種更新策略(Newest-Only、Share-Append、Share-Update)。(ii)為了評(píng)估混合軌跡數(shù)據(jù)分析的性能，我們使用了幾個(gè)典型的離線(即ID/范圍/kNN查詢)和在線(即實(shí)時(shí)運(yùn)動(dòng)模式檢測(cè)和ID/范圍/kNN查詢)軌跡分析案例，如第7節(jié)所討論的。
在我們的實(shí)驗(yàn)中，我們使用了兩個(gè)現(xiàn)實(shí)生活中的數(shù)據(jù)集(例如:例如，GeoLife和Taxi)和一個(gè)合成數(shù)據(jù)集(即Brinkhoff)，其詳細(xì)信息包括軌跡數(shù)、位置數(shù)、快照數(shù)、平均長(zhǎng)度和數(shù)據(jù)大小，總結(jié)在表1中
-GeoLife:這個(gè)數(shù)據(jù)集保存了每個(gè)用戶3年以上的GPS記錄。gps信息的采集是周期性的，91%的軌跡采樣間隔為5s。
-Taxi:該數(shù)據(jù)集由中國(guó)杭州的出租車生成。軌跡由出租車的車牌號(hào)識(shí)別，每條軌跡代表一輛出租車3個(gè)月的軌跡，每5秒采樣一次。
- Brinkhoff:該數(shù)據(jù)集由Brinkhoff生成器生成。軌跡是在拉斯維加斯城市的真實(shí)道路網(wǎng)絡(luò)上生成的。運(yùn)動(dòng)物體的位置每1秒更新一次，物體以隨機(jī)但合理的方向和速度沿著道路網(wǎng)絡(luò)移動(dòng)。
實(shí)驗(yàn)參數(shù)設(shè)計(jì)如表2
在實(shí)驗(yàn)中，我們研究了五個(gè)參數(shù)的不同設(shè)置對(duì)性能的影響，如表2中總結(jié)的，其中默認(rèn)值以粗體顯示。這里，n代表在軌跡編輯中對(duì)靜態(tài)軌跡數(shù)據(jù)集的編輯次數(shù)。第二，o_r表示離線軌跡分析案例中運(yùn)動(dòng)物體w.r.t的百分比，表示在線分析過程中每次更新的運(yùn)動(dòng)物體的百分比。此外，ξ表示(online) range查詢中使用的查詢區(qū)域w.r.t，即包含所有軌跡點(diǎn)的整個(gè)區(qū)域的大小。k表示(在線)kNN查詢中的k。n表示Dragoon系統(tǒng)的從工作節(jié)點(diǎn)數(shù)。另外，實(shí)時(shí)協(xié)同運(yùn)動(dòng)模式檢測(cè)中使用的參數(shù)設(shè)置為之前工作中默認(rèn)值[14]，即M=15,K=180,L=30, g =30。注意，在下面的實(shí)驗(yàn)中，我們采用L1范數(shù)作為軌跡兩個(gè)位置之間的相似距離進(jìn)行簡(jiǎn)化。但是，它很容易支持其他距離函數(shù)。
性能指標(biāo)(i)對(duì)于ID/Range/kNN查詢和軌跡編輯，執(zhí)行時(shí)間(即每個(gè)查詢或編輯的平均處理時(shí)間)被用來評(píng)估它們的性能。(ii)對(duì)于在線id /Range/kNNquery和協(xié)同移動(dòng)模式檢測(cè)，我們使用時(shí)延和吞吐量作為性能指標(biāo)。更具體地說，對(duì)于在線ID/Range/kNN查詢，我們分別驗(yàn)證更新和查詢處理階段。在更新階段，目標(biāo)是找到相應(yīng)的數(shù)據(jù)分區(qū)，然后將新到達(dá)的軌跡點(diǎn)插入到歷史數(shù)據(jù)分區(qū)中，更新延遲表示將當(dāng)前St(所有到達(dá)timet的點(diǎn))插入到歷史軌跡中的平均時(shí)間，而整個(gè)更新表示系統(tǒng)每秒插入的次數(shù)。在查詢階段處理中，查詢延遲被定義為每個(gè)在線ID/Range/kNN查詢的平均響應(yīng)時(shí)間，并且整個(gè)查詢表示系統(tǒng)每秒處理的ID/Range/kNN查詢的數(shù)量。我們還報(bào)告了在數(shù)據(jù)更新處理場(chǎng)景中系統(tǒng)的內(nèi)存占用情況，包括在線ID/Range/kNN查詢的軌跡編輯和更新階段。
9.總結(jié)
在本文中，我們提出了一種新型的、混合的、高效的彈道數(shù)據(jù)管理和分析系統(tǒng)——dragoon系統(tǒng)。為了同時(shí)支持歷史軌跡和流軌跡的管理，龍騎采用了mRDD模型，包括RDD Share、RDD Update和RDD Mirror。RDD Update提供了三種針對(duì)不同場(chǎng)景的更新策略，分別是:newest - only、Share- append和Share-Update; RDD Mirror提供了在分布式環(huán)境下避免數(shù)據(jù)一致性的讀寫控制。此外，Dragoon的混合分析管道為歷史軌跡和流軌跡提供支持。對(duì)大型真實(shí)和合成數(shù)據(jù)集的實(shí)驗(yàn)研究提供了對(duì)Dragoon的可伸縮性和性能的洞察力，并與最先進(jìn)的系統(tǒng)進(jìn)行了比較，得出了以下結(jié)果:
-對(duì)于歷史軌跡數(shù)據(jù)，dragoon在離線軌跡查詢方面的性能與現(xiàn)有軌跡系統(tǒng)UlTraMan相當(dāng)。然而，在軌跡編輯場(chǎng)景中，dragoon可以減少多達(dá)兩倍的存儲(chǔ)開銷。
-對(duì)于流軌跡數(shù)據(jù)，盡管現(xiàn)有的通用流系統(tǒng)Spark streaming和Flink能夠在小工作量的情況下提供更高的更新效率，但Dragoon至少實(shí)現(xiàn)了40%的可伸縮性，并為最新的在線分析提供了平均兩倍的性能改進(jìn)
-Share-Append更新效率最高，而Newest-Only查詢效率最高。但是，newtest - only不適合周期在線分析，Share-Append只支持時(shí)態(tài)數(shù)據(jù)劃分。
未來，應(yīng)用dragoon進(jìn)行更大的軌跡數(shù)據(jù)管理和處理，設(shè)計(jì)更有效的指標(biāo)來支持更多類型的軌跡數(shù)據(jù)分析(如離線軌跡相似度計(jì)算和在線子軌跡聚類)是值得關(guān)注的。此外，擴(kuò)展mRDD模型用于通用大數(shù)據(jù)管理或開發(fā)另一個(gè)新的數(shù)據(jù)集增強(qiáng)模型用于大結(jié)構(gòu)化數(shù)據(jù)分析也是一個(gè)很有前途的方向。
