1樓：速溶雀巢咖啡
先不說具體推導。我們看下協議流程。
首先paxos是個多數派協議。
其次多數派達成一致的協議分成了2個階段。
系統的角色有：proposer，acceptor。（我們暫且認為proposer和acceptor部署在一台機器上）
acceptor存有3個變數：version， value，value-version。
version: 版本號。value：提議值。value-version：提議值被接受時候的版本號。
acceptor承諾，不會接受當前請求裡面攜帶的版本號小於verison的請求。
第一階段：
proposer向acceptor發起Prepare請求。帶上自增的版本號。這一階段是為了搶占acceptor的寫入許可權，也就是把這個版本號寫入導acceptor裡面的version。
當半數回覆請求後，proposer通過比較acceptor之前儲存的版本。確保自己的版本號能寫入大多數機器後。就可以進入第二階段，提議乙個值。
如果第一階段acceptor返回的value都是空的華，提議的值可以自己定。
如果acceptor返回的value有不為空的，就在返回裡面找value-version最大的value作為提議值。
注意上面這個點是整個paxos形成多數派共識的關鍵點。
第二階段：
proposer發起提議寫入乙個值請求。
acceptor通過比較version,把proposer提議的值寫入。從而形成多數派共識。
後續就算有其他proposer發起提議。也會用現在已經形成多數派共識的值。
以上只是在系統中確定乙個值。
多個paxos例項確定一些列值。目前用於比較多的場景是kv儲存的變更序列。
具體推導和證明過程可以參看網上其他資料。
2樓：
建議看看6.824-2015的note：
nil.csail.mit.edu/6.824/2015/notes/l-paxos.txt有例子、有推論
3樓：馬宇
哎，看了這些答案之後才知道要把乙個知識點講簡單，講清楚真的是很難啊。
很多人都是要麼照搬一大段理論知識，要麼在這邊舉各種所謂「幫助理解」的例子，用各種「自以為很淺顯實際上增加了理解難度的」名詞，來自我滿足。
我也找了很多文章，沒看到有什麼淺顯易懂的解釋，這種精品的講解可遇不可求啊。
4樓：中方
公司決定去旅遊，需要決定乙個目的地。
你們是一家自由的公司。想上班就上班，想下班就下班，想偷懶就偷懶。在任何時候，你都不能確定某個員工在不在。
那麼，怎麼做才可以盡可能不被懶散的員工影響，盡快決定目的地呢？
為此，公司設立了一些規定：
為了保證不受懶散的人影響。每個人都可以提議想去的地方。但是需要自己去請求公司一半以上的人同意。
為了盡快達成一致，每個建議都有唯一編號，編號越大越重要。
這些規定還不夠，還需要制定流程來保證。
乙個叫 萊斯利·蘭伯特
的同事想出乙個辦法。他說，只要你們按我說的流程去辦事，我保證，只要公司有超過一半的員工在，目的地就能夠被選舉出來，並且是唯一的。
他的方法是這樣的。
提議的人呢，在提議之前，先諮詢公司超過一半的人，看看之前它們都收到哪些建議並且把你的建議編號告訴他們。
如果發現有比你重要的建議，直接放棄提議。
如果沒有更重要的建議，就在收集到的建議裡面找個最重要的，把它的編號改成你的。
如果詢問的所有人都沒採納過建議，那最好，在建議裡寫上你想去的地方就好。
收到建議的人呀，你們記住乙個事就好了。
永遠採納更重要的建議！
無論在任何時候，只要知道某個建議存在，哪怕只是乙個編號，都要拒絕重要性比它低的建議。
怎麼證明？
用數學歸納法證明：
對於乙個被提出的建議n，編號比它小的建議，要麼得不到一半以上的人同意，要麼目的地與n的相同。
5樓：zjufisher
推薦一下google的乙個tech talk, https://www.
6樓：Learner
作者都說了，paxos是再簡單不過的演算法了，幼兒園都能看懂，你們長篇大論的扯，也能說簡單易懂？
演算法的核心就是大多數，是團隊思想，只有大多數接受的提議才是通過的提議，在保證大多數存活的前提下，已經通過的提議才能傳遞下去，不會被遺忘和篡改
7樓：
Paxos兩部曲了解一下?
無名氏：推導Basic Paxos演算法
無名氏：推導Multi-Paxos演算法
200行的Basic Paxos實現也順便了解一下?
JimChengLin/paxos-edu
8樓：eloggo
大家有沒有研究過virtual synchrony？這也是一種在分布式節點間傳遞訊息，確保送達，一致性的技術。通常現在用在管理集群節點狀態，一直發探測訊息，發現異常節點會踢出集群。
所以如果利用這個技術來達到paxos的效果一樣可以呀，比如每個節點都有乙個集群節點的狀態列表，傳送到任何乙個節點的request都可以根據狀態列表來廣播更新同一條資料，達到資料一致性，一旦發現某節點沒有在timeout內更新成功，就踢出集群，對於併發場景可以對request維護乙個全域性遞增的乙個seq號。這樣的話感覺沒問題呀，為什麼現在分布式系統中paxos或類paxos協議會大行其道？另外補充一點是，這個virtual synchrony不需要強leader，每個節點是對等的。
大家看看有什麼硬傷嗎？或是哪些強一致場景非paxos不可？
9樓：
Paxos 協議---我覺得下面這段解釋的很不錯，簡單的例子，避免長篇大論，通俗易懂。
Paxos協議用於達成共識性問題，即對多個節點產生的值，該演算法能保證只選出唯一乙個值。
主要有三類節點：
提議者（Proposer）：提議乙個值；
接受者（Acceptor）：對每個提議進行投票；
告知者（Learner）：被告知投票的結果，不參與投票過程。
執行過程
規定乙個提議包含兩個字段：[n, v]，其中n為序號（具有唯一性），v為提議值。
下圖演示了兩個Proposer和三個Acceptor的系統中執行該演算法的初始過程，每個Proposer都會向所有Acceptor 傳送提議請求。
當Acceptor接收到乙個提議請求，包含的提議為[n1, v1]，並且之前還未接收過提議請求，那麼傳送乙個提議響應，設定當前接收到的提議為[n1, v1]，並且保證以後不會再接受序號小於n1的提議。
如下圖，Acceptor X在收到 [n=2, v=8] 的提議請求時，由於之前沒有接收過提議，因此就傳送乙個[no previous] 的提議響應，並且設定當前接收到的提議為[n=2, v=8]，並且保證以後不會再接受序號小於2的提議。其它的Acceptor 類似。
如果Acceptor接收到乙個提議請求，包含的提議為[n2, v2]，並且之前已經接收過提議[n1, v1]。如果n1 > n2，那麼就丟棄該提議請求；否則，傳送提議響應，該提議響應包含之前已經接收過的提議[n1, v1]，設定當前接收到的提議為[n2, v2]，並且保證以後不會再接受序號小於n2的提議。
如下圖，Acceptor Z 收到Proposer A 發來的[n=2, v=8]的提議請求，由於之前已經接收過[n=4, v=5]的提議，並且 n > 2，因此就拋棄該提議請求；Acceptor X收到Proposer B發來的[n=4, v=5]的提議請求，因為之前接收到的提議為 [n=2, v=8]，並且2 <= 4，因此就傳送[n=2, v=8]的提議響應，設定當前接收到的提議為[n=4, v=5]，並且保證以後不會再接受序號小於4的提議。Acceptor Y 類似。
當乙個 Proposer 接收到超過一半 Acceptor 的提議響應時，就可以傳送接受請求。
Proposer A 接收到兩個提議響應之後，就傳送 [n=2, v=8] 接受請求。該接受請求會被所有 Acceptor 丟棄，因為此時所有 Acceptor 都保證不接受序號小於 4 的提議。
Proposer B 過後也收到了兩個提議響應，因此也開始傳送接受請求。需要注意的是，接受請求的 v 需要取它收到的最大 v 值，也就是 8。因此它傳送 [n=4, v=8] 的接受請求。
Acceptor 接收到接受請求時，如果序號大於等於該 Acceptor 承諾的最小序號，那麼就傳送通知給所有的 Learner。當 Learner 發現有大多數的 Acceptor 接收了某個提議，那麼該提議的提議值就被 Paxos 選擇出來。
約束條件
1. 正確性
指只有乙個提議值會生效。
因為 Paxos 協議要求每個生效的提議被多數 Acceptor 接收，並且 Acceptor 不會接受兩個不同的提議，因此可以保證正確性。
2. 可終止性
指最後總會有乙個提議生效。
Paxos 協議能夠讓 Proposer 傳送的提議朝著能被大多數 Acceptor 接受的那個提議靠攏，因此能夠保證可終止性。
10樓：
假設存在n臺伺服器儲存key，舊的值為key_old其中有3臺更新了，那麼這三颱需要向其他伺服器廣播，讓其他伺服器也更新key的值。
因此這三颱是提議者，其他伺服器是接受者（但只是先對而言的）
提議者生成乙個時間戳，並向所有的伺服器廣播這個時間戳和之前的key_old的值
接受者，接收到時間戳和key_old以後
判斷key_old和自己儲存的key是否相同
相同的話，表示廣播的伺服器確實是更新了key的值，因此自己也需要跟著更新。然後判斷時間戳：
如果沒有時間戳，那麼就儲存新的時間戳
表示同意更新為這個提議者伺服器的key值，儲存的時間戳和key值，並且回覆提議者剛剛儲存的時間戳和key(此時一定是key_old)，等待提議者回覆要更新的key值。
如果大於已儲存的時間戳，那麼更新為較大的時間戳
這裡的含義是，雖然這台接受者，在之前答應了一台提議者要更新為他的值，但是他並沒有及時的發過key來,因此就被搶占了。
然後這台伺服器改為答應新來的這台提議者，接受他的key。
並回覆給這台提議者，儲存的時間戳和key值，此時也是key_old
如果對比出的key不相同
那麼表示這台伺服器要不是已經接受一台提議者的key，要不就是一台提議者。
如果一台接受者，接受了一台提議者的key，那麼這台接受者，到本次結束，都只能接受這台接受者的key。
然後回覆給提議者，儲存時間戳和新key值。
提議者，在收到回覆以後，
如果收到的key值都是key_old，表示都沒有更新過，並且只有在回覆數超過一半的時候，才可以廣播自己時間戳和key給所有的伺服器，如果不夠一半，那麼就重新生成依次時間戳重複上面步驟
注意這裡，這台伺服器一定要確保所有的伺服器都能夠更新為自己key，除了已經接受提議者的接受者。
這裡有抽屜原理
如果收到key不等於key_old
那麼表示，有的伺服器已經更新過了。開始比較返回的時間戳
如果時間戳大於自己傳送的時間戳，那麼不用理睬
不用理睬的含義是，每次更新key，都是以最先更新的那台接受者的key為做種結果。
如果時間戳小於自己傳送的時間戳，那麼表示這台伺服器接受了早於自己更新的值。
因此需要將自己的key，更改為，時間戳最小的那台伺服器的key
然後收到回覆的，需要更新的伺服器自己的時間戳和更新後的key值。
過程就是這樣的。
這裡的要點在於
對於接受者來說，
如果自己的key需要更新，那麼他只接受時間戳較大的提議者的key
一旦接受者，接受了一台提議者的key以後那麼這台接受者，就不能夠在接受其他提議者的key了。但是，可以繼續根據這台接受者的key，更新自己的key
對於提議者來說
需要向所有的伺服器廣播
只有在接收到一半以上的伺服器的需要更新的訊息以後，以後才能夠繼續更新。
原因在於，如果兩台提議者，各接收到了沒有交集的一半的伺服器的更新請求，那麼整個伺服器就分成兩半，每一半持有自己的乙個key
接受者收到的key和之前的key_old不一樣，表示這台接受者已經更新過一次了。那麼接收到的時間戳，如果時間戳小於自己的，表示，這台接受者更新的key要早。那麼自己的更新是沒有必要的。
因此更改為接受到的這個key值。
更新標準，所有的接受者中，最先更新的那台接受者的key，將會是最終所有伺服器的key
什麼時候結束。
只要一台提議者，接收到了和key_old值不同的伺服器，而且時間戳要小。那麼就想所有的伺服器廣播這個key，（但是自己的時間戳不改）
因此這裡考慮一種極端的情況：
（或者是，在乙個提議者根據收到的時間戳，判斷是否應該修改自己的key的那一步說反了？）
怎麼淺顯易懂生動形象又「危言聳聽」地告訴老媽 每天兩次每次一片的鈣片不能每天一次每次兩片吃？
諾亞方舟 作為乙個醫生，鈣片這東西吸收率超級差的，主要還是要靠多運動曬太陽，促進吸收，分開吃還是一起吃差不了太多，要促進吸收最好買含維生素D的鈣片 小明 這個問題簡單啊，你給你媽說人體每天每次的需要的量就那麼多，如果多了就有兩種情況出現第一種就是壓根兒沒發吸收，浪費了一片的錢，這到沒啥。第二種情況那...
如何理解DAG資料結構，並且用淺顯易懂的話說出來？
小羊開門吶是我 DAG Directed Acyclic Graph，中文意為 有向無環圖 有向無環圖是一種儲存資料的方式。有向 指所有資料順著同一方向儲存 無環 指資料結構間不構成迴圈。像條毛線織的圍巾，可以一直編下去。為什麼要連線 標箭頭？因為使用者每發起一筆交易，必須驗證之前的兩筆交易。這很像...
如何向文科生淺顯易懂的講解薛丁格的貓？
補充一些 你不去看，貓在盒子裡是既死又活的疊加態，但你不知道是生還是死。你想知道，就要開啟盒子。一旦去看了，貓的生死就不一定是在盒子裡決定的。因為你不能判斷貓是之前就活著 死了，還是你開啟的瞬間因為你的干預死了 還活著 或者只是你開啟的那一瞬間是死的 活的，這個不好理解，因為貓不可能死而復生 這個假...