【正文】 cebook公司Tao圖形數(shù)據(jù)庫是基于mysql來進(jìn)行開發(fā)。根據(jù)報(bào)道美國NSA就是利用2011年開源的Apache Accumulo(屬于分布式KV數(shù)據(jù)庫)來存儲(chǔ)社會(huì)關(guān)系網(wǎng)絡(luò)數(shù)據(jù)。(2) 圖數(shù)據(jù)查詢圖數(shù)據(jù)查詢其實(shí)就是”遍歷”圖(Traverse)。圖數(shù)據(jù)庫查詢語言可以使用Gremlin、Cypher等查詢語言來查詢圖。例如Neo4j就支持Cypher查詢語言。Cyper查詢語言需要以一個(gè)節(jié)點(diǎn)來啟動(dòng)(START)查詢，然后使用MATCH關(guān)鍵詞以WHERE關(guān)鍵字過濾節(jié)點(diǎn)或者關(guān)系的屬性，最后以RETRUN關(guān)鍵詞來指定查詢所返回的數(shù)據(jù)是節(jié)點(diǎn)、關(guān)系還是節(jié)點(diǎn)或者關(guān)系的屬性字段。例如：START barbara = node:nodeindex(name=”Barbara”)。MATCH(barbara)—(connected_node)RETURNconnected_node.(3) 兩類圖數(shù)據(jù)庫區(qū)別第一類與第二類圖數(shù)據(jù)庫區(qū)別在于以下幾點(diǎn)：查詢功能方面第一類圖數(shù)據(jù)庫可以以非常高效率方式支持復(fù)雜查詢，既支持從指定起點(diǎn)開始，以任意深度來遍歷圖，并且還可以支持各種過濾。這樣就可以很方便的執(zhí)行各種圖專用查詢?nèi)蝿?wù)，例如“查找兩個(gè)節(jié)點(diǎn)間所有路徑或者最短路徑”等。相反第二類數(shù)據(jù)庫則只能支持較為簡(jiǎn)單查詢，如FlockDB就只支持深度為1的關(guān)系遍歷(個(gè)人認(rèn)為也可以實(shí)現(xiàn)，只是效率不高)?？蓴U(kuò)展性方面大部分第一種圖形數(shù)據(jù)庫都不支持分布，個(gè)人認(rèn)為可能分布后這種復(fù)雜查詢難以做到高效，因此可擴(kuò)展性不好。而第二種由于只支持簡(jiǎn)單的圖便歷，一般通過采取按“邊”切分的方法來進(jìn)行分布存儲(chǔ)，因此可擴(kuò)展性較好。２) 圖數(shù)據(jù)OLAP處理對(duì)圖數(shù)據(jù)進(jìn)行復(fù)雜分析，就需要分布式的批處理框架。例如大規(guī)模的PageRank計(jì)算。在這個(gè)領(lǐng)域出現(xiàn)并行圖計(jì)算框架常見有Apache Giraph、Apache Hama、GraphLab、Pregel、GraphX等。Pregel是Google根據(jù)BSP并行計(jì)算模型開發(fā)的圖計(jì)算引擎，目前該系統(tǒng)沒有開源。GraphX是Spark項(xiàng)目組基于Spark框架開發(fā)的圖計(jì)算引擎；而GraphLab則是直接在MPI框架基礎(chǔ)上開發(fā)的專用圖計(jì)算引擎。下面簡(jiǎn)單介紹幾種主流并行圖計(jì)算引擎。３　并行圖計(jì)算引擎1) 基于BSP模型的Pregel引擎簡(jiǎn)介Pregel是Google公司開發(fā)的并行圖計(jì)算引擎，主要用于實(shí)現(xiàn)各種機(jī)器學(xué)習(xí)算法。Pregel的輸入是一個(gè)有向圖，該有向圖每一個(gè)頂點(diǎn)都有一個(gè)相應(yīng)由String描述的頂點(diǎn)標(biāo)識(shí)符。每一個(gè)頂點(diǎn)都有一個(gè)與之對(duì)應(yīng)可修改用戶自定義值。每一條有向邊都和其源頂點(diǎn)關(guān)聯(lián)，并且也擁有一個(gè)可修改的用戶自定義值，并同時(shí)還記錄了其目標(biāo)頂點(diǎn)的標(biāo)識(shí)符。Pregel可以采用多種文件格式進(jìn)行圖的保存，比如可以用text文件、關(guān)系數(shù)據(jù)庫、Bigtable。為了避免規(guī)定死一種特定文件格式，Pregel將從輸入中解析出圖結(jié)構(gòu)的任務(wù)從圖的計(jì)算過程中進(jìn)行了分離。計(jì)算結(jié)果可以以任何一種格式輸出并根據(jù)應(yīng)用程序選擇最適合的存儲(chǔ)方式。Pregel library本身提供了很多常用文件格式的readers和writers，但是用戶可以通過繼承Reader和Writer類來定義他們自己的讀寫方式。編寫一個(gè)Pregel程序需要繼承Pregel中已預(yù)定義好的一個(gè)基類——Vertex類。用戶覆寫Vertex類的虛函數(shù)Compute()，該函數(shù)會(huì)在每一個(gè)超級(jí)步中對(duì)每一個(gè)頂點(diǎn)進(jìn)行調(diào)用。預(yù)定義的Vertex類方法允許Compute()方法查詢當(dāng)前頂點(diǎn)及其邊的信息，以及發(fā)送消息到其他的頂點(diǎn)。Compute()方法可以通過調(diào)用GetValue()方法來得到當(dāng)前頂點(diǎn)的值，或者通過調(diào)用MutableValue()方法來修改當(dāng)前頂點(diǎn)的值。同時(shí)還可以通過由出邊的迭代器提供的方法來查看修改出邊對(duì)應(yīng)的值?；贐SP的執(zhí)行模型讀取輸入初始化該圖，當(dāng)圖被初始化好后，運(yùn)行一系列的超級(jí)步直到整個(gè)計(jì)算結(jié)束，這些超級(jí)步之間通過一些全局的同步點(diǎn)分隔，輸出結(jié)果結(jié)束計(jì)算。在每個(gè)超級(jí)步中，頂點(diǎn)的計(jì)算都是并行的，每個(gè)頂點(diǎn)執(zhí)行相同的用于表達(dá)給定算法邏輯的用戶自定義函數(shù)。每個(gè)頂點(diǎn)可以修改其自身及其出邊的狀態(tài)，接收前一個(gè)超級(jí)步(S1)中發(fā)送給它的消息，并發(fā)送消息給其他頂點(diǎn)(這些消息將會(huì)在下一個(gè)超級(jí)步中被接收)，甚至是修改整個(gè)圖的拓?fù)浣Y(jié)構(gòu)。邊，在這種計(jì)算模式中并不是核心對(duì)象，沒有相應(yīng)的計(jì)算運(yùn)行在其上。算法是否能夠結(jié)束取決于是否所有的頂點(diǎn)都已經(jīng)“vote”標(biāo)識(shí)其自身已經(jīng)達(dá)到“halt”狀態(tài)了。在第0個(gè)超級(jí)步，所有頂點(diǎn)都處于active狀態(tài)，所有的active頂點(diǎn)都會(huì)參與所有對(duì)應(yīng)superstep中的計(jì)算。頂點(diǎn)通過將其自身的status設(shè)置成“halt”來表示它已經(jīng)不再active。這就表示該頂點(diǎn)沒有進(jìn)一步的計(jì)算需要執(zhí)行，除非被再次被外部觸發(fā)，而Pregel框架將不會(huì)在接下來的superstep中執(zhí)行該頂點(diǎn)，除非該頂點(diǎn)收到其它頂點(diǎn)傳送的消息。如果頂點(diǎn)接收到消息被喚醒進(jìn)入active狀態(tài)，那么在隨后的計(jì)算中該頂點(diǎn)必須顯式的deactive。整個(gè)計(jì)算在所有頂點(diǎn)都達(dá)到“inactive”狀態(tài)，并且沒有message在傳送的時(shí)候宣告結(jié)束。2) graphLab(1) 簡(jiǎn)介GraphLab一套基于c++的開源圖計(jì)算庫，提供了在共享內(nèi)存情況下的異步、動(dòng)態(tài)和并行圖計(jì)算的高層抽象API。該庫采用MPI和TCPIP來實(shí)現(xiàn)進(jìn)程間通訊，采用Pthreads實(shí)現(xiàn)進(jìn)程內(nèi)的多線程并發(fā)計(jì)算，支持從HDFS和標(biāo)準(zhǔn)文件系統(tǒng)中讀取數(shù)據(jù)。GraphLab定義了多種用于存儲(chǔ)圖的文件格式，包括tsv,snap, adj bintsv4。(2) 與Pregel的不同GraphLab不是采用BSP的嚴(yán)格執(zhí)行模型，GraphLab的基于BSP的Pregel的典型的改進(jìn)是在更好的“異步迭代計(jì)算”和“動(dòng)態(tài)計(jì)算”。因此該框架計(jì)算效率比Pregel更好。異步計(jì)算：很多重要的MLDM算法迭代更新一大批參數(shù)，圖結(jié)構(gòu)導(dǎo)致參數(shù)更新依賴其它的參數(shù)。同步系統(tǒng)會(huì)以上一次更新的參數(shù)基礎(chǔ)上一次更新所有的參數(shù)（BSP模型中超級(jí)步之間市全局路障同步），而異步系統(tǒng)則以最近的參數(shù)作為輸入來更新參數(shù)。異步迭代更新可以極大加 快MLDM算法的計(jì)算速度。因?yàn)槿绻捎猛接?jì)算，則存在木桶效應(yīng)，整體速度取決于最慢的那臺(tái)機(jī)器。在大規(guī)模云計(jì)算環(huán)境下，負(fù)載不均衡、網(wǎng)絡(luò)不均衡、硬件差異和多租戶等會(huì)導(dǎo)致不同 機(jī)器之間的速度存在差異。另外由于圖分割不均衡，以及計(jì)算復(fù)雜性等導(dǎo)致各個(gè)節(jié)點(diǎn)計(jì)算量也不均衡。動(dòng)態(tài)計(jì)算：很多MLDM算法的迭代計(jì)算收斂都不對(duì)稱，例如在參數(shù)優(yōu)化是，通常很多參數(shù)在很少幾次迭代中就會(huì)快速收斂，而剩下少數(shù)參數(shù)則即使經(jīng)過多次迭代也會(huì)收斂很慢。因此如果我們等同更新所有的參數(shù)，則會(huì)浪費(fèi)大量的時(shí)間在重復(fù)計(jì)算那些已近收斂的參數(shù)上。最近的一些計(jì)算框架部分支持動(dòng)態(tài)計(jì)算，例如Pregel可以通過讓某些節(jié)點(diǎn)跳過一些超級(jí)步來部分支持動(dòng)態(tài)計(jì)算。(3) GraphLab的計(jì)算模型graphLab包括三個(gè)部分：數(shù)據(jù)圖、更新函數(shù)、同步操作。數(shù)據(jù)圖表達(dá)用戶可修改 的程序狀態(tài)，存儲(chǔ)可變的用戶自定義數(shù)據(jù)和計(jì)算之間依賴。更新函數(shù)通過一個(gè)scope的數(shù)據(jù)變換來表達(dá)用戶對(duì)數(shù)據(jù)圖的計(jì)算和操作。同步操作并發(fā)維護(hù)全局匯總。一個(gè)點(diǎn)的scope代表存儲(chǔ)在這個(gè)點(diǎn)上的數(shù)據(jù) 和所有與這個(gè)點(diǎn)相鄰的點(diǎn)和邊上的所有數(shù)據(jù)。update f (v ,s(v) ) (s(v) , 邊集合) 。經(jīng)過一個(gè)更新函數(shù)后，新計(jì)算出 的s(v) 會(huì)被寫回圖，并返回一個(gè)定點(diǎn)集合，針對(duì)該集合的每個(gè)點(diǎn)再執(zhí)行 f(u ,s(u))為了更高效的并行執(zhí)行，GraphLab容許GraphLab框架動(dòng)態(tài)的選擇執(zhí)行順序，即RemoveNext(T)的返回值。因?yàn)楹芏郙LDM算法需要執(zhí)行優(yōu)先級(jí)別，因此也可以指定點(diǎn)的優(yōu)先級(jí)，這樣GraphLab會(huì)綜合考慮優(yōu)先級(jí)以及網(wǎng)絡(luò)情況來調(diào)度。(3) GraphLab的并行計(jì)算根據(jù)領(lǐng)域知識(shí)，將圖分割為K份，K值遠(yuǎn)大于機(jī)器數(shù)量。每個(gè)分區(qū)被稱為atom, 以一個(gè)文件形式存儲(chǔ)類似HDFS的分布式文件系統(tǒng)上。Atom中存儲(chǔ)的是增加點(diǎn)和變的操作記錄，可以通過回放的方式來重構(gòu)圖。采取把點(diǎn)著色的方法，先保證每個(gè)點(diǎn)和相鄰點(diǎn)之間的顏色都不相同。通過一個(gè)顏色一個(gè)顏色的并發(fā)執(zhí)行，來實(shí)現(xiàn)邊一致性。把這種成為顏色步，與BSP的超步模型相對(duì)應(yīng)。該引擎保證在執(zhí)行下一個(gè)顏色步之前，所有的修改都被傳遞，實(shí)現(xiàn)顏色步之間的路障同步。 由Master根據(jù)atom索引來計(jì)算atom的位置，并負(fù)責(zé)機(jī)器與atom之間的分配關(guān)系。然后每個(gè)機(jī)器讀取atom文件來加載圖。每個(gè)機(jī)器上有一個(gè)調(diào)度器負(fù)責(zé)調(diào)度屬于自己的子圖的點(diǎn)的計(jì)算。調(diào)度器負(fù)責(zé)把每個(gè)需要執(zhí)行update 函數(shù)之前所需要的數(shù)據(jù)和鎖準(zhǔn)備好后，放入一個(gè)流水處理隊(duì)列中，再由一個(gè)worker線程池來執(zhí)行，通過一個(gè)分布式算法來確定所有機(jī)器上的調(diào)度器中的T為空，也就是整個(gè)計(jì)算結(jié)束。3)graphX基于SPARK圖形計(jì)算引擎，GraphX提供的API可以很方便的表達(dá)各種針對(duì)的轉(zhuǎn)換、過濾和查詢操作，但是GraphX不能直接實(shí)現(xiàn)迭代并行圖計(jì)算算法，但是可以基于這些API用來實(shí)現(xiàn)各種并行圖計(jì)算算法。在GraphX論文中描述了利用GraphX來實(shí)現(xiàn)Pregel、PowerGraph的方法。GraphX的優(yōu)勢(shì)是可以很方便的與shark等進(jìn)行集成，例如直接對(duì)shark查詢后的結(jié)果進(jìn)行圖計(jì)算。4) 總結(jié)(1)上述計(jì)算引擎都可以以靈活方式來存儲(chǔ)圖，基本上都可以以文件方式來存儲(chǔ)圖數(shù)據(jù)，實(shí)現(xiàn)計(jì)算引擎與存儲(chǔ)分離。(2)圖計(jì)算引擎都根據(jù)MDML算法特點(diǎn)采用專用計(jì)算模型，以提高效率。(3) 所有圖計(jì)算引擎在計(jì)算時(shí)，基本都是需要把數(shù)據(jù)都加載到內(nèi)存中。(來自preglel論文：當(dāng)前整個(gè)的計(jì)算狀態(tài)都是駐留在內(nèi)存中的。我們已經(jīng)開始將一些數(shù)據(jù)存到本地磁盤，同時(shí)我們會(huì)繼續(xù)在這個(gè)方向進(jìn)行深入的研究，希望可以支持規(guī)模太大以至于內(nèi)存無法完全存下的情況。THANKS !!!致力為企業(yè)和個(gè)人提供合同協(xié)議，策劃案計(jì)劃書，學(xué)習(xí)課件等等打造全網(wǎng)一站式需求歡迎您的下載，資料僅供參考可修改編輯