標籤：

使用Paxos前的八大問題

01-26

相信不少做存儲或者資料庫的人已經被Paxos轟炸過過一輪，我也不能免俗，最近也儘可能的翻了一些Paxos的文章，看了這些文章後，我個人感覺最好的理解方式是將Paxos要解決的問題具體化，細節化，然後，我想任何一個有著豐富經驗的同學都能不依賴Paxos的任何資料很好的回答這些問題，這些答案的形式化綜合起來就應該是網路上的各種Paxos解釋。我相信問題導向逐步推導的方式比衝上去學習Paxos文章裡面的流程有趣一些，同時，沒準還可以發現一個更適合自己業務的改進。

問題一：Paxos[2]解決什麼問題？

在保證一致性的前提下，提高系統的可用性。系統中破壞可用性的場景包括，機器down機（硬碟等各種硬體損壞類比），機器間網路丟包、高延時。解決這些問題的根本思路是多副本，這樣一個機器down其他副本還可以使用。多副本早已被大家廣泛使用，之前最主要的思路是主備機制，又叫做primary-second，或者master-slave，核心思路是主承擔所有的操作，並定期非同步將主上面數據的變化同步到備。在主備系統運行過程中，如果備出問題，服務不受影響；如果主出問題，就切換到備，因為主總是比備多一點數據，所以這個過程中可能丟數據。丟多少數據呢？這取決於主隔多少時間能將最新的信息同步到備，如果主每隔1小時就能保證1小時前的數據完全到備，那麼最多丟一個小時。那麼，丟數據的量能縮短嗎？5分鐘？1秒鐘？

對於一個繁忙的資料庫系統，1秒鐘的數據丟失可能也是災難，那麼最小粒度是什麼？就是per request，即主上面每一個變化備都能同步感受到，那麼主down掉的時候，備能無損的接管服務，這就是MySQL 主備強同步的思路。但是，如果每個request都要備參與，就意味著這個系統如果備掛了就不可服務了，這也是線上恐怕很少有人選擇MySQL主備強同步的理由，怎麼辦？多加幾個備來降低備不可用對系統的影響。

多加幾個備之後，就帶了兩個問題，

1. 這些主備之間數據一致性怎麼解決？Paxos是一種思路，即多數派同意的就是正確的

2. 那如果主掛了呢，這裡有兩種選擇，一種是任何人在任何時候都可以是主，這時候就沒有主備之分了，這是basic paxos[2]的思路；另一種思路是，主掛了就讓某一個備成為主，系統可以繼續服務，這是viewstamped replication[3]、Raft[4]、Zab[5]（廣義上可以算Paxos）的思路，在multi-paxos[6]裡面也提到了使用leader減少prepare message，leader切換條件更靈活，也可以歸類為這個序列。

上面兩個問題就是Paxos要解決的核心問題，即Safety（數據是一致的）和Liveness（系統總是能繼續前進）。

問題二：狀態機(Replication State Machine, RSM)和一致性有何關係

狀態機有一個很好的特性：任何初始狀態一樣的狀態機，如果執行的命令序列一樣，則最終達到的狀態也一樣。而存在多個參與者的系統的一致性可以理解為，系統多數成員就某一系列決議得到了相同的判斷結果，使用狀態機來描述就是，如果在某一個時刻系統不再接受外部輸入，則系統中存在多個參與者具有完全相同的狀態機。上面兩點結合在一起，就得到系統參與者保持一致的關鍵是，起始狀態完全一致，執行命令序列完全一致，那麼系統的行為就是可以重複的。這跟單機資料庫系統可以類比，資料庫重做日誌就等於命令序列，資料庫數據存儲就等於狀態機，唯一不同的是單機資料庫日誌序列化lock一下就可以做，那麼多個參與者之間如何讓日誌序列化呢？這就是Paxos等一致性協議致力解決的具體問題，即如果狀態機狀態的改變是由命令1...N組成的，那麼Paxos需要保證對任何一個1<=k<=N，命令序列的內容被系統中絕大部分的參與者同意。這個k可以稱之為log position，log index，不同文章叫法不同。這裡我們對上面問題一的一致性問題進行了具體化，只要保證了大部分參與者執行的命令序列是一樣的，系統就是一致的。再具體化一步，保證命令序列中每個序號對應的命令是一樣的，就能保證命令序列是一樣的。Paxos的責任就是保證：在一個命令序列中，同一個序號下面對應的命令內容是一樣的。[7]的描述還是比較清晰的。

問題三：Paxos如何保證多參與者同一個序號對應同樣的命令內容

這是各類Paxos演算法的核心，不過我認為在準備動手寫代碼前這是最不重要的一部分，因為除了最開始的paxos文章說的比較模糊，後面出來的都把這一塊描述的異常清晰，甚至各種優化都幫著想好了。這裡面理解下面幾點就行，

  1. 目標：讓第k個命令序號執行x命令（x比如是inc）

  2. 動作：給所有人發請求，<no, k, x>，no每次都要漲，這個好理解，否則一個網路上漂了半天的包被伺服器收到怎麼辦？

  3. 結果：如果大部分參與者都同意，就確定了<k, add>的對應關係；否則，每個Paxos演算法都有一系列的規則來讓系統一定能達成一個共同的決議，具體參考每個演算法；

問題四：leader選還是不選

