余 瑯，戴振邦，黃家珞，劉官啟，鄭林杰，虎俊瑤

（西北民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 甘肅 蘭州 730124）

0 引言

分布式云存儲(chǔ)服務(wù)是新一代數(shù)字技術(shù)發(fā)展的重要基石。分布式系統(tǒng)只能滿足一致性[1]、可用性、分區(qū)容錯(cuò)性（Consistency、Availability、Partition tolerance）中的兩種特性，即CAP理論。對(duì)于大部分分布式應(yīng)用來(lái)說(shuō)，都需要滿足A、P特性，舍棄一致性。在保證業(yè)務(wù)的高并發(fā)性、高可用性和高穩(wěn)定性的同時(shí)，如何保證數(shù)據(jù)的一致性成為一個(gè)比較嚴(yán)峻的問(wèn)題。在最理想的情況下，集群中每個(gè)存儲(chǔ)單元的變化都能立即被其他節(jié)點(diǎn)知道，并且能時(shí)刻保持?jǐn)?shù)據(jù)的一致性[2]，這就是強(qiáng)一致性模型。但大多數(shù)情況下，網(wǎng)絡(luò)IO是不可控制的。在保證強(qiáng)一致性的大多數(shù)情況下，我們會(huì)犧牲高可用性，比如Guerraoui等[3]基于增量更新所提出的ICG方案，通過(guò)犧牲通信開(kāi)銷和查詢正確度，提高了ICG的操作延時(shí)。

因此，在大部分分布式應(yīng)用中選擇保證可用性、分區(qū)容錯(cuò)性，而舍棄強(qiáng)一致性。與MySQL集群一樣，Redis集群采用最終一致性以保證集群數(shù)據(jù)的同步收斂，來(lái)達(dá)到分布式系統(tǒng)的穩(wěn)定性。

1 Raft模型選舉

Raft算法[4]是一種基于Paxos的典型主從復(fù)制模式，相較于Paxos更加容易理解和工程實(shí)現(xiàn)，解決主機(jī)選舉問(wèn)題是Raft模型的首要關(guān)鍵點(diǎn)。初始狀態(tài)下，所有服務(wù)器都是Follower，并且隨機(jī)睡眠一段時(shí)間（0～1 000 ms），接著進(jìn)行倒計(jì)時(shí)。最先被喚醒的Follower會(huì)升級(jí)為Candidate，并請(qǐng)求其他Follower為它投票，多于半數(shù)則成為L(zhǎng)eader。由此完成Leader的選舉。

1.1 Raft心跳以及Leader宕機(jī)解決方案

在Raft模型中，Leader通過(guò)不斷地向所有Follower發(fā)送心跳包來(lái)判斷其是否在線的方法來(lái)維護(hù)一個(gè)Follower集合。在某Follower宕機(jī)后，Leader會(huì)將這個(gè)Follower移出集合，以確保每臺(tái)Follower的可用性。但Leader掛機(jī)后，休眠的Follower將進(jìn)入激活狀態(tài)，其中某些Follower會(huì)進(jìn)入Candidate狀態(tài)，并向其他Follower進(jìn)行選舉聲明，要求投票，收到半數(shù)投票后的Candidate將升級(jí)為L(zhǎng)eader。

Raft模型利用上述方案解決了集群中主從的轉(zhuǎn)換問(wèn)題。但在Raft模型中，Leader掛機(jī)后可能會(huì)同時(shí)有多個(gè)Follower升級(jí)為Candidate。由于在相同的選舉周期中每個(gè)Follower只有一次投票機(jī)會(huì)，若群集數(shù)量足夠，則可以避免同時(shí)將多個(gè)Candidate升級(jí)為L(zhǎng)eader。但在少量集群的情況下，若選舉過(guò)程中Candidate比Follower更多，所有的Candidate都會(huì)無(wú)法升級(jí)為L(zhǎng)eader，結(jié)果會(huì)導(dǎo)致阻塞系統(tǒng)多個(gè)選舉期。

1.2 最終一致性保證

Raft模型中只有Leader能夠執(zhí)行寫(xiě)操作，當(dāng)Leader接受寫(xiě)操作時(shí)，就更新寫(xiě)日志，同時(shí)對(duì)Leader管理的Follower進(jìn)行同步復(fù)制。為了確?？捎眯裕挥性谄渌鸉ollower全部同步完成之后，才會(huì)將所讀請(qǐng)求負(fù)載均衡地分配給各個(gè)服務(wù)器，否則讀操作會(huì)全部轉(zhuǎn)發(fā)到Leader中操作。

