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

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

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

在論文中，她對(duì)分布式共識(shí)的代表算法Paxos提出了質(zhì)疑，并證明了當(dāng)前分布式共識(shí)很多未解決的問(wèn)題只是Paxos這個(gè)算法的問(wèn)題，而不是因?yàn)榉植际焦沧R(shí)本身的問(wèn)題。

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

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

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

論文摘要

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

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

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

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

論文簡(jiǎn)介

我們?cè)谏畹母鱾€(gè)方面都依賴(lài)計(jì)算機(jī)系統(tǒng)。我們希望系統(tǒng)能夠快速響應(yīng)，按預(yù)期運(yùn)行，并在需要時(shí)可用。然而，構(gòu)成這些系統(tǒng)的組件，例如計(jì)算機(jī)和連接它們的網(wǎng)絡(luò)，是不可靠的。

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

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

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

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

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

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

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

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

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

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

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

研究動(dòng)機(jī)

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

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

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

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

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

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

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

這些問(wèn)題在某些系統(tǒng)中很常見(jiàn)，它們通常相互關(guān)聯(lián)并逐步升級(jí)。實(shí)際上，部署Paxos并不能保證可用性，因?yàn)樗惴ǖ倪M(jìn)度取決于滿(mǎn)足當(dāng)今系統(tǒng)無(wú)法保證的同步和活躍條件。

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

由于領(lǐng)導(dǎo)者負(fù)責(zé)決策，所有決策請(qǐng)求必須轉(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)致一段時(shí)間不可用。

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

研究方法

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

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

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

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

研究局限

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

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

弱化語(yǔ)義 - 我們不支持具有弱化語(yǔ)義的操作，例如過(guò)時(shí)讀取或依賴(lài)于同步或有界時(shí)鐘漂移的操作，例如主租約。

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

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

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

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

論文大綱

本文共分為8章，通過(guò)逐步推廣流行的Paxos算法，構(gòu)建了解決分布式共識(shí)的新型廣義算法?？偟膩?lái)說(shuō)，我們做出了以下重要貢獻(xiàn)：

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

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

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

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

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

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

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

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

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