鬼佬大哥大
  • / 15
  • 下載費用:30 金幣  

一種面向大規模社交網絡的圖數據存儲及查詢方法.pdf

關 鍵 詞:
一種 面向 大規模 社交 網絡 數據 存儲 查詢 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201510229346.3

申請日:

2015.05.07

公開號:

CN104899156A

公開日:

2015.09.09

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 12/06申請日:20150507|||公開
IPC分類號: G06F12/06 主分類號: G06F12/06
申請人: 中國科學院信息工程研究所; 國家計算機網絡與信息安全管理中心
發明人: 周薇; 包秀國; 馬宏遠; 程工; 冉攀峰; 劉春陽; 王卿; 韓冀中; 龐琳; 李雄; 賀敏; 劉瑋
地址: 100093北京市海淀區閔莊路甲89號
優先權:
專利代理機構: 北京君尚知識產權代理事務所(普通合伙)11200 代理人: 司立彬
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510229346.3

授權公告號:

||||||

法律狀態公告日:

2017.11.14|||2015.10.07|||2015.09.09

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種面向大規模社交網絡的圖數據存儲及查詢方法,本發明數據存儲管理器對收到的圖數據采用Key-Value方式存儲,以圖數據的頂點ID為Key,以頂點鄰域為Value;對每一頂點鄰域的數據存儲:將與該頂點鄰域相連的多條邊以時間戳有序存儲到固定大小的內存塊中,并構成雙向鏈表,將該頂點的屬性信息和索引信息存儲到一數據結構中。當數據存儲管理器收到訪問頂點v的訪問請求時,數據存儲管理器將該頂點v及其k階鄰域傳輸給請求者;請求者將返回數據緩存在本地,下次查詢時,首先檢查本地的緩存,如果不存在查詢的頂點,則將訪問請求發送給所述數據存儲管理器。本發明能滿足動態更新、適合處理數據稀疏的場景和隨機訪問。

權利要求書

權利要求書
1.  一種面向大規模社交網絡的圖數據存儲方法,其步驟為:
1)數據存儲管理器對收到的圖數據采用Key-Value方式存儲,其中以圖數據的頂點ID為Key,以頂點鄰域為Value;
2)對每一頂點鄰域的數據存儲:將與該頂點鄰域對應頂點相連的多條邊以時間戳有序存儲到固定大小的內存塊Block中,并使用鏈表結構將所占用的內存塊Block構成Block雙向鏈表,將該頂點的屬性信息和指向該Block雙向鏈表頭部和尾部的索引信息存儲到一數據結構Vertex中。

2.  如權利要求1所述的方法,其特征在于,所述內存塊Block由一負責存儲資源分配的Block池管理器進行分配與回收;所述Block雙向鏈表中的內存塊Block包括三部分:第一部分為指向Block雙向鏈表中當前內存塊Block的前一個內存塊Block的指針,第二部分為指向Block雙向鏈表中當前內存塊Block的后一個Block的指針,第三部分為當前內存塊Block存儲的邊。

3.  如權利要求2所述的方法,其特征在于,所述步驟2)中,當一頂點有新邊需要存儲到頂點鄰域時,將該新邊按時間戳排序,查看Block雙向鏈表頭部的Block是否未滿,如果未滿,則將該新邊追加在該Block的頭部;如果頭部的Block已滿,則由Block池管理器分配一新的內存塊Block并添加到該Block雙向鏈表的頭部,然后將該新邊存儲到該新內存塊Block中。

4.  如權利要求1或2或3所述的方法,其特征在于,每一所述內存塊Block中設有一數據域,用于保存所存邊的時間戳區間;當對頂點領域中的邊進行刪除時,從Block雙向鏈表尾部的內存塊Block開始選取一邊,如果該邊的時間戳小于尾部內存塊Block的時間戳區間下界,則結束刪除操作,如果該邊的時間戳大于該時間戳區間的上界,則從該Block雙向鏈表末尾移除該內存塊Block;如果該邊的時間戳位于該時間戳區間內,則掃描該內存塊Block中的邊,刪除比該邊的時間戳早的邊。

