領(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)者能夠簡(jiǎn)化可復(fù)制日志的管理。例如，領(lǐng)導(dǎo)者能夠決定在哪個(gè)地方放置新的日志條目而不需要咨詢其他服務(wù)器的意見，并且數(shù)據(jù)以一種簡(jiǎn)單的形式從領(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)掛了，然后開始一場(chǎng)選舉，以選出一個(gè)新的領(lǐng)導(dǎo)者。為了開始一場(chǎng)選舉，
- 跟隨者會(huì)增加自己的任期，并轉(zhuǎn)換為候選人狀態(tài)
- 它會(huì)給集群中的其他服務(wù)器發(fā)送 RequestVote 消息，問他們是否愿意為自己投票
- 候選人處于候選狀態(tài)，直到
- 自己成為領(lǐng)導(dǎo)者
- 別的服務(wù)器成為了領(lǐng)導(dǎo)者
- 沒有選出領(lǐng)導(dǎo)者
對(duì)于接收者來說，如果投贊同票，需要同時(shí)滿足一下兩個(gè)條件：
- 如果一個(gè)服務(wù)器的當(dāng)前任期大于候選人的任期，那么該服務(wù)器投反對(duì)票。
- 如果一個(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)中返回反對(duì)意見和自己的任期。領(lǐng)導(dǎo)者收到后會(huì)將自己的任期更新為這個(gè)更大的任期，并回到跟隨著狀態(tài)。
沒有選出領(lǐng)導(dǎo)者
候選人在選舉中既沒有贏也沒有輸：如果多個(gè)跟隨者在同一時(shí)間成為候選人，選票就可能被分裂，以至于沒有一個(gè)候選人能獲得大多數(shù)選票。在這種情況下，每個(gè)候選人都開始一場(chǎng)新的選舉：增加自己的任期編號(hào)，然后發(fā)送新一輪的 RequestVote 信息。但是，在沒有外部干預(yù)的情況下，分裂投票的情況有可能無限重復(fù)。
如何避免分裂選票的情況
什么是分裂選票的情況？一場(chǎng)選舉沒有一個(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è)問題很簡(jiǎn)單，只要候選人開始的選舉的時(shí)間錯(cuò)開就行了。那候選人什么時(shí)候會(huì)開始選舉呢？根據(jù)前文，如果一個(gè)跟隨者在 election timeout 的時(shí)間內(nèi)沒有接收到任何消息，就會(huì)開始一場(chǎng)選舉。所以，只要每個(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)者的方法非常快。