1.3 Raft日志

對(duì)于Raft模型來(lái)說(shuō)，每臺(tái)服務(wù)器無(wú)論是領(lǐng)導(dǎo)者還是跟隨者，都各自保存一份日志。日志來(lái)自于客戶端的請(qǐng)求，其本身被分成了多條記錄，記錄是由下標(biāo)索引的位置來(lái)進(jìn)行確定其唯一性。在記錄中有兩個(gè)主要信息：（1）每條記錄都包括一條供狀態(tài)機(jī)執(zhí)行的命令，命令的格式可以是客戶端與狀態(tài)機(jī)所達(dá)成一致的某種格式。（2）每條記錄都包括一個(gè)任期號(hào)，這個(gè)任期號(hào)是該條記錄創(chuàng)建時(shí)，領(lǐng)導(dǎo)者所處的任期。隨著日志記錄的增多，這個(gè)任期號(hào)也會(huì)單調(diào)上升。每臺(tái)服務(wù)器都必須保證日志能在崩潰后還可以恢復(fù)，所以日志通常是存于磁盤(pán)或其他穩(wěn)定的存儲(chǔ)介質(zhì)中。無(wú)論服務(wù)器作何更新，它都需要在接收到其他服務(wù)器的響應(yīng)之前將內(nèi)容寫(xiě)入磁盤(pán)。如果某條記錄在大多數(shù)服務(wù)器的日志中都存在，那么我們就稱該條記錄已提交(Committed)。如果一條記錄是已提交的，那么它就能安全的被狀態(tài)機(jī)執(zhí)行，Raft 就可保證該條記錄的持久性。

1.4 Raft日志一致性

Raft期望能將集群日志維持高水準(zhǔn)的一致性。理想狀態(tài)下，所有日志在任何時(shí)候信息都是相同的，甚至是服務(wù)器崩潰時(shí)也如此。雖難以達(dá)到理想狀態(tài)，但Raft會(huì)盡可能地保證在所有服務(wù)器上的日志是一樣的。

日志記錄的索引以及任期號(hào)在任何時(shí)候都是有效的，他們的組合可以唯一地標(biāo)識(shí)每一條日志的記錄。如果在不同的服務(wù)器中有兩條記錄的索引是相同的，任期號(hào)也是相同的，那么就可以保證它們所存儲(chǔ)的記錄也是相同的。除此之外，還能保證在這條記錄之前的所有記錄都能一一對(duì)應(yīng)。所以任期號(hào)和索引的組合可以保證整個(gè)日志的起始位置至該點(diǎn)位置的記錄的一致性。如果某條記錄是已提交的，那么在該記錄之前的記錄都應(yīng)該處于已提交狀態(tài)。

2 Raft模型針對(duì)小集群優(yōu)化方案

2.1 同步方案——網(wǎng)狀同步

在同步方案中，我們不采用Raft的原本同步方案，Leader不再主動(dòng)進(jìn)行心跳檢測(cè)，而是讓Follower進(jìn)行定期向Leader報(bào)告當(dāng)前信息。Leader會(huì)添加Follower集合和Leader集合的差集，然后將其發(fā)送給Follower最新的集群集合。通過(guò)這種方式，我們可以確保所有Follower都能在一個(gè)周期內(nèi)與Leader維護(hù)系統(tǒng)的集群集合相同，實(shí)現(xiàn)網(wǎng)狀同步。

如圖1所示，若服務(wù)器在接入時(shí)因?yàn)榫W(wǎng)絡(luò)等問(wèn)題發(fā)生故障，導(dǎo)致Follower相對(duì)于Leader發(fā)生分區(qū)（圖1左），就不可實(shí)現(xiàn)分布式的可用性。但在經(jīng)過(guò)上述過(guò)程（網(wǎng)狀同步）之后，F(xiàn)ollower會(huì)重新被分配到Leader上，同時(shí)該服務(wù)器會(huì)對(duì)Leader進(jìn)行同步，從而解決分區(qū)問(wèn)題。

2.2 選舉問(wèn)題優(yōu)化方案——繼承

上文提到了當(dāng) Leader發(fā)生宕機(jī)時(shí) Raft模型所提供的解決方案，并提到了在該解決方案中由于集群較小，服務(wù)器數(shù)量較少可能導(dǎo)致多個(gè)選舉周期阻塞問(wèn)題。該問(wèn)題的關(guān)鍵在于同一時(shí)間有多個(gè)Follower升級(jí)為Candidate的投票分歧問(wèn)題。吳奕等[5]提出了為每個(gè)節(jié)點(diǎn)設(shè)置C標(biāo)志位的策略。但該方法適用于具有大量節(jié)點(diǎn)的集群。那么我們?cè)谛〖褐锌梢赃x擇使用Leader定期地選擇出下一個(gè)Candidate的方法來(lái)解決該問(wèn)題。在 Leader發(fā)生宕機(jī)之后，Candidate經(jīng)過(guò)其他 Follower同意便可繼承 Leader的角色（這里為了確定Leader發(fā)生宕機(jī)問(wèn)題，Candidate不可以直接升級(jí)為L(zhǎng)eader，要由半數(shù)以上的Follower同意后才可以升級(jí)為L(zhǎng)eader）。同時(shí) Raft算法中的周期選舉被替換為周期分配。在周期分配模式中，Leader將為所維護(hù)的節(jié)點(diǎn)集合分配角色，包括一個(gè) Candidate和多個(gè)Follower。

2.3 優(yōu)化后每個(gè)節(jié)點(diǎn)的工作流程

如圖2所示：在優(yōu)化之后，每個(gè)服務(wù)器在一個(gè)工作周期中執(zhí)行以下任務(wù)：Leader：定期發(fā)送任命報(bào)告，為每個(gè)服務(wù)器分配新的角色。Candidate：定期檢查L(zhǎng)eader的存活狀態(tài)，若發(fā)現(xiàn)宕機(jī)就讓Follower進(jìn)行檢測(cè)，一旦有一半以上的Follower檢測(cè)到Leader不在線，則Candidate將立即升級(jí)為L(zhǎng)eader，并為所有的Follower分配新角色。若當(dāng)Leader在線時(shí)，Candidate也會(huì)進(jìn)行Follower的工作。Follower：定期上報(bào)服務(wù)器集合狀態(tài)，更新最新的服務(wù)器集合。

2.4 優(yōu)化效果

以上的優(yōu)化，在我們用Goland語(yǔ)言設(shè)計(jì)的goDFS——分布式文件系統(tǒng)中得到實(shí)現(xiàn)。在實(shí)驗(yàn)過(guò)程中可實(shí)現(xiàn)網(wǎng)狀同步。在選舉過(guò)程中，通過(guò)Leader定期地選擇出下一個(gè)Candidate，不再使用Raft模型原始的選舉方法，可以有效避免同時(shí)產(chǎn)生多個(gè)Candidate，避免不斷重新選舉導(dǎo)致系統(tǒng)堵塞的情況。

在選舉過(guò)程中，Leader通過(guò)繼承的方式定期地選擇出下一個(gè)Candidate。雖然該方法使Leader和Candidate同時(shí)宕機(jī)的概率非常小，但在實(shí)驗(yàn)中我們也手動(dòng)停止Leader和Candidate的運(yùn)行，結(jié)果是會(huì)導(dǎo)致集群崩潰，說(shuō)明該算法后期還需進(jìn)行優(yōu)化。

2.5 優(yōu)化后的集群失效問(wèn)題

通過(guò)上述說(shuō)明，繼承模式相對(duì)于選舉模式而言，不會(huì)產(chǎn)生多個(gè)Candidate競(jìng)爭(zhēng)所引起的選舉周期阻塞問(wèn)題，在Leader正常的情況下有更小的開(kāi)銷。但繼承模式相對(duì)于選舉模式來(lái)說(shuō)安全性較低，如當(dāng)Candidate和Leader同時(shí)宕機(jī)時(shí)，則不能將其恢復(fù)為正常狀態(tài)，即Leader會(huì)失效。對(duì)于小型集群來(lái)說(shuō)，Leader的壓力更大，而Candidate和Leader同時(shí)宕機(jī)的概率是極小的。而且在少量機(jī)器中，兩個(gè)節(jié)點(diǎn)同時(shí)失效，也會(huì)使集群崩潰。但在一般情況下，小集群中使用繼承模式是可以保證集群穩(wěn)定運(yùn)行，且一定程度上可解決小集群同步問(wèn)題。

2.6 繼承失敗問(wèn)題以及解決方案

