數(shù)據(jù)備份是為了數(shù)據(jù)的安全些，比如數(shù)據(jù)庫系統(tǒng)，一主一備是基本的配置。當同一數(shù)據(jù)儲存多份之后，每份數(shù)據(jù)之間理論上應該是要一樣的（畢竟是同一數(shù)據(jù)），但如何在實際中保證他們是一樣的，就是所謂的分布式系統(tǒng)的一致性難題。
Paxos算法解決的就是分布式系統(tǒng)的一致性問題。

問題：

假設有一堆進程，能對某個變量應該是什么值發(fā)表建議。paxos算法可以保證最終會選取一個值給這個變量。

1. 如果沒有進程提出值，最終肯定也是沒有結果的。
2. 如果有多個線程提出意見，最終只有一個值并選定，并且這個選定的值大家都會知道（然后就可以更新本地自己的變量了）

角色劃分

從角色上劃分，有proposer, acceptor,learner。
對于proposer，提出一個值v。直接提出就好了。
對于acceptor，對于接受到的proposer提出的proposal?？梢赃x擇接受，或者拒絕。既然有兩種選擇，就需要給出選擇的依據(jù)。
learner只需要知道結果，因此對于值是如何達成一致的沒有任何的幫助。因此下面主要通過proposer和acceptor的角度分析paxos算法。

過程推導

Conclusion 1: acceptor 必須接受第一個到達的proposal

1. 假設只有一個節(jié)點的情況。自己即是proposer, 又是 acceptor。當然自己沒有理由拒絕自己的提案。
2. 假設兩個節(jié)點的情況，A propose 一個值，而B 為了讓系統(tǒng)達成最終的一致，只能接受自己收到的提議。
3. 擴展到多個節(jié)點， 考慮節(jié)點可能失效，消息可能丟失。對于一個acceptor，當他接受到一個提議時，他是無法預測未來是否還有提議，在這種情況下，他只能接受這個值。如果他不接受，系統(tǒng)最終就可能達不成一致。
   總結上面3點，對于acceptor，對于第一條達到的消息，只能選擇接受。

Conclusion 2: acceptor 可以接受多個proposal

按照P1的原則，如果每個acceptor接受一次消息后，系統(tǒng)就達成了一致，那么P1足夠保障系統(tǒng)的一致性。但由于proposer不止一個，acceptor也不止一個，當兩個propose人的提案被不同的acceptor接收以后，導致沒有一個提案獲得大多數(shù)acceptor的接收，系統(tǒng)達不成一致。
在這個場景下，為了達成最終的一致，proposer會再次提出提案，而acceptor也會再次接收到提案。對于這些提案，acceptor一定是可能接收的（如果全是拒絕的策略，那么系統(tǒng)永遠不能一致了）。
也就是說，對于acceptor而言，他是可能接受多個proposal 的。
為了能將各個proposal區(qū)分開來，將每個proposal分配一個編號id。proposal目標包含一個編號id和值value。當proposer發(fā)出提案時，需要使用唯一的id。

Conclusion 3: acceptor接受proposal_id 更大的提案

我們知道，第一個proposal用戶已經(jīng)接受了?，F(xiàn)在問題是，對于后來的proposal，用戶如何選擇接受或者拒絕。
proposal中只包含兩個東西。一個是id，一個是value。
對于value，只有兩種情況

1. 當value一樣的情況，選擇接受當然不會有問題，但對于系統(tǒng)達成一致性沒什么幫助。
2. 當value不一樣的情況。如果全部拒絕，則系統(tǒng)最終達不成一致。如果全部接受，那么又回到混沌初開的原點，不需要任何算法了，對于acceptor，來一個提案，接受一個。能不能達成一致看運氣了。
   所以從value的角度看，甚至沒有辦法給出一個拒絕或者接受的條件（哪怕是個不靠譜的條件也行）。

回到id，也只有兩種情況

1. id比第一次接受的proposal的id要大。
2. id比第一次接受的proposal的id要小。
   兩種情況沒有本質區(qū)別，我們可以選擇一種進行接受，另一種進行拒絕。為了符合人性，選擇大的id接受。
   當然，這種選擇也是靠天吃飯，但至少acceptor有個拒絕接受的依據(jù)了。

Conclusion 4：proposer提出的value需要和已經(jīng)通過的提案（如果有的話）保持一致。

acceptor已經(jīng)盡力了。剩下的只能看proposer的了。
proposer提出提案也是只包含id和value。
id可以考慮的東西不多，畢竟acceptor只接受更大的id，那不妨提出提案的時候選個盡量大的。

