CAP理論

CAP理論告訴我們，一個分布式系統不可能同時滿足以下三種

• 一致性（C:consistency）
• 可用性（A:Available）
• 分區容錯性（P:Partition Tolerance）

這三個基本要求，最多只能同時滿足其中的兩項，因為P是必須的，因此往往選擇就在CP或者AP中

（1）一致性（C:consistency）

? ? ? ? 在分布式環境中，一致性是指數據在多個副本之間是否能夠保持數據一致的特性。在一致性的需求下，當一個系統在數據一致的狀態下執行更新操作后，應該保證系統的數據仍然處于一致的狀態。

（2）可用性（A:Available）

? ? ? ?可用性是指系統提供的服務必須一直處于可用的狀態，對于用戶的每一個操作請求總是能夠在有限的時間內返回結果。

（3）分區容錯性（P:Partition Tolerance）

分布式系統在遇到任何網絡分區故障的時候，仍然需要保證對外提供滿足一致性和可用性，除非是整個網絡環境都發生了故障(多個副本，其中幾個副本down掉不影響系統使用)

Zookeeper保證的是CP

（1）Zookeeper不能保證每次服務請求的可用性。（注：在極端環境下，Zookeeper可能會丟棄一些請求，消費者程序需要重新請求才能獲得結果）。所以說，Zookeeper不能保證服務可用性

（2）進行Leader選舉時集群都是不可用。

Paxos算法

Paxos算法：一種基于消息傳遞且具有高度容錯特性的一致性算法。

Paxos算法解決的問題：就是如何快速正確的在一個分布式系統中對某個數據值達成一致，并且保證不論發生任何異常，都不會破壞整個系統的一致性。

Paxos算法描述：

在一個Paxos系統中，首先將所有節點劃分為Proposer（提議者），Acceptor（接受者）和Learner（學習者）。（注意：每個節點都可以身兼數職）。

一個完整的Paxos算法流程分為三個階段：

PrePare準備階段

• Proposer向多個Acceptor發出Propose請求Promise（承諾）
• Acceptor針對收到的Propose請求進行Promise（承諾）

Accept接受階段

• Proposer收到多數Acceptor承諾的Promise后，向Acceptor發出Propose請求（承諾）
• Acceptor針對收到的Propose請求進行Accept處理

Learn學習階段

• Proposer將形成的決議發送給所有Learners

Paxos算法流程：

（1）Prepare：Proposer生產全局唯一且遞增的Proposal ID，向所有Acceptor發送Propose請求，這里無需攜帶提案內容，只攜帶Proposal ID即可。

（2）Promise：Acceptor收到Propose請求后，做出“兩個承諾，一個應答”。

• 不再接受Proposal ID小于等于（注意：這里是<=）當前請求的Propose請求。
• 不再接受Proposal ID小于（注意：這里是<）當前請求的Accept請求。
• 不違背以前做出的承諾下，回復已經Accept過的提案中Proposal ID最大的那個提案的Value和Proposal ID，沒有則返回空值。

（3）Propose：Proposer收到多數Acceptor的Promise應答后，從應答中選擇Proposal ID最大的提案的Value，作為本次要發起的提案。如果所有應答的提案Value均為空值，則可以自己隨意決定提案Value。然后攜帶當前Proposal ID，向所有Acceptor發送Propose請求。

（4）Accept：Acceptor收到Propose請求后，在不違背自己之前做出的承諾下，接受并持久化當前Proposal ID和提案Value。

（5）Learn：Proposer收到多數Acceptor的Accept后，決議形成，將形成的決議發送給所有Leader。

情況1：

有A1，A2，A3，A4，A5 5位議員，就稅率問題進行決議

• A1發起1號Proposal的Propose，等待Promise承諾；
• A2-A5回應Promise；
• A1在收到兩份回復時就會發起稅率10%的Proposal；
• A2-A5回應Accept；
• 通過Proposal，稅率10%。

情況2：

