raft算法mysql主从复制_Etcd raft算法实现原理分析
1.1 主要概念
要實現集群數據的一致性，節點在進行通信的時候必定需要遵守特定規則進行數據校驗，而這些規則具體都是通過某些具有特定含義的屬性來實現的。為了讓對Raft 算法比較陌生的讀者對算法的關鍵概念有一個初步認識，作者整理了算法中涉及的概念如下所示：
1.2 節點狀態
Raft 算法比較簡單，其中一個原因是節點的狀態少，一共只有三種角色，大大降低了角色間轉換的復雜性。這三種角色分別是Leader 、Follower 和Candidate (其實大部分時間只有Leader 和Follower 角色，因為Candidate 只是選舉的一個過渡角色)，每種角色都有自己的運行規則。角色之間可以在一定條件下進行角色轉換，狀態轉換如下圖所示：
l Follower：集群啟動時，每個Raft 節點初始以Follower的角色運行。他們各自維護了一個超時字段(ElectionTick屬性)，如果在超時時間段內Follower都沒有收到來自Leader的消息，Follower就知道這個時候集群中沒有Leader節點，這時它會把自己的角色轉換為Candidate，并發起領導人選舉。
l Candidate：處于Candidate狀態的節點會發起選舉的操作的操作，如果選舉成功，那它將成為下一任的領導人，如果選舉失敗，就轉化為Follower節點，負責處理Leader節點發起的請求，比如添加日志，心跳檢測等操作。在選舉過程中可能會有多個節點競爭領導人角色，并且多個選舉人獲得同樣多的選票。這時候大家都不能當選Leader，經過一定時間，Follower會重新發起一輪選舉，保證一次選舉最多只有一個領導人。這里面有一些優化機制，比如每個候選人重新發起選舉的間隔時間是不一樣的，可以降低多次選票相同，重新選舉的問題。
l Leader：Leader節點主要負責集群中數據的管理，包括給Follower發送添加日志、心跳檢測(HeartbeatTick 屬性)等命令。在Raft 節點運行過程中可能會有這種情況，即當前Leader節點宕機了，這時其他節點會重新選出一個Leader并且運行了一段時間，宕機的Leader節點恢復了，新的Leader會給老的Leader發送消息，這時老的Leader發現消息里面的任期(Term字段)比自己當前的Term更大，老的Leader就知道自己已經不是最新的領導人了，它會主動轉換為Follewer角色。
1.3領導人選舉
根據1.2 的介紹我們知道，Raft 節點在一啟動的時候，就初始化為Follower 角色，并且每個Follower 角色都有一個ElectionTick 的隨機超時屬性。在超時的時間內如果Leader 對它們發起請求或者心跳檢測，Follower 節點會使自己轉變為Candidate 進行領導人選舉。在領導人選舉過程中，每個節點最多只能給一個節點投票，如果有兩個節點發起投票，先到的那個節點會獲得選票。這樣能夠保證每次選舉期間最多只有一個節點當選。論文中節點發起選舉參數和接收者實現規則如下圖所示：
1. Follower首先給自己發送一個消息，使自己變為Candidate角色，設置Term+1 然后并發的對集群的所有節點發送選舉的消息。集群中每個節點保存了一個數組，這個數組保存集群中所有節點的信息
2. 收到消息的Follower節點會對選舉的請求做出參數校驗和選舉響應，如果Candidate發送的消息里面的Term比自己當前記錄的更大，并且Candidate擁有自己已經更新的最新日志信息，就同意為Candidate投票，否則拒絕投票。
3. 如果Candidate收到大多數節點的投票響應，那Candidate就會成為新一任的Leader。給其他發送消息，并更
4. 如果Candidate沒有當選Leader，就使自己轉變為Follower角色，聽從Leader的指令。
步驟1 描述的操作可能會出現一個問題；假如集群出現網絡錯誤，使得集群中的節點(A 、B 、C 、D 、E 五個節點)被分成兩部分，節點A 、B 、C 和節點D 、E 。這時D 、E 沒收到Leader 節點的消息會重新發起選取，但是由于不能獲得多數節點的選票，因此Term 會不斷增大。如圖3 所示，當網絡回復的時候，D 、E 節點的Term 已經比正常集群的Term 更大，因此節點D 或節點E 將當選Leader ，導致節點A 、B 、C 在節點D 、E 宕機時期添加的正常數據被清除，從而破壞集群的歷史數據。
這個問題在數據一致性的應用場景是不允許出現的，Raft 算法采用PreVote 算法解決了這個問題。PreVote 算法在Candidate 發起選舉之前，會首先向其他節點發送一個預投票信息，這時Term 沒有加1 ，如果超過半數節點同意了選舉請求，Candidate 才設置Term+1 ，真正發起領導人選舉投票。在上述環境中D 、E 節點是沒辦法獲得超過半數節點的選票，因此節點只能反復Prevote ，Term 卻沒有機會增加。當網絡恢復的時候當收到Node A 的消息，立刻使自己變成Follower 繼續為集群服務。
1.4日志復制
Raft 集群中Leader 節點負責與客戶端的交互，當非Follower 節點接收到客戶端請求的時候，該節點會把該請求重定向到leader 節點，這種集中式的處理方式大大降低了集群和客戶端的交互復雜度。用戶的每次請求操作在Raft 集群中最終都是一個日志復制的過程，我們來看看一次簡單日志復制過程：
1. 客戶端給Leader節點發送一個 SET X = 5 的請求。
2. Leader節點收到客戶端請求，首先把SET X = 5的指令寫到日志中，然后把請求并發發送到所有Follower節點。
3. Follower節點收到Leader請求，也把SET X = 5 寫到日志中，然后響應Leader 節點。
4. 當Leader節點收到大部分Follower節點寫入成功后，把 SET X = 5 這個指令 commit 這個時候，Leader 節點上的X 才真正等于5，并發送commit 成功給所有Follower節點。
5. Follower節點收到Leader節點commit成功的信息，也commit，這個時候就實現了Raft集群數據的一致性。
在日志復制過程中，節點會對相應參數進行檢測，避免無效信息被加入到日志中造成集群中數據不一致。論文中日志發送參數和節點校驗規則如圖5 所示：
添加日志消息的參數及其含義解釋如下：
1. Term: 發送者的任期號。
2. LeaderId: 領導人的id。
3. PrevLogIndex: 之前Leader發送給Follower的最后一條日志索引，用于 Follower 確認與 Leader 的日志是否完全一致。新添加的日志會在這個索引之后開始。
4. PrevLogTerm: prevLogIndex索引對應的任期，用于檢測Term的合法性。
5. Entries[]: 發送的日志數組，一次可以發送多條日志以提高效率。
6. LeaderCommit: Leader節點已經提交的最大日志索引，當節點收到這個記錄的時候就知道，自提交日志到這個索引值是安全的。
消息接收者的數據校驗規則：
1. 節點接收到消息時，如果發現消息來源的Term 小于自己當前記錄的currentTerm，直接忽略這個消息。
2. 節點會根據prevLogIndex找到自己對應log的任期號term，如果和term和prevLogTerm不匹配，則直接返回false，不處理這個消息。
3. 檢測entries數組是否和自己已經保存的log有沖突，如果有沖突，則刪除這個沖突索引之后的所有日志。
4. 把所有新的日志entries加到自己的日志中。
5. 如果leaderCommit > commitIndex(自己已提交的最大索引)，則設置 commitIndex = min( leaderCommit, entries)數組的最后一個元素的索引。
◆◆
2. Etcd raft 源碼分析
◆◆
研究了Raft 的算法設計思想，接下來我們看Etcd 是怎么實現Raft 算法的。研究的Etcd 源碼為V3.1.20 版本，下載地址https://github.com/etcd-io/etcd 。為了使讀者對raft 算法代碼結構有一個大致認識，我根據raft 啟動過程畫出以下代碼調用圖。建議要看源碼的讀者可以對著以下流程自己進入代碼走一遍，對etcd 的raft 源碼結構有一個大致印象，不然后面的代碼可能會看的不知所云。
Etcd 的啟動方法在etcdmain/main.go 文件中，應用啟動后，raft 相關會啟動兩個協程，一個運行內層函數(raftnode.go 文件的node.run 方法) ，另一個運行外層函數(etcdserver/raft.go 文件中的start 方法)。內層函數主要處理節點數據內部的變更，外層函數主要負責獲取內層函數的變更信息與其他節點的通信。內層函數和外層函數都有node 這個結構體的引用，因此兩個協程之間可以通過node 里面的Channel 進行通信。
在Etcd 的raft 實現中，所有消息都被封裝到一個結構體中，參數根據消息類型進行組裝，因此很多參數都是可選的。一開始覺得所有消息的屬性都集成在一個結構體不太好，后來看代碼過程中發現這個結構體中屬性并不多，而且大部分屬性在大部分消息中都是要用到的。只是冗余少數字段但是大大減少了消息結構體的數量，使得消息參數整體看起來更簡單。消息類型和屬性如下圖所示：
介紹了消息類型，接下來我們來看看raft 算法中領導人選舉的具體源碼實現。領導人選舉的大致步驟為
1. Candidate: 內層函數raft.run把消息添加到raft.msgs的slice結構中。
2. Candidate: 內層函數監聽到raft.msgs有新消息寫入，把raft.msgs的消息封裝成一個Ready結構體，然后把這個結構體放入 node.readyc這個channel。
3. Candidate: 外層函數raftNode.start 監聽到node.readyc這個channel中有數據到達，拿到這個消息，根據消息的目標節點把消息發送出去。
4. Follower: Follower收到Candidate的領導人選舉請求，對請求做出響應。
5. Candidate：統計選舉的回復，如果超過半數節點同意則當選Leader，否則轉為Follower。
源碼部分我將從go.etcd.io/etcd/etcdserver/raft.go 文件的StartNode(c *Config, peers []Peer) 函數開始分析，從這里開始主要是Raft 算法的核心實現。在StartNode 方法結尾啟動了一個協程用于運行內層函數。
在StartNode 方法中，節點啟動后初始化為Follower 角色，如果在選舉超時內沒有收到Leader 的消息，會發出一個選舉超時事件，這個事件在內層函數(raftnode.go 文件的node.run 方法) 中被捕獲，調用r.tick 函數，tick 實際上是一個函數變量，在becomeFollower 函數中被賦值為tickElection ，因此r.tick 方法實際上調用的是tickElection 方法進行領導人選舉。
tickElection 方法中會檢測相應參數，如果節點當前可選舉，并且已超時則會節點的狀態機函數(raftraft.go 文件Step 函數)傳入一個類型為pb.MsgHup 的選舉消息，這個消息不用于節點間通信，只是通知自己可以重新發起一輪領導人選舉。
進入Step 狀態機函數，pb.MsgHup 消息被捕獲到，還是先檢測相應參數，如果檢測到自己已經是Leader ，就忽略這個消息。否則根據是否是Prevote 階段進入相應投票階段，前面我們說到，Prevote 解決了raft 集群網絡分區造成的問題。
campaign 方法(raftraft.go 文件campaign 函數)中對消息做進一步處理，這里節點會排除自己對其他每個節點“發送“預選舉/ 選舉的消息，注意這里并沒有真正發送消息，而是把消息加到raft 結構體的msgs 切片中。Raft.msgs 結構體主要用于臨時存放待發送的消息。
當數據被寫到raft.msgs 切片時，內層函數(raftnode.go 文件的node.run 方法)監聽到raft.msgs 中有新數據待發送，會把數據封裝成一個Ready 結構體放入node.readyc channel 中，清空raft.msgs 消息，并賦值advancec 為node.advancec channel 。一開始沒看懂為什么這樣寫，后來在外層函數看到有一個往node.advancec 寫入空結構體的操作才明白。當源節點往readyc 寫入ready 數據后，就是一個異步操作，根本不知道目標節點什么時候能夠處理完這個消息。源節點和目標節點通過node.advancec channel 就可以傳遞消息已經處理完的信號，源節點收到這個信號就可以進行后續的操作。
由于外層函數(etcdserver/raft.go 文件中的start 方法)擁有node.readyc 的引用，并且監聽著這個管道，把readyc 到來的消息拿出來，根據消息結構體中的目標節點把消息發送出去，這個時候就是端到端節點消息的發送了。
Candidate 節點選舉的消息發出去后，目的節點會在狀態機函數(raftraft.go 文件Step 函數)中捕獲到這個消息，捕獲的消息類型為pb.MsgVote 和pb.MsgPreVote 。在這里對Term 和消息的index 進行了檢測。對Term 的檢測主要包括：1. 之前是不是已經給這個節點投過票，如果沒投過票可以繼續投，這表示是投票的PreVote 階段。2. 投票節點的Term 是否大于自己的Term, 只有大于才是合理的Term 值。3. 已經投過票，這次的投票請求者是否和自己投過票的節點一樣，這表示正式的投票階段，第二次投票的必須和第一次投票的一樣；對于Index 的檢測主要是發起投票節點日志的Term 必須比自己的大，或者Term 相同，但是日志索引更多，也就是說發起投票的節點至少要擁有和自己一樣或者更新的日志記錄。這部分檢測都通過后就回復同意投票的消息，否則回復否定投票的消息。
當所有節點都回復完Candidate 選舉的請求時。這時候再回到Candidate 節點，消息仍然會在狀態機函數(raftraft.go 文件Step 函數)被捕獲。因為消息類型既不是pb.MsgHup ，又不是pb.MsgVote ，沒有對應消息，所以代碼會走到switch case 的default 部分，調用r.step(r, m) 函數，step 是一個函數變量，因為當前節點是Candidate 角色，所以r.step 對應stepCandidate 函數。在這個函數里，Candidate 對選票進行統計，如果獲得超過半數的選票，就當選Leader ，否則變為Follower 。
到此，領導人選舉的源碼分析就大致完成了，日志添加過程，心跳檢測機制等其他操作其實是一樣的消息流轉機制，只不過消息類型不同，只要找到相應的消息類型，一步步分析下來還是比較簡單的。另外Etcd存儲部分和Raft算法緊密相關，并且Etcd V3版本相比與V2版本的存儲機制進行了較大的更新和優化，由于時間和篇幅的關系，這部分內容下次再分析。Etcd raft算法實現原理初步分析就到這里，個人理解有限，如果有不對的地方歡迎指出！
— END—
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的raft算法mysql主从复制_Etcd raft算法实现原理分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： IntelMEM.exe是什么进程 In
- 下一篇： internet.exe是什么病毒吗 i