如何讓程序通過協(xié)作共同去達成一個業(yè)務目標？

答：1.使用分布式互斥 2.使用分布式選舉 3.使用分布式共識 4.使用分布式事務

④ 分布式協(xié)調與同步

1.分布式互斥算法

對于同一共享資源，一個程序正在使用的時候也不希望被其他程序打擾。這就要求同一時刻只能有一個程序能夠訪問這種資源。

在分布式系統(tǒng)里，這種排他性的資源訪問方式，叫作分布式互斥，而這種被互斥訪問的共享資源就叫作臨界資源。

• 分布式互斥算法一：集中式算法

  • 優(yōu)點：直觀、簡單、信息交互量少、易于實現(xiàn)、程序只需和協(xié)調者通信，程序之間無需通信

  • 缺點：協(xié)調者可能會成為系統(tǒng)的性能瓶頸、單點故障(使用主備)

  • 使用場景：較為廣泛

引入一個協(xié)調者程序，得到一個分布式互斥算法：

每個程序在需要訪問臨界資源時，先給協(xié)調者發(fā)送一個請求；

如果當前沒有程序使用這個資源，協(xié)調者直接授權請求程序訪問，否則，按照FIFO規(guī)則進行排隊等待；

如果有程序使用完資源，則通知協(xié)調者，協(xié)調者從隊列里取出排在最前面的請求，并給它發(fā)送授權消息，拿到授權消息的程序，可以直接去訪問臨界資源

一個程序完成一次臨界資源訪問，需要如下幾個流程和消息交互(三次)：

向協(xié)調者發(fā)送請求授權信息，1 次消息交互；

協(xié)調者向程序發(fā)放授權信息，1 次消息交互；

程序使用完臨界資源后，向協(xié)調者發(fā)送釋放授權，1 次消息交互。

• 分布式互斥算法二：分布式算法（組播和輪播算法）

  • 優(yōu)點：每個程序按時間順序公平地訪問資源、簡單粗暴、易于實現(xiàn)

  • 缺點：可用性比集中式算法低（1.臨界資源的程序增多時，容易產生“信令風暴” 2.一旦某一程序發(fā)生故障，會導致整個系統(tǒng)不可用）

  • 改進：如果檢測到一個程序故障，則直接忽略這個程序，無需再等待它的同意消息

  • 適用場景：節(jié)點數(shù)目少且變動不頻繁的系統(tǒng)，且由于每個程序均需通信交互，因此適合P2P結構的系統(tǒng)。(Hadoop)

當一個程序要訪問臨界資源時，先向系統(tǒng)中的其他程序發(fā)送一條請求消息（請求的資源、請求者的 ID，以及發(fā)起請求的時間），在接收到所有程序返回的同意消息后，才可以訪問臨界資源；

如果當前程序正在使用資源，其他程序申請了這個資源，那么當前程序會將這個申請資源的程序放在隊列（記錄請求資源的時間、對應的程序、申請的資源）里，等到釋放此資源，就向隊列里的第一個需要此資源的程序發(fā)送”同意使用資源“的消息，并從隊列移除此程序（機制：先到先得、投票需全票通過）

一個程序完成一次臨界資源的訪問，需要進行如下幾個流程和信息交互(2*(n-1))：

向其他 n-1 個程序發(fā)送訪問臨界資源的請求，總共需要 n-1 次消息交互；

需要接收到其他 n-1 個程序回復的同意消息，方可訪問資源，總共需要 n-1 次消息交互。

• 分布式互斥算法三：令牌環(huán)算法（一致性哈希）

  • 優(yōu)點：不需要像分布式算法那樣挨個征求其他程序的意見了，所以相對而言，在令牌環(huán)算法里單個程序具有更高的通信效率；同時，在一個周期內，每個程序都能訪問到臨界資源，因此令牌環(huán)算法的公平性也很好，甚至更好；
  • 缺點：不管環(huán)中的程序是否想要訪問資源，都需要接收并傳遞令牌，所以也會帶來一些無效通信(可以進行加權處理)；單點故障問題，可以這么改進：若某一個程序出現(xiàn)故障，則直接將令牌傳遞給故障程序的下一個程序，這樣穩(wěn)定性也挺好的
  • 適用場景：系統(tǒng)規(guī)模小，系統(tǒng)中每個程序使用臨界資源的頻率高且使用時間比較短

