CAP定理

CAP由[Eric Brewer]在2000年PODC會議上提出，是Eric Brewer在Inktomi期間研發(fā)搜索引擎、分布式web緩存時得出的關于數(shù)據(jù)一致性(consistency)、服務可用性(availability)、分區(qū)容錯性(partition-tolerance)的猜想：

It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.

該猜想在提出兩年后被證明成立，成為我們熟知的CAP定理：

• 數(shù)據(jù)一致性(consistency)：所有節(jié)點在同一時刻能夠看到同樣的數(shù)據(jù)，也即“強一致性”；
• 服務可用性(availability)：所有讀寫請求在一定時間內(nèi)得到響應，可終止、不會一直等待；

• 分區(qū)容錯性(partition-tolerance)：因為網(wǎng)絡故障導致的系統(tǒng)分區(qū)不影響系統(tǒng)正常運行。

  
  
  q6bmAn6.png

我們把解決一致性問題（Consensus Problem）的算法叫做一致性算法（Consensus Algorithm）或者一致性協(xié)議（Consensus Protocol）。CAP定理能夠?qū)⑦@些一致性算法的集合進行歸類：

C+A ：以2階段提交(2 phase commit)為代表的嚴格選舉協(xié)議。當通信中斷時算法不具有終止性（即不具備分區(qū)容忍性）;
C+P ：以Paxos、Raft為代表的多數(shù)派選舉算法。當不可用的執(zhí)行過程超過半數(shù)時，算法無法得到正確結(jié)果（即會出現(xiàn)不可用的情況）;
A+P ：以Gossip協(xié)議為代表的沖突解決協(xié)議。當網(wǎng)絡分區(qū)存在和執(zhí)行過程正確時，只能等待分區(qū)消失才保持一致性（即不具備強一致性）

基于CAP定理，我們需要根據(jù)不同場景的不同業(yè)務要求來進行算法上的權衡。對于分布式存儲系統(tǒng)來說，網(wǎng)絡連接故障是無法避免的。在設計系統(tǒng)時不得不考慮分區(qū)容忍性，所以我們實際上只能在一致性和可用性之間進行權衡。

強一致性與可用性的矛盾會導致十分令人頭疼的抉擇。在實際情況中，對于不是那么重要的數(shù)據(jù)的存取操作，往往會調(diào)低一致性來增加可用性。

工程實踐上根據(jù)具體的業(yè)務場景，或保證強一致(safety)，或在節(jié)點宕機、網(wǎng)絡分化的時候保證可用(liveness)。2PC、3PC是相對簡單的解決一致性問題的協(xié)議，下面我們就來了解2PC和3PC。

2PC

2PC(tow phase commit)兩階段提交^[5]顧名思義它分成兩個階段，先由一方進行提議(propose)并收集其他節(jié)點的反饋(vote)，再根據(jù)反饋決定提交(commit)或中止(abort)事務。我們將提議的節(jié)點稱為協(xié)調(diào)者(coordinator)，其他參與決議節(jié)點稱為參與者(participants, 或cohorts)：

階段1

2PC, phase one

在階段1中，coordinator發(fā)起一個提議，分別問詢各participant是否接受。

階段2

2PC, phase two

在階段2中，coordinator根據(jù)participant的反饋，提交或中止事務，如果participant全部同意則提交，只要有一個participant不同意就中止。

3PC

3PC(three phase commit)即三階段提交，既然2PC可以在異步網(wǎng)絡+節(jié)點宕機恢復的模型下實現(xiàn)一致性，那還需要3PC做什么，3PC是什么鬼？

在2PC中一個participant的狀態(tài)只有它自己和coordinator知曉，假如coordinator提議后自身宕機，在watchdog啟用前一個participant又宕機，其他participant就會進入既不能回滾、又不能強制commit的阻塞狀態(tài)，直到
participant宕機恢復。這引出兩個疑問：

1. 能不能去掉阻塞，使系統(tǒng)可以在commit/abort前回滾(rollback)到?jīng)Q議發(fā)起前的初始狀態(tài)
2. 當次決議中，participant間能不能相互知道對方的狀態(tài)，又或者participant間根本不依賴對方的狀態(tài)

相比2PC，3PC增加了一個準備提交(prepare to commit)階段來解決以上問題：

圖片截取自wikipedia

coordinator接收完participant的反饋(vote)之后，進入階段2，給各個participant發(fā)送準備提交(prepare to commit)指令。participant接到準備提交指令后可以鎖資源，但要求相關操作必須可回滾。coordinator接收完確認(ACK)后進入階段3、進行commit/abort，3PC的階段3與2PC的階段2無異。協(xié)調(diào)者備份(coordinator watchdog)、狀態(tài)記錄(logging)同樣應用在3PC。

participant如果在不同階段宕機，我們來看看3PC如何應對：

• 階段1: coordinator或watchdog未收到宕機participant的vote，直接中止事務；宕機的participant恢復后，讀取logging發(fā)現(xiàn)未發(fā)出贊成vote，自行中止該次事務
• 階段2: coordinator未收到宕機participant的precommit ACK，但因為之前已經(jīng)收到了宕機participant的贊成反饋(不然也不會進入到階段2)，coordinator進行commit；watchdog可以通過問詢其他participant獲得這些信息，過程同理；宕機的participant恢復后發(fā)現(xiàn)收到precommit或已經(jīng)發(fā)出贊成vote，則自行commit該次事務
• 階段3: 即便coordinator或watchdog未收到宕機participant的commit ACK，也結(jié)束該次事務；宕機的participant恢復后發(fā)現(xiàn)收到commit或者precommit，也將自行commit該次事務

因為有了準備提交(prepare to commit)階段，3PC的事務處理延時也增加了1個RTT，變?yōu)?個RTT(propose+precommit+commit)，但是它防止participant宕機后整個系統(tǒng)進入阻塞態(tài)，增強了系統(tǒng)的可用性，對一些現(xiàn)實業(yè)務場景是非常值得的。

參考資料

分布式系統(tǒng)理論基礎 - CAP
分布式系統(tǒng)理論基礎 - 一致性、2PC和3PC
FLP不可能原理