分布式圖形實驗：機器學習框架以及云技術中的數(shù)據(jù)挖掘

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

Du→v

存儲著wu,v

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