一：一緻性算法Paxos
Paxos算法是基于消息傳遞且具有高度容錯特性的一緻性算法，是目前公認的解決分布式一緻性問題最有效的算法之一。
1.1 Paxos解決了什麼問題
在常見的分布式系統中，總會發生諸如通信異常、節點故障、網絡分區等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證不論發生以上任何異常，都不會破壞整個系統的一緻性。
注意：這裡某個資料的值并不隻是狹義上的某個數，它可以是一條日志，也可以是一條指令（command）。根據應用場景不同，某個資料的值有不同的含義。
1.2 Paxos的相關概念
提案 (Proposal)：Proposal資訊包括提案編号 (Proposal ID) 和提案的值 (Value)
在Paxos算法中，有三種角色）：
- Proposer：提案發起者，提案者提倡客戶請求，試圖說服Acceptor對此達成一緻，并在發生沖突時充當協調者以推動協定向前發展
- Acceptor：決策者，可以準許提案，Acceptor可以接受（accept）提案；如果某個提案被標明（chosen），那麼該提案裡的value就被确定了
- Learners：最終決策的學習者，學習者充當該協定的複制因素
1.4 Proposer生成提案規則
Proposer生成提案之前，應該先去『學習』已經被標明或者可能被標明的value，然後以該value作為自己提出的提案的value。如果沒有value被標明，Proposer才可以自己決定value的值。這樣才能達成一緻。這個學習的階段是通過一個『Prepare請求』實作的。
下圖為多數Acceptor集合（半數以上）沒有接收提案的情況：
Proposer提案生成算法：
-
Proposer選擇一個新的提案編号N，然後向某個Acceptor集合（半數以上）發送請求，要求該集合中的每個Acceptor做出如下響應（response）。
(a) 向Proposer承諾保證不再接受任何編号小于N的提案。
(b) 如果Acceptor已經接受過提案，那麼就向Proposer響應已經接受過的編号小于N的最大編号的提案。
我們将該請求稱為編号為N的Prepare請求。
-
如果Proposer收到了半數以上的Acceptor的響應，那麼它就可以生成編号為N，Value為V的提案[N,V]。這裡的V是所有的響應中編号最大的提案的Value。如果所有的響應中都沒有提案，那 麼此時V就可以由Proposer自己選擇。
生成提案後，Proposer将該提案發送給半數以上的Acceptor集合，并期望這些Acceptor能接受該提案。
我們稱該請求為Accept請求。（注意：此時接受Accept請求的Acceptor集合不一定是之前響應Prepare請求的Acceptor集合）
1.5 Acceptor接收提案規則
一個Acceptor可能會收到來自Proposer的兩種請求，分别是Prepare請求和Accept請求，對這兩類請求作出響應的條件分别如下：
- Prepare請求：Acceptor可以在任何時候響應一個Prepare請求
- Accept請求：在不違背Accept現有承諾的前提下，可以任意響應Accept請求
是以，對Acceptor接受提案給出如下限制：
p1a：一個Acceptor隻要尚未響應過任何編号大于N的Prepare請求，那麼他就可以接受這個編号為N的提案。
Acceptor算法優化
由上面可知，如果Acceptor收到一個編号為N的Prepare請求，在此之前它已經響應過編号大于N的Prepare請求。根據P1a，該 Acceptor不可能接受編号為N的提案。是以，該Acceptor可以忽略編号為N的Prepare請求。
通過這個優化，每個Acceptor隻需要記住它已經準許的提案的最大編号以及它已經做出Prepare請求響應的提案的最大編号就行了
1.6 Paxos算法描述
階段一：
- (a) Proposer選擇一個提案編号N，然後向半數以上的Acceptor發送編号為N的Prepare請求。
- (b) 如果一個Acceptor收到一個編号為N的Prepare請求，且N大于該Acceptor已經響應過的所有Prepare請求的編号，那麼它就會将它已經接受過的編号最大的提案（如果有的話）作為響應回報給Proposer，同時該Acceptor承諾不再接受任何編号小于N的提案。
階段二：
- (a) 如果Proposer收到半數以上Acceptor對其發出的編号為N的Prepare請求的響應，那麼它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編号最大的提案的value，如果響應中不包含任何提案，那麼V就由Proposer自己決定。
- (b) 如果Acceptor收到一個針對編号為N的提案的Accept請求，隻要該Acceptor沒有對編号大于N的Prepare請求做出過響應，它就接受該提案。
1.7 Learner學習被標明的value
三種方式：