大規模並行圖計算：從理論到實踐

圖片

圖 (Graph) 適用於在理論意義上表示多個實體組間的聯繫，並且已在數據科學領域中用於實現各種目的，包括按網絡熱度排名、社交網絡設計以及協助導航。許多情況下，這類應用需要處理包含數千億條邊的圖，這些圖因太大而無法在單臺消費級機器上進行處理。對圖算法進行擴展的典型方法是在分佈式設置下運行，即劃分多臺計算機間的數據（和算法），並行執行計算。雖然這種方法可以處理包含數萬億條邊的圖，但同時也帶來了新的挑戰。換言之，由於每臺計算機一次只能看到輸入圖的一小部分，因此我們需要處理機器間通信，並設計可劃分在多臺計算機上的算法。

2008 年，用於實現分佈式算法的框架 MapReduce 面世。它在提供良好容錯能力的同時以透明方式處理機器間的通信，並指引了許多分佈式計算框架的開發，包括 Pregel、Apache Hadoop 以及許多其他框架。儘管如此，開發超大圖分佈式計算算法的挑戰依然存在，並且在這種情況下，即使是設計解決基本問題（例如：連通分量、最大匹配或最短路徑）的高效算法都已成熱門研究領域。雖然近期的研究驗證瞭解決許多問題的新算法，包括我們用於連通分量（在理論和實踐中）以及層次聚類的算法，但是仍然需要能夠更快速解決各種問題的方法。

今天，我們將展示兩篇近期針對此問題發表的論文，整個過程包括：先爲分佈式圖算法構建理論模型，然後演示如何應用該模型。所提出的模型 “自適應大規模並行計算 (AMPC)” 增強了 MapReduce 的理論功能，同時提供在更少的計算回合下解決許多圖問題的途徑。我們還展示瞭如何在實踐中有效地實現 AMPC 模型。我們介紹的這套算法包含用於最大獨立集、最大匹配、連通分量和最小生成樹的算法，其運行速度是當前最先進方法的 7 倍。

MapReduce 的侷限性

爲了解 MapReduce 在開發圖算法上的侷限性，我們考慮了連通分量問題的簡化變體。其中，輸入是一組有根樹，目標是針對每個節點計算其樹的根。但即使是這個看似簡單的問題，也不容易在 MapReduce 中得到解決。實際上，在大規模並行計算 (MPC) 模型（即，MapReduce、Pregel、Apache Giraph 以及許多其他分佈式計算框架背後的理論模型）中，人們普遍認爲此問題至少需要多輪與 log n 成正比的計算，其中 n 是圖中的總節點數。雖然 log n 看似不是一個大數字，但處理包含數萬億條邊的圖的算法通常會在每輪計算中將數百太字節的數據寫入磁盤中，因此即便是稍微減少幾輪計算也可節省大量資源。

圖片

關於查找根節點的問題。節點以藍色圓形表示。灰色箭頭從每個節點指向其父節點。根節點是沒有父節點的節點。橙色箭頭的路徑展示了算法在從節點到其所屬樹的根節點的過程

在用於查找連通分量和計算層次聚類的算法中，我們發現了一個類似的子問題。我們發現，可通過使用分佈式哈希表 (DHT)（這項服務使用大量鍵值對進行初始化，然後實時返回與所提供鍵關聯的值）來實現這些算法，從而避免 MapReduce 的侷限性。在我們的實現中，DHT 會爲每個節點儲存其父節點。然後，處理圖節點的機器可以使用 DHT 並沿着這個樹到達根位置。雖然使用 DHT 能夠很好地解決這個具體問題（儘管它依賴於深度較小的輸入樹），但我們不清楚這種思路能否得到更廣泛的應用。

自適應大規模並行計算模型

爲了將此方法擴展到其他問題上，我們開始開發一種模型，從理論上分析利用 DHT 的算法。產生的 AMPC 模型基於完善的 MPC 模型構建，並且正式描述了通過使用分佈式哈希表引入的功能。

MPC 模型中有大量機器，它們通過同步回合中傳遞的消息進行通信。一個回合中發送的消息是在下一回合開始的時候傳遞的，並構成該回合的整個輸入（即，機器不會保留從一個回合到下一回合的信息）。在第一個回合中，我們可以假設輸入隨機分佈在機器間。我們的目標是最大限度地減少計算回合數，同時確保每個回合機器間都能實現負載平衡。

圖片

MPC 模型中的計算。每一列在後續計算回合中表示一臺機器。當所有機器完成一個計算回合後，系統會傳遞該回閤中發送的所有消息，並且下一回合將會開始

然後，我們通過引入一種新方法對 AMPC 模型進行形式化，其中機器每個回合會對一個只寫的分佈式哈希表進行寫入，而非通過消息進行通信。在新回合開始後，上一回合的哈希表將變爲只讀狀態，而一個新的只寫輸出哈希表將可供使用。重要的是，只有通信方法發生變化，每臺機器的通信量和可用空間則完全按照 MPC 模型中的方式受到限制。因此，在較高級別上，所添加的 AMPC 模型功能是每臺機器可以選擇要讀取的數據，而非被動獲得一份數據。

圖片

AMPC 模型中的計算。當所有機器已完成一個計算回合後，它們生成的數據將保存到分佈式哈希表中。在下一回閤中，每臺機器可以從此分佈式哈希表中讀取任意值並寫入新的分佈式哈希表

算法和經驗評估

得益於機器通信方式中這個看似細微的差異，我們能夠爲許多基本圖問題設計出速度更快的算法。特別是，我們證明了無論圖的大小如何，都能在回合數固定的情況下找到連通分量、最小生成樹、最大匹配以及最大獨立集。

爲了研究 AMPC 算法的實際適用性，我們將 Flume C++（FlumeJava 的 C++ 版本）與 DHT 通信層相結合，對該模型進行了實例化。我們評估了用於最小生成樹、最大獨立集和最大匹配的 AMPC 算法，並發現其速度可以達到未使用 DHT 的實現的 7 倍。同時，AMPC 實現完成任務所使用的平均回合數是 未使用 DHT 的實現的 1/10，並且向磁盤寫入的數據也更少。

我們 AMPC 模型的實現利用了硬件加速的遠程直接內存訪問 (RDMA)，該技術允許讀取遠程機器的內存，延遲時間爲數微秒，僅比讀取本地內存慢一個數量級。雖然一些 AMPC 算法比其對應的 MPC 算法傳遞更多數據，但前者的整體速度更快，因爲它們主要使用 RDMA 執行快速讀取，而非用更多時間寫入磁盤。

結論

受到高效的實際實現啓發，我們藉助 AMPC 模型構建了一個理論框架，然後開發了提供良好經驗性能並保持良好容錯屬性的新理論算法。我們很高興看到 AMPC 模型已成爲進一步研究的主題，同時瞭解到使用 AMPC 模型或其實際實現能夠更高效地解決哪些其他問題。

致謝

本文中所提到的兩篇論文的共同作者包括 Soheil Behnezhad、Laxman Dhulipala、Hossein Esfandiari 和 Warren Schudy。另外，感謝 Graph Mining 團隊的成員所給予的協助，特別感謝 Mohammad Hossein Bateni 對本文的貢獻。如需詳細瞭解我們近期對可擴展圖算法的研究，請觀看我們最近在 Graph Mining and Learning 研討會中發佈的視頻。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/yNQvBZM_WjQ7-xuHd-TCqg

猜你喜歡