又?jǐn)]了一遍分布式協(xié)議，準(zhǔn)備自己對(duì)paxos復(fù)盤下，下面是感覺(jué)還不錯(cuò)可以參考的文章, 知識(shí)只能是?？闯Ｐ铝?。

推薦書：從PAXOS到ZOOKEEPER分布式一致性原理與實(shí)踐

• 維基百科之Paxos算法
  大家都是這個(gè)寫的最經(jīng)典，但是真心看不懂啊，可以先擼一遍留下來(lái)印象，回頭再擼
• 如何淺顯易懂地解說(shuō) Paxos 的算法？
  好多的回答，挑著看吧
• 關(guān)于分布式事務(wù)、兩階段提交協(xié)議、三階提交協(xié)議
  算是基本說(shuō)明吧 兩階段 3階段
• Raft協(xié)議實(shí)戰(zhàn)之Redis Sentinel的選舉Leader源碼解析
  這個(gè)可以做補(bǔ)充
• Zab vs. Paxos 原
  提到paxos算是有限狀態(tài)機(jī)，理解的一個(gè)新思路，zab那塊不是很明白順序性怎么回事。
  -zookeeper入門系列-理論基礎(chǔ)-zab協(xié)議

1 文章摘抄

basic paxos一些想法

• basic paxos一些想法：
  分布式一致性與分布式鎖之間存在差別，例如對(duì)于一個(gè)值同時(shí)發(fā)起兩個(gè)修改，一致性不確保兩個(gè)修改都會(huì)執(zhí)行，執(zhí)行其中任意一個(gè)都是可能的，常見(jiàn)情況是其中一個(gè)返回修改失敗，再次進(jìn)行修改后成功。一致性只保證所有機(jī)器中的值是相等的。其實(shí)在預(yù)決議和最終決議兩個(gè)階段，acceptor的策略是一樣的，同意編號(hào)更大的，proposer的策略也是一樣的，超過(guò)一半同意就執(zhí)行下一步。但是因?yàn)闀r(shí)序問(wèn)題，不同消息到達(dá)acceptor時(shí)，acceptor存在不同情況（錯(cuò)位），需要作出一個(gè)能最終達(dá)到一致性的決定，
  優(yōu)先級(jí)：更大編號(hào)的最終決議>更小編號(hào)的最終決議>更大編號(hào)的預(yù)決議>更小編號(hào)的預(yù)決議>沒(méi)有預(yù)決議。

作者：樓虎彪
鏈接：https://www.zhihu.com/question/19787937/answer/370367692

提議ID生成算法

image.png

1） P0提交的時(shí)候發(fā)現(xiàn)了P1已經(jīng)提交，P1編號(hào)為1 >P0的0，因此P0重新計(jì)算編號(hào)：當(dāng)前最大的s是1，是P1提供的，那最大s對(duì)應(yīng)m的計(jì)算公式是m1=(s1-ir1)/n,即為m=(1-1)/3=0，當(dāng)前節(jié)點(diǎn)m是0，與P0現(xiàn)在的m是相等的，因此m++；那new s0=m*n+ir0 即為1*3+0=3

2） P2以編號(hào)2提交，發(fā)現(xiàn)小于P0的3，因此P2重新編號(hào)：當(dāng)前最大的s是P0的3，所以m=（3-0）/3=1;比當(dāng)前節(jié)點(diǎn)的m大，所以當(dāng)前節(jié)點(diǎn)的m需要等于最新的m，那new P2 = 1*3+2 = 5。

這個(gè)算法如果proposer擴(kuò)節(jié)點(diǎn)了怎么整？

paxos協(xié)議的問(wèn)題

1. 活鎖問(wèn)題。在base-paxos算法中，不存在leader這樣的角色，于是存在這樣一種情況，即P1提交了一個(gè)proposal n1并且通過(guò)了prepare階段；此時(shí)P2提交了一個(gè)proposal n2(n2>n1)并且也通過(guò)了prepare階段；P1在commit時(shí)因?yàn)橐呀?jīng)通過(guò)了n2而被拒絕；于是P1繼續(xù)提交一個(gè)proposal n3并且通過(guò)prepare階段；巧的是此時(shí)P2開始commit了，由于n2<n3再次被拒絕……如此循環(huán)往復(fù)。這種情況被稱為活鎖。即整個(gè)系統(tǒng)都沒(méi)死，但由于互相請(qǐng)求資源而被互相鎖死。為了不發(fā)生活鎖的情況，最簡(jiǎn)單的方式當(dāng)然是縮減proposer到一個(gè)，這樣就不會(huì)發(fā)生互相請(qǐng)求鎖死的情況，也即退化。事實(shí)上很多后來(lái)的工業(yè)級(jí)協(xié)議，都是paxos協(xié)議的退化或者變種。

2. 復(fù)雜度問(wèn)題。base-paxos協(xié)議中還存在這樣那樣的問(wèn)題，于是各種變種paxos出現(xiàn)了，比如為了解決活鎖問(wèn)題，出現(xiàn)了multi-paxos；為了解決通信次數(shù)較多的問(wèn)題，出現(xiàn)了fast-paxos；為了盡量減少?zèng)_突，出現(xiàn)了epaxos?？梢钥吹剑I(yè)級(jí)實(shí)現(xiàn)需要考慮更多的方面，諸如性能，異常等等。這也是為啥許多分布式的一致性框架并非真正基于paxos來(lái)實(shí)現(xiàn)的原因。

3. 全序問(wèn)題。對(duì)于paxos算法來(lái)說(shuō)，不能保證兩次提交最終的順序，zab解決了這個(gè)問(wèn)題。

作者：liweisnake
原文：https://blog.csdn.net/liweisnake/article/details/70045164

2 擼了好幾天paxos算法了，按照自己的理解整理下。自己寫了個(gè)流程圖，便于理解吧。

分布式算法.png

3 數(shù)學(xué)歸納法

看了好久也沒(méi)看明白算法的證明，惡補(bǔ)了下數(shù)學(xué)歸納法，高中的知識(shí)已經(jīng)還給老師了。。。。。

按照出題的形式來(lái)吧，一般數(shù)學(xué)歸納法證明的數(shù)學(xué)題都張下面這樣。手寫吧,電腦寫數(shù)學(xué)題還是麻煩。

微信圖片_20190412172811.png