日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

分布式一致性算法概要

隨著各種高并發(fā)訪問、海量數(shù)據(jù)處理等應(yīng)用場景越來越多，為了應(yīng)對這些使用場景，分布式系統(tǒng)應(yīng)運(yùn)而生。分布式系統(tǒng)得以發(fā)展，得益于諸多優(yōu)點(diǎn)，比如：可以避免 單點(diǎn)故障 ，容易 橫向擴(kuò)展 等。所謂單點(diǎn)故障指的是：單個組件發(fā)生故障會導(dǎo)致整個系統(tǒng)的癱瘓，而容易橫向擴(kuò)展的意思是我們可以通過增加機(jī)器來提高整個系統(tǒng)的性能。分布式系統(tǒng)在帶來諸多優(yōu)點(diǎn)的同時，也帶來了一些挑戰(zhàn)，我們下面來重點(diǎn)描述清楚其中的一個核心挑戰(zhàn)： 在分布式系統(tǒng)中如何保證數(shù)據(jù)的一致性 。關(guān)于分布式系統(tǒng)的基本概念，可以參考相關(guān)的理論書籍。

在眾多分布式一致性協(xié)議中， paxos 算法經(jīng)過了嚴(yán)格的數(shù)學(xué)證明。然而由于該算法非常難以理解，尤其是在各種系統(tǒng)的實現(xiàn)時，一般采用 paxos 的簡化版本或者 paxos 的一些變種協(xié)議，比如 Raft 和 Zab 等。為此，本文選取 Raft 算法來進(jìn)行介紹。我們可以通過構(gòu)造一個如下的應(yīng)用場景來幫助我們理解一個算法。

以一個數(shù)據(jù)存儲系統(tǒng)為例，如果 client 想要在 server 上設(shè)置一個值，假如一開始有一個 server 和 一個 client，此時只要一個server 完成值的設(shè)置即可?？墒侨绻卸鄠€ server 存在的話，要如何保證所有的 server 節(jié)點(diǎn)上存儲的值是一致的呢？如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個節(jié)點(diǎn)執(zhí)行相同的操作序列，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個“一致性算法”以保證每個節(jié)點(diǎn)看到的指令一致。

Raft 算法介紹

在一個由 Raft 協(xié)議組織的集群中有三類角色：

• Leader（領(lǐng)袖）
• Follower（群眾）
• Candidate（候選人）

每個節(jié)點(diǎn)都會處于以上三種角色中的一種。

算法的主體大致可分為2個過程：

• 選舉(Leader Election)
• 日志同步(Log Replication)

下面我們分別介紹 Raft 算法中的選舉流程和日志同步流程，隨后會介紹 Raft 算法對一些異常情況的處理。

選舉

選舉和現(xiàn)實社會中的民主選舉制度很像，剛開始沒有 Leader，所有集群中的參與者都是 Follower, 當(dāng) Follower 超過選舉超時時間 ( election timeout ) 沒收到來自 Leader 的心跳報文，則成為 Candidate，增加任期 ( Term ) 并向其他節(jié)點(diǎn)發(fā)起新的選舉請求。接收到請求的節(jié)點(diǎn)如果還沒投票，則投票給該節(jié)點(diǎn)，并重置自己的超時時間。如果某個 Candidate 節(jié)點(diǎn)接收到的選票的個數(shù)占大多數(shù)（超過 1/2）， 它就會成為 Leader 節(jié)點(diǎn)，這就是所謂的 Leader election 的過程。每隔一定時間向 Follower 發(fā)送心跳報文來維持自己的 『統(tǒng)治』地位。

集群中的每個節(jié)點(diǎn)都處于以上三種角色中的一種，其狀態(tài)轉(zhuǎn)換圖可以總結(jié)如下：

下面通過幾個例子來幫助我們理解這個選舉過程：

1. 可以正常選舉出 Leader 的例子 ：

在此例子中，一共有三個節(jié)點(diǎn)，復(fù)現(xiàn)流程如下：

• 節(jié)點(diǎn) B 首先出現(xiàn)心跳超時，然后變成 Candidate 角色。
• 節(jié)點(diǎn) B 首先把自己寶貴的一票投給自己，然后請求其他節(jié)點(diǎn)也將贊同票投給自己。
• 節(jié)點(diǎn) A 和 C 此時還未出現(xiàn)超時，仍然處于 Follower 角色，接收到請求后，投票給了 節(jié)點(diǎn) B。
• 節(jié)點(diǎn) B 接收到的贊同票超過半數(shù)，成為 Leader 節(jié)點(diǎn)。

