摘要：底層網絡有一個，負責為每個消息加上一個序列號，為了防止故障或者失效，需要一個來進行監控。且論文作者在真實的環境下測試得到，對于這樣一個三層胖樹結構的網絡，的情況下，添加一個序列號并不會增加額外的延遲開銷，的情況下，只有的延遲。

??首先標題有點嘩眾取寵之嫌，但是暫時想不到更加合適的標題，就姑且這么使用吧。分布式共識算法一直是一個熱門的研究話題，之所以要分布式共識，無外乎就是單點服務容易宕機，異常，出錯，從而導致系統不可用，于是就有了備份容錯的機制，那么一份數據多地(location)存儲，如果不發生修改操作那就無需一致性協議的引入，但是這僅僅是理想情況，真實的應用中絕大多數都是需要執行更新操作的，這才有了分布式共識的需求。目前最為認同的共識算法就是lamport大神在98年發表的論文中提及的Paxos協議(然而由于太難以理解又在01年發表了paxos made simple)，即使過了這么多年，Paxos依然難以理解和難以實現，工程實現大多都是精簡版，最為出名的也有Raft，以及Zookeeper中的Zab。筆者之前讀過paxos made simple，雖然能理解，但是總覺得有點一知半解(也寫了一篇小博客理解paxos協議-分布式共識算法（consensus）)。最近剛好看了一篇新的論文，結合Paxos來重新梳理下什么是分布式共識算法，怎么實現分布式共識算法。

??Just Say NO to Paxos Overhead:Replacing Consensus with Network Ordering 這篇論文是2016年osdi上的一篇論文，第一作者是華盛頓大學計算機系統實驗的一個PHD。標題看上去也非常的奪人眼球，拜讀完之后，對于作者的想法還持有一點疑惑，但是這篇文章很好的闡述了怎么實現分布式共識算法，對于理解Paxos有難度的同學不妨先去閱讀下這篇論文，能更好的去理解，下面筆者就用純大白話的形式來一步步說明分布式共識算法。

??lamport大神在其論文中也提及到，所謂的分布式共識要達成的目標：

達成一致的結果一定是由某個進程或者某個應用提出來的，而不是事先約定的結果。

最后要達成一致表明只有一個值能被選中。

只有已經被選中的值才能被其他不參與決策的人(learner)知道。

??如果直接從上面的話來理解，那么就會陷入一個誤區，或者說，看不明一致性的完整過程，換一個角度，我們如何來保證多個replica一致性呢，很簡單，目前最為流行的機制就是State Machine Replication(aka SMR)。SMR是這么定義的，(1).初始state要相同，(2).對于同一個state，給定相同的輸入參數，執行相同的操作，輸出結果是相同的。所以用SMR來保證一致性的要求就是，相同的狀態，輸入相同的參數，執行相同的操作。相同的狀態屬于上一步的結果，所以約束其實就是兩個，相同的參數(argument)，相同的操作(operation)，說到底，paxos那些復雜的過程就是為了保證這兩個約束條件。

??相同的參數：看起來簡單的約束，實際實現并非易事，首先在異步網絡的情況，消息亂序情況就嚴重干擾了這一約束，你想想看，節點1先執行request n后執行m，節點2先執行m后執行n，結果能一樣嗎？那么paxos是如何保證這個有序性的呢？Paxos在其運行過程，一旦提案p被大多數的acceptors接受，那么后續提出的更高編號的提案都應該包含這個p，看明白了嗎，就是一個提案未被確認執行前，所有的acceptors都不允許新的提案(這里的新的提案指的是value不同的提案)發生，這就間接解決了亂序的問題，paxos保證所有的節點在每一次paxos提案期間只能執行一個提案(同一個value)，從而來保證參數相同，消息有序。

??相同的操作：客戶端發起狀態修改必然會帶著一個operation的請求(實際工程中實現是通過調用不同的接口如insert，update，delete等)，那么當這個請求廣播給所有的節點，那么執行自然是相同的操作。問題就在于異步網絡無法保證可靠性，假如部分節點網絡失效，有些沒收到request，自然不會去執行。那么一部分節點執行，一部分節點不執行才是導致操作不同的原因(commit和do-nothing)。體現在paxos就是一旦經過大部分的acceptor同意的提案到被learner學習的過程。工程上常見的實現方法是用leader來管理復制日志來實現操作相同的。

