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

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

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

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

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

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