聊聊分布式架構(gòu)09——分布式中的一致性協(xié)議

這篇具有很好參考價值的文章主要介紹了聊聊分布式架構(gòu)09——分布式中的一致性協(xié)議。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

01從集中式到分布式

系統(tǒng)特點

集中式特點

分布式特點

事務(wù)處理差異

02一致性協(xié)議與Paxos算法

2PC（Two-Phase Commit）

階段一：提交事務(wù)請求

階段二：執(zhí)行事務(wù)提交

優(yōu)缺點

3PC（Three-Phase Commit）

階段一：CanCommit

階段二：PreCommit

階段三：doCommit

優(yōu)缺點

Paxos算法

拜占庭將軍問題

Paxos 算法概述

Paxos 算法的基本流程

03Google Chubby對Paxos的實現(xiàn)

聊聊分布式架構(gòu)09——分布式中的一致性協(xié)議,分布式架構(gòu),分布式,架構(gòu)

01從集中式到分布式

系統(tǒng)特點

集中式特點

集中式系統(tǒng)通常是單一服務(wù)器或單一數(shù)據(jù)中心的架構(gòu)。在集中式系統(tǒng)中，每個終端或客戶端機器僅僅負責數(shù)據(jù)的錄入和輸出，而數(shù)據(jù)的存儲與控制處理完全交由主機完成。但是，隨著業(yè)務(wù)不斷發(fā)現(xiàn)，加上單一大型主機進行系統(tǒng)擴容又比較困難。以阿里集團的“去IOE”計劃啟動，電商系統(tǒng)開始正式邁入分布式系統(tǒng)時代。

分布式特點

分布式系統(tǒng)是一個硬件或軟件組件分布在不同的網(wǎng)絡(luò)計算機上，彼此之間僅僅通過消息傳遞進行通信和協(xié)調(diào)的系統(tǒng)。不難理解，分布式系統(tǒng)都會有如下幾個特征:

分布性：多臺計算機在空間上隨意分布
對等性：沒有主/從之分，既沒有控制整個系統(tǒng)的主機，也沒有被控制的從機，所有計算機節(jié)點是對等的。
并發(fā)性：多個節(jié)點可能會并發(fā)地操作一些共享的資源，如數(shù)據(jù)庫或分布式存儲等。
缺乏全局時鐘：分布式系統(tǒng)由空間上隨意分布的多個進程組成的，在系統(tǒng)中，很難定義誰先誰后。
故障總會發(fā)生：系統(tǒng)中的所有計算機，都有可能發(fā)生任何形式的故障。

事務(wù)處理差異

事務(wù)具有四個特征：原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）和持久性（Durability），簡稱為事務(wù)的ACID特性。

原子性（Atomicity）：原子性表示事務(wù)是一個不可分割的工作單元。這意味著事務(wù)中的所有操作要么全部成功，要么全部失敗。如果事務(wù)的任何部分失敗，整個事務(wù)將被回滾，以確保數(shù)據(jù)庫狀態(tài)不會處于不一致的狀態(tài)。
一致性（Consistency）：一致性確保事務(wù)在執(zhí)行前和執(zhí)行后，數(shù)據(jù)庫的狀態(tài)保持一致。這意味著事務(wù)必須遵循數(shù)據(jù)庫的完整性約束和業(yè)務(wù)規(guī)則，以確保數(shù)據(jù)的正確性。如果事務(wù)違反了完整性約束，它將被回滾。
隔離性（Isolation）：隔離性指的是多個并發(fā)事務(wù)之間的獨立性。即使多個事務(wù)同時訪問數(shù)據(jù)庫，它們也不應(yīng)相互干擾。數(shù)據(jù)庫管理系統(tǒng)必須確保每個事務(wù)以獨立的方式訪問數(shù)據(jù)，以防止數(shù)據(jù)競爭和不一致性。
持久性（Durability）：持久性確保一旦事務(wù)成功提交，其影響將持久保存在數(shù)據(jù)庫中，即使在系統(tǒng)發(fā)生故障時也是如此。這意味著數(shù)據(jù)的更改不會因系統(tǒng)崩潰而丟失。

在單機數(shù)據(jù)庫中，我們很容易能夠?qū)崿F(xiàn)一套滿足ACID特性的事務(wù)處理系統(tǒng)，但是分布式的事務(wù)處理中問題卻層出不窮。其中最為突出的問題是在可用性和一致性之間永遠無法存在一個兩全其美的方案，針對這個難題的討論，出現(xiàn)了CAP和BASE這樣的分布式系統(tǒng)經(jīng)典理論。

