普通小學生也能理解的Paxos算法講解_風聞

我在上一篇文章小學生也能輕鬆掌握的Paxos/Raft算法奧秘簡單介紹了Paxos算法的一種直觀理解方式。但是有同學反映説內容還是有點難以理解，恐怕只有天才小學生才能看懂。出現這種情況，可能是因為文章內容比較多，在其中解釋了分佈式共識算法的方方面面。為了確保普通資質的小學生也可以看懂，我在本文中做了進一步簡化，只集中講述Paxos算法的基礎部分。

Paxos算法是對時間靜止這一九級魔法的模擬實現。一旦理解了這一點，剩下的就只是一些平凡的技術細節了。Paxos中的很多細節本質上都是對模擬失敗時的補救措施和容錯機制而已，它的核心邏輯為：

如果時間靜止模擬成功，則我們可以百分百確認共識已經達成。

如果我們不確定時間靜止是否模擬成功，則重試下一輪模擬。

重試的時候為了避免已經達成的共識被推翻，需要看一眼上一輪模擬的結果，不能選擇與已經達成的共識衝突的值。

為了允許一定的容錯性，多數派成功就算成功。

在建立時間靜止的圖像之後不需要任何超過小學生認知程度的推理能力就可以完全理解Paxos算法。以下是一個詳細的分步驟的推理過程。如果有哪個步驟存在邏輯跳躍，可以留言討論，我再修改一下。

我們要解決的是一個最簡單的共識問題：如何讓分散在多個地方的人共同選擇一個同樣的值。 例如我們如何讓A,B,C三個人都同意選擇值為X。困難在於，你剛讓人送信給A，B，C讓他們選擇值1，他們的回信還在路上，不知道什麼人找上了A，告訴他值應該是2，導致A將自己的決定改成了2。因為A,B,C不在同一個地方，你只能逐一寫信去和他們説，但是每次接到信，再給你回信的過程中，都可能有意外情況發生，總有其他人也試圖寫信説服A,B,C選擇其他的值。因為A,B,C對所有人都是一視同仁的，所以他們如果能接受你的意見，肯定也就能接受後來的其他人的意見，導致他們的意見總是變來變去，無法統一。 （理解共識問題是什麼，以及它有什麼難度，應該只需要小學文化）

如果你會魔法，要避免其他人的干擾就很簡單。可以施展時間靜止魔法，讓所有人的時間都靜止下來，停在t0時刻，然後你直接找到A，和他説值是1， 説完你再去找B，和他説值是1。因為時間靜止的過程中，只有你是自由活動的，其他人的活動都被凍結了，所以不會有任何干擾的存在。當你和A,B,C都説完之後，再讓時間流動起來，這樣A,B,C就在t0時刻統一了認識，認為值是1。 （理解時間靜止可以幫助實現共識也只需要小學文化，看過魔法相關的動畫片可能會有幫助）

雖然我們的世界並沒有魔法，但是我們可以模擬魔法的實現。你可以寫信給ABC（第一階段），信的內容是：請假裝時間靜止在9點鐘。ABC接到信後給你回覆：同意。然後他們將自己的鐘的指針撥到9點鐘。你從ABC接收到回信後，發出第二階段的信：如果時間還靜止在9點鐘，則設置值為1，同時時間前進到9點01秒。如果ABC都回復了你的第二階段的信件，反饋説9點鐘的時候設置值為1成功，你就知道時間靜止成功了，而且ABC的值都設置為了1。 （模擬時間靜止魔法需要分為兩個步驟：一是請求時間靜止，二是驗證時間確實是靜止的。時間靜止之後我們才能幹活，幹完活才能驗證。這個邏輯非常簡單，小學生肯定可以理解）

