大規模動態演化圖的存儲與分析系統研究圖數據通過頂點和邊的結構表達實體間的相互聯系。圖數據的分析計算技術,也稱圖挖掘技術,是通過分析實體間聯系,獲得關于實體的性質、特征等重要信息的一項技術,正廣泛地應用于信息檢索、社交分析、生物計算等多個領域。本文所述的圖存儲分析系統是支持圖分析計算的平臺系統。它利用抽象的編程接口支持圖分析算法的高效實現,利用優化的系統設計提供高效的算法執行,從而實現超大規模的圖數據分析。在大數據時代的今天,大規模圖存儲與分析系統及其相關技術已經成為一個重要的研究方向。而近年來,隨著社交網絡媒體、移動互聯網等新型應用的普及,信息的組織方式、傳播方式等,正發生著新的變化——信息呈現出更為明顯的動態化特征。隨著這一變化,捕捉了數據時序特征的動態演化圖,其數據挖掘分析的價值正受到更多的重視,并隨著演化圖數據分析理論研究的同步深入,逐漸成為一個新的發展趨勢。然而現有的圖存儲與分析平臺系統針對的是靜態圖,并不適合動態演化圖。因此,本文研究問題的重點,就在于：如何針對動態演化圖分析這一類新的應用,設計并實現高效的大規模存儲分析系統。我們通過分析,將動態演化圖相關的應用主要總結為：(1)分析動態演化圖準實時狀態和(2)分析動態演化圖長期變化趨勢兩類。前者著重于分析動態演化圖的最新狀態,而后者著重于分析動態演化圖的長期歷史變化過程。在文中,我們為這兩類應用算法,設計并實現了動態演化圖存儲、分析系統。該系統以圖數據的實時變化作為輸入,產生具有全局一致性的圖數據更新,并用于動態演化圖準實時狀態分析；同時,它會將接收到的時序數據存儲下來,重新組織并用于動態演化圖長期變化趨勢分析。在系統的設計實現中,我們將針對動態演化圖準實時狀態分析和動態演化圖長期變化趨勢分析的兩部分功能分別抽象成以下兩個子問題加以解決：一、動態演化圖在線分析的系統問題。在該問題中,大量新的圖數據高速產生,應用需要不斷地對最新的圖數據進行在線處理,從而得到準實時的分析結果。然而實現準實時分析,數據的處理延遲需要足夠低。此外,在分布式環境下,還需保持動態數據訪問的全局一致性,從而保證分析結果的正確性。為此,我們設計了動態演化圖在線分析子系統。該子系統的架構的設計考慮了處理流程的耦合關系,對圖數據存儲和分析計算進行了解耦。它選用了一個“時段提交”技術來處理圖更新,并為系統的計算部分提出了全新的增量計算模型,大大降低分析計算的延遲。我們完成了該系統的工程實現,并在1億條真實推特文本數據上進行了包括爭議話題探測、近似最短路徑計算、用戶排序等多種應用的測試。利用40臺機器組成的集群,我們獲得了10萬每秒的推文處理速率,并保持2.5分鐘以內的數據延遲,滿足了我們最初設定的“遠超推文的產生速率”的性能要求。二、動態演化圖離線分析的系統問題。在該問題中,系統需要保存動態演化圖的長期歷史數據,并支持動態演化圖長期變化趨勢的離線分析。相對于靜態圖分析處理的是單一的靜態圖,長時間跨度動態演化圖分析面對的是多個時間點對應的一系列靜態圖。更大的數據量帶來更高的處理開銷,因而系統分析計算的性能非常重要。此外,系統還需要為動態演化圖復雜多變的存取模式提供高效的訪問性能,為分析性能提供保障。為此我們在文中提出了動態演化圖離線分析子系統。它的副本相異數據排布技術利用數據中心多個數據備份的特點,為動態演化圖不同類型的訪問提供不同針對性的數據組織方式,從而在復雜多變的存取訪問中獲得更好的數據存取性能;利用全新的局部性感知分批調度技術——局部性分批調度,我們提高了分析計算中高速緩存的利用率并減少了數據同步的開銷,極大地改善了長時間跨度動態演化圖分析的整體性能。在實際大規模動態演化圖進行的多項應用測試結果表明,該系統能夠提供相對于目前數據庫系