CAP 定理（CAP Theorem）：
- 一致性（Consistency）：所有節(jié)點看到的數(shù)據(jù)是一致的。這意味著無論對于系統(tǒng)的任何部分，如果讀取操作返回了某個值，那么后續(xù)的讀操作都應(yīng)該返回相同的值。
- 可用性（Availability）：系統(tǒng)能夠響應(yīng)讀取和寫入請求，即系統(tǒng)在有限時間內(nèi)響應(yīng)每個非故障請求。
- 分區(qū)容忍性（Partition Tolerance）：系統(tǒng)在面臨網(wǎng)絡(luò)分區(qū)（節(jié)點之間的通信中斷）的情況下仍能繼續(xù)運行。
CAP 定理指出，分布式系統(tǒng)無法同時滿足這三個特性，最多只能同時滿足其中兩個。這意味著在面對網(wǎng)絡(luò)分區(qū)時，分布式系統(tǒng)需要在一致性和可用性之間做出權(quán)衡。不同的系統(tǒng)可以選擇不同的策略，具體取決于應(yīng)用程序的需求。
BASE 模型：
- 基本可用性（Basically Available）：系統(tǒng)保持基本的可用性，即使出現(xiàn)故障，也能繼續(xù)運行。系統(tǒng)可以放寬一些一致性要求，以保持可用性。
- 柔性狀態(tài)（Soft state）：系統(tǒng)的狀態(tài)可以隨時發(fā)生變化，而不一定要保持強一致性。在某些時刻，系統(tǒng)的部分數(shù)據(jù)可能會處于不一致狀態(tài)，但這并不妨礙系統(tǒng)的正常運行。
- 最終一致性（Eventually Consistent）：最終一致性意味著系統(tǒng)最終會在某個時刻達到一致狀態(tài)，盡管在某些時刻可能不是一致的。系統(tǒng)通過異步復(fù)制等機制來逐漸將數(shù)據(jù)帶入一致狀態(tài)。
BASE 模型強調(diào)了在分布式系統(tǒng)中放寬一致性要求，以提高可用性和性能。它適用于一些大規(guī)模、高并發(fā)、高可用性的系統(tǒng)，如互聯(lián)網(wǎng)應(yīng)用和分布式數(shù)據(jù)庫。

02一致性協(xié)議與Paxos算法

在對分布式系統(tǒng)進行架構(gòu)設(shè)計的過程中，往往需要在一致性和可用性之間反復(fù)權(quán)衡，于是產(chǎn)生了一系列的一致性協(xié)議和算法，其中最著名的就是二階段提交協(xié)議(2PC)、三階段提交協(xié)議(3PC)和Paxos算法了。

2PC（Two-Phase Commit）

整個事務(wù)是分為兩個階段提交，二階段提交是一種強一致性的算法。

階段一：提交事務(wù)請求

事務(wù)詢問

協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
執(zhí)行事務(wù)

各個參與者節(jié)點執(zhí)行事務(wù)操作，并將 Undo 和 Redo 信息記錄到事務(wù)日志中，盡量把提交過程中所有消耗時間的操作和準備都提前完成確保后面100%成功提交事務(wù)。
各個參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)

如果各個參與者成功執(zhí)行了事務(wù)操作，那么就反饋給參與者 yes 的響應(yīng)，表示事務(wù)可以執(zhí)行；如果參與者沒有成功執(zhí)行事務(wù)，就反饋給協(xié)調(diào)者 no 的響應(yīng)，表示事務(wù)不可以執(zhí)行。

階段二：執(zhí)行事務(wù)提交

在階段二中，協(xié)調(diào)者會根據(jù)反饋的情況決定最終是否可以進行事務(wù)提交操作。

執(zhí)行事務(wù)提交(都返回yes)
1. 發(fā)送提交請求
  
  協(xié)調(diào)者向所有參與者節(jié)點發(fā)出Commit請求。
2. 事務(wù)提交
  
  參與者接收到Commit請求后，正式執(zhí)行事務(wù)提交操作，并在完成提交后釋放事務(wù)執(zhí)行期間占用的資源
3. 反饋事務(wù)提交結(jié)果。
  
  參與者完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送Ack消息。
4. 完成事務(wù)
  
  協(xié)調(diào)者收到所有參與者反饋的Ack消息后，完成事務(wù)

聊聊分布式架構(gòu)09——分布式中的一致性協(xié)議,分布式架構(gòu),分布式,架構(gòu)

中斷事務(wù)(任何一個返回了no或者等待超時)
1. 發(fā)送回滾請求
  
  協(xié)調(diào)者向所有參與者發(fā)出RollBack請求。
2. 事務(wù)回滾
  
  參與者接收到RollBack請求后，利用階段一的Undo信息執(zhí)行回滾，在回滾完成后釋放事務(wù)執(zhí)行期間占用的資源。
3. 反饋事務(wù)回滾結(jié)果
  
  參與者在完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送Ack消息。