為了保證模擬的真實性，ABC需要主動維護時間的概念，避免破壞時間的內在特性。首先，時間是單向流動的，如果時間已經來到了9點，所有9點前發生的事情應該都已經發生過了，不可能在9點之後再發生8點的事情，因此ABC如果已經同意時間靜止在9點，就不可能再同意時間靜止在9點之前，比如在8點靜止。第二，如果時間靜止了，則只有發起時間靜止魔法的人可以活動，其他人的活動都會被凍結。所以如果ABC已經同意你的要求將時間靜止在9點了，就不會再同意另外一個同樣時間的時間靜止要求，否則意味着在時間靜止的時候還存在着兩個活動者，這和時間靜止的定義不符合。ABC通過主動忽略那些違背時間特性的事實，從而實現了想象中的時間的單向流動，這可以幫助我們排除很多混亂的情況。 （ABC每次接收到信件都會導致時間前進，因此接收到第二階段信件的時候如果發現時間沒變，則表示在請求時間靜止到設置值的過程中，沒有任何事情發生，也就沒有其他人要求設置值。時間的這個特性小學生應該可以理解）

ABC在同意時間靜止在9點之後，如果有人寫信請求時間靜止在10點鐘，則ABC也會同意這一請求，這是因為ABC對所有人都是一視同仁的，他們只是維護時間概念的單向性，並不會專門支持你的選擇。如果ABC做出了這樣的選擇，則表示前一輪的時間靜止魔法模擬被自動結束了，並沒有完成設置值的過程，而且因為時間已經移動到10點鐘，9點鐘的設值請求會被拒絕。為什麼ABC在接收你的時間靜止請求後，不堅持等待你的第二封信的到來？這是為了系統的容錯性。如果你的信在途中丟失了或者你信寫了一半乾別的去了，那ABC死等你的第二封信豈不是有點冤？所以為了避免中間過程出錯後無法繼續下去，ABC最好的選擇就是接受其他人的第一封信，重新開始新一輪的嘗試。需要注意的是，如果ABC曾經同意過時間靜止，那麼這就意味着在9點鐘曾經發生過時間靜止，即使最後被意外結束，也只是説此次時間靜止沒有成功設置值。前一個時間靜止被自動終止是為了保證時間靜止不會交錯，只能先後執行。 （畢竟是模擬魔法，必然需要考慮到模擬失敗的情況，失敗後只要不產生矛盾，不要有兩個人同時實現時間靜止就可以。一次模擬失敗後可以重新嘗試，小學生也可以理解真正的魔法和模擬的魔法之間的區別）

如果你成功模擬了9點鐘的時間靜止，通知ABC設置值為1，那會不會有其他人後面會再次成功模擬一次10點鐘的時間靜止，將值又改為2？因為我們要實現的是一個最基本的共識算法，它有個額外的技術要求，就是一旦值達成共識，就不允許再被修改（如果允許修改，再考慮到多數派響應，會導致無法判定的情況）。因此我們還需要設計一個額外的機制，來避免上面説的情況。避免的方法也很簡單，就是接收到第一封請求時間靜止的信件的時候，如果ABC發現自己此前已經接受過值了，除了回覆同意之外，還把這個值和接受它的時間告訴新一輪的時間靜止發起者，而發起者如果發現ABC都已經接受了值為1，那麼他不能改變這個值，只能是用值1去繼續完成時間靜止模擬的第二階段。ABC在不同的時刻反覆設置值為同一個值不會產生任何矛盾。 （兩個時間靜止魔法T1和T2肯定不會交錯，一定是先後執行。那麼執行T2的時候只要主動看一下T1的結果，如果T1成功設置了值為1，那麼T2就也要採用值為1，這樣就不會產生T2覆蓋T1結果的情況。寫之前看一下上次讀的情況，這是小學生也能理解的避免衝突的策略）