??有了上述的認知，再來看一致性，是不是就會覺得明朗許多，本文標題中的另一個名字是NOPaxos，自然重點就是講解這篇論文了，下面就來看看論文的作者是如何實現分布式共識算法。

??聲明：這里不是純翻譯論文，如果想了解全部的過程，可以點閱前面的鏈接查看。 傳統的一致性算法如paxos是把上述兩個約束條件放在應用層去實現，這樣的好處是不依賴于特定的網絡結構，但是同時也有一些弊端，首先是一致性的時間比較長，性能較低，第二是實現難度比較大且復雜。作者另辟蹊徑，如果網絡層能保證消息有序，那么paxos前面整個投票過程就無需存在了，這樣就把一致性的責任分攤在了網絡層（并非指TCP/IP協議棧中的網絡層）和應用層。論文主要做了四方面的工作：

定義了一個有序不可靠的廣播模型(ordered unreliable multicast model，OUM)，能提供強有序的package，但是不保證package一定被接收/處理。

描述了如何實現這樣一個OUM模型，提供了三種不同的實現方案。

介紹應用層的NOPaxos協議，如何在應用層協調state一致性。

為上述的實現做實驗驗證。

??按照論文本身的說法，最簡單的實現，就是給每個消息增加一個單調遞增1的序列號(sequence number)，這樣，節點在接受到消息的時候，就能知道每個消息的先后順序了。除此之外，這一層無需再提供任何的保證，這樣使得設計和實現都比較簡單。簡單的情況下，OUM為每個request都添加一個sequence number，應用層通過libOUM調用接收到這個request之后，判斷是否是當前想要接受的信息。只要sequence number是遞增1，就能判斷出是否亂序或者正常情況。如果出現了跳躍，比如當前需要的消息序列號是n，然后卻接受到了一個序列號為m(m > n)的消息，那么上層應用就知道n-m中間的消息是丟失，進而執行其他操作，這樣保證每個replica接收到的消息是相同的順序。下圖是NOPaxos的一個整體架構：

??每個客戶端都需要集成兩個庫，一個是用于處理網絡消息的libOUM，一個是用于協調多個replica之間操作的NOPaxos。底層網絡有一個sequencer，負責為每個消息加上一個序列號，為了防止sequencer故障或者失效，需要一個controller來進行監控。總的來說，這個架構總共有三種角色，controller，sequencer，client，其中client有兩種協議OUM和NOPaxos。下面就一個個的來介紹這些角色分別承擔的功能和用途。

1. sequencer

??正如前面所說，sequencer的功能很簡單，就是為每個消息添加一個序列號，這個序列號必須是單調遞增1的。論文中，作者提供了三種不同的實現方式，分別是，基于可編程的交換機內實現，基于middlebox原型的硬件實現，純軟件實現。在介紹這三種實現之前，先來考慮這樣一個網絡結構，

??上圖是一個三層胖樹的結構3-level fat-tree，根據設計，所有的客戶端發出來的信息都要經過sequencer，如果原本客戶端與replica在同一個局域網內，這樣的設計首先會導致消息路徑增長，因為消息首先要走到sequencer，再從sequencer轉發回來，明顯消息走過的路徑就變長了。所以這里對于sequencer最合理的位置，就是放在root switch（至于為啥是放在這個位置會使得性能最好，可以參考網絡拓撲fat-tree的設計思路，筆者對于網絡拓撲沒有深入研究，這里就不展開）。且論文作者在真實的環境下測試得到，對于這樣一個三層胖樹結構的網絡，88%的情況下，添加一個序列號并不會增加額外的延遲開銷，99%的情況下，只有5us的延遲。因此，增加這樣一個sequencer并不會帶來性能的下降（論文解釋的原因是，不管存不存在這個sequencer，大部分的package都是需要走到root-switch才能達到大多數的group）。sequencer的位置確定了，那么接下來就是實現了：

in-switch：理想情況下，如果有一個可編程的交換機，那么這個交換機可以直接拿來做sequencer，因為交換機本身就是優化設計來作為消息投遞，拆包解包的。然而這些交換機大部分都是商業閉源的，市面上比較少見很難買到，作者的實驗是在Intel的Arista7150交換機上實現的，基本能達到0延遲。不僅如此，交換機本身的計算模型是非常有限的，且只能用類似于P4的編程語言開發。

