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

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

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

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

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

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

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

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

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

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

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

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

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

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

介紹應(yīng)用層的NOPaxos協(xié)議，如何在應(yīng)用層協(xié)調(diào)state一致性。

為上述的實現(xiàn)做實驗驗證。

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

??每個客戶端都需要集成兩個庫，一個是用于處理網(wǎng)絡(luò)消息的libOUM，一個是用于協(xié)調(diào)多個replica之間操作的NOPaxos。底層網(wǎng)絡(luò)有一個sequencer，負責為每個消息加上一個序列號，為了防止sequencer故障或者失效，需要一個controller來進行監(jiān)控?？偟膩碚f，這個架構(gòu)總共有三種角色，controller，sequencer，client，其中client有兩種協(xié)議OUM和NOPaxos。下面就一個個的來介紹這些角色分別承擔的功能和用途。

1. sequencer

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

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

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

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

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

2.controller

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

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

總節(jié)點數(shù)為2f+1，f是最多允許fail的節(jié)點數(shù)，這個就不必說了，paxos也是這么限制的，最少要半數(shù)以上節(jié)點同意提案方可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內(nèi)，每個message都有一個單調(diào)遞增1的序列號，這個就是該序列號

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

sync-point：最新的同步點

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

1. Normal Operation

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

2. Gap Agrement

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

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

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

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

3. view change

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

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

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

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