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

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

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

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

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

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

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

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