如果ABC都成功同意在t時刻時間靜止，然後在t時刻都成功設置同樣的值，我們接到三人的回覆後發現他們都在t時刻設置了同樣的值，那麼我們很容易做出判斷：共識已經達成。複雜的情況在於，如果信件中途丟失怎麼辦？如果A出遠門了或者回信很慢怎麼辦？為了提高容錯性，我們可以改變策略，不要求每次都得到ABC三者的響應，而是隻要求多數派（三人中的任意兩人）成功響應即可。此時我們可以驗證，上面的執行策略仍然可以保證達成共識。首先，當t時刻多數派同意接受值為1的時候，t時刻就不可能有另外的值也得到多數派的認可。因為任意兩個多數派必定有交集，例如AB和BC這兩個多數派都包含B，而因為時間靜止才能成功寫入，所以B不可能在t時刻既接受值1，又接受值2（B在不同的時刻仍然有可能接受不同的值），所以只要是多數派成功設置的值，那就一定是在t時刻的一個可以被公認的值。當A和B都承認值是1後，即使信件丟失或者C已經做出了與AB相反的選擇，他的任何行為都不會推翻t時刻的這個結果（多數派承認值是1），這樣只需要用某種方法通知C多數派的結果就可以了。也就是説，當ABC都認可多數派的決定的時候，最終ABC的認識可以被統一為值是1。 （在t時刻多數派接受值是X後，這個X就成為t時刻的共識的值。將共識的定義修改為多數派認可雖然看起來有點繞，但一般的小學生應該還是可以理解的）

第一階段發起時間靜止模擬的時候，我們也可以只要求多數派響應。如果AB成功回覆説同意時間靜止在9點鐘，仿照上一節的推理，顯然就不可能再有另外一個多數派回覆説同意時間靜止在9點鐘。此時，如果A和B都回復説尚未接受任何值，我們就可以任意選擇一個值來進行第二階段的設置值。但是如果A和B其中有任何一個人回覆説已經有人在8點鐘設置了值為2，則需要仔細分析一下：第一個可能是兩人都回復説8點鐘設置了值為2，則此時已經滿足多數派接受的要求，共識已經達成，但是我們也可以選擇值為2，然後繼續執行第二階段，反正重複設置共識值為2沒有任何問題。第二個可能是兩個人的回覆不一致，此時因為沒有讀取到C的結果，所以有可能已經達成多數派一致，也可能尚未達成，在僅接收到A和B的回覆的時候無法確定（正是因為可能存在這種無法確定的情況，我們才要求共識一旦達成就不能被改變）。我們注意到值總是在時間靜止狀態下被接受的，也就是説如果A接受了8點鐘值是1，那麼一定有多數派承諾過8點鐘時間靜止。因為多數派同意的所有時間靜止的時刻可以按照先後順序排成一個序列，而且每個時刻最多隻有一個值，所以對於A和B返回結果不一致的情況，我們只需要選擇時間刻度最大的那個值就可以了。這樣可以保證如果前面一個時刻已經達成共識，後面的時刻一定會選擇同樣的值。 （一旦意識到多數派在所有時間靜止時刻的處理結果是一個單向發展的情況：一開始多數派都沒有值，然後有可能有共識的值，最後是確定有共識的值，那麼選擇最大時刻所對應的值就不是一件很難理解的事情了）

整體的推理策略是先不考慮任何異常情況，總是認為可以接收到所有人的響應，這種情況下只要時間靜止模擬成功，我們就可以確定共識的值被確定下來。然後再考慮容錯的情況，此時我們經過分析，發現只要多數派接受值就可以確定是否成功實現了時間靜止，併成功設置了共識的值。當我們不確定是否已經成功模擬時間靜止的情況下，可以反覆重試直至成功。最後是發現多數派上進行的時間靜止模擬是一個單向發展序列，反覆重試時只要選擇時間刻度最大的值就不會破壞已經達成的共識。

對比最後我們對比一下采用時間靜止這一魔法學圖像的Paxos算法描述和傳統的Paxos算法描述：

準備階段（Prepare Phase）：（1）提議者選擇一個提案編號N，並向接受者的多數派發送準備請求（Prepare(N)）。

