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定理等流行公式。然而，這樣的公式很粗糙。

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