圖引擎底層存儲的設計與實現

馬洪賓,陳貴海

(上海交通大學計算機科學與工程系,上海200240)

圖引擎底層存儲的設計與實現

馬洪賓,陳貴海

(上海交通大學計算機科學與工程系,上海200240)

隨著社交網絡和語義Web等數據應用的興起,催生了許多圖數據處理產品,包括Neo4j,HyperGraphDB等,然而這些產品在設計時并未充分考慮圖應用對數據可用性和可擴展性的更高要求。為此,提出一種基于分布式內存云的圖引擎底層建模和存儲解決方案。在內存云上搭建分布式鍵值引擎,進而在鍵值存儲的基礎上對圖的數據進行建模和讀寫。在大規模數據集上的實驗結果表明,該方案具有較好的圖隨機訪問性能,并能夠高效地支持海量規模的圖數據應用。

圖處理;云計算;分布式;數據建模;存儲;數據結構

1 概述

圖是最常見的數據結構之一,與線性表和樹相比,它的結構更加復雜,對數據的表現能力也更豐富。傳統的圖應用包括道路分析［1］、論文引用分析［2］、網頁鏈接分析［3］等。 隨著社交網絡［4-5］、語義網絡［6］等研究領域的興起,由于圖在表示實體間關系方面的顯著優勢,因此越來越多的研究嘗試使用圖來存儲和挖掘數據。

學術界和工業界已有大量工作致力于圖的應用和理論研究。截止目前,已有很多圖數據庫產品可供選擇。但是隨著數據規模的日益增長,圖的規模也隨之呈現爆發式增長的趨勢。如何有效地存儲和使用海量規模的圖數據集,成為圖數據庫領域內的一大難題。

本文結合圖數據應用對可用性和可擴展性的要求,提出一種基于分布式內存Key-Value引擎的圖數據存儲和建模方案,介紹底層使用的分布式內存云引擎,根據圖應用對數據建模的需求分析建模技術,并將已知的語義Web數據集導入到系統中,對系統性能進行全面分析。

2 圖數據應用及其挑戰

2.1 使用圖數據結構進行數據建模的優勢

在已知的大數據問題中,有很大一部分的問題可以由圖進行更為直觀的建模。而且這種直觀的建模方式可以帶來高效的數據讀寫效率。以社交網絡為例,網絡中的兩大元素:人物與人物之間的關系,可以分別對應到圖里面的頂點和邊。假設采用鄰接表的形式存儲圖的邊,那么所有的邊都可以保存在頂點上。人物的一些屬性,例如姓名、年齡等,可以作為頂點的屬性存放在頂點內。與此相對地,也可以使用關系數據庫將數據建模成為一個人物表和一個朋友關系表。當客戶端程序需要獲取某個特定人物的朋友列表時,假設采用圖建模的方式,程序可以首先找到代表該人物的圖頂點,然后通過一次頂點內的訪問獲得其所有鄰居。而在關系數據庫中,需要將朋友關系表與人物表進行一次內聯結才能達到相同目的。當然,用戶可以選擇對朋友關系表中的外鍵來加速這一過程,但這又勢必會帶來了額外開銷。

無論是在單機的多核計算處理器上,還是在分布式環境中的多機多處理器環境下,對并行計算是否友好都已經成為衡量一個模型好壞的重要標準。在圖模型的領域,以頂點為中心的計算模型因為它的簡單性、可擴展性和靈活性而被廣泛地采用。在以頂點為中心的計算模型中,每個頂點都可以成為最細粒度的計算單元,一個或者多個頂點的計算工作可以由同一個操作系統線程或進程負責,以頂點為中心的計算模型可以將工作量自然地切割,并且適用于同步和異步、集中式和分布式的計算模型。

2.2 圖數據庫面臨的挑戰

傳統的圖數據庫面臨可用性與可擴展性［7］之間的博弈。傳統圖數據庫可以粗略地分為以下3類:

(1)基于磁盤存儲的單機實現

