Paxos算法可以說是一致性領(lǐng)域最著名的算法之一了。

這幾天仔細(xì)讀了幾遍 Leslie Lamport的論文 《Paxos Made Simple》 ，可以說對(duì)paxos有了簡(jiǎn)單的理解，Lamport的證明過程簡(jiǎn)單靈巧，用他論文的Abstract來說就是： The Paxos algorithm, when presented in plain English, is very simple。

強(qiáng)烈推薦感興趣的朋友去讀一下這篇論文。下面講解的內(nèi)容可能不完全跟論文思路相同，會(huì)有一點(diǎn)自己的語(yǔ)言和想法在里面。證明的過程會(huì)有所省略，因?yàn)檫@篇的目的不是把證明過程完完整整講清楚，是想讓大家更容易的對(duì)Paxos算法有一個(gè)初步的理解。想看證明過程的朋友不妨去看這篇論文，畢竟才11頁(yè)看起來很快。

The Problem

首先我們假設(shè)一個(gè)場(chǎng)景，這里有很多的進(jìn)程，每個(gè)進(jìn)程都可以propose（提議）一個(gè)value，共識(shí)算法是為了保證：

在眾多proposed value中，只有一個(gè)value會(huì)被選中。

如果沒有進(jìn)程propose任何的value，那么最后不會(huì)有value被選中。

如果某一個(gè)value被選中了，那么所有的進(jìn)程都應(yīng)該可以知道這個(gè)value。

對(duì)于這個(gè)算法，有以下三個(gè)安全性需求（給出英文以防翻譯不當(dāng)）：

只有一個(gè)被propose過的value，才可能被選中（Only a value that has been proposed may by chosen）。

只會(huì)有一個(gè)value被選中（Only a single value is chosen）。

只有當(dāng)一個(gè)value確確實(shí)實(shí)被選中了，進(jìn)程才會(huì)知道（A process never learns that a value has been chosen unless it actually has been）。

下面即將進(jìn)入證明的過程，首先介紹以下會(huì)出現(xiàn)的三種角色：proposer, acceptor以及l(fā)earner。proposer的工作就是上文說過的propose value，并發(fā)送給acceptor；acceptor的工作就是接收從proposer那里發(fā)來的信息，根據(jù)情況給出反饋信息；learner的工作就是得知已經(jīng)被選中的value。

最后的目的就是保證：超過半數(shù)（the majority set）的acceptor選擇了同一個(gè)value，并且learner可以得知這個(gè)value被選中了。

Choosing a Value

這個(gè)部分論文中有詳細(xì)的推導(dǎo)過程，我們直接跳到推導(dǎo)的結(jié)果部分。其間新添加了一個(gè)參數(shù)：每個(gè)proposer發(fā)送的proposal（即發(fā)送給Acceptor，用來提議value的信息）中，都包括兩個(gè)參數(shù)。一個(gè)用來標(biāo)識(shí)proposal的proposal number，另一個(gè)是所提議的value。所以proposal形如<proposal number, proposed value>。（ 為了避免混淆，下文統(tǒng)一稱proposal number為編號(hào)）

進(jìn)過推導(dǎo)，最后得出的 proposer的算法如下：

proposer選擇一個(gè)新的編號(hào)n（注意是編號(hào)，不是proposal），發(fā)送request給acceptor，并要求它們回復(fù)以下兩點(diǎn)：(a). 承諾以后不會(huì)接收比n小的編號(hào)的proposal； (b). 回復(fù)曾經(jīng)接收過的，編號(hào)小于n中的所有proposal中編號(hào)最大的那個(gè)proposal。（翻譯過來有點(diǎn)繞嘴，給出英文原文：(b). The proposal with the highest number less than n that it has accepted, if any.）——這里我們把這樣的request起名叫做prepare request

如果proposer收到了超過半數(shù)的accepter的回復(fù)的話，他就可以提出一個(gè)proposal了。這個(gè)proposal = <proposal number n, Value v>。其中v是所有回復(fù)中，有最高編號(hào)的那個(gè)proposal的value值(上面b中提到的編號(hào))。另外一種情況如果所有的回復(fù)都顯示，目前acceptor們都沒有接受過任何一個(gè)proposal，那么這種情況該proposer可以自己隨便選擇一個(gè)value發(fā)送給acceptor。—— 這里我們把這樣的request起名叫做accept request

