處理非常大型的圖對(duì)象一直都是個(gè)挑戰(zhàn)，但最近大數(shù)據(jù)技術(shù)的進(jìn)步卻讓這一工作變得更具實(shí)踐性。作為紐約市的一家專注于跨設(shè)備內(nèi)容分發(fā)的創(chuàng)業(yè)公司，Tapad利用大數(shù)據(jù)技術(shù)處理TB級(jí)的數(shù)據(jù)，并已將圖處理作為其商業(yè)模型的核心業(yè)務(wù)。

　　像Facebook和Twitter這樣的社交網(wǎng)絡(luò)，其數(shù)據(jù)天生就適合于圖表示法。而對(duì)這方面屬性不太明顯的數(shù)據(jù)，我們也可以用圖對(duì)象來(lái)表示，比如Tapad的設(shè)備圖。Tapad的聯(lián)合創(chuàng)始人兼CTO，Dag Liodden，解釋了為什么對(duì)設(shè)備使用圖表示法很有意義：

　　“Tapad采用面向圖的方式對(duì)設(shè)備間的關(guān)系進(jìn)行建模。在設(shè)備圖中，我們把匿名標(biāo)示符(如cookie ID)表示為節(jié)點(diǎn)并且追蹤這些節(jié)點(diǎn)的市場(chǎng)信息。節(jié)點(diǎn)間的邊則結(jié)合使用測(cè)定數(shù)據(jù)、概率統(tǒng)計(jì)模型以及機(jī)器學(xué)習(xí)技術(shù)計(jì)分或加權(quán)重。我們將‘設(shè)備’的概念定義為一個(gè)起始設(shè)備或節(jié)點(diǎn)(比如說(shuō)某個(gè)瀏覽器的cookie ID)和由該起點(diǎn)出發(fā)的、在一組可定制邊約束下能達(dá)到的節(jié)點(diǎn)集合(比如說(shuō)一個(gè)Tablet和一個(gè)Connected TV的cookie ID)。相對(duì)于單個(gè)節(jié)點(diǎn)僅有的聚合信息，實(shí)際的圖結(jié)構(gòu)使我們能夠在動(dòng)態(tài)平衡數(shù)據(jù)準(zhǔn)確度和規(guī)模方面更具靈活性，而且還能更容易地運(yùn)用新的邊推理模型來(lái)對(duì)圖進(jìn)行擴(kuò)充。”

　　用合適的工具完成合適的工作很重要，這個(gè)道理同樣適用于圖處理：對(duì)于通過(guò)傳統(tǒng)工作負(fù)載就能處理的圖對(duì)象，我們就沒(méi)必要使用大數(shù)據(jù)技術(shù)。正如Dag所說(shuō)：

　　“‘大數(shù)據(jù)’對(duì)我而言就像個(gè)門(mén)檻，跨過(guò)之后你就不能再使用少數(shù)通用的、現(xiàn)成的工具來(lái)存儲(chǔ)和分析數(shù)據(jù)了，而是要依據(jù)具體的用例對(duì)不同的技術(shù)加以取舍。隨著軟硬件解決方案的進(jìn)步和成熟，這些閾值每年都在變動(dòng)，而我們所處理的數(shù)據(jù)集的大小以及所進(jìn)行的分析的復(fù)雜程度亦是如此。”

　　對(duì)Facebook來(lái)說(shuō)，這個(gè)閾值達(dá)到了幾PB級(jí)，詳情可參閱他們?cè)?013紐約ACM SIGMOD大會(huì)上的報(bào)告。對(duì)Tapad而言，圖對(duì)象的數(shù)據(jù)量雖然較小，但依然不可能用傳統(tǒng)的方法來(lái)處理：

　　“全美的圖對(duì)象當(dāng)前有大約11億個(gè)節(jié)點(diǎn)，它們代表著移動(dòng)電話、平板、筆記本、游戲終端以及電視機(jī)。其中有些節(jié)點(diǎn)是臨時(shí)的，比如因?yàn)闉g覽器使用非持久的cookie，導(dǎo)致節(jié)點(diǎn)缺少數(shù)據(jù)而沒(méi)有邊緣。非臨時(shí)節(jié)點(diǎn)平均有大概5個(gè)邊緣和約500個(gè)離散的信息片段與其相關(guān)聯(lián)，如行為分段。實(shí)時(shí)圖數(shù)據(jù)量達(dá)到了幾 TB級(jí)，而且我們還要跨多個(gè)數(shù)據(jù)中心每秒對(duì)其進(jìn)行幾十萬(wàn)次的讀取、寫(xiě)入操作。圖對(duì)象的更新實(shí)現(xiàn)了跨地域相互復(fù)制，每個(gè)數(shù)據(jù)中心由配備了20TB Flash SSD存儲(chǔ)和2TB RAM的服務(wù)器來(lái)支撐。”

　　近幾年涌現(xiàn)出很多處理大型圖對(duì)象的技術(shù)，尤其是2013年，我們看到了幾個(gè)新成員加入到該生態(tài)系統(tǒng)中。有兩類系統(tǒng)值得考慮：

　　針對(duì)OLTP工作負(fù)載，能夠快速低延遲訪問(wèn)小部分圖數(shù)據(jù)的圖數(shù)據(jù)庫(kù)。

　　針對(duì)OLAP工作負(fù)載，能夠?qū)D對(duì)象中的大部分?jǐn)?shù)據(jù)進(jìn)行批處理的圖處理引擎。

