Jeff Dean推薦網紅博士論文：對分散式共識核心演算法Paxos的重大改進

新智元推薦

來源：圖靈TOPIA(ID：turingtopia)

編輯：劉靜

【新智元導讀】Jeff Dean近日推薦了一篇網紅博士論文——改進分散式共識機制。本文作者Heidi Howard，是劍橋大學計算機科學與技術系系統研究小組的分散式系統研究員。她在論文中對分散式共識的代表演算法Paxos提出之質疑，得到了眾網友們的點贊。

Heidi的研究領域一直圍繞分散式系統中的一致性，容錯性和性能並且專註於分散式一致性演算法。她最廣為人知的是Leslie Lamport用於解決共識的Paxos演算法的泛化，稱為Flexible Paxos。

昨天，Heidi的博士論文《改進分散式共識》公開。

在論文中，她對分散式共識的代表演算法Paxos提出了質疑，並證明了當前分散式共識很多未解決的問題只是Paxos這個演算法的問題，而不是因為分散式共識本身的問題。

共識機制是什麼？

簡單來講，它並不是解決對網路裡面的是非的判斷，而是說當我在網路中發生了兩個可能會產生衝突的交易時候，我去選擇哪一個，或者再換一句話說，如果有兩個事實都是可以成立的時候，去選擇哪一個，這是一個決策的機制，而不是判斷是非的機制。

分散式共識是目前大熱的區塊鏈的核心技術。

論文摘要

在日常生活中的各個方面，我們都依賴於分散式系統。分散式共識，即在面對故障和非同步時達成協議的能力，是用不可靠組件構建可靠分散式系統的基礎和強大原語。

20多年來，Paxos演算法一直是分散式共識的代名詞。Paxos被廣泛應用於生產系統，但人們對它知之甚少，並且在實踐中證明它是重量級的，不可擴展的和不可靠的。

因此，為了更好地理解該演算法，優化其性能並減輕其局限性，Paxos一直是廣泛研究的主題。在本文中，我們重新研究了Paxos如何解決分散式共識的基礎。我們的假設是，這些限制並不是共識問題所固有的，而是Paxos方法特有的。

令人驚訝的是，我們的分析結果大大削弱了這一廣泛研究的演算法的要求。我們對分散式共識的修訂理解使我們能夠構建一個多樣化的演算法族來解決共識;涵蓋了經典演算法和新演算法，以達到以前認為不可能的共識。我們將探討這種新理解的廣泛影響，從實用優化到生產系統，再到基本新穎的共識方法，從而在性能，可擴展性和可靠性方面實現新的權衡。

論文簡介

我們在生活的各個方面都依賴計算機系統。我們希望系統能夠快速響應，按預期運行，並在需要時可用。然而，構成這些系統的組件，例如計算機和連接它們的網路，是不可靠的。

分散式共識是指如何在面對故障和非同步時可靠地達成一致的問題。這一長期挑戰對於分散式系統至關重要，一旦解決了這個問題，我們就可以用不可靠的組件構建可靠的分散式系統。

20年來，Lamport的Paxos演算法已經成為分散式共識的代名詞。它在生產中得到了廣泛的應用，優化、擴展和更好地理解該演算法一直是廣泛研究的課題。

儘管它很受歡迎，但Paxos在實踐中表現不佳，它的方法不夠靈活、特別重量級而且不可擴展，在面對非同步和失敗時可能無法使用。本文重新審視了分散式共識的問題及其解決方法。

首先，我們證明了Paxos實際上只是解決分散式共識的廣泛方法的一個方面，這為新一代高性能，可擴展且具有彈性的共識演算法打開了大門。然後，我們探索了這個結果可能產生的一些新演算法;其中一些甚至能夠在以前認為不可能的地方達成共識。

我們描述了在現代分散式系統中達成共識的實際方法。對於不熟悉該領域的讀者，我們將概述本研究的歷史背景，重點關注分散式共識問題的早期表述如何形成（並且可論證有限）今天如何解決。

接下來是我們對這種廣泛採用的方法的批評，以及我們重新審視如何解決共識的動機。我們描述了我們為調查共識而選擇的方法，並強調了對共識領域作出的驚人貢獻。

現有技術

在各方之間達成協議的能力是現代社會的一項基本必要條件，無論是決定開會的時間還是由誰來治理國家。對於分散式計算機系統也是如此，其中主機需要協議以共享諸如定址，資源分配，文件系統，主要選舉，路由，鎖定，排序和協調等重要功能的一致狀態。

