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

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

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

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

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

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

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

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