分布式圖形實(shí)驗(yàn)：機(jī)器學(xué)習(xí)框架以及云技術(shù)中的數(shù)據(jù)挖掘

分布式圖形實(shí)驗(yàn)：機(jī)器學(xué)習(xí)框架以及云技術(shù)中的數(shù)據(jù)挖掘摘要：像MapReduce這類高級數(shù)據(jù)并行處理框架在對大規(guī)模數(shù)據(jù)處理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)進(jìn)行簡化的同時，并不能天然地或者高效的支持許多重要的數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)算法，在此基礎(chǔ)上構(gòu)建的機(jī)器學(xué)習(xí)系統(tǒng)往往是低效的。為填補(bǔ)這一空白，我們引入Graphlab，它實(shí)現(xiàn)了異步、動態(tài)的并行圖計(jì)算模式，同時保證數(shù)據(jù)一致性，且在共享內(nèi)存基礎(chǔ)上具有很好的計(jì)算并行度。在本論文中，我們從Graphlab框架本身拓展到更具實(shí)際意義、更有挑戰(zhàn)性的具有健壯數(shù)據(jù)一致性的分布式計(jì)算。我們在圖計(jì)算基礎(chǔ)上擴(kuò)展開發(fā)了流水線鎖定和數(shù)據(jù)版本技術(shù)來減少網(wǎng)絡(luò)擁塞和降低網(wǎng)絡(luò)傳輸開銷。同時，我們介紹了使用經(jīng)典Chandy-Lamport快照算法實(shí)現(xiàn)的容錯機(jī)制，并論證了可以在Graphlab框架基礎(chǔ)上方便的實(shí)現(xiàn)。最后，我們評價了我們的分布式實(shí)現(xiàn)方案在亞馬遜虛擬計(jì)算平臺上的性能，并展示了相對于Hadoop的實(shí)現(xiàn)方案，亞馬遜虛擬機(jī)群部署Graphlab系統(tǒng)會有1到2個數(shù)量級的性能提升。1.介紹伴隨著機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)的規(guī)模增長、復(fù)雜度提升，急需一個能夠在大規(guī)模集群上快速并行執(zhí)行數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)任務(wù)的系統(tǒng)。同時，像亞馬遜彈性計(jì)算云這樣的云集算服務(wù)提供了在不具備實(shí)體集群情況下進(jìn)行大規(guī)模節(jié)點(diǎn)計(jì)算的可能。不幸的是，設(shè)計(jì)、實(shí)現(xiàn)并且調(diào)試分布式機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法需要能夠?qū)υ萍悍浅Ｊ炀毜氖褂茫@些對機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘?qū)＜覀儤?gòu)成極其艱巨的挑戰(zhàn)，因?yàn)檫@需要他們在實(shí)現(xiàn)復(fù)雜數(shù)據(jù)算法模型的同時能夠處理并行競爭條件、死鎖、分布式狀態(tài)和通信協(xié)議等難題。盡管如此，對大規(guī)模計(jì)算和數(shù)據(jù)存儲的需求，已經(jīng)驅(qū)使很多人就某些獨(dú)立的算法模型，開發(fā)出新的并行分布式機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘系統(tǒng)（如引文2，14，15，30，35）。由于不同的研究團(tuán)體重復(fù)性地解決相同的并行或者分布式計(jì)算問題，這些消耗時間和重復(fù)勞動的努力僅僅緩慢推動了這個領(lǐng)域的發(fā)展。因此，研究機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的群體及組織需要一個高水平的面向很多機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘應(yīng)用中都會遇到的異步、動態(tài)、圖并行計(jì)算模式的，并且隱藏并行和分布式系統(tǒng)復(fù)雜設(shè)計(jì)邏輯的分布式系統(tǒng)模型。不幸的是，已經(jīng)存在的高水平并行計(jì)算模式例如mapreduce，Dryad和Pregel都不能很好的支持滿足這些苛刻的特制要求。為了幫助填補(bǔ)這一空白，我們介紹Graphlab計(jì)算模式，它在共享內(nèi)存環(huán)境下，直接面向異步、動態(tài)和圖并行計(jì)算。在這篇文論中，我們將多核的Graphlab概念拓展到分布式環(huán)境下，并對分布式執(zhí)行模型進(jìn)行樂形式化的描述。我們在保證嚴(yán)格的一致性要求的基礎(chǔ)上，探索出多種分布式執(zhí)行模型的實(shí)現(xiàn)方式。為了實(shí)現(xiàn)這個目標(biāo)，融入數(shù)據(jù)版本控制技術(shù)來間情網(wǎng)絡(luò)擁堵，引入流水線分布式鎖機(jī)制來降低網(wǎng)絡(luò)傳輸開銷。為了處理數(shù)據(jù)局部性和入口帶來的挑戰(zhàn)，我們引入原子圖機(jī)制，以實(shí)現(xiàn)在分布式環(huán)境下的快速構(gòu)建圖數(shù)據(jù)結(jié)構(gòu)。我們還通過經(jīng)典的Chandy-Lamport快照算法為Graphlab框架增加容錯機(jī)制，并證明了此機(jī)制在Graphlab概念中可以很容易被實(shí)現(xiàn)。我們對我們在亞馬遜彈性計(jì)算服務(wù)基礎(chǔ)上使用C++優(yōu)化實(shí)現(xiàn)的Graphlab系統(tǒng)進(jìn)行樂綜合性能分析。我們展示出在Graphlab框架上開發(fā)的應(yīng)用程序性能相當(dāng)于在Hadoop/mapreduce框架同等實(shí)現(xiàn)下的20-60倍，且能和使用MPI精心設(shè)計(jì)的實(shí)現(xiàn)相匹敵。我們的主要貢獻(xiàn)如下：一個機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法共性綜述以及現(xiàn)有大數(shù)據(jù)框架的局限性。一個修改過的可以部署在分布式環(huán)境下的Graphlab概念版本和執(zhí)行模型。兩種可實(shí)現(xiàn)的新的分布式執(zhí)行模型實(shí)施方案。彩色引擎：使用圖著色算法實(shí)現(xiàn)靜態(tài)調(diào)度的高效、漸進(jìn)、一致的執(zhí)行。加鎖引擎：采用分布式流水線鎖機(jī)制和延遲消除方法實(shí)現(xiàn)對動態(tài)、優(yōu)先執(zhí)行的支持。通過兩個快照方案實(shí)現(xiàn)容錯。在分布式Graphlab框架下實(shí)現(xiàn)三種高水準(zhǔn)的機(jī)器學(xué)習(xí)算法。對部署在擁有64個節(jié)點(diǎn)512個CPU的亞馬遜彈性計(jì)算服務(wù)集群上的Graphlab系統(tǒng)進(jìn)行大量評測，并和Hadoop、Pregel和MPI進(jìn)行對比。2.MLDM的算法性能：在論文的這一部分，我們將詳細(xì)敘述Graphlab概念下的大規(guī)模分布式機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘系統(tǒng)所獨(dú)有的關(guān)鍵特性，并解釋其他的分布式框架為何不具備這些特性。這些特性和分布式框架列在表格1中。圖結(jié)構(gòu)計(jì)算：很多機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘方面的研究進(jìn)展將焦點(diǎn)聚集在對數(shù)據(jù)相關(guān)性的建模上。通過對數(shù)據(jù)相關(guān)性進(jìn)行建模，我們能夠從包含噪音的數(shù)據(jù)中抽取出更多有價值的信息。例如，與僅僅孤立的處理購物者數(shù)據(jù)相比，對相似購物者的相關(guān)性建模能夠做出更好的推薦。不幸的是，類似于Mapreduce的分布式數(shù)據(jù)處理模型并不能通用性的適應(yīng)相關(guān)性計(jì)算需求，而這又是很多更高級機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法所需要的。盡管，很多時候可以將相關(guān)性計(jì)算映射到Mapreduce計(jì)算模式中，但是結(jié)果的轉(zhuǎn)換較難實(shí)現(xiàn)，且很可能引入較難解決的效率問題。因此，我們最近逐漸推出了類似于Pregel的天然支持?jǐn)?shù)據(jù)相關(guān)性計(jì)算的Graphlab。這些計(jì)算模式采用頂點(diǎn)為中心的計(jì)算模型，計(jì)算被作為核心在每個頂點(diǎn)上執(zhí)行。例如，Pregel是一個大規(guī)模同步通信的框架，頂點(diǎn)間通過消息進(jìn)行通信。另一方面，Graphlab則建立在有序共享內(nèi)存基礎(chǔ)上，每個頂點(diǎn)均可以讀寫相鄰頂點(diǎn)的數(shù)據(jù)。Graphlab穩(wěn)定的并行執(zhí)行為效率提供保障。開發(fā)者在使用Graphalb時可以不用管新并行數(shù)據(jù)的轉(zhuǎn)移，而將主要注意力放在算法各部分的執(zhí)行順序上，由此，Graphlab會讓圖并行算法在設(shè)計(jì)和實(shí)現(xiàn)上更為簡單。異步迭代計(jì)算：很多重要的機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法需要迭代更新大量的參數(shù)。由于底層采用圖數(shù)據(jù)結(jié)構(gòu)，頂點(diǎn)或者邊上的參數(shù)更新依賴于相鄰頂點(diǎn)或者邊上的參數(shù)。同步型系統(tǒng)在更新參數(shù)時會使用上一迭代步驟得到的參數(shù)值作為輸入，同時將參數(shù)更新到集群中的各個節(jié)點(diǎn)上，而同樣情形下，異步型系統(tǒng)可以使用最新的參數(shù)作為輸入更新參數(shù)值。因此，異步系統(tǒng)給很多算法帶來客觀的性能收益。例如，很多線性系統(tǒng)（很多機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法都是線性系統(tǒng)）已經(jīng)被論證如果能夠解決異步問題，性能將會有很大的提升。除此之外，還有很多例子（如置信傳播、最大期望化、隨即優(yōu)化等）經(jīng)驗(yàn)上都是異步執(zhí)行大大優(yōu)于同步執(zhí)行。如圖1，我們論證樂為什么Pagerank在異步計(jì)算模式下可以加速收斂。同步計(jì)算帶來高昂的性能損失，這是因?yàn)槊恳粋€步驟的執(zhí)行時間都是由運(yùn)行最慢的機(jī)器決定的。最慢機(jī)器的苦逼表現(xiàn)可能由很多因素導(dǎo)致，包括負(fù)載和網(wǎng)絡(luò)的不穩(wěn)定，硬件變化，一機(jī)多用（云主機(jī)中首要因素）。如果使用同步機(jī)算，這些還有其他服務(wù)不穩(wěn)定的運(yùn)行將導(dǎo)致非常嚴(yán)重的性能問題。另外，就算圖譜結(jié)構(gòu)可以被均勻的分割到各個節(jié)點(diǎn)，運(yùn)行時，多個節(jié)點(diǎn)聚合會產(chǎn)生出額外的不確定性。例如，在實(shí)際應(yīng)用中，理論上的圖譜會受到密律分布的特征影響，運(yùn)行時間曲線產(chǎn)生很大的傾斜，甚至圖譜被隨機(jī)切分。此外，每個節(jié)點(diǎn)真實(shí)的運(yùn)作會以問題的特定方式對數(shù)據(jù)進(jìn)行依賴。因?yàn)镸apReduce和Dryad這些大規(guī)模數(shù)據(jù)處理框架在設(shè)計(jì)時并不支持迭代計(jì)算，近期出現(xiàn)的Mapreduce擴(kuò)展版本-Spark和其他大數(shù)據(jù)并行處理框架開始支持迭代計(jì)算。然而，這些框架并不支持分布式異步計(jì)算。大規(guī)模同步型分布式計(jì)算框架（BSP）如Pregel、Picolo和BPGL都不天然的支持異步計(jì)算模式。另外一方面，基于共享內(nèi)存的Graphlab被設(shè)計(jì)成為一種天然支持異步迭代算法的高性能框架。動態(tài)計(jì)算：很多機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法迭代計(jì)算的收斂性是不平衡的。例如，在參數(shù)最優(yōu)化的計(jì)算中，很多參數(shù)會在少量的迭代后收斂，同時剩下的參數(shù)會在后面較多的迭代步驟后慢慢收斂。在圖一(b)中我們繪制了PageRank算法達(dá)到收斂前的需要的更新次數(shù)曲線。很讓人驚訝，大量的頂點(diǎn)僅需要一次迭代便收斂了，同時僅有百分之三的頂點(diǎn)需要超過十次的迭代才能收斂。引文39中的張演示優(yōu)先計(jì)算可以對包含PageRank在內(nèi)的圖算法進(jìn)行進(jìn)一步深入的收斂優(yōu)化。如果我們總是平均的更新所有的參數(shù)，那么會讓很多已經(jīng)收斂了的參數(shù)上重復(fù)計(jì)算以致浪費(fèi)大量時間。相反的，如果我們能夠盡早的將計(jì)算聚集在那些較難收斂的參數(shù)上，那么我們很可能能夠加速它們的收斂。在圖一(c)種我們以經(jīng)驗(yàn)論證了如何通過動態(tài)調(diào)度加快Loopy置信度傳播算法（一種很常見的機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法）的收斂速度。一些近期推出的概念已經(jīng)包含了動態(tài)計(jì)算的形式。例如，Pregel通過允許在每個計(jì)算步驟中跳過一些計(jì)算來允許一定限制的動態(tài)計(jì)算。其他的如Pearce和Graphlab則允許用戶可以適應(yīng)性的按照優(yōu)先級進(jìn)行計(jì)算。雖然Pregel和Graphlab都支持動態(tài)計(jì)算，但只有Graphlab允許帶優(yōu)先級的計(jì)算形式，同時具備動態(tài)地從鄰接頂點(diǎn)獲取全部信息的能力（3.2節(jié)將詳細(xì)敘述）。在這篇文章中，我們放松一些引文24中描述的Graphlab最初的調(diào)度需求，以使分布式的FIFO隊(duì)列和優(yōu)先調(diào)度更有效率。可串行化：因?yàn)槲覀冎浪械牟⑿谢瘓?zhí)行都可以等化為串行執(zhí)行，串行化能夠消除很多同設(shè)計(jì)、實(shí)現(xiàn)和具體使用的并行算法（機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘）相關(guān)聯(lián)的難題。此外，很多算法在并行化被允許的情況下可以得到加速收斂，甚至很多算法只有串行化才能保證正確性。例如，當(dāng)允許并行競爭的時候，動態(tài)ALS算法（5.1節(jié)）是不穩(wěn)定的。吉布斯采樣，一個非常流行的機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法，要求串行化才能保證統(tǒng)計(jì)上正確性。圖表1：大規(guī)模計(jì)算框架對比圖表。(a)引文38描述的Mapreduce的迭代擴(kuò)展。(b)引文18提出的Dryad的迭代擴(kuò)展。(c)Piccolo不提供保證一致性的機(jī)制，但是提出了一個允許用戶同步寫的彌補(bǔ)機(jī)制。圖1：(a)在16個處理器上構(gòu)建了一個兩千五百萬個頂點(diǎn)和叁億伍仟伍佰萬條邊的Web圖后進(jìn)行Pagerank算法實(shí)驗(yàn)產(chǎn)出的收斂比例圖，縱軸為未收斂頂點(diǎn)數(shù)，采用指數(shù)刻度，橫軸為所用時間。(b)分布式動態(tài)PageRank算法頂點(diǎn)更新的總次數(shù)。值得注意的是，多數(shù)頂點(diǎn)在一次迭代后就收斂了。(c)Loopy置信度傳播算法在網(wǎng)頁反作弊探測上的收斂比例。(d)在Netflix電影推薦問題上應(yīng)用動態(tài)ALS算法，對比串行和非串行（有競爭的）執(zhí)行。非串行執(zhí)行表現(xiàn)出不穩(wěn)定的收斂現(xiàn)象。一個強(qiáng)制串行化計(jì)算的框架能夠消除很多一致性引入的復(fù)雜度，這樣能夠讓機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘?qū)＜野迅嗟淖⒁饬Ψ旁谒惴ê湍Ｐ偷脑O(shè)計(jì)上。因?yàn)閿?shù)據(jù)競爭會帶來臟數(shù)據(jù)，在并行運(yùn)行的程序中調(diào)試數(shù)學(xué)計(jì)算代碼是一件非常困難的事情。很吃驚，很多異步框架例如Piccolo僅提供最初級的彌補(bǔ)數(shù)據(jù)競爭的機(jī)制。Graphlab支持寬范圍的一致性環(huán)境，允許程序選擇能夠保證算法正確性的一致性級別。在第四部分，我們將介紹我們研發(fā)出的分布式環(huán)境下強(qiáng)制串行化的技術(shù)。3.DIST.GRAPHLABABSTRACTIONGraphlab框架主要由三部分組成：數(shù)據(jù)圖，更新函數(shù)和同步操作。（3.1節(jié)）圖狀數(shù)據(jù)表述用戶可修改的程序狀態(tài)，而且存儲了易變的用戶定義數(shù)據(jù)和經(jīng)過編碼的系數(shù)的相關(guān)性計(jì)算數(shù)據(jù)。（3.2節(jié)）更新函數(shù)表示用戶計(jì)算和通過在被稱作作用于的小范圍重疊上下文中數(shù)據(jù)傳輸進(jìn)行的數(shù)據(jù)圖操作。（3.5節(jié)）最后，同步操作將同時創(chuàng)建全局聚合。為了在具體問題中使用Graphlab框架，我們將使用PageRank作為執(zhí)行示例。示例1，PageRank。PageRank算法遞歸定義了一個網(wǎng)頁的排名值v，如下公式：wu,v表示頁面u鏈接到v的權(quán)重，R(u)代表頁面u的Rank值，α表示從頁面u跳轉(zhuǎn)到v的概率。PageRank算法迭代計(jì)算直到Rank值的變化小雨某個很小的閾值。Graphlab框架存儲程序狀態(tài)為一個有向數(shù)據(jù)圖。數(shù)據(jù)圖G(V,E,D)是一個管理用戶定義數(shù)據(jù)D的容器。這里我們說的數(shù)據(jù)是指模型參數(shù)、算法狀態(tài)和統(tǒng)計(jì)數(shù)據(jù)。用戶可以將特定的數(shù)據(jù)同圖中的每個頂點(diǎn)v和邊e(u到v)關(guān)聯(lián)起來。然而，由于Graphlab框架不依賴邊的方向，所以我們使用u?v表示u和v之間存在雙向邊。最后，圖狀數(shù)據(jù)是易變的。但同時圖的結(jié)構(gòu)是靜態(tài)的，不會隨著程序執(zhí)行而改變。示例2.數(shù)據(jù)圖來自互聯(lián)網(wǎng)頁圖譜，每個頂點(diǎn)代表一個Web頁面，每條邊表示一個超鏈接。頂點(diǎn)數(shù)據(jù)Dv存儲R(v)，當(dāng)前對PageRank值的估計(jì)，邊