已有的借助磁盤存儲空間的單機圖數據庫,雖然能夠在假設磁盤空間沒有限制的前提下,克服數據的規模問題。根據程序訪問局部性原理,這類圖數據庫也可以在內存中緩存適量的緩存,以期減少數據訪問的開銷。然而,圖應用的隨機訪問性質決定了程序在圖中對頂點的訪問呈現隨機的特征,因此難以找到一種簡單通用的緩存算法來加速數據訪問。而大量的隨機讀寫是對磁盤訪問速度的災難。因此,基于磁盤的解決方案會帶來不能接受的性能問題。

(2)基于MapReduce/Hadoop的實現

這類實現的典型代表為PEGASUS［8］,一個基于Hadoop的分布式圖信息挖掘系統。Hadoop對應Google的分布式計算框架MapReduce［9］,它的文件系統HFS(Hadoop File System)對應于MapReduce的GFS(Google File System)［10］。圖數據以文件的形式存放在HFS中。雖然這類實現在可擴展性和容錯性方面得到了保證,但是Hadoop的計算模型與圖數據上的計算需求并不完全匹配。Hadoop的作業調度與任務分配要求對數據的反復讀寫,這造成了同樣的圖信息被反復地在磁盤中讀寫,增加了系統的 I/O開銷。另外,為離線數據分析而設計的Hadoop也不能滿足對反應時間具有更高要求的在線圖數據查詢需求。

(3)基于分布式和列式存儲的實現

在MapReduce后,Google相繼推出了基于GFS的列存儲引擎BigTable［11］以及Dremel［12］。這類列式儲引擎將數據的不同維度(列)單獨存儲,并且可以靈活地根據數據的使用頻率,將某些常用維度的數據配置在內存中,以減少磁盤I/O,提高讀寫性能。列式存儲需要對數據模型具有嚴格定義。在圖數據中,使用鄰接表來表示頂點間的關系。鄰接表的一個基本性質是其長度可變,而像BigTable這樣的列式存儲引擎對這一性質并無很好的支持。可變長、可嵌套、可重復的列成員在Dremel中被引入,但是由于Dremel是一個只讀的交互式在線分析系統,圖數據的頂點增加/刪除、關系的增加/刪除就無法被支持。

3 基于分布式內存云的圖引擎存儲解決方案

3.1 分布式內存云引擎——Trinity

Trinity是微軟亞洲研究院設計并實現的服務于云計算的一款輕量的高性能分布式內存Key-Value存儲引擎［13］。在Trinity系統中,所有數據都被保存在內存云中,因此能夠支撐每秒數百萬次的隨機讀寫。另外,Trinity支持通過配置服務器集群的方式,靈活地調整系統的服務能力［14］。Trinity向客戶端提供以下統一接口:

Trinity作為一個Key-Value存儲引擎,其中的Key僅限長整數類型,而Value則是一段不定長的字節數組,稱為BLOB。因此,Trinity可以看作是一個long-＞BLOB的Key-Value存儲引擎。

從單機角度觀察,Trinity在啟動時向操作系統申請大塊的內存,用以對 BLOB進行動態儲存。Trinity封裝了高效的內存管理模塊,可以進行高效的垃圾收集和內存清理。另外,Trinity提供細粒度的鎖機制,保證對于單個鍵值對的修改是原子的。從集群角度觀察,每個Trinity的服務器實例負責維護一批BLOB,Trinity系統通過對Key的哈希對不同BLOB進行分割。各個實例之間由高速以太網互聯。

3.2 在BLOB上的圖頂點建模

Trinity中的每個BOLB都是獨立的個體,彼此之間互相獨立,且每個BLOB擁有全局唯一的長整數標識符。在BLOB的不同區間段內存儲不同的信息,可以自然地將BLOB隱射成圖數據中的頂點,如圖1所示。每個頂點中存儲的信息可以分為兩部分:屬性和邊。然而,BLOB只是簡單的字節數組,無法為上層應用提供更多數據格式的信息。因此,需要在BLOB上搭建數據訪問層,以便上層圖處理程序能夠有效獲得感興趣的圖信息。

圖1 每個BLOB視作一個圖頂點的情況

