第2章：一緻性協定
根據CAP理論，在P必須被滿足的情況下，需要在C和A之間進行權衡。是以産生了一系列的一緻性協定。
最著名的一緻性理論就是二階段送出協定、三階段送出協定和Paxos算法。
本章介紹二階段和三階段協定的優缺點，并重點介紹Paxos算法。
2.1 2PC與3PC
每個節點知道自己的事務是否成功，但無法擷取其他節點的結果。
為了讓一個事務能夠跨節點執行，則需要一個“協調者”來統一排程分布式節點的執行邏輯。
協調者通過排程參與的節點，來保證事務的運作，是以衍生出了二階段送出和三階段送出兩種協定。
2.1.1 2PC
2PC指的是二階段送出。
目前絕大部分關系型資料庫采用二階段送出協定來完成分布式事務處理的，利用該協定能夠非常友善地完成所有分布式事務參與者的協調，統一決定事務的送出或復原。
協定說明
階段一：送出事務請求：
協調者詢問各個參與者是否能夠執行事務，是以又稱“投票階段”
（1）事務詢問：
協調者詢問參與者是否能夠執行事務，然後等待參與者的響應
（2）執行事務：
各參與者節點執行事務操作，将Undo和Redo資訊記錄事務中
（3）參與者向協調者回報
若執行成功則回報yes，若失敗則回報no。
階段二：執行事務送出
根據參與者的回報情況，來決定是否要執行事務。
如果所有的參與者都回報yes，那麼就開始執行事務，（1）協調者發送送出請求（2）參與者開始執行事務 （3）回報送出的結果 （4）完成事務
如果有任何一個回報no，則中斷事務，（1）發送復原請求 （2）事務復原 （3）回報事務復原結果 （4）中斷事務
2PC的優缺點
優點：原理簡單、實作友善
缺點：
同步阻塞（參與者必須等待其他參與者回報完才可以執行）
單點問題（一旦協調者出現問題，将會很嚴重）
腦裂（有一部分收到了commit請求，另一部分沒有收到，導緻整個系統出現不一緻的情況）
太過保守（任何一個節點失敗都會導緻事務的失敗）
2.1.2 3PC
基于二階段存在的同步阻塞、單點問題、腦裂、太過保守的問題，提出了改進的三階段協定
三階段将二階段提出的“送出事務請求”一分為二，形成了CanCommit、PreCommit和doCommit三階段的事務處理協定。
階段一：CanCommit
（1）事務詢問：
協調者向參與者詢問是否能夠執行事務
（2）協調者接收回報
參與者會根據情況回答yes還是no
階段二：PreCommit
根據參與者的回報，會得到兩種結果。如果都是yes，則執行事務預送出，否則執行中斷事務
事務預送出
（1）協調者發送預送出請求
（2）事務預送出
（3）參與者向協調者回報事務執行的響應
中斷事務
（1）發送中斷請求
（2）中斷事務
階段三：doCommit
在預送出成功之後，才會進行真正的送出，否則中斷事務
執行送出
（1）協調者發送送出請求給參與者
（2）協調者正式送出事務
（3）參與者回報事務送出的結果
（4）完成事務
中斷事務
（1）發送中斷請求
（2）事務復原
（3）回報事務復原結果
（4）中斷事務
3PC的優缺點
（1）優點：降低參與者的阻塞範圍，并能夠在單點故障後達成一緻
（2）缺點：如果在預送出之後，出現網絡阻塞，那麼參與者依然會進行事務的送出，出現資料不一緻的情況。
2.2 Paxos算法
一種基于消息傳遞且高度容錯特性的一緻性算法，是目前解決分布式一緻性最有效的算法之一。
Paxos解決的問題
如果在一個可能異常的分布式系統中，快速且正确地讓資料内部達成一緻。
2.2.1 追本溯源
1982年，Lamport等人提出了一種計算機容錯理論，并設想了以下場景
拜占庭帝國有很多軍隊，不同軍隊的将軍之間必須指定一個統一的行動計劃（進攻還是撤退），
但是，将軍都是分開的，隻能靠通訊員進行通信。然而，通訊員也可能有叛徒，會任意篡改消息。
在有叛徒的情況下，這在分布式系統中完成一緻性幾乎是不可能的。
是以在一緻性算法中，假設信道是可靠的，沒有叛徒。
1990年，Lamport又提出了一個理論解決了一緻性的問題，同樣他也假設了一個場景來解決一緻性問題
古希臘有一個叫Paxos的小島，島上通過議會的形式通過法令，議會中的議員通過信使進行消息傳遞。
議員和信使都是兼職的，他們随時都會離開議會，也可能重複傳遞消息，也可能一去不複返。
是以，議會協定要保證這種情況下法令仍然可以正确的産生。
2.2.2 Paxos理論的誕生
由于Lamport使用了故事的方式進行算法的描述，導緻當時的委員會沒人能夠讀懂這個算法，委員會要求他用嚴謹的數學證明他的算法，但是Lamport拒絕了。
1996年，其他人幫助Lamport用數學的形式化術語定義并證明了Paxos算法。
2001年，Lamport用通俗易懂的方式講訴了原文。
2.2.3 Paxos算法詳解
作者用2001年通俗易懂的版本來解釋一緻性算法的合理性。
問題描述
假設有一組可以提案的程序（議員）集合，那麼一緻性算法需要保證以下幾點
（1）這些被提出的提案、隻有一個會被標明
（2）如果沒有提案提出，那麼就不會有被標明的提案
（3）當提案被標明後，程序可以擷取被標明提案的資訊
對于一緻性來說，安全性（Safety）需求如下：
（1）隻有被提出的提案才能被標明
（2）隻能有一個值被標明
（3）某個程序認為改提案被標明，那麼這個提案一定被標明
在Paxos一緻性算法中，有三種參與角色，分别用Proposer(議員)、Acceptor（接收者）和Learner（信使）來表示。
一個程序不止一種角色，不同參與者之間通過收發消息來通信，那麼（1）程序直接可能會各種問題 （2）資訊可能會丢失，但是不會被篡改
提案的標明
如果隻有一個Acceptor，那麼接收提案很簡單，但是一旦出現問題，将是不可挽回的。
如果有多個Acceptor，那麼Proposer向多個Acceptor發送提案，每個Acceptor都會準許該提案、如果足夠多的Acceptor準許該提案，那麼該提案就被標明了。
足夠多的定義是什麼？規定一個包含絕大部分Acceptor的子集，并且一個Acceptor隻能準許一個提案，就能保證隻有一個提案被標明了。
推導過程
如果：一個Acceptor必須準許它收到的第一個提案。
由此會産生如下問題
（1）如果有5個Proposer提出了5個提案剛好被5個Acceptor準許
（2）如果2個提案發給5個Acceptor，但有一個Acceptor出現異常，4個提案剛好各被2個Acceptor準許。
是以Paxos沒有采用一個Acceptor的方法
是以：一個Acceptor能夠準許不止一個提案
當某一個提案已經被半數以上的Acceptor準許了，那麼就直接標明該提案。
通過引入一個全局唯一編号（從小到大），編号越大的提案越有可能被接收 。此時提案被變成了[編号，Value],即[編号，具體的提案内容]
但是如果[編号，Value] 的提案被選中，那麼後續提案中已經被選中的Value（具體的提案内容）必須是一樣的。
p2: 如果[M0,V0]的提案被標明了，那麼所有編号比M0更高的，且被選中的提案，其Value值也必須是V0
要滿足p2,則需要同時滿足p2a和p2b
p2a:如果[M0,V0]被標明了，那麼所有編号比M0更高的，且被Acceptor準許的提案，其Value值也必須是V0
p2b:如果[M0,V0]被標明了，那麼之後任何Proposor産生的編号更高的提案，其Value值都為V0
proposal如何滿足p2b
proposer在産生一個編号為Mn的提案時，必須知道目前比M0小，且最大，且被Acceptor接收的編号數。
并且proposer要求所有的Acceptor都不要再準許編号小于M0的提案。
當proposer發送請求前，需要Acceptor做出如下回應（prepare請求）
（1）Acceptor需要承諾，不再準許編号小于M0的提案
（2）Acceptor傳回編号比M0小，且最大的編号數，目前Acceptor通過的編号最大的Value（Vn，提案的具體内容）
如果Proposer接收到半數以上Acceptor的prepare響應結果後，就可以發送accept請求
（1）他就可以産生編号為M0，Value值為Vn的提案
Acceptor如何滿足p2a
Acceptor可能會收到Proposer的兩種請求，分别是prepare請求和accept請求。
prepare請求：Acceptor可以在任何時候響應一個prepare請求
accept請求：在不違背Accept現有承諾下，可以響應任意accept請求。承諾為：如果一個Acceptor沒有響應過編号大于M0的prepare請求。
算法陳訴
階段一：
（1）Proposer提出一個編号為M0的提案，且向Acceptor超過半數的子集發送Prepare請求
（2）如果Acceptor接收到的M0大于任何已經準許過的編号，就将比目前M0小，且最大的編号的Value（具體提案）給Proposer。同時承諾不再準許小于M0的提案
階段二：
（1）如果Proposer收到半數以上的Acceptor對于其發出的編号Vn和做出的承諾（prepare請求的響應），就把目前的[M0，V0]作為提案發送給Acceptor
（2）Acceptor收到這個提案後，隻要acceptor沒有接收比目前編号大的提案，就通過這個提案（通過accept請求）
提案的擷取
當選定提案後，如何讓Learner擷取提案，作者提出了三種方案
方案一：
最簡單的做法，一旦該提案被超過半數的Acceptor接收，就立刻通知Learner
缺點：費時間，如果有n個Acceptor和m個Learner，那麼通信就需要m*n次
方案二：
當選定提案後，将結果通知給一個主Learner，再由主Learner通知其他Learner。
确定：主Learner一旦出現故障，将是不可挽回的
方案三：
針對方案二，進行了改進。因為一個Leaner不可靠，就可以通知給多個主Learner
當選定提案後，将結果通知給一個主Learner集合
通俗了解
proposer（議員）是一群趨炎附勢的人，當proposer收到一群acceptor的回報後，知道某個提案最有可能被acceptor接收（編号最大的），然後proposer發送的提案都是這個提案。
acceptor是一群沒有感情的接受機器，它隻通過編号大且已經被目前acceptor同意的提案。
當提案通過過半後，acceptor就将結果告訴給Learner
![ElasticJob‐Lite：Simple作業[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)