CAP

CAP原則權(quán)衡

通過CAP理論，我們知道無法同時滿足一致性、可用性和分區(qū)容錯性這三個特性，那要舍棄哪個呢。

CA without P

如果不要求P（不允許分區(qū)），則C（強一致性）和A（可用性）是可以保證的。但其實分區(qū)不是你想不想的問題，而是始終會存在，因此CA的系統(tǒng)更多的是允許分區(qū)后各子系統(tǒng)依然保持CA。[單機數(shù)據(jù)庫]

CP without A

如果不要求A（可用），相當于每個請求都需要在Server之間強一致，而P（分區(qū)）會導致同步時間無限延長，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫分布式事務都屬于這種模式。[數(shù)據(jù)庫強一致集群，eg：Oracle在確認子節(jié)點插入成功后才返回]

AP wihtout C

要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點之間可能會失去聯(lián)系，為了高可用，每個節(jié)點只能用本地數(shù)據(jù)提供服務，而這樣會導致全局數(shù)據(jù)的不一致性?，F(xiàn)在眾多的NoSQL都屬于此類。[數(shù)據(jù)庫高可用集群，eg：主備模式，在主節(jié)點插入成功后就返回]

互聯(lián)網(wǎng)系統(tǒng)一般是要求AP然后保持最終一致；金融系統(tǒng)一般是保持CA舍棄P

BASE

由于BASE理論需要在一致性和可用性方面做出權(quán)衡，因此涌現(xiàn)了很多關(guān)于一致性的算法和協(xié)議。其中比較著名的有二階提交協(xié)議（2 Phase Commitment Protocol），三階提交協(xié)議（3 Phase Commitment Protocol）和Paxos算法

二階提交協(xié)議和三階提交協(xié)議就是基于XA規(guī)范提出的其中，二階段提交就是實現(xiàn)XA分布式事務的關(guān)鍵。

XA規(guī)范

XA規(guī)范是由 X/Open組織（即現(xiàn)在的 Open Group ）定義的分布式事務處理模型。 X/Open DTP 模型（ 1994 ）包括

• 應用程序（ AP ）
• 事務管理器（ TM ）：交易中間件等
• 資源管理器（ RM ）：關(guān)系型數(shù)據(jù)庫等
• 通信資源管理器（ CRM ）：消息中間件等

二階段提交

• 準備階段

事務詢問：協(xié)調(diào)者向所有的參與者詢問，是否準備好了執(zhí)行事務，并開始等待各參與者的響應。
執(zhí)行事務：各參與者節(jié)點執(zhí)行事務操作。如果本地事務成功，將Undo和Redo信息記入事務日志中，但不提交；否則，直接返回失敗，退出執(zhí)行。
各參與者向協(xié)調(diào)者反饋事務詢問的響應：如果參與者成功執(zhí)行了事務操作，那么就反饋給協(xié)調(diào)者 Yes響應，表示事務可以執(zhí)行提交；如果參與者沒有成功執(zhí)行事務，就返回No給協(xié)調(diào)者，表示事務不可以執(zhí)行提交。

• 提交階段

提交事務過程如下
發(fā)送提交請求：協(xié)調(diào)者向所有參與者發(fā)出commit請求。
事務提交：參與者收到commit請求后，會正式執(zhí)行事務提交操作，并在完成提交之后，釋放整個事務執(zhí)行期間占用的事務資源。
反饋事務提交結(jié)果：參與者在完成事務提交之后，向協(xié)調(diào)者發(fā)送Ack信息。
事務提交確認：協(xié)調(diào)者接收到所有參與者反饋的Ack信息后，完成事務。

中斷事務過程如下
發(fā)送回滾請求：協(xié)調(diào)者向所有參與者發(fā)出Rollback請求。
事務回滾：參與者接收到Rollback請求后，會利用其在提交階段種記錄的Undo信息，來執(zhí)行事務回滾操作。在完成回滾之后，釋放在整個事務執(zhí)行期間占用的資源。
反饋事務回滾結(jié)果：參與者在完成事務回滾之后，想?yún)f(xié)調(diào)者發(fā)送Ack信息。
事務中斷確認：協(xié)調(diào)者接收到所有參與者反饋的Ack信息后，完成事務中斷。

二階段提交優(yōu)缺點

開源實現(xiàn)

Raincat

三階段提交

三階段提交（Three-phase commit），也叫三階段提交協(xié)議（Three-phase commit protocol），是二階段提交（2PC）的改進版本。
所謂的三個階段分別是：詢問，然后再鎖資源，最后真正提交。

• 第一階段：CanCommit

