Jeff Dean近日推薦了一篇網(wǎng)紅博士論文——改進分布式共識機制。本文作者Heidi Howard，是劍橋大學計算機科學與技術(shù)系系統(tǒng)研究小組的分布式系統(tǒng)研究員。她在論文中對分布式共識的代表算法Paxos提出之質(zhì)疑，得到了眾網(wǎng)友們的點贊。

Heidi的研究領(lǐng)域一直圍繞分布式系統(tǒng)中的一致性，容錯性和性能并且專注于分布式一致性算法。她最廣為人知的是Leslie Lamport用于解決共識的Paxos算法的泛化，稱為Flexible Paxos。

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

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

共識機制是什么？

簡單來講，它并不是解決對網(wǎng)絡里面的是非的判斷，而是說當我在網(wǎng)絡中發(fā)生了兩個可能會產(chǎn)生沖突的交易時候，我去選擇哪一個，或者再換一句話說，如果有兩個事實都是可以成立的時候，去選擇哪一個，這是一個決策的機制，而不是判斷是非的機制。

分布式共識是目前大熱的區(qū)塊鏈的核心技術(shù)。

論文摘要

在日常生活中的各個方面，我們都依賴于分布式系統(tǒng)。分布式共識，即在面對故障和異步時達成協(xié)議的能力，是用不可靠組件構(gòu)建可靠分布式系統(tǒng)的基礎和強大原語。

20多年來，Paxos算法一直是分布式共識的代名詞。Paxos被廣泛應用于生產(chǎn)系統(tǒng)，但人們對它知之甚少，并且在實踐中證明它是重量級的，不可擴展的和不可靠的。

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

令人驚訝的是，我們的分析結(jié)果大大削弱了這一廣泛研究的算法的要求。我們對分布式共識的修訂理解使我們能夠構(gòu)建一個多樣化的算法族來解決共識;涵蓋了經(jīng)典算法和新算法，以達到以前認為不可能的共識。我們將探討這種新理解的廣泛影響，從實用優(yōu)化到生產(chǎn)系統(tǒng)，再到基本新穎的共識方法，從而在性能，可擴展性和可靠性方面實現(xiàn)新的權(quán)衡。

論文簡介

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

分布式共識是指如何在面對故障和異步時可靠地達成一致的問題。這一長期挑戰(zhàn)對于分布式系統(tǒng)至關(guān)重要，一旦解決了這個問題，我們就可以用不可靠的組件構(gòu)建可靠的分布式系統(tǒng)。

20年來，Lamport的Paxos算法已經(jīng)成為分布式共識的代名詞。它在生產(chǎn)中得到了廣泛的應用，優(yōu)化、擴展和更好地理解該算法一直是廣泛研究的課題。

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

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

我們描述了在現(xiàn)代分布式系統(tǒng)中達成共識的實際方法。對于不熟悉該領(lǐng)域的讀者，我們將概述本研究的歷史背景，重點關(guān)注分布式共識問題的早期表述如何形成（并且可論證有限）今天如何解決。

接下來是我們對這種廣泛采用的方法的批評，以及我們重新審視如何解決共識的動機。我們描述了我們?yōu)檎{(diào)查共識而選擇的方法，并強調(diào)了對共識領(lǐng)域作出的驚人貢獻。

現(xiàn)有技術(shù)

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

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

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

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

研究動機

盡管Paxos已經(jīng)成為分布式系統(tǒng)中達成共識的事實上的方法，但它也并非沒有局限性。

首先，Paxos是出了名的難理解，導致了大量的后續(xù)工作，用更簡單的術(shù)語解釋算法并填補原始描述中的空白，這是構(gòu)建實際實現(xiàn)所必需的。理論與系統(tǒng)社區(qū)之間的這種不一致最好用以下引語說明：

Paxos算法以簡單的英語呈現(xiàn)，非常簡單。[Paxos]是最簡單，最明顯的分布式算法之一。- Leslie Lamport

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

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

其次，對多數(shù)協(xié)議的依賴意味著Paxos算法決策速度很慢，因為每個算法都需要往返于多個參與者之間。通過讓大多數(shù)參與者參與每個決策，參與者和領(lǐng)導者之間的網(wǎng)絡上設置了高負載。因此，系統(tǒng)的規(guī)模有限，通常只有三到五個參與者，因為每增加一名參與者，整體性能就會顯著下降。

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

這些問題在某些系統(tǒng)中很常見，它們通常相互關(guān)聯(lián)并逐步升級。實際上，部署Paxos并不能保證可用性，因為算法的進度取決于滿足當今系統(tǒng)無法保證的同步和活躍條件。

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

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

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

研究方法

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

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

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

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

研究局限

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

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

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

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

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

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

特定系統(tǒng) - 所有算法都是作為高級表示提供的，而不是具體的協(xié)議或?qū)崿F(xiàn)。為了繼續(xù)適用于一系列現(xiàn)有系統(tǒng)和其他系統(tǒng)，我們不會對特定系統(tǒng)或工作負載進行優(yōu)化，因為這是廣泛研究的主題。例如，Ring Paxos和Multi-Ring Paxos 針對提供IP多播的網(wǎng)絡進行了優(yōu)化。

論文大綱

本文共分為8章，通過逐步推廣流行的Paxos算法，構(gòu)建了解決分布式共識的新型廣義算法?？偟膩碚f，我們做出了以下重要貢獻：

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

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

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

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

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

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

本論文的結(jié)果是一系列實現(xiàn)分布式共識的方法，這些方法概括了最流行的現(xiàn)有算法，如Paxos和Fast Paxos 。我們的目標是進一步了解這個通常知之甚少的領(lǐng)域，并展示解決共識的可能正確方法的廣度。

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

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