2. 平分選票的情況

由于 Raft 協(xié)議并不要求集群中的節(jié)點(diǎn)個數(shù)為奇數(shù)，于是在四個節(jié)點(diǎn)的集群中，可能出現(xiàn)如下的情況：

復(fù)現(xiàn)流程如下：

• 節(jié)點(diǎn) B 和 C 幾乎同時心跳超時，成為 Candidate 角色。
• 節(jié)點(diǎn) B 和 C 均將自己的贊同票投給自己。
• 節(jié)點(diǎn) A 投給了節(jié)點(diǎn) B，而 節(jié)點(diǎn) D 則投給了節(jié)點(diǎn) C。
• 出現(xiàn)兩個 Candidate 的選票相同的情況。

當(dāng)出現(xiàn)這種情況的時候，沒有任何一個節(jié)點(diǎn)接收到的贊同票超過半數(shù)，于是此選舉過程不會有 Leader 角色出現(xiàn)。大家各自等待超時，然后開啟下一輪的選舉流程。

疑問：那有沒有可能在下一輪的選舉過程依然出現(xiàn)平分選票的情況？答案是有的，可是 Raft 有一個機(jī)制可以避免此種情況持續(xù)發(fā)生： 每個節(jié)點(diǎn)的超時時間都是隨機(jī)的 ，這樣就可以盡量避免多次出現(xiàn)以上的情況。

3. 選舉流程要點(diǎn)總結(jié)

「1」Leader 角色通過發(fā)送心跳報文來維護(hù)自己的統(tǒng)治地位。「2」Follower 角色接收不到心跳報文，則超時開始下一輪的選舉?！?」每個節(jié)點(diǎn)的超時時間都是隨機(jī)的?！?」成為 Leader 節(jié)點(diǎn)需要贊同票超過半數(shù)?！?」選舉結(jié)束，所有除 Leader 的候選人又變回 Follower 服從 Leader。

日志同步

當(dāng)選舉完成后，客戶端進(jìn)行的操作都要通過 Leader 來進(jìn)行。Leader 接受到客戶端發(fā)來的操作請求后，首先記錄到日志中，此時為 uncommitted 狀態(tài)。然后在下一個心跳報文中通知所有 Follower，當(dāng)大多數(shù) Follower 響應(yīng) ACK 后，Leader 響應(yīng)客戶端，進(jìn)入 committed 階段，并向 Follower 發(fā)送 commit 通知應(yīng)用( Apply )操作。

日志同步流程如下：

上圖中的序號對應(yīng)一個存儲的步驟， 日志同步 流程總結(jié)如下：「1」client 給 Leader 發(fā)送一個操作請求，假設(shè)為 SET X=8?！?」Leader 會把 SET X=8 這個操作記錄到本地 log，此時為 uncommited 狀態(tài)，同時將這個操作發(fā)送給所有的 Follower?！?」Follower 接收到操作請求后，也將 SET X=8 這個操作記錄到本地 log（uncommited 狀態(tài)），然后給 Leader 回復(fù) ACK 信息。「4」Leader 節(jié)點(diǎn)當(dāng)接收到的 ACK 超過半數(shù)后，給 client 回復(fù) ACK 信息，進(jìn)入 commited 階段。「5」Leader 節(jié)點(diǎn)首先應(yīng)用自己的 log，然后將 commit 消息發(fā)送給 Follower, 讓 Follower 也 應(yīng)用自己存儲的日志信息。

Raft 中的異常處理

我們已經(jīng)介紹了 Raft 算法的正常處理流程，然而現(xiàn)實總是很骨感，會出現(xiàn)各種異常的情況。client 和 Leader 之間的通信異常，不會影響到集群內(nèi)部狀態(tài)的一致性，不再贅述；如果在一個任期內(nèi)，F(xiàn)ollower 角色宕機(jī)，處理流程比較簡單。其呈現(xiàn)出來的現(xiàn)象就是 步驟「3」異常，然而只要 Leader 能夠接收到超過半數(shù)的 ACK，就不會影響到正常的存儲流程。但是 Leader 角色會針對該 Follower 節(jié)點(diǎn)，持續(xù)進(jìn)行步驟 「2」 的動作，直到接收到步驟 「3」的回應(yīng)信息或者我們把該 Follower 節(jié)點(diǎn)從集群中拿掉；Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)的可用性來確保集群數(shù)據(jù)的一致性。下面重點(diǎn)介紹在各種情況下 Leader 節(jié)點(diǎn)出現(xiàn)故障時，Raft 協(xié)議是如何保障數(shù)據(jù)一致性的。

