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

大規(guī)模動(dòng)態(tài)演化圖的存儲(chǔ)與分析系統(tǒng)研究圖數(shù)據(jù)通過頂點(diǎn)和邊的結(jié)構(gòu)表達(dá)實(shí)體間的相互聯(lián)系。圖數(shù)據(jù)的分析計(jì)算技術(shù),也稱圖挖掘技術(shù),是通過分析實(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è)重要的研究方向。而近年來,隨著社交網(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ā)展趨勢。然而現(xiàn)有的圖存儲(chǔ)與分析平臺(tái)系統(tǒng)針對的是靜態(tài)圖,并不適合動(dòng)態(tài)演化圖。因此,本文研究問題的重點(diǎn),就在于：如何針對動(dòng)態(tài)演化圖分析這一類新的應(yīng)用,設(shè)計(jì)并實(shí)現(xiàn)高效的大規(guī)模存儲(chǔ)分析系統(tǒng)。我們通過分析,將動(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)演化圖長期變化趨勢兩類。前者著重于分析動(dòng)態(tài)演化圖的最新狀態(tài),而后者著重于分析動(dòng)態(tài)演化圖的長期歷史變化過程。在文中,我們?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ì)將接收到的時(shí)序數(shù)據(jù)存儲(chǔ)下來,重新組織并用于動(dòng)態(tài)演化圖長期變化趨勢分析。在系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)中,我們將針對動(dòng)態(tài)演化圖準(zhǔn)實(shí)時(shí)狀態(tài)分析和動(dòng)態(tài)演化圖長期變化趨勢分析的兩部分功能分別抽象成以下兩個(gè)子問題加以解決：一、動(dòng)態(tài)演化圖在線分析的系統(tǒng)問題。在該問題中,大量新的圖數(shù)據(jù)高速產(chǎn)生,應(yīng)用需要不斷地對最新的圖數(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ù)訪問的全局一致性,從而保證分析結(jié)果的正確性。為此,我們設(shè)計(jì)了動(dòng)態(tài)演化圖在線分析子系統(tǒng)。該子系統(tǒng)的架構(gòu)的設(shè)計(jì)考慮了處理流程的耦合關(guān)系,對圖數(shù)據(jù)存儲(chǔ)和分析計(jì)算進(jìn)行了解耦。它選用了一個(gè)“時(shí)段提交”技術(shù)來處理圖更新,并為系統(tǒng)的計(jì)算部分提出了全新的增量計(jì)算模型,大大降低分析計(jì)算的延遲。我們完成了該系統(tǒng)的工程實(shí)現(xiàn),并在1億條真實(shí)推特文本數(shù)據(jù)上進(jìn)行了包括爭議話題探測、近似最短路徑計(jì)算、用戶排序等多種應(yīng)用的測試。利用40臺(tái)機(jī)器組成的集群,我們獲得了10萬每秒的推文處理速率,并保持2.5分鐘以內(nèi)的數(shù)據(jù)延遲,滿足了我們最初設(shè)定的“遠(yuǎn)超推文的產(chǎn)生速率”的性能要求。二、動(dòng)態(tài)演化圖離線分析的系統(tǒng)問題。在該問題中,系統(tǒng)需要保存動(dòng)態(tài)演化圖的長期歷史數(shù)據(jù),并支持動(dòng)態(tài)演化圖長期變化趨勢的離線分析。相對于靜態(tài)圖分析處理的是單一的靜態(tài)圖,長時(shí)間跨度動(dòng)態(tài)演化圖分析面對的是多個(gè)時(shí)間點(diǎn)對應(yīng)的一系列靜態(tài)圖。更大的數(shù)據(jù)量帶來更高的處理開銷,因而系統(tǒng)分析計(jì)算的性能非常重要。此外,系統(tǒng)還需要為動(dòng)態(tài)演化圖復(fù)雜多變的存取模式提供高效的訪問性能,為分析性能提供保障。為此我們在文中提出了動(dòng)態(tài)演化圖離線分析子系統(tǒng)。它的副本相異數(shù)據(jù)排布技術(shù)利用數(shù)據(jù)中心多個(gè)數(shù)據(jù)備份的特點(diǎn),為動(dòng)態(tài)演化圖不同類型的訪問提供不同針對性的數(shù)據(jù)組織方式,從而在復(fù)雜多變的存取訪問中獲得更好的數(shù)據(jù)存取性能;利用全新的局部性感知分批調(diào)度技術(shù)——局部性分批調(diào)度,我們提高了分析計(jì)算中高速緩存的利用率并減少了數(shù)據(jù)同步的開銷,極大地改善了長時(shí)間跨度動(dòng)態(tài)演化圖分析的整體性能。在實(shí)際大規(guī)模動(dòng)態(tài)演化圖進(jìn)行的多項(xiàng)應(yīng)用測試結(jié)果表明,該系統(tǒng)能夠提供相對于目前數(shù)據(jù)庫系