大規(guī)模動態(tài)演化圖的存儲與分析系統(tǒng)研究.pdf

1、圖數(shù)據(jù)通過頂點和邊的結(jié)構(gòu)表達(dá)實體間的相互聯(lián)系。圖數(shù)據(jù)的分析計算技術(shù)，也稱圖挖掘技術(shù)，是通過分析實體間聯(lián)系，獲得關(guān)于實體的性質(zhì)、特征等重要信息的一項技術(shù)，正廣泛地應(yīng)用于信息檢索、社交分析、生物計算等多個領(lǐng)域。本文所述的圖存儲分析系統(tǒng)是支持圖分析計算的平臺系統(tǒng)。它利用抽象的編程接口支持圖分析算法的高效實現(xiàn)，利用優(yōu)化的系統(tǒng)設(shè)計提供高效的算法執(zhí)行，從而實現(xiàn)超大規(guī)模的圖數(shù)據(jù)分析。在大數(shù)據(jù)時代的今天，大規(guī)模圖存儲與分析系統(tǒng)及其相關(guān)技術(shù)已經(jīng)成為一個重

2、要的研究方向。
　　而近年來，隨著社交網(wǎng)絡(luò)媒體、移動互聯(lián)網(wǎng)等新型應(yīng)用的普及，信息的組織方式、傳播方式等，正發(fā)生著新的變化——信息呈現(xiàn)出更為明顯的動態(tài)化特征。隨著這一變化，捕捉了數(shù)據(jù)時序特征的動態(tài)演化圖，其數(shù)據(jù)挖掘分析的價值正受到更多的重視，并隨著演化圖數(shù)據(jù)分析理論研究的同步深入，逐漸成為一個新的發(fā)展趨勢。然而現(xiàn)有的圖存儲與分析平臺系統(tǒng)針對的是靜態(tài)圖，并不適合動態(tài)演化圖。因此，本文研究問題的重點，就在于:如何針對動態(tài)演化圖分析這一類

3、新的應(yīng)用，設(shè)計并實現(xiàn)高效的大規(guī)模存儲分析系統(tǒng)。
　　我們通過分析，將動態(tài)演化圖相關(guān)的應(yīng)用主要總結(jié)為:(1)分析動態(tài)演化圖準(zhǔn)實時狀態(tài)和(2)分析動態(tài)演化圖長期變化趨勢兩類。前者著重于分析動態(tài)演化圖的最新狀態(tài)，而后者著重于分析動態(tài)演化圖的長期歷史變化過程。在文中，我們?yōu)檫@兩類應(yīng)用算法，設(shè)計并實現(xiàn)了動態(tài)演化圖存儲、分析系統(tǒng)。該系統(tǒng)以圖數(shù)據(jù)的實時變化作為輸入，產(chǎn)生具有全局一致性的圖數(shù)據(jù)更新，并用于動態(tài)演化圖準(zhǔn)實時狀態(tài)分析;同時，它會將接收

4、到的時序數(shù)據(jù)存儲下來，重新組織并用于動態(tài)演化圖長期變化趨勢分析。在系統(tǒng)的設(shè)計實現(xiàn)中，我們將針對動態(tài)演化圖準(zhǔn)實時狀態(tài)分析和動態(tài)演化圖長期變化趨勢分析的兩部分功能分別抽象成以下兩個子問題加以解決:
　　一、動態(tài)演化圖在線分析的系統(tǒng)問題。在該問題中，大量新的圖數(shù)據(jù)高速產(chǎn)生，應(yīng)用需要不斷地對最新的圖數(shù)據(jù)進(jìn)行在線處理，從而得到準(zhǔn)實時的分析結(jié)果。然而實現(xiàn)準(zhǔn)實時分析，數(shù)據(jù)的處理延遲需要足夠低。此外，在分布式環(huán)境下，還需保持動態(tài)數(shù)據(jù)訪問的全局一致

5、性，從而保證分析結(jié)果的正確性。為此，我們設(shè)計了動態(tài)演化圖在線分析子系統(tǒng)。該子系統(tǒng)的架構(gòu)的設(shè)計考慮了處理流程的耦合關(guān)系，對圖數(shù)據(jù)存儲和分析計算進(jìn)行了解耦。它選用了一個“時段提交”技術(shù)來處理圖更新，并為系統(tǒng)的計算部分提出了全新的增量計算模型，大大降低分析計算的延遲。我們完成了該系統(tǒng)的工程實現(xiàn)，并在1億條真實推特文本數(shù)據(jù)上進(jìn)行了包括爭議話題探測、近似最短路徑計算、用戶排序等多種應(yīng)用的測試。利用40臺機器組成的集群，我們獲得了10萬每秒的推文處

6、理速率，并保持2.5分鐘以內(nèi)的數(shù)據(jù)延遲，滿足了我們最初設(shè)定的“遠(yuǎn)超推文的產(chǎn)生速率”的性能要求。
　　二、動態(tài)演化圖離線分析的系統(tǒng)問題。在該問題中，系統(tǒng)需要保存動態(tài)演化圖的長期歷史數(shù)據(jù)，并支持動態(tài)演化圖長期變化趨勢的離線分析。相對于靜態(tài)圖分析處理的是單一的靜態(tài)圖，長時間跨度動態(tài)演化圖分析面對的是多個時間點對應(yīng)的一系列靜態(tài)圖。更大的數(shù)據(jù)量帶來更高的處理開銷，因而系統(tǒng)分析計算的性能非常重要。此外，系統(tǒng)還需要為動態(tài)演化圖復(fù)雜多變的存取模式

7、提供高效的訪問性能，為分析性能提供保障。為此我們在文中提出了動態(tài)演化圖離線分析子系統(tǒng)。它的副本相異數(shù)據(jù)排布技術(shù)利用數(shù)據(jù)中心多個數(shù)據(jù)備份的特點，為動態(tài)演化圖不同類型的訪問提供不同針對性的數(shù)據(jù)組織方式，從而在復(fù)雜多變的存取訪問中獲得更好的數(shù)據(jù)存取性能;利用全新的局部性感知分批調(diào)度技術(shù)——局部性分批調(diào)度，我們提高了分析計算中高速緩存的利用率并減少了數(shù)據(jù)同步的開銷，極大地改善了長時間跨度動態(tài)演化圖分析的整體性能。在實際大規(guī)模動態(tài)演化圖進(jìn)行的多項