3PC的CanCommit階段其實和2PC的準備階段很像。協(xié)調(diào)者向參與者發(fā)送commit請求，參與者如果可以提交就返回Yes響應，否則返回No響應。
事務詢問：協(xié)調(diào)者向參與者發(fā)送CanCommit請求。詢問是否可以執(zhí)行事務提交操作。然后開始等待參與者的響應
響應反饋：參與者接到CanCommit請求之后，正常情況下，如果其自身認為可以順利執(zhí)行事務，則返回Yes響應，并進入預備狀態(tài)；否則反饋No。

• 第二階段：PreCommit
  協(xié)調(diào)者在得到所有參與者的響應之后，會根據(jù)結(jié)果執(zhí)行2種操作：執(zhí)行事務預提交，或者中斷事務

執(zhí)行事務預提交
發(fā)送預提交請求：協(xié)調(diào)者向所有參與者節(jié)點發(fā)出 preCommit 的請求，并進入 prepared 狀態(tài)。
事務預提交：參與者受到 preCommit 請求后，會執(zhí)行事務操作，對應 2PC 準備階段中的 “執(zhí)行事務”，也會 Undo 和 Redo 信息記錄到事務日志中。
各參與者響應反饋:如果參與者成功執(zhí)行了事務，就反饋 ACK 響應，同時等待指令：提交（commit） 或終止（abort）

中斷事務
發(fā)送中斷請求：協(xié)調(diào)者向所有參與者節(jié)點發(fā)出 abort 請求 。
中斷事務：參與者如果收到 abort 請求或者超時了，都會中斷事務。

• 第三階段：Do Commit
  該階段進行真正的事務提交，也可以分為以下兩種情況

執(zhí)行提交
發(fā)送提交請求：協(xié)調(diào)者接收到各參與者發(fā)送的ACK響應，那么他將從預提交狀態(tài)進入到提交狀態(tài)。并向所有參與者發(fā)送 doCommit 請求。
事務提交：參與者接收到 doCommit 請求之后，執(zhí)行正式的事務提交。并在完成事務提交之后釋放所有事務資源。
響應反饋：事務提交完之后，向協(xié)調(diào)者發(fā)送 ACK 響應。
完成事務：協(xié)調(diào)者接收到所有參與者的 ACK 響應之后，完成事務。

中斷事務
協(xié)調(diào)者沒有接收到參與者發(fā)送的 ACK 響應（可能是接受者發(fā)送的不是ACK響應，也可能響應超時），那么就會執(zhí)行中斷事務。
發(fā)送中斷請求：協(xié)調(diào)者向所有參與者發(fā)送 abort 請求。
事務回滾：參與者接收到 abort 請求之后，利用其在階段二記錄的 undo 信息來執(zhí)行事務的回滾操作，并在完成回滾之后釋放所有的事務資源。
反饋結(jié)果：參與者完成事務回滾之后，向協(xié)調(diào)者發(fā)送 ACK 消息。
中斷事務：協(xié)調(diào)者接收到參與者反饋的 ACK 消息之后，完成事務的中斷。

三階段提交優(yōu)缺點

開源實現(xiàn)

hmily

Paxos協(xié)議

Paxos協(xié)議中，有一組完全對等的參與節(jié)點（稱為accpetor），這組節(jié)點各自就某一事件做出決議，如果某個決議獲得了超過半數(shù)節(jié)點的同意則生效。Paxos協(xié)議中只要有超過一半的節(jié)點正常，就可以工作，能很好對抗宕機、網(wǎng)絡分化等異常情況。

Paxos協(xié)議中，有三類節(jié)點：

• Proposer：提案者。Proposer可以有多個，Proposer提出議案（value）。所謂value，在工程中可以是任何操作，例如“修改某個變量的值為某個值”、“設置當前primary為某個節(jié)點”等等。Paxos協(xié)議中統(tǒng)一將這些操作抽象為value。不同的Proposer可以提出不同的甚至矛盾的value，例如某個Proposer提議“將變量X設置為1”，另一個Proposer提議“將變量X設置為2”，但對同一輪Paxos過程，最多只有一個value被批準。

• Acceptor：批準者。Acceptor有N個，Proposer提出的value必須獲得超過半數(shù)(N/2+1)的Acceptor批準后才能通過。Acceptor之間完全對等獨立。

• Learner：學習者。Learner學習被批準的value。所謂學習就是通過讀取各個Proposer對value的選擇結(jié)果，如果某個value被超過半數(shù)Acceptor通過，則Learner學習到了這個value。這里類似Quorum機制，某個value需要獲得W=N/2+1的Acceptor批準，從而學習者需要至少讀取N/2+1個Accpetor，至多讀取N個Acceptor的結(jié)果后，能學習到一個通過的value。

上述三類角色只是邏輯上的劃分，實踐中一個節(jié)點可以同時充當這三類角色。

Paxos協(xié)議一輪一輪的進行，每輪都有一個編號。每輪Paxos協(xié)議可能會批準一個value，也可能無法批準一個value。如果某一輪Paxos協(xié)議批準了某個value，則以后各輪Paxos只能批準這個value。上述各輪協(xié)議流程組成了一個Paxos協(xié)議實例，即一次Paxos協(xié)議實例只能批準一個value，這也是Paxos協(xié)議強一致性的重要體現(xiàn)。

