引言
關(guān)于一致性的話(huà)題，在分布式領(lǐng)域算是一個(gè)殿堂級(jí)的課題撮弧。但從各種文章上看出大家對(duì)其理解比較模糊，大概都能說(shuō)出一些相關(guān)的概念姚糊，但都沒(méi)法完全解析清楚贿衍。本篇文章我將從一致性說(shuō)起，好好聊一聊對(duì)一致性概念的思考和理解救恨，然后引出paxos算法贸辈。
關(guān)于paxos算法，先給出幾個(gè)形容該算法的表述：
- Google Chubby的作者M(jìn)ike Burrows說(shuō)過(guò):這個(gè)世界上只有一種一致性算法肠槽，那就是Paxos
- 計(jì)算機(jī)分布式系統(tǒng)中號(hào)稱(chēng)最難理解的協(xié)議-Paxos
- Paxos的作者Leslie Lamport寫(xiě)了篇paper裙椭，因此獲得了圖靈獎(jiǎng)
可能大家對(duì)paxos不是很了解躏哩，而說(shuō)起raft都知道。因?yàn)閜axos的理論太抽象揉燃，無(wú)法很容易落地工程中扫尺，而raft作為multi paxos的一個(gè)應(yīng)用，其貢獻(xiàn)在于其一致性理論很好理解炊汤，落地又比較簡(jiǎn)單正驻，所以被大家所熟知。raft很好地解釋了HOW抢腐，但缺少WHY姑曙，而paxos從本質(zhì)上解釋了WHY。
本文從一致性的理論一步一步推導(dǎo)出paxos的核心理念迈倍，然后給出paxos的具體步驟（很多paxos的文章也只是談了這一步伤靠，并沒(méi)有給出理念）。
1. 一致性
一般我們?cè)谡務(wù)撘恢滦缘臅r(shí)候啼染，有的人會(huì)說(shuō)事務(wù)中的ACID中的C宴合，有的人會(huì)說(shuō)是分布式事務(wù)中的強(qiáng)一致性，有的人會(huì)說(shuō)是CAP理論上中C迹鹅，也有的人會(huì)說(shuō)是實(shí)現(xiàn)了paxos/raft算法的就是一致性結(jié)構(gòu)卦洽。很多人都會(huì)對(duì)一致性的理解都是模凌兩可的，拿這個(gè)一個(gè)領(lǐng)域內(nèi)的原理去解釋另一個(gè)領(lǐng)域的東西斜棚。
那今天我們來(lái)先好好說(shuō)一說(shuō)一致性這個(gè)問(wèn)題阀蒂。
在計(jì)算機(jī)軟件領(lǐng)域，我們談到一致性弟蚀，其實(shí)會(huì)涉及到三個(gè)領(lǐng)域：數(shù)據(jù)庫(kù)蚤霞，業(yè)務(wù)邏輯以及分布式。
在數(shù)據(jù)庫(kù)中义钉，一致性是指事務(wù)特性中ACID的C昧绣，在事務(wù)的開(kāi)始和結(jié)束以后，數(shù)據(jù)庫(kù)的一致性約束沒(méi)有被破壞断医。即以事務(wù)為單位，數(shù)據(jù)庫(kù)從一個(gè)一致性狀態(tài)變到另一個(gè)一致性狀態(tài)奏纪。
在業(yè)務(wù)邏輯中鉴嗤，通常一份邏輯數(shù)據(jù)，被拆分到不同的數(shù)據(jù)庫(kù)中甚至不同的系統(tǒng)中序调，我們沒(méi)有辦法使用本地事務(wù)來(lái)保證這份邏輯數(shù)據(jù)的原子性和一致性醉锅，這個(gè)時(shí)候通常可以借助分布式事務(wù)來(lái)解決发绢，或者其他一些可補(bǔ)償?shù)臋C(jī)制硬耍。通常這些一致性都維持在弱一致性（最終一致性）層面上垄琐。
在分布式系統(tǒng)中，一致性（強(qiáng)一致性）是指一份邏輯數(shù)據(jù)冗余存在多個(gè)物理副本中经柴，對(duì)其執(zhí)行讀寫(xiě)操作的表現(xiàn)行為是否一致的狸窘。這也符合CAP原理的闡述。（所以當(dāng)有人讓你舉例CP場(chǎng)景的時(shí)候坯认，千萬(wàn)別再拿銀行轉(zhuǎn)賬說(shuō)事了翻擒。）下面我們著重說(shuō)一下分布式系統(tǒng)的一致性理論。
2. 分布式一致性
上面我們說(shuō)到分布式系統(tǒng)一致性是指牛哺，一份邏輯數(shù)據(jù)冗余存在多個(gè)物理副本中陋气，對(duì)其執(zhí)行讀寫(xiě)操作的表現(xiàn)行為是否一致的。我們下面來(lái)好好解讀一下這句話(huà)引润。
首先巩趁，提問(wèn)一下，什么一份邏輯數(shù)據(jù)需要冗余存在多個(gè)物理副本中淳附？
核心點(diǎn)在于可用率议慰。我們知道一些牛逼的系統(tǒng)的可用率都很高，可以達(dá)到9個(gè)9（99.9999999%）燃观。這些牛逼的系統(tǒng)其實(shí)都是搭建在一些不那么可靠的硬件設(shè)施上褒脯。那提升可用率一個(gè)很明顯的做法就是冗余恢復(fù)，我使用多臺(tái)機(jī)器存在同一份數(shù)據(jù)缆毁，當(dāng)一臺(tái)機(jī)器出問(wèn)題后番川，我可以讀另一臺(tái)機(jī)器。假設(shè)一臺(tái)機(jī)器出問(wèn)題的概率是1%脊框，那兩臺(tái)都出問(wèn)題的概率就是1%*1%颁督，隨著機(jī)器的增加，都出問(wèn)題的概率越小浇雹，而從可用率得到有效提高沉御。
然后，再來(lái)看“對(duì)其執(zhí)行讀寫(xiě)操作的表現(xiàn)行為是否一致”這句話(huà)昭灵。
多副本的意思是說(shuō)同一份邏輯數(shù)據(jù)冗余在多個(gè)副本中吠裆，那么是否是說(shuō)所有副本每時(shí)每刻都必須數(shù)據(jù)完全一樣呢？
這個(gè)問(wèn)題的答案是顯然不需要的烂完。我們引入多副本的目的在于提高可用率试疙，即當(dāng)出現(xiàn)某幾臺(tái)機(jī)器掛掉，或者網(wǎng)絡(luò)不可達(dá)抠蚣，或者數(shù)據(jù)延遲的時(shí)候祝旷，副本集群仍然可以給出正確的讀寫(xiě)結(jié)果。
其實(shí)這里引出兩個(gè)概念：狀態(tài)視角的一致性和操作視角的一致性。
狀態(tài)視角的一致性是說(shuō)：所有副本的數(shù)據(jù)狀態(tài)在任何時(shí)刻都是一致的怀跛。
操作視角的一致性是說(shuō)：任何對(duì)副本集群的操作的結(jié)果是一致的距贷。
然后再來(lái)引申一下，當(dāng)多個(gè)副本中吻谋，因?yàn)橐恍┰颍ňW(wǎng)絡(luò)不可靠）出現(xiàn)數(shù)據(jù)狀態(tài)的不一致的時(shí)候忠蝗，整個(gè)副本集群可以通過(guò)自己的方式來(lái)對(duì)某個(gè)提議（操作）能夠達(dá)成統(tǒng)一的意見(jiàn)。這個(gè)概念就叫做共識(shí)滨溉。這里我們只是簡(jiǎn)單聊一下共識(shí)什湘，下面我們會(huì)詳細(xì)討論下這個(gè)問(wèn)題。
對(duì)晦攒，這里也解釋了闽撤，當(dāng)我們說(shuō)到paxos算法的時(shí)候，都說(shuō)他是一個(gè)共識(shí)算法的原因脯颜。
3. 復(fù)制算法
上面說(shuō)到一份邏輯數(shù)據(jù)冗余在多個(gè)副本中哟旗。如何冗余呢？
說(shuō)到底就是數(shù)據(jù)復(fù)制栋操，當(dāng)一個(gè)副本收到一個(gè)新數(shù)據(jù)的時(shí)候闸餐，將這個(gè)數(shù)據(jù)復(fù)制給其他副本的動(dòng)作。
下面我們來(lái)看一下常見(jiàn)的幾種復(fù)制算法從引出我們的paxos矾芙。
主從同步復(fù)制
原理很簡(jiǎn)單舍沙，所有的讀寫(xiě)交給主節(jié)點(diǎn)。當(dāng)主節(jié)點(diǎn)收到寫(xiě)操作時(shí)剔宪，必須同步復(fù)制給所有從節(jié)點(diǎn)拂铡，只有所有從節(jié)點(diǎn)都返回成功后，主節(jié)點(diǎn)才向客戶(hù)點(diǎn)返回成功葱绒。
這里的主從同步復(fù)制保證了上面提到的狀態(tài)視角的一致性感帅。
但是對(duì)于可用率來(lái)反而降低了。任何一個(gè)從節(jié)點(diǎn)失敗地淀，本次客戶(hù)端的請(qǐng)求就會(huì)失敗失球。
主從異步復(fù)制
原理上將也很簡(jiǎn)單，就是寫(xiě)請(qǐng)求只要寫(xiě)主節(jié)點(diǎn)就返回給客戶(hù)端成功帮毁。
然后從節(jié)點(diǎn)異步復(fù)制实苞。這也是MySQL binlog的復(fù)制策略。
異步復(fù)制解決了上面同步復(fù)制的可用率問(wèn)題烈疚，但是如果當(dāng)主節(jié)點(diǎn)寫(xiě)入成功到復(fù)制給從階段這段時(shí)間黔牵，主節(jié)點(diǎn)故障，這樣數(shù)據(jù)就丟失了胞得。
多數(shù)派讀寫(xiě)
我們既希望能保證可用率荧止，又希望能夠保證在部分機(jī)器掛的時(shí)候，不會(huì)數(shù)據(jù)丟失造成不一致阶剑。
那么思路就是寫(xiě)的時(shí)候跃巡，同步寫(xiě)一部分副本，其他副本異步去寫(xiě)牧愁。
這也就引出來(lái)多數(shù)派讀寫(xiě)素邪。
那么我們面臨的問(wèn)題是同步多多少個(gè)副本呢？讀的時(shí)候猪半？
如上圖所示兔朦，我們?cè)趺幢ＷC讀到就是剛才寫(xiě)入的副本呢？
這里就引入多數(shù)派讀寫(xiě)的理論磨确。
假設(shè)沽甥，我們有3個(gè)副本（一般副本數(shù)都是奇數(shù)，至于為什么乏奥，聰明的你肯定能想出來(lái)）摆舟，我們同步寫(xiě)2個(gè)，讀的時(shí)候邓了，如果一定到2個(gè)上都去讀恨诱，那么無(wú)論我們讀到的是哪2個(gè)，肯定至少能得到剛才同步寫(xiě)的一臺(tái)機(jī)器上骗炉。
即多數(shù)派寫(xiě)的機(jī)器和多數(shù)派讀機(jī)器的情況下照宝，一定有重復(fù)機(jī)器。
（n/2+1）+(n/2+1) > n句葵。
所以說(shuō)多數(shù)派讀寫(xiě)既有主從同步復(fù)制的數(shù)據(jù)一致性厕鹃，又有主從異步復(fù)制的可用率（因?yàn)橥綄?xiě)，只需要超過(guò)半數(shù)的機(jī)器的成功就同步返回成功了）笼呆。
4. 從多數(shù)派讀寫(xiě)引出paxos
版本號(hào)的引入
剛才說(shuō)了多數(shù)派讀寫(xiě)的基本原理熊响，首先會(huì)面臨一個(gè)問(wèn)題：
假設(shè)3副本集群中a的初始狀態(tài)是0，然后客戶(hù)端將a改為1诗赌。副本1和副本2此時(shí)a=1汗茄，副本3的a=0，然后客戶(hù)端進(jìn)行多數(shù)派讀铭若，讀到的是副本1和副本3洪碳，這樣到底a是0還是1呢？
解決這個(gè)問(wèn)題的辦法就是引入版本號(hào)叼屠。
當(dāng)寫(xiě)數(shù)據(jù)的時(shí)候瞳腌，將版本號(hào)+1，這樣镜雨，讀取的時(shí)候嫂侍，取版本號(hào)最大的那個(gè)。
共識(shí)問(wèn)題
當(dāng)我們引入版本號(hào)之后，其實(shí)還是會(huì)有問(wèn)題挑宠。
首先客戶(hù)端希望寫(xiě)入a1的值是1菲盾，然后當(dāng)進(jìn)行了多數(shù)派寫(xiě)后，還未返回客戶(hù)端結(jié)果時(shí)各淀，副本1宕機(jī)了懒鉴。這樣因?yàn)榭蛻?hù)端收不到任何response，就會(huì)進(jìn)行重試碎浇，那這次临谱，突然又想把a(bǔ)的值設(shè)置為2了。
然后這是就出現(xiàn)的問(wèn)題奴璃。版本號(hào)最大的是1悉默，但1這個(gè)版本號(hào)居然對(duì)應(yīng)了兩個(gè)值。無(wú)法決定應(yīng)該返回哪個(gè)值了苟穆。
我們把這個(gè)問(wèn)題擴(kuò)展引申一下麦牺，我們希望的是對(duì)同一件事（a1的更新）的多個(gè)提議，只能有一個(gè)提議被確認(rèn)鞭缭。
這里引申出一個(gè)很重要的概念：共識(shí)剖膳。
我們先來(lái)看一下共識(shí)的問(wèn)題域的定義：
Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If
no value is proposed, then no value should be chosen. If a value has been
chosen, then processes should be able to learn the chosen value. The safety
requirements for consensus are:
? Only a value that has been proposed may be chosen,
? Only a single value is chosen, and
? A process never learns that a value has been chosen unless it actually
has been.
We won’t try to specify precise liveness requirements. However, the goal is
to ensure that some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.
這里解讀一下，假設(shè)一個(gè)多節(jié)點(diǎn)的數(shù)據(jù)集群岭辣，每個(gè)節(jié)點(diǎn)都可以對(duì)同一件事進(jìn)行提議吱晒，共識(shí)算法的目標(biāo)是保證只會(huì)有一個(gè)提議被選擇。
即：
- 僅會(huì)有一個(gè)被提議的value被選擇沦童。
- 被選擇的提議將不會(huì)發(fā)生改變仑濒。
- 一旦某個(gè)提供被選擇，則任何一個(gè)節(jié)點(diǎn)最終都會(huì)學(xué)到這個(gè)被選擇的提議值偷遗。
5. 引入paxos算法
5.1 思想
那么為了達(dá)到這個(gè)目的墩瞳，我們應(yīng)該如何解決呢？
如果只有一個(gè)acceptor的話(huà)氏豌，其實(shí)這個(gè)問(wèn)題很好解決喉酌。第一個(gè)proposer提議后，拒絕后面所有的提議泵喘。有多個(gè)acceptor的話(huà)泪电，如果每次讀寫(xiě)都是對(duì)所有acceptor同步的話(huà)，這個(gè)問(wèn)題就變成了單個(gè)acceptor的問(wèn)題纪铺。但為了可用率相速，我們只允許每次讀寫(xiě)，多數(shù)派成功后就可以鲜锚。那應(yīng)該怎么辦呢突诬？
paxos里引入一個(gè)很有意思的理念：反向理念苫拍。即讓數(shù)據(jù)記住寫(xiě)入者。
paxos算法是通過(guò)引入兩階段的多數(shù)派讀寫(xiě)+數(shù)據(jù)記憶來(lái)實(shí)現(xiàn)旺隙。
增加一個(gè)階段的最主要目的為了讓副本上記住最后一個(gè)提議者怯疤。使得二階段的時(shí)候，副本只接受記錄到的最后一個(gè)提議者催束。
5.2 roles
這里引入paxos算法的幾個(gè)角色。一個(gè)副本節(jié)點(diǎn)可以同時(shí)擔(dān)當(dāng)幾個(gè)角色伏社，不會(huì)影響算法協(xié)議的正確性抠刺。
Client
表示發(fā)起請(qǐng)求給副本集群的客戶(hù)端。
Acceptor (Voters)
就是副本集群中的普通節(jié)點(diǎn)摘昌。超過(guò)半數(shù)的Acceptors are called Quorums
Proposer
是副本集群中的某個(gè)節(jié)點(diǎn)速妖，承接客戶(hù)端的請(qǐng)求以及發(fā)起提議。
Learner
與協(xié)議算法本身無(wú)關(guān)聪黎。當(dāng)一個(gè)值被確認(rèn)后罕容，發(fā)送給所有l(wèi)earner。learner用來(lái)對(duì)客戶(hù)端作出響應(yīng)稿饰。多數(shù)情況下锦秒，proposer也是一個(gè)learner。
目的為了提高可用率喉镰，可以增加learner的數(shù)量旅择。
5.3 具體過(guò)程
paxos的兩階段分為兩個(gè)步驟：prepare和accept
為了下面好理解，我們事先先定義幾個(gè)概念：
round：代表一個(gè)提議侣姆。
- proposer端：
round_num： 代表proposer發(fā)起一次提議標(biāo)識(shí)生真。這個(gè)值遞增。即每次發(fā)起提議時(shí)捺宗，這個(gè)值一定大于歷史上發(fā)起過(guò)的round_num柱蟀。- acceptor端
last_round_num：代表acceptor可以接受哪個(gè)proposer來(lái)寫(xiě)。
v：代表acceptor已經(jīng)寫(xiě)入的值
v_round_num：代表v寫(xiě)入的時(shí)候蚜厉，對(duì)應(yīng)的proposer的round_num
5.3.1 Phase 1
第一階段包括
Prepare過(guò)程
proposer向acceptor進(jìn)行提議长已，發(fā)送一個(gè)round_num，這個(gè)值遞增昼牛。即每次發(fā)起提議時(shí)痰哨，這個(gè)值一定大于歷史上發(fā)起過(guò)的round_num。
Promise過(guò)程
當(dāng)acceptor收到proposer的prepare請(qǐng)求后匾嘱，需要向proposer保證斤斧，我以后只會(huì)接受你的請(qǐng)求。
if (last_round_num > round_num) { // 代表本次提議round_num是一個(gè)老的了霎烙，直接拒絕
refuse;
}
set last_round_num = round_num; // 代表從現(xiàn)在開(kāi)始我只接受last_round_num的提議
return (last_round_num, v, v_round_num);
5.2.2 Phase 2
Accept過(guò)程
當(dāng)proposer收到多數(shù)派的acceptor的Promise返回值后撬讽，做出以下判斷：
if (v全部都是null){ // v從來(lái)沒(méi)有被設(shè)置過(guò)蕊连，那么我就設(shè)置自己想設(shè)置的值
set accept_value = want_set_v;
} else {
if (發(fā)現(xiàn)有一個(gè)的last_round_num要大于自己的round_num){// 本次提議為老提議
中斷本次提議;
}else {// 這一步又叫做修復(fù)。修復(fù)在Phase1的時(shí)候游昼，少數(shù)派的節(jié)點(diǎn)
從多個(gè)acceptor的返回值中挑一個(gè)最大的v_round_num對(duì)應(yīng)v
set accept_value = v; round_num = v_round_num;
}
}
send round_num, accept_value
總結(jié)一句話(huà)甘苍，當(dāng)發(fā)現(xiàn)有人已經(jīng)設(shè)置v了，則我也設(shè)置v烘豌，保持不變载庭。
如果都沒(méi)人設(shè)置v，那我就設(shè)置自己想設(shè)置的值廊佩。
這一步也是保證了
只會(huì)有一個(gè)提議被確認(rèn)的理論囚聚。
Accepted過(guò)程
當(dāng)acceptor收到proposer的Accept請(qǐng)求后，拒絕不等于last_round_num的請(qǐng)求标锄，然后更新v和v_round_num顽铸。
if (round_num != last_round_num) { //拒絕不等于last_round_num的請(qǐng)求。
refuse;
}else{
set v = accept_value;
set v_round_num = round_num;
}
5.4 看paxos如何解決有沖突的現(xiàn)象
以下這張圖解釋了發(fā)生了沖突的時(shí)候料皇，paxos是如何解決的谓松。
圖中已經(jīng)畫(huà)的很清楚了，就不做詳細(xì)解釋了践剂。
5.5 活鎖問(wèn)題
其實(shí)paxos是有一個(gè)可能存在活鎖的問(wèn)題的鬼譬。從上面我們知道當(dāng)某個(gè)proposer失敗后，它會(huì)遞增round_num進(jìn)行重試逊脯。
當(dāng)兩個(gè)proposer交替失敗后重試后拧簸，可能出現(xiàn)循環(huán)鎖的問(wèn)題，導(dǎo)致一直都沒(méi)法確認(rèn)值男窟。
如圖所示
6. 擴(kuò)展
我們上面說(shuō)的額paxos實(shí)際上是最樸實(shí)的classic paxos盆赤。
classic paxos一直以來(lái)被詬病的地方是說(shuō)，一次寫(xiě)入歉眷，需要兩次rpc牺六，影響效率。
所以L(fǎng)eslie Lamport老爺子對(duì)paxos進(jìn)行了優(yōu)化, multi paxso和fast paxos汗捡。
multi paxso
我們引入另一個(gè)角色：leader淑际。
所有的提議都由leader來(lái)做，如果leader相對(duì)穩(wěn)定的話(huà)扇住。其實(shí)我們可以不要classic paxos中的第一階段春缕。
前面我們說(shuō)過(guò)，第一階段的一個(gè)最主要的目的是數(shù)據(jù)記憶艘蹋，即我只允許你來(lái)修改我的值锄贼。那如果都是由leader來(lái)提議的話(huà)创坞，第一階段可以省略的炉峰。
如果省略，那round_num怎么搞的？
在實(shí)際應(yīng)用中铐望，我們一般都是對(duì)一組連續(xù)的value進(jìn)行提議奏司。
所以假設(shè)我們第一次提議的時(shí)候窄坦，兩階段妄辩，使用的round_num是N。那么后續(xù)直接使用N+1就可以了惫确。這樣后續(xù)的提議就只需要第二階段就可以了手报。
而且，因?yàn)槲覀兌际鞘褂胠eader來(lái)提議改化，也解決了上面提到的活鎖的問(wèn)題掩蛤。
我們熟知的raft，其核心就是multi paxos的一個(gè)應(yīng)用所袁。之所以raft比paxos流行的原因是因?yàn)閞aft的描述額更佳直白，更加工程化凶掰。
chubby燥爷，zookeeper，spanner等著名應(yīng)用都是使用multi paxso協(xié)議的一些擴(kuò)展懦窘。
fast paxso
沒(méi)沖突：1輪rpc
有沖突：2輪rpc
意思就是說(shuō)先直接進(jìn)行第2次rpc寫(xiě)入看看前翎，如果發(fā)現(xiàn)失敗（多數(shù)派寫(xiě)入的時(shí)候副本的可接受的客戶(hù)端不是本次請(qǐng)求的客戶(hù)端）畅涂，就會(huì)退化為class paxos港华。如果成功就成功了。
有點(diǎn)類(lèi)似于JAVA中的偏向鎖的概念午衰。
參考文檔：
https://blog.openacid.com/algo/paxos/
http://www.lamport.org/
http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos
