一、分布式架構介紹

什么是分布式系統

分布式系統指一個硬件或軟件組件分布在不同的網絡計算機上，彼此之間僅僅通過消息傳遞進行通信和協調的系統。

通俗的理解，分布式系統就是一個業務拆分成多個子業務，分布在不同的服務器節點，共同構成的系統稱為分布式系統，同一個分布式系統中的服務器節點在空間部署上是可以隨意分布的，這些服務器可能放在不同的機柜中，也可能在不同的機房中，甚至分布在不同的城市。

分布式與集群的區別

集群指多個服務器做同一個事件

分布式指多個服務器做不同事情

分布式系統特性

• 分布性

空間中隨機分布。這些計算機可以分布在不同機房，不同城市，甚至不同的國家

• 對等性

分布式系統中的計算機沒有主從之分，組成分布式系統的所有節點都是對等的；

• 并發性

同一個分布式系統的多個節點，可能會并發地操作一些共享資源，諸如數據庫或分布式存儲；

• 缺乏全局時鐘性

各個計算機之間是依賴于交互信息來進行相互通信，很難定義兩件事情的先后順序，缺乏全局始終控制序列；

• 故障總會發生

組成分布式的計算機，都有可能在某一時刻突然間崩掉。分的計算機越多，可能崩掉一個的機率就越大。如果再考慮到設計程序的異常故障，也會加大故障的概率。

• 處理單點故障

單點SPoF(Single Point Of Failure):某個角色或功能只有某一臺計算機在支撐，在這臺計算機上出現的故障是單點故障；

分布式系統面臨問題

• 通信異常

網絡本身的不可靠性，因此每次網絡通信都會伴隨著網絡不可用的風險（光纖、路由、DNS等硬件設備或系統的不可用），都會導致最終分布式系統無法順利進行一次網絡通信，另外，即使分布式系統各節點之間的網絡通信能夠正常運行，其延時也會大于單機操作，存在巨大的延時差別，也會影響消息的收發過程，因此消息丟失和 消息延遲變的非常普遍；

• 網絡分布

網絡之間出現了網絡不連通，但各個子網絡的內部網絡是正常的，從而導致整個系統的網絡環境被切分成若干個孤立的區域，分布式系統就會出現局部小集群，在極端情況下，這些小集群會獨立完成原本要整個分布式系統才能完成的功能，包括數據的事務處理，這就對分布式一致性提出非常大的挑戰；

• 節點故障

節點故障是分布式系統下另一個比較常見的問題，指的是組成分布式系統的服務器節點出現的宕機或“僵死”現象，根據經驗來說，每個節點都有可能出現故障，并且經常發生；

• 三態

分布式系統每一次請求與響應存在特有“三態”概念，即成功、失敗和超時；

• 重發

分布式系統在發生調用的時候可能會出現失敗、超時的情況，這個時候需要重新發起調用

• 冪等

一次和多次請求某一個資源對于資源本身應該具有同樣的結果（網絡超時等問題除外）。也就是說，其任意多次執行對資源本身所產生的影響均與一次執行的影響相同。

二、分布式理論

分布式數據一致性，指的是數據在多份副本中存儲時，各副本中的數據是一致的；

分布式系統當中，數據往往會有多個副本。多個副本就需要保證數據的一致性。這就帶來了同步的問題，因為網絡延遲問題等因素，我們幾乎沒有辦法保證可以同時更新所有機器當中的包括備份所有數據，就會有數據不一致的情況。

一致性分為：

• 強一致性

在分布式系統中，如果每次讀取都能保證返回最近一次寫入的值，則稱系統具有強一致性。即所有節點上的數據都是實時同步的

• 弱一致性

系統在寫入成功后，會盡可能地保證到某個時間級別（比如秒級別）后，數據能夠達到一致狀態。

• 最終一致性

最終一致性也是弱一致性的一種，它無法保證數據更新后，所有后續的訪問都能看到最新數值，而是需要一個時間，在這個時間之后可以保證這一點（就是一段時間后，節點間的數據會最終達到一致狀態），而在這個時間內，數據也許是不一致的，這個系統無法保證強一致性的時間片段被稱為“不一致窗口”。不一致窗口的時間長短取決于很多因素，比如備份數據的個數、網絡傳輸延遲速度、系統負載等。

最終一致性在實際應用中又有多種變種：

• 因果一致性

如果進程A通知進程B它已更新了一個數據項，那么進程B的后續訪問將返回更新后的值。與進程A無因果關系的進程C的訪問遵守一般的最終一致性規則

• 讀己之所寫一致性

當進程A自己更新一個數據項之后，它總是訪問到更新過的值，絕不會看到舊值。這是因果一致性模型的一個特例

• 會話一致性

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

• 單調讀一致性

如果一個進程已經讀取到特定值，那么該進程不會讀取到該值以前的任何值

• 單調寫一致性

系統保證對同一個進程的寫操作串行化

CAP定理

CAP定理（CAP theorem），又被稱作布魯爾定理（Brewer's theorem），它指出對于一個分布式計算系統來說，不可能同時滿足以下三點：

一致性：所有節點訪問時都是同一份最新的數據副本

可用性：每次請求都能獲取到不錯的響應，但是不保證獲取的數據為最新數據