網上見到有人爭論basic paxos不用選leader，對運維更友好，對網路抖動容忍度高等等，這個更像是一個工程實現問題，而不是理論問題。在一個多參與者的系統裡面，如果每個人都提議，那麼顯然衝突的概率是很大的，衝突了就要重新開始新一輪提議，這會導致很低效，就好像高速路上8車道變成了1車道，這時候誰先走就是一個問題，如果沒有警察叔叔，必定亂成一鍋粥，在一個高壓力的系統中問題類似。選了一個leader之後，leader知道沒人跟自己搶，就可以省不少事，事情省了，系統也簡單了，這就是Raft的思路。同時，如果有了leader，批量確認命令序列也成了可能（否則同一個paxos group衝突肯定高的嚇人，有了警察叔叔每個車道可以一次放行20輛，沒有警察叔叔一次放20輛可能很快就會因為事故全部堵死），這就是multi-paxos，即一次確認多個命令。選leader不是沒有弊端，如果leader掛了，這時候系統是不能服務的，必須等新的leader選出來，這個一般幾百毫秒搞定。那麼，leader掛的時候如何降低對服務的影響？就是將paxos group做的精細一點，一個leader掛了，隻影響這個paxos group，其餘正常服務。如果碰到leader節點網路抖動，也可以迅速切換，減小影響。整體來看，選leader是較好的做法，人類社會不也需要leader嘛。

問題五：機器down掉後，新加入的機器是否能立刻服務

這點取決於狀態機如何維護，是整個系統作為一個狀態機還是每個參與者都是一個獨立的狀態機。如果整個系統被當做一個獨立的狀態機，那麼任何機器加入進來都可以立刻服務，因為系統的狀態是完整的，這也是basic paxos能達到的效果。如果系統中每個參與者都被當做一個獨立的狀態機，那麼任何新機器加入進來必須先從其他機器獲得一個過去的狀態（snapshot），類似資料庫備份裡面的數據文件，然後執行這個狀態之後的命令，類似執行資料庫重做日誌，等到狀態已經追趕上系統中的多數參與者，就可以提供服務，這是Raft的效果。從描述看，Raft似乎弱了點，但是本質上兩個是類似的，因為basic paxos將整個系統視為狀態機增加了複雜性，且在參與者連續down的場景中，一樣不能很好的解決，也需要儘快讓新機器追狀態，以達到每個命令都有多replica。

問題六：paxos group如何隨著新節點加入而改變

這個問題被稱為view change，就是說參與者變多了，比如1 2 3變成1 2 3 4 5，或者參與者要換一批，比如 1 2 3換成4 5 6，這個問題Raft處理的最好，簡潔明了，說簡單點就是在新舊config交疊的時候，leader必須得到新舊兩個group的認可，這就避免了多leader腦裂的問題。viewstamped replication第一版在變配的時候要停機，revised解決了這個問題；paxos make simple裡面的N+alpha方案不太好懂，按照文中的描述，在極端情況下有正確性問題（練習題[10]裡面最後的題目，當然，工程實現上可以繞，這本來就是一個低頻動作）

問題七：不同方案哪個資源會首先成為瓶頸

在leader方案中，最容易成為瓶頸的是網路，因為從方案設計上使用的就不均衡，leader接受請求後轉給其他參與者，出口帶寬會承壓，這時候可以選擇chain forward，讓其餘參與者也承擔網路流量。磁碟方面還好，畢竟都上paxos了，PCIe介面NVME SSD盤應該少不了，秒幾十萬寫不是事，還有像Oceanbase[11]講的，log落盤就返回的話磁碟更不是事。現在CPU也越來越強大，配合上各類專用處理器，牛的不行。

問題八：讀的時候怎麼保證一致性

這個問題在各個Paxos文章裡面敘述的不太明顯，其實是一個很難的工程問題。basic paxos裡面沒有專門提，我揣摩意思就是讀跟寫一樣，走完整的多參與者決策流程，這個肯定能讀到一致的數據，但是性能恐怕不會好。在leader選舉的方案裡面，也不是件簡單的事情。直接讀leader的話，因為leader可能是過期的，那麼可能導致讀到的數據是過期的，這時候又要給leader加上lease機制，而這個機制更進一步限制了leader掛時候的可用性恢復。這裡或許提供兩類介面是一個明智的選擇，比如

1. 非一致讀：可能讀到過期數據，這時候讀任何一個參與者都行，不過也不能太隨便，client可以提要求，該參與者與leader的距離不能超過一個閾值或者已經apply到RSM的序列號至少得大於client曾經寫過的命令序列號。

2. 一致讀：只能讀leader，或者為了負載均衡，leader選一個狀態一致的參與者也行。

以上是近來研究paxos的一點記錄，算是一個總結，歡迎交流微信teaworldvc20。

  1. 封面圖片來自：cs.rutgers.edu/~pxk/rut

  2. research.microsoft.com/

  3. 101.96.10.62/www.pmg.cs

  4. zh.scribd.com/document/

  5. tcs.hut.fi/Studies/T-79

  6. research.microsoft.com/

  7. ramcloud.stanford.edu/~

  8. ramcloud.stanford.edu/~

  9. ramcloud.stanford.edu/~

  10. ramcloud.stanford.edu/~

  11. zhihu.com/question/1984

微信鏈接：mp.weixin.qq.com/s?

weixin.qq.com/r/tTvo7Bb (二維碼自動識別)

推薦閱讀：

※Paxos演算法詳解
※paxos演算法第二階段的必要性是什麼？
※如何評價阿里最近推出的paxos基礎庫？
※如何淺顯易懂地解說 Paxos 的演算法？

TAG:Paxos | 分布式一致性 | 分布式数据库 |