圖的應用千變萬化,對圖頂點和邊的定義也會存在巨大差異。例如,一個典型社交網絡可能需要定義人物這樣的圖頂點,也需要把人物和人物之間的關系定義為圖中的邊。而在一個語義Web的圖應用中,用戶可能更希望將任意的主語和賓語定義為圖頂點,而將謂詞定義為圖中的關系。總而言之,一個通用的圖引擎無法提前預知圖應用所需的數據結構,因此允許用戶提前對圖的結構進行定義。例如,社交網絡中的人物頂點可以由以下語句定義:

根據定義,所有人物頂點的實例都由一個整數記錄其年齡,一個字符串記錄其姓名,還有一個可變長的長整數容器記錄其所有朋友的標識符。對頂點的定義模仿了面向對象語言(例如Java)中對類的定義。然而,在實際存儲方式上卻完全不同。在面向對象語言中,對象只保存各個非基本類型成員的引用,成員具體的內容保存在堆上,其物理地址并不一定相鄰。而在實現中,由于需要將圖頂點所有的信息保存到一段BLOB中,成員會按序依次排列,所有成員在存儲邏輯地址上是保證相鄰的,稱為線性排列。

采用基于BLOB的線性排列,而不采用類似于面向對象語言基于堆的儲存方式的主要原因有以下2個方面:

(1)前者相對于后者更具空間優勢。為了克服傳統圖數據庫在可用性上的瓶頸,達到最高效的訪問速度來適應圖的隨機訪問性質,考慮將大部分的圖數據放入內存中。盡管采用分布式的內存云引擎作為底層存儲,但是考慮到內存云的代價,更經濟有效地利用內存空間仍然具有重要的意義。以對象為單元存儲圖頂點,涉及到引用類型的開銷,以及對象本身的開銷(例如對象上的鎖)等。事實上,在64 bit.NET平臺上,一個空對象也需要占據12 Byte的空間。因此,以BLOB的形式存儲圖頂點更具空間優勢。

(2)以BLOB形式存儲的節點更有利于在分布式環境中分發傳送。在不同機器間傳送對象,需要首先在發送端將對象序列化成字節序列,然后通過網絡傳送至接收端,并由接收端負責將字節序列反序列化成對象,單個對象的序列化和反序列化的開銷可能難以察覺,但是在大型的圖應用中,通常需要在不同機器間傳輸成千上萬的圖頂點。在這種情況下,序列化和反序列化的代價就變得十分顯著。然而,基于BLOB的儲存形式無需經歷序列化和反序列化的過程,BLOB本身就是字節數組,可以直接在網絡上傳輸。

3.3 具體實現

為了能夠用方便的接口讀寫BLOB中的數據,需要將用戶定義的圖頂點類型編譯并生成相應的訪問器。

3.3.1 訪問器類的生成

對于每種類型的圖頂點,為它的每一個成員分配一個訪問器。根據成員的長度是否固定,訪問器又可以細分為定長訪問器和變長訪問器。定長訪問器適用于對基本類型成員的訪問,而可變長的成員如字符串、線性容器等需要由變長訪問器來訪問。例如人物頂點中,由于age成員占據固定4 Byte的空間,因此只需分配一個定長訪問器IntegerAccessor來訪問它,而對于name成員來說,由于無法提前確定該字符串的長度,使用變長訪問器StringAccessor訪問它。同理,成員friends的類型是長整數線性表,也需要生成一個變長訪問器LongListAccessor才能訪問它。

可以看到,對于每種成員類型,需要為其生成對應的訪問器類型。已知的最大規模圖應用需要定義數千種頂點類型,但是由于不同頂點類型的成員類型存在大量重復,例如同樣的StringAccessor適用于任何擁有字符串成員的頂點類型,因此訪問器類型的種類數目反而不是很多。訪問器訪問BLOB內數據的方式如圖2所示。

圖2 使用訪問器的BLOB數據訪問

在初始化訪問器實例時,傳入成員的指針,以便訪問器知道成員從何開始。對與定長訪問器而言,無需額外的信息,即可了解數據存放的格式。例如,如果在給定開始指針之后,一個IntegerAccessor就明白在開始指針之后的4 Byte就是需要訪問的整數數據。而對于變長訪問器而言,需要借助一些輔助信息才能夠確定數據的格式。例如,對于所有簡單數據類型的線性表容器,如List＜long＞類型,在成員的開始用一個整數的空間存放該容器的大小,當一個LongListAccessor訪問這個成員時,首先讀取首部4 Byte的容器大小信息,然后將指針向后偏移4 Byte,才開始真正訪問數據。

