前言
春節在家閑着沒事看了幾篇論文，把一緻性協定的幾篇論文都過了一遍。在看這些論文之前，我一直有一些疑惑，比如同樣是有Leader和兩階段送出，Zookeeper的ZAB協定和Raft有什麼不同，Paxos協定到底要怎樣才能用在實際工程中，這些問題我都在這些論文中找到了答案。接下來，我将嘗試以自己的語言給大家講講這些協定，使大家能夠了解這些算法。同時，我自己也有些疑問，我會在我的闡述中提出，也歡迎大家一起讨論。水準有限，文中難免會有一些纰漏門也歡迎大家指出。
邏輯時鐘
邏輯時鐘其實算不上是一個一緻性協定，它是Lamport大神在1987年就提出來的一個想法，用來解決分布式系統中，不同的機器時鐘不一緻可能帶來的問題。在單機系統中，我們用機器的時間來辨別事件，就可以非常清晰地知道兩個不同僚件的發生次序。但是在分布式系統中，由于每台機器的時間可能存在誤差，無法通過實體時鐘來準确分辨兩個事件發生的先後順序。但實際上，在分布式系統中，隻有兩個發生關聯的事件，我們才會去關心兩者的先來後到關系。比如說兩個事務，一個修改了rowa，一個修改了rowb，他們兩個誰先發生，誰後發生，其實我們并不關心。那所謂邏輯時鐘，就是用來定義兩個關聯事件的發生次序，即‘happens before’。而對于不關聯的事件，邏輯時鐘并不能決定其先後，是以說這種‘happens before’的關系，是一種偏序關系。
圖和例子來自于這篇
部落格此圖中，箭頭表示程序間通訊，ABC分别代表分布式系統中的三個程序。
邏輯時鐘的算法其實很簡單：每個事件對應一個Lamport時間戳，初始值為0
如果事件在節點内發生，時間戳加1
如果事件屬于發送事件，時間戳加1并在消息中帶上該時間戳
如果事件屬于接收事件，時間戳 = Max(本地時間戳，消息中的時間戳) + 1
這樣，所有關聯的發送接收事件，我們都能保證發送事件的時間戳小于接收事件。如果兩個事件之間沒有關聯，比如說A3和B5，他們的邏輯時間一樣。正是由于他們沒有關系，我們可以随意約定他們之間的發生順序。比如說我們規定，當Lamport時間戳一樣時，A程序的事件發生早于B程序早于C程序，這樣我們可以得出A3 ‘happens before’ B5。而實際在實體世界中，明顯B5是要早于A3發生的，但這都沒有關系。
邏輯時鐘貌似目前并沒有被廣泛的應用，除了DynamoDB使用了vector clock來解決多版本的先後問題（如果有其他實際應用的話請指出，可能是我孤陋寡聞了），Google的Spanner 也是采用實體的原子時鐘來解決時鐘問題。但是從Larmport大師的邏輯時鐘算法上，已經可以看到一些一緻性協定的影子。
Replicated State Machine
說到一緻性協定，我們通常就會講到複制狀态機。因為通常我們會用複制狀态機加上一緻性協定算法來解決分布式系統中的高可用和容錯。許多分布式系統，都是采用複制狀态機來進行副本之間的資料同步，比如HDFS，Chubby和Zookeeper。
所謂複制狀态機，就是在分布式系統的每一個執行個體副本中，都維持一個持久化的日志，然後用一定的一緻性協定算法，保證每個執行個體的這個log都完全保持一緻，這樣，執行個體内部的狀态機按照日志的順序回放日志中的每一條指令，這樣用戶端來讀時，在每個副本上都能讀到一樣的資料。複制狀态機的核心就是圖中 的Consensus子產品，即今天我們要讨論的Paxos，ZAB，Raft等一緻性協定算法。
Paxos
Paxos是Lamport大神在90年代提出的一緻性協定算法，大家一直都覺得難懂，是以Lamport在2001又發表了一篇新的論文《Paxos made simple》，在文中他自己說Paxos是世界上最簡單的一緻性算法，非常容易懂……但是業界還是一緻認為Paxos比較難以了解。在我看過Lamport大神的論文後，我覺得，除去複雜的正确性論證過程，Paxos協定本身還是比較好了解的。但是，Paxos協定還是過于理論，離具體的工程實踐還有太遠的距離。我一開始看Paxos協定的時候也是一頭霧水，看來看去發現Paxos協定隻是為了單次事件答成一緻，而且答成一緻後的值無法再被修改，怎麼用Paxos去實作複制狀态機呢？另外，Paxos協定答成一緻的值隻有Propose和部分follower知道，這協定到底怎麼用……但是，如果你隻是把Paxos協定當做一個理論去看，而不是考慮實際工程上會遇到什麼問題的話，會容易了解的多。Lamport的論文中對StateMachine的應用隻有一個大概的想法，并沒有具體的實作邏輯，想要直接把Paxos放到複制狀态機裡使用是不可能的，得在Paxos上補充很多的東西。這些是為什麼Paxos有這麼多的變種。
Basic-Paxos
Basic-Paxos即Lamport最初提出的Paxos算法，其實很簡單，用三言兩語就可以講完，下面我嘗試着用我自己的語言描述下Paxos協定，然後會舉出一個例子。要了解Paxos，隻要記住一點就好了，Paxos隻能為一個值形成共識，一旦Propose被确定，之後值永遠不會變，也就是說整個Paxos Group隻會接受一個提案（或者說接受多個提案，但這些提案的值都一樣）。至于怎麼才能接受多個值來形成複制狀态機，大家可以看下一節Multi-Paxos.
Paxos協定中是沒有Leader這個概念的，除去Learner（隻是學習Propose的結果，我們可以不去讨論這個角色），隻有Proposer和Acceptor。Paxos并且允許多個Proposer同時提案。Proposer要提出一個值讓所有Acceptor答成一個共識。首先是Prepare階段，Proposer會給出一個ProposeID n（注意，此階段Proposer不會把值傳給Acceptor）給每個Acceptor，如果某個Acceptor發現自己從來沒有接收過大于等于n的Proposer，則會回複Proposer，同時承諾不再接收ProposeID小于等于n的提議的Prepare。如果這個Acceptor已經承諾過比n更大的propose，則不會回複Proposer。如果Acceptor之前已經Accept了（完成了第二個階段）一個小于n的Propose，則會把這個Propose的值傳回給Propose，否則會傳回一個null值。當Proposer收到大于半數的Acceptor的回複後，就可以開始第二階段accept階段。但是這個階段Propose能夠提出的值是受限的，隻有它收到的回複中不含有之前Propose的值，他才能自由提出一個新的value，否則隻能是用回複中Propose最大的值做為提議的值。Proposer用這個值和ProposeID n對每個Acceptor發起Accept請求。也就是說就算Proposer之前已經得到過acceptor的承諾，但是在accept發起之前，Acceptor可能給了proposeID更高的Propose承諾，導緻accept失敗。也就是說由于有多個Proposer的存在，雖然第一階段成功，第二階段仍然可能會被拒絕掉。
下面我舉一個例子，這個例子來源于這篇
假設有Server1，Server2， Server3三個伺服器，他們都想通過Paxos協定，讓所有人答成一緻他們是leader，這些Server都是Proposer角色，他們的提案的值就是他們自己server的名字。他們要擷取Acceptor1~3這三個成員同意。首先Server2發起一個提案【1】,也就是說ProposeID為1，接下來Server1發起來一個提案【2】,Server3發起一個提案【3】.
首先是Prepare階段：
假設這時Server1發送的消息先到達acceptor1和acceptor2，它們都沒有接收過請求，是以接收該請求并傳回【2，null】給Server1，同時承諾不再接受編号小于2的請求；
緊接着，Server2的消息到達acceptor2和acceptor3，acceptor3沒有接受過請求，是以傳回proposer2 【1，null】，并承諾不再接受編号小于1的消息。而acceptor2已經接受Server1的請求并承諾不再接收編号小于2的請求，是以acceptor2拒絕Server2的請求；
最後，Server3的消息到達acceptor2和acceptor3，它們都接受過提議，但編号3的消息大于acceptor2已接受的2和acceptor3已接受的1，是以他們都接受該提議，并傳回Server3 【3，null】；
此時，Server2沒有收到過半的回複，是以重新取得編号4，并發送給acceptor2和acceptor3，此時編号4大于它們已接受的提案編号3，是以接受該提案，并傳回Server2 【4，null】。
接下來進入Accept階段，
Server3收到半數以上（2個）的回複，并且傳回的value為null，是以，Server3送出了【3，server3】的提案。
Server1在Prepare階段也收到過半回複，傳回的value為null，是以Server1送出了【2，server1】的提案。
Server2也收到過半回複，傳回的value為null，是以Server2送出了【4，server2】的提案。
Acceptor1和acceptor2接收到Server1的提案【2，server1】，acceptor1通過該請求，acceptor2承諾不再接受編号小于4的提案，是以拒絕；
Acceptor2和acceptor3接收到Server2的提案【4，server2】，都通過該提案；
Acceptor2和acceptor3接收到Server3的提案【3，server3】，它們都承諾不再接受編号小于4的提案，是以都拒絕。
此時，過半的acceptor（acceptor2和acceptor3）都接受了提案【4，server2】，learner感覺到提案的通過，learner開始學習提案，是以server2成為最終的leader。
Multi-Paxos
剛才我講了，Paxos還過于理論，無法直接用到複制狀态機中，總的來說，有以下幾個原因
- Paxos隻能确定一個值，無法用做Log的連續複制
- 由于有多個Proposer，可能會出現活鎖，如我在上面舉的例子中，Server2的一共提了兩次Propose才最終讓提案通過，極端情況下，次數可能會更多
- 提案的最終結果可能隻有部分Acceptor知曉，沒法達到複制狀态機每個instance都必須有完全一緻log的需求。
那麼其實Multi-Paxos，其實就是為了解決上述三個問題，使Paxos協定能夠實際使用在狀态機中。解決第一個問題其實很簡單。為Log Entry每個index的值都是用一個獨立的Paxos instance。解決第二個問題也很簡答，讓一個Paxos group中不要有多個Proposer，在寫入時先用Paxos協定選出一個leader（如我上面的例子），然後之後隻由這個leader做寫入，就可以避免活鎖問題。并且，有了單一的leader之後，我們還可以省略掉大部分的prepare過程。隻需要在leader當選後做一次prepare，所有Acceptor都沒有接受過其他Leader的prepare請求，那每次寫入，都可以直接進行Accept，除非有Acceptor拒絕，這說明有新的leader在寫入。為了解決第三個問題，Multi-Paxos給每個Server引入了一個firstUnchosenIndex，讓leader能夠向向每個Acceptor同步被選中的值。解決這些問題之後Paxos就可以用于實際工程了。
Paxos到目前已經有了很多的補充和變種，實際上，之後我要讨論的ZAB也好，Raft也好，都可以看做是對Paxos的修改和變種，另外還有一句流傳甚廣的話，“世上隻有一種一緻性算法，那就是Paxos”。
ZAB
ZAB即Zookeeper Atomic BoardCast，是Zookeeper中使用的一緻性協定。ZAB是Zookeeper的專用協定，與Zookeeper強綁定，并沒有抽離成獨立的庫，是以它的應用也不是很廣泛，僅限于Zookeeper。但ZAB協定的論文中對ZAB協定進行了詳細的證明，證明ZAB協定是能夠嚴格滿足一緻性要求的。
ZAB随着Zookeeper誕生于2007年，此時Raft協定還沒有發明，根據ZAB的論文，之是以Zookeeper沒有直接使用Paxos而是自己造輪子，是因為他們認為Paxos并不能滿足他們的要求。比如Paxos允許多個proposer，可能會造成用戶端送出的多個指令沒法按照FIFO次序執行。同時在恢複過程中，有一些follower的資料不全。這些斷論都是基于最原始的Paxos協定的，實際上後來一些Paxos的變種，比如Multi-Paxos已經解決了這些問題。當然我們隻能站在曆史的角度去看待這個問題，由于當時的Paxos并不能很好的解決這些問題，是以Zookeeper的開發者創造了一個新的一緻性協定ZAB。
ZAB其實和後來的Raft非常像，有選主過程，有恢複過程，寫入也是兩階段送出，先從leader發起一輪投票，獲得超過半數同意後，再發起一次commit。ZAB中每個主的epoch number其實就相當于我接下來要講的Raft中的term。隻不過ZAB中把這個epoch number和transition number組成了一個zxid存在了每個entry中。
ZAB在做log複制時，兩階段送出時，一個階段是投票階段，隻要收到過半數的同意票就可以，這個階段并不會真正把資料傳輸給follower，實際作用是保證當時有超過半數的機器是沒有挂掉，或者在同一個網絡分區裡的。第二個階段commit，才會把資料傳輸給每個follower，每個follower（包括leader）再把資料追加到log裡，這次寫操作就算完成。如果第一個階段投票成功，第二個階段有follower挂掉，也沒有關系，重新開機後leader也會保證follower資料和leader對其。如果commit階段leader挂掉，如果這次寫操作已經在至少一個follower上commit了，那這個follower一定會被選為leader，因為他的zxid是最大的，那麼他選為leader後，會讓所有follower都commit這條消息。如果leader挂時沒有follower commit這條消息，那麼這個寫入就當做沒寫完。
由于隻有在commit的時候才需要追加寫日志，是以ZAB的log，隻需要append-only的能力，就可以了。
另外，ZAB支援在從replica裡做stale read，如果要做強一緻的讀，可以用sync read，原理也是先發起一次虛拟的寫操作，到不做任何寫入，等這個操作完成後，本地也commit了這次sync操作，再在本地replica上讀，能夠保證讀到sync這個時間點前所有的正确資料，而Raft所有的讀和寫都是經過主節點的
Raft
Raft是斯坦福大學在2014年提出的一種新的一緻性協定。作者表示之是以要設計一種全新的一緻性協定，是因為Paxos實在太難了解，而且Paxos隻是一個理論，離實際的工程實作還有很遠的路。是以作者狠狠地吐槽了Paxos一把：
- Paxos協定中，是不需要Leader的，每個Proposer都可以提出一個propose。相比Raft這種一開始設計時就把選主和協定達成一緻分開相比，Paxos等于是把選主和propose階段雜糅在了一起，造成Paxos比較難以了解。
- 最原始的Paxos協定隻是對單一的一次事件答成一緻，一旦這個值被确定，就無法被更改，而在我們的現實生活中，包括我們資料庫的一緻性，都需要連續地對log entry的值答成一緻，是以單單了解Paxos協定本身是不夠的，我們還需要對Paxos協定進行改進和補充，才能真正把Paxos協定應用到工程中。而對Paxos協定的補充本身又非常複雜，而且雖然Paxos協定被Lamport證明過，而添加了這些補充後，這些基于Paxos的改進算法，如Multi-Paxos，又是未經證明的。
- 第三個槽點是Paxos協定隻提供了一個非常粗略的描述，導緻後續每一個對Paxos的改進，以及使用Paxos的工程，如Google的Chubby，都是自己實作了一套工程來解決Paxos中的一些具體問題。而像Chubby的實作細節其實并沒有公開。也就是說要想在自己的工程中使用Paxos，基本上每個人都需要自己定制和實作一套适合自己的Paxos協定。
是以，Raft的作者在設計Raft的時候，有一個非常明确的目标，就是讓這個協定能夠更好的了解，在設計Raft的過程中，如果遇到有多種方案可以選擇的，就選擇更加容易了解的那個。作者舉了一個例子。在Raft的選主階段，本來可以給每個server附上一個id,大家都去投id最大的那個server做leader，會更快地達成一緻（類似ZAB協定），但這個方案又增加了一個serverid的概念，同時在高id的server挂掉時，低id的server要想成為主必須有一個等待時間，影響可用性。是以Raft的選主使用了一個非常簡單的方案：每個server都随機sleep一段時間，最早醒過來的server來發起一次投票，擷取了大多數投票即可為主。在通常的網絡環境下，最早發起投票的server也會最早收到其他server的贊成票，是以基本上隻需要一輪投票就可以決出leader。整個選主過程非常簡單明了。
除了選主，整個Raft協定的設計都非常簡單。leader和follower之間的互動（如果不考慮snapshot和改變成員數量）一共隻有2個RPC call。其中一個還是選主時才需要的RequestVote。也就是說所有的資料互動，都隻由AppendEntries 這一個RPC完成。
了解Raft算法，首先要了解Term這個概念。每個leader都有自己的Term，而且這個term會帶到log的每個entry中去，來代表這個entry是哪個leader term時期寫入的。另外Term相當于一個lease。如果在規定的時間内leader沒有發送心跳（心跳也是AppendEntries這個RPC call）,Follower就會認為leader已經挂掉，會把自己收到過的最高的Term加上1做為新的term去發起一輪選舉。如果參選人的term還沒自己的高的話，follower會投反對票，保證選出來的新leader的term是最高的。如果在time out周期内沒人獲得足夠的選票（這是有可能的），則follower會在term上再加上1去做新的投票請求，直到選出leader為止。最初的raft是用c語言實作的，這個timeout時間可以設定的非常短，通常在幾十ms，是以在raft協定中，leader挂掉之後基本在幾十ms就能夠被檢測發現，故障恢複時間可以做到非常短。而像用Java實作的Raft庫，如Ratis，考慮到GC時間，我估計這個逾時時間沒法設定這麼短。
在Leader做寫入時也是一個兩階段送出的過程。首先leader會把在自己的log中找到第一個空位index寫入，并通過AppendEntries這個RPC把這個entry的值發給每個follower，如果收到半數以上的follower（包括自己）回複true，則再下一個AppendEntries中，leader會把committedIndex加1，代表寫入的這個entry已經被送出。如在下圖中，leader将x=4寫入index=8的這個entry中，并把他發送給了所有follower，在收到第一台（自己），第三台，第五台（圖中沒有畫index=8的entry，但因為這台伺服器之前所有的entry都和leader保持了一緻，是以它一定會投同意），那麼leader就獲得了多數票，再下一個rpc中，會将Committed index往前挪一位，代表index<=8的所有entry都已經送出。至于第二台和第四台伺服器，log内容已經明顯落後，這要麼是因為前幾次rpc沒有成功。leader會無限重試直到這些follower和leader的日志追平。另外一個可能是這兩台伺服器重新開機過，處于恢複狀态。那麼這兩台伺服器在收到寫入index=8的RPC時，follower也會把上一個entry的term和index發給他們。也就是說prevLogIndex=7，prevLogTerm=3這個資訊會發給第二台伺服器，那麼對于第二台伺服器，index=7的entry是空的，也就是log和leader不一緻，他會傳回一個false給leader，leader會不停地從後往前周遊，直到找到一個entry與第二台伺服器一緻的，從這個點開始重新把leader的log内容發送給該follower，即可完成恢複。raft協定保證了所有成員的replicated log中每個index位置，如果他們的term一緻，内容也一定一緻。如果不一緻，leader一定會把這個index的内容改寫成和leader一緻。
其實經過剛才我的一些描述，基本上就已經把Raft的選主，寫入流程和恢複基本上都講完了。從這裡，我們可以看出Raft一些非常有意思的地方。
第一個有意思的地方是Raft的log的entry是可能被修改的，比如一個follower接收了一個leader的prepare請求，把值寫入了一個index，而這個leader挂掉，新選出的leader可能會重新使用這個index，那麼這個follower的相應index的内容，會被改寫成新的内容。這樣就造成了兩個問題，首先第一個，raft的log無法在append-only的檔案或者檔案系統上去實作，而像ZAB，Paxos協定，log隻會追加，隻要求檔案系統有append的能力即可，不需要随機通路修改能力。
第二個有意思的地方是，為了簡單，Raft中隻維護了一個Committed index，也就是任何小于等于這個committedIndex的entry，都是被認為是commit過的。這樣就會造成在寫入過程中，在leader獲得大多數選票之前挂掉（或者leader在寫完自己的log之後還沒來得及通知到任何follower就挂掉），重新開機後如果這個server繼續被選為leader，這個值仍然會被commit永久生效。因為leader的log中有這個值，leader一定會保證所有的follower的log都和自己保持一緻。而後續的寫入在增長committedIndex後，這個值也預設被commit了。
舉例來說，現在有5台伺服器，其中S1為leader，但是當他在為index=1的entry執行寫入時，先寫到了自己的log中，還沒來得及通知其他server append entry就當機了。
當S1重新開機後，任然有可能被重新當選leader，當S1重新當選leader後，仍然會把index=1的這個entry複制給每台伺服器（但是不會往前移動Committed index）
此時S1又發生一次寫入，這次寫入完成後，會把Committed index移動到2的位置，是以index=1的entry也被認為已經commit了。
這個行為有點奇怪，因為這樣等于raft會讓一個沒有獲得大多數人同意的值最終commit。這個行為取決于leader，如果上面的例子中S1重新開機後沒有被選為leader，index=1的entry内容會被新leader的内容覆寫，進而不會送出未經過表決的内容。
雖然說這個行為是有點奇怪，但是不會造成任何問題，因為leader和follower還是會保持一緻，而且在寫入過程中leader挂掉，對用戶端來說是本來就是一個未決語義，raft論文中也指出，如果使用者想要exactly once的語義，可以在寫入的時候加入一個類似uuid的東西，在寫入之前leader查下這個uuid是否已經寫入。那麼在一定程度上，可以保證exactly once的語義。
Raft的論文中也比較了ZAB的算法，文中說ZAB協定的一個缺點是在恢複階段需要leader和follower來回交換資料，這裡我沒太明白，據我了解，ZAB在重新選主的過程中，會選擇Zxid最大的那個從成為主，而其他follower會從leader這裡補全資料，并不會出現leader從follower節點補資料這一說。
後話
目前，經過改進的Paxos協定已經用在了許多分布式産品中，比如說Chubby，PaxosStore，阿裡雲的X-DB，以及螞蟻的OceanBase，都選用了Paxos協定，但他們都多多少少做了一些補充和改進。而像Raft協定，普遍認為Raft協定隻能順序commit entry，性能沒有Paxos好，但是TiKV中使用了Raft，其公開的文章宣傳對Raft做了非常多的優化，使Raft的性能變的非常可觀。阿裡的另外一個資料庫PolarDB，也是使用了改進版的Parallel-Raft，使Raft實作了并行送出的能力。相信未來會有更多的基于Paxos/Raft的産品會面世，同時也對Raft/Paxos也會有更多的改進。
參考文獻
- 《Time, clocks, and the ordering of events in a distributed system》
- 《Implementing fault-tolerant services using the state machine approach- A tutorial》
- 《Paxos Made Simple》
- 《Paxos made live- An engineering perspective》
- 《Multi-Paxos》（Standford大學的一個ppt）
- 《Zab- High-performance broadcast for primary-backup systems》
- 《In search of an understandable consensus algorithm》（raft）