分區容錯性：分布式系統在遇到任何網絡分區故障的時候，仍然能夠對外提供滿足一致性和可用性的服務，除非整個網絡環境都發生了故障

因此，我們只能二選一：

CA（Consistency+Availability）:關注一致性和可用性，它需要非常嚴格的全體一致的協議；

CP（Consistency+partition tolerance）：關注一致性和分區容忍性。它關注的是系統里大多數人的一致性協議。這樣的系統只需要保證大多數結點數據一致，而少數的結點會在沒有同步到最新版本的數據時變成不可用的狀態。這樣能夠提供一部分的可用性。

AP(availability + partition tolerance):這樣的系統關心可用性和分區容忍性。因此，這樣的系統不能達成一致性，需要給出數據沖突，給出數據沖突就需要維護數據版本。

放棄一致性，滿足分區容錯，那么節點之間就有可能失去聯系，為了高可用，每個節點只能用本地數據提供服務，而這樣會容易導致全局數據不一致性。對于互聯網應用來說，機器數量龐大，節點分散，網絡故障正常不過了，那么此時就是保障AP，放棄C的場景，而從實際中理解，像網站這種偶爾沒有一致性是能接受的，但不能訪問問題就大了。

對于銀行來說，就是必須保證強一致性，也就是說C必須存在，那么就只有CA和CP兩種情況，當保障一致性和可用性（CA），那么一旦出現通信故障，系統將完全不可用。另一方面，如果保障了強一致性和分區容錯（CP），那么就具備了部分可用性。實際應該選擇什么，是需要通過業務場景進行權衡的（并不是所有情況都是CP好于CA，只能查看信息但不能更新信息有時候還不如直接拒絕服務）

BASE理論

BASE：全稱 Basically Available（基本可用）、Soft state（軟狀態）和Eventually consistent（最終一致性）三個短語的縮寫，BASE理論是對CAP中一致性和可用性權衡的結果，其來源于對大型互聯網分布式實踐的總結，是基于CAP定理逐步演化而來的。其核心思想是：既是無法做到強一致性，但每個應用都可以根據自身的業務特點，采用適當的方式來使系統達到最終一致性。

1、Basically Available(基本可用)

假設系統，出現 了不可預知的故障，但還是能用，相比較正常的系統而言：

• 響應時間上的損失：正常情況下的搜索引擎0.5秒即返回給用戶結果，而基本可用的搜索引擎可以在1秒返回結果；
• 功能上的損失：在一個電商網站上，正常情況下，用戶可以順利完成每一筆訂單，但是到了大促期間，為了保護購物系統的穩定性，部分消費者可能會被引導到一個降級頁面；

2、Soft state（軟狀態）

相對于原子性而言，要求多個節點的數據副本都是一致的，這是一種“硬狀態”。

軟狀態指的是：允許系統中的數據存在中間狀態，并認為該狀態不會影響系統的整體可用性，即允許系統在多個不同節點的數據副本存在數據延時。

3、Eventually consistent（最終一致性）

上面說的軟狀態，不可能一直是軟狀態，必須有個時間期限。在期限過后，應當保證所有副本保持數據一致性。從而達到數據的最終一致性。這個時間期限取決于網絡延時，系統負載，數據復制方案設計等等因素。

?

Base 理論是在 CAP 上發展的，CAP 理論描述了分布式系統中數據一致性、可用性、分區容錯性之間的制約關系，當你選擇了其中的兩個時，就不得不對剩下的一個做一定程度的犧牲。

Base 理論則是對 CAP 理論的實際應用，也就是在分區和副本存在的前提下，通過一定的系統設計方案，放棄強一致性，實現基本可用，這是大部分分布式系統的選擇，比如 NoSQL 系統、微服務架構。

三、分布式事務

兩階段提交協議（2PC）

兩階段提交協議，簡稱2PC（2 Prepare Commit）是比較常用的解決分布式事務問題的方式，要么所有參與進程都提交事務，要么都取消事務，即實現ACID中的原子性的常用手段。

分布式事務：事務提供一種操作本地數據庫的不可分割的一系列操作“要么什么都不做，要么做全套”的機制，而分布式事務就是為了操作不同數據庫的不可分割的一系列操作“要么什么都不做，要么做全套”的機制；

1、成功執行事務提交流程

階段一：

• 事務詢問

協調者向所有的參與者發送事務內容，詢問是否可以執行事務提交操作，并開始等待各參與者的響應；

• 執行事務
• 各參與者向協調者反饋事務詢問的響應

階段二：

• 發送提交請求

協調者向所有參與者發出commit請求；

• 事務提交

參與者收到commit請求后，會正式執行事務提交操作，并在完成提交之后釋放整個事務執行期間占用的事務資源；

• 反饋事務提交結果

參與者在完成事務提交之后，向協調者發送ACK信息；

• 完成事務

協調者接收到所有參與者反饋的ACK信息后，完成事務；

2、中斷事務流程

假如任何一個參與者向協調者反饋了NO響應，或者在等待超時之后，協調者尚無法接收到所有參與者的反饋響應，那么就會中斷事務

階段一：

• 事務詢問

協調者向所有的參與者發送事務內容，詢問是否可以執行事務提交操作，并開始等待各參與者的響應；

• 執行事務（寫本地的Undo/Redo日志）
• 各參與者向協調者反饋事務詢問的響應

階段二：

• 發送回滾請求

協調者向所有參與者發出Rollback請求

• 事務回滾

參與者接收到Rollback請求后，會利用其在階段一中記錄的Undo信息來執行事務回滾操作，并在完成回滾之后釋放在整個事務執行期間占用的資源；

• 反饋事務回滾結果

參與者在完成事務回滾之后，向協調者發送ACK信息；

• 中斷事務

協調者接收到所有參與者反饋的ACK信息后，完成事務中斷；

3、缺點

2PC原理簡單，但存在以下缺點：

• 同步阻塞

在二階段提交的執行過程中，所有參與該事務操作的邏輯都處于阻塞狀態，即當參與者占有公共資源時，其他節點訪問公共資源會處于阻塞狀態；

• 單點問題

若協調器出現問題，那么整個二階段提交流程將無法運轉，若協調者是在階段二中出現問題時，那么其他參與者將會一直處于鎖定事務資源的狀態中，而無法繼續完成事務操作；

• 數據不一致

在階段二中，執行事務提交的時候，當協調者向所有的參與者發送Commit請求之后，發生了局網絡異常或者是協調者在尚未發送完Commit請求之前自身發生了崩潰，導致最終只有部分參與者收到了Commit請求，于是會話出現數據不一致的現象；

• 太過保守

在進行事務提交詢問的過程中，參與者出現故障而導致協調者始終無法獲取到所有參與者的響應信息的話，此時協調者只能依靠自身的超時機制來判斷是否需要中斷事務，這樣的策略過于保守，即沒有完善的容錯機制，任意一個結點的失敗都會導致整個事務的失敗。

MySQL Cluster 內部數據的同步就是用的 2PC 協議。

三階段提交協議（3PC）

3PC，全稱 “three phase commit”，是 2PC 的改進版，將 2PC 的 “提交事務請求” 過程一分為二，共形成了由CanCommit、PreCommit和doCommit三個階段組成的事務處理協議。

三階段提交升級點（基于二階段）：

• 三階段提交協議引入 了超時機制；
• 在第一階段和第二階段中，引入了一個準備階段。保證了在最后提交階段之前各參與節點的狀態是一致的；

1、第一階段（CanCommit 階段）：

協調者向參與者發送commit請求，參與者如果可以提交就返回Yes響應，否則返回No響應；

• 事務詢問

協調者向參與者發送CanCommit請求。詢問是否可以執行事務提交操作。然后開始等待參與者的響應；

• 響應反饋

參與者接到CanCommit請求之后，正常情況下，如果其自身認為可以順利執行事務，則返回Yes響應，并進入預備狀態。否則，反饋No

2、第二階段（PreCommit 階段)：

協調者根據參與者的反應情況來決定是否可以執行事務的PreCommit操作。根據響應情況，有以下兩種可能

• Yes

• • 發送預提交請求：協調者向參與者發送PreCommit請求，并進入Prepared階段；
  • 事務預提交：參與者接收到PreCommit請求后，會執行事務操作，并將undo或redo信息記錄到事務日志中；
  • 響應反饋：如果參與者成功地執行了事務操作，則返回ACK響應，同時開始等待最終指令；

• No

假如有任何一個參與者向協調者發送了No響應，或者等待超時之后，協調者都沒有接到參與者的響應，那么就執行事務的中斷。則有：

• 發送中斷請求：協調者向所有參與者發送abort請求
• 中斷事務：參與者收到來自協調者的abort請求之后（或超時之后，仍未收到協調者的請求），執行事務的中斷

3、第三階段（doCommit 階段）：

該階段進入真正的事物提交，也可以分為執行提交和中斷事務兩種情況。

• 執行成功

• • 發送提交請求：協調者接收到參與者發送的ACK響應，那么它將從預提交狀態進入提交狀態。并向所有參與者發送doCommit請求；
  • 事務提交：參與者接收到doCommit請求之后，執行正式的事務提交。并在完成事務提交之后釋放所有事務資源；
  • 響應反饋：事務提交完之后，向協調者發送ACK響應；
  • 完成事務：協調者接收到所有參與者的ACK響應之后，完成事務；

• 中斷事務

• • 發送中斷請求：協調者向所有參與者發送abort請求；
  • 事務回滾：參與者接收到abort請求之后，利用其在階段二記錄的undo信息來執行事務的回滾操作，并在完成回滾之后釋放所有的事務資源；
  • 反饋結果：參與者完成事物回滾后，向協調者發送ACK信息；
  • 中斷事務：協調者接收到所有參與者反饋的ACK消息之后，執行事務的中斷；

注意：一旦進入階段三，可能會出現2 種故障：協調者出現問題、協調者和參與者之間的網絡故障

如果出現了任一一種情況，最終都會導致參與者無法收到doCommit請求或者abort請求，針對這種情況，參與者都會在等待超時之后，繼續進行事務提交，也就出現數據的不一致

4、2PC對比3PC

• 首先對于協調者和參與者都設置了超時機制（在2PC中，只有協調者擁有超時機制，即如果在一定時間內沒有收到參與者的消息則默認失敗），主要是避免了參與者在長時間無法與協調者節點通訊（協調者掛掉了）的情況下，無法釋放資源的問題，因為參與者自身擁有超時機制會在超時后，自動進行本地commit從而進行釋放資源。而這種機制也側面降低了整個事務的阻塞時間和范圍。
• 通過CanCommit、PreCommit、DoCommit三個階段的設計，相較于2PC而言，多設置一個緩沖階段保證了在最后提交階段之前各參與節點的狀態是一致的；
• PreCommit是一個緩沖，保證了在最后提交階段之前各參與節點的狀態是一致的；

3PC協議并沒有完全解決數據一致性問題

TCC事務

TCC是Try、Confirm、Cancel三個詞語的縮寫，TCC要求每個分支事務實現三個操作：預處理Try、確認Confirm、撤銷Cancel。Try操作做業務檢查及資源預留，Confirm做業務確認操作，Cancel實現一個與Try相反的操作即回滾操作。TM首先發起所有的分支事務的try操作，任何一個分支事務的try操作執行失敗，TM將會發起所有分支事務的Cancel操作，若try操作全部成功，TM將會發起所有分支事務的Confirm操作，其中Confirm/Cancel操作若執行失敗，TM會進行重試。

分支事務失敗的情況：

TCC分為三個階段：

1.Try 階段是做業務檢查(一致性)及資源預留(隔離)，此階段僅是一個初步操作，它和后續的Confirm 一起才能真正構成一個完整的業務邏輯。

2.Confirm 階段是做確認提交，Try階段所有分支事務執行成功后開始執行 Confirm。通常情況下，采用TCC則認為 Confirm階段是不會出錯的。即：只要Try成功，Confirm一定成功。若Confirm階段真的出錯了，需引入重試機制或人工處理。

3.Cancel 階段是在業務執行錯誤需要回滾的狀態下執行分支事務的業務取消，預留資源釋放。通常情況下，采用TCC則認為Cancel階段也是一定成功的。若Cancel階段真的出錯了，需引入重試機制或人工處理。

4.TM事務管理器

TM事務管理器可以實現為獨立的服務，也可以讓全局事務發起方充當TM的角色，TM獨立出來是為了成為公

用組件，是為了考慮系統結構和軟件復用。

TM在發起全局事務時生成全局事務記錄，全局事務ID貫穿整個分布式事務調用鏈條，用來記錄事務上下文，追蹤和記錄狀態，由于Confirm 和cancel失敗需進行重試，因此需要實現為冪等，冪等性是指同一個操作無論請求多少次，其結果都相同。

Seata

整體機制

兩階段提交協議的演變：

• 一階段：業務數據和回滾日志記錄在同一個本地事務中提交，釋放本地鎖和連接資源。
• 二階段：

• • 提交異步化，非常快速地完成。
  • 回滾通過一階段的回滾日志進行反向補償。

一階段加載

在一階段，Seata會攔截“業務SQL”

解析SQL語義，找到“業務SQL" 要更新的業務數據，在業務數據被更新前，將其保存成"before image”

執行“業務SQL" 更新業務數據，在業務數據更新之后,

其保存成"after image”，最后生成行鎖。

以上操作全部在一個數據庫事務內完成, 這樣保證了一階段操作的原子性。

• 二階段提交

二階段如果順利提交的話，因為"業務SQL"在一階段已經提交至數據庫，所以Seata框架只需將一階段保存的快照數據和行鎖刪掉，完成數據清理即可。

二階段回滾

二階段如果是回滾的話，Seata 就需要回滾一階段已經執行的 “業務SQL"，還原業務數據。

回滾方式便是用"before image"還原業務數據；但在還原前要首先要校驗臟寫，對比“數據庫當前業務數據”和"after image"。

如果兩份數據完全一致就說明沒有臟寫， 可以還原業務數據，如果不一致就說明有臟寫, 出現臟寫就需要轉人工處理。

四、分布式算法

NWR協議

NWR是一種在分布式存儲系統中用于控制一致性級別的一種策略。在亞馬遜的云存儲系統中，就應用NWR來控制一致性。

• N：在分布式存儲系統中，有多少備份數據
• W:代表一次成功的更新操作要求至少有W份數據寫入成功
• R:代表一次成功的讀數據操作要求至少有R份數據成功讀取

NWR值的不同組合會產生不同的一致性效果，當W+R>N的時候，整個系統對于客戶端來講能保證強一致性。

以常見的N=3、W=2、R=2為例:

• N=3，表示，任何一個對象都必須有三個副本
• W=2表示，對數據的修改操作只需要在3個副本中的2個上面完成就返回
• R=2表示，從三個對象中要讀取到2個數據對象，才能返回

在分布式系統中，數據的單點是不允許存在的。所以，N必須大于2，N越高，系統的維護和整體成本就越高。工業界通常把N設置為3。

當W是2、R是2的時候，W+R>N，這種情況對于客戶端就是強一致性的。

當R+W<=N，無法保證數據的強一致性

Gossip協議

Gossip 協議也叫 Epidemic 協議 （流行病協議）。原本用于分布式數據庫中節點同步數據使用，后被廣泛用于數據庫復制、信息擴散、集群成員身份確認、故障探測等。

Gossip協議利用一種隨機的方式將信息傳播到整個網絡中，并在一定時間內使得系統內的所有節點數據一致。Gossip其實是一種去中心化思路的分布式協議，解決狀態在集群中的傳播和狀態一致性的保證兩個問題。

