可靠分布式系統(tǒng)-paxos的直觀解釋
https://mp.weixin.qq.com/s/3OZgqEWQcEf6V9v6eoSUUA
本文鏈接: [https://blog.openacid.com/algo/paxos/]
前言
paxos是什么?
在分布式系統(tǒng)中保證多副本數(shù)據(jù)強一致的算法.
paxos有啥用?
沒有paxos的一堆機器, 叫做分布式;
有paxos協(xié)同的一堆機器, 叫分布式系統(tǒng).
Google Chubby的作者Mike Burrows說過:
這個世界上只有一種一致性算法，那就是Paxos …
其他一致性算法, 都可以看做paxos在實現(xiàn)中的變體和擴展.
另外一個經(jīng)常被提及的分布式算法是[raft], raft的貢獻在于把一致性算法落地. 因為 [Leslie Lamport] 的理論很抽象, 要想把他的理論應(yīng)用到現(xiàn)實中, 還需要工程師完全掌握他的理論再添加工程必要的環(huán)節(jié)才能跑起來.
經(jīng)常有人問起raft和paxos的區(qū)別, 或在實現(xiàn)中應(yīng)該選擇哪個, 在不了解paxos之前可能會有這種疑問. 對于這個問題, 就像是被問及四則運算和算盤有什么區(qū)別, 小店老板應(yīng)該使用四則運算還是用算盤結(jié)賬一樣.
記得 Leslie Lamport 2015年時來了一次北京, 那時會場上有人也問了老爺子 paxos和raft有啥區(qū)別.
老爺子當(dāng)時給出的回答是: 沒聽過raft…
raft的核心可以認為是multi paxos的一個應(yīng)用, 對于要掌握一致性算法的核心內(nèi)容, 從paxos入手, 更容易去掉無關(guān)干擾, 直達問題本質(zhì). 所以我們選擇paxos作為了解一致性算法的入口, 聊開了聊透了.
網(wǎng)絡(luò)上raft比paxos流行, 因為raft的描述更直白一些, 實際上raft比paxos更復(fù)雜. raft詳細的解釋了”HOW”, 缺少”WHY”的解釋. paxos從根本上解釋清楚了”WHY”, 但一直缺少一份通俗易懂的教程. 以至于沒有被更廣泛的接受. 所以就有了本文, 一篇paxos入門教程, 從基本的分布式中的復(fù)制的問題出發(fā), 通過逐步解決和完善這幾個問題, 最后推導(dǎo)出paxos的算法.
本文分為2個部分:
前1部分是分布式一致性問題的討論和解決方案的逐步完善, 用人話得出paxos算法的過程. 如果只希望理解paxos而不打算花太多時間深入細節(jié), 只閱讀這1部分就可以啦.
第2部分是paxos算法和協(xié)議的嚴格描述. 這部分可以作為paxos原paper的實現(xiàn)部分的概括. 如果你打算實現(xiàn)自己的paxos或類似協(xié)議, 需要仔細了解協(xié)議細節(jié), 希望這部分內(nèi)容可以幫你節(jié)省閱讀原paper的時間.
圖片是xp之前做過的paxos分享使用的slides, 在此基礎(chǔ)上加入了更多口頭解釋的內(nèi)容.
分布式系統(tǒng)要解決的問題
slide-00
slide-01
paxos的工作, 就是把一堆運行的機器協(xié)同起來, 讓多個機器成為一個整體系統(tǒng). 在這個系統(tǒng)中, 每個機器都必須讓系統(tǒng)中的狀態(tài)達成一致, 例如三副本集群如果一個機器上上傳了一張圖片, 那么另外2臺機器上也必須復(fù)制這張圖片過來, 整個系統(tǒng)才處于一個一致的狀態(tài).
slide-02
我是無需解釋的目錄頁.?
slide-03
分布式系統(tǒng)的一致性問題最終都歸結(jié)為分布式存儲的一致性. 像aws的對象存儲可靠性要求是9~13個9. 而這么高的可靠性都是建立在可靠性沒那么高的硬件上的.
slide-04
幾乎所有的分布式存儲(甚至單機系統(tǒng), 參考[EC第一篇:原理], [EC第二篇:實現(xiàn)], [EC第三篇:極限]) 都必須用某種冗余的方式在廉價硬件的基礎(chǔ)上搭建高可靠的存儲. 而冗余的基礎(chǔ)就是多副本策略, 一份數(shù)據(jù)存多份. 多副本保證了可靠性, 而副本之間的一致, 就需要paxos這類分布式一致性算法來保證.
slide-05
在早些年各種各樣的復(fù)制策略都被提出來來解決各種場景下的需要. 除了復(fù)制的份數(shù)之外, 各種各樣的算法實際上都是在嘗試解決一致的問題. 從下一頁開始簡單回顧下各種復(fù)制策略, 看看他們的優(yōu)缺點以及paxos如何解決副本之間一致性的問題.
不太完美的復(fù)制策略
slide-06
無需解釋的目錄頁?
slide-07
主從異步復(fù)制是最簡單的策略之一, 它很容易實現(xiàn), 但存在一個問題: 客戶端收到一個數(shù)據(jù)已經(jīng)安全(OK)的信息, 跟數(shù)據(jù)真正安全(數(shù)據(jù)復(fù)制到全部的機器上)在時間上有一個空隙, 這段時間負責(zé)接收客戶端請求的那個機器(master)如果被閃電擊中或被隕石砸到或被打掃衛(wèi)生的大姐踢斷了電源, 那數(shù)據(jù)就可能會丟失. 因此它不是一個可靠的復(fù)制策略(使用主從異步復(fù)制要求你必須相信宇宙中不存在閃電隕石和掃地大姐).
slide-08
跟主從異步復(fù)制相比,?主從同步復(fù)制提供了完整的可靠性: 直到數(shù)據(jù)真的安全的復(fù)制到全部的機器上之后, master才告知客戶端數(shù)據(jù)已經(jīng)安全.
但主從同步復(fù)制有個致命的缺點就是整個系統(tǒng)中有任何一個機器宕機, 寫入就進行不下去了. 相當(dāng)于系統(tǒng)的可用性隨著副本數(shù)量指數(shù)降低.
slide-09
然鵝, 在同步和異步之間, 做一個折中, 看起來是一個不錯的方案. 這就是半同步復(fù)制. 它要求master在應(yīng)答客戶端之前必須把數(shù)據(jù)復(fù)制到足夠多的機器上, 但不需要是全部.?這樣副本數(shù)夠多可以提供比較高的可靠性; 1臺機器宕機也不會讓整個系統(tǒng)停止寫入.
但是它還是不完美, 例如數(shù)據(jù)a復(fù)制到slave-1, 但沒有到達slave-2; 數(shù)據(jù)b復(fù)制達到了slave-2但沒有到達slave-1, 這時如果master掛掉了需要從某個slave恢復(fù)出數(shù)據(jù), 任何一個slave都不能提供完整的數(shù)據(jù). 所以在整個系統(tǒng)中, 數(shù)據(jù)存在某種不一致.
slide-10
為了解決半同步復(fù)制中數(shù)據(jù)不一致的問題, 可以將這個復(fù)制策略再做一改進:?多數(shù)派讀寫: 每條數(shù)據(jù)必須寫入到半數(shù)以上的機器上. 每次讀取數(shù)據(jù)都必須檢查半數(shù)以上的機器上是否有這條數(shù)據(jù).
在這種策略下, 數(shù)據(jù)可靠性足夠, 宕機容忍足夠, 任一機器故障也能讀到全部數(shù)據(jù).
slide-11
然鵝多數(shù)派讀寫的策略也有個但是, 就是對于一條數(shù)據(jù)的更新時, 會產(chǎn)生不一致的狀態(tài). 例如:
node-1, node-2都寫入了a=x,
下一次更新時node-2, node-3寫入了a=y.
這時, 一個要進行讀取a的客戶端如果聯(lián)系到了node-1和node-2, 它將看到2條不同的數(shù)據(jù).
為了不產(chǎn)生歧義, 多數(shù)派讀寫還必須給每筆寫入增加一個全局遞增的時間戳. 更大時間戳的記錄如果被看見, 就應(yīng)該忽略小時間戳的記錄. 這樣在讀取過程中, 客戶端就會看到a=x?, a=y? 這2條數(shù)據(jù), 通過比較時間戳1和2, 發(fā)現(xiàn)y是更新的數(shù)據(jù), 所以忽略a=x?. 這樣保證多次更新一條數(shù)據(jù)不產(chǎn)生歧義.
slide-12
是的,?但是又來了. 這種帶時間戳的多數(shù)派讀寫依然有問題. 就是在客戶端沒有完成一次完整的多數(shù)派寫的時候: 例如, 上面的例子中寫入, a=x?寫入了node-1和node-2, a=y?時只有node-3 寫成功了, 然后客戶端進程就掛掉了, 留下系統(tǒng)中的狀態(tài)如下:
這時另一個讀取的客戶端來了,
如果它聯(lián)系到node-1和node-2, 那它得到的結(jié)果是a=x?.
如果它聯(lián)系到node-2和node-3, 那它得到的結(jié)果是a=y?.
整個系統(tǒng)對外部提供的信息仍然是不一致的.
slide-13
現(xiàn)在我們已經(jīng)非常接近最終奧義了, paxos可以認為是多數(shù)派讀寫的進一步升級, paxos中通過2次原本并不嚴謹?shù)亩鄶?shù)派讀寫, 實現(xiàn)了嚴謹?shù)膹娨恢耤onsensus算法.
從多數(shù)派讀寫到paxos的推導(dǎo)
slide-14
首先為了清晰的呈現(xiàn)出分布式系統(tǒng)中的核心問題: 一致性問題, 我們先設(shè)定一個假象的存儲系統(tǒng), 在這個系統(tǒng)上, 我們來逐步實現(xiàn)一個強一致的存儲, 就得到了paxos對一致性問題的解決方法.
slide-15
在實現(xiàn)中, set命令直接實現(xiàn)為一個多數(shù)派寫, 這一步非常簡單. 而inc操作邏輯上也很簡單, 讀取一個變量的值i?, 給它加上一個數(shù)字得到i?, 再通過多數(shù)派把i?寫回到系統(tǒng)中.
slide-16
冰雪如你一定已經(jīng)看到了這種實現(xiàn)方式中的問題: 如果有2個并發(fā)的客戶端進程同時做這個inc的操作, 在多數(shù)派讀寫的實現(xiàn)中, 必然會產(chǎn)生一個Y客戶端覆蓋X客戶端的問題. 從而產(chǎn)生了數(shù)據(jù)更新點的丟失.
而paxos就是為了解決這類問題提出的, 它需要讓Y能檢測到這種并發(fā)沖突, 進而采取措施避免更新丟失.
slide-17
提取一下上面提到的問題: 讓Y去更新的時候不能直接更新i?, 而是應(yīng)該能檢測到i?的存在, 進而將自己的結(jié)果保存在下一個版本i?中, 再寫回系統(tǒng)中.
而這個問題可以轉(zhuǎn)化成: i的每個版本只能被寫入一次, 不允許修改. 如果系統(tǒng)設(shè)計能滿足這個要求, 那么X和Y的inc操作就都可以正確被執(zhí)行了.
slide-18
于是我們的問題就轉(zhuǎn)化成一個更簡單, 更基礎(chǔ)的問題: 如何確定一個值(例如i?)已經(jīng)被寫入了.
直觀來看, 解決方法也很簡單, 在X或Y寫之前先做一次多數(shù)派讀, 以便確認是否有其他客戶端進程已經(jīng)在寫了, 如果有, 則放棄.
slide-19
但是!!!, 這里還有個并發(fā)問題, X和Y可能同時做這個寫前讀取的操作, 并且同時得出一個結(jié)論: 還沒有其他進程在寫入, 我可以寫. 這樣還是會造成更新丟失的問題.
slide-20
為了解決上面的問題, 存儲節(jié)點還需要增加一個功能, 就是它必須記住誰最后一個做過寫前讀取的操作. 并且只允許最后一個完成寫前讀取的進程可以進行后續(xù)寫入, 同時拒絕之前做過寫前讀取的進程寫入的權(quán)限.
可以看到, 如果每個節(jié)點都記得誰讀過, 那么當(dāng)Y最后完成了寫前讀取的操作后, 整個系統(tǒng)就可以阻止過期的X的寫入.
這個方法之所以能工作也是因為多數(shù)派寫中, 一個系統(tǒng)最多只能允許一個多數(shù)派寫成功. paxos也是通過2次多數(shù)派讀寫來實現(xiàn)的強一致.
slide-21
以上就是paxos算法的全部核心思想了, 是不是很簡單? 剩下的就是如何實現(xiàn)的簡單問題了: 如何標識一個客戶端如X和Y, 如何確認誰是最后一個完成寫前讀寫的進程, 等等.
slide-22
[Leslie Lamport] 就這么把這么簡單的一個算法寫了個paper就獲得了圖領(lǐng)獎! 騷年, 改變世界就這么容易!
paxos算法描述
接下來的篇幅中我們將用計算機的語言準確的描述整個paxos運行的過程.
slide-23
首先明確要解決的問題:
slide-24
我們要介紹的paxos實際上是最樸實的classic paxos, 在這之后我們順提下幾個老爺子對paxos的優(yōu)化, multi paxso和fast paxos, 它們都是針對paxos的理論層面的優(yōu)化.
slide-25
paxos算法中解決了如何在不可靠硬件基礎(chǔ)上構(gòu)建一個可靠的分布式系統(tǒng)的方法. 但paxos核心算法中只解決網(wǎng)絡(luò)延遲/亂序的問題, 它不試圖解決存儲不可靠和消息錯誤的問題, 因為這兩類問題本質(zhì)上跟分布式關(guān)系不大, 屬于數(shù)據(jù)校驗層面的事情.
有興趣可以參考 [Byzantine Paxos] 的介紹.
slide-26
本文盡量按照 [Classic Paxos] 的術(shù)語來描述,
老爺子后面的一篇 [Fast Paxos] 實現(xiàn)了fast-paxos, 同時包含了classic-paxos, 但使用了一些不同的術(shù)語表示.
Proposer 可以理解為客戶端.
Acceptor 可以理解為存儲節(jié)點.
Quorum 在99%的場景里都是指多數(shù)派, 也就是半數(shù)以上的Acceptor.
Round 用來標識一次paxos算法實例, 每個round是2次多數(shù)派讀寫: 算法描述里分別用phase-1和phase-2標識. 同時為了簡單和明確, 算法中也規(guī)定了每個Proposer都必須生成全局單調(diào)遞增的round, 這樣round既能用來區(qū)分先后也能用來區(qū)分不同的Proposer(客戶端).
slide-27
在存儲端(Acceptor)也有幾個概念:
last_rnd 是Acceptor記住的最后一次進行寫前讀取的Proposer(客戶端)是誰, 以此來決定誰可以在后面真正把一個值寫到存儲中.
v 是最后被寫入的值.
vrnd 跟v是一對, 它記錄了在哪個Round中v被寫入了.
v和vrnd是用于恢復(fù)一次未完成的paxos用的. 一次未完成的paxos算法運行可能留下一些沒有達到多數(shù)派的值的寫入(就像原生的多數(shù)派寫的臟讀的問題), paxos中通過vrnd來決定哪些值是最后寫入的, 并決定恢復(fù)哪個未完成的paxos運行. 后面我們會通過幾個例子來描述vrnd的作用.
slide-28
首先是paxos的phase-1, 它相當(dāng)于之前提到的寫前讀取過程. 它用來在存儲節(jié)點(Acceptor)上記錄一個標識: 我后面要寫入; 并從Acceptor上讀出是否有之前未完成的paxos運行. 如果有則嘗試恢復(fù)它; 如果沒有則繼續(xù)做自己想做的事情.
我們用類似yaml的格式來描述phase-1的請求/應(yīng)答的格式:
phase-1成功后, acceptor應(yīng)該記錄X的rnd=1, 并返回自己之前保存的v和vrnd.
slide-29
Proposer X收到多數(shù)(quorum)個應(yīng)答, 就認為是可以繼續(xù)運行的.如果沒有聯(lián)系到多于半數(shù)的acceptor, 整個系統(tǒng)就hang住了, 這也是paxos聲稱的只能運行少于半數(shù)的節(jié)點失效.
這時Proposer面臨2種情況:
所有應(yīng)答中都沒有任何非空的v, 這表示系統(tǒng)之前是干凈的, 沒有任何值已經(jīng)被其他paxos客戶端完成了寫入(因為一個多數(shù)派讀一定會看到一個多數(shù)派寫的結(jié)果). 這時Proposer X繼續(xù)將它要寫的值在phase-2中真正寫入到多于半數(shù)的Acceptor中.
如果收到了某個應(yīng)答包含被寫入的v和vrnd, 這時, Proposer X 必須假設(shè)有其他客戶端(Proposer) 正在運行, 雖然X不知道對方是否已經(jīng)成功結(jié)束, 但任何已經(jīng)寫入的值都不能被修改!, 所以X必須保持原有的值. 于是X將看到的最大vrnd對應(yīng)的v作為X的phase-2將要寫入的值.
這時實際上可以認為X執(zhí)行了一次(不知是否已經(jīng)中斷的)其他客戶端(Proposer)的修復(fù).
slide-30
在第2階段phase-2, Proposer X將它選定的值寫入到Acceptor中, 這個值可能是它自己要寫入的值, 或者是它從某個Acceptor上讀到的v(修復(fù)).
同樣用類似yaml的方式描述請求應(yīng)答:
slide-31
當(dāng)然這時(在X收到phase-1應(yīng)答, 到發(fā)送phase-2請求的這段時間), 可能已經(jīng)有其他Proposer又完成了一個rnd更大的phase-1, 所以這時X不一定能成功運行完phase-2.
Acceptor通過比較phase-2請求中的rnd, 和自己本地記錄的rnd, 來確定X是否還有權(quán)寫入. 如果請求中的rnd和Acceptor本地記錄的rnd一樣, 那么這次寫入就是被允許的, Acceptor將v寫入本地, 并將phase-2請求中的rnd記錄到本地的vrnd中.
用例子看paxos運行
好了paxos的算法描述也介紹完了. 這些抽象的算法描述, 其中的規(guī)則覆蓋了實際所有可能遇到的情況的處理方式. 一次不太容易看清楚它們的作用, 所以我們接下來通過幾個例子來看看paxos如何處理各種不同狀態(tài)并最終使整個系統(tǒng)的狀態(tài)達成一致.
slide-32
沒沖突的例子不解釋了?
slide-33
X和Y同時運行paxos, Y迫使X中斷的例子:
X成功完成了寫前讀取(phase-1), 將rnd=1寫入到左邊2個Acceptor.
Y用更大的rnd=2, 覆蓋了X的rnd, 將rnd=2寫入到右邊2個Acceptor.
X以為自己還能運行phase-2, 但已經(jīng)不行了, X只能對最左邊的Acceptor成功運行phase-2, 而中間的Acceptor拒絕了X的phase-2.
Y對右邊2個Acceptor成功運行了phase-2, 完成寫入v=y, vrnd=2.
slide-34
繼續(xù)上面的例子, 看X如何處理被搶走寫入權(quán)的情況:
這時X的phase-2沒成功, 它需要重新來一遍, 用更大的rnd=3.
X成功在左邊2個Acceptor上運行phase-1之后, X發(fā)現(xiàn)了2個被寫入的值: v=x, vrnd=1 和 v=y, vrnd=2; 這時X就不能再寫入自己想要寫入的值了. 它這次paxos運行必須不能修改已存在的值, 這次X的paxos的運行唯一能做的就是, 修復(fù)(可能)已經(jīng)中斷的其他proposer的運行.
這里v=y, vrnd=2 是可能在phase-2達到多數(shù)派的值. v=x, vrnd=1不可能是, 因為其他proposer也必須遵守算法約定, 如果v=x, vrnd=1在某個phase-2達到多數(shù)派了, Y一定能在phase-1中看到它, 從而不會寫入v=y, vrnd=2.
因此這是X選擇v=y, 并使用rnd=3繼續(xù)運行, 最終把v=y, vrnd=3寫入到所有Acceptor中.
slide-35
Paxos 還有一個不太重要的角色Learner, 是為了讓系統(tǒng)完整加入的, 但并不是整個算法執(zhí)行的關(guān)鍵角色, 只有在最后在被通知一下.
Paxos 優(yōu)化
slide-36
第一個優(yōu)化?multi-paxos:
paxos誕生之初為人詬病的一個方面就是每寫入一個值就需要2輪rpc:phase-1和phase-2. 因此一個尋常的優(yōu)化就是用一次rpc為多個paxos實例運行phase-1.
例如, Proposer X可以一次性為i?~i??這10個值, 運行phase-1, 例如為這10個paxos實例選擇rnd為1001, 1002…1010. 這樣就可以節(jié)省下9次rpc, 而所有的寫入平均下來只需要1個rpc就可以完成了.
這么看起來就有點像raft了:
再加上commit概念(commit可以理解為: 值v送達到多數(shù)派這件事情是否送達到多數(shù)派了),
和組成員變更(將quorum的定義從”多于半數(shù)”擴展到”任意2個quourm必須有交集”).
slide-37
第二個優(yōu)化?fast-paxos:
fast-paxos通過增加quorum的數(shù)量來達到一次rpc就能達成一致的目的. 如果fast-paxos沒能在一次rpc達成一致, 則要退化到classic paxos.
slide-38
fast-paxos為了能在退化成classic paxos時不會選擇不同的值, 就必須擴大quorum的值. 也就是說fast-round時, quorum的大小跟classic paxos的大小不一樣. 同樣我們先來看看為什么fast-quorum不能跟classic-quorum一樣, 這樣的配置會引起classic階段回復(fù)時選擇錯誤的值 y?:
slide-39
要解決這個問題, 最粗暴的方法是把fast-quorum設(shè)置為n, 也就是全部的acceptor都寫入成功才認為fast-round成功(實際上是退化到了主從同步復(fù)制). 這樣, 如果X和Y兩個proposer并發(fā)寫入, 誰也不會成功, 因此X和Y都退化到classic paxos進行修復(fù), 選任何值去修復(fù)都沒問題. 因為之前沒有Proposer認為自己成功寫入了.
如果再把問題深入下, 可以得出, 如果classic paxos的quorum是n/2+1, 那么fast-round的quorum應(yīng)該是大于?n, ?的由來可以簡單理解為: 在最差情況下, 達到fast-quorum的acceptor在classic-quorum中必須大于半數(shù), 才不會導(dǎo)致修復(fù)進程選擇一個跟fast-round不同的值.
slide-40
下面是一個fast-round中X成功, Y失敗的沖突的例子:
X已經(jīng)成功寫入到4(fast-quorum>?n)個acceptor, Y只寫入1個, 這時Y進入classic-round進行修復(fù), 可以看到, 不論Y選擇哪3(classic quorum)個acceptor, 都可以看到至少2個x?, 因此Y總會選擇跟X一樣的值, 保證了寫入的值就不會被修改的條件.
slide-41
再來看一個X和Y都沒有達到fast-quorum的沖突:
這時X和Y都不會認為自己的fast-round成功了, 因此修復(fù)過程選擇任何值都是可以的. 最終選擇哪個值, 就回歸到X和Y兩個classic-paxos進程的競爭問題了. 最終會選擇x?或y?中的一個.
其他
slide-42
一個很容易驗證的優(yōu)化, 各種情況下都能得到一致的結(jié)果.
slide-43
廣告頁, 不解釋了?
本次的 pdf 可以下載和在線看哦:
[可靠分布式系統(tǒng)-paxos的直觀解釋.pdf]
[可靠分布式系統(tǒng)-paxos的直觀解釋.html]
本文鏈接: [https://blog.openacid.com/algo/paxos/]
[可靠分布式系統(tǒng)-paxos的直觀解釋.pdf]:?https://blog.openacid.com/post-res/paxos/可靠分布式系統(tǒng)-paxos的直觀解釋.pdf
[可靠分布式系統(tǒng)-paxos的直觀解釋.html]:?https://blog.openacid.com/post-res/paxos/可靠分布式系統(tǒng)-paxos的直觀解釋.html
[raft]:?https://raft.github.io/
[Leslie Lamport]:?http://www.lamport.org/
[Byzantine Paxos]:?https://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos
[Classic Paxos]:?http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
[Fast Paxos]:?http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos
[EC第一篇:原理]:?https://blog.openacid.com/storage/ec-1
[EC第二篇:實現(xiàn)]:?https://blog.openacid.com/storage/ec-2
[EC第三篇:極限]:?https://blog.openacid.com/storage/ec-3
