圖是實體組之間聯(lián)系的有用理論表示，并已用于數(shù)據(jù)科學中的各種目的，從按受歡迎程度對網(wǎng)頁進行排名和繪制社交網(wǎng)絡(luò)，到輔助導航。在許多情況下，此類應用程序需要處理包含數(shù)千億條邊的圖，這對于在單個消費級機器上處理來說太大了?？s放圖算法的典型方法是在分布式系統(tǒng)中運行設(shè)置，即在多臺計算機之間劃分數(shù)據(jù)（和算法）以并行執(zhí)行計算。

雖然這種方法允許人們處理具有數(shù)萬億條邊的圖，但它也帶來了新的挑戰(zhàn)。也就是說，由于每臺計算機一次只能看到一小部分輸入圖，因此需要處理機器間通信和設(shè)計可以拆分到多臺計算機的算法。

一個實現(xiàn)分布式算法的框架MapReduce于 2008 年推出。它透明地處理機器之間的通信，同時提供良好的容錯能力，并激發(fā)了許多分布式計算框架的開發(fā)，包括Pregel、Apache Hadoop等。盡管如此，在非常大的圖上開發(fā)分布式計算算法的挑戰(zhàn)仍然存在，并在這種情況下設(shè)計有效的算法，即使是基本問題，如連通分量、最大匹配或最短路徑，一直是一個活躍的研究領(lǐng)域。雖然最近的工作已經(jīng)證明了許多問題的新算法，包括我們的連接組件算法（理論和實踐）和層次聚類，但仍然需要可以更快地解決一系列問題的方法。

今天，我們通過首先構(gòu)建分布式圖算法的理論模型，然后演示如何應用該模型來解決這個問題。所提出的模型，自適應大規(guī)模并行計算(AMPC)，增強了 MapReduce 的理論能力，提供了一種以更少的計算輪次解決許多圖問題的途徑。我們還展示了如何在實踐中有效地實施AMPC 模型。我們描述的算法套件，包括最大獨立集、最大匹配、連通分量和最小生成樹的算法， 工作速度比當前最先進的方法快 7 倍。

MapReduce

的局限性 為了理解 MapReduce 在開發(fā)圖算法方面的局限性，請考慮連通分量問題的簡化變體。輸入是有根樹的集合，目標是為每個節(jié)點計算其樹的根。即使是這個看似簡單的問題，在 MapReduce 中也不容易解決。事實上，在大規(guī)模并行計算(MPC) 模型中——MapReduce、Pregel、Apache Giraph和許多其他分布式計算框架背后的理論模型——這個問題被廣泛認為至少需要多輪與log n成比例的計算，其中n是圖中節(jié)點的總數(shù)。雖然log n看起來不是一個很大的數(shù)字，但處理萬億邊圖的算法通常每輪都會將數(shù)百 TB 的數(shù)據(jù)寫入磁盤，因此即使輪數(shù)的小幅減少也可能帶來顯著的資源節(jié)省。

我們的算法中出現(xiàn)了一個類似的子問題，用于尋找連接的組件和計算層次聚類。我們觀察到，可以通過使用分布式哈希表(DHT)實現(xiàn)這些算法來繞過 MapReduce 的限制，這是一種使用一組鍵值對初始化的服務(wù)，然后返回與提供的鍵相關(guān)聯(lián)的值即時的。在我們的實現(xiàn)中，對于每個節(jié)點，DHT 存儲其父節(jié)點。然后，處理圖節(jié)點的機器可以使用 DHT 并“向上走”樹直到它到達根。雖然 DHT 的使用對這個特定問題很有效（盡管它依賴于不太深的輸入樹），但不清楚這個想法是否可以更廣泛地應用。

自適應大規(guī)模并行計算模型

為了將這種方法擴展到其他問題，我們首先開發(fā)了一個模型來從理論上分析利用 DHT 的算法。由此產(chǎn)生的 AMPC 模型建立在完善的 MPC 模型之上，并正式描述了使用分布式哈希表帶來的功能。

在 MPC 模型中，有一組機器，它們通過同步輪次中的消息傳遞進行通信。一輪中發(fā)送的消息在下一輪開始時傳遞，并構(gòu)成該輪的整個輸入（即，機器不保留從一輪到下一輪的信息）。在第一輪中，可以假設(shè)輸入隨機分布在機器上。目標是最小化計算輪數(shù)，同時確保每輪機器之間的負載平衡。

然后我們通過引入一種新方法來形式化 AMPC 模型，其中機器每輪寫入一個只寫分布式哈希表，而不是通過消息進行通信。一旦新一輪開始，前一輪的哈希表變?yōu)橹蛔x，并且新的只寫輸出哈希表變?yōu)榭捎?。重要的是，只有通信方法發(fā)生了變化——每臺機器的通信量和可用空間都以與 MPC 模型中完全相同的方式受到限制。因此，在高層次上，AMPC 模型的附加功能是每臺機器都可以選擇要讀取的數(shù)據(jù)，而不是提供一條數(shù)據(jù)。

算法和經(jīng)驗評估

機器通信方式的這種看似微小的差異使我們能夠為許多基本的圖形問題設(shè)計更快的算法。特別是，我們表明無論圖的大小如何，都可以在恒定的輪數(shù)中找到連通分量、最小生成樹、最大匹配和最大獨立集。

為了研究 AMPC 算法的實際適用性，我們通過將 Flume C++（FlumeJava的 C++ 對應物）與 DHT 通信層相結(jié)合來實例化模型。我們已經(jīng)針對最小生成樹、最大獨立集和最大匹配評估了我們的 AMPC 算法，并觀察到與不使用 DHT 的實現(xiàn)相比，我們可以實現(xiàn)高達 7 倍的加速。同時，AMPC 實現(xiàn)平均使用少 10 倍的輪數(shù) 來完成，并且向磁盤寫入的數(shù)據(jù)也更少。

我們對 AMPC 模型的實現(xiàn)利用了硬件加速遠程直接內(nèi)存訪問(RDMA)，該技術(shù)允許從遠程機器的內(nèi)存中讀取幾微秒的延遲，這僅比讀取慢一個數(shù)量級從本地內(nèi)存。 雖然一些 AMPC 算法比 MPC 算法傳輸?shù)臄?shù)據(jù)更多，但它們總體上更快，因為它們主要使用 RDMA 執(zhí)行快速讀取，而不是昂貴的磁盤寫入。

結(jié)論

利用 AMPC 模型，我們建立了一個受實際高效實現(xiàn)啟發(fā)的理論框架，然后開發(fā)了新的理論算法，這些算法提供了良好的經(jīng)驗性能并保持了良好的容錯特性。

更新說明：優(yōu)先更新微信公眾號“雨夜的博客”，后更新博客，之后才會陸續(xù)分發(fā)到各個平臺，如果先提前了解更多，請關(guān)注微信公眾號“雨夜的博客”。

博客來源：雨夜的博客