1、原理

Gossip 協議的消息傳播方式有兩種：反熵傳播和謠言傳播

1）反熵傳播

以固定的概率傳播所有的數據。所有參與節點只有兩個狀態：Suspective(病原)、Infective(感染)。過程是種子節點會把所有的數據都跟其他節點共享，以便消息節點之間數據的任何不一致，它可以保證最終、完全的一致。缺點是消息數量非常龐大，且無限制；通常只用于新加入節點的數據初始化。

2）謠言傳播

是以固定的概率僅傳播新到達的數據。所有參與節點有三種狀態：Suspective（病原）、Infective(感染)、Remove（愈除）。過程是消息只包含最新update，謠言消息在某個時間點之后會被標記為removed，并且不再被傳播。缺點是系統有一定的概率會不一致，通常用于節點間數據增量同步。

2、通信方式

Gossip 協議最終目的是將數據分發到網絡中的每一個節點。根據不同的具體應用場景，網絡中兩個節點之間存在三種通信方式：推送模式、拉取模式、推/拉模式

• Push

節點A將數據及對應的版本號推送給B節點，B節點更新A中比自己新的數據

• Pull

A僅將數據key,version推送給B，B將本地比A新的數據（key、value、version）推送給A，A更新本地

?

• Push/Pull

與Pull類似，只是多了一步，A再將本地比B新的數據推送給B，B則更新本地

3、優缺點

Gossip是一種去中心化的分布式協議，數據通過節點像病毒一樣逐個傳播。因為是指數級傳播，整體傳播速度非常快。

1）優點

• 擴展性：允許節點的任意增加和減少，新增節點的狀態最終會與其他節點一致；
• 容錯：任意節點的宕機和重啟都不會影響Gossip消息的傳播，具有天然的分布式系統容錯特性；
• 去中心化：無需中心節點，所有節點都是對等的，任意節點無需知道整個網絡狀況，只要網絡連通，任意節點可把消息散播到全網；
• 最終一致性：Gossip協議實現信息指數級的快速傳播，因此在新信息需要傳播時，消息可以快速地發送到全局節點，在有限的時間人能夠做到所有節點都擁有最新的數據；

2）缺點

• 消息延遲：節點隨機向少數幾個節點發送消息，消息最終是通過多個輪次的散播而到達全網；不可避免的造成消息延遲；
• 消息冗余：節點定期隨機選擇周圍節點發送消息，而收到消息的節點也會重復該步驟；不可避免的引起同一節點消息多次接收，增加消息處理壓力；

Gossip協議由于以上優缺點，所以適合于AP場景的數據 一致性處理，常見應用有：P2P網絡通信、Redis Cluster、Consul

Paxos算法

Paxos算法是基于消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分布式一致性問題最有效的算法之一。

Paxos的最大特點就是難，不僅難以理解，更難以實現。Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

1、解決什么問題

在常見的分布式系統中，總會發生諸如機器宕機或網絡異常（包括消息的延遲、丟失、重復、亂序、還有網絡分區）等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正確地在集群內部對某個數據的值達成一致，并且保證不論發生以上任何異常，都不會破壞整個系統的一致性。

這里某個數據的值并不只是狹義上的某個數，它可以是一條日志，也可以是一條命令（command）。。。根據應用場景不同，某個數據的值有不同的含義。

2PC和3PC的時候在一定程度上是可以解決數據一致性問題的。但是并沒有完全解決就是協調者宕機的情況。

如何解決2PC和3PC的存在的問題呢?

其實在引入多個協調者之后又引入主協調者。那么這個就是最簡單的一種Paxos算法。

Paxos的版本有: Basic Paxos , Multi Paxos, Fast-Paxos, 具體落地有Raft 和zk的ZAB協議

2、Basic Paxos相關概念

1）角色介紹

• Client:：客戶端

客戶端向分布式系統發起請求，并等待響應。例如，對分布式文件服務器中文件的寫請求。

• Proposer:提案發起者

提案者提倡客戶端請求，試圖說服Acceptor達成一致，并在發生沖突時充當協調者推動協議向前發展

• Acceptor：決策者，可以批準提案

Acceptor可以接受提案，并進行投票，投票結果是否通過以多數派為準，以如果某個提案被選定，那么該提案里的value就被選定了

• Learner：最終決策的學習者

學習者充當該協議的復制因素（不參與投票）

2）決策模型

3）basic paxos流程

basic paxos流程一共分為4個步驟：

• Prepare

Proposer提出一個提案，編號為N，此N大于這個Proposer之前所有提出的編號，請求Acceptor的多數人接受這個提案

• Promise

如果編號N大于此Acceptor之前接收的提案編號則接收，否則拒絕

• Accept

如果達到多數派，Proposer會發出accept請求，此請求包含提案編號和對應的內容

• Accepted

如果此Acceptor在此期間沒有接受到任何大于N的提案，則接收此提案內容，否則忽略

3、Basic Paxos流程圖

1）無故障的basic Paxos

2）Acceptor失敗時的basic Paxos

在下圖中，多數派中的一個Acceptor發生故障，因此多數派大小變為2。在這種情況下，BasicPaxos協議仍然成功。

?

3）Proposer失敗時的basic Paxos