Hardware Middlebox Prototype Sequencing：相比于可編程交換機來說，基于SDN的OpenFlow交換機實現難度降低了很多，可以采用C語言開發，根據作者的實驗，這種情況下能99%的case有16us的延遲。

End-host Sequencing：使用普通的終端機（如果linux server）來作為sequencer，這種實現最為簡單，但是性能最差。畢竟交換機是數據鏈路層或者網絡層工作的，而終端機是應用層的級別了，且交換機本身是專門用于package轉發和處理，性能差距自然很明顯。

2.controller

??有了sequencer自然能實現消息有序性，但是同時也引進了一個問題，sequencer是一個單節點，一下子就使得整個系統脆弱了很多，雖然說發生故障的概率不高，但是一旦發生故障，整個系統不可用不說，還可能出錯。這個時候就需要controller出場了，controller的主要目的是監視sequencer，一旦發現sequencer不可用或者不可達，則會選擇一個替換的sequencer，并更新其路由表。這一過程引入一個新的概念，session。每當一個sequencer失效了，需要挑選新的sequencer的時候，首先重新選定一個session number，并將信息更新到新的sequencer上。這樣用一個session的概念就能來維護跨sequencer的消息有序了（會在消息頭上加上一個二元組 [session-number, sequencer-number] ）。一旦libOUM接收到了一個更高編號的session number，則說明，舊的session已經失效了，但是此時，libOUM并不知道是否有丟失舊的session中的package，所以不能返回一個drop-notification，只能返回一個session-terminated，由上層應用去決定改如何處理。至于上層如何處理，后面會講。這里session number可以采用本地時間戳，或者將session number持久化到磁盤然后遞增。此外controller的可靠性可以由多個節點來保證，controller選舉sequencer的算法甚至可以直接使用paxos或者raft等，畢竟節點失效并不是一個經常發生的事。

??NOPaxos從架構圖中可知，屬于一致性協議最上層的協議了，通過調用底層的libOUM保證消息有序，剩下的如何保證操作一致就是在這個協議中實現的。下面會分別介紹不同的情況下，NOPaxos是如何執行的，首先講明一些概念和變量：

總節點數為2f+1，f是最多允許fail的節點數，這個就不必說了，paxos也是這么限制的，最少要半數以上節點同意提案方可commit。

replica number：每個replica（每個副本稱為一個replica）都有一個number，

status：每個replica都有一個status，normal或者viewchange

view-id：視圖的id，是一個二元組，[leader-num, session-num]，這的leader-num實際就是leader的replica number，session-num就是前文中OUM層的session number

session-msg-num：在一個session內，每個message都有一個單調遞增1的序列號，這個就是該序列號

log-slot：log用來appendrequest操作，log-slot用來表明這個操作在日志中的位置。

sync-point：最新的同步點

??系統運行只有，協議的運行過程，只會出現四種不同的情況，正常的操作，出現消息丟失，發生視圖轉換，系統狀態同步。下面就分別講解這四種情況下接收到不同消息時該如何處理，另外關于leader選舉可以參考viewstamped-replication。

1. Normal Operation

??正常的情況下，客戶端廣播(broadcast)一個request的消息（消息內容為，[request, op, request-id]，其中request-id是用于response的時候，判斷是哪個消息，理解為消息的unique key）當replica接受到這樣一個消息的時候，首先OUM帶過來的一個session-msg-num判斷是不是自己正在等待的消息，如果是，則遞增session-msg-num并將op寫入日志（注意，這里并不執行）。如果replica是leader的話，那么就執行這個操作，并寫入日志。然后每個replica會回復客戶端一個消息（內容為，[reply, view-id, log-slot-num, request-id, result]，這里的result只有leader才有回復，其他為null）。客戶端會等待f+1個reply，能match上view-id和log-slot-nums的回復，其中必須有一個是leader，如果沒有接收到足夠的回復，則會超時甚至重試。上述是正常的情況下，正常的處理過程。【問題：如果leader提交了，然而client并沒有收到f+1個reply，這個時候怎么辦，沒有任何機制能反駁leader？raft的機制就是確認replica已經寫入了日志才commit的，所以他這里沒寫明我也不明白是為啥】

2. Gap Agrement