繼承的解決方案雖然一定程度上解決了Raft競(jìng)爭(zhēng)選舉中斷導(dǎo)致的多集群?jiǎn)栴}，但是繼承方案仍然存在一定的問(wèn)題，如可能發(fā)生Leader和Candidate同時(shí)掛機(jī)的情況（在Leader重新任命一個(gè)Candidate之前，Leade發(fā)生故障，并且同時(shí)Candidate也發(fā)生故障導(dǎo)致導(dǎo)致節(jié)點(diǎn)繼承失?。?duì)于該問(wèn)題我們可以對(duì)選舉流程進(jìn)行優(yōu)化。一種可行的方法是，Leader在選舉時(shí)可以指定多個(gè)Candidate作為候選者，通過(guò)對(duì)Candidate的冗余來(lái)解決上述問(wèn)題。當(dāng)Leader和其中一個(gè)或多個(gè)Candidate宕機(jī)時(shí)，其他Candidate可以再次請(qǐng)求Follower進(jìn)行投票來(lái)選舉Leader。但同時(shí)，也會(huì)引入多個(gè)Candidate競(jìng)爭(zhēng)的問(wèn)題，這時(shí)我們可以控制在選舉Leader時(shí)對(duì) Candidate進(jìn)行排序，使得 Candidate形成線性關(guān)聯(lián)關(guān)系，即使在選舉過(guò)程中發(fā)生多個(gè)Candidate升級(jí)為多個(gè)Leader的問(wèn)題，也會(huì)在下一個(gè)周期由最高級(jí)別的Candidate（Leader）發(fā)生網(wǎng)狀同步來(lái)恢復(fù)集群的一致性。但系統(tǒng)在一段時(shí)間可能會(huì)出現(xiàn)多個(gè)集群，即便恢復(fù)后，也有可能發(fā)生日志的沖突，因此需要一定的時(shí)間進(jìn)行恢復(fù)。

第二種方法是由Candidate選擇一個(gè)服務(wù)器進(jìn)行信息備份，Candidate的備份服務(wù)器會(huì)監(jiān)聽(tīng)Candidate的狀態(tài)。當(dāng)Candidate以及Leader都發(fā)生宕機(jī)時(shí)，Candidate的備份服務(wù)器則會(huì)進(jìn)行繼承升級(jí)，成為新的Leader。雖然這種方案并沒(méi)有從根本上解決Leader以及Candidate同時(shí)失效的問(wèn)題，但是在集群數(shù)量較少的情況下，Candidate以及Leader都發(fā)生宕機(jī)后，則整個(gè)系統(tǒng)大概率將會(huì)進(jìn)入降級(jí)或者不可用的狀態(tài)，所以在一定程度上可以解決Leader以及Candidate同時(shí)失效的問(wèn)題。

3 結(jié)語(yǔ)

本文針對(duì)Raft模型在小集群情況下對(duì)Leader選舉方案和日志同步方案進(jìn)行優(yōu)化，但仍有些問(wèn)題需要探討和研究。如在選舉過(guò)程中我們采用的是繼承的方法，通過(guò)Leader狀態(tài)的服務(wù)器定期地選擇出下一個(gè)Candidate。但該方法可能會(huì)出現(xiàn)Leader和Candidate同時(shí)宕機(jī)的極小概率情況，在小集群中會(huì)導(dǎo)致集群崩潰。在3.5所提的方法中，Leader在選舉時(shí)指定多個(gè)Candidate作為候選者的方法會(huì)使得某段時(shí)間內(nèi)系統(tǒng)出現(xiàn)多個(gè)集群，需要一定的時(shí)間來(lái)進(jìn)行恢復(fù)，即便恢復(fù)后，日志也有可能發(fā)生沖突，所以恢復(fù)所需要的時(shí)間具有不確定性。但在小集群中由于節(jié)點(diǎn)少，同步日志的時(shí)間和恢復(fù)時(shí)間仍然是較短的，因此該方法仍然具有一定的可行性。另一種方法是由Candidate選擇一個(gè)服務(wù)器進(jìn)行信息備份，這種方案并沒(méi)有從根本上解決Leader和Candidate同時(shí)宕機(jī)的問(wèn)題，但Candidate 和Leader同時(shí)宕機(jī)大概率會(huì)使得系統(tǒng)將會(huì)進(jìn)入降級(jí)狀態(tài)或者崩潰不可用，所以該方法在小集群中的使用仍然具有一定的適用性。因此這些問(wèn)題優(yōu)化的設(shè)計(jì)和實(shí)現(xiàn)后期仍有待研究。