Proposer在提出提案之后但在達成協議之前失敗。具體來說，傳遞到Acceptor的時候失敗了,這個時候需要選出新的Proposer（提案人）,那么 Basic Paxos協議仍然成功

4）當多個提議者發生沖突時的basic Paxos

最復雜的情況是多個Proposer都進行提案,導致Paxos的活鎖問題.

針對活鎖問題解決起來非常簡單: 只需要在每個Proposer再去提案的時候隨機加上一個等待時間即可.

4、Multi-Paxos流程圖

針對basic Paxos是存在一定得問題,首先就是流程復雜,實現及其困難, 其次效率低(達成一致性需要2輪RPC調用),針對basic Paxos流程進行拆分為選舉和復制的過程.

1）第一次流程-確定Leader

選舉1：在三個Acceptor選擇一個Leader即a,有一票通過和拒絕權利

復制2：復制到其他Acceptor和Learners，a+1代表一直使用同一個Leader

2）第二次流程-直接由Leader確認

5、Multi-Paxos角色重疊流程圖

Multi-Paxos在實施的時候會將Proposer，Acceptor和Learner的角色合并統稱為“服務器”。因此，最后只有“客戶端”和“服務器”。

開源的ZooKeeper(zab協議)，以及MySQL 5.7推出的用來取代傳統的主從復制的MySQL GroupReplication等紛紛采用Paxos算法解決分布式一致性問題。

Raft協議

斯坦福大學RamCloud項目中提出了易實現，易理解的分布式一致性復制協議 Raft。Java，

C++，Go 等都有其對應的實現之后出現的Raft相對要簡潔很多。引入主節點，通過競選確定主節點。節 點類型：Follower、Candidate 和 Leader

Leader 會周期性的發送心跳包給 Follower。每個 Follower 都設置了一個隨機的競選超時時間，一 般為 150ms~300ms，如果在這個時間內沒有收到 Leader 的心跳包，就會變成 Candidate，進入競選階段, 通過競選階段的投票多的人成為Leader 。

1、相關概念

節點狀態

• Leader（主節點）：接受 client 更新請求，寫入本地后，然后同步到其他副本中
• Follower（從節點）：從 Leader 中接受更新請求，然后寫入本地日志文件。對客戶端提供讀
• Candidate（候選節點）：如果 follower 在一段時間內未收到 leader 心跳。則判斷 leader

可能故障，發起選主提議。節點狀態從 Follower 變為 Candidate 狀態，直到選主結束

請求

TermId：任期號，時間被劃分成一個個任期，每次選舉后都會產生一個新的 termId，一個任期內只有一個 leader

RequestVot:請求投票，candidate 在選舉過程中發起，收到多數派響應后，成為 leader。

2、競選階段流程

1）分布式系統的最初階段，此時只有 Follower，沒有 Leader。Follower A 等待一個隨

機的競選超時時間之后，沒收到 Leader 發來的心跳包，因此進入競選階段。

2）此時 A 發送投票請求給其它所有節點。

3）其它節點會對請求進行回復，如果超過一半的節點回復了，那么該 Candidate 就會變成 Leader。

4）之后 Leader 會周期性地發送心跳包給 Follower，Follower 接收到心跳包，會重新開始計時。

3、Leader節點宕機

Follower在規定超時時間內沒有收到Leader心跳包就會變成 Candidate，進入競選階段, 通過競選階段的投票多的人成為Leader 。

4、多個Candidate競選

1） 如果有多個 Follower 成為 Candidate，并且所獲得票數相同，那么就需要重新開始投票

2）當重新開始投票時，由于每個節點設置的隨機競選超時時間不同，因此能下一次再次出現多個 Candidate 并獲得同樣票數的概率很低

5、日志復制

1）、來自客戶端的修改都會被傳入 Leader。注意該修改還未被提交，只是寫入日志中。

2）、Leader 會把修改復制到所有 Follower。

3）、Leader 會等待大多數的 Follower 也進行了修改，然后才將修改提交。

4）、 此時 Leader 會通知的所有 Follower 讓它們也提交修改，此時所有節點的值達成一致。

6、網絡分區

1）最初始正常情況下狀態,B節點會對其他4個節點發送心跳

2） 當出現網絡分區情況, 但是出現網絡分區的請求后,只能對A發送心跳,同時其他三個節點會再次選出 一個leader節點

7、網絡分區情況日志復制

1）不同分區寫入數據不同

2）最終E節點Termid最大成為Leader節點,同步節點數據,達成數據一致性

?

Consul、sentinel采用Raft協議解決一致性問題

Lease機制

Lease機制，翻譯過來即是租約機制，是一種在分布式系統常用的協議，是維護分布式系統數據一致性的一種常用工具。

Lease機制有以下幾個特點：

• Lease是頒發者對一段時間內數據一致性的承諾；
• 頒發者發出Lease后，不管是否被接收，只要Lease不過期，頒發者都會按照協議遵守承諾；
• Lease的持有者只能在Lease的有效期內使用承諾，一旦Lease超時，持有者需要放棄執行，重新申請Lease。

在分布式中最直觀的處理方法是在每個副本與主副本維護一個心跳，期望通過心跳是否存在而判斷對方是否依舊存活。 由于在某個時刻Node1主節點突然出現網絡抖動或者網絡中斷情況(注意:不是宕機),導致從節點無法接受到心跳

