項(xiàng)目中使用ETCD來(lái)實(shí)現(xiàn)服務(wù)發(fā)現(xiàn)和配置信息的存儲(chǔ)，最近我抽空研究了一下ETCD和背后的一致性算法 — Raft算法的邏輯。
ETCD是什么
- ETCD是一個(gè)go語(yǔ)言實(shí)現(xiàn)的高可靠的KV存儲(chǔ)系統(tǒng)，支持HTTP協(xié)議的PUT/GET/DELETE操作；
- 為了支持服務(wù)注冊(cè)與發(fā)現(xiàn)，支持WATCH接口（通過(guò)http long poll實(shí)現(xiàn)）；
- 支持KEY持有TTL屬性；
- CAS（compare and swap）操作;
- 支持多key的事務(wù)操作；
- 支持目錄操作
簡(jiǎn)單的來(lái)說(shuō)，ETCD可以看做是一個(gè)no sql的存儲(chǔ)，存的是key-value的node，每個(gè)node又可以像樹(shù)形結(jié)構(gòu)一樣產(chǎn)生子node。它是集群化的運(yùn)行狀態(tài)來(lái)保證高可用，并且對(duì)外提供了一套簡(jiǎn)單友好的交互接口。
其實(shí)ETCD暫時(shí)就想介紹這么多，本文的重點(diǎn)在于Raft算法，只是我機(jī)智的考慮到站內(nèi)的SEO才加上ETCD的名號(hào):smirk:，以后會(huì)陸續(xù)寫(xiě)一些其他與ETCD相關(guān)的內(nèi)容。
一致性的基礎(chǔ)：Raft算法
ETCD實(shí)現(xiàn)高可靠的基礎(chǔ)在于Raft算法，也是理解ETCD工作原理最重要的一部分。類(lèi)似于zookeeper的zab協(xié)議（Paxos算法），Raft也是用于保證分布式環(huán)境下多節(jié)點(diǎn)數(shù)據(jù)的一致性，但更易于理解。
看了很多相關(guān)Raft算法的技術(shù)文章，要么是介紹的過(guò)于簡(jiǎn)單，要么是過(guò)于晦澀難懂。最后看了原始的論文In search of an Understandable Consensus Algorithm和infoQ上對(duì)應(yīng)的中文翻譯Raft 一致性算法論文譯文才對(duì)整個(gè)邏輯有細(xì)致的理解。
首先來(lái)看看Raft大致的原理，這是一個(gè)選主（leader selection）思想的算法，集群總每個(gè)節(jié)點(diǎn)都有三種可能的角色：
- leader
對(duì)客戶端通信的入口，對(duì)內(nèi)數(shù)據(jù)同步的發(fā)起者，一個(gè)集群通常只有一個(gè)leader節(jié)點(diǎn) - follower:
非leader的節(jié)點(diǎn)，被動(dòng)的接受來(lái)自leader的數(shù)據(jù)請(qǐng)求 - candidate:
一種臨時(shí)的角色，只存在于leader的選舉階段，某個(gè)節(jié)點(diǎn)想要變成leader，那么就發(fā)起投票請(qǐng)求，同時(shí)自己變成candidate。如果選舉成功，則變?yōu)閏andidate，否則退回為follower
數(shù)據(jù)提交的過(guò)程
先看前兩種角色，leader扮演的是分布式事務(wù)中的協(xié)調(diào)者，每次有數(shù)據(jù)更新的時(shí)候產(chǎn)生二階段提交（two-phase commit）。在leader收到數(shù)據(jù)操作的請(qǐng)求，先不著急更新本地?cái)?shù)據(jù)（數(shù)據(jù)是持久化在磁盤(pán)上的），而是生成對(duì)應(yīng)的log，然后把生成log的請(qǐng)求廣播給所有的follower。
每個(gè)follower在收到請(qǐng)求之后有兩種選擇：一種是聽(tīng)從leader的命令，也寫(xiě)入log，然后返回success回去；另一種情況，在某些條件不滿足的情況下，follower認(rèn)為不應(yīng)該聽(tīng)從leader的命令，返回false。例如下圖，leader收到客戶端的寫(xiě)請(qǐng)求，我們暫時(shí)不考慮請(qǐng)求的具體值，虛線表示leader先寫(xiě)log，
然后告訴所有的follower準(zhǔn)備提交數(shù)據(jù)，先和我一樣寫(xiě)log，
然后回到leader，此時(shí)如果超過(guò)半數(shù)的follower都成功寫(xiě)了log，那么leader開(kāi)始第二階段的提交：正式寫(xiě)入數(shù)據(jù)，然后同樣廣播給follower，follower也根據(jù)自身情況選擇寫(xiě)入或者不寫(xiě)入并返回結(jié)果給leader。繼續(xù)上面的例子，leader先寫(xiě)自己的數(shù)據(jù)，然后告訴follower也開(kāi)始持久化數(shù)據(jù)，
最終所有節(jié)點(diǎn)的數(shù)據(jù)達(dá)成一致，圖中用實(shí)線表示已提交的數(shù)據(jù)。
這兩階段中如果任意一個(gè)都有超過(guò)半數(shù)的follower返回false或者根本沒(méi)有返回，那么這個(gè)分布式事務(wù)是不成功的。此時(shí)雖然不會(huì)有回滾的過(guò)程，但是由于數(shù)據(jù)不會(huì)真正在多數(shù)節(jié)點(diǎn)上提交，所以會(huì)在之后的過(guò)程中被覆蓋掉。
選舉的過(guò)程
上面只說(shuō)了常規(guī)時(shí)候兩種角色是如何協(xié)調(diào)工作的，還剩下candidate沒(méi)說(shuō)，對(duì)，就是一個(gè)follower是如何逆襲成為leader的。
初始狀態(tài)下，大家都是平等的follower，那么follow誰(shuí)呢，總要選個(gè)老大吧。大家都蠢蠢欲動(dòng)，每個(gè)follower內(nèi)部都維護(hù)了一個(gè)隨機(jī)的timer。如下圖，
在timer時(shí)間到了的時(shí)候還沒(méi)有人主動(dòng)聯(lián)系它的話，那它就要變成candidate，同時(shí)發(fā)出投票請(qǐng)求（RequestVote）給其他人。特殊情況如下圖，S1和S3都變成了candidate，
當(dāng)然選不選就是人家的事了，原則是
每個(gè)follower一輪只能投一次票給一個(gè)candidate，
對(duì)于相同條件的candidate，follower們采取先來(lái)先投票的策略。如果超過(guò)半數(shù)的follower都認(rèn)為他是合適做領(lǐng)導(dǎo)的，那么恭喜，新的leader產(chǎn)生了，如下圖，S3變成了新一屆的大哥，又可以很開(kāi)心的像上一節(jié)一樣的正常工作了。
但是如果很不幸，沒(méi)有人愿意選這個(gè)悲劇的candidate，那它只有老老實(shí)實(shí)的變回小弟的狀態(tài)。
選舉完成之后，leader靠什么來(lái)確保小弟是跟著我的呢？答案是定時(shí)發(fā)送心跳檢測(cè)(heart beat)。小弟們也是通過(guò)心跳來(lái)感知大哥的存在的。如下圖
同樣的，如果在timer期間內(nèi)沒(méi)有收到大哥的聯(lián)絡(luò)，這時(shí)很可能大哥已經(jīng)跪了，如下圖，所有小弟又開(kāi)始蠢蠢欲動(dòng)，新的一輪(term)選舉開(kāi)始了。
好了，Raft算法的大致原理就是這樣了，下面我們來(lái)說(shuō)說(shuō)一些沒(méi)說(shuō)到的細(xì)節(jié)問(wèn)題。
選舉時(shí)會(huì)產(chǎn)生的問(wèn)題
之前說(shuō)過(guò)，在選舉階段，每個(gè)follower如果在自身的timer到期之后都會(huì)變成candidate去參與選舉。所以就這個(gè)candidate身份而言，是沒(méi)有特別條件的，每個(gè)follower都有機(jī)會(huì)參選。但是，在分布式的環(huán)境里，每個(gè)follower節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是不一樣的，考慮一下下圖的情況，在這些節(jié)點(diǎn)經(jīng)歷了一些損壞和恢復(fù)。此時(shí)S4想當(dāng)leader，
但是如果S4成功當(dāng)選的話，根據(jù)leader為上的原則，S4的log在index為4-7的數(shù)據(jù)，會(huì)覆蓋掉S2和S3的8。如何解決這樣的沖突的問(wèn)題呢？有兩種方法：第一種是S4在變?yōu)榇蟾缰?，先向所有的小弟拿?shù)據(jù)來(lái)保證自己數(shù)據(jù)是最全的；第二種方法是其他小弟遇到這樣資歷不足的大哥想上位的時(shí)候，完全不予以理睬。Raft算法認(rèn)為第一種策略過(guò)于復(fù)雜，所以選擇了第二種，保證數(shù)據(jù)只從leader流向follower。S4在vote請(qǐng)求中會(huì)帶上自身數(shù)據(jù)的描述信息，包括：
- term，自身處于的選舉周期
- lastLogIndex，log中最新的index值
- lastLogTerm，log中最近的index是在哪個(gè)term中產(chǎn)生的
S2和S3在收到vote請(qǐng)求時(shí)候會(huì)和自身的情況進(jìn)行對(duì)比，每個(gè)節(jié)點(diǎn)保存的數(shù)據(jù)信息包括：
- currentTerm，節(jié)點(diǎn)處于的term號(hào)
- log[ ]，自身的log集合
- commitIndex，log中最后一個(gè)被提交的index值
對(duì)比的原則有：
- 如果term < currentTerm，也就是說(shuō)candidate的版本還沒(méi)我新，返回 false
- 如果已經(jīng)投票給別的candidate了（votedFor），則返回false
- log匹配，如果和自身的log匹配上了，則返回true
這個(gè)log匹配原則（Log Matching Property）具體是：
如果在不同日志中的兩個(gè)條目有著相同的索引和任期號(hào)，則它們所存儲(chǔ)的命令是相同的。
如果在不同日志中的兩個(gè)條目有著相同的索引和任期號(hào)，則它們之間的所有條目都是完全一樣的。
這樣就可以一直等到含有最新數(shù)據(jù)的candidate被選上，從而保證領(lǐng)導(dǎo)人完全原則（Leader Completeness）：
如果一個(gè)日志的index在一個(gè)給定term內(nèi)被提交，那么這個(gè)index一定會(huì)出現(xiàn)在所有term號(hào)更大的領(lǐng)導(dǎo)人中。
好了，繼續(xù)看圖說(shuō)話。S4的vote請(qǐng)求，
| term | lastLogIndex | lastLogTerm |
|---|---|---|
| 10 | 6 | 7 |
被無(wú)情的拒絕。接下來(lái)S3也變成了candidate，
一直等到S3變成了candidate，發(fā)出vote請(qǐng)求。
| term | lastLogIndex | lastLogTerm |
|---|---|---|
| 11 | 6 | 8 |
被S4和S10接受，變成新的leader，并初始化兩個(gè)數(shù)組：
- nextIndex[ ]，表示需要發(fā)給每個(gè)follower的下一個(gè)日志條目的索引（初始化為leader最新log的index+1，因?yàn)閘eader總是先假定所有的follower和自己是一致的，后面說(shuō)明當(dāng)有不一致的時(shí)候是如何協(xié)商的）
- matchIndex[ ]，表示已經(jīng)復(fù)制到每個(gè)follower的log的最高index值（從0開(kāi)始遞增）
在這個(gè)例子中，S3中的這兩個(gè)數(shù)組會(huì)初始化為，
| S1 | S2 | S4 | S5 | |
|---|---|---|---|---|
| nextIndex | 7 | 7 | 7 | 7 |
| matchIndex | 0 | 0 | 0 | 0 |
數(shù)據(jù)更新的問(wèn)題
現(xiàn)在新的一屆leader選舉出來(lái)了，雖然選舉的過(guò)程保證了leader的數(shù)據(jù)是最新的，但是follower中的數(shù)據(jù)還是可能存在不一致的情況。比如下圖的S4，這就需要一個(gè)補(bǔ)償機(jī)制來(lái)糾正這個(gè)問(wèn)題。
在正常情況下，S3會(huì)給S4發(fā)心跳請(qǐng)求(一種名叫AppendEntries請(qǐng)求的特殊格式，entries為空)，其中攜帶一些數(shù)據(jù)信息，包括，
| term | prevIndex | prevTerm | entries | commitIndex |
|---|---|---|---|---|
| 11 | 6 | 8 | [ ] | 6 |
commitIndex之前已經(jīng)解釋過(guò)了，是log中最后一個(gè)被提交的index值。prevIndex與lastLogIndex類(lèi)似，都是最新的日志的index值，只是屬于不同的請(qǐng)求類(lèi)型。
prevTerm也與lastLogTerm類(lèi)似，是prevLogIndex對(duì)應(yīng)的term號(hào)。
S4在接收到該請(qǐng)求之后會(huì)做一致性的判斷，規(guī)則包括，
- 如果 term < currentTerm返回 false
- 如果在prevLogIndex處的log的term號(hào)與prevLogTerm不匹配時(shí)，返回 false
- 如果一條已經(jīng)存在的log與新的沖突（index相同但是term號(hào)不同），則刪除已經(jīng)存在的日志和它之后所有的日志，返回true
- 添加任何在已有的log中不存在的index，返回true
- 如果請(qǐng)求中l(wèi)eader的commitIndex > 自身的commitIndex，則比較leader的commitIndex和最新log index，將其中較小的賦給自身的commitIndex
結(jié)果與規(guī)則2不符合，返回false給S3。這時(shí)S3需要做一次退讓?zhuān)薷谋４娴膎extIndex數(shù)組，將S4的nextIndex退化為6
再次發(fā)送AppendEntries詢(xún)問(wèn)S4
| term | prevIndex | prevTerm | entries | commitIndex |
|---|---|---|---|---|
| 11 | 5 | 8 | [ ] | 5 |
如此循環(huán)的退讓?zhuān)恢钡絥extIndex減小到4
S3此時(shí)發(fā)送的請(qǐng)求為，
| term | prevIndex | prevTerm | entries | commitIndex |
|---|---|---|---|---|
| 11 | 3 | 3 | [ ] | 3 |
S4和自己的log匹配成功，返回true，并告訴leader，當(dāng)前的matchIndex等于3。S3收到之后更新matchIndex數(shù)組，
| S1 | S2 | S4 | S5 | |
|---|---|---|---|---|
| nextIndex | 7 | 7 | 4 | 7 |
| matchIndex | 0 | 6 | 3 | 0 |
并發(fā)送從nextIndex之后的數(shù)據(jù)(entries)，
| term | prevIndex | prevTerm | entries | commitIndex |
|---|---|---|---|---|
| 11 | 3 | 3 | [8] | 4 |
S4再根據(jù)覆蓋的原則，把自身的數(shù)據(jù)追平leader，并拋棄之后的數(shù)據(jù)。
這樣消息往復(fù)，數(shù)據(jù)最終一致。
一些其他的問(wèn)題
還有一些值得注意的特殊情況，比如log的清理。log是以追加的方式遞增的，隨著系統(tǒng)的不斷運(yùn)行，log會(huì)越來(lái)越大。Raft通過(guò)log的snapshot方式，可以定期壓縮log為一個(gè)snapshot，并且清除之前的log。壓縮的具體策略可以參考原論文。
還有集群節(jié)點(diǎn)的增減。當(dāng)網(wǎng)絡(luò)發(fā)生波動(dòng)的時(shí)候，節(jié)點(diǎn)可能需要增減甚至發(fā)生網(wǎng)絡(luò)分區(qū)。具體參考：ETCD系列之二：部署集群
總結(jié)
Raft是一種基于leader選舉的算法，用于保證分布式數(shù)據(jù)的一致性。所有節(jié)點(diǎn)在三個(gè)角色（leader, follower和candidate）之中切換。選舉階段candidate向其他節(jié)點(diǎn)發(fā)送vote請(qǐng)求，但是只有包括所有最新數(shù)據(jù)的節(jié)點(diǎn)可以變?yōu)閘eader。
在數(shù)據(jù)同步階段，leader通過(guò)一些標(biāo)記（commitIndex，term，prevTerm，prevIndex等等）與follower不斷協(xié)商最終達(dá)成一致。當(dāng)有新的數(shù)據(jù)產(chǎn)生時(shí)，采用二階段（twp-phase）提交，先更新log，等大多數(shù)節(jié)點(diǎn)都做完之后再正式提交數(shù)據(jù)。
以上的圖片來(lái)自github上raft算法的算法動(dòng)畫(huà)的截圖。
（完）
