paxos和一個實際的key-value分散式系統讀寫的距離

04-20

我隨便的寫一點我個人在工作中實際使用的方案。

首先有2個問題比較棘手也少有被提到：

當前一輪paxos決議總共有哪些節點？
在強一致的要求下，每個節點決議到達哪個步驟後阻塞寫？哪個步驟後阻塞讀？什麼時候可以丟棄寫（新來的決議）？什麼時候才恢復服務。

第一個問題實質上是paxos共識決議發起之前，首先內部需要達成的共識。這個共識在很多文章中被忽略掉了，或者簡單的認為超過1半的節點掛了之後就可以認為paxos共識無法進行下去了（問題是什麼時候才知道有多少掛了？）。事實上我們可以發現如果第一個問題不好好解決，第二個問題的解決會受到極大的障礙。這個問題本身是無法用paxos解決的（他其實是paxos成立的前提：無拜占庭問題）。在實際中，我個人推薦使用獨立的observer或者proxy作為觀察者 來觀察節點數，盡量避免腦裂。

第二個問題我們可以簡單的加一個共識來進行解決：是否所有節點都已經accept了本輪共識？換句話來說，對key x 的讀寫共識可以設計如下步驟：

收到對x的寫請求後，如果發現存在還在決議中的寫，那麼丟棄他並阻塞住返回。讓先寫覆蓋後寫，性能會好些, 因為這樣只有第一個寫需要達到共識，後續請求都丟棄盡量避免再次發起共識決議。如果發生衝突，acceptor自行決定丟棄哪一個，保留哪一個，這個決議方法需要遵守paxos中需要的嚴格偏序關係。在後續步驟成功完成前新來的寫請求都丟棄並阻塞住返回，等到前面的寫共識完成並且可讀之後才返回。
在對x的寫共識完成之前，新的讀請求一直返回舊的value。注意我們把所有的寫操作都阻塞返回了，所以不會產生ABBA問題。
在對x的寫共識完成之後，自動進行「是否所有節點都已經accept了本輪寫共識」共識決議。在這個階段，大家都是提案者（提案會不斷的做並集合併），除非某個節點還沒進入2就收到了3的共識請求那就自動accept。在這個階段，任何新的讀請求都會阻塞，直到本輪共識結束之後才返回新的value；任何新的寫請求都會阻塞，直到本輪共識結束之後才返回成功（實際新的寫請求會被忽略）。這一輪決議需要所有節點（而不是二分之一）都accept了之後才能結束，任何節點需要看到所有的其他節點accept之後才能進入到階段4重新恢復服務能力，所以x被全局鎖住了。如果有節點掛了，推薦用靠觀察者來解除全局鎖狀態。注意不宜輕易使用觀察者來驅動回退，最極端的情況下是某個節點只能和剩餘節點中的1個節點X通信了，需要大家等足夠長的超時時間來等X把這個信息擴散給大家來解除鎖，，無中心的一致性置信擴散是O(n^3)時間複雜度，有中心則是平方複雜度，願不願意設個中心就看你n的數量和你自己的抉擇了。
對於任何孤立的一個節點，倒序返回不同的寫請求的成功，再返回讀請求。我們讓成功的那個寫請求在所有寫請求中最後返回，但比所有的讀請求先返回。

我們注意到實際上每個節點的讀狀態都是

返回舊value ,
阻塞中，
返回新value。

注意任意兩個不同的節點不會分別同時處於狀態1和3之中，因為如上所述從2中脫離進入3需要確保其他節點至少進入2了（如上所述，「是否所有節點都已經accept了本輪寫共識」這輪共識必須全局accept了之後才能），所以是強一致的。「是否所有節點都已經accept了本輪寫共識」這就需要我們本文開頭提到的共識：「當前一輪paxos決議總共有哪些節點？」

注意「先寫覆蓋後寫」這並不奇怪。在cpu多核亂序發射中，在無鎖的情況下A線程先寫 B線程後寫同一個地址（這個「先後」假設是通過某個「幽靈」觀察出來的，因為沒鎖或者同步原語的情況其實很難定義線程間的「先後」），最終讀出來的結果可能是A線程的結果，這並不違反通常的多核編程語義。這樣的好處主要就是在寫頻率較高的時候，提升了寫達成共識的速率。為了和通常的編程語義不混淆，我們實現有效寫比無效寫後返回即可。

注意如果運維增節點，新節點本身需要先跑齊數據，同時（通過觀察者）接收寫共識請求（這下知道有觀察者的好處了吧，因為第一輪共識需要通過觀察者，這樣觀察者是有全量寫請求的。），跑齊數據再開始把節點加入觀察者返回的「所有節點」結果。

如果運維刪節點，需要先從觀察者中去掉自己，再等待所有在進行中的共識完成。