Du→v

存儲著wu,v

，即有向鏈接的權(quán)重。在Graphlab框架中，將計(jì)算以更新函數(shù)的形式進(jìn)行編碼。一個更新函數(shù)是一個無狀態(tài)的程序，這個程序可以在一個頂點(diǎn)的范圍內(nèi)進(jìn)行數(shù)據(jù)修改，也可以對其他頂點(diǎn)將要執(zhí)行的更新函數(shù)進(jìn)行調(diào)度。所謂v的作用域，指的是v中存儲的數(shù)據(jù)和存儲在所有鄰接節(jié)點(diǎn)和鄰接邊中的數(shù)據(jù)，如圖2(a)。Graphlab框架更新函數(shù)以頂點(diǎn)v和它的作用域Sv作為輸入，返回?cái)?shù)據(jù)Sv的一個新的版本和頂點(diǎn)集合T。更新函數(shù)被執(zhí)行完成后，被修改后的數(shù)據(jù)Sv會被更新到數(shù)據(jù)圖中。被更新后的頂點(diǎn)u∈T會按照將在3.3節(jié)中詳細(xì)描述的執(zhí)行語義，被申請執(zhí)行更新函數(shù)f(u,Su)。相比較引文25和19中采用的消息傳遞和數(shù)據(jù)流模型，Graphlab允許用戶定義更新函數(shù)在鄰接頂點(diǎn)和邊上自由的完成數(shù)據(jù)的讀取和修改。簡單用戶只需要編碼，而不需要了解數(shù)據(jù)流動的方法。通過控制哪些頂點(diǎn)可以被返回加入到集合T并被執(zhí)行，Graphlab更新函數(shù)能夠高效的實(shí)現(xiàn)適應(yīng)性計(jì)算。例如，一個更新函數(shù)可能只會在本身數(shù)據(jù)發(fā)生實(shí)質(zhì)變化的時候才會返回它的鄰接節(jié)點(diǎn)。在動態(tài)計(jì)算的表現(xiàn)形式上，Pregel和Graphlab有著重要的不同。Graphlab將計(jì)算的調(diào)度和數(shù)據(jù)的移動分離開。因而，Graphlab更新函數(shù)可以訪問鄰接節(jié)點(diǎn)的數(shù)據(jù)，哪怕鄰接節(jié)點(diǎn)沒有調(diào)度執(zhí)行這次更新。相反的，Pregel更新函數(shù)是消息初始化的，因此只能在消息中訪問數(shù)據(jù)，表現(xiàn)能力受到限制。例如,因?yàn)橛?jì)算給定頁面的PageRank值時需要所有的鄰接頁面，盡管一些鄰接頁面PR值沒有發(fā)生變化，所以動態(tài)PageRank在Pregel很難被表示。因此，在Pregel中，向想臨頂點(diǎn)發(fā)送數(shù)據(jù)的決定只能由接收頂點(diǎn)發(fā)起，而不能由發(fā)送頂點(diǎn)發(fā)起。然而，在Graphlab中，由于鄰接頂點(diǎn)只負(fù)責(zé)調(diào)度，更新函數(shù)可以直接讀取鄰接頂點(diǎn)的數(shù)據(jù)，哪怕他們沒有變化，所以可以很自然的表示拉取數(shù)據(jù)模型。示例三。PageRank的更新函數(shù)計(jì)算相鄰頂點(diǎn)排名值總和并提交作為當(dāng)前頂點(diǎn)的排名值。這個算法是具有適應(yīng)性的，只有當(dāng)前頂點(diǎn)更新超過設(shè)定閾值時，鄰居頂點(diǎn)才會被調(diào)度更新。Graphlab執(zhí)行模型，如算法2中展示，遵循一個簡單的單循環(huán)語義。Graphlab框架的輸入包括如數(shù)據(jù)圖G=(V,E,D)，一個更新函數(shù)，一個被執(zhí)行的初始化了的頂點(diǎn)集合T。當(dāng)T中海油頂點(diǎn)時，算法刪除并執(zhí)行一個頂點(diǎn)，并添加新的頂點(diǎn)到集合T。重復(fù)的頂點(diǎn)被忽略。最終在結(jié)算結(jié)束的時候，結(jié)果數(shù)據(jù)圖和全局變量被返回給用戶。為了讓分布式執(zhí)行更加高效，我們放松了對共享內(nèi)存Graphlab框架中執(zhí)行順序的要求，且允許Graphlab在運(yùn)行時決定最好的頂點(diǎn)執(zhí)行順序。例如，RemoveNext(T)可能選擇返回能夠使網(wǎng)絡(luò)通信開銷最小的頂點(diǎn)。Graphlab框架僅僅需要集合T中的所有頂點(diǎn)最終都能被執(zhí)行，因?yàn)楹芏鄼C(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法能夠通過優(yōu)先級運(yùn)行進(jìn)行優(yōu)化，Graphlab框架允許用戶設(shè)計(jì)頂點(diǎn)集合T中頂點(diǎn)的優(yōu)先級順序。Graphlab運(yùn)行時可能使用這些頂點(diǎn)優(yōu)先級結(jié)合系統(tǒng)的目標(biāo)優(yōu)化頂點(diǎn)執(zhí)行順序。通過允許多個處理器可以在同一個數(shù)據(jù)圖中執(zhí)行循環(huán)，同時刪除或者執(zhí)行不同的頂點(diǎn)，Graphlab框架是一個可以自動轉(zhuǎn)換并行運(yùn)行的豐富的串行模型。為了保證串行計(jì)算語義，我么必須保證重疊計(jì)算不同時運(yùn)行。我們引入若干一致性模型，他們允許保證串行性的同時對并行運(yùn)行進(jìn)行優(yōu)化。Graphlab運(yùn)行的時候需要確保串行執(zhí)行。串行執(zhí)行隱含著，當(dāng)按照算法2進(jìn)行運(yùn)行時，必須相應(yīng)的對更新函數(shù)進(jìn)行串行調(diào)度，以在數(shù)據(jù)圖中生成相同的數(shù)值。通過保證可串行性，Graphalb在分布式計(jì)算環(huán)境中簡化了高度并行動態(tài)計(jì)算。一個成功串行化的簡單方法是確保同時執(zhí)行的更新函數(shù)作用域不重疊。在引文24中，我們稱它為完全的一致性模型，參見圖2(b)。然而，完整的一致性限制了并行度的潛能，因?yàn)橥瑫r執(zhí)行更新函數(shù)必須是在兩個分離的頂點(diǎn)上（見圖2（c））。然而，對于很多機(jī)器學(xué)習(xí)算法，更新函數(shù)不需要完全的對作用域內(nèi)所有數(shù)據(jù)的讀寫訪問。例如，PageRank更新公式1只需要讀取邊和相鄰頂點(diǎn)。為了在保證串行性的同時提升并行度，Graphlab定義了邊一致性模型。邊一致性模型保證每次更新函數(shù)值近單獨(dú)的讀寫訪問自己的頂點(diǎn)和相鄰邊，而只讀性訪問鄰接頂點(diǎn)，如圖2(b)。因此，邊一致性模型通過允許更新函數(shù)在松覆蓋的作用域內(nèi)安全并行運(yùn)行來提升并行度。見圖2（c）。最后，頂點(diǎn)一致性模型允許所有的更新函數(shù)可以并行的運(yùn)行，提供最大程度的并行度。在很多機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法中，在數(shù)據(jù)圖中維護(hù)描述全局統(tǒng)計(jì)信息的數(shù)據(jù)是必需的。例如，很多統(tǒng)計(jì)推理算法需要追蹤全局收斂預(yù)測器。為了滿足這個需求，Graphlab框架定義了能夠被更新函數(shù)讀取但是需要同步操作寫入的全局變量。同Pregel中的聚合想死，同步操作是一個定義在圖中所有作用域上的相關(guān)的可交換求和。不同于Pregel，同步操作引入了一個終結(jié)步驟。中介步驟用于支持類似于歸一化的任務(wù)，這種任務(wù)在機(jī)器學(xué)習(xí)-數(shù)據(jù)挖掘算法中很常用。同樣形成對比，Pregel在每個超級步后執(zhí)行聚合操作，Graphlab同步操作持續(xù)在后臺運(yùn)行維持對全局變量的估計(jì)。圖2：(a)數(shù)據(jù)圖和S1作用域。灰色的圓柱體表示用戶定義的頂點(diǎn)和邊數(shù)據(jù)，同時不規(guī)則的區(qū)域是包含頂點(diǎn){1,2,3,4}的頂點(diǎn)1的作用域S1。對頂點(diǎn)1申請執(zhí)行的更新函數(shù)能夠讀取和修改作用域S1內(nèi)的所有數(shù)據(jù)（頂點(diǎn)數(shù)據(jù)D1,D2,D3,D4，邊數(shù)據(jù)D1?2,D1?3,andD1?4）。(b)各種一致性模型下，在頂點(diǎn)3執(zhí)行的更新函數(shù)的讀寫權(quán)限。在完全一致性模型下，更新函數(shù)對整個作用域有完整的讀寫權(quán)限。在邊一致性模型下，更新函數(shù)對鄰接邊數(shù)據(jù)僅有讀取權(quán)限。最后，頂點(diǎn)一致性模型只對中心頂點(diǎn)數(shù)據(jù)有寫權(quán)限。(c)一致性和并行度之間的交換折中。黑色舉行表示不能被重疊的寫鎖區(qū)域。更新函數(shù)可以在黑色頂點(diǎn)上并行執(zhí)行。在更強(qiáng)的一致性模型下，僅有很少的函數(shù)可以同