2.分布式選舉算法

• 分布式選舉算法一：Bully算法

  • 在所有活著的節(jié)點中，選取 ID 最大的節(jié)點作為主節(jié)點（比如 MongoDB 的副本集故障轉移功能）

• 分布式選舉算法二：Raft算法

  • 核心思想是“少數(shù)服從多數(shù)”，獲得投票最多的節(jié)點成為主。

  • 多數(shù)派選主算法通常采用奇數(shù)節(jié)點，以防兩個節(jié)點均獲得一半投票，無法選出主節(jié)點。

  • 集群中每個節(jié)點擁有 3 種角色（每一輪選舉，每個節(jié)點只能投一次票）：

    Leader：即主節(jié)點，同一時刻只有一個 Leader，負責協(xié)調和管理其他節(jié)點；
    
    Candidate：即候選者，每一個節(jié)點都可以成為 Candidate，節(jié)點在該角色下才可以被選為新的 Leader；
    
    Follower：Leader 的跟隨者，不可以發(fā)起選舉。
    

• 分布式選舉算法三：ZAB算法

  • ZAB 算法可以說是對 Raft 算法的改進，是為 ZooKeeper 實現(xiàn)分布式協(xié)調功能而設計的。

  • 多數(shù)派選主算法通常采用奇數(shù)節(jié)點，以防兩個節(jié)點均獲得一半投票，無法選出主節(jié)點。

  • 集群中每個節(jié)點擁有 3 種角色：

    Leader，主節(jié)點；
    
    Follower，跟隨者節(jié)點；
    
    Observer，觀察者，無投票權。
    

3.分布式共識算法

• 分布式選舉問題，其實就是傳統(tǒng)的分布式共識方法，主要是基于多數(shù)投票策略實現(xiàn)的。

4.分布式事務算法

事務具備四大基本特征 ACID，分布式事務，就是在分布式系統(tǒng)中運行的事務，由多個本地事務組合而成。

但隨著分布式系統(tǒng)規(guī)模不斷擴大，復雜度急劇上升，達成強一致性所需時間周期較長，限定了復雜業(yè)務的處理；

為了適應復雜業(yè)務，出現(xiàn)了BASE理論，該理論的一個關鍵點就是采用最終一致性代替強一致性，算是ACID的弱化。

BASE理論：

由于CAP 不可能同時滿足，而分區(qū)容錯是對于分布式系統(tǒng)而言又是必須的，Base 理論是對 CAP 中一致性和可用性權衡的結果，是基于 CAP 定理逐步演化而來的，其核心思想是：既是無法做到強一致性，但每個應用都可以根據(jù)自身的業(yè)務特點，采用適當?shù)姆绞絹硎瓜到y(tǒng)達到最終一致性。

• Basically Available(基本可用)

  • 分布式系統(tǒng)在出現(xiàn)故障時，允許損失部分可用功能，保證核心功能可用。舉個例子：電商網站交易付款出問題了，商品依然可以正常瀏覽。

• Soft state（軟狀態(tài)）

  • 由于不要求強一致性，所以BASE允許系統(tǒng)中存在中間狀態(tài)（也叫軟狀態(tài)），這個狀態(tài)不影響系統(tǒng)可用性，如訂單的“支付中”、“數(shù)據(jù)同步中”等狀態(tài)，待數(shù)據(jù)最終一致后狀態(tài)改為“成功”狀態(tài)。

• Eventually consistent（最終一致性）

  • 經過一段時間，所有節(jié)點數(shù)據(jù)都會達到一致。如訂單中的“支付中”狀態(tài)，最終會變成“支付成功”或者“支付失敗”，使訂單狀態(tài)與實際交易結果達成一致，但需要一定時間的延遲和等待。

分布式事務主要是解決在分布式環(huán)境下，組合事務的一致性問題。實現(xiàn)分布式事務有以下 3 種基本方法：