協議涵蓋分散式系統中的廣泛決策問題。分散式共識是一個這樣的問題，其特徵在於兩個保證：首先，所有決策都是最終的，不需要假設可靠性或同步性（安全保證）；其次，最終將達成一個決策(進度保證)。如果不對同步性或可靠性做出假設，就無法保證進展。因此，解決共識的演算法旨在保證在最弱的活躍度假設下的進展。

Paxos演算法最初由Leslie Lamport於1998年提出，後來被改進，是我們今天如何實現分散式共識的核心。從廣義上講，其方法分兩個階段進行，每個階段都需要大多數參與者的同意。第一階段是將參與者之一確定為領導者，防止過去的領導者做出任何進一步的決定。

一旦大多數參與者同意誰將領導，領導者將進入第二階段，通過獲得大多數參與者的支持做出決策。領導者負責確保在演算法的第一階段學習到的所有過去的決策都被保留下來，並且只有在安全的情況下才會提出新的值。只要至少大多數參與者正在啟動並同步通信，該演算法就能保證做出決策。這種方法現在被廣泛採用作為許多生產系統的基礎。

研究動機

儘管Paxos已經成為分散式系統中達成共識的事實上的方法，但它也並非沒有局限性。

首先，Paxos是出了名的難理解，導致了大量的後續工作，用更簡單的術語解釋演算法並填補原始描述中的空白，這是構建實際實現所必需的。理論與系統社區之間的這種不一致最好用以下引語說明：

Paxos演算法以簡單的英語呈現，非常簡單。[Paxos]是最簡單，最明顯的分散式演算法之一。- Leslie Lamport

Paxos非常難以理解。完整的解釋是出了名的不透明;很少有人能夠成功地理解它，並且只有付出很大的努力。。。。在NSDI 2012的與會者的非正式調查中，我們發現很少有人對Paxos感到滿意，即使是經驗豐富的研究人員也是如此。

我們的結論是，Paxos沒有為系統建設或教育提供良好的基礎。- Diego Ongaro和John Ousterhout

其次，對多數協議的依賴意味著Paxos演算法決策速度很慢，因為每個演算法都需要往返於多個參與者之間。通過讓大多數參與者參與每個決策，參與者和領導者之間的網路上設置了高負載。因此，系統的規模有限，通常只有三到五個參與者，因為每增加一名參與者，整體性能就會顯著下降。

很明顯，如果大多數參與者都失敗了，那麼Paxos就無法達成協議。但是，這只是整體情況的一部分，未能達成協議不僅會導致主機不可用，還會導致網路分區，主機速度慢，網路擁塞，持久存儲等資源爭用，時鐘偏差，數據包丟失等無數問題。

這些問題在某些系統中很常見，它們通常相互關聯並逐步升級。實際上，部署Paxos並不能保證可用性，因為演算法的進度取決於滿足當今系統無法保證的同步和活躍條件。

Paxos的共識方法是確定了一位參與者為領導者，並使該參與者對決策負責。這種集中式方法將簡單性作為單一的序列化點提供，但它也使演算法的性能與單個高度擁塞的參與者的性能相關。

由於領導者負責決策，所有決策請求必須轉發給領導者並由領導者處理，這進一步增加了決策延遲。領導者在分散式系統中引入了單點故障。雖然Paxos能夠在給定條件下從領導者故障中恢復，但是這種恢復可能是緩慢且麻煩的並且通常導致一段時間不可用。

這些限制眾所周知，但在實踐中很少使用Paxos的替代品。分散式共識中的大量學術文獻通常側重於通過優化，擴展和實用實現來減輕這些限制。鑒於我們迄今為止所討論的局限性，亞馬遜的Dynamo和Facebook的TAO 等生產系統選擇犧牲強一致性保證以支持高可用性。

研究方法

自然會出現這樣的問題：這些限制是否是共識問題所固有的，還是Paxos演算法採用的方法所特有的？同樣，Paxos演算法是達成共識的最佳解決方案嗎？這些問題將指導我們的研究。

我們的方法是重新審視分散式共識的問題，以及我們作為一個社區如何處理這個問題。與以前的工作相比，我們對如何在單一價值上達成共識進行了廣泛的研究。由於Paxos的廣泛採用以及我們對共識的基礎理論的關注，我們的分析結果可能具有廣泛的影響，這些影響與特定系統，硬體，工作負載或部署方案無關（因此不受限於範圍） 。

我們首先開發一個框架，用於證明共識演算法的正確性，並將其應用於Paxos演算法。該框架的目的是明確如何在正確性證明中使用演算法的屬性。這允許我們修改演算法並驗證正確性，而無需重新驗證整個演算法。