4. 中斷事務(wù)
  協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)中斷。

聊聊分布式架構(gòu)09——分布式中的一致性協(xié)議,分布式架構(gòu),分布式,架構(gòu)

優(yōu)缺點

優(yōu)點：原理簡單，實現(xiàn)方便。
缺點：同步阻塞，單點問題，腦裂。

3PC（Three-Phase Commit）

3PC是2PC的改進版，將二階段提交協(xié)議的“提交事務(wù)請求”過程一分為二，形成由CanCommit、PreCommit和do Commit三個階段組成的事務(wù)處理協(xié)議，如下所示：

階段一：CanCommit

事務(wù)詢問

協(xié)調(diào)者向所有參與者發(fā)送一個包含事務(wù)內(nèi)容的CanCommit請求，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)

參與者在接收到來自協(xié)調(diào)者的CanCommit請求后，正常情況下，如果自身認為能順利執(zhí)行事務(wù)，會反饋yes，進入預(yù)備狀態(tài)，否則反饋no。

階段二：PreCommit

根據(jù)階段一的反饋情況，包含兩種可能：

執(zhí)行事務(wù)預(yù)提交(都返回yes)
1. 發(fā)送預(yù)提交請求
  
  協(xié)調(diào)者向所有參與者發(fā)出PreCommit的請求，進入Prepared階段。
2. 事務(wù)預(yù)提交
  
  參與者收到PreCommit請求后，執(zhí)行實務(wù)操作，記錄Undo和Redo信息到事務(wù)日志中。
3. 各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的響應(yīng)
  
  如果參與者成功執(zhí)行了事務(wù)操作，反饋給協(xié)調(diào)者Ack響應(yīng)，等待最終指令：提交(commit)或中止(abort)
中斷事務(wù)(任何一個返回了no或者等待超時)
1. 發(fā)送中斷請求
  
  協(xié)調(diào)者向所有參與者發(fā)出abort請求。
2. 中斷事務(wù)
  
  無論是收到協(xié)調(diào)者的abort請求，還是等待協(xié)調(diào)者請求過程中出現(xiàn)超時，參與者都會中斷事務(wù)。

階段三：doCommit

該階段會進行真正的提交，可能包含兩種情況。

執(zhí)行提交
1. 發(fā)送提交請求
  
  假設(shè)協(xié)調(diào)者正常，并且收到所有的參與者的Ack響應(yīng)，將從“預(yù)提交”轉(zhuǎn)為“提交”狀態(tài)，向所有參與者發(fā)送doCommit請求。
2. 事務(wù)提交
  
  參與者收到doCommit請求，正式執(zhí)行事務(wù)提交，并在完成事務(wù)提交后釋放資源。
3. 反饋事務(wù)提交結(jié)果
  
  參與者完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送Ack消息。
4. 完成事務(wù)
  
  協(xié)調(diào)者收到所有參與者反饋的Ack消息，完成事務(wù)。
中斷事務(wù)
1. 發(fā)送中斷請求
  
  假設(shè)協(xié)調(diào)者正常，向所有參與者節(jié)點發(fā)送abort請求。
2. 事務(wù)回滾
  
  參與者收到abort請求，利用階段二中的Undo信息執(zhí)行事務(wù)回滾，回滾完成后釋放資源。
3. 反饋事務(wù)回滾結(jié)果
  
  參與者完成事務(wù)回滾后，向協(xié)調(diào)者發(fā)送Ack消息。
4. 中斷事務(wù)
  
  協(xié)調(diào)者收到所有參與者反饋的Ack消息后，中斷事務(wù)。

一旦進入階段三，可能會存在一下兩種故障：

協(xié)調(diào)者出現(xiàn)問題
協(xié)調(diào)者與參與者之間網(wǎng)絡(luò)出現(xiàn)問題

無論哪種情況，最終參與者都會在等待超時后，繼續(xù)進行事務(wù)提交。

優(yōu)缺點

優(yōu)點：降低了參與者的阻塞范圍，在單點故障之后繼續(xù)達成一致。
缺點：網(wǎng)絡(luò)分區(qū)的出現(xiàn)會導(dǎo)致協(xié)調(diào)者和參與者無法正常地網(wǎng)絡(luò)通信，參與者仍會提交事務(wù)，會導(dǎo)致數(shù)據(jù)的不一致性。

Paxos算法

Paxos算法是1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法。它需要解決的問題是如何在一個可能發(fā)生異常的分布式系統(tǒng)中快速且正確地在集群內(nèi)部對某個數(shù)據(jù)的值達成一致，且不會破壞系統(tǒng)的一致性。

拜占庭將軍問題

