數據的一致性與一致性算法（CAP原則、Paxos算法、Raft算法、ZAB協議）

一、數據的一致性

1.定義

• 一些分布式系統通過復制數據來提高系統的可靠性和容錯性，并且將數據的不同的副本存放在不同的機器
• 在數據有多分副本的情況下，如果網絡、服務器或者軟件出現故障，會導致部分副本寫入成功，部分副本寫入失敗。這就造成各個副本之間的數據不一致，數據內容沖突。

2.模型

• 強一致性
  • 要求無論更新操作實在哪一個副本執行，之后所有的讀操作都要能獲得最新的數據。
• 弱一致性
  • 用戶讀到某一操作對系統特定數據的更新需要一段時間，我們稱這段時間為“不一致性窗口”。
• 最終一致性
  • 是弱一致性的一種特例，保證用戶最終能夠讀取到某操作對系統特定數據的更新。
  • 從客戶端來看，有可能暫時獲取的不是最新的數據，但是最終還是能訪問到最新的
  • 從服務端來看，數據存儲并復制到分布到整個系統超過半數的節點，以保證數據最終一致。

3.最終一致性

• 因果一致性（Casual Consistency）

  • 如果進程A通知進程B它已更新了一個數據項，那么進程B的后續訪問將返回更新后的值，且一次寫入將保證取代前一次寫入。
  • 與進程A無因果關系的進程C的訪問，遵守一般的最終一致性規則。
  • 查詢微博和評論

• 讀己之所寫一致性（read-your-writes）

  • 當進程A自己更新一個數據項之后，它總是訪問到更新過的值，絕不會看到舊值。這是因果一致性模型的一個特例。
  • 讀自己的數據都從主服務器去讀取，讀其他人的數據再從從服務器去讀取
  • 發表微博與修改微博

• 會話（Session）一致性

  • 這是上一個模型的實用版本，它把訪問存儲系統的進程放到會話的上下文中。只要會話還存
  • 在，系統就保證“讀己之所寫”一致性。如果由于某些失敗情形令會話終止，就要建立新的會話，而且系統的保證不會延續到新的會話。
  • 確保會話內訪問的都是最新的

• 單調（Monotonic）讀一致性

  • 如果進程已經看到過數據對象的某個最新值，那么任何后續訪問都不會返回在那個值之前的值。
  • 不會讀取最舊的數據

• 單調寫一致性

  • 系統保證來自同一個進程的寫操作順序執行。要是系統不能保證這種程度的一致性，就非常難以編程了。

  • 按照順序完成數據的書寫

二、CAP原則

1.定義

• CAP定理是2000年，由 Eric Brewer 提出來的。Brewer認為在分布式的環境下設計和部署系統時，有3個核心的需求，以一種特殊的關系存在。
• 這3個核心的需求是：Consistency，Availability和Partition Tolerance
• CAP定理認為：一個提供數據服務的存儲系統無法同時滿足數據一致性、數據可用性、分區容忍性

2.概念

• Consistency：
  • 一致性，這個和數據庫ACID的一致性類似，但這里關注的所有數據節點上的數據一致性和正確性，而數據庫的ACID關注的是在在一個事務內，對數據的一些約束。
  • 系統在執行過某項操作后仍然處于一致的狀態。在分布式系統中，更新操作執行成功后所有的用戶都應該讀取到最新值。
• Availability：
  • 可用性，每一個操作總是能夠在一定時間內返回結果。需要注意“一定時間”和“返回結果”。
  • “一定時間”是指系統結果必須在給定時間內返回。
  • “返回結果”是指系統返回操作成功或失敗的結果。
• Partition Tolerance：
  • 分區容忍性，是否可以對數據進行分區。這是考慮到性能和可伸縮性。

3.推導

• 如果要求對數據進行分區了，就說明了必須節點之間必須進行通信，涉及到通信，就無法確保在有限的時間內完成指定的任務
• 如果要求兩個操作之間要完整的進行，因為涉及到通信，肯定存在某一個時刻只完成一部分的業務操作，在通信完成的這一段時間內，數據就是不一致性的。
• 如果要求保證一致性，那么就必須在通信完成這一段時間內保護數據，使得任何訪問這些數據的操作不可用。