• A1、A5同時發起Propose（序號分別為1,2）
• A2承諾A1，A4承諾A5，A3行為成為關鍵
• 情況1：A3先收到A1消息，承諾A1。
• A1發起Proposal（1, 10%），A2，A3接受。
• 之后A3又收到A5消息，回復A1：（1, 10%），并承諾A5。
• A5發起Proposal（2, 20%），A3，A4接受。之后A1，A5同時廣播決議。
• 情況2：A3先收到A1消息，承諾A1。之后立刻收到A5消息，承諾A5.
• A1發起Proposal（1, 10%），無足夠響應，A1重新Propose（序號3），A3再次承諾A1。
• A5發起Proposal（2, 20%），無足夠響應，A5重新Propose（序號4），A3再次承諾A5。
• ......

造成這種情況的原因是系統重有一個以上的Proposer，多個Proposers互相爭奪Acceptor，造成遲遲無法達成一致的情況，這對這種情況，一種改進的Paxos算法被提出：從系統中選出一個節點作為Leader，只有Leader能夠發起提案。這樣，一次Paxos流程中只有一個Proposer，不會出現活鎖的情況，此時只會出現例子中第一種情況。

ZAB協議：

Zab算法：Zab借鑒了Paxos算法，是特別為Zookeeper設計的支持崩潰恢復的原子廣播協議。基于該協議，Zookeeper設計為只有一臺客戶端（Leader）負責處理外部的寫事務請求，然后Leader客戶端將數據同步到其它Follower節點，即Zookeeper只有一個Leader可以發起提案。

Zab協議內容：

? ? ? ? 包括兩種基本的模式：消息廣播、崩潰恢復。

（1）客戶端發起一個寫操作請求。

（2）Leader服務器將客戶端的請求轉化為事務Proposal提案，同時為每個Proposal分配一個全局的ID，即zxid。

（3）Leader服務器為每個Follower服務器分配一個單獨的隊列，然后將需要廣播的Proposal依次放到隊列中去，并且根據FIFO策略進行消息發送。

（4）Follower接收到Proposal后，會首先將其以事務日志的方式寫入本地磁盤中，寫入成功后Leader反饋一個Ack(確認消息)響應消息。

（5）Leader接收到超過半數以上Follower的Ack響應消息后，即認為消息發送成功，可以發送commit消息。

（6）Leader向所有Follower廣播commit消息，同時自身也會完成事務提交。Follower接收到commit消息后，會將上一條事務提交。

（7）Zookeeper采用Zab協議的核心，就是只要有一臺服務器提交了Proposal，就要確認所有的服務器最終都能正確提交Proposal

崩潰恢復：

一旦Leader服務器出現崩潰或者由于網絡原因導致Leader服務器失去了與過半Follower的聯系，那么就會進入崩潰恢復模式

1）假設兩種服務器異常情況：

（1）假設一個事務在Leader提出之后，Leader掛了。

（2）一個事務在Leader上提交了，并且過半的Follower都響應Ack了，但是Leader在Commit消息發出之前掛了。

2）Zab協議崩潰恢復要求滿足以下兩個要求：

（1）確保已經被Leader提交的提案Proposal，必須最終被所有的Follower服務器提交。（已經產生的提案，Follower必須執行）

（2）確保丟棄已經被Leader提出的，但是沒有被提交的Proposal。（丟棄胎死腹中的提案）

崩潰恢復——Leader選舉：

崩潰恢復主要包括兩部分：Leader選舉和數據恢復

Leader選舉：根據上述要求，Zab協議需要保證選舉出來的Leader需要滿足以下條件：

（1）新選舉出來的Leader不能包含未提交的Proposal。即新Leader必須都是已經提交了Proposal的Follower服務器節點。

（2）新選舉的Leader節點中含有最大的zxid。這樣做的好處是可以避免Leader服務器檢查Proposal的提交和丟棄工作。

崩潰恢復——數據恢復：

崩潰恢復主要包括兩部分：Leader選舉和數據恢復

Zab如何數據同步：

（1）完成Leader選舉后，在正式開始工作之前（接收事務請求，然后提出新的Proposal），Leader服務器會首先確認事務日志中的所有的Proposal是否已經被集群中過半的服務器Commit。

（2）Leader服務器需要確保所有的Follower服務器能夠接收到每一條事務的Proposal，并且能將所有已經提交的事務Proposal應用到內存數據中。等到Follower將所有尚未同步的事務Proposal都從Leader服務器上同步過，并且應用到內存數據中以后，Leader才會把該Follower加入到真正可用的Follower列表中。