這種方法的令人驚訝的結果有兩個方面：確性的證明沒有充分利用所提供的屬性的強度;其次，有許多方法滿足相同的屬性。這些觀察結果構成了我們逐步推廣Paxos演算法的基礎。在每個階段，我們都能夠通過建立在原始證明的基礎上來驗證正確性。

研究局限

拜占庭容錯 - 我們假設演算法被正確地實現和執行。參與者和他們之間的網路不能任意或惡意行動。不假設這種情況的共識演算法稱為拜占庭容錯。PBFT [CL99]是這種演算法的一個例子。

重新配置 - 我們假設一組固定且已知的參與者，每個參與者都有一個唯一的標識符。重構在文獻中有廣泛的討論，是許多演算法的組成部分。例子包括Stoppable Paxos，VRR ，Raft 。

弱化語義 - 我們不支持具有弱化語義的操作，例如過時讀取或依賴於同步或有界時鐘漂移的操作，例如主租約。

實現細節 - 我們假設無邊界存儲，任意值的表示，狀態或消息沒有損壞。參與者可以停止並重新啟動。重新啟動時，持久狀態不變，重新初始化非持久狀態，並從頭開始再次執行演算法。假設本文提供的偽代碼由單個線程按順序執行，並且每條線以原子方式執行。必須在繼續之前完成對state的寫入，包括寫入持久存儲。這可以通過諸如預寫日誌之類的技術來實現。從狀態讀取必須始終返回一個最新值。

偏序 - 我們的演算法決定一個單一值（或決定一個完全有序的，無限的值序列）。我們不考慮就多個系列值，部分有序序列[Lam05b]或有限序列[MLZ08]達成一致。

實踐進展 - 參與者可以以任意速度運作。消息最終被傳遞，但是通信信道傳遞消息的時間沒有限制。消息可能無序或多次傳遞。然而，演算法的進展取決於廣泛的假設，包括同步和定時。我們在這些假設下證明了演算法的進展，但它們並不是最小的。

特定系統 - 所有演算法都是作為高級表示提供的，而不是具體的協議或實現。為了繼續適用於一系列現有系統和其他系統，我們不會對特定系統或工作負載進行優化，因為這是廣泛研究的主題。例如，Ring Paxos和Multi-Ring Paxos 針對提供IP多播的網路進行了優化。

論文大綱

本文共分為8章，通過逐步推廣流行的Paxos演算法，構建了解決分散式共識的新型廣義演算法。總的來說，我們做出了以下重要貢獻：

第2章我們首先定義分散式共識的問題，並概述兩個已知的解決方案，一個簡單的稻草人演算法和廣泛使用的Paxos演算法。我們證明兩種演算法都滿足解決共識的必要要求。

第3章在知識章節的系統化中，我們概述了Paxos演算法最常見的改進，將基礎演算法貢獻與文獻中使用的框架和術語的細節分開，這些文獻中使用的框架和術語通常在不同的出版物中有很大的不同。

第4章我們通過弱化quorum交集要求來概括Paxos演算法，允許演算法的兩個階段中的每個階段都有不相交的交集。然後，我們提出了進一步的一般化，通過弱化quorum交集要求，允許演算法的第一階段和隨後的第二階段之間不相交。

第5章我們證明了quorum交集是可傳遞的並且可以重複使用，允許在某些情況下使用較少的參與者來做出決策。

第6章我們通過利用演算法第一階段的知識來弱化價值選擇規則來推廣Paxos演算法。這種一般化使參與者在選擇建議值時具有更大的靈活性。

第7章我們進一步擴展我們的泛型，允許各種共享階段的機制，以便最好地利用迄今為止的泛型。我們提出的演算法可以提供新的進度保證，並可以在幾個階段做出決策。

本論文的結果是一系列實現分散式共識的方法，這些方法概括了最流行的現有演算法，如Paxos和Fast Paxos 。我們的目標是進一步了解這個通常知之甚少的領域，並展示解決共識的可能正確方法的廣度。

在論文的後面，我們探討了我們對共識的修訂理解的廣泛影響。我們專註於如何提高共識演算法的性能和可靠性，從而建立在它們之上的分散式系統。分散式系統因需要在理想特性之間進行折衷而聞名，這在很大程度上歸功於CAP定理等流行公式。然而，這樣的公式很粗糙。

我們的目標是量化達成共識的具體權衡，並演示實現這些特性的演算法。

參考鏈接：

https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-935.pdf

更多閱讀

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！