4.結論

• 在大型網站應用中，數據規模總是快速擴張的，因此可伸縮性即分區容忍性必不可少，規模變大以后，機器數量也會變得龐大，這是網絡和服務器故障會頻繁出現，要想保證應用可用，就必須保證分布式處理系統的高可用性。
• 在大型網站中，通常會選擇強化分布式存儲系統的可用性和伸縮性，在某種程度上放棄一致性。

三、Paxos算法

1.簡介

• Paxos算法是Leslie Lamport宗師提出的一種基于消息傳遞的分布式一致性算法，使其獲得2013年圖靈獎。
• Paxos在1990年提出，被廣泛應用于分布式計算中，Google的Chubby，Apache的Zookeeper都是基于它的理論來實現的
• Paxos算法解決的問題是分布式一致性問題，即一個分布式系統中的各個進程如何就某個值（決議）達成一致。
• 傳統節點間通信存在著兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messagespassing），Paxos是一個基于消息傳遞的一致性算法。

2.算法描述

Paxos描述了這樣一個場景，有一個叫做Paxos的小島(Island)上面住了一批居民，島上面所有的事情 由一些特殊的人決定，他們叫做議員(Senator)。議員的總數(Senator Count)是確定的，不能更 改。島上每次環境事務的變更都需要通過一個提議(Proposal)，每個提議都有一個編號(PID)，這個編 號是一直增長的，不能倒退。每個提議都需要超過半數((Senator Count)/2 +1)的議員同意才能生 效。每個議員只會同意大于當前編號的提議，包括已生效的和未生效的。如果議員收到小于等于當前編號 的提議，他會拒絕，并告知對方：你的提議已經有人提過了。這里的當前編號是每個議員在自己記事本上 面記錄的編號，他不斷更新這個編號。整個議會不能保證所有議員記事本上的編號總是相同的。現在議會 有一個目標：保證所有的議員對于提議都能達成一致的看法。 現在議會開始運作，所有議員一開始記事本上面記錄的編號都是0。有一個議員發了一個提議：將電費設 定為1元/度。他首先看了一下記事本，嗯，當前提議編號是0，那么我的這個提議的編號就是1，于是他 給所有議員發消息：1號提議，設定電費1元/度。其他議員收到消息以后查了一下記事本，哦，當前提議 編號是0，這個提議可接受，于是他記錄下這個提議并回復：我接受你的1號提議，同時他在記事本上記 錄：當前提議編號為1。發起提議的議員收到了超過半數的回復，立即給所有人發通知：1號提議生效！收 到的議員會修改他的記事本，將1好提議由記錄改成正式的法令，當有人問他電費為多少時，他會查看法 令并告訴對方：1元/度。 現在看沖突的解決：假設總共有三個議員S1-S3，S1和S2同時發起了一個提議:1號提議，設定電費。S1 想設為1元/度, S2想設為2元/度。結果S3先收到了S1的提議，于是他做了和前面同樣的操作。緊接著他 又收到了S2的提議，結果他一查記事本，咦，這個提議的編號小于等于我的當前編號1，于是他拒絕了這 個提議：對不起，這個提議先前提過了。于是S2的提議被拒絕，S1正式發布了提議: 1號提議生效。S2 向S1或者S3打聽并更新了1號法令的內容，然后他可以選擇繼續發起2號提議。

3.Paxos推斷

• 小島(Island) 服務器集群
• 議員(Senator) 單臺服務器
• 議員的總數(Senator Count)是確定的
• 提議(Proposal) 每一次對集群中的數據進行修改
• 每個提議都有一個編號(PID)，這個編號是一直增長的
• 每個提議都需要超過半數((Senator Count)/2 +1)的議員同意才能生效
• 每個議員只會同意大于當前編號的提議
• 每個議員在自己記事本上面記錄的編號，他不斷更新這個編號
• 整個議會不能保證所有議員記事本上的編號總是相同的
• 議會有一個目標：保證所有的議員對于提議都能達成一致的看法。
• 前期投票(>1/2)，后期廣播(all)
• Paxos算法
  • 數據的全量備份
  • 弱一致性 ——》最終一致性

4.算法模型延伸