會在剩下的副節點中選取一個當主節點

主要解決思路有四種：

• 設計給容忍雙主的分布式協議
• Raft協議——通過Term版本高的同步低的
• 用lease機制
• 涉及去中心化Gossip協議

1、原理

1）引入中心節點負責下發Lease

2）出現網絡問題

在01:05期間如果出現網絡抖動導致其他節點申請Lease會申請失敗, 因為中心節點在01:10之前都會承認有主節點,不允許其他節點在申請Lease

3）如果網絡恢復

4）如果到01:10時間,主節點會進行續約操作,然后在下發新的Lease

5）如果主節點宕機,其他節點申請Lease也會失敗,承認主節點存在

6）副節點申請Lease,申請成功. 因為Lease過期

2、容錯

1）主節點宕機

lease機制天生即可容忍網絡、lease接收方的出錯,時間即Lease剩余過期時長

2）中心節點異常

頒發者宕機可能使得全部節點沒有lease，系統處于不可用狀態，解決的方法就是使用一個小集群而不是單一節點作為頒發者。

3）時差問題

中心節點與主節點之間的時鐘可能也存在誤差，只需要中心節點考慮時鐘誤差即可。

lease時間長短一般取經驗值1-10秒即可。太短網絡壓力大，太長則收回承諾時間過長影響可用性。

3、應用

1）GFS(Google 文件系統)中，Master通過lease機制決定哪個是主副本，lease在給各節點的心跳響應消息中攜帶。收不到心跳時，則等待lease過期，再頒發給其他節點。

2）chubby中，paxos選主后，從節點會給主頒發lease，在期限內不選其他節點為主。另一方面，主節點給每個client節點發送lease，用于判斷client死活。

五、分布式鎖

基于數據庫的分布式鎖

數據庫表鎖：通過在數據庫中創建一個表，表中包含鎖的信息（如鎖標識、鎖持有者、過期時間等）。當需要加鎖時，向表中插入一條記錄，如果插入成功則表示獲取鎖成功；釋放鎖時，刪除相應的記錄。這種方法依賴于數據庫的唯一索引來保證互斥性。
樂觀鎖：在數據庫表中增加版本號或時間戳字段，在更新數據時檢查版本號或時間戳是否發生變化，如果未變則更新數據并增加版本號或時間戳，否則表示數據已被其他事務修改，當前操作需重新嘗試。

基于Redis的分布式鎖

SETNX

Redis的SETNX（SET if Not eXists）命令是實現分布式鎖的一種簡單方式。當SETNX命令執行時，如果指定的key不存在，則將該key的值設為value，并返回1；如果key已存在，則不做任何操作，返回0。這樣就可以通過SETNX命令的返回值來判斷是否獲取鎖成功。但需要注意的是，SETNX命令本身不具備設置過期時間的功能，因此需要額外使用EXPIRE命令來設置鎖的過期時間，以避免死鎖。不過，在Redis 2.6.12及以后的版本中，可以使用SET命令的NX（Not Exists）選項和PX（設置key的過期時間，單位為毫秒）選項來同時完成這兩個操作，實現原子性。

Redisson

Redisson是一個在Redis的基礎上實現的一個Java駐內存數據網格（In-Memory Data Grid）。它不僅實現了分布式鎖，還提供了許多其他分布式服務和數據結構。Redisson的分布式鎖是基于Redis的發布/訂閱（Pub/Sub）功能和Lua腳本來實現的。當一個客戶端需要獲取鎖時，它會向Redis發送一個Lua腳本，該腳本會嘗試設置一個key的value（通常為客戶端的UUID或線程ID），并設置過期時間。如果設置成功，則表示獲取鎖成功；如果設置失敗（因為其他客戶端已經設置了該key），則客戶端會訂閱一個與鎖相關的頻道，并等待其他客戶端釋放鎖的通知。這種方式的好處是可以避免輪詢Redis服務器來檢查鎖的狀態，從而減少網絡開銷和CPU使用率。