對比：提議者選擇一個時刻t，並向接受者的多數派發送時間靜止模擬請求，

（2）當接受者收到準備請求後，如果提案編號N大於該接受者之前見過的任何提案編號，則接受者承諾不再接受編號小於N的提案，並將其之前接受的最高編號的提案作為響應發送給提議者。

對比： 當接受者收到時間靜止請求後，如果發現時刻t是一個未來的時刻，則把時鐘撥到這一時刻，承諾時間靜止在此時刻，並把之前接受過的最大時刻的提案作為響應發送給提議者。

接受階段（Accept Phase）：（1）當提議者從多數派的接受者那裏收到準備階段的響應後，它會將提案內容（value）發送給接受者的多數派，該提案內容為準備階段響應中最高編號提案的內容，如果沒有響應，則可以為任意值。

對比：當提議者從多數派的接受者那裏收到時間靜止請求階段的響應後，它會將提案內容發送給接受者的多數派，該提案內容為請求階段響應中最近一次時間靜止所設置的值（可能實現了共識的值），如果沒有響應，則可以為任意值

（2）接受者收到提案（Propose(N, value)）後，如果提案編號N大於等於該接受者之前承諾的提案編號，則接受該提案，並將其作為已接受的提案。

對比：接受者收到提案後，如果提案中的時刻大於等於該接收者承諾的時間靜止時刻，則表示從承諾的時刻到提案中的時刻，這個接受者的本地時間一直處於靜止狀態，接受該提案。（但是這並不保證多數派都實現了本地時間靜止，只是可能靜止，此時接受者接受的提案是可能實現了共識的提案）

一些細節提案編號的唯一性和遞增：在Paxos算法中，每個提案必須有一個唯一的、遞增的編號，以確保算法的進展。一般的做法是每個發起者具有一個不同的編號k，然後它再維護一個不斷遞增的序列號seq，然後以(seq,k)作為唯一遞增編號。首先比較seq，當seq相等時，可以比較k的大小來確定相對大小。對應到時間靜止的模擬，這個編號就可以看作是一種時刻的表達方式。同一個時刻，不應該有兩個人發起時間靜止模擬請求。另外，即使是有兩個人同時發起時間靜止模擬也不會影響到算法的正確性，在算法設計中要求接受者在承諾時間靜止在某一時刻之後，拒絕後續的對同一時刻的時間靜止請求，這樣在多數派層面，不會有兩個人同時成功實現在時刻t發起時間靜止。對於提案編號的唯一性要求是為了減少衝突，改善性能。即使提案編號不唯一、不遞增也不會產生問題，只是所有具有不唯一、不遞增的編號的提案都會被拒絕或者忽略掉。

多個提議者的問題：在分佈式系統中可能有多個提議者，這可能導致“提案衝突”。採用時間靜止的圖像，首先接受者會拋棄所有時間靜止之前時刻的提案，從而避免了一部分衝突。然後在每一個得到多數派同意的時間靜止時刻，多數派最多隻會接受一個值，這使得多數派層面的衝突圖像變得簡化。因為每個提議者提出的時間靜止時刻是唯一的、遞增的，肯定不會重複，而在一次提議中只會提議一個值，所以每次時間靜止最多隻會設置一個值，如果中途被更新時刻的時間靜止所打斷，則此次時間靜止可能還沒有設置值，或者在局部接受者的本地設置了值。但只要在多數派層面沒有在指定時刻設置成一樣的值，就還沒有達成共識。

失敗和恢復的處理：在分佈式系統中，節點可能會失敗，之後又恢復。前面的分析表明，只要多數派同意時間靜止開始，就可以認為時間靜止開始，多數派認為時間靜止成功，就可以認為時間靜止成功。因此無論節點何時失敗，何時恢復，只需要考慮多數派的彙總意見即可。另外一個隱含的假定是，節點具有記憶能力，如果它失敗了再恢復不應該丟失以前的記憶，也就是接受過的值和承諾過的內容。