如果Paxos島上的議員人人平等，在某種情況下會由于提議的沖突而產生一個“活鎖”（所謂活鎖我的理解是大 家都沒有死，都在動，但是一直解決不了沖突問題）。Paxos的作者在所有議員中設立一個總統，只有總統有 權發出提議，如果議員有自己的提議，必須發給總統并由總統來提出。 情況一：屁民甲(Client)到某個議員(ZK Server)那里詢問(Get)某條法令的情況(ZNode的數據)，議員毫 不猶豫的拿出他的記事本(local storage)，查閱法令并告訴他結果，同時聲明：我的數據不一定是最新 的。你想要最新的數據？沒問題，等著，等我找總統Sync一下再告訴你。 情況二：屁民乙(Client)到某個議員(ZK Server)那里要求政府歸還欠他的一萬元錢，議員讓他在辦公室等 著，自己將問題反映給了總統，總統詢問所有議員的意見，多數議員表示欠屁民的錢一定要還，于是總統發表 聲明，從國庫中拿出一萬元還債，國庫總資產由100萬變成99萬。屁民乙拿到錢回去了(Client函數返回)。 情況三：總統突然掛了，議員接二連三的發現聯系不上總統，于是各自發表聲明，推選新的總統，總統大選期 間政府停業，拒絕屁民的請求。

• 無主集群模型
  • 人人都會發送指令,投票
    • 投票人數有可能導致分區(分不同陣營)，
      • 6個節點 33對立
      • 類似于以前黨爭
  • 事務編號混亂，每個節點都有可能有自己的提議
    • 提議的編號不能重復和小于
• 有主集群模型
  • 只能有一個主發送指令，發送提議
  • 單主會單點故障，肯定有備用的方案
    • 重新選舉
    • 切換到備用節點
  • 如果存在多個主就會腦裂
• 主要集群中節點數目高于1/2+1，集群就可以正常運行

四、Raft算法

1.簡介

• Raft 適用于一個管理日志一致性的協議，相比于 Paxos 協議 Raft 更易于理解和去實現它。
• Raft 將一致性算法分為了幾個部分，包括領導選取（leader selection）、日志復制（logreplication）、安全（safety）
• http://thesecretlivesofdata.com/raft/

2.問題

• 分布式存儲系統通過維護多個副本來提高系統的availability，難點在于分布式存儲系統的核心問題：

  • 維護多個副本的一致性

• Raft協議基于復制狀態機（replicated state machine）

  • 一組server從相同的初始狀態起，按相同的順序執行相同的命令，最終會達到一致的狀態

  • 一組server記錄相同的操作日志，并以相同的順序應用到狀態機。

• Raft有一個明確的場景，就是管理復制日志的一致性

  • 每臺機器保存一份日志，日志來自于客戶端的請求，包含一系列的命令，狀態機會按順序執行這些命令。

3.角色分配

• Raft算法將Server劃分為3種狀態，或者也可以稱作角色：
  • Leader
    • 負責Client交互和log復制，同一時刻系統中最多存在1個。
  • Follower
    • 被動響應請求RPC，從不主動發起請求RPC。
  • Candidate
    • 一種臨時的角色，只存在于leader的選舉階段，某個節點想要變成leader，那么就發起
    • 投票請求，同時自己變成candidate

4.算法流程

• Term

  • Term的概念類比中國歷史上的朝代更替，Raft 算法將時間劃分成為任意不同長度的任期（term）。
  • 任期用連續的數字進行表示。每一個任期的開始都是一次選舉（election），一個或多個候選人會試圖成為領導人。如果一個候選人贏得了選舉，它就會在該任期的剩余時間擔任領導人。在某些情況下，選票會被瓜分，有可能沒有選出領導人，那么，將會開始另一個任期，并且立刻開始下一次選舉。Raft 算法保證在給定的一個任期最多只有一個領導人。

• RPC

  • Raft 算法中服務器節點之間通信使用遠程過程調用（RPCs）

  • 基本的一致性算法只需要兩種類型的 RPCs，為了在服務器之間傳輸快照增加了第三種 RPC。

    • RequestVote RPC：候選人在選舉期間發起

    • AppendEntries RPC：領導人發起的一種心跳機制，復制日志也在該命令中完成

    • InstallSnapshot RPC: 領導者使用該RPC來發送快照給太落后的追隨者

