大規(guī)模實(shí)時(shí)數(shù)據(jù)流連接關(guān)鍵技術(shù)的研究.pdf

1、互聯(lián)網(wǎng)、傳感器以及物聯(lián)網(wǎng)等技術(shù)的發(fā)展，使數(shù)據(jù)產(chǎn)生的速度越來越快。無處不在的數(shù)據(jù)中隱藏著各種有價(jià)值的信息，這些信息給人們的日常生活提供了便利。
　　在很多應(yīng)用中，信息以數(shù)據(jù)流的形式提供給用戶，這些信息帶有很強(qiáng)的時(shí)效性，要求用戶以“on-the-fly”的形式進(jìn)行處理。另外，由于設(shè)備以及應(yīng)用特點(diǎn)的限制，單條數(shù)據(jù)流往往只能提供部分?jǐn)?shù)據(jù)，用戶需要將多條數(shù)據(jù)流結(jié)合起來才能獲取完整信息。連接(Join)作為獲取綜合信息的有效手段之一，在數(shù)據(jù)流

2、處理中占有重要地位。
　　大數(shù)據(jù)時(shí)代的到來使單節(jié)點(diǎn)的計(jì)算模式已經(jīng)不能滿足數(shù)據(jù)流連接的需求，由多個(gè)“shared-nothing”廉價(jià)節(jié)點(diǎn)構(gòu)成的集群成為解決該問題的有效手段之一。本文在深入研究和總結(jié)相關(guān)工作的基礎(chǔ)上，圍繞分布式環(huán)境下多路數(shù)據(jù)流的連接問題展開研究，內(nèi)容主要集中在以下幾個(gè)方面:
　　首先，在數(shù)據(jù)流模型下提出了基于增量計(jì)算的Compressed直方圖構(gòu)建和維護(hù)算法。在允許的誤差范圍內(nèi)，Compressed直方圖可以反

3、映當(dāng)前滑動(dòng)窗口中數(shù)據(jù)的大致分布情況，為接下來多路數(shù)據(jù)流的連接優(yōu)化問題提供支持，該部分為后面研究的基礎(chǔ)。
　　其次，針對二路數(shù)據(jù)流的特點(diǎn)提出了基于流水線的二路數(shù)據(jù)流連接算法。該算法將計(jì)算節(jié)點(diǎn)以線性形式組織，將兩條數(shù)據(jù)流以相向的方式注入流水線，可以處理二路數(shù)據(jù)流等值及不等值連接，在不需要數(shù)據(jù)備份的條件下能夠保證結(jié)果的完整性。另外，在流水線模型下提出了基于上游備份的容錯(cuò)機(jī)制、類似按壓橡皮泥的負(fù)載均衡機(jī)制以及可擴(kuò)展性機(jī)制等。
　　再

4、次，針對多路數(shù)據(jù)流等值連接的特點(diǎn)提出了基于一致性hash的多路數(shù)據(jù)流等值連接分配算法，該算法在保證相關(guān)聯(lián)元組能夠分配到相同節(jié)點(diǎn)的前提下，可以維持各個(gè)計(jì)算節(jié)點(diǎn)間的負(fù)載均衡。另外，根據(jù)直方圖提供的信息，在數(shù)據(jù)流連接過程中采用基于貪心的算法實(shí)時(shí)維持連接樹，保證數(shù)據(jù)流以相對較優(yōu)的順序執(zhí)行，減少網(wǎng)絡(luò)傳輸及連接過程的執(zhí)行時(shí)間。
　　最后，對通用性更強(qiáng)的多路數(shù)據(jù)流非等值連接進(jìn)行了研究，提出了基于范圍hash和共享時(shí)間片的分配策略。這兩個(gè)策略在兼

5、顧結(jié)果完整性和負(fù)載均衡的同時(shí)，也盡量減少備份數(shù)據(jù)的傳遞量，降低網(wǎng)絡(luò)負(fù)載。另外，針對很多應(yīng)用滑動(dòng)窗口中連接屬性屬于多重集的情況，提出了基于(key，valueList)的“GroupJoin”連接算法，降低網(wǎng)絡(luò)傳輸量，在某些情況下減少執(zhí)行時(shí)間。
　　本文從分布式多路數(shù)據(jù)流連接出發(fā)，提出了適合二路數(shù)據(jù)流連接的流水線算法、適合等值連接的一致性hash算法以及適合非等值連接的范圍hash和共享時(shí)間片算法，并在這些算法的基礎(chǔ)上提出了一系列的