在理解分布式一致性:Raft協(xié)議中们衙，我們詳細分析了什么是分布式一致性和實現(xiàn)分布式一致性的Raft協(xié)議揖赴，本文我們主要講一下分布式一致性的Paxos協(xié)議。
大家可能在各個場合都聽說過Paxos協(xié)議，畢竟這個開創(chuàng)性的協(xié)議是很多分布式協(xié)議的鼻祖慕的，比如后面比較有名的Raft協(xié)議就是基于Paxos協(xié)議發(fā)展而來的。現(xiàn)實中也有很多產(chǎn)品在使用Paxos協(xié)議挤渔，像是Google的Chubby肮街，Spanner，IBM的SVC等判导。 但是在筆者的學(xué)習(xí)過程中嫉父，發(fā)現(xiàn)介紹Paxos協(xié)議的很多，但是真正能把它講明白的卻很少眼刃。所以筆者特意花了一定的時間來研究Paxos協(xié)議绕辖，現(xiàn)把學(xué)習(xí)結(jié)果分析如下。
其實Paxos的作者Leslie Lamport早在2001年就寫過一篇Paxos Made Simple的論文擂红，來盡可能的簡化Paxos的描述仪际。大家可以在Paxos Made Simple獲取作者的這篇論文。
角色
在Paxos協(xié)議中存在5種角色: client, acceptor, proposer, learner, 和 leader昵骤。但在實際的實現(xiàn)中树碱，一個服務(wù)可能同時扮演一個或者多個角色，這樣做的考慮是為了減少消息延遲和消息數(shù)量变秦，提升整個Paxos協(xié)議的工作效率成榜。
Client Client 是指請求的發(fā)起端，Client發(fā)送請求給分布式系統(tǒng)蹦玫，并等待回復(fù)伦连。
Acceptor (Voters) Acceptor 可以看做是消息請求的存儲器。一般來說Acceptors是由一定數(shù)量的服務(wù)組成的钳垮，當消息被發(fā)送給Acceptor惑淳， 只有大部分Acceptor確認接收此消息，該消息才會被存儲饺窿，否則該消息將被丟棄歧焦。
Proposer Proposer 可以看做Client的代理人，Proposer將Client的消息請求發(fā)送給Acceptors，并等待Acceptors的確認绢馍。在發(fā)生消息沖突時向瓷，Proposer將會嘗試解決沖突。
Learner Learners可以看做是所有被確認消息的執(zhí)行器舰涌，一旦有Client的消息請求被Acceptors確認之后猖任，Learners會做相應(yīng)的處理（如：執(zhí)行消息內(nèi)容，發(fā)送回復(fù)給Client）瓷耙。Learner可以有多個朱躺。
Leader Paxos需要一個Leader來確保分布式系統(tǒng)可以按步驟進行下去。這里的Leader其實就是一個Proposer, Paxos協(xié)議會確保只有一個Proposer會被當做Leader搁痛。
Proposal Number & Agreed Value
Proposal Number 也叫提案編號长搀，我們用n表示，對于每一個Proposer來說鸡典，每一個提案編號都是唯一的源请。 Agreed Value也叫確認值，我們用v來表示彻况，v是Acceptors確認的值谁尸。 兩個值組合起來就是（n，v）纽甘。
Basic Paxos
Paxos協(xié)議有很多變種良蛮，這里我們首先介紹一下Basis Paxos，后面的文章我們會繼續(xù)介紹其他的Paxos協(xié)議贷腕。當然背镇，既然是基礎(chǔ)的Paxos協(xié)議，搞懂了它泽裳，對于其他的Paxos協(xié)議自然手到擒來瞒斩。
在Basic Paxos 協(xié)議中，有很多次的執(zhí)行過程涮总，每次執(zhí)行過程產(chǎn)生一個單獨的執(zhí)行結(jié)果胸囱。每次執(zhí)行過程都有很多輪次，每一輪都有2個階段瀑梗。
階段1
階段1A：Prepare
在Prepare階段烹笔，一個Proposer會創(chuàng)建一個Prepare消息，每個Prepare消息都有唯一的提案編號n抛丽。n并不是將要提案的內(nèi)容谤职，而只是一個唯一的編號，用來標志這個Prepare的消息亿鲜。 n必須比該Proposer之前用過的所有編號都大允蜈，一般來說我們可以以數(shù)字遞增的方式來實現(xiàn)這個編號。 接下來Proposer會把該編號發(fā)送給Acceptors，只有大多數(shù)Acceptors接收到Proposer發(fā)來的消息饶套，該消息才算是發(fā)送成功漩蟆。-
階段1B：Promise
所有的Acceptors都在等待從Proposers發(fā)過來的Prepare消息。當一個Acceptor收到從Proposer發(fā)過來的Prepare消息時候妓蛮，會有兩種情況：- 該消息中的n是Acceptor所有收到的Prepare消息中最大的一個怠李，那么該Acceptor必須返回一個Promise消息給Proposer，告訴它后面所有小于n的消息我都會忽略掉蛤克。如果該Acceptor在過去的某個時間已經(jīng)確認了某個消息捺癞，那么它必須返回那個消息的proposal number m 和 accepted value w （m，w）咖耘。如果該Acceptor在過去并沒有確認過任何消息翘簇，那么會返回NULL撬码。
- 如果Prepare消息中的n小于該Acceptor之前接收到的消息儿倒，那么該消息會被Acceptor忽略（為了優(yōu)化也可以返回一個拒絕消息給Proposer，告訴它不要再發(fā)小于n的消息給我了）呜笑。
階段2
- 階段2A：Accept
如果一個Proposer從Acceptors接收到了足夠多的Promises（>n/2）夫否，這表示該Proposer可以開始下一個Accept請求的階段了，在Accept階段叫胁，Proposer需要設(shè)置一個值凰慈，然后向Acceptors發(fā)送Accept請求。 在階段1B我們講到了驼鹅，如果Acceptor之前確認過消息微谓，那么會把該消息編號和消息的值（m，w）返回給Proposer输钩， Proposer收到多個Acceptors返回過來的消息之后豺型，會從中選擇編號最大的一個消息所對應(yīng)的值z，并把他作為Accept請求的值（n买乃，z）發(fā)給Acceptor姻氨。如果所有的Acceptors都沒有確認過消息，那么Proposer可以自主選擇要確認的值z剪验。 - 階段 2b: Accepted
當Acceptor接收到了Proposer的確認消息請求（n肴焊，z），如果該Acceptor在階段1b的時候沒有promise只接收>n的消息功戚，那么該（n娶眷，z）消息就必須被Acceptor確認。 當（n啸臀，z）消息被Acceptor確認時届宠，Acceptor會發(fā)送一個Accepted（n，z）消息給Proposer 和所有的Learner。當然在大部分情況下Proposer和Learner這兩個角色可以合并席揽。
如果該Acceptor在階段1b的時候promise只接收>n的消息顽馋，那么該確認請求消息會被拒絕或者忽略。
按照以上的邏輯就會出現(xiàn)在一個輪次中幌羞，Acceptor 確認多次消息的情況寸谜。什么情況下才會出現(xiàn)這樣的情況呢？ 我們舉個例子：
Acceptor 收到Accept（n属桦，z）熊痴，然后返回了Accepted（n，z）聂宾，接下來該Acceptor 又收到了Prepare（n+1)請求果善，按照階段1B的原則，Acceptor會 Promise （n+1系谐，z）巾陕，然后Acceptor 收到Accept（n+1，z）纪他，最后返回Accepted（n+1鄙煤，z）。大家可以看到盡管Acceptor 確認了多次請求茶袒，但是最終會確保確認的值是保持一致的梯刚。
下面我們會用序列圖的方式形象的描述Basis Paxos中可能出現(xiàn)的各種情況。
Basic Paxos without failures
在該序列圖中薪寓，有1個Client亡资，3個Acceptors和1個Learner，該圖表示的是在第一輪執(zhí)行過程中就成功的例子向叉。
在第一輪就成功只是Paxos協(xié)議中一部分情況锥腻，其實在真實的世界中由于網(wǎng)絡(luò)，系統(tǒng)等各種原因會造成多種情況的意外植康，最后導(dǎo)致協(xié)議往往并不能在第一輪就成功旷太，往往需要經(jīng)歷好幾輪。
Basic Paxos when an Acceptor fails
如果有一個Acceptor因為各種原因掛掉了销睁，3個Acceptors變成了2個Acceptors供璧，還是滿足>n/2 的要求，所以還是會成功冻记。
Basic Paxos when an Proposer fails
如果Proposer 在發(fā)送了一條Accept消息之后睡毒，但是還沒收到Accepted消息之前就掛掉了，只有一個Acceptor接收到了Accept消息冗栗。那么整個Paxos協(xié)議就沒法進行下去了演顾，這時一個新的Leader（Proposer）會被選舉出來供搀，重新開始一輪新的共識。
Basic Paxos when multiple Proposers conflict
最后再描述一個最復(fù)雜的情況钠至，即有多個Proposers認為他們是Leaders葛虐，并不斷的發(fā)送Prepare請求。為什么會有多個Leaders呢？ 有可能一個Proposer當了一段時間Leader之后掛掉了，新的Proposer被選為Leader繼續(xù)新的一輪共識拉馋。后面掛掉的Proposer又恢復(fù)了，它認為自己還是Leader牙勘，所以繼續(xù)發(fā)送Prepare請求。
本次的Basic Paxos協(xié)議就介紹到這里。后面我們會繼續(xù)介紹Paxos的其他變種。
