利用大數據技術進行圖處理
處理非常大型的圖對象一直都是個挑戰，但最近大數據技術的進步卻讓這一工作變得更具實踐性。作為紐約市的一家專注于跨設備內容分發的創業公司，Tapad利用大數據技術處理TB級的數據，并已將圖處理作為其商業模型的核心業務。
像非死book和推ter這樣的社交網絡，其數據天生就適合于圖表示法。而對這方面屬性不太明顯的數據，我們也可以用圖對象來表示，比如Tapad的設備圖。Tapad的聯合創始人兼CTO，Dag Liodden，解釋了為什么對設備使用圖表示法很有意義：
“Tapad采用面向圖的方式對設備間的關系進行建模。在設備圖中，我們把匿名標示符（如cookie ID）表示為節點并且追蹤這些節點的市場信息。節點間的邊則結合使用測定數據、概率統計模型以及機器學習技術計分或加權重。我們將‘設備’的概念定義為一 個起始設備或節點（比如說某個瀏覽器的cookie ID）和由該起點出發的、在一組可定制邊約束下能達到的節點集合（比如說一個Tablet和一個Connected TV的cookie ID）。相對于單個節點僅有的聚合信息，實際的圖結構使我們能夠在動態平衡數據準確度和規模方面更具靈活性，而且還能更容易地運用新的邊推理模型來對圖進 行擴充。”
</blockquote>用合適的工具完成合適的工作很重要，這個道理同樣適用于圖處理：對于通過傳統工作負載就能處理的圖對象，我們就沒必要使用大數據技術。正如Dag所說：
“‘大數據’對我而言就像個門檻，跨過之后你就不能再使用少數通用的、現成的工具來存儲和分析數據了，而是要依據具體的用例對不同的技術加以取舍。隨著軟硬件解決方案的進步和成熟，這些閾值每年都在變動，而我們所處理的數據集的大小以及所進行的分析的復雜程度亦是如此。”
</blockquote>對非死book來說，這個閾值達到了幾PB級，詳情可參閱他們在2013紐約ACM SIGMOD大會上的報告。對Tapad而言，圖對象的數據量雖然較小，但依然不可能用傳統的方法來處理：
“全美的圖對象當前有大約11億個節點，它們代表著移動電話、平板、筆記本、游戲終端以及電視機。其中有些節點是臨時的，比如因為瀏覽器使用非持久 的cookie，導致節點缺少數據而沒有邊緣。非臨時節點平均有大概5個邊緣和約500個離散的信息片段與其相關聯，如行為分段。實時圖數據量達到了幾 TB級，而且我們還要跨多個數據中心每秒對其進行幾十萬次的讀取、寫入操作。圖對象的更新實現了跨地域相互復制，每個數據中心由配備了20TB Flash SSD存儲和2TB RAM的服務器來支撐。”
</blockquote>近幾年涌現出很多處理大型圖對象的技術，尤其是2013年，我們看到了幾個新成員加入到該生態系統中。有兩類系統值得考慮：
- 針對OLTP工作負載，能夠快速低延遲訪問小部分圖數據的圖數據庫。
- 針對OLAP工作負載，能夠對圖對象中的大部分數據進行批處理的圖處理引擎。
</ul>知名的圖數據庫已經很多了，但最近仍冒出了幾個標新立異的項目。Neo4j算是最老牌、最成熟的圖數據庫之一，但因不支持分片而依然存在可伸縮性的問題。另一個相當年輕，卻在2013年非常流行的數據庫便是Titan。作為后端無關的圖數據庫，它支持HBase和Cassandra的可伸縮架構，并且如2013年的一篇博文所報道的，它在內部使用了一套優化的頂點和邊表示法以使其能處理幾十億個邊對象。
但你不必非要使用圖特定數據庫，更通用的可伸縮的NoSQL數據庫也是有效的解決方案。基于Google BigTable并在2011年開源的Apache Accumulo就是一個通用數據庫的例子，它的數據記錄很靈活，所以也適合存儲大型圖對象，同時還可以用來存儲含有類型化的邊和權重的圖對象，2013年發布的一份技術報告表明NSA也在使用它。Cassandra或者Aerospike則是另一種數據庫，它們能通過適當的數據模型，用邊、頂點和權重給圖對象高效地建模。非死book也構建了自己的解決方案，他們在被稱為Tao的系統中使用了MySQL和Memcache組合，并正在使用這一方案為其用戶提供社區圖服務。據Dag所說，Tapad在其設備圖的設計過程中也運用了同樣的哲學：
“將實時的圖對象保存在鍵值對存儲中可以支持快速的遍歷和更新。我們就是把圖的快照周期性地存進HDFS，然后從中提取它們進行高級圖處理并用其他 數據流來擴充，之后再把結果回填至‘實時圖’。雖然使用圖特定的數據庫會有一些優勢，但以我們目前的設置，既可以在鍵值對存儲中極快且簡單地遍歷圖對象， 還可在Hadoop上慢速但非常靈活地進行遍歷和分析操作，對我們來說它工作的很好，至少現在如此。”
</blockquote>和存儲于數據庫中的圖對象一樣 ，可大規模進行的操作也只是局限于查找和小范圍的遍歷。至于在圖對象中進行更加復雜的分析，就需要分布式的批處理框架。為了達到最佳性能，GraphLab框架使用了Message Passing Interaface(MPI)模型來調整并運行基于HDFS數據的復雜算法。而新近的框架如Apache Giraph和Apache Hama則基于Bulk Synchronous Paralle(BSP)范式，該范式是由Google的Pregel項目推廣開的。而生態系統中最新的項目便是GraphX和Faunus。GraphX項目運行于2013年才問世的Spark之上，而Faunnus則通過用Hadoop運行MapReduce作業的方式來處理Titan數據庫中圖對象。Tapad正在運用這些新技術處理其離線圖數據。按照Dag所說：
“目前，我們主要的圖處理框架雖是Apache Giraph，但我們也在嘗試Saprk GraphX和GraphLab。所有這些架構還都很年輕，學習曲線也頗為陡峭，而且全都有自己的優缺點及注意事項。舉個例子，Giraph和 GraphX由于能很好地支持我們的Hadoop架構所以很方便，但GraphLab卻完全是因為其性能而更吸引我們。”
</blockquote>有些項目正試圖提供統一的架構以支持OLTP和OLAP查詢。來自Lab41的Dendrite就是這樣一個項目，它利用基于Titan的GraphLab進行存儲、處理，并用AngularJS實現可視化。因為這個非常年輕的項目在2014年年初才公開，所以社群反響有限，但是它試著顧及到所有用例，這應該有助于它的普及。
參考英文原文：Graph Processing Using Big Data Technologies
來自：http://www.infoq.com/cn/news/2014/04/graph-bigdata-tapad本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！