　　知名的圖數(shù)據(jù)庫(kù)已經(jīng)很多了，但最近仍冒出了幾個(gè)標(biāo)新立異的項(xiàng)目。Neo4j算是最老牌、最成熟的圖數(shù)據(jù)庫(kù)之一，但因不支持分片而依然存在可伸縮性的問(wèn)題。另一個(gè)相當(dāng)年輕，卻在2013年非常流行的數(shù)據(jù)庫(kù)便是Titan。作為后端無(wú)關(guān)的圖數(shù)據(jù)庫(kù)，它支持HBase和Cassandra的可伸縮架構(gòu)，并且如2013年的一篇博文所報(bào)道的，它在內(nèi)部使用了一套優(yōu)化的頂點(diǎn)和邊表示法以使其能處理幾十億個(gè)邊對(duì)象。

　　但你不必非要使用圖特定數(shù)據(jù)庫(kù)，更通用的可伸縮的NoSQL數(shù)據(jù)庫(kù)也是有效的解決方案。基于Google BigTable并在2011年開(kāi)源的Apache Accumulo就是一個(gè)通用數(shù)據(jù)庫(kù)的例子，它的數(shù)據(jù)記錄很靈活，所以也適合存儲(chǔ)大型圖對(duì)象，同時(shí)還可以用來(lái)存儲(chǔ)含有類型化的邊和權(quán)重的圖對(duì)象，2013年發(fā)布的一份技術(shù)報(bào)告表明NSA也在使用它。Cassandra或者Aerospike則是另一種數(shù)據(jù)庫(kù)，它們能通過(guò)適當(dāng)?shù)臄?shù)據(jù)模型，用邊、頂點(diǎn)和權(quán)重給圖對(duì)象高效地建模。Facebook也構(gòu)建了自己的解決方案，他們?cè)诒环Q為T(mén)ao的系統(tǒng)中使用了MySQL和Memcache組合，并正在使用這一方案為其用戶提供社區(qū)圖服務(wù)。據(jù)Dag所說(shuō)，Tapad在其設(shè)備圖的設(shè)計(jì)過(guò)程中也運(yùn)用了同樣的哲學(xué)：

　　“將實(shí)時(shí)的圖對(duì)象保存在鍵值對(duì)存儲(chǔ)中可以支持快速的遍歷和更新。我們就是把圖的快照周期性地存進(jìn)HDFS，然后從中提取它們進(jìn)行高級(jí)圖處理并用其他數(shù)據(jù)流來(lái)擴(kuò)充，之后再把結(jié)果回填至‘實(shí)時(shí)圖’。雖然使用圖特定的數(shù)據(jù)庫(kù)會(huì)有一些優(yōu)勢(shì)，但以我們目前的設(shè)置，既可以在鍵值對(duì)存儲(chǔ)中極快且簡(jiǎn)單地遍歷圖對(duì)象，還可在Hadoop上慢速但非常靈活地進(jìn)行遍歷和分析操作，對(duì)我們來(lái)說(shuō)它工作的很好，至少現(xiàn)在如此。”

　　和存儲(chǔ)于數(shù)據(jù)庫(kù)中的圖對(duì)象一樣 ，可大規(guī)模進(jìn)行的操作也只是局限于查找和小范圍的遍歷。至于在圖對(duì)象中進(jìn)行更加復(fù)雜的分析，就需要分布式的批處理框架。為了達(dá)到最佳性能，GraphLab框架使用了Message Passing Interaface(MPI)模型來(lái)調(diào)整并運(yùn)行基于HDFS數(shù)據(jù)的復(fù)雜算法。而新近的框架如Apache Giraph和Apache Hama則基于Bulk Synchronous Paralle(BSP)范式，該范式是由Google的Pregel項(xiàng)目推廣開(kāi)的。而生態(tài)系統(tǒng)中最新的項(xiàng)目便是GraphX和Faunus。GraphX項(xiàng)目運(yùn)行于2013年才問(wèn)世的Spark之上，而Faunnus則通過(guò)用Hadoop運(yùn)行MapReduce作業(yè)的方式來(lái)處理Titan數(shù)據(jù)庫(kù)中圖對(duì)象。Tapad正在運(yùn)用這些新技術(shù)處理其離線圖數(shù)據(jù)。按照Dag所說(shuō)：

　　“目前，我們主要的圖處理框架雖是Apache Giraph，但我們也在嘗試Saprk GraphX和GraphLab。所有這些架構(gòu)還都很年輕，學(xué)習(xí)曲線也頗為陡峭，而且全都有自己的優(yōu)缺點(diǎn)及注意事項(xiàng)。舉個(gè)例子，Giraph和 GraphX由于能很好地支持我們的Hadoop架構(gòu)所以很方便，但GraphLab卻完全是因?yàn)槠湫阅芏覀儭！?/P>

　　有些項(xiàng)目正試圖提供統(tǒng)一的架構(gòu)以支持OLTP和OLAP查詢。來(lái)自Lab41的Dendrite就是這樣一個(gè)項(xiàng)目，它利用基于Titan的GraphLab進(jìn)行存儲(chǔ)、處理，并用AngularJS實(shí)現(xiàn)可視化。因?yàn)檫@個(gè)非常年輕的項(xiàng)目在2014年年初才公開(kāi)，所以社群反響有限，但是它試著顧及到所有用例，這應(yīng)該有助于它的普及。