對于value。
我們首先要注意整個一致性算法的目標是在value上達成一致。也就是說，如果某個acceptor提出的value已經(jīng)被大多數(shù)的acceptor接受了，你現(xiàn)在要提出一個提案（你還不知道已經(jīng)在value上達成了一致，剛剛說被大多數(shù)acceptor接受這個事情是屬于上帝視角，在一段時間內(nèi)，整個系統(tǒng)都不知道這件事而這件事確實已經(jīng)發(fā)生），你選擇了一個大的id，剛剛那批達成一致了的acceptor又沒有辦法拒絕你，所以這個時候，為了達成一致性，你提出的value必須和已經(jīng)被大多數(shù)acceptor認可的value一樣。
從上帝視角看，當你要提出一個proposal的時候，系統(tǒng)的狀態(tài)分為兩種

1. 某個提案被大多數(shù)acceptor已經(jīng)接受，其值為value。此時proposal提出的提案也必須為value。
2. 還沒有達成一致。此時proposal提出的提案的值可以任意。

Conclusion 5: proposer根據(jù)接受到acceptor反饋的proposal決定如何選取value。

如果acceptor沒有返回任何proposal，則proposer可以任意選取value。否則選擇其中最大的proposal的值。

對于一個proposer而言，

1. 他已經(jīng)知道了整個系統(tǒng)達成了一致。他肯定不會提出提案。
2. 如果他不知道整個系統(tǒng)是否一致，這個時候他該怎么提出值？

此時別無他法，只能由該proposer去詢問每個acceptor，而每個acceptor的回答會有兩種情況

1. 我沒有接受過任何proposal。
2. 我接受過proposal。

對于情況2，需要進行分析

1. 該acceptor可能接受過多個proposal。

2. 該acceptor返回的proposal可能是已經(jīng)通過的提案，也可能還沒有通過，只是這個acceptor接受而已。
   在詢問一圈之后，proposer會收到多個acceptor的回答?；卮鹬邪烁鱾€acceptor曾經(jīng)接受了的proposal。這些proposal中可能一個都沒有通過--此時該proposer可以隨意提出value，也可能有一個（最多一個了）是已經(jīng)通過的--此時該選取哪個proposal的值又是一個問題。
   為了便于區(qū)分，先將這一次proposal的詢問行為定義為prepare_request。
   同時，我們需要解決的問題演變?yōu)榱耍喝绾卧诟鱾€acceptor回到的proposal中選取一個，作為此次提案的value依據(jù)。

3. 如果這堆提案中沒有一個是通過的，則proposer可以任意提出value。

4. 其中有提案時通過的，記其中一個為m=(m, v)，其對應的大多數(shù)集合為C。
   劃重點：當提案(m,v)通過是，集合C中的所有acceptor接受過的最大的proposal都是(m,v)。所以當m+1號提案提出時，為了獲取到v這個值，他一定要獲取到C中至少一個acceptor的回復，因此m+1好提案正式提出前，至少要獲取都大多數(shù)集合的acceptor的回復才行。
   對于m+1而言，獲取大多數(shù)集合的回復，并且使用通過的最大的proposal的v就能滿足Conclusition4。由于m+1的提案值也是v，因此對于集合C，依然保持了接受的最大proposal的v就是通過的提案value。
   因此對于m+2號提案，可以使用與m+1號提案相同的方式。
   通過簡單的歸納證明，沿用此方法，能使得在m之后的所有提案都具有相同的提案值。

也就是說:如果n要提出(n, v)，那么存在一個大多數(shù)集合C。滿足

1. C中的acceptor沒有接受過任何提議。-- 對應于還沒有提案通過的情況
   或者 2. C中的acceptor接受小于n的最大提議的值為v。 -- 對應于有提案通過的情況

在上述條件的情況下，如果v被通過，則后續(xù)提出的所有值都將是v?？梢試栏褡C明反證如下：
對于m+1，如果提出的值不等v。那么存在一個大多數(shù)集合C沒有接受過任何值，或者C中接受的小于m+1提案的提議值不等于v。而(m,v)已經(jīng)被接受，因此不存在那樣的集合C。

因此，對于proposer的要求出來了：
當獲取到acceptor返回的proposal后，選取最大的proposal作為值，如果不存在，則可以任意選取。

至此，paxos的整個過程已經(jīng)確定了。
預請求階段:

1. proposer選定編號n，將編號發(fā)送給acceptors
2. acceptor收到預請求后，a) 保證后面不在接受比n小的提案。 b) 返回已經(jīng)接受過的，編號比n小的，最大的提案。

請求階段：

1. 如果proposer收到了大多數(shù)acceptor的反饋。則進入請求階段。其value為 a) 如果acceptor沒有返回任何已經(jīng)接受過的proposal。 b) acceptor返回的proposal中編號最大的對應的value。
2. acceptor接受到請求后，如果大于等于其接收過的最大的預請求編號，就接受這個請求。

一些易混點

1. acceptor返回給proposal的是小于預編號的最大接受提案。