5.  如權利要求1所述的方法,其特征在于,所述數據存儲管理器將存儲資源分成兩類:粗粒度存儲資源和細粒度存儲資源,所述數據存儲管理器的內存中設置有界緩存窗口;其中所述粗粒度存儲資源用于存儲設定的大文件,并常駐于內存,所述細粒度存儲資源用于存儲按需分配的小文件;所述數據存儲管理器按需將細粒度存儲資源載入該有界緩存窗口,當該有界緩存窗口被占滿,需要加載新的細粒度存儲資源時,采用緩存替換算法將該有界緩存窗口中已有的細粒度存儲資源換出,然后載入新的細粒度存儲資源。

6.  如權利要求5所述的方法,其特征在于,所述粗粒度存儲資源和所述細粒度存儲資源均劃分成固定大小的所述內存塊Block,每一內存塊Block擁有唯一的Block ID。

7.  如權利要求5所述的方法,其特征在于,所述數據存儲管理器首先分配粗粒度存儲資源的內存塊Block,當粗粒度存儲資源耗盡時,開始按需地動態地分配細粒度存儲資源在內存塊Block。

8.  如權利要求5所述的方法,其特征在于,所述數據存儲器定期地掃描圖數據,將過期的圖數據從所述粗粒度存儲資源中刪除并轉存到所述細粒度存儲資源中。

9.  一種基于權利要求1所述方法存儲的圖數據的圖數據查詢方法,其特征在于,當數據存儲管理器收到訪問頂點v的訪問請求時,數據存儲管理器將該頂點v及其k階鄰域傳輸給請求者;請求者將返回數據緩存在本地,下次查詢時,首先檢查本地的緩存,如果不存在查詢的頂點,則將訪問請求發送給所述數據存儲管理器。

10.  如權利要求9所述的方法,其特征在于,所述頂點v的k階鄰域為從該頂點v出發經過最短距離k條邊可達的全部頂點構成的集合。

說明書