1. 寫操作 到達(dá) Leader 節(jié)點(diǎn)，但尚未同步到 Follower 節(jié)點(diǎn)

此刻集群的狀態(tài)如下，用方框中的灰色表示當(dāng)前處于 uncommited 狀態(tài)。

如果集群在此狀態(tài)，Leader 節(jié)點(diǎn)宕機(jī)，則 Raft 的處理流程如下：「1」Follower 節(jié)點(diǎn)超時，然后選舉出新一任期的 Leader，然后它并沒有處于 uncommited 狀態(tài)的日志?！?」Client 節(jié)點(diǎn)由于 Ack 超時，可安全發(fā)起重試。「3」原來的 Leader 節(jié)點(diǎn)恢復(fù)后以 Follower 角色重新加入集群。并從當(dāng)前任期的新 Leader 處同步數(shù)據(jù)，可能會覆蓋原來處于 uncommited 狀態(tài)的日志。

2. 寫操作 到達(dá) Leader 節(jié)點(diǎn)，且將寫操作同步到 Follower 節(jié)點(diǎn)，但還未向 Leader 回復(fù) ACK 信息。

此刻集群的狀態(tài)如下，用方框中的灰色表示當(dāng)前處于 uncommited 狀態(tài)。

如果集群在此狀態(tài)，Leader 節(jié)點(diǎn)宕機(jī)，則 Raft 的處理流程如下：「1」Follower 節(jié)點(diǎn)超時，然后選舉出新一任期的 Leader，并且它存在處于 uncommited 狀態(tài)的日志?！?」新的 Leader 節(jié)點(diǎn)假裝沒有剛才的選舉過程，繼續(xù)從步驟（2）開始執(zhí)行，以完成數(shù)據(jù)的提交?！?」Client 節(jié)點(diǎn)由于 ACK 超時，可安全發(fā)起重試。「4」原來的 Leader 節(jié)點(diǎn)恢復(fù)后以 Follower 角色重新加入集群。并從當(dāng)前任期的新 Leader 處同步數(shù)據(jù)。

此時，在上面步驟「1」中選舉新的 Leader 節(jié)點(diǎn)時，需要滿足一個限制條件，即新的 Leader 節(jié)點(diǎn)需要具有最新的日志信息，所謂的最新是通過任期和日志的偏移量兩個參數(shù)來判定的，這個限制是為了解決只有部分 Follower 節(jié)點(diǎn)接收到寫操作請求的情況。

3. Leader 節(jié)點(diǎn)接收到寫操作的 ACK 信息，處于 commited 狀態(tài)，然而 Follower 處于 uncommited 狀態(tài)。

此種情況是由于，在步驟（5）執(zhí)行過程中，Leader 宕機(jī)導(dǎo)致的，此刻集群的狀態(tài)如下，用方框中的灰色表示當(dāng)前處于 uncommited 狀態(tài)，用方框中的黑色表示當(dāng)前處于 commited 狀態(tài)，同時圓圈中的值表示操作已經(jīng)生效。

對于此種情況，Raft 協(xié)議的處理流程和上面情況2的處理流程是一樣的。

4. 腦裂

由于網(wǎng)絡(luò)故障，產(chǎn)生分區(qū)將原先的 Leader 節(jié)點(diǎn)和 Follower 節(jié)點(diǎn)分隔開，F(xiàn)ollower 收不到 Leader 的心跳將發(fā)起選舉，產(chǎn)生新的 Leader，這時就產(chǎn)生了雙 Leader，這就是所謂的腦裂。這種情況下某些 Leader 由于獲取不到大多數(shù)的投票，所以數(shù)據(jù)永遠(yuǎn)不會提交成功。當(dāng)網(wǎng)絡(luò)故障恢復(fù)后，舊的 Leader 發(fā)現(xiàn)有 Term 更新的 Leader 存在，則自動降級為 Follower 并從最新的 Leader 同步數(shù)據(jù)達(dá)成集群一致。

總結(jié)

本文以 Raft 協(xié)議為契機(jī)來介紹分布式環(huán)境中的一致性。首先介紹了 Leader 選舉和日志同步的過程，然后介紹了 Raft 協(xié)議是如何處理各種異常情況的。通過 Raft 協(xié)議的學(xué)習(xí)，不僅可以對分布式一致性有一個概括性的了解，同時也會有助于對其他一致性協(xié)議（比如 paxox）的學(xué)習(xí)。在此基礎(chǔ)上，可以嘗試閱讀一些 Raft 開源的實現(xiàn), 以加深進(jìn)一步的理解。