740
技術社區[雲棲]
Paxos分析之一—Paxos是什麼
Paxos有2種含義，廣義上來講，是指一係列協議的統稱，比如cheap Paxos <Cheap Paxos>(2004), fast paxos <Fast Paxos >(2005)，Disk Paxos 和Byzantine Paxos<The ABCD’s of Paxos> (2001)；狹義上來講，是指Leslie Lamport在其論文<The Part-Time Parliament >(1989)中提出的協議。
那Paxos協議是什麼那？可以看到很多文章在介紹Paxos時，都將其介紹為“是一種強一致性協議”，我覺得這麼說不夠準確。那麼Paxos究竟是什麼那？我們來看看幾篇Paxos經典的論文是如何定義Paxos的。Leslie Lamport在自己另外一篇論文<Paxos Made Simple> （2001）裏這麼說的：The Paxos algorithm for implementing a fault-tolerant distributed system
has been regarded as difficult to understand, perhaps because the original
presentation was Greek to many readers. 我們的重點在前半句，至於要理解後半句，需要了解Paxos的產生曆史，Paxos的曆史是計算機曆史中最有趣的曆史之一，這裏就不八卦了，有興趣的同學可以自行google.
另外一篇論文<Paxos made code>這樣描述Paxos：
The PAXOS algorithm for solving consensus is used to implement a fault-tolerant
Atomic Broadcast.
這篇論文中<Paxos Made Live - An Engineering Perspective>這樣描述：
We used the Paxos algorithm (“Paxos”) as the base for a framework that implements a fault-tolerant
log.
從這3句描述Paxos的句子中可以發現，都共同提到了一個詞：fault-tolerant。Fault-tolerant就是Paxos的核心。通常Paxos被用在數據寫入多個副本的場景，Paxos可以保證在容忍少量節點（n/2）掛掉的情況下仍然可以保證數據最終被成功寫入所有副本。假設我們不用Paxos，自己來實現副本寫入的邏輯，我們同步寫所有的副本，當所有副本都返回成功後，再通知用戶這條數據寫入成功，這種實現可以達到寫入多個副本的目的，但是這種方式無法容忍節點掛掉。Paxos的核心就是在容忍節點掛掉的情況下，保證數據最終寫入所有副本。所以說Paxos的核心是fault-tolerant，在任何一個Paxos的定義中都沒有提到一致性，所以說一致性不是Paxos關注的點。（Paxos是否保證強一致性這裏就不討論了）
從上麵的3句話中我們還能看出2個點，第一個點是Paxos解決什麼問題：consensus。什麼是consensus，有人把它翻譯成一致性（也許這就是為什麼Paxos被有些人誤解為"是一種強一致性協議"的原因吧，錯誤的翻譯了這個詞），其實不準確，應該翻譯成共識。共識也就是說多個進程在分布式的條件下，針對一個值達成共識。後麵會再解釋consensus。
第二個點就是Paxos可以用來實現Atomic Broadcast，或者log（也可以說狀態機）。後麵也會再解釋Atomic Broadcast和狀態機。
總結一下Paxos是什麼：
核心：fault-tolerant
解決的問題：consensus
應用在：Atomic Broadcast和狀態機
場景：數據寫入多個副本
接下來，說一下Paxos具體是什麼？Leslie Lamport的論文中的Paxos協議由2個部分組成，一個是basic Paxos，一個是multi Paxos。協議中定義了4中角色：client, proposer, acceptor, learner 。這裏要特別指出的是learner。了解Zookeeper的人都知道，Zookeeper所使用的Zab協議和Paxos類似（有人說Zab是Paxos的變種，個人覺得2者差別很大)。Zookeeper中有3種角色，leader，follower，observer，在Zookeeper中observer角色其實是可用可無，但是在Paxos中learner角色是必須的。個人曾經受上麵說法的影響，認為learner類似oberserver的所起的功能，導致很長時間無法正確理解Paxos協議的細節。
Basic Paxos是一種consensus算法。consensus像上麵所說的是用來讓多個進程針對一個值達成共識的，而且這個共識一旦達成就不可更改。這裏我們先不展開說明達成共識是怎樣的一個過程。我們這裏假設你已經理解了這個過程。這個過程可以單獨再寫篇文章來分析。這個達成共識過程就是Atomic Broadcast要完成功能。Zab其實就是從這個角度出發，將自己叫作原子廣播協議（Zookeeper Atomic Broadcast)。
那麼我們針對一個值達成共識有什麼用？這就要來說multi Paxos。我們把獨立的一個這樣達成共識的過程成之為一個實例(instance)。那麼我們反複運行這個過程，就可以形成一係列的共識，也就是一係列的實例。那麼這個反複運行的過程就是multi Paxos。一係列的實例，就是一係列確定下來的值，這一係列的值可以看做一個日誌流，而且是複製到所有節點上的日誌流。Raft就是從這個角度出發，這樣定義自己"Raft is a consensus algorithm for managing a replicated log"<In Search of an Understandable Consensus Algorithm>。（個人覺得Raft和Paxos的細節差別也很大)。接下來我們就可以基於這個日誌實現狀態機(state machine）。這個狀態機可以用來實現可靠的存儲係統，在存儲係統中的一個節點寫入一個值或者修改一個值，我們將這個變更寫入日誌，做為日誌的一條記錄，也就是一個Paxos的一個實例，日誌被複製到其他節點，其他節點按照相同的順序重做日誌，那麼就會得到和主節點完全相同的狀態。從而實現了一個fault-tolerant的存儲係統。所以說存儲係統引入類似Paxos這樣的協議是提高了係統的可靠性。
最後再總結一下Paxos是什麼：
核心：fault-tolerant
解決的問題：consensus
應用在：Atomic Broadcast和狀態機
場景：數據寫入多個副本
最後更新：2017-08-13 22:23:14