3.3.2 動態容器擴容的支持

圖應用的數據處于經常性的變化之中。社交網絡中的人物隨時會增加新的好友關系,同時也有可能解除原有的好友關系。因此,可支持動態增減的容器類型不可或缺。由于本文設計一個圖頂點所有的數據順序存放在一個固定大小的字節數組中,因此任何一個容器的擴容都有可能導致空間不足。可以觀察到,在圖2中,BLOB的尾端有一部分不屬于任何成員的空間,稱為緩沖區。當任何一個容器試圖擴容,請求更多的空間時,如果緩沖區的大小足夠,那么該擴容請求可以通過簡單的向后生長來實現。如圖3所示。如果緩沖區的大小不足以支持當前的擴容請求,那么需要向Trinity系統申請一塊更大的內存區間來存放擴容后的新數據,同時把原有的內存區間標記為廢棄,以便Trinity內置的內存垃圾收集器能夠回收利用。

圖3 容器擴容

3.3.3 嵌套支持

為向圖應用提供更豐富的建模工具,允許用戶自行定義除了圖頂點之外的結構體,并允許在圖頂點的定義中直接嵌套使用它。以社交網絡中的人物為例,如果對于每個好友,不僅希望保存他的標識符,還希望保存對各個不同好友的備注簽名,那么可以將好友關系定義為一個特定結構體,在這個結構體中分別記錄好友的標識符和對好友的備注簽名,這種情況下人物的朋友成員可以按以下方式定義:

在存儲上,結構體會以和基本類型相似的方式,順序保存在BLOB中。不同的是,系統會為每個結構體生成特別的訪問器,保證結構體能被正確地讀寫。另外,結構體的引入增加了成員內存管理的復雜度,為了支持嵌套成員的擴容和縮減,每個成員都需要保存其上層成員的Resize函數指針,在需要擴容或縮減時,各個成員遞歸地調用Resize方法,直到傳遞到最終能夠處理該事件的圖頂點自身。對于好友關系中的備注簽名成員alias,如果希望將其修改成更長的字符串,就需要向上遞歸地調用結構體Friendship、容器FriendshipList以及圖頂點Person的Resize函數。該過程如圖4所示。

圖4 遞歸調用Resize方法

4 實驗結果與分析

基于分布式內存云的圖引擎存儲解決方案,首先借助內存云的優良擴展性,解決了可擴展性的問題,能夠對海量圖數據的存儲和計算提供較好的支持。在實驗中,將RDF(Resource Description Framework)數據集導入到圖引擎中。原數據集采用文本記錄,大小超過1 TB,擁有約110億條三元組,導入到圖引擎中共生成了30億個頂點、50億條邊。即使采用基于BLOB的緊湊內存存儲結構,整個數據集仍然占用了480 GB左右的內存。

基于內存的底層存儲對圖的隨機訪問具有較好的支撐,因此圖引擎在可用性上體現出較大優勢。圖5是對17個不同類型的圖頂點成員進行隨機訪問所花費的時間。橫坐標從P01至P17分別代表不同的17種查詢,縱坐標表示所花費時間。

圖5 圖頂點成員隨機訪問速度

借助于性能優異的底層存儲引擎,上層的圖引擎應用能夠表現出更優異的性能。分別使用8臺96 GB DDR3內存的服務器存儲上文提到的RDF數據集,并使用高速路由InfiniteBand對服務器進行互聯,并使用子圖匹配算法對圖數據進行子圖搜索。圖6刻畫了若干查詢的響應速度,橫坐標從Q1至Q7分別代表7個不同的插敘,縱坐標即完成查詢的時間。

圖6 圖查詢響應速度

由圖5、圖6可以看出,分布式內存云引擎可以為圖引擎提供穩定高效的底層數據訪問。在此之上,圖引擎可以向客戶端提供幾十毫秒內的查詢響應時間,有助于客戶端高效快速地完成查詢任務。

