Paxos協(xié)議相關(guān)知識(shí)點(diǎn)有哪些

大家可能在各個(gè)場(chǎng)合都聽(tīng)說(shuō)過(guò)Paxos協(xié)議，畢竟這個(gè)開(kāi)創(chuàng)性的協(xié)議是很多分布式協(xié)議的鼻祖，比如后面比較有名的Raft協(xié)議就是基于Paxos協(xié)議發(fā)展而來(lái)的?，F(xiàn)實(shí)中也有很多產(chǎn)品在使用Paxos協(xié)議，像是Google的Chubby，Spanner，IBM的SVC等。 但是在筆者的學(xué)習(xí)過(guò)程中，發(fā)現(xiàn)介紹Paxos協(xié)議的很多，但是真正能把它講明白的卻很少。所以筆者特意花了一定的時(shí)間來(lái)研究Paxos協(xié)議，現(xiàn)把學(xué)習(xí)結(jié)果分析如下。

角色

在Paxos協(xié)議中存在5種角色: client, acceptor, proposer, learner, 和 leader。但在實(shí)際的實(shí)現(xiàn)中，一個(gè)服務(wù)可能同時(shí)扮演一個(gè)或者多個(gè)角色，這樣做的考慮是為了減少消息延遲和消息數(shù)量，提升整個(gè)Paxos協(xié)議的工作效率。

Client
Client 是指請(qǐng)求的發(fā)起端，Client發(fā)送請(qǐng)求給分布式系統(tǒng)，并等待回復(fù)。

Acceptor (Voters)
Acceptor 可以看做是消息請(qǐng)求的存儲(chǔ)器。一般來(lái)說(shuō)Acceptors是由一定數(shù)量的服務(wù)組成的，當(dāng)消息被發(fā)送給Acceptor， 只有大部分Acceptor確認(rèn)接收此消息，該消息才會(huì)被存儲(chǔ)，否則該消息將被丟棄。

Proposer
Proposer 可以看做Client的代理人，Proposer將Client的消息請(qǐng)求發(fā)送給Acceptors，并等待Acceptors的確認(rèn)。在發(fā)生消息沖突時(shí)，Proposer將會(huì)嘗試解決沖突。

Learner
Learners可以看做是所有被確認(rèn)消息的執(zhí)行器，一旦有Client的消息請(qǐng)求被Acceptors確認(rèn)之后，Learners會(huì)做相應(yīng)的處理（如：執(zhí)行消息內(nèi)容，發(fā)送回復(fù)給Client）。Learner可以有多個(gè)。

Leader
Paxos需要一個(gè)Leader來(lái)確保分布式系統(tǒng)可以按步驟進(jìn)行下去。這里的Leader其實(shí)就是一個(gè)Proposer, Paxos協(xié)議會(huì)確保只有一個(gè)Proposer會(huì)被當(dāng)做Leader。

Proposal Number & Agreed Value

Proposal Number 也叫提案編號(hào)，我們用n表示，對(duì)于每一個(gè)Proposer來(lái)說(shuō)，每一個(gè)提案編號(hào)都是唯一的。
Agreed Value也叫確認(rèn)值，我們用v來(lái)表示，v是Acceptors確認(rèn)的值。
兩個(gè)值組合起來(lái)就是（n，v）。

Basic Paxos

Paxos協(xié)議有很多變種，這里我們首先介紹一下Basis Paxos，后面的文章我們會(huì)繼續(xù)介紹其他的Paxos協(xié)議。當(dāng)然，既然是基礎(chǔ)的Paxos協(xié)議，搞懂了它，對(duì)于其他的Paxos協(xié)議自然手到擒來(lái)。

在Basic Paxos 協(xié)議中，有很多次的執(zhí)行過(guò)程，每次執(zhí)行過(guò)程產(chǎn)生一個(gè)單獨(dú)的執(zhí)行結(jié)果。每次執(zhí)行過(guò)程都有很多輪次，每一輪都有2個(gè)階段。

階段1