??假如此時libOUM本來在等待session-msg-num編號的請求，卻來了一個更大的請求，說明，中間發生丟包了。那么此時，libOUM就會向上層返回一個drop-notification，告知session-msg-num丟失了（同一個session內）并且遞增session-msg-num。如果是非leader接收到drop-notification，那么可以向相鄰節點copy請求，或者不做任何事。如果leader節點接收到了這樣一個返回值，則會在日志中追加一個NO-OP，并且執行下面的操作：

發送一個[gap-commit, log-slot]給所有的replica

非leader節點接收到消息之后，會在指定的位置插入一個NO-OP（可能位置已經插入了一個request的op），并且向leader響應一個[gap-commit-rep, log-slot]的消息。leader等待這個消息，必要的時候要重試。

??對于drop操作，客戶端是不需要顯式通知到的，因為可以等待客戶端超時。當然這里在實際開發的時候可以進行一些優化，比如leader沒有接收到的時候，也可以向其他的節點進行copy，減少NO-OP的數目。

3. view change

??前文也說到了，NOPaxos這一層有一個leader的概念，且OUM有一個session的概念，如果這兩個一旦有一個發生改變，就需要進行view change操作了。view change協議能保證新老視圖中間的狀態一致性，且能很好的從老的視圖切換到新的視圖。NOPaxos中的視圖變換協議類似于Viewstamped Replication[42]。算法闡述如下：當一個replica懷疑當前的leader掛了，或者接收到了一個session-terminated，亦或者接收到一個view-change/view-change-req的消息。此時他就適當的增加leader-num或者session-num，并且將狀態status設置為viewchange。一旦session-num發生改變，session-msg-num則重置為0。然后廣播一個消息[view-change-req, view-id]給其他的replica，并且發送一個[view-change, view-id, v`, session-msg
-num, log]給新的leader，v`表示上一個狀態status為normal的視圖的view-id。當一個replica處于viewchange狀態的時候，會忽略其他消息，除了start-view， view-change，view-change-req。如果超時，則重新廣播和發送指定消息給新leader。當新leader接收到f+1個view-change的消息的時候，則會執行下列操作：從最近最新的view且status為normal的replica合并日志（每個replica都會發送一個log信息給新的leader）。合并規則是，如果大家都是no-op，那就是no-op，如果有一個是request，那就是request。leader拿到新的view-id之后設置session-msg-num比合并日志大的數字，然后廣播一個消息[start-view, view-id, session-msg-num, log]給所有的replica.當其他的replica收到了這個start-view的消息之后，會更新自己監聽的信息，包括view-id，session-msg-num等，并要先同步下日志，如果發生了日志更新，則會發送reply信息給客戶端。最后把自己的status設置為normal。

4. Synchronization
??定時同步，這個屬于優化范疇，前文也說到，在正常的情況下，leader進行commit操作，replica只進行日志append，但是隨著系統的運行，會導致log越來越大，如果leader發生變更，那么就會有一個問題，新leader恢復時間非常長。為了在leader變更的時候，恢復時間縮短，NOPaxos決定周期性的進行數據同步。這一步驟的目的就是確保在sync-point前的所有數據，log狀態都是一致的。小論文并沒有詳細的指出如何解決這一問題，放在了大論文中去講了。

??首先定義正確性是：一個request被執行或者NO-OP這樣的日志被寫進f+1個節點中，且如果客戶端確保一個request執行成功的標記是收到f+1個回復，并且我們說一個view v的log是stable的，表明這個會成為所有高于view v的視圖的前綴日志。
(1).stable log中的成功操作，在resulting log中也是同樣正確的。
(2).replica總是開始于一個view中一個正確的session-msg-num
??值得注意的是，一個操作（request或者no-op一旦被commit到日志中，將會永遠呆著），因為如果在view change期間，同時發生了操作commit，意味著f+1個節點同意了view change，而f+1個節點提交了日志，也就說明了，至少有一個節點同時執行了這兩件事。而且新leader會跟其他的節點同步日志，所以如果是大多數的節點承認的日志會同步到leader中去。

??后記：閱讀完之后，總覺得有點問題，github上有這個代碼的開源實現，NOPaxos的源碼，筆者還沒來得及去看，后續如果看了會繼續開更，希望更多喜歡分布式共識和分布式一致性的朋友能一起談論這個話題。