5 結束語

在大數據環境背景下,圖數據處理面對上億規模頂點的海量數據處理問題。傳統的基于磁盤或者分布式文件系統的解決方案,在應對圖應用的大量隨機訪問請求時存在性能瓶頸。本文基于分布式內存云提出一種新穎的圖建模和存儲方案,可對上層圖應用提供靈活高效的數據訪問接口。實驗結果表明,本文方案能夠實現海量規模的圖數據處理。

［1］ Porta S,Crucitti P,Latora V.The Network Analysis of Urban Streets:A Dual Approach［J］.Physica A: Statistical Mechanics and Its Applications,2006, 369(2):853-866.

［2］ Narin F.Evaluative Bibliometrics:The Use of Publication and Citation Analysis in the Evaluation of Scientific Activity［M］.Cherry Hill,USA:Computer Horizons,1976.

［3］ Lawrence P.The PageRank Citation Ranking:Bringing Order to the Web［R］.Stanford University,Technical Report:SIDL-WP-1999-0120,1999.

［4］ Wasserman S.SocialNetwork Analysis:Methodsand Applications［M］.Cambridge,UK:Cambridge University Press,1994.

［5］ Mislove A.Measurement and Analysis of Online Social Networks［C］//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement.New York,USA: ACM Press,2007:29-42.

［6］ Berners-Lee T,Hendler J,Lassila O.The Semantic Web［J］.Scientific American,2001,284(5):28-37.

［7］ Ramakrishnan R,Gehrke J.Database Management Systems［M］.［S.l.］:McGraw-Hill,2000.

［8］ Deelman E.Pegasus:A Framework for Mapping Complex Scientific Workflows onto Distributed Systems［J］.Scientific Programming Journal,2005,13(3):219-237.

［9］ Dean J,Sanjay G.MapReduce:Simplified Data Processing on Large Clusters［J］.Communications of the ACM,2008, 51(1):107-113.

［10］ Ghemawat S,Howard G,Leung Shun-Tak.The Google File System［J］.ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

［11］ Chang F.Bigtable:A Distributed Storage System for Structured Data［J］.ACM Transactions on Computer Systems,2008,26(2):4-9.

［12］ Melnik S.Dremel:Interactive Analysis of Web-scale Datasets［J］.Proceedings of the VLDB Endowment, 2010,3(1/2):330-339.

［13］ Shao Bin,Wang Haixun,Li Yatao.Trinity:A Distributed Graph Engine on a Memory Cloud［C］//Proceedings of 2013 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2013:505-516.

［14］ 于 戈,谷 峪,鮑玉斌,等.云計算環境下的大規模圖數據處理技術［J］.計算機學報,2011,34(10): 1753-1768.

編輯 陸燕菲

Design and Implementation of Underlying Storage for Graph Engine

MA Hongbin,CHEN Guihai
(Department of Computer Science and Engineering,Shanghai Jiaotong University,Shanghai 200240,China)

Graph applications rise with the emerging of social network and semantic Web,and generate many graph data processing products,including Neo4j,HyperGraphDB,etc.However,current solutions fail to take into consideration graph applications'higher requirements on data availability and scalability.This paper proposes a modeling and storage solution based on distributed memory cloud.It takes advantage of the prior work to build a key-value system over the memory cloud,then builds data modeling and read-write based on it.Experimental results on large scaled datasets show that this solution has a good figure random access performance,and it can support massive graph applications efficiently.

graph processing;cloud computing;distributed;data modeling;storage;data structure

1000-3428(2014)11-0060-05

A

TP311

10.3969/j.issn.1000-3428.2014.11.012

馬洪賓(1989-),男,碩士研究生,主研方向:數據查詢處理,分布式系統,云計算;陳貴海,教授、博士生導師。

2013-11-18

2013-12-17E-mail:790123072@qq.com

中文引用格式:馬洪賓,陳貴海.圖引擎底層存儲的設計與實現［J］.計算機工程,2014,40(11):60-64.

英文引用格式:Ma Hongbin,Chen Guihai.Design and Implementation of Underlying Storage for Graph Engine［J］.Computer Engineering,2014,40(11):60-64.