說明書一種面向大規模社交網絡的圖數據存儲及查詢方法
技術領域
本發明涉及一種面向大規模社交網絡的圖數據存儲及查詢方法,屬于軟件技術領域。
背景技術
目前,圖數據存儲的主流做法是將圖數據經過預處理,轉化為邊和頂點的記錄,以順序數據集的形式存儲在分布式文件系統的大文件中。訪問圖數據時,以順序掃描的方式訪問存儲圖數據的大文件。該組織方式無法為多輪迭代的圖計算應用提供有效的數據存儲和訪問性能,為了提高圖數據的訪問性能,圖數據的內存管理技術成為了一個重要的趨勢,如Trinity,Giraph等。
Neo4j是采用Key-Value存儲模型的圖數據庫,最基本的存儲單位是頂點和邊,當廣度遍歷BFS時,獲取某一頂點鄰域操作的性能明顯比以頂點鄰域作為基本存儲單位的系統要低。Neo4j所有的數據存儲在磁盤上,采用內存緩存加速數據訪問,可以調節內存緩存的大小,獲得最佳的性能。
Trinity是由微軟亞洲研究院設計的基于內存云的圖計算引擎。采用基于內存的Key-Value存儲,其中key是圖頂點的唯一ID,用以定位尋址cell,cell是包含該頂點鄰域內的相鄰頂點信息的任意長度的連續內存字節塊。圖數據的每個頂點對應一個cell,cell存儲在trunk中,trunk是大小不超過2GB的連續內存。
Redis也采用Key-Value存儲,但是Redis只能處理集群內存可以容納下的圖數據。
Neo4j是采用Key-Value存儲模型的圖數據庫,然而當圖數據規模顯著大于內存緩存的大小時,其性能也隨著顯著降低;當訪問異地數據時,Neo4j采用按需請求的方式,無法充分利用帶寬。
Trinity是由微軟亞洲研究院設計的基于內存云的圖計算引擎。當數據頻繁更新時,插入和刪除等操作會使得cell變大或者縮小。當cell變大之后,現有的存儲區域無法容納,就需要開辟更大的存儲空間裝載cell,將cell從原來位置移動到新的位置;當cell縮小之后,原來的存儲cell的空間中縮小的部分空余出,會產生很多內存碎片。由此可見,cell的增大和縮小會形成大量的內存碎片,從而削弱內存的利用率。Trinity采用內存緊縮和預分配更大內存的方式解決外部碎片的問題。不過無論采用何種方法,數據在內存中的搬運移動是不可避免的,并且該操作是非常耗時的。因此,在圖數據頻繁更新的場景下,Trinity的性能表現不理想。在Trinity中,當內存無法容納全部圖數據時,部分trunk會位于磁盤上。當請求的cell不在 內存時,就需要將目標trunk全部換入內存,由于圖數據訪問具有隨機性,數據訪問的局部性很差,多個連續請求的cell有可能不在換入內存的trunk中,因此需要將新的trunk換入。在遠程數據訪問方面,Trinity采用按需請求的方式。
Redis也采用Key-Value存儲,當圖數據的數據量不斷增長,超過內存容量時,只能依賴增加機器節點數目方式。當集群規模增加時,需要重新劃分數據,并且做數據遷移。Redis的數據劃分交由客戶端完成,服務端程序無法代理異地圖數據的請求。
由以上研究工作可知,圖計算的數據訪問需求以及圖數據的自身特點對圖數據的存儲提出了挑戰,傳統的數據存儲方式比如文件系統或者分布式文件系統和Key-Value存儲模型的圖數據庫難以高效的支持圖數據訪問和更新,進而不能有效的支持圖計算。因此,需要根據圖數據的訪問特性以及圖數據本身的特點設計高效的圖數據存儲系統。
發明內容
本發明的目的在于針對社交網絡數據的海量性、頻繁更新、隨機訪問以及稀疏性等特點,提供一種面向大規模社交網絡的圖數據存儲及查詢方法。
本發明能夠滿足鄰域的隨機訪問。本發明設計了一種基于鄰域的三級圖數據存儲結構。以頂點鄰域為基本存儲單位,頂點鄰域是由固定大小內存block構成的雙向鏈表,該雙向鏈表中包含該頂點的所有關聯邊的信息,block可被直接尋址。
本發明采用零移動的數據更新機制。我們設計了一種適合圖數據頻繁更新的內存組織方法。圖數據更新時,由block池負責block的分配和回收。和回收引起頂點鄰域的縮小或者擴增時,我們只是修改雙鏈表的首尾,并且不必緊縮存儲空間消除外部碎片,也不必分配更大存儲空間,將數據從原來地方搬移到新分配的空間中。此機制不但提高了內存的使用率,而且也解決了其他解決方案所面臨的緊縮和移動操作。
本發明采用感知應用的遠程預取策略。圖數據的單次數據請求的數據訪問量少,引起頻繁的遠程IO操作。使用該策略,在當前的異地數據請求處理時,預測后續計算的所需數據,然后該預測數據與當前請求數據一同返回給客戶進程,緩存在其本地。通過該機制能夠顯著降低IO次數,提供數據訪問的可預測性和有效性。本發明分析總結常見的圖算法,根據每輪更新中需要參考圖中的哪些頂點,這些算法可以分為兩類,即鄰域算法和非鄰域算法。在鄰域算法中,每一輪迭代更新每個頂點屬性值時僅需訪問相鄰頂點的值。而在非鄰域算法中,更新每個頂點屬性值還需要訪問除鄰域外其它頂點的值。
本發明的技術方案為:
一種面向大規模社交網絡的圖數據存儲方法,其步驟為:
1)數據存儲管理器對收到的圖數據采用Key-Value方式存儲,其中以圖數據的頂點ID為Key,以頂點鄰域為Value;
2)對每一頂點鄰域的數據存儲:將與該頂點鄰域對應頂點相連的多條邊以時間戳有序存儲到固定大小的內存塊Block中,并使用鏈表結構將所占用的內存塊Block構成Block雙向鏈表,將該頂點的屬性信息和指向該Block雙向鏈表頭部和尾部的索引信息存儲到一數據結構Vertex中。
進一步的,所述內存塊Block由一負責存儲資源分配的Block池管理器進行分配與回收;所述Block雙向鏈表中的內存塊Block包括三部分:第一部分為指向Block雙向鏈表中當前內存塊Block的前一個內存塊Block的指針,第二部分為指向Block雙向鏈表中當前內存塊Block的后一個Block的指針,第三部分為當前內存塊Block存儲的邊。
進一步的,所述步驟2)中,當一頂點有新邊需要存儲到頂點鄰域時,將該新邊按時間戳排序,查看Block雙向鏈表頭部的Block是否未滿,如果未滿,則將該新邊追加在該Block的頭部;如果頭部的Block已滿,則由Block池管理器分配一新的內存塊Block并添加到該Block雙向鏈表的頭部,然后將該新邊存儲到該新內存塊Block中。
進一步的,每一所述內存塊Block中設有一數據域,用于保存所存邊的時間戳區間;當對頂點領域中的邊進行刪除時,從Block雙向鏈表尾部的內存塊Block開始選取一邊,如果該邊的時間戳小于尾部內存塊Block的時間戳區間下界,則結束刪除操作,如果該邊的時間戳大于該時間戳區間的上界,則從該Block雙向鏈表末尾移除該內存塊Block;如果該邊的時間戳位于該時間戳區間內,則掃描該內存塊Block中的邊,刪除比該邊的時間戳早的邊。
進一步的,所述數據存儲管理器將存儲資源分成兩類:粗粒度存儲資源和細粒度存儲資源,所述數據存儲管理器的內存中設置有界緩存窗口;其中所述粗粒度存儲資源用于存儲設定的大文件,并常駐于內存,所述細粒度存儲資源用于存儲按需分配的小文件;所述數據存儲管理器按需將細粒度存儲資源載入該有界緩存窗口,當該有界緩存窗口被占滿,需要加載新的細粒度存儲資源時,采用緩存替換算法將該有界緩存窗口中已有的細粒度存儲資源換出,然后載入新的細粒度存儲資源。
進一步的,所述粗粒度存儲資源和所述細粒度存儲資源均劃分成固定大小的所述內存塊Block,每一內存塊Block擁有唯一的Block ID。
進一步的,所述數據存儲管理器首先分配粗粒度存儲資源的內存塊Block,當粗粒度存儲資源耗盡時,開始按需地動態地分配細粒度存儲資源在內存塊Block。
如權利要求5所述的方法,其特征在于,所述數據存儲器定期地掃描圖數據,將過期的圖數據從所述粗粒度存儲資源中刪除并轉存到所述細粒度存儲資源中。
一種圖數據查詢方法,其特征在于,當數據存儲管理器收到訪問頂點v的訪問請求時,數據存儲管理器將該頂點v及其k階鄰域傳輸給請求者;請求者將返回數據緩存在本地,下次查詢時,首先檢查本地的緩存,如果不存在查詢的頂點,則將訪問請求發送給所述數據存儲管理器。
進一步的,所述頂點v的k階鄰域為從該頂點v出發經過最短距離k條邊可達的全部頂點構成的集合。
與現有技術相比,本發明的積極效果為:
(1)能滿足動態更新。社交網絡用戶頻繁產生數據,在實際應用中,數據分析對數據的時效性具有很高的要求,用戶的行為產生的新數據需要不斷的加入。
(2)適合處理數據稀疏的場景。在社交網絡中,用戶的好友數目的差別很多,少數用戶(如大V),擁有很多好友,而眾多普通用戶的好友數目稀少,從統計角度看,社交網絡數據是平均出度很小的極度稀疏圖。
(3)適合隨機訪問。在訪問圖數據的過程中,不同于訪問順序數據集,一般先訪問某個頂點,然后訪問相鄰頂點,再次訪問相鄰頂點的相鄰頂點,如此不斷地從一個頂點出發,由近及遠,最后完成對整個圖的遍歷。
附圖說明
圖1本發明方法中的數據存儲管理;
圖2為頂點鄰域的存儲模型;
圖3為本地寫實驗結果對比圖;
圖4為本地讀實驗結果對比圖;
圖5為實際數據和存儲資源消耗對比圖;
圖6為遠程寫的實驗結果對比圖;
圖7為遠程讀的實驗結果對比圖;
圖8為數據更新的實驗結果對比圖;
圖9遠程預取和非預取的性能對比圖。
具體實施方式
以下結合附圖對本發明的原理和特征進行描述,所舉實例只用于解釋本發明,并非用于限定本發明的范圍。
本發明可以分為三部分:零移動的數據組織策略、自適應數據規模的存儲管理策略以及應用感知的異地預取策略。
零移動的數據組織策略
圖數據增量更新是指將產生的新邊插入圖中和從圖中刪除過時的舊邊。將社交媒體用戶的每時每刻的活動足跡產生新鮮圖數據需要予以存儲,而圖數據中不再具有使用價值的過時圖數據予以刪除。
本文采用Key-Value存儲,以頂點ID做Key,以頂點鄰域做Value。頂點鄰域的數據組織特點有:1)采用以時間戳將頂點相鄰的邊有序的存儲到Block雙向鏈表中,便于從鏈表的頭部插入新邊,從尾部刪除舊邊。2)為了降低邊在雙向鏈表的存儲代價,將與頂點相連的多條邊順序存儲在固定大小的內存塊Block中,存儲同一頂點的邊的block塊構成Block雙向鏈表。Block由專門負責存儲資源分配的Block池管理器負責分配回收。3)頂點鄰域由數據結構Vertex和Block鏈表構成,其中Vertex是用戶自定義的C語言的結構,其中包含了頂點的屬性信息和指向Block雙向鏈表頭部和尾部的索引信息。
當向頂點鄰域插入新邊時,將新邊按時間戳排序,先查看鏈表頭部的Block是否未滿,如果沒有滿,就追加在該Block的頭部;如果頭部的Block已滿,且依然有待插入的新邊,則由Block池管理器分配新的Block,添加到鏈表的頭部,用待插入邊填充新Block。重復該過程,直至更新完全部的新邊。當刪除頂點鄰域中的老化邊時,從Block雙鏈表尾部的Block開始,為了快速的刪除舊邊,Block中有專門的數據域保存所存邊的時間戳區間。如果想要刪除的邊的時間戳小于時間戳區間的下界,則結束刪除操作;當待刪邊的時間戳大于時間戳區間的上界,則從鏈表末尾移除該Block,通過Block管理池回收已刪除的Block;如果當待刪除邊的時間戳出現在時間戳區間中,則掃描該Block中的邊,刪除比待刪除邊的時間戳老的邊,并結束操作。
采用Block雙向鏈表存儲以時間戳有序的出邊的方式組織頂點鄰域,有諸多優點。第一,避免采用單條邊存儲的小額內存空間的頻繁動態分配和存儲過多額外的元數據。因為圖數據的更新比較頻繁,而每條邊的數據量比較少,更新操作引起小額內存的頻繁動態分配;并且邊中的元數據相對于實際數據的比率也加大,導致內存內存的分配效率和利用率降低,而且單挑邊的存儲也不利于訪問頂點鄰域。第二,避免了采取頂點的全部出邊整體存儲的方式不利于圖數據動態更新的問題,采用整體的存儲,頂點的全部出邊存儲blob(動態分配的長度不固定的連續內存空間),新邊插入操作會導致原存儲空間耗盡,必須開辟足夠大的新存儲空間,挪動原來的數據,并插入新邊。舊邊刪除到操作會導致存儲空間空余數量可觀的不可用的內部碎片。通常采用定期緊縮操作,數據移動重新整理圖數據,以消除碎片。這種組織方 式雖然訪問頂點鄰域具有很高的性能,但是緊縮操作會顯著影響圖數據的隨機增量跟新的效率。
在本系統中,充分考慮了圖數據的特征以及對圖數據的訪問特性,設計了一種圖數據的頂點鄰域存儲模型,如圖2所示。每個Block由三部分組成,第一部分為指向前一個block的指針,第二部分為指向后一個block的指針,第三部分為該block存儲的邊。此模型可以有效地支持圖數據更新。
本文提出的圖數據存儲方法在數據更新方面與業界使用的方式有如下幾點不同:
首先,Redis和Neo4j的數據存儲采用連續分配的方式,但隨著數據不斷地更新,超出已分配存儲塊時,需要分配更大的連續內存塊,然后將原來的數據挪動到新塊中,并將新數據插入。頻繁的數據更新,會造成數據的頻繁挪動。盡管Redis采用了一種預先分配機制,每次分配的內存多于實際需要的內存數目,以應對未來可能的數據擴增。但沒有從根本上解決內存數據挪動的問題。而本發明采用鏈接分配的方式,通過block管理池管理空閑內存塊,已分配的內存塊鏈接成雙向鏈表,數據的更新發生在鏈表末尾,不用引起數據的挪動和復制。
其次,在Redis和Neo4j中,圖數據的頂點和邊分別存儲,而本文提出的方法直接存儲圖的頂點鄰域。存儲相同規模的圖數據,Redis和Neo4j需要啟動更多數目的網絡I/O。Redis和Neo4j啟動I/O的次數為圖頂點數目和邊數目之和,而本發明啟動I/O的次數為圖頂點數目,而在社交媒體圖結構中,圖的邊數目是遠遠大于圖頂點數目。即便可以采用批量數據傳輸,由于Redis和Neo4j數據訪問采用類似SQL的查詢語言,需要將寫入的數據在客戶端轉換為批量查詢語句,并且在服務器端經過解析執行,轉換和解析影響了效率。而本發明本身采用頂點及其鄰域作為數據組織單位,在遠程訪問過程中,客戶端采用buffer緩存待寫入目標機器的數據,當緩沖區滿,或者超時事件發生,才將buffer中的數據批量地發送給目標機器。
最后,Neo4j每次數據更新,都是事務操作,服務期需要將數據寫入同步到磁盤文件中。而Redis采用RDB的機制,通過后臺I/O線程將內存中某一時間斷面的數據寫入到磁盤文件中,每次寫入過程會阻塞其他更新。而本發明在更新時,采用mmap接口,在內存區域和磁盤文件之間建立映射,數據寫入到內存區域,由操作系統內核負責將數據更新同步到磁盤文件中。
綜合以上不同點,本發明在做數據更新的過程中在設計上有多個優勢,可以達到更高的更新性能。
自適應數據規模的存儲管理策略
圖計算的數據訪問具有很高的隨機性,采用內存組織數據能夠提高數據隨機訪問效率。然后,圖數據的數據規模具有海量性,集群的有限內存無法負載大規模圖數據。本文提出了 自適應數據規模的內存管理策略,優先使用內存組織圖數據,當內存資源耗盡時,容許數據溢出到磁盤中。具體的做法是:將圖數據管理系統的可以使用的存儲資源分成兩類,一類是粗粒度存儲資源,另一類是細粒度存儲資源。
粗粒度資源對應本地Linux文件系統的預先分配的大文件,文件大小為2GB、4GB甚至更大,前提是不超過集群單個節點可用內存容量。運行時,粗粒度資源被全部加載,并常駐于內存。細粒度資源對于本地Linux文件系統的按需分配的小文件,文件大小為4MB、8MB,而且小文件的數目隨著圖數據的增加不斷變大。運行時,無法將粗粒度資源和全體細粒度資源全部置于內存,因此在內存中開辟有界緩存窗口,按需將細粒度資源載入窗口。當窗口被占滿,需要加載新的細粒度資源時,需要根據緩存替換算法,選擇窗口中已有的細粒度資源,將其換出,然后載入新的資源。
兩類資源都被劃分成固定大小的Block,全體Block擁有唯一的Block ID,可以根據BlockID隨機地訪問Block。Block是存儲資源的基本分配單位,由Block池管理器負責分配和回收Block。當頂點鄰域的Block雙向鏈表頭部未滿時,需要為新插入邊分配新的Block作為鏈表的頭部;當刪除頂點鄰域的舊邊時,需要釋放和回事空的Block。所有的Block要么處于空閑狀態,要么屬于某個指定的頂點鄰域。
資源分配時,可以根據數據的規模動態地選擇存儲資源。首先從粗粒度資源開始分配,目的是盡量采用內存組織數據。當粗粒度資源耗盡時,開始按需地動態地分配細粒度資源,存儲溢出內存的數據。頂點鄰域中的邊以時間戳有序存儲,可以定期地掃描圖數據,將過期的圖數據從粗粒度資源中刪除,轉存到細粒度資源中,從而是內存中的數據保持新鮮。
采用自適應數據規模的存儲分配策略,既可以盡力使用內存組織數據,從而提高數據訪問的隨機性,又允許圖數據規模增大時,將數據從內存溢出到磁盤中,解決了海量圖數據的管理問題。
應用感知的異地預取策略
在本發明中,為了加快異地數據訪問的效率,提出了一種感知應用特征的異地預取的機制。通過該機制,更夠顯著地提高異地數據訪問的吞吐率。
圖數據的訪問,類似于訪問順序存儲的數據,具有明顯的局部性。圖計算的算法一般基于圖的遍歷算法。以廣度優先遍歷為例,訪問頂點v時,v的k階鄰域(從頂點v出經過最短距離k條邊可達的全部頂點構成的集合)的頂點被訪問概率隨著k增大而降低,因此,處理v的訪問請求時,系統根據頂點位置信息可以預測近期最有可能被訪問的頂點,將頂點v和近期最有可能被訪問的頂點的數據合并在一起,傳輸給請求者。請求者將預先取得的數據緩存在本地,下次獲取異地數據時,先檢查本地的緩存,如果存在,直接訪問本地即可,否 則向異地請求數據。
很多圖計算框架會順序地讀取圖數據的子圖的全部頂點,此時,可以采用順序預取的方式。預取方式的選擇要符合圖計算的數據訪問特點,可以提供多種預取的策略,讓用戶選擇從中選擇最佳的預取策略。
實例1數據訪問實例
本發明測試了本發明以及比較系Redis和Neo4j在不同并發量下的寫性能,該寫性能取了十個數據集下的平均值,其中在測試圖3中,本發明使用NYNN表示。
由圖3可知,本發明本地寫性能明顯優于Redis和Neo4j,元數據的設計和數據傳輸格式和數據寫入的機制影響了寫的性能。首先本發明圖數據的劃分采用連續的等寬頂點區間,能夠通過首次數據寫入請求,將元數據緩存在本地,此后使用緩存在本地的元數據進行數據尋址,這樣減少了尋址的IO開銷。寫入數據的時候,自己寫入本地的內存映射文件中。Redis和Neo4j都提供了方便使用的查詢命令/語言,先將用戶寫入數據的請求,封裝成查詢命令,然后通過本地網絡發送給server,由server負責解析命令,完成查詢。
本發明測試了本發明以及比較系Redis和Neo4j在不同并發量下的讀性能,該讀性能取了十個數據集下的平均值。
如圖4所示,本地讀操作,本發明可以達到GB/s量級,而Redis和Neo4j是10MB/s~100MB/s,本發明可以直接將圖數據通過mmap接口映射到客戶進程的地址空間中,進行操作。而Redis和Neo4j采用查詢命令向server請求數據。
為了反應圖數據存儲系統的存儲效率,本發明比較了多個系統的存儲膨脹比,即存儲同樣多的數據,看內存和磁盤的占用膨脹比。
如圖5所示,對比Redis,Neo4j和本發明的磁盤使用情況,可以明顯的觀察到,Neo4j作為基于磁盤的存儲系統,占用磁盤空間最大,數據存儲的時候,需要存儲屬性值和屬性名,而且屬性值采用字符串的形式存儲。Redis所需的磁盤存儲空間最少,Redis的數據持久化之前,將數據進行壓縮。而內存的使用中,Redis的內存使用最大,因為Redis將全部數據加載到內存。Neo4j和本發明都可以配置所需內存的大小。
本發明測試了本發明以及比較系Redis和Neo4j在不同并發量下的遠程寫性能,該寫性能取了十個數據集下的平均值。
如圖6所示,遠程寫數據,本發明的性能明顯高于Neo4j和Redis。本發明的數據交換采用報文的形式傳輸字節流。而Redis和Neo4j采用查詢命令或語言,降低了數據的傳輸效率。此外本發明的后臺數據寫入采用多線程處理,提高的效率。Redis采用事件驅動模型的單線出處理。
本發明測試了本發明以及比較系Redis和Neo4j在不同并發量下的遠程讀性能,該讀性能取了十個數據集下的平均值。
如圖7所示,遠程讀操作,本發明采用了數據預取機制,能夠批量傳輸有效數據。而Redis和Neo4j都沒有采用預取機制。
實例2數據更新實例
本文測試了本發明以及比較系Redis和Neo4j的數據更新性能,該性能取了十個數據集下的平均值。
如圖8所示,對于數據的增量更新,本發明采用了鏈式的分配方式,能夠消除數據插入和刪除引起的數據頻繁挪動問題。而Redis和Neo4j采用了順序分配的方式,隨著數據的更新,需要挪動數據,重定位數據,在這個過程中,無法進行新的查詢處理。
實例3數據遠程訪問實例
本文測試了本發明在有預取機制和非預取的情況下的性能差異。本發明提供多種數據預取機制,便于上層應用更加自己的應用背景選擇最佳的數據預取方式。本實驗采用BFS預取,實驗用到的算法是統計圖數據集中圖的總邊數,算法的思路為:將圖的頂點劃分為n個分片,每個分片指定一個線程處理,所有線程并行訪問本發明中的圖數據。線程將訪問請求中要訪問的頂點放入隊列,然后處理隊列頭部的頂點,訪問頂點的鄰域,統計頂點邊數。如果當前邊的終點位于線程所屬分片,則將該終點放入隊列。不斷的循環處理隊列的首部,直到隊列為空。但所有的線程完成頂點的統計,將結果累計,算法結束。該算法為BFS遍歷算法,能夠很好的利用BFS預取機制,預取數據在后續的訪問中,具有很高的命中率。
如圖9所示,本發明提供了多種數據預取機制,比如順序預取,BFS預取和DFS預取。上層的計算框架可以選擇最佳的預取方式批量的從異地獲取圖數據,圖數據訪問過程中,每次讀取數據量比較少,雖然相鄰時間的數據讀取是可以預測的。通過將大批小量數據的訪問積攢成大塊數據,可以充分利用帶寬資源,降低IO啟動時間,這樣我們可以通過較低的并發獲得較高的數據吞吐率。

關于本文
本文標題:一種面向大規模社交網絡的圖數據存儲及查詢方法.pdf
鏈接地址:http://www.wwszu.club/p-6369762.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大