import org.redisson.Redisson;  
import org.redisson.api.RedissonClient;  
import org.redisson.config.Config;  public class RedissonConfig {  public static RedissonClient createClient() {  Config config = new Config();  // 假設你使用的是單節點Redis  config.useSingleServer().setAddress("redis://127.0.0.1:6379");  // 如果使用哨兵、集群等其他模式，請相應配置  return Redisson.create(config);  }  
}import org.redisson.api.RLock;  
import org.redisson.api.RedissonClient;  public class DistributedLockExample {  public static void main(String[] args) {  // 獲取Redisson客戶端  RedissonClient redisson = RedissonConfig.createClient();  // 獲取分布式鎖  RLock lock = redisson.getLock("myLock");  try {  // 嘗試獲取鎖，最多等待100秒，上鎖以后10秒自動解鎖  // 注意：lock()方法在沒有設置leaseTime的情況下，默認是永久持有的，需要手動釋放  // 這里為了演示，我們設置了leaseTime為10秒  boolean isLocked = lock.tryLock(100, 10, TimeUnit.SECONDS);  if (isLocked) {  try {  // 執行需要同步的代碼  System.out.println("Lock acquired, executing critical section");  Thread.sleep(2000);  } catch (InterruptedException e) {  e.printStackTrace();  } finally {  // 釋放鎖  lock.unlock();  System.out.println("釋放鎖");  }  } else {  System.out.println("未獲取到鎖");  }  // 5. 關閉 Redisson 客戶端  redisson.shutdown();  }  
}

基于ZooKeeper的分布式鎖

ZooKeeper是一個開源的分布式協調服務，它使用Zab協議來保證數據的一致性。ZooKeeper的分布式鎖是通過創建臨時順序節點來實現的。當一個客戶端需要獲取鎖時，它會在ZooKeeper中創建一個臨時順序節點（該節點的名稱會包含一個序列號，表示創建的順序）。然后，客戶端會檢查自己創建的節點是否是所有節點中序列號最小的那個。如果是，則表示獲取鎖成功；如果不是，則客戶端會監聽前一個節點的刪除事件（因為ZooKeeper的臨時節點在客戶端斷開連接時會自動刪除）。一旦前一個節點被刪除，客戶端就會再次檢查自己是否是當前序列號最小的節點，并重復上述過程直到獲取鎖成功。這種方式的好處是它可以保證鎖的公平性和可重入性，并且ZooKeeper的集群特性還可以保證分布式鎖的高可用性。

import org.apache.curator.framework.CuratorFramework;  
import org.apache.curator.framework.CuratorFrameworkFactory;  
import org.apache.curator.retry.ExponentialBackoffRetry;  
import org.apache.curator.framework.recipes.locks.InterProcessMutex;  @Service  
public class DistributedLockService {  private static final String LOCK_PATH = "/your/lock/path";  private final CuratorFramework curatorFramework;  public DistributedLockService() {  RetryPolicy retryPolicy = new ExponentialBackoffRetry(1000, 3);  this.curatorFramework = CuratorFrameworkFactory.newClient("localhost:2181", retryPolicy);  this.curatorFramework.start();  }  public void withLock(Runnable runnable) throws Exception {  InterProcessMutex lock = new InterProcessMutex(curatorFramework, LOCK_PATH);  try {  if (lock.acquire(10, TimeUnit.SECONDS)) {  try {  runnable.run();  } finally {  lock.release();  }  }  } catch (Exception e) {  // 處理異常  }  }  // 確保在Spring容器關閉時關閉Curator客戶端  @PreDestroy  public void close() {  CuratorFrameworkUtils.closeQuietly(curatorFramework);  }  
}

基于ETCD的分布式鎖

ETCD是一個高可用的鍵值存儲系統，它內部采用Raft協議來保證數據的一致性。ETCD的分布式鎖是通過其Lease機制和Revision機制來實現的。當一個客戶端需要獲取鎖時，它會在ETCD中創建一個以某個前綴開頭的key，并設置該key的Lease（租約）。Lease是一個可以自動續期的租約，如果客戶端在租約到期前沒有續期，則ETCD會自動刪除該key。同時，ETCD還會為每個key分配一個Revision號，該號在每次事務后遞增，以保證key的版本一致性。客戶端在創建key時會獲取當前的Revision號，并監聽比自己小的Revision號的key的刪除事件。一旦監聽到前一個key的刪除事件，客戶端就會嘗試獲取鎖。這種方式的好處是它可以利用ETCD的集群特性和一致性算法來保證分布式鎖的高可用性和一致性。
?

綜上所述，分布式鎖有多種實現方式，每種方式都有其獨特的底層原理和適用場景。在實際應用中，可以根據具體的需求和場景選擇合適的分布式鎖實現方式。

六、分布式id生成方案

UUID（Universally Unique Identifier）

工作方式：UUID是通過一系列算法生成的128位數字，通常基于時間戳、計算機硬件標識符、隨機數等元素。
全局唯一性：算法設計確保了即使在分布式系統中也能生成全局唯一的ID。
優點：
實現簡單，無需網絡交互。
保證了ID的全球唯一性。
缺點：
通常不能保證順序性。
ID較長（36個字符），可能導致存儲和索引效率低下。
網絡依賴性：無網絡依賴。

數據庫自增ID

工作方式：基于數據庫的auto_increment自增ID機制。
順序性：保證了生成ID的順序性和唯一性。
優點：
簡單可靠，保證順序性。
缺點：
可能成為系統的單點故障，對數據庫有較高的依賴。
無法扛住高并發場景，有性能瓶頸。
網絡依賴性：高度依賴網絡，所有ID生成請求都需要訪問數據庫。

雪花算法（SnowFlake）

工作方式：Twitter開發的一種生成64位ID的服務，基于時間戳、節點ID和序列號。
時間戳：確保ID按時間順序增長。
優點：
ID有時間順序，長度適中（64位）。
生成速度快。
缺點：
對系統時鐘有依賴，時鐘回撥會導致ID沖突。
網絡依賴性：通常無需網絡交互，除非在多機器環境中同步機器ID。

Redis生成

工作方式：利用Redis的原子操作（如INCR和INCRBY命令）生成唯一的遞增數值。
分布式環境中的應用：在分布式環境中，可以部署多個Redis實例，每個實例可以獨立生成ID，或者通過配置不同的起始值和步長來確保ID的全局唯一性。
優點：
快速、簡單且易于擴展。
支持高并發環境。
缺點：
依賴于外部服務（Redis），需要管理和維護額外的基礎設施。
網絡依賴性：高度依賴網絡。