Raft算法
raft是一個分布式共識算法厘贼。
raft算法實現(xiàn)
raft將系統(tǒng)角色分為領(lǐng)導(dǎo)者(Leader)界酒，跟隨者(Follower)，和候選人(Candidate)
領(lǐng)導(dǎo)者(Leader)：接收客戶端請求嘴秸，并向跟隨者(Follower)同步日志請求,當(dāng)日志同步到大多數(shù)節(jié)點上告訴Follower提交日志
跟隨者(Follower)：接收并持久化Leader同步的日志毁欣，在Leader告知日志可以提交之后，提交日志
候選人(Candidate)：Leader選舉過程中的臨時角色
Raft要求系統(tǒng)在任意時刻最多只有一個Leader赁遗，正常工作期間只有Leader和Followers
選舉過程
follower(跟隨者)超時沒有收到Leader(領(lǐng)導(dǎo)者)的信息,他會成為一個Candidate（候選者）并且開始Leader選舉署辉，收到大多數(shù)服務(wù)器的投票的Candidate會成為新的Leader。Leader在宕機(jī)之前會一直保持Leader的狀態(tài)岩四。
raft算法將時間分為一個個任期(term),每一個term的開始都是Leader選舉哭尝，在成功選舉Leader之后，Leader會在整個term內(nèi)管理整個集群剖煌，如果Leader選舉失敗材鹦，該term就會因為沒有Leader而結(jié)束。
leader選舉
Raft使用心跳（heartbeat）觸發(fā)領(lǐng)導(dǎo)者（Leader)選舉耕姊，當(dāng)服務(wù)器啟動時桶唐，初始化為跟隨者（Follower）。Leader向所有的Followers周期性的發(fā)送heartbeat茉兰，如果Follower尤泽，在選舉超時的時間內(nèi)沒有收到Leader的hearbeat，就會等待一段隨機(jī)時間后發(fā)起一次Leader選舉规脸。
Follower將當(dāng)前的term加一然后轉(zhuǎn)換成候選者（Candidate）坯约，他首先給自己投票并且給集群中的其他服務(wù)發(fā)送投票請求（RequestVote RPC）會有以下三種結(jié)果：
贏得了多數(shù)選票，成功選舉Leader
收到了Leader的消息莫鸭，表示其他服務(wù)器已經(jīng)搶先當(dāng)選了Leader
沒有服務(wù)器贏得多數(shù)選票闹丐，Leader選舉失敗，等待選舉時間超時后發(fā)起下一次選舉
選舉出Leader后被因，Leader通過定期向所有Follower發(fā)送心跳位置其統(tǒng)治卿拴，若Follower一段時間為收到Leader收到Leader心跳則認(rèn)為Leader可能已經(jīng)掛了衫仑，再次發(fā)起Leader選舉過程
日志同步
領(lǐng)導(dǎo)者(Leader)選出來，就開始接收客戶請求堕花，Leader把請求作為日志條目(Log entries)加入到他的日志匯總文狱，然后并行的向其他服務(wù)器發(fā)起添加條目（ApendEnteries）RPC復(fù)制日志條目，當(dāng)這條日志被復(fù)制到大多數(shù)服務(wù)器上航徙，Leader將這條日志應(yīng)用到狀態(tài)機(jī)并向客戶端返回執(zhí)行結(jié)果如贷。
某些跟隨者（Followers）可能沒有成功復(fù)制日志，Leader會無限重試添加條目（AppendEntries） RPC直到所有的Followers最終存儲了所有的日志條目到踏。
日志由有序編號(log index)的日志條目組成。每個日志條目包含它被創(chuàng)建時的任期號（term）和用于狀態(tài)機(jī)執(zhí)行的命令尚猿。如果一條日志被復(fù)制到大多數(shù)服務(wù)器上就認(rèn)為可以提交（commit）了
Raft日志同步保證一下倆點：
如果不同日志的倆條條目有著相同的索引(log index)和任期號(term)窝稿，則他們所有存儲的命令都是相同的
如果不同的日志倆條條目有著相同的索引(log index)和任期號(term),則他們的所有條目都是完全一樣的
第一條特性源于Leader在一個term內(nèi)在給定的一個log index最多創(chuàng)建一條日志條目，同時該條目在日志中的位置也從來不會改變凿掂。
第二條特性源于 AppendEntries 的一個簡單的一致性檢查伴榔。當(dāng)發(fā)送一個 AppendEntries RPC 時，Leader會把新日志條目緊接著之前的條目的log index和term都包含在里面庄萎。如果Follower沒有在它的日志中找到log index和term都相同的日志踪少，它就會拒絕新的日志條目。
一般情況下糠涛，Leader和Followers的日志保持一致援奢，因此 AppendEntries 一致性檢查通常不會失敗。然而忍捡，Leader崩潰可能會導(dǎo)致日志不一致：舊的Leader可能沒有完全復(fù)制完日志中的所有條目集漾。
一個Follower可能會丟失掉Leader上的一些條目，也有可能包含一些Leader沒有的條目砸脊，也有可能兩者都會發(fā)生具篇。丟失的或者多出來的條目可能會持續(xù)多個任期。
Leader通過強(qiáng)制Followers復(fù)制它的日志來處理日志的不一致凌埂，F(xiàn)ollowers上的不一致的日志會被Leader的日志覆蓋驱显。
Leader為了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方瞳抓，然后覆蓋Followers在該位置之后的條目埃疫。
Leader會從后往前試，每次AppendEntries失敗后嘗試前一個日志條目挨下，直到成功找到每個Follower的日志一致位點熔恢，然后向后逐條覆蓋Followers在該位置之后的條目。
安全性
Raft增加了倆條限制條件保證安全性：
-
擁有最新已提交日志索引的Follower才有資格成為Leader
在投票的時候候選者（Cadidate）在發(fā)送RequestVote Rpc時候要帶上自己的最后一條日志的term和log index 臭笆，其他節(jié)點收到消息時叙淌，如果發(fā)現(xiàn)自己的日志比請求中攜帶的更新秤掌，則拒絕投票。比較原則: 本地的最后一條日志條目(log entry)的任期(term)更大鹰霍，則term大的更新闻鉴，如果term一樣大，則log index大的更新
-
Leader只能推進(jìn)提交索引(commit index) 來提交當(dāng)前任期（now term）的已經(jīng)復(fù)制到大多數(shù)服務(wù)器上的日志茂洒，舊的任期（old term）日志的提交要等到提交當(dāng)前任期(now term)的日志來間接提交（日志索引(log index)小于提交日志(commit index）的日志被間接提交）孟岛。
舊的任期日志需要等到當(dāng)前任期提交，之前的日志索引小雨提交日志的索引被當(dāng)前日志提交
之所以要這樣督勺，是因為可能會出現(xiàn)已提交的日志又被覆蓋的情況：
成員變更
成員變更是在集群運行過程中副本發(fā)生變化渠羞，增加/減少副本，節(jié)點替換等
成員變更也是一個分布式一致性問題智哀，因為成員變更提交日志的變更時刻可能不同次询。可能導(dǎo)致舊的成員配置和新的成員配置有差異瓷叫，可能導(dǎo)致出現(xiàn)舊的和新的成員配置同時選舉出新的Leader形成不同的決策屯吊，從而破壞安全性。
Raft提出了倆階段成員變更方法：
集群先從舊成員配置切換到一個過渡成員配置摹菠，稱為共同一致盒卸，共同一致是舊成員配置和新成員配置的組合，一旦共同一致新舊組合被提交次氨，系統(tǒng)再切換到新成員配置