• 階段1A：Prepare

  在Prepare階段，一個(gè)Proposer會(huì)創(chuàng)建一個(gè)Prepare消息，每個(gè)Prepare消息都有唯一的提案編號(hào)n。n并不是將要提案的內(nèi)容，而只是一個(gè)唯一的編號(hào)，用來(lái)標(biāo)志這個(gè)Prepare的消息。
  n必須比該P(yáng)roposer之前用過(guò)的所有編號(hào)都大，一般來(lái)說(shuō)我們可以以數(shù)字遞增的方式來(lái)實(shí)現(xiàn)這個(gè)編號(hào)。
  接下來(lái)Proposer會(huì)把該編號(hào)發(fā)送給Acceptors，只有大多數(shù)Acceptors接收到Proposer發(fā)來(lái)的消息，該消息才算是發(fā)送成功。

• 階段1B：Promise

  所有的Acceptors都在等待從Proposers發(fā)過(guò)來(lái)的Prepare消息。當(dāng)一個(gè)Acceptor收到從Proposer發(fā)過(guò)來(lái)的Prepare消息時(shí)候，會(huì)有兩種情況：

• 該消息中的n是Acceptor所有收到的Prepare消息中最大的一個(gè)，那么該Acceptor必須返回一個(gè)Promise消息給Proposer，告訴它后面所有小于n的消息我都會(huì)忽略掉。如果該Acceptor在過(guò)去的某個(gè)時(shí)間已經(jīng)確認(rèn)了某個(gè)消息，那么它必須返回那個(gè)消息的proposal number m 和 accepted value w （m，w）。如果該Acceptor在過(guò)去并沒(méi)有確認(rèn)過(guò)任何消息，那么會(huì)返回NULL。

• 如果Prepare消息中的n小于該Acceptor之前接收到的消息，那么該消息會(huì)被Acceptor忽略（為了優(yōu)化也可以返回一個(gè)拒絕消息給Proposer，告訴它不要再發(fā)小于n的消息給我了）。

階段2

• 階段2A：Accept

  如果一個(gè)Proposer從Acceptors接收到了足夠多的Promises（>n/2），這表示該P(yáng)roposer可以開(kāi)始下一個(gè)Accept請(qǐng)求的階段了，在Accept階段，Proposer需要設(shè)置一個(gè)值，然后向Acceptors發(fā)送Accept請(qǐng)求。
  在階段1B我們講到了，如果Acceptor之前確認(rèn)過(guò)消息，那么會(huì)把該消息編號(hào)和消息的值（m，w）返回給Proposer， Proposer收到多個(gè)Acceptors返回過(guò)來(lái)的消息之后，會(huì)從中選擇編號(hào)最大的一個(gè)消息所對(duì)應(yīng)的值z(mì)，并把他作為Accept請(qǐng)求的值（n，z）發(fā)給Acceptor。如果所有的Acceptors都沒(méi)有確認(rèn)過(guò)消息，那么Proposer可以自主選擇要確認(rèn)的值z(mì)。

• 階段 2b: Accepted
  當(dāng)Acceptor接收到了Proposer的確認(rèn)消息請(qǐng)求（n，z），如果該Acceptor在階段1b的時(shí)候沒(méi)有promise只接收>n的消息，那么該（n，z）消息就必須被Acceptor確認(rèn)。
  當(dāng)（n，z）消息被Acceptor確認(rèn)時(shí)，Acceptor會(huì)發(fā)送一個(gè)Accepted（n，z）消息給Proposer 和所有的Learner。當(dāng)然在大部分情況下Proposer和Learner這兩個(gè)角色可以合并。
  如果該Acceptor在階段1b的時(shí)候promise只接收>n的消息，那么該確認(rèn)請(qǐng)求消息會(huì)被拒絕或者忽略。
  按照以上的邏輯就會(huì)出現(xiàn)在一個(gè)輪次中，Acceptor 確認(rèn)多次消息的情況。什么情況下才會(huì)出現(xiàn)這樣的情況呢？ 我們舉個(gè)例子：
  Acceptor 收到Accept（n，z），然后返回了Accepted（n，z），接下來(lái)該Acceptor 又收到了Prepare（n+1)請(qǐng)求，按照階段1B的原則，Acceptor會(huì) Promise （n+1，z），然后Acceptor 收到Accept（n+1，z），最后返回Accepted（n+1，z）。大家可以看到盡管Acceptor 確認(rèn)了多次請(qǐng)求，但是最終會(huì)確保確認(rèn)的值是保持一致的。