每輪Paxos協(xié)議分為兩個階段，準備階段和批準階段，在這兩個階段Proposer和Acceptor有各自的處理流程。

• 1 準備階段（占坑階段）
  • 1.1 第一階段A：Proposer選擇一個提議編號n，向所有的Acceptor廣播Prepare（n）請求。
  • 1.2 第一階段B：Acceptor接收到Prepare（n）請求，若提議編號n比之前接收的Prepare請求都要大，則承諾將不會接收提議編號比n小的提議，并且?guī)现癆ccept的提議中編號小于n的最大的提議，否則不予理會。
• 2 接受階段（提交階段）
  • 2.1 第二階段A：整個協(xié)議最為關(guān)鍵的點：Proposer得到了Acceptor響應
    • 2.1.1 如果未超過半數(shù)accpetor響應，直接轉(zhuǎn)為提議失敗。
    • 2.1.2 如果超過多數(shù)Acceptor的承諾，又分為不同情況：
      • 2.1.2.1 如果所有Acceptor都未接收過值（都為null），那么向所有的Acceptor發(fā)起自己的值和提議編號n，記住，一定是所有Acceptor都沒接受過值；
      • 2.1.2.2 如果有部分Acceptor接收過值，那么從所有接受過的值中選擇對應的提議編號最大的作為提議的值，提議編號仍然為n。但此時Proposer就不能提議自己的值，只能信任Acceptor通過的值，維護一但獲得確定性取值就不能更改原則
  • 2.2 第二階段B Acceptor接收到提議后，如果該提議版本號不等于自身保存記錄的版本號（第一階段記錄的），不接受該請求，相等則寫入本地

把握和理解這兩點就基本理解了paxos的精髓
1.理解第一階段accpetor的處理流程：如果本地已經(jīng)寫入了，不再接受和同意后面的所有請求，并返回本地寫入的值；如果本地未寫入，則本地記錄該請求的版本號，并不再接受其他版本號的請求，簡單來說只信任最后一次提交的版本號的請求，使其他版本號寫入失效
2.理解第二階段proposer的處理流程：未超過半數(shù)accpetor響應，提議失?。怀^半數(shù)的accpetor值都為空才提交自身要寫入的值，否則選擇非空值里版本號最大的值提交，最大的區(qū)別在于是提交的值是自身的還是使用以前提交的

Paxos能解決的問題

• database replication, log replication等， 如bdb的數(shù)據(jù)復制就是使用paxos兼容的算法。Paxos最大的用途就是保持多個節(jié)點數(shù)據(jù)的一致性

• naming service, 如大型系統(tǒng)內(nèi)部通常存在多個接口服務相互調(diào)用。

  • 1 通常的實現(xiàn)是將服務的ip/hostname寫死在配置中，當service發(fā)生故障時候，通過手工更改配置文件或者修改DNS指向的方法來解決。缺點是可維護性差，內(nèi)部的單元越多，故障率越大。
  • 2 LVS雙機冗余的方式，缺點是所有單元需要雙倍的資源投入。
    通過Paxos算法來管理所有的naming服務，則可保證high available分配可用的service給client。象ZooKeeper還提供watch功能，即watch的對象發(fā)生了改變會自動發(fā)notification, 這樣所有的client就可以使用一致的，高可用的接口。

• config配置管理

  • 1 通常手工修改配置文件的方法，這樣容易出錯，也需要人工干預才能生效，所以節(jié)點的狀態(tài)無法同時達到一致。
  • 2 大規(guī)模的應用都會實現(xiàn)自己的配置服務，比如用http web服務來實現(xiàn)配置中心化。它的缺點是更新后所有client無法立即得知，各節(jié)點加載的順序無法保證，造成系統(tǒng)中的配置不是同一狀態(tài)

• membership用戶角色/access control list, 比如在權(quán)限設置中，用戶一旦設置某項權(quán)限比如由管理員變成普通身份，這時應在所有的服務器上所有遠程CDN立即生效，否則就會導致不能接受的后果。

• 號碼分配。通常簡單的解決方法是用數(shù)據(jù)庫自增ID, 這導致數(shù)據(jù)庫切分困難，或程序生成GUID, 這通常導致ID過長。更優(yōu)雅的做法是利用paxos算法在多臺replicas之間選擇一個作為master, 通過master來分配號碼。當master發(fā)生故障時，再用paxos選擇另外一個master。

Paxos協(xié)議實現(xiàn)

微信PaxosStore：深入淺出Paxos算法協(xié)議
微信自研生產(chǎn)級paxos類庫PhxPaxos實現(xiàn)原理介紹
phxpaxos

小結(jié)