ZooKeeper靈魂----paxos小島
近期拜讀了Leslie Lamport的1998年發表的大作《The Part-Time Parliament》，對分散式有所瞭解的人，應該聽說過這篇論文。我在之前看過多個版本的個人理解的文章，自己一直沒有看過原文，看完以後才知道，這篇論文是對考古發掘的倫理做了描述，同時加上作者的一些推理，遺憾的是考古發掘並沒有展示出完整的Paxos協議，缺失很多細節，所以這不是一個完善的分散式資料庫解決方案，更像是一個待完善的系統原型。
論文中有很多數學推理過程難度很高，因個人能力有限，只能根據自己的理解大概描述一下，希望沒有誤解和曲解作者原意，也歡迎大家指正。
先講故事
故事發生在一個商業繁榮、政治精明的小島(Paxos)，這裡建立了政府國會取代了之前的神權政治。小島上所有法令(Decress)都由議會的議員(Legislator)表決通過，然後由議員記錄在各自手中的律薄(Ledger)上。但是由於這裡商業繁榮，沒有人願意做專職的議員，都是由小島居民兼職的。由於平時工作很忙，所以兼職議員們會經常進出國會大廳，甚至中途去出海捕魚，半年後再回到國會大廳。
好在兼職議員們相互高度信任，所有提議都會被通過，不會有人反對(關於這點，不太明白當時小島就是這樣，還是作者有意這樣描述)。並且，兼職議員們只要待著議會大廳，總會積極的完成工作。
小島上的Paxos演算法經歷了幾個階段的發展。下面分階段介紹：
階段一：早期神會
由於所有議員可以隨時離開議會大廳，所以，一個法令如果要獲得多數議員的通過，就需要對一個法令發起多輪投票，為了保證法令有序通過，數學家們制定了3條規則：
B1(β): 每一輪投票都有一個唯一的編號(假設是遞增的)。
B2(β): 任意兩輪投票的法定人數集合(指：在大廳中但是不一定完成投票的議員)中，至少有一個重合的議員。
B3(β): 投票集合β中的任意一輪投票V，如果本輪法定人數集合的議員參與了以前的投票(並完成投票)，那麼這些以前的投票中最近一次投票(最大編號)的法令，和本次投票的法令的編號相同。
註解：
1.原文解釋B1~B3規則時使用的是「牧師」(神會階段叫牧師，國會階段叫議員)，為了避免大家混淆和誤解，本文全部使用議員。
2.這3條規則還不能指導神會的正常運轉，我們先理解規則，不考慮尚未提及的問題。
3.B1(β)就不用解釋了。B2(β)的意思就是參與投票的議員需要過半數，以保證投票的一致性。
3.B3(β)是比較難以理解的，原文中有推導過程，但是本人能力有限，沒看懂，呵呵。這裡說一下我的理解：如果法令是按順序通過的，並且每一個通過的法令必須經過大多數議員投票通過，那麼，如果本輪投票有效，就意味著本輪有大多數議員投票，並且投票的法令就是上一次待通過的發法令(因為更早的法令已經投票通過了)或者無待投票的法令(那就可以發起新的投票了)。這些猜測在後面的文章中會慢慢打開來講。
階段二：初級協議
在神會階段的基礎上，發展出了初級協議。原文中用6個步驟描述了初級協議的投票過程。但是我個人不習慣於他的描述方法，所以這裡嘗試使用比較大眾化的語言解釋一遍。
首先，假設每一位議員的律簿的正面用於按照順序記錄已經通過的法令，比較正式，不可更改。律薄的背面(便簽的作用，可以擦寫)用於記錄不連續的法令，以後再謄抄到正面。另外，律薄的背面還要記錄幾個關於投票過程的重要信息：
v: 議員自己上次完成投票的投票編號
b: 新一輪投票中接收到的新投票編號
下面就講解這6個步驟：
1.議員p根據自己律薄的記錄，選擇一個新的投票編號b(b>v)。然後給大廳的其他議員，發送通知消息NextBallot=b。
2.議員q收到p發送的消息以後，找到自己在b之前參與的投票編號v(b>v)，並返回v；如果不存在v就返回null。返回消息LastVote(b)=v 。注意，此時q會鎖定v~b之間的投票，即：議員q只會對b進行投票。
3.議員p收到大廳內所有議員的step2響應匯總成一個集合V，根據B3法則，選擇出本輪投票的法令d，然後，給大廳內所有議員發送開始投票的消息BeginBallot (b, d)。
4.議員q開始表決(投票就表示贊同)，修改自己律薄上記錄的上次投票編號v=b。如果不表決可是因為：收到另一個議員p1發起的新投票編號b1(b1>b)，這樣在step2中鎖定範圍包括了b，所以，此時不能完成b輪投票；或者因為睡著了而沒有投票等等。
5.議員p收到大廳所有議員的投票，那麼法令d表決通過，在律薄上記錄法令d，然後發送Success(d)消息。
6.議員q在律薄上記錄法令d。
註解：
1.步驟2有個注意點：議員p發起的b輪投票，議員q在step2鎖定了v~b之間的投票。假如此時另外一個議員p1發起了b1輪投票(b1>b)，那麼議員q在b1輪的step2就會鎖定v~b1之間的投票，然後，如果議員q收到議員p的b輪step4的請求，那麼他將不會投票，以免違背對於議員p1的承諾。
2.根據步驟1-6，通過無限輪次投票，最終會通過議員律薄上待處理的所有法令。但是，遺憾的是，文章到此還沒有描述新的提議是如何進入投票環節的，暫時賣個關子。
3.由於任何牧師都可以隨時發起投票，所以這個協議不能保證每個牧師新發起的編號是不重複的，所以，後面引入了總統的角色。
4.由於議會裡面都是一羣不靠譜的人，所以可能出現：重複執行某些步驟、消息重複傳遞、消息丟失。但是，這些都不會產生問題，大家自己理解，就不一一解釋了。
階段三：基礎協議
在初級協議的基礎上，增加了以下限制：
1.任意時間點，只能由一位牧師發起一輪投票。
2.在step2完成以後，議員q將鎖定所有小於b的投票，這比初級協議更為嚴格。
註解：
這個階段新增的兩個約束，降低了多個議員同時發起多輪投票的混亂場景，保證了投票過程的一致性。
階段四：完整的神會協議
基礎協議保證了一致性，但是無法保證投票的可進展性，如：議員p什麼時候發起投票，如果一直傻傻的等著，那麼什麼法令都無法通過；如果他是個急性子，未等到上一輪投票結束，又發起新的倫理，由於step2的鎖承諾的原因，新的投票會阻塞舊的投票，不斷發起新的投票，最後的結果還是沒有法令通過。那麼，完整協議需要解決的是協議的可進展性問題。
首先，需要選擇一個總統(president)。同時，假設經過一段時間後，會議沒有人員進出了，那麼就認為接下來的T分鐘內(原文未講解T的制定規則)通過選舉只會有一位總統。選舉的方式就是每隔T-11分鐘(11分鐘是一個議員處理消息+傳遞消息時間，也就是保證在T時間結束之前，完成一次名字交換)議員把自己的名字告訴大家，如果在T分鐘內，仍然沒有收到比自己更大的名字，那麼他就認為自己是總統。
然後，總統什麼時候該發起投票呢，投票頻率怎麼樣呢，所以，總統需要知道每個步驟需要的時間。假設前面提到的6個步驟，每個議員處理消息的時間至少需要7分鐘，消息傳遞的時間至少需要4分鐘。那麼全程至少需要需要：7分鐘*6個步驟 + 4分鐘*5次消息傳遞=62分鐘。但是，完成一輪投票的時間不是T-11+62分鐘，為什麼呢？接著說。
完整協議沒有機制保證總統的律薄上一開始就記錄了最新的法令條紋和投票信息，那麼按照B1規則，選出的投票編號b，有可能不是最大的，所以在step3之後，發送投票表決的時候，會遭到其他議員的反對(step4)，告訴總統最新的投票編號是b1(b1>b)，所以，完整協議完成一輪投票的時間，可能是T+99(44分鐘是總統收到投票編號太小的消息的時間，55分鐘是完成step1-6的總時間，但不包括step6本身執行時間)，為什麼說可能呢，因為這裡的44分鐘不是必須的。
最終，只要議會大廳的大門關閉T+99分鐘，就一定可以通過至少一部法令。
階段五：多法令並行的國會
1.自動補齊法令：總統在step1選擇新投票編號b的時候，找到自己律薄中編號最大的法令n，然後發送NextBallot(b,n)給其他議員。當其他議員收到該消息以後，議員會返回自己律薄中紀錄的>n的法令，同時向總統請求自己缺少的法令；當然，如果議員律簿中最大的法令，那麼返回正常的LastVote(b)消息。（階段四的投票編號衝突需要等到step4才發生，step5才能被總統感知，所以，這裡的改進是非常有必要的。）
2.如何引入新法令：總統引入新法令前，需要學習一個多數集合(過半)的議員已經投過票的法令。所有通過的法令至少被一個多數集合的議員投過票。所以，總統可以查看自己的律薄就知道當前的法令是否已經全部通過，然後就可以提議新的法令了。
3.簡化的投票：如果會議大廳的大門關閉，一段時間內沒有人員出入，那麼總統和議員是固定的，這時候的投票就很簡單了，只需要step3-5即可以完成一輪投票。甚至總統可將上一輪投票的step5消息和這一輪的step3消息合併為一個消息發送，這就變成了是一個高效的議會。
階段五：多法令並行的國會
1.自動補齊法令：總統在step1選擇新投票編號b的時候，找到自己律薄中編號最大的法令n，然後發送NextBallot(b,n)給其他議員。當其他議員收到該消息以後，議員會返回自己律薄中紀錄的>n的法令，同時向總統請求自己缺少的法令；當然，如果議員律簿中最大的法令，那麼返回正常的LastVote(b)消息。（階段四的投票編號衝突需要等到step4才發生，step5才能被總統感知，所以，這裡的改進是非常有必要的。）
2.如何引入新法令：總統引入新法令前，需要學習一個多數集合(過半)的議員已經投過票的法令。所有通過的法令至少被一個多數集合的議員投過票。所以，總統可以查看自己的律薄就知道當前的法令是否已經全部通過，然後就可以提議新的法令了。
3.簡化的投票：如果會議大廳的大門關閉，一段時間內沒有人員出入，那麼總統和議員是固定的，這時候的投票就很簡單了，只需要step3-5即可以完成一輪投票。甚至總統可將上一輪投票的step5消息和這一輪的step3消息合併為一個消息發送，這就變成了是一個高效的議會。
階段六：更進一步的發展
當管理Paxos小島變得更為複雜，一些新的問題就隨之而來了：
1.關於選擇一個新總統的問題：議員z出海捕魚半年後回到議會大廳，他立刻當選為新的總統(因為他的名字的字母順序是最大的)，那麼在他開始發起投票之前，必須先學習這半年的法令，這將是一個漫長的過程，而在此期間議會一直處於等待狀態。
2.長長的律薄：經過長期積累，律薄會變得很長。而同一件事情(如：羊毛的價格)也會被不斷更新，事實上大家只需要知道最後一次通過的相關法令即可。
3.官僚化：原文中提的這一點，我覺得和「法令的學習」是一致的。
4.法令的學習：隨著法令的增加，同一件事的新舊法令也越來越多，如何保證兩個農民能學習到一致的法令(或者有分歧時如何統一)，這就需要為每一個領域指定一位議員做該領域的專家，負責解釋該領域的最新法令。
5.不誠實的議員和無心之失：這兩種情況都會導致議員之間法令的不一致，如何保證議會系統的自穩定性，很不幸，暫時還沒有被發掘。
6.選舉新的議員：由於法令需要過半數議員的同意才能通過，如果當前法令選舉了大量新的議員，而這些議員又無法參加議會(如：已故、長期出海等)，這樣議會就停擺了。
註解：
以上幾點分別對應分散式資料庫裡面的一些問題處理：如果新節點的加入、MVC、讀寫一致性等等。
與分散式資料庫的對照
議會議員-------數據處理節點
小島居民-------客戶端
當前法令-------資料庫狀態
Paxos協議------三階段提交
轉載自Paxos小島的故事(The Part-Time Parliament讀書筆記)
推薦閱讀：