• 基于 XA 協(xié)議的二階段提交協(xié)議方法(強一致性)

  • XA協(xié)議可以分為兩部分：事務管理器和本地資源管理器

  • 算法詳解（原理類似分布式互斥的集中式算法）

    • 優(yōu)點：
      • 簡單
    • 缺點：
      • 同步阻塞：二階段提交算法在執(zhí)行過程中，所有參與節(jié)點都是事務阻塞型的；也就是說，當本地資源管理器占有臨界資源時，其他資源管理器如果要訪問同一臨界資源，會處于阻塞狀態(tài)。
      • 單點故障：事務管理器會有此問題
      • 數(shù)據(jù)不一致：在提交階段，當協(xié)調者向參與者發(fā)送 DoCommit 請求之后，如果發(fā)生了局部網絡異常，或者在發(fā)送提交請求的過程中協(xié)調者發(fā)生了故障，就會導致只有一部分參與者接收到了提交請求并執(zhí)行提交操作，但其他未接到提交請求的那部分參與者則無法執(zhí)行事務提交，于是整個分布式系統(tǒng)便出現(xiàn)了數(shù)據(jù)不一致的問題。

    事務管理器作為協(xié)調者，負責各個本地資源的提交和回滾；
    資源管理器就是分布式事務的參與者，通常由數(shù)據(jù)庫實現(xiàn)（實現(xiàn)XA接口）
    二階段提交協(xié)議（2PC）用于保證分布式系統(tǒng)中事務提交時的數(shù)據(jù)一致性，是 XA 在全局事務中用于協(xié)調多個資源的機制。
    

    二階段提交協(xié)議算法（2PC）：投票（voting）和提交（commit）
    第一階段：投票
    協(xié)調者（Coordinator，即事務管理器）會向事務的參與者（Cohort，即本地資源管理器）發(fā)起執(zhí)行操作的 CanCommit 請求，并等待參與者的響應；
    參與者接收到請求后，會執(zhí)行請求中的事務操作，記錄日志信息但不提交；
    待參與者執(zhí)行成功，則向協(xié)調者發(fā)送“Yes”消息，表示同意操作；若不成功，則發(fā)送“No”消息，表示終止操作。
    
    第二階段：提交
    當所有的參與者都返回了響應后（Yes 或 No 消息）后，系統(tǒng)進入了提交階段；
    在提交階段，協(xié)調者會根據(jù)所有參與者返回的信息向參與者發(fā)送 DoCommit 或 DoAbort 指令：
    若協(xié)調者收到的都是“Yes”消息，則向參與者發(fā)送“DoCommit”消息，參與者會完成剩余的操作并釋放資源，然后向協(xié)調者返回“HaveCommitted”消息；
    如果協(xié)調者收到的消息中包含“No”消息，則向所有參與者發(fā)送“DoAbort”消息，此時發(fā)送“Yes”的參與者則會根據(jù)之前執(zhí)行操作時的回滾日志對操作進行回滾，然后所有參與者會向協(xié)調者發(fā)送“HaveCommitted”消息；
    協(xié)調者接收到“HaveCommitted”消息，就意味著整個事務結束了。
    