在拜占庭帝國，有一位將軍領(lǐng)導(dǎo)一支軍隊，他需要協(xié)調(diào)攻城的計劃。將軍的軍隊分布在城市周圍，而城市之間的通信需要通過信使傳遞消息。然而，帝國中存在叛變的將軍，他們可能會傳遞虛假的消息以迷惑其他將軍。問題的目標是找到一種方法，使得忠誠的將軍能夠在叛變的將軍存在的情況下達成共識，以決定是否進攻城市。

Paxos 算法概述

是一種用于分布式系統(tǒng)中的共識算法，它的主要目標是使多個節(jié)點在分布式環(huán)境中達成一致的決策。

Paxos 算法解決了拜占庭將軍問題中的信任問題和共識問題。它具有以下基本概念：

提議者（Proposers）：這些是節(jié)點，它們提出值（決策）并試圖說服其他節(jié)點接受這個值。
接受者（Acceptors）：這些是節(jié)點，它們接受提議并投票贊成或反對提議。
學(xué)習者（Learners）：這些是節(jié)點，它們學(xué)習提議的結(jié)果并在需要時應(yīng)用它們。

Paxos 算法的基本流程

提議階段：
- 提議者向接受者提出提議（值）。
- 接受者根據(jù)一定規(guī)則投票贊成或反對提議。規(guī)則包括：一個接受者只能投票一次，接受者可以投贊成或反對票，如果一個接受者已經(jīng)接受了一個提議，它不能再接受其他提議。
批準階段：
- 如果提議者獲得了多數(shù)接受者的贊成票，提議被批準。
- 提議者通知所有節(jié)點提案已被批準，節(jié)點學(xué)習(獲取)這個值。
學(xué)習階段：
- 學(xué)習者學(xué)習提案的結(jié)果，并在需要時應(yīng)用它。

03Google Chubby對Paxos的實現(xiàn)

Google Chubby 是 Google 內(nèi)部使用的分布式鎖服務(wù)，它基于 Paxos 算法實現(xiàn)。Chubby 允許分布式系統(tǒng)在多個節(jié)點之間協(xié)同工作，以確保數(shù)據(jù)一致性和強一致性。Google Chubby 不是開源的。

Chubby 本來應(yīng)該被設(shè)計成一個包含Paxos算法的協(xié)議庫，應(yīng)用程序可以基于這個庫方便地使用Paxos算法，但是它并沒有這么做，而是把Chubby設(shè)計成了一個需要訪問中心化節(jié)點的分布式鎖服務(wù)。既然是一個服務(wù)，那么它肯定需要是一個高可靠的服務(wù)。所以 Chubby 被構(gòu)建為一個集群，集群中存在一個中心節(jié)點（MASTER），采用Paxos協(xié)議，通過投票的方式來選舉一個獲得過半票數(shù)的服務(wù)器作為 Master，在 chubby 集群中，每個服務(wù)器都會維護一份數(shù)據(jù)的副本，在實際的運行過程中，只有 master 服務(wù)器能執(zhí)行事務(wù)操作，其他服務(wù)器都是使用paxos協(xié)議從master節(jié)點同步最新的數(shù)據(jù)。

以下是關(guān)于 Google Chubby 和其對 Paxos 的實現(xiàn)的一些簡要信息：

Paxos 算法實現(xiàn)：Chubby 使用 Paxos 算法作為其核心共識算法。Paxos 用于確保 Chubby 中的數(shù)據(jù)一致性。這意味著 Chubby 使用多個 Paxos 實例來處理不同類型的數(shù)據(jù)，例如鎖、配置信息等。
領(lǐng)導(dǎo)者選舉：Chubby 中有一個特殊的節(jié)點稱為 "master" 或 "leader"，它負責協(xié)調(diào)鎖服務(wù)并維護一致性。Chubby 使用 Paxos 來選擇 leader。Leader 選舉是 Paxos 的一個實例，用于確保只有一個節(jié)點成為 leader。
分布式鎖管理：Chubby 提供了分布式鎖服務(wù)，使得多個客戶端可以競爭獲取鎖。這些鎖的管理也基于 Paxos，確保鎖的一致性和互斥性。
配置管理：Chubby 用于存儲和維護配置信息，如服務(wù)的地址、節(jié)點信息等。這也是一個使用 Paxos 來維護一致性的應(yīng)用。
故障容忍性：Chubby 具有一定的故障容忍性。即使一些節(jié)點出現(xiàn)故障，Chubby 仍然能夠繼續(xù)工作。Paxos 的特性使得 Chubby 在節(jié)點失效和網(wǎng)絡(luò)分區(qū)的情況下能夠維護一致性。
性能優(yōu)化：Chubby 做了一些性能優(yōu)化，以提高 Paxos 算法的效率。這包括緩存機制和快速恢復(fù)機制。