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

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

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

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

共識機(jī)制是什么？

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

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

論文摘要

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

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

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

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

論文簡介

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

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

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

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

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

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

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

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

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

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

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

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

研究動機(jī)

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

首先，Paxos是出了名的難理解，導(dǎo)致了大量的后續(xù)工作，用更簡單的術(shù)語解釋算法并填補(bǔ)原始描述中的空白，這是構(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)建設(shè)或教育提供良好的基礎(chǔ)。- Diego Ongaro和John Ousterhout

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

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

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

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

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

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

研究方法

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

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

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

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

研究局限

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

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

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

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

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

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

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

論文大綱

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

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

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

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

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

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

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

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

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

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