圖解分布式一致性算法
今天的文章，咱們會通過圖的方式，來深入學習和理解分布式一致性的實現(xiàn)原理。
開始的時候，咱們先來靈魂一問：什么是分布式一致性?
- 你的應(yīng)用是單節(jié)點嗎?
- 你的系統(tǒng)用戶多嗎、支持擴容嗎?
- 你的系統(tǒng)擴容后數(shù)據(jù)能保持一致嗎?
- 你的系統(tǒng)是否使用Raft、Paxos?
- ……
是否理解都沒關(guān)系，后面開始咱們的例子，通過圖的方式，來描述一致性的工作原理。
一、前奏
假設(shè)咱們有個系統(tǒng)。是個單節(jié)點的系統(tǒng)，只部署在一個實例上?？梢园阉斫獬梢粋€數(shù)據(jù)庫服務(wù)(Database Server)，實例上只有一個數(shù)據(jù)X，咱們后續(xù)的故事都是要圍繞操作變更X的值開展的。
咱們還有個客戶端(Client)，它要向節(jié)點 (Server) 寫數(shù)據(jù)，這個時候應(yīng)用代碼寫起來也簡單，這個數(shù)據(jù)的一致性很容易保證。
寫請求執(zhí)行后，客戶端和服務(wù)端的X數(shù)據(jù)都變成了8。
在用戶量少的時候，還天天操心啥時候來個百萬千萬用戶，等用戶稍微一多起來才發(fā)現(xiàn)，原來的一個實例扛不住了。這個時候為了支持更多用戶訪問，又擴容出來了更多的實例。
那么這下問題來了，當我們有多個實例節(jié)點間的時候，客戶端向其中一個節(jié)點寫了數(shù)據(jù)，如何再同步給其他節(jié)點呢?怎樣保證節(jié)點間數(shù)據(jù)的一致性呢?這就是分布式一致性問題。
二、 Raft 協(xié)議概覽
Raft 就是一個解決上述分布式一致性問題的協(xié)議。類似的協(xié)議還有Paxos、Zab等等。相比 Paxos，Raft 更易理解和實現(xiàn)。
咱們本次會俯瞰 Raft ， 來了解其工作原理。
在 Raft 里， 節(jié)點可能存在三種狀態(tài)：
- Follower
- Candidate
- Leader
在后面的圖里內(nèi)容中，上述三種狀態(tài)分別和下面三個圖一一對應(yīng)。
任何時候，都只會處于上述三種狀態(tài)中的一種。初始時候，所以節(jié)點都處于 Follower狀態(tài)。
如果follower 節(jié)點不再能接收到 leader 節(jié)點的消息， 他們的狀態(tài)就會變成 Candidate。
Candidate 節(jié)點會向其他節(jié)點發(fā)起投票請求，
其他節(jié)點也會投票進行響應(yīng)。
如果獲得了多數(shù)節(jié)點的投票，那 Candidate節(jié)點會成為Leader。
上面的這個過程就是分布式一致性協(xié)議中的「選舉」(Leader Election)。
后續(xù)所有對于系統(tǒng)的變更，都是通過Leader進行的。經(jīng)由 Leader 再到達其他節(jié)點。
每次 Client 的變更請求到達 leader 時，都會視為一個 Entry ，先添加到節(jié)點的日志 (Log)里。這個新增的 log entry，目前還并沒有提交，所以不會真的更新節(jié)點里 X 的值。
leader 首先會復制 log entry 給所有 follower節(jié)點。
然后， leader 會等待，直到多數(shù)節(jié)點都寫入了entry。
在收到多數(shù)節(jié)點的寫入響應(yīng)之后， leader 節(jié)點會將 entry 提交，此時 leader節(jié)點的值變成了 5.
然后 leader 會通知 follower 節(jié)點 自己的 entry 已經(jīng)提交了。
此時各個 follower 節(jié)點也會將之前收到的entry 進行提交。
整個系統(tǒng)目前所有的集群節(jié)點都達到了一致的狀態(tài)。這個過程一般稱為日志復制(Log Replication)。
三、 Leader Election
Raft 里有項控制選舉的超時時間設(shè)置。選舉超時時間是一個follower變成 candidate 的等待時間。值是150ms到300ms間的一個隨機值.
在選舉超時后， follower 會變成 candidate 開始一個新的選舉周期(term),同時會給自己投一票。
并且給其他節(jié)點發(fā)送請求投票的消息。
如果收到消息的節(jié)點在這一個周期還沒有投過票，那他需要給 candidate 投一票，并且該節(jié)點重置他的選舉超時時間。
如果 candidate 收到大多數(shù)節(jié)點的投票，就會成為leader。
leader 此時會在心跳檢測的周期內(nèi)，給給所有的follower發(fā)送Append Entries messages 。檢測的頻率是通過心跳超時時間設(shè)置的。
然后 每個 follower 也會給 Append Entries message 發(fā)送響應(yīng)。
這個選舉周期會一直持續(xù)直到某個 follower 停止心跳消息接收變成 candidate。
我們停掉 leader 再來看一下重新選舉的情況。
此時 節(jié)點 B 已經(jīng)停止，所以 節(jié)點A 和節(jié)點C 都收不到心跳消息。咱們前面說收不到心跳消息的話，節(jié)點的狀態(tài)會從 Follower 變成 Candidate，所以A 和C 在各自的選舉超時時間設(shè)置內(nèi)會改變狀態(tài)，
此時，節(jié)點 A 和 節(jié)點 C 都在等待，由于節(jié)點C先超時，所以會先開始一輪選舉。和上面的選舉過程一樣，會先新增Term，給自己投一票，并發(fā)送投票請求給其他節(jié)點。
在收到節(jié)點A的投票后，節(jié)點C現(xiàn)在升級為 term 2的 leader。
咱們前面總在說的「大多數(shù)節(jié)點投票」(a majority of votes)。這個能保證能在一個投票周期內(nèi)，只會產(chǎn)生一個 leader。
假設(shè)兩個節(jié)點同時從 Follower 狀態(tài)變成了 Candidate，這個時候兩者都會升級 Term，并請求其他節(jié)點不給自己投票。
這個時候兩者的 Term 其實是相同的，在同一個 Term 內(nèi) 其他節(jié)點只會投出一票，所以每個 Candidate 都只會收到一個節(jié)點的投票。
因為沒有超過「大多數(shù)」，所以都會不能成為 leader。這些節(jié)點就會等待新一輪的選舉，此時節(jié)點D先開始發(fā)起投票，并收到了大多數(shù)的投票，所以在Term 5 最終成為 leader。
四、 Log Replication
在選舉出一個leader之后，就需要復制所有的變更信息到系統(tǒng)里的所有節(jié)點。這些是通過和心跳檢測相同的的Append Entries message 來完成的。
我們來看下這個過程。一開始， client會向leader發(fā)送一個變更。
這個變更會加到 leader的log中，并會在下一次心跳檢測的時候發(fā)給 follower。
follower在收到消息之會，都會給 leader 發(fā)送響應(yīng)的 ack消息。
收到大多數(shù)的 follower 響應(yīng)之后， leader 會提交這個entry，并且發(fā)送響應(yīng)給 client。
并在下次心跳的時候，通知 follower 們執(zhí)行提交操作。
follower 在寫入完成后再給 leader 發(fā)送響應(yīng)。
此時 Client 又給給 leader 發(fā)送消息，要給X 來執(zhí)行個 加2 的操作。leader 將消息添加到 log 之后，給各個follower 發(fā)送心跳。
follower 們收到之后繼續(xù)返回響應(yīng)。
leader 收到 ack 之后，確認本次執(zhí)行進行 commit ，然后給 client 發(fā)回響應(yīng)。并在下次心跳的時候，把寫入發(fā)給各個 follower。
此時，咱們的系統(tǒng)里 X變成了7，各個節(jié)點的數(shù)據(jù)保持一致。
五、「大多數(shù)」是多少?
前面許多場景咱們都提到「大多數(shù)」。那大多數(shù)到底是多少呢?
比如我們在選舉的時候，在日志復制的時候，都需要大多數(shù) follower 發(fā)送回響應(yīng)消息。
這里的大多數(shù)和咱們?nèi)粘Ｉ罾锏幕疽恢?，即超過半數(shù)。比如一共有5個節(jié)點，此時有一個 candidate 起成為 leader，在投票過程中，至少要收到3個投票才行。
官網(wǎng)有個可以自定義時間進行交互的動圖，感興趣的朋友可以自行查看。
【本文為51CTO專欄作者“侯樹成”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號『Tomcat那些事兒』獲取授權(quán)】