• 日志復制（Log Replication）

  • 主要用于保證節點的一致性，這階段所做的操作也是為了保證一致性與高可用性。

  • 當Leader選舉出來后便開始負責客戶端的請求，所有事務（更新操作）請求都必須先經過Leader處理

  • 日志復制（Log Replication）就是為了保證執行相同的操作序列所做的工作。

  • 在Raft中當接收到客戶端的日志（事務請求）后先把該日志追加到本地的Log中

  • 然后通過heartbeat把該Entry同步給其他Follower，Follower接收到日志后記錄日志然后向Leader發送ACK

  • 當Leader收到大多數（n/2+1）Follower的ACK信息后將該日志設置為已提交并追加到本地磁盤中

  • 通知客戶端并在下個heartbeat中Leader將通知所有的Follower將該日志存儲在自己的本地磁盤中。

五、ZAB協議

1.簡介

• ZAB（Zookeeper Atomic Broadcast） 協議是為分布式協調服務zookeeper專門設計的一種支持崩潰恢復的原子廣播協議。
• ZAB是ZooKeeper實現分布式數據一致性的核心算法，ZAB借鑒Paxos算法
• 在zookeeper中，主要依賴ZAB協議來實現分布式數據一致性，基于該協議，zookeeper實現了一種主備模式的系統架構來保持集群中各個副本之間的數據一致性。

2.ZAB協議的三個階段

• 發現：即要求zookeeper集群必須選擇出一個leader進程，同時leader會維護一個follower可用列表。將來客戶端可以這follower中的節點進行通信。
• 同步：leader要負責將本身的數據與follower完成同步，做到多副本存儲。這樣也是體現了CAP中CP。follower將隊列中未處理完的請求消費完成后，寫入本地事物日志中。
• 廣播：leader可以接受客戶端新的proposal請求，將新的proposal請求廣播給所有的follower。

3.協議核心

• ZAB協議的核心是定義了對于那些會改變ZooKeeper服務器數據狀態的事務請求處理方式，即：
  • 所有事務請求必須由一個全局唯一的服務器來協調處理，這樣的服務器被稱為Leader服務器，而余下的其他服務器稱為Follower服務器。Leader服務器負責將一個客戶端事務請求轉換成一個事務Proposal(提議)，并將該Proposal分發給集群中所有的Follower服務器。之后Leader服務器需要等待所有的Follower服務器的反饋，一旦超過半數的Follower服務器進行了正確的反饋后，那么Leader就會再次向所有的Follower服務器分發Commit消息，要求其將前一個Proposal進提交。

4.兩種基本模式

• 1》崩潰恢復之數據恢復
  • 當整個集群正在啟動時，或者當leader節點出現網絡中斷、崩潰等情況時，ZAB協議就會進入恢復模式并選舉產生新的leader，當leader服務器選舉出來后，并且集群中有過半的機器和該leader節點完成數據同步后（同步指的是數據同步，用來保證集群中過半的機器能夠和leader服務器的數據狀態保持一致），ZAB協議就會退出恢復模式。
• 2》消息廣播之原子廣播
  oposal進提交。

4.兩種基本模式

• 1》崩潰恢復之數據恢復
  • 當整個集群正在啟動時，或者當leader節點出現網絡中斷、崩潰等情況時，ZAB協議就會進入恢復模式并選舉產生新的leader，當leader服務器選舉出來后，并且集群中有過半的機器和該leader節點完成數據同步后（同步指的是數據同步，用來保證集群中過半的機器能夠和leader服務器的數據狀態保持一致），ZAB協議就會退出恢復模式。
• 2》消息廣播之原子廣播
  • 當集群中已經有過半的Follower節點完成了和Leader狀態同步以后，那么整個集群就進入了消息廣播模式。這個時候，在Leader節點正常工作時，啟動一臺新的服務器加入到集群，那這個服務器會直接進入數據恢復模式，和leader節點進行數據同步。同步完成后即可正常對外提供非事務請求的處理。

總結

以上是生活随笔為你收集整理的3.数据的一致性与一致性算法（CAP原则、Paxos算法、Raft算法、ZAB协议）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。