前言

本文參考Paxos made simple這篇論文, 對Paxos演算法的推導過程用接地氣的場景來表述. 下文會從"n個同學開party, 需要確定誰來當東道主"的場景, 一步一步的推導出Paxos演算法.

背景

假設有n個同學, 準備週末去某個人家裡開party, 他們現在需要確認他們這些人中究竟誰做東道主負責party的舉辦事宜.

每個人都可以提議自己當東道主, 並且有權同意、否決別人的提議(也就是系統中, 每個節點既是proposer, 又是acceptor).另外, 他們每個人之間都是點對點通信的, 比如說通過微信私聊的方式.

那麼, 通過什麼投票方案可以得到一個共識呢? 總體方向肯定就是"多數派原則"了. 但是這個原則之下, 還是有很多邊邊角角的問題會導致無法達成共識, 還需要有具體措施來規避這些問題.

下面會從"多數派原則"這個最基本方案, 一步一步的解決遇到的問題, 一次次的迭代, 最終漸漸推導出完善的一套方案: Paxos!

例如, 下文的版本1隻是使用"多數派原則"這個基本方案存在明顯的漏洞, 後面的版本2、3、4在版本1的基礎上， 一步一步的解決這些問題.

版本1 多數派原則

問題:

無法達成多數派, 出現split vote, 形成僵持局面

假設n=5, 共有ABCDE這些個同學(系統中有5個節點).

另外還假設這些同學脾氣都很犟, 不肯變通, 自己同意了一個提議後, 打死都不再改變主意了(不允許各個節點accept一個值後, 不能再改變).

我們看看這樣的設定會有什麼問題, 最後來思考如何避免這個問題.

那麼考慮這個場景: 同學A向提議"來我家", AB都同意了; 與此同時, 同學C提議"來我家", CD都同意了; 與此同時,同學E提議"來我家", E自己同意了. 這樣下來, 沒有一個提議可以形成多數派.

由於這些同學脾氣都很犟, 互不相讓,不再改變主意, 那麼這次開party肯定就泡湯了, 因為5個同學沒有達成一致的共識.

解決方案:

允許acceptor改變自己的主意, 如果acceptor即是已經accept了某個值, 後面也可以accept其他的提議.

也就是一輪投票不成, 大家可以再商量商量, 不要脾氣犟的跟驢一樣.

版本2 節點可以接受後續的提議

在版本1的基礎上, 添加一個新措施: 節點可以改變主意, 接受後續的提議. 這樣我們就有了迭代2. 我們繼續看版本2的問題是什麼.

問題:

有acceptor在接受一個提議後又改變了主意, 可能會導致系統選擇了多個值(conflict choice)

假設n=5, 共有ABCDE這些個同學(系統中有5個節點).

另外還假設這些同學脾氣都很好, 可以改變自己的主意.

那麼考慮這個場景: 同學A向提議"來我家", ABC都同意了; 與此同時, 同學E提議"來我家", CDE都同意了;

這裡E充當了老好人的作用, 導致這5個同學都以為達成共識了, 同學們裡面有兩個人都認為自己是東道主了. 最後AB高高興興的在A的家裡開party, 然而CDE就是在E的家裡開party...

解決方案:

在proposer提議之前, 再引入一個prepare階段: 先向所有acceptor發起詢問, 詢問它有沒有已經接受某個值(accepted, 不一定是chosen. 當然, 在Paxos中, 這個accepted的值肯定也是最後被chosen的值), 如果有接受的值, 那proposer必須改變自己的提議值, 使用已經接受的值作為新的提議值. prepare階段之後, 再進行提議階段(accept階段).

版本3 兩階段協議

在版本2的基礎上, 引入了兩階段協議的思想. 這樣我們就有了版本3.

問題:

系統節點之間的通信沒有保障, 消息可能丟失, 也可能延時到達. 可能導致proposer誤認為當前還沒有被accepted值, 也就是兩階段協議形如虛設, 最後導致了和版本2一樣的問題(conflict choice)

假設n=5, 共有ABCDE這些個同學, 他們使用兩階段協議的思想來進行協商.

考慮如下圖所示場景:

同學A發起提議前的prepare階段發現還沒有值被接受, 所以直接提議"來我家".

