領(lǐng)導(dǎo)者選舉
什么是領(lǐng)導(dǎo)者
Raft 首先選舉一個(gè)服務(wù)器作為領(lǐng)導(dǎo)者，然后讓這個(gè)領(lǐng)導(dǎo)者全面負(fù)責(zé)可復(fù)制日志的管理叫潦。領(lǐng)導(dǎo)者需要從客戶端接受日志條目善玫，將這些日志條目復(fù)制到別的服務(wù)器，告訴其它服務(wù)器什么時(shí)候可以安全地把日志條目輸入到他們的狀態(tài)機(jī)割卖。
為什么Raft算法需要一個(gè)領(lǐng)導(dǎo)者
有一個(gè)領(lǐng)導(dǎo)者能夠簡化可復(fù)制日志的管理。例如患雏，領(lǐng)導(dǎo)者能夠決定在哪個(gè)地方放置新的日志條目而不需要咨詢其他服務(wù)器的意見鹏溯，并且數(shù)據(jù)以一種簡單的形式從領(lǐng)導(dǎo)者流向其它服務(wù)器。
如何選舉一個(gè)領(lǐng)導(dǎo)者
觸發(fā)選舉
服務(wù)器啟動(dòng)時(shí)淹仑，初始狀態(tài)是跟隨者狀態(tài)丙挽。如果跟隨者一直接收領(lǐng)導(dǎo)者或候選人的消息，就會(huì)保持在跟隨者狀態(tài)匀借。在正常情況下颜阐，領(lǐng)導(dǎo)者會(huì)定時(shí)發(fā)送心跳消息給所有的跟隨者以維護(hù)他們的統(tǒng)治。如果一個(gè)跟隨者在一個(gè)叫做 election timeout 的時(shí)間內(nèi)都沒有接收到任何消息吓肋，它就認(rèn)為領(lǐng)導(dǎo)者已經(jīng)掛了凳怨，然后開始一場選舉，以選出一個(gè)新的領(lǐng)導(dǎo)者是鬼。為了開始一場選舉肤舞，
- 跟隨者會(huì)增加自己的任期，并轉(zhuǎn)換為候選人狀態(tài)
- 它會(huì)給集群中的其他服務(wù)器發(fā)送 RequestVote 消息均蜜，問他們是否愿意為自己投票
- 候選人處于候選狀態(tài)李剖，直到
- 自己成為領(lǐng)導(dǎo)者
- 別的服務(wù)器成為了領(lǐng)導(dǎo)者
- 沒有選出領(lǐng)導(dǎo)者
對于接收者來說，如果投贊同票囤耳，需要同時(shí)滿足一下兩個(gè)條件：
- 如果一個(gè)服務(wù)器的當(dāng)前任期大于候選人的任期篙顺，那么該服務(wù)器投反對票。
- 如果一個(gè)服務(wù)器的當(dāng)前任期小于候選人的任期紫皇，那么它更新自己的當(dāng)前任期為更大值慰安。如果當(dāng)前服務(wù)器是領(lǐng)導(dǎo)者或候選人狀態(tài)，恢復(fù)到跟隨者狀態(tài)聪铺。
- 如果一個(gè)服務(wù)器在當(dāng)前任期沒有給其他候選人投過票化焕，或者投過票給當(dāng)前候選人，并且候選人的日志至少要跟服務(wù)器自己的日志一樣新铃剔，那么該服務(wù)器投贊同票撒桨。
自己成為領(lǐng)導(dǎo)者
如果一個(gè)候選人接收到了同一個(gè)任期內(nèi)的大多數(shù)服務(wù)器的投票查刻，那么它就贏得了選舉。這個(gè)規(guī)則保證了：在一個(gè)特定的任期凤类，最多只有一個(gè)候選人能夠贏得選舉穗泵。在一個(gè)給定的任期，每臺(tái)服務(wù)器將會(huì)為最多一個(gè)候選人投票谜疤，即先到先服務(wù)原則佃延。這個(gè)原則有利于某個(gè)候選人得到大多數(shù)選票，減少選舉失敗的可能性夷磕。贏得選舉的候選人會(huì)成為領(lǐng)導(dǎo)者履肃，然后發(fā)送心跳消息給其他所有服務(wù)器，以建立自己的統(tǒng)治并阻止新的選舉坐桩。
別的服務(wù)器成為了領(lǐng)導(dǎo)者
在等待投票的時(shí)候尺棋，候選人可能接收到自認(rèn)為是領(lǐng)導(dǎo)者的服務(wù)器發(fā)來的 AppendEntries 消息，這時(shí)候
- 如果領(lǐng)導(dǎo)者的任期大于等于候選人的任期绵跷，那么候選人認(rèn)為這個(gè)領(lǐng)導(dǎo)者是合法的膘螟，然后回到跟隨者狀態(tài).
- 如果領(lǐng)導(dǎo)者的任期小于候選人的任期，那么候選人拒絕承認(rèn)并繼續(xù)處于候選狀態(tài)碾局。候選人會(huì)發(fā)送一個(gè)響應(yīng)荆残，響應(yīng)中返回反對意見和自己的任期。領(lǐng)導(dǎo)者收到后會(huì)將自己的任期更新為這個(gè)更大的任期擦俐，并回到跟隨著狀態(tài)脊阴。
沒有選出領(lǐng)導(dǎo)者
候選人在選舉中既沒有贏也沒有輸：如果多個(gè)跟隨者在同一時(shí)間成為候選人握侧，選票就可能被分裂蚯瞧，以至于沒有一個(gè)候選人能獲得大多數(shù)選票。在這種情況下品擎，每個(gè)候選人都開始一場新的選舉：增加自己的任期編號埋合，然后發(fā)送新一輪的 RequestVote 信息。但是萄传，在沒有外部干預(yù)的情況下甚颂，分裂投票的情況有可能無限重復(fù)。
如何避免分裂選票的情況
什么是分裂選票的情況秀菱？一場選舉沒有一個(gè)候選人能獲得大多數(shù)選票振诬，這就叫分裂選票。為什么會(huì)出現(xiàn)這種情況呢衍菱？其實(shí)是多個(gè)候選人在同一時(shí)間開始選舉造成的赶么。例如，一個(gè)5臺(tái)服務(wù)器的集群脊串，3臺(tái)服務(wù)器同時(shí)開始選舉辫呻，就有可能出現(xiàn)2票清钥、2票、1票的情況放闺。此時(shí)祟昭，沒有一臺(tái)服務(wù)器贏得選舉。解決這個(gè)問題很簡單怖侦，只要候選人開始的選舉的時(shí)間錯(cuò)開就行了篡悟。那候選人什么時(shí)候會(huì)開始選舉呢？根據(jù)前文匾寝，如果一個(gè)跟隨者在 election timeout 的時(shí)間內(nèi)沒有接收到任何消息恰力，就會(huì)開始一場選舉。所以旗吁，只要每個(gè)跟隨者的 election timeout 不一樣的踩萎，就可以極大地避免分裂投票的情況出現(xiàn)。
Raft 算法采用隨機(jī)化的 election timeout 來確保分裂選票的情況很少出現(xiàn)很钓。即使出現(xiàn)了香府，也能很快被解決。為了在第一時(shí)間避免分裂選票码倦，election timeout 從一個(gè)固定間隔隨機(jī)選擇（例如150—300ms）企孩。這樣做可以將服務(wù)器的超時(shí)時(shí)間分散開，使得大多數(shù)情況下袁稽，某個(gè)時(shí)刻勿璃，只有一個(gè)服務(wù)器超時(shí)。它會(huì)在其他服務(wù)器超時(shí)前贏得選舉和發(fā)送心跳消息推汽。即使出現(xiàn)了分裂選票的情況补疑，每個(gè)候選者都會(huì)重新隨機(jī)選擇 election timeout 并等待，超時(shí)后再開始新的選舉歹撒。這種方法可以減少新的選舉中出現(xiàn)分裂選票的可能性莲组。第九章展示了這種選舉領(lǐng)導(dǎo)者的方法非常快暖夭。
