溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java分布式一致性協議與Paxos，Raft算法是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java分布式一致性協議與Paxos，Raft算法是什么”吧！
由于BASE理論需要在一致性和可用性方面做出權衡，因此涌現了很多關于一致性的算法和協議。其中比較著名的有二階提交協議（2 Phase Commitment Protocol），三階提交協議（3 Phase Commitment Protocol）和Paxos算法。
本文要介紹的2PC協議，分為兩個階段提交一個事務。并通過協調者和各個參與者的配合，實現分布式一致性。
兩個階段事務提交協議，由協調者和參與者共同完成。
角色 XA概念 作用
協調者 事務管理器 協調各個參與者，對分布式事務進行提交或回滾
參與者 資源管理器 分布式集群中的節點
分布式事務是指會涉及到操作多個數據庫的事務，其實就是將對同一庫事務的概念擴大到了對多個庫的事務。目的是為了保證分布式系統中的數據一致性。
分布式事務處理的關鍵是：
需要記錄事務在任何節點所做的所有動作；
事務進行的所有操作要么全部提交，要么全部回滾。
2.1. XA規范的組成
XA規范是由 X/Open組織（即現在的 Open Group ）定義的分布式事務處理模型。 X/Open DTP 模型（ 1994 ）包括：
應用程序（ AP ）
事務管理器（ TM ）：交易中間件等
資源管理器（ RM ）：關系型數據庫等
通信資源管理器（ CRM ）：消息中間件等
2.2. XA規范的定義
XA規范定義了交易中間件與數據庫之間的接口規范（即接口函數），交易中間件用它來通知數據庫事務的開始、結束以及提交、回滾等。而XA接口函數由數據庫廠商提供。
二階提交協議和三階提交協議就是基于XA規范提出的其中，二階段提交就是實現XA分布式事務的關鍵。
2.3. XA規范編程規范
配置TM，給TM注冊RM作為數據源。其中，一個TM可以注冊多個RM。
AP向TM發起一個全局事務。這時，TM會發送一個XID（全局事務ID）通知各個RM。
AP從TM獲取資源管理器的代理（例如：使用JTA接口，從TM管理的上下文中，獲取出這個TM所管理的RM的JDBC連接或JMS連接）。
AP通過從TM中獲取的連接，間接操作RM進行業務操作。TM在每次AP操作時把XID傳遞給RM，RM正是通過這個XID關聯來操作和事務的關系的。
AP結束全局事務時，TM會通知RM全局事務結束。開始二段提交，也就是prepare - commit的過程。
XA規范的流程，大致如圖所示：
3.1. 二階段提交的定義
二階段提交的算法思路可以概括為：每個參與者將操作成敗通知協調者，再由協調者根據所有參與者的反饋情報，決定各參與者是否要提交操作還是中止操作。
所謂的兩個階段分別是：
第一階段：準備階段（投票階段）
第二階段：提交階段（執行階段）
3.1.1. 準備階段
準備階段分為三個步驟：
a. 事務詢問
協調者向所有的參與者詢問，是否準備好了執行事務，并開始等待各參與者的響應。
b. 執行事務
各參與者節點執行事務操作。如果本地事務成功，將Undo和Redo信息記入事務日志中，但不提交；否則，直接返回失敗，退出執行。
c. 各參與者向協調者反饋事務詢問的響應
如果參與者成功執行了事務操作，那么就反饋給協調者 Yes響應，表示事務可以執行提交；如果參與者沒有成功執行事務，就返回No給協調者，表示事務不可以執行提交。
3.1.2. 提交階段
在提交階段中，會根據準備階段的投票結果執行2種操作：執行事務提交，中斷事務。
提交事務過程如下：
a. 發送提交請求
協調者向所有參與者發出commit請求。
b. 事務提交
參與者收到commit請求后，會正式執行事務提交操作，并在完成提交之后，釋放整個事務執行期間占用的事務資源。
c. 反饋事務提交結果
參與者在完成事務提交之后，向協調者發送Ack信息。
d. 事務提交確認
協調者接收到所有參與者反饋的Ack信息后，完成事務。
中斷事務過程如下：
a. 發送回滾請求
協調者向所有參與者發出Rollback請求。
b. 事務回滾
參與者接收到Rollback請求后，會利用其在提交階段種記錄的Undo信息，來執行事務回滾操作。在完成回滾之后，釋放在整個事務執行期間占用的資源。
c. 反饋事務回滾結果
參與者在完成事務回滾之后，想協調者發送Ack信息。
d. 事務中斷確認
協調者接收到所有參與者反饋的Ack信息后，完成事務中斷。
3.1. 二階段提交的優缺點
優點：原理簡單，實現方便。
缺點：同步阻塞，單點問題，數據不一致，容錯性不好。
同步阻塞
在二階段提交的過程中，所有的節點都在等待其他節點的響應，無法進行其他操作。這種同步阻塞極大的限制了分布式系統的性能。
單點問題
協調者在整個二階段提交過程中很重要，如果協調者在提交階段出現問題，那么整個流程將無法運轉。更重要的是，其他參與者將會處于一直鎖定事務資源的狀態中，而無法繼續完成事務操作。
數據不一致
假設當協調者向所有的參與者發送commit請求之后，發生了局部網絡異常，或者是協調者在尚未發送完所有 commit請求之前自身發生了崩潰，導致最終只有部分參與者收到了commit請求。這將導致嚴重的數據不一致問題。
容錯性不好
如果在二階段提交的提交詢問階段中，參與者出現故障，導致協調者始終無法獲取到所有參與者的確認信息，這時協調者只能依靠其自身的超時機制，判斷是否需要中斷事務。顯然，這種策略過于保守。換句話說，二階段提交協議沒有設計較為完善的容錯機制，任意一個節點是失敗都會導致整個事務的失敗。
對于2PC協議存在的同步阻塞、單點問題，將在下一篇文章的3PC協議中引入解決方案。
由于二階段提交存在著諸如同步阻塞、單點問題、腦裂等缺陷。所以，研究者們在二階段提交的基礎上做了改進，提出了三階段提交。
與兩階段提交不同的是，三階段提交有兩個改動點。
引入超時機制 - 同時在協調者和參與者中都引入超時機制。
在第一階段和第二階段中插入一個準備階段，保證了在最后提交階段之前各參與節點的狀態是一致的。
三階段提交（Three-phase commit），也叫三階段提交協議（Three-phase commit protocol），是二階段提交（2PC）的改進版本。
所謂的三個階段分別是：詢問，然后再鎖資源，最后真正提交。
第一階段：CanCommit
第二階段：PreCommit
第三階段：Do Commit
2.1. 階段一：CanCommit
3PC的CanCommit階段其實和2PC的準備階段很像。協調者向參與者發送commit請求，參與者如果可以提交就返回Yes響應，否則返回No響應。
a. 事務詢問
協調者向參與者發送CanCommit請求。詢問是否可以執行事務提交操作。然后開始等待參與者的響應。
b. 響應反饋
參與者接到CanCommit請求之后，正常情況下，如果其自身認為可以順利執行事務，則返回Yes響應，并進入預備狀態；否則反饋No。
2.2. 階段二：PreCommit
協調者在得到所有參與者的響應之后，會根據結果執行2種操作：執行事務預提交，或者中斷事務。
2.2.1. 執行事務預提交
a. 發送預提交請求
協調者向所有參與者節點發出 preCommit 的請求，并進入 prepared 狀態。
b. 事務預提交
參與者受到 preCommit 請求后，會執行事務操作，對應 2PC 準備階段中的 “執行事務”，也會 Undo 和 Redo 信息記錄到事務日志中。
c. 各參與者響應反饋
如果參與者成功執行了事務，就反饋 ACK 響應，同時等待指令：提交（commit） 或終止（abort）。
2.2.2. 中斷事務
a. 發送中斷請求
協調者向所有參與者節點發出 abort 請求 。
b. 中斷事務
參與者如果收到 abort 請求或者超時了，都會中斷事務。
2.3. 階段三：Do Commit
該階段進行真正的事務提交，也可以分為以下兩種情況。
2.3.1. 執行提交
a. 發送提交請求
協調者接收到各參與者發送的ACK響應，那么他將從預提交狀態進入到提交狀態。并向所有參與者發送 doCommit 請求。
b. 事務提交
參與者接收到 doCommit 請求之后，執行正式的事務提交。并在完成事務提交之后釋放所有事務資源。
c. 響應反饋
事務提交完之后，向協調者發送 ACK 響應。
d. 完成事務
協調者接收到所有參與者的 ACK 響應之后，完成事務。
2.3.2. 中斷事務
協調者沒有接收到參與者發送的 ACK 響應（可能是接受者發送的不是ACK響應，也可能響應超時），那么就會執行中斷事務。
a. 發送中斷請求
協調者向所有參與者發送 abort 請求。
b. 事務回滾
參與者接收到 abort 請求之后，利用其在階段二記錄的 undo 信息來執行事務的回滾操作，并在完成回滾之后釋放所有的事務資源。
c. 反饋結果
參與者完成事務回滾之后，向協調者發送 ACK 消息。
d. 中斷事務
協調者接收到參與者反饋的 ACK 消息之后，完成事務的中斷。
3.1. 三階段提交的優點
相對于二階段提交，三階段提交主要解決的單點故障問題，并減少了阻塞的時間。
因為一旦參與者無法及時收到來自協調者的信息之后，他會默認執行 commit。而不會一直持有事務資源并處于阻塞狀態。
3.2. 三階段提交的缺點
三階段提交也會導致數據一致性問題。由于網絡原因，協調者發送的 abort 響應沒有及時被參與者接收到，那么參與者在等待超時之后執行了 commit 操作。
這樣就和其他接到 abort 命令并執行回滾的參與者之間存在數據不一致的情況。
用于達成共識性問題，即對多個節點產生的值，該算法能保證只選出唯一一個值。
主要有三類節點：
提議者（Proposer）：提議一個值；
接受者（Acceptor）：對每個提議進行投票；
告知者（Learner）：被告知投票的結果，不參與投票過程。
執行過程
規定一個提議包含兩個字段：[n, v]，其中 n 為序號（具有唯一性），v 為提議值。
下圖演示了兩個 Proposer 和三個 Acceptor 的系統中運行該算法的初始過程，每個 Proposer 都會向所有 Acceptor 發送提議請求。
當 Acceptor 接收到一個提議請求，包含的提議為 [n1, v1]，并且之前還未接收過提議請求，那么發送一個提議響應，設置當前接收到的提議為 [n1, v1]，并且保證以后不會再接受序號小于 n1 的提議。
如下圖，Acceptor X 在收到 [n=2, v=8] 的提議請求時，由于之前沒有接收過提議，因此就發送一個 [no previous] 的提議響應，設置當前接收到的提議為 [n=2, v=8]，并且保證以后不會再接受序號小于 2 的提議。其它的 Acceptor 類似。
如果 Acceptor 接收到一個提議請求，包含的提議為 [n2, v2]，并且之前已經接收過提議 [n1, v1]。如果 n1 > n2，那么就丟棄該提議請求；否則，發送提議響應，該提議響應包含之前已經接收過的提議 [n1, v1]，設置當前接收到的提議為 [n2, v2]，并且保證以后不會再接受序號小于 n2 的提議。
如下圖，Acceptor Z 收到 Proposer A 發來的 [n=2, v=8] 的提議請求，由于之前已經接收過 [n=4, v=5] 的提議，并且 n > 2，因此就拋棄該提議請求；Acceptor X 收到 Proposer B 發來的 [n=4, v=5] 的提議請求，因為之前接收到的提議為 [n=2, v=8]，并且 2 <= 4，因此就發送 [n=2, v=8] 的提議響應，設置當前接收到的提議為 [n=4, v=5]，并且保證以后不會再接受序號小于 4 的提議。Acceptor Y 類似。
當一個 Proposer 接收到超過一半 Acceptor 的提議響應時，就可以發送接受請求。
Proposer A 接收到兩個提議響應之后，就發送 [n=2, v=8] 接受請求。該接受請求會被所有 Acceptor 丟棄，因為此時所有 Acceptor 都保證不接受序號小于 4 的提議。
Proposer B 過后也收到了兩個提議響應，因此也開始發送接受請求。需要注意的是，接受請求的 v 需要取它收到的最大 v 值，也就是 8。因此它發送 [n=4, v=8] 的接受請求。
Acceptor 接收到接受請求時，如果序號大于等于該 Acceptor 承諾的最小序號，那么就發送通知給所有的 Learner。當 Learner 發現有大多數的 Acceptor 接收了某個提議，那么該提議的提議值就被 Paxos 選擇出來。
約束條件
正確性
指只有一個提議值會生效。
因為 Paxos 協議要求每個生效的提議被多數 Acceptor 接收，并且 Acceptor 不會接受兩個不同的提議，因此可以保證正確性。
可終止性
指最后總會有一個提議生效。
Paxos 協議能夠讓 Proposer 發送的提議朝著能被大多數 Acceptor 接受的那個提議靠攏，因此能夠保證可終止性。
1 Paxos算法
1.1 基本定義
算法中的參與者主要分為三個角色，同時每個參與者又可兼領多個角色:
⑴proposer 提出提案，提案信息包括提案編號和提議的value;
⑵acceptor 收到提案后可以接受(accept)提案;
⑶learner 只能”學習”被批準的提案;
算法保重一致性的基本語義:
⑴決議(value)只有在被proposers提出后才能被批準(未經批準的決議稱為”提案(proposal)”);
⑵在一次Paxos算法的執行實例中，只批準(chosen)一個value;
⑶learners只能獲得被批準(chosen)的value;
有上面的三個語義可演化為四個約束:
⑴P1:一個acceptor必須接受(accept)第一次收到的提案;
⑵P2a:一旦一個具有value v的提案被批準(chosen)，那么之后任何acceptor 再次接受(accept)的提案必須具有value v;
⑶P2b:一旦一個具有value v的提案被批準(chosen)，那么以后任何 proposer 提出的提案必須具有value v;
⑷P2c:如果一個編號為n的提案具有value v，那么存在一個多數派，要么他們中所有人都沒有接受(accept)編號小于n的任何提案，要么他們已經接受(accpet)的所有編號小于n的提案中編號最大的那個提案具有value v;
1.2 基本算法(basic paxos)
算法(決議的提出與批準)主要分為兩個階段:
prepare階段：
(1). 當Porposer希望提出方案V1，首先發出prepare請求至大多數Acceptor。Prepare請求內容為序列號
(2). 當Acceptor接收到prepare請求
a). 如果SN2>SN1，則忽略此請求，直接結束本次批準過程;
b). 否則檢查上次批準的accept請求
accept批準階段：
(1a). 經過一段時間，收到一些Acceptor回復，回復可分為以下幾種:
a). 回復數量滿足多數派，并且所有的回復都是
b). 回復數量滿足多數派，但有的回復為：
c). 回復數量不滿足多數派，Proposer嘗試增加序列號為SN1+，轉1繼續執行;
(1b). 經過一段時間，收到一些Acceptor回復，回復可分為以下幾種:
a). 回復數量滿足多數派，則確認V1被接受;
b). 回復數量不滿足多數派，V1未被接受，Proposer增加序列號為SN1+，轉1繼續執行;
(2). 在不違背自己向其他proposer的承諾的前提下，acceptor收到accept 請求后即接受并回復這個請求。
1.3 算法優化(fast paxos)
Paxos算法在出現競爭的情況下，其收斂速度很慢，甚至可能出現活鎖的情況，例如當有三個及三個以上的proposer在發送prepare請求后，很難有一個proposer收到半數以上的回復而不斷地執行第一階段的協議。因此，為了避免競爭，加快收斂的速度，在算法中引入了一個Leader這個角色，在正常情況下同時應該最多只能有一個參與者扮演Leader角色，而其它的參與者則扮演Acceptor的角色，同時所有的人又都扮演Learner的角色。
在這種優化算法中，只有Leader可以提出議案，從而避免了競爭使得算法能夠快速地收斂而趨于一致，此時的paxos算法在本質上就退變為兩階段提交協議。但在異常情況下，系統可能會出現多Leader的情況，但這并不會破壞算法對一致性的保證，此時多個Leader都可以提出自己的提案，優化的算法就退化成了原始的paxos算法。
一個Leader的工作流程主要有分為三個階段：
(1).學習階段 向其它的參與者學習自己不知道的數據(決議);
(2).同步階段 讓絕大多數參與者保持數據(決議)的一致性;
(3).服務階段 為客戶端服務，提議案;
1.3.1 學習階段
當一個參與者成為了Leader之后，它應該需要知道絕大多數的paxos實例，因此就會馬上啟動一個主動學習的過程。假設當前的新Leader早就知道了1-134、138和139的paxos實例，那么它會執行135-137和大于139的paxos實例的第一階段。如果只檢測到135和140的paxos實例有確定的值，那它最后就會知道1-135以及138-140的paxos實例。
1.3.2 同步階段
此時的Leader已經知道了1-135、138-140的paxos實例，那么它就會重新執行1-135的paxos實例，以保證絕大多數參與者在1-135的paxos實例上是保持一致的。至于139-140的paxos實例，它并不馬上執行138-140的paxos實例，而是等到在服務階段填充了136、137的paxos實例之后再執行。這里之所以要填充間隔，是為了避免以后的Leader總是要學習這些間隔中的paxos實例，而這些paxos實例又沒有對應的確定值。
1.3.4 服務階段
Leader將用戶的請求轉化為對應的paxos實例，當然，它可以并發的執行多個paxos實例，當這個Leader出現異常之后，就很有可能造成paxos實例出現間斷。
1.3.5 問題
(1).Leader的選舉原則
(2).Acceptor如何感知當前Leader的失敗，客戶如何知道當前的Leader
(3).當出現多Leader之后，如何kill掉多余的Leader
(4).如何動態的擴展Acceptor
Raft 和 Paxos 類似，但是更容易理解，也更容易實現。
Raft 主要是用來競選主節點。
單個 Candidate 的競選
有三種節點：Follower、Candidate 和 Leader。Leader 會周期性的發送心跳包給 Follower。每個 Follower 都設置了一個隨機的競選超時時間，一般為 150ms~300ms，如果在這個時間內沒有收到 Leader 的心跳包，就會變成 Candidate，進入競選階段。
下圖表示一個分布式系統的最初階段，此時只有 Follower，沒有 Leader。Follower A 等待一個隨機的競選超時時間之后，沒收到 Leader 發來的心跳包，因此進入競選階段。
此時 A 發送投票請求給其它所有節點。
其它節點會對請求進行回復，如果超過一半的節點回復了，那么該 Candidate 就會變成 Leader。
之后 Leader 會周期性地發送心跳包給 Follower，Follower 接收到心跳包，會重新開始計時。
多個 Candidate 競選
如果有多個 Follower 成為 Candidate，并且所獲得票數相同，那么就需要重新開始投票，例如下圖中 Candidate B 和 Candidate D 都獲得兩票，因此需要重新開始投票。
當重新開始投票時，由于每個節點設置的隨機競選超時時間不同，因此能下一次再次出現多個 Candidate 并獲得同樣票數的概率很低。
日志復制
來自客戶端的修改都會被傳入 Leader。注意該修改還未被提交，只是寫入日志中。
Leader 會把修改復制到所有 Follower。
Leader 會等待大多數的 Follower 也進行了修改，然后才將修改提交。
此時 Leader 會通知的所有 Follower 讓它們也提交修改，此時所有節點的值達成一致。
感謝各位的閱讀，以上就是“Java分布式一致性協議與Paxos，Raft算法是什么”的內容了，經過本文的學習后，相信大家對Java分布式一致性協議與Paxos，Raft算法是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