在他的提議被BC同學看到之前, E同學發起了提議"來我家"(他在prepare階段也發現當前還沒有值被選定).

由於網路的不可靠, 同學E的提議先於A的提議到達了BC那, 所以BC先accept了同學E的提議. 所以同學E認為已經確定了自己就是開patry的東道主.

但是, 故事還沒有結束, BC同學此後又收到了A同學遲來的提議, 因為同學們都是脾氣挺好的老好人, 所以BC改變了主意接受A同學作為東道主.

所以, 現在的情況又和版本2類似, 同學們裡面有兩個人都認為自己是東道主了.

解決方案:

上述場景中, 因為"遲來"的提議導致了conflict choice的出現, 所以, 我們需要有手段可以屏蔽掉上述場景中那些"遲來"的提議.

方法是為每個提議都進行編號, 而且acceptor需要承諾如果已經遇到一個編號為n的提議, 那麼後續遇到的編號小於n的提議, 都直接拒絕.

編號維護

每個proposer節點都保存自己至今為止所看到、用到過的最大的編號，記為maxProposal.

要生成一個新的提議號時，proposer用n=++maxProposal來作為提議編號.

在proposer角度來看, 這個編號可以不需要持久化. 從下文可以知道, 只要acceptor做了持久化即可.

版本4 有序的兩階段協議

經過多次迭代, 我們已經接近完美的投票流程了. 我們再版本3的基礎上, 對所有提議進行編號後, 得到的新版的投票流程如下:

prepare階段

  • proposer: 發起prepare請求, 請求中攜帶著本次提議的編號n, 其中n=++maxProposal.
  • acceptor: 接到prepare請求時, 如果編號n大於等於promiseProposal, 那麼他承諾永遠也不會同意提議編號比這n值小的prepare請求, 記為promiseProposal=n, 需要進行持久化. 另外, 如果它已經accept了某個值, 需要把接受的值(記為acceptedValue)和當時的提議編號(記為acceptedProposal)返回給proposer; 如果n小於promiseProposal, 那麼acceptor可以拒絕該請求, 同時要返回自己的promiseProposal以便proposer更新下一次的提議編號.

proposer在發出prepare請求之如果收到多數派的acceptor的承諾, 那麼可以進入accept階段. 根據acceptor返回的acceptedValue來確定有沒有已經被accept的值, 如果有, 我們就要在accept階段時使用這個值. 否則的話使用自己一開始的提議值.

如果prepare階段沒有收到多數派的承諾, 說明本次提議已經過期, 需要更新自己的提議編號, 重新發起prepare請求.

accept階段

  • proposer: 發起accept請求, 請求中攜帶本次提議的編號n和本次的提議值.
  • acceptor: 接到accept請求後, 檢查編號n是否大於等於promiseProposal, 如果是, 那麼acceptor接受該提議, 更新acceptedProposal和promiseProposal的值為n, 以及更新acceptedValue為提議值, 需要進行持久化; 如果不是的話, acceptor就拒絕該請求, 同時要返回自己的promiseProposal以便proposer更新下一次的提議編號.

如果proposer收到了過半數的acceptor的接受，那麼它就可以確定自己提議的值被選定了. 否則需要更新提議編號, 重新回到prepare階段.

最後我們一步步完善後得到的流程其實就是Paxos演算法. 關於Paxos的正確性的證明, 在這裡就不贅述了. Paxos演算法的具體流程和證明請參考[1].

最終, 同學們通過Paxos演算法確定了誰家作為東道主, party順利舉行! (當然, 也可能有少數派的同學出狀況了沒有參加party~~).

總結

我們從簡單的"多數派原則", 經過的多次迭代可以簡述為如下:

  1. 純粹"多數派原則"會導致split vote的問題.
  2. 所以要允許acceptor改變自己的主意, 但這樣做會導致多個值被選定(conflict choice).
  3. 所以要引入兩階段協議, 讓proposer提議之前, 檢查有沒有已經被選定的值, 沒有的話再來提議. 但是可能會有延時到達的提議, 導致兩階段形同虛設.
  4. 所以要對proposal進行排序. 如果acceptor已經接受了更加新的提議, 對於遲來的老的提議應該拒絕掉.

參考

[1] Paxos made simple

一步一步推導Paxos演算法?

www.ioseeker.com圖標
推薦閱讀：
相關文章