• 三階段提交協(xié)議方法3PC(強一致性)

  • 為了解決2PC的單點故障、部分數(shù)據(jù)不一致問題，引入了超時機制和準備階段，成為3PC

  • 算法詳解

    • 優(yōu)點：
      • 無單點故障問題、無同步阻塞問題、強一致性、同步執(zhí)行
    • 缺點：
      • 參與者接收到doCommit消息后，如果網絡出現(xiàn)分區(qū)，此時協(xié)調者所在的節(jié)點和參與者無法進行通信，參與者依然會進行事務的提交，會出現(xiàn)數(shù)據(jù)的不一致性（在 DoCommit 階段，當參與者向協(xié)調者發(fā)送 Ack 消息后，如果長時間沒有得到協(xié)調者的響應，在默認情況下，參與者會自動將超時的事務進行提交，不會像兩階段提交那樣被阻塞住）
      • 性能較低
      • 系統(tǒng)吞吐量不高

    協(xié)調者和參與者都引入超時機制；
    如果協(xié)調者或參與者在規(guī)定的時間內沒有接收到來自其他節(jié)點的響應，就會根據(jù)當前的狀態(tài)選擇提交或者終止整個事務。
    
    在第一階段和第二階段中間引入了一個準備階段，也就是在提交階段之前，加入了一個預提交階段；
    在預提交階段排除一些不一致的情況，保證在最后提交之前各參與節(jié)點的狀態(tài)是一致的；
    實現(xiàn)：把 2PC 的提交階段一分為二，全部有CanCommit、PreCommit、DoCommit 三個階段。
    
    第一階段：CanCommit，與2PC的第一階段類似
    協(xié)調者向參與者發(fā)送請求操作（CanCommit請求），詢問參與者是否可以執(zhí)行事務提交操作，然后等待參與者的響應；
    參與者收到CanCommit 請求之后，回復 Yes，表示可以順利執(zhí)行事務，否則回復 No。
    
    第二階段：PreCommit
    協(xié)調者根據(jù)參與者的回復情況，來決定是否可以進行 PreCommit 操作：
    如果所有參與者回復的都是“Yes”，那么協(xié)調者就會執(zhí)行事務的預執(zhí)行：
    1 發(fā)送預提交請求：協(xié)調者向參與者發(fā)送 PreCommit 請求，進入預提交階段。
    2 事務預提交：參與者接收到 PreCommit 請求后執(zhí)行事務操作，并將 Undo 和 Redo信息記錄到事務日志中。
    3 響應反饋：如果參與者成功執(zhí)行了事務操作，則返回 ACK 響應，同時開始等待最終指令。
    如果任何一個參與者向協(xié)調者發(fā)送了“No”消息，或者等待超時之后，協(xié)調者都沒有收到參與者的響應，就執(zhí)行中斷事務的操作：
    1 發(fā)送中斷請求：協(xié)調者向所有參與者發(fā)送“Abort”消息。
    2 終斷事務：參與者收到“Abort”消息之后，或超時后仍未收到協(xié)調者的消息，執(zhí)行事務的終斷操作。
    
    第三階段：DoCommit
    根據(jù) PreCommit 階段協(xié)調者發(fā)送的消息，進入執(zhí)行提交階段或事務中斷階段：
    執(zhí)行提交階段：
    1 發(fā)送提交請求：協(xié)調者接收到所有參與者發(fā)送的 Ack 響應，從預提交狀態(tài)進入到提交狀態(tài)，并向所有參與者發(fā)送 DoCommit 消息。
    2 事務提交：參與者接收到 DoCommit 消息之后，正式提交事務。完成事務提交之后，釋放所有鎖住的資源。
    3 響應反饋：參與者提交完事務之后，向協(xié)調者發(fā)送 Ack 響應。
    4 完成事務：協(xié)調者接收到所有參與者的 Ack 響應之后，完成事務。
    事務中斷階段：
    1 發(fā)送中斷請求：協(xié)調者向所有參與者發(fā)送 Abort 請求。
    2 事務回滾：參與者接收到 Abort 消息之后，利用其在 PreCommit 階段記錄的 Undo信息執(zhí)行事務的回滾操作，并釋放所有鎖住的資源。
    3 反饋結果：參與者完成事務回滾之后，向協(xié)調者發(fā)送 Ack 響應。
    4 終斷事務：協(xié)調者接收到參與者反饋的 Ack 消息之后，執(zhí)行事務的終斷，并結束事務。
    

• 基于消息的最終一致性方法(最終一致性)

  • 2PC和3PC有兩個共同的缺點：

    • 需要鎖定資源，降低系統(tǒng)性能
    • 沒有解決數(shù)據(jù)不一致的問題

  • 解決方案：引入MQ，用于在多個應用之間進行消息傳遞，將需要分布式處理的事務通過消息或者日志的方式異步執(zhí)行，消息或日志可以存到本地文件、數(shù)據(jù)庫或消息隊列中，再通過業(yè)務規(guī)則進行失敗重試。
    

• 總結對比2PC、3PC、MQ最終一致性