然后是相應(yīng)得出的acceptor的算法：

如果acceptor收到了一個(gè)新的prepare request，并且編號(hào)n大于它曾經(jīng)回復(fù)過的任何prepare request的編號(hào)的話。acceptor就會(huì)回復(fù)保證不會(huì)再接收編號(hào)小于n的任何proposal，并且回復(fù)曾經(jīng)收到的過prepare request中最大的編號(hào)（如果曾經(jīng)收到過的話）。

如果收到了accept request，并且其中的編號(hào)為n。acceptor在沒有回復(fù)過比n更大的編號(hào)的prepare request的情況下，會(huì)接受這個(gè)accept request。

至此，就是proposer和acceptor的算法。下面還有在此基礎(chǔ)上進(jìn)一步的內(nèi)容。

Learning a Chosen Value

想要得知是否已經(jīng)有一個(gè)value被算法選擇出來了，learner需要去查詢是否有超過半數(shù)的acceptor已經(jīng)接受了某個(gè)proposal。最簡(jiǎn)單的實(shí)現(xiàn)肯定是，所有的acceptor在接受了一個(gè)proposal之后，給所有的learner發(fā)送消息。這種情況下所有的learner都可以第一時(shí)間發(fā)現(xiàn)the chosen value。但是這樣做的信息數(shù)量太多了，需要優(yōu)化。

于是我們可以在所有的learner中選出一個(gè)負(fù)責(zé)人（Distinguished Learner），所有的acceptor都把消息發(fā)給它，然后它轉(zhuǎn)發(fā)給其他所有的learner。這種方法雖然效率很高，但是如果被選出的負(fù)責(zé)人fail了，系統(tǒng)就無從得知the chosen value了。

更一般性的實(shí)現(xiàn)就是，選出幾個(gè)負(fù)責(zé)人，他們一起從事上述的工作，雖然增加了一點(diǎn)消息數(shù)量，但是安全性得到了很大提升。（后面兩種實(shí)現(xiàn)都可以）

Progress

還有一點(diǎn)點(diǎn)問題需要解決，假設(shè)有兩個(gè)proposer不斷地發(fā)出proposal，每次都比對(duì)方的編號(hào)大1。這樣就會(huì)導(dǎo)致兩個(gè)人的所有proposal都不會(huì)被采納（原因看上面算法很容易分析）。

為了解決這個(gè)問題，我們需要同樣選出一個(gè)proposer中的負(fù)責(zé)人（Distinguished proposer），使得只有這個(gè)負(fù)責(zé)人去負(fù)責(zé)提出proposal，這樣就可以解決上述問題。

The Implementation

上面三部分就講完了整個(gè)paxos算法了。

所以我們假設(shè)的這個(gè)進(jìn)程系統(tǒng)中，paxos算法一共需要三種角色：proposer，acceptor和learner（每個(gè)進(jìn)程可以擔(dān)當(dāng)多個(gè)角色）。并且需要選出一個(gè)或者多個(gè)leader來?yè)?dān)當(dāng)負(fù)責(zé)人（Distinguished proposer/learner）。

但是在我講述這個(gè)算法的過程中有很多前提或者假設(shè)都被省略掉了，比如：

• 我們的系統(tǒng)是customary asynchronous, non-Byzantine model。
• 所有的角色都以任意的速度進(jìn)行操作，有可能遭遇failure或者重啟。
• 所有的消息都經(jīng)過任意長(zhǎng)的時(shí)間才會(huì)被接收到，而且可能出現(xiàn)重復(fù)甚至丟失，但是不會(huì)被損壞。

所以很慚愧的說我這篇文章是很不嚴(yán)謹(jǐn)?shù)?#xff0c;只是把論文中paxos算法簡(jiǎn)明的講述了出來，如果有漏洞甚至理解錯(cuò)誤的地方，希望大家不吝賜教。

https://zhuanlan.zhihu.com/p/25438477

總結(jié)

以上是生活随笔為你收集整理的Paxos算法小结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。