2.CAP原則
CAP原則又稱CAP定理，指的是在一個分布式系統(tǒng)中，一致性（Consistency）、可用性（Availability）、分區(qū)容錯性（Partition tolerance）
It states, that though its desirable to have Consistency, High-Availability and Partition-tolerance in every system, unfortunately no system can achieve all three at the same time.
在分布式系統(tǒng)的設計中，沒有一種設計可以同時滿足一致性，可用性，分區(qū)容錯性 3個特性
1998年，加州大學的計算機科學家 Eric Brewer 提出，分布式系統(tǒng)有三個指標。
- 一致性（C）：在分布式系統(tǒng)中的所有數(shù)據(jù)備份，在同一時刻是否同樣的值，即寫操作之后的讀操作，必須返回該值。（分為弱一致性、強一致性和最終一致性）
- 可用性（A）：在集群中一部分節(jié)點故障后，集群整體是否還能響應客戶端的讀寫請求。（對數(shù)據(jù)更新具備高可用性）
- 分區(qū)容忍性（P）：以實際效果而言，分區(qū)相當于對通信的時限要求。系統(tǒng)如果不能在時限內(nèi)達成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當前操作在C和A之間做出選擇
要滿足CAP理論，而分布式共識算法解決的就是CAP理論中的一致性問題。整個一致性問題分為三種問題：
- 順序一致性
- 線性一致性
- 因果一致性
其中線性一致性要求所有線程的操作按照一個絕對的時鐘順序執(zhí)行，這意味著線性一致性是限制并發(fā)的，否則這種順序性就無法保證。由于在真實環(huán)境中很難保證絕對時鐘同步，因此線性一致性是一種理論。
實現(xiàn)線性一致性的代價也最高，但是實戰(zhàn)中可以弱化部分線性一致性：只保證有因果關系的事件的順序，沒有因果關系的事件可以并發(fā)執(zhí)行，其指的是假設有兩個事件：A事件和B事件，如果A發(fā)生在B后面，那么就稱A和B具有因果關系。
Paxos和Raft這些分布式共識算法就是用來多個節(jié)點之間達成共識的，其可以解決一定的一致性問題。其中raft對于分布式的入門者來說最好理解，因此，我們選擇raft作為我們的講解目標。
2. 共識算法RAFT
2.1 數(shù)據(jù)處理流程
在深入了解raft的實現(xiàn)之前，我們需要先對擁有raft的分布式集群有一個宏觀了解。
當我們向集群中的每一臺主機中加入一致性協(xié)議之后，我們數(shù)據(jù)的存儲會發(fā)生什么變化？
根據(jù)上圖我們可以大致推斷：
- 客戶端發(fā)出命令，被集群中的一臺機器接收，不直接提交到狀態(tài)機(State Machine)進行持久化，而是先提交到 共識協(xié)議層(Consensus Moudle)
- 共識協(xié)議層(Consensus Moudle)將客戶端命令持久化到本地日志中，同時分發(fā)到其他機器上
- 當其他機器會收到含有命令的日志，并持久化，最后從日志中取出命令，應用到狀態(tài)機
2.2 RAFT 詳解
2.2.1 RAFT 狀態(tài)機
遵循Raft算法的分布式集群中每個節(jié)點扮演以下三種角色之一：
leader：領導者，其負責和客戶端通信，接收來自客戶端的命令并將其轉(zhuǎn)發(fā)給follower
follower：跟隨者，其一絲不茍的執(zhí)行來自leader的命令
candidate：候選者，當follower長時間沒收到 leader的消息就會揭竿而起成為候選者，搶奪成為leader的資格
2.2.2 節(jié)點數(shù)據(jù)結(jié)構定義
其中各個字段分為需要持久化的與不需要持久化的（易失的）：
持久化狀態(tài)
| 參數(shù) | 解釋 |
|---|---|
| currentTerm | 服務器最新任期，可理解為邏輯時鐘 |
| voteFor | 當前term內(nèi)自己給候選人投票的候選人Id,未投票則為-1 |
| log[] | 日志條目，單條日志包括 客戶端操作，leader接收到該條目時的term,以及日志索引(初始為1,如圖) |
currentTerm 參數(shù)raft集群內(nèi)的邏輯時鐘值，全局遞增，準確來說時Lamport Timestamp的變體。
Lamport Timestamp算法
該算法十分簡單，當一個集群內(nèi)的多臺機器需要維護一個全局時間，可以這樣做：
- 每個進程本地存儲一份全局時間副本
- 某進程內(nèi)時間發(fā)送，遞增自身時間副本
- 發(fā)送消息時附加上時間副本值
- 收到消息，比較消息中與自己的時間副本值，選擇較大的時間值加1，并更新自身時間
易失性狀態(tài)
| 參數(shù) | 解釋 | 初始值 |
|---|---|---|
| commitIndex | 已知提交的最高的日志條目的索引 | 0 |
| lastApplied | 已知被應用到狀態(tài)機的最高的日志條目的索引 | 0 |
除此之外，Leader還維護了兩個數(shù)組：
Leader易失性狀態(tài)
| 參數(shù) | 解釋 | 初始值 |
|---|---|---|
| nextIdx [] | 對于i號節(jié)點，發(fā)送到該節(jié)點的下一跳日志的索引 | Leader最后日志條目索引+1 |
| matchIdx[] | 對于i號節(jié)點，已知的已經(jīng)復制到該節(jié)點的最高日志條目的索引 | 0,單調(diào)遞增 |
2.2.3 節(jié)點 RPC 操作
2.2.3.1 請求投票(RequestVote)
候選人發(fā)起選舉投票RPC到集群內(nèi)的其他節(jié)點
- 請求參數(shù) (RequestVoteArgs)
| 參數(shù) | 解釋 |
|---|---|
| term | 候選人任期號 |
| candidateId | 候選人Id |
| lastLogIndex | 候選人最后的日志條目的索引 |
| lastLogTerm | 候選人最后日志條目的term |
- 響應參數(shù) (RequestVoteReply)
| 參數(shù) | 解釋 |
|---|---|
| term | 當前任期號，幫助候選者更新自身任期號 |
| voteGranded | 候選人是否贏得此張選票 |
-
選舉邏輯
- 節(jié)點為Canaditate
選舉準備操作
- 自增當前的term,
- 給自己投一票
- 重置選舉超時計時器
發(fā)送RPC投票請求到其他server
選舉中操作
- 接收到超過半數(shù)節(jié)點的選票，變?yōu)長eader
- 接收到到來自Leader的日志追加RPC,變回Follower
- 選舉超時前未發(fā)生2或3，再次發(fā)起選舉
- 節(jié)點為 Follower
狀態(tài)變更準則：
如果在自身選舉超時時間超時前未收到Leader的心跳或者日志追加，也沒有給某個Candiate投票，那么自己變成候選人
投票準則：
- 如果候選人term小于currentTerm ,拒絕投票，并且返回currentTerm讓候選人更新
- 如果voteFor為-1或者恰好等于Candidate,則將候選人的最后一條日志與自己的最后一條日志term進行對比，大于自己則投票，小于自己則拒絕，相等則比較索引
練習: 根據(jù)教程結(jié)合RAFT論文，實現(xiàn)raft的選舉機制
2.2.3.2 心跳通知與日志追加(AppendEntires)
請求參數(shù)(AppendEntriesArgs)
| 參數(shù) | 解釋 |
|---|---|
| term | Leader任期號 |
| leaderId | LeaderId |
| prevLogIndex | 新日志之前的那條日志索引 |
| prevLogTerm | 新日志之前的那條日志任期 |
| entries | 需要被追加與保存的日志條目列表(做心跳時日志條目為空) |
| leaderCommit | Leader已知的已經(jīng)提交的最高的日志條目索引 |
響應參數(shù)(AppendEntriesReply)
| 參數(shù) | 解釋 |
|---|---|
| term | 當前任期 |
| success | 結(jié)果為真，則說明follower的所有日志與prevLogIndex，preLogTerm匹配 |
- 具體邏輯
前置邏輯
- 如果接收到的RPC請求或請求中，term >currentTerm,那么更新currentTerm = term,并變更狀態(tài)為follower. 這一點體現(xiàn)了term的邏輯時鐘的作用
- 如果commitIndex > LastApplied,那么LastApplied++,將索引為LastApplied的日志應用到狀態(tài)機
節(jié)點為Leader
- 選舉成功成為領導人之后，立即發(fā)送心跳(空日志)到其他節(jié)點，按照一定時間間隔不斷發(fā)送，避免其他節(jié)點超時觸發(fā)選舉
- 接收到client的請求，先附加日志條目到本地日志中，在條目被引用到狀態(tài)機后響應client
- 對于一個follower,如果最后一條日志的索引大于等于nextIndex,則發(fā)送從nextIndex開始的所有日志條目
追加成功: 更新nextIndex和matchIndex中follower對于的值
追加失敗: 發(fā)送日志沖突，Leader減少nextIndex進行重發(fā)嘗試
當半數(shù)節(jié)點已經(jīng)收到某條日志，即存在一個數(shù)N 滿足N>commitIndex,且大多數(shù)的matchIndex[i]>=N成立，且log[N].term == currentTerm成立，那么更新commitindex為N文章來源：http://www.zghlxwxcb.cn/news/detail-458578.html
節(jié)點為follower文章來源地址http://www.zghlxwxcb.cn/news/detail-458578.html
- 如果Leader的term小于 自身的term ,返回false
- 在接收者的日志中，如果能夠找到一個日志條目的prevLogIndex以及prevLogTerm與請求中的相同，那么繼續(xù)執(zhí)行，否則返回false
- 如果一個已經(jīng)存在的條目和待追加日志條目發(fā)送沖突，即index相同，term不相同，那么刪除該已經(jīng)存在的日志以及其之后的所有日志，保證Leader的絕對權威
- 追加日志中不存在的所有新日志
如果leadcommit > commitIndex,即領導者的已知提交到最高日志索引大于接收者的已知的最高的日志索引,則把commitIndex重置為 min(leadercommit,最新日志的索引)
2.2.3 RAFT優(yōu)化
2.2.3.1 日志快照
到了這里，關于【分布式】分布式共識算法 --- RAFT的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
