姓名：鄧復(fù)元
學(xué)號(hào)17020120041
轉(zhuǎn)載自：https://blog.csdn.net/NetEaseResearch/article/details/110006508
【嵌牛導(dǎo)讀】：本文介紹了RAFT算法的特點(diǎn)和基本應(yīng)用
【嵌牛鼻子】：Curve實(shí)踐
【嵌牛模塊】：RAFT算法概念彤钟、特點(diǎn)、應(yīng)用場合
【嵌牛正文】：
urve作為高性能、高可用苛秕、高可靠的新一代分布式存儲(chǔ)系統(tǒng)，對(duì)于多副本數(shù)據(jù)同步榔组，負(fù)載均衡搞坝，容災(zāi)恢復(fù)方面都有較高的要求。Curve選用Raft算法作為底層一致性協(xié)議喉祭，并基于Raft的特性养渴，實(shí)現(xiàn)了異常情況下的數(shù)據(jù)遷移和自動(dòng)恢復(fù)。下面首先簡要介紹一下Raft算法的一些基本概念和術(shù)語泛烙，再詳細(xì)介紹其在Curve中的實(shí)踐理卑。
Raft算法中，有Leader蔽氨，F(xiàn)ollower藐唠，Candidate三種角色，它們之間的轉(zhuǎn)換關(guān)系如下圖：
在同一時(shí)刻鹉究，只能有一個(gè)Leader宇立，當(dāng)選Leader后到發(fā)起下一次選舉稱為一個(gè)任期（term），Leader負(fù)責(zé)通過心跳向follower保持統(tǒng)治自赔，并同步數(shù)據(jù)給Follower妈嘹。Follower發(fā)起選舉的前提是超時(shí)未收到Leader的心跳。
Leader競選：RAFT是一種Majority的協(xié)議绍妨，即贏得選舉的條件是獲得包括自己以內(nèi)的大多數(shù)節(jié)點(diǎn)的投票润脸。Follower超時(shí)未收到Leader的心跳，則會(huì)成為Candidate痘绎，發(fā)起新一輪的選舉津函。每個(gè)節(jié)點(diǎn)在每個(gè)Term內(nèi)只能投一次票，且服從先到先服務(wù)原則孤页。為了避免多個(gè)Follower同時(shí)超時(shí)尔苦，raft中的選舉超時(shí)時(shí)間是一個(gè)固定時(shí)間加一個(gè)隨機(jī)時(shí)間。
日志復(fù)制：在任期內(nèi)行施，Leader接收來自client的請(qǐng)求允坚，并將其封裝成一個(gè)日志條目（Raft Log Entry）把它append到自己的raft log中，然后并行地向其它服務(wù)器發(fā)起AppendEntries RPC蛾号，當(dāng)確定該entry被大多數(shù)節(jié)點(diǎn)成功復(fù)制后（這個(gè)過程叫commit）稠项，就可以執(zhí)行命令（這一步叫apply），并返回給client結(jié)果鲜结。log entry由三個(gè)部分組成展运，分別是：1、log index精刷，2拗胜、log所屬的term，3怒允、要執(zhí)行的命令埂软。
配置變更：在Raft中，稱復(fù)制組有哪些成員稱為配置纫事，配置并不是固定的勘畔，會(huì)根據(jù)需求增刪節(jié)點(diǎn)或異常情況下需要替換掉有問題的節(jié)點(diǎn)所灸。從一個(gè)配置直接切換到另一個(gè)配置是不安全的，因?yàn)椴煌姆?wù)器會(huì)在不同的時(shí)間點(diǎn)進(jìn)行切換炫七。因此Raft配置變更時(shí)爬立，會(huì)先創(chuàng)建一個(gè)特殊的log entry Cold,new，這條entry被commit后诉字，會(huì)進(jìn)入共同一致階段懦尝，即新舊配置一起做決定知纷。這時(shí)候壤圃，再生成一個(gè)Cnew的log entry，等這條entry被commit后琅轧，就可以由新配置獨(dú)立做決定了伍绳。
安裝快照：Raft快照指的是某個(gè)時(shí)刻保存下來的系統(tǒng)狀態(tài)的集合≌Ч穑快照有兩方面的作用：一個(gè)是日志壓縮冲杀，打了快照之后，在此時(shí)刻之前的log entry就可以刪除了睹酌。另一個(gè)是啟動(dòng)加速权谁，系統(tǒng)起來的時(shí)候不需要重新回放所有日志。當(dāng)Leader同步日志給Follower的時(shí)候憋沿，發(fā)現(xiàn)所需的log entry已經(jīng)被快照刪掉了旺芽，即可通過發(fā)送InstallSnapshot RPC給Follower進(jìn)行同步。
Curve系統(tǒng)是一個(gè)分布式存儲(chǔ)系統(tǒng)辐啄，在Curve系統(tǒng)中采章，數(shù)據(jù)分片的最小單位稱之為Chunk，默認(rèn)的Chunk大小是16MB壶辜。在大規(guī)模的存儲(chǔ)容量下悯舟，會(huì)產(chǎn)生大量的Chunk，如此眾多的Chunk砸民，會(huì)對(duì)元數(shù)據(jù)的存儲(chǔ)抵怎、管理產(chǎn)生一定壓力。因此引入CopySet的概念岭参。CopySet可以理解為一組ChunkServer的集合反惕，一個(gè)Copyset管理多個(gè)Chunk，多副本間的同步和管理已Copyset為單位組織冗荸。ChunkServer承璃，Copyset和Chunk三者之間的關(guān)系如下圖：
Curve copyset選用了braft作為一致性協(xié)議的組件，使用方式為multi-raft蚌本，即同一個(gè)機(jī)器盔粹，可以屬于多個(gè)復(fù)制組隘梨，反過來說，一個(gè)機(jī)器上舷嗡，可以存在多個(gè)raft實(shí)例轴猎。基于braft进萄，我們實(shí)現(xiàn)了副本間數(shù)據(jù)同步捻脖，系統(tǒng)調(diào)度，輕量級(jí)raft快照等功能中鼠，下面一一詳細(xì)介紹可婶。
CopysetNode在ChunkServer端封裝了braft node，具體關(guān)系如下圖所示：
Curve client發(fā)送一個(gè)寫請(qǐng)求時(shí)援雇，三副本情況下的具體的步驟如下：
Client發(fā)送寫請(qǐng)求給Leader ChunkServer
ChunkServer收到請(qǐng)求矛渴，將請(qǐng)求封裝成一個(gè)log entry，提交給raft
braft模塊在本地持久化entry的同時(shí)發(fā)送entry給其他副本（ChunkServer）
本地持久化entry成功惫搏，且另一個(gè)副本也落盤成功則commit
commit后執(zhí)行apply具温，apply即執(zhí)行我們的寫盤操作。
在此過程中筐赔，用戶的數(shù)據(jù)和操作铣猩，通過braft中的log entry的方式在副本間傳遞，進(jìn)行數(shù)據(jù)同步茴丰。在三副本場景下达皿，向上層返回的時(shí)間取決于兩個(gè)較快的副本的速度，因此可以減少慢盤的影響较沪。對(duì)于較慢的那個(gè)副本鳞绕，leader也會(huì)通過無限重試的方式同步數(shù)據(jù)，因此在系統(tǒng)正常工作的前提下尸曼，最終三個(gè)副本的數(shù)據(jù)是一致的们何。
在Curve中，ChunkServer定期向元數(shù)據(jù)節(jié)點(diǎn)MDS上報(bào)心跳控轿，心跳中除了ChunkServer自身的一些統(tǒng)計(jì)信息冤竹，還包含ChunkServer上面的CopySet的統(tǒng)計(jì)信息，包含它的leader茬射，復(fù)制組成員鹦蠕，是否有配置變更執(zhí)行中，配置的epoch等在抛。MDS基于這些統(tǒng)計(jì)信息钟病，會(huì)生成一系列的Raft配置變更請(qǐng)求并下發(fā)給Copyset的leader所在的ChunkServer。
Curve ChunkServer會(huì)定期向MDS上報(bào)心跳。MDS調(diào)度下發(fā)配置變更是在心跳的response中完成的肠阱。上報(bào)心跳的過程如下圖：
心跳是定時(shí)任務(wù)觸發(fā)的票唆，ChunkServer除了上報(bào)一些自己的容量信息等統(tǒng)計(jì)信息外，還會(huì)上報(bào)Copyset的一些信息屹徘，比如leader走趋，成員，epoch噪伊，是否有進(jìn)行中的配置變更等簿煌。
MDS在心跳response中下發(fā)配置變更的過程如下圖：
ChunkServer收到response后，解析其中的配置變更信息鉴吹，并下發(fā)給每個(gè)Copyset姨伟。
epoch同步配置。MDS生成的調(diào)度信息拙寡，是由后臺(tái)定時(shí)任務(wù)觸發(fā)授滓，并在ChunkServer下一次請(qǐng)求到來時(shí)在response中下發(fā)的琳水，因此MDS下發(fā)的配置變更有可能是過期的肆糕。為了實(shí)現(xiàn)MDS和ChunkServer之間的配置同步，Curve引入了epoch機(jī)制在孝，初始狀態(tài)诚啃，epoch初始為0，每進(jìn)行一次配置變更（包括leader變更）私沮，epoch都會(huì)加一始赎。當(dāng)MDS中的epoch等于ChunkServer端的epoch時(shí)，即將下發(fā)的配置變更才認(rèn)為是有效的仔燕。epoch與term有何區(qū)別造垛？term用于表示Leader的任期，即只跟選舉有關(guān)晰搀，而epoch是與配置變更相關(guān)的五辽，也包括了Leader選舉這種情況。
epoch的更新外恕。epoch是在ChunkServer端更新的杆逗，braft在實(shí)現(xiàn)上提供了一個(gè)用戶狀態(tài)機(jī)，在braft內(nèi)部發(fā)生變化鳞疲，比如apply罪郊，出錯(cuò)，關(guān)閉尚洽，打快照悔橄，加載快照，leader變更，配置變更等時(shí)會(huì)調(diào)用用戶狀態(tài)機(jī)中對(duì)應(yīng)的函數(shù)癣疟。Curve copyset通過繼承的方式實(shí)現(xiàn)這個(gè)用戶狀態(tài)機(jī)來完成與braft的交互尺铣，epoch是在on_configuration_committed函數(shù)中加一的。在braft中争舞，當(dāng)Leader變更的時(shí)候會(huì)把當(dāng)前的配置再提交一遍凛忿，因此在on_configuration_committed中增加epoch即可保證在配置發(fā)生變化或者Leader變更時(shí)epoch順序遞增。
epoch的持久化竞川。在MDS端店溢，epoch隨著CopySet的其他信息一起持久化在etcd中。ChunkServer也對(duì)epoch進(jìn)行了持久化委乌，但是ChunkServer中持久化epoch并不是每次epoch發(fā)生變化都需要持久化的床牧。這是利用了raft的日志回放和快照功能≡饷常考慮以下兩種情況：
假設(shè)raft沒有打快照戈咳，那么就不需要持久化epoch，因?yàn)樗胁僮魅罩竞敬担ㄅ渲米兏膃ntry都已持久化著蛙，當(dāng)服務(wù)重啟的時(shí)候，回放這些日志的時(shí)候會(huì)依次再調(diào)用一遍on_configuration_committed耳贬，最后epoch會(huì)恢復(fù)到重啟前的值踏堡。
當(dāng)raft有快照時(shí)，打快照前的entry都會(huì)被刪除咒劲，就不能通過上面的方式回放顷蟆，因此必須要持久化。但我們只需要在打raft快照時(shí)持久化epoch的當(dāng)前值即可腐魂。這樣當(dāng)系統(tǒng)重啟的時(shí)候帐偎，會(huì)先安裝raft快照，安裝后epoch恢復(fù)到快照時(shí)的值蛔屹，再通過執(zhí)行后面的log entry削樊，最終epoch恢復(fù)到重啟前的值。在打快照時(shí)更新epoch是在on_snapshot_save函數(shù)中完成的判导。
上面介紹Raft算法的時(shí)候介紹過嫉父，Raft需要定時(shí)打快照，以清理老的log entry眼刃，否則Raft日志會(huì)無限增長下去绕辖。打快照的時(shí)候需要保存系統(tǒng)當(dāng)前的狀態(tài)，對(duì)于Curve塊存儲(chǔ)場景來說擂红，系統(tǒng)狀態(tài)就是Chunk當(dāng)前的數(shù)據(jù)仪际。直觀的方案是將打快照時(shí)刻的全部chunk拷貝一遍備份起來围小。但是這樣有兩個(gè)問題：
空間上要多出一倍，空間浪費(fèi)非常嚴(yán)重
Curve默認(rèn)打快照的間隔是30分鐘一次树碱，這種方案下會(huì)有頻繁的數(shù)據(jù)拷貝肯适，對(duì)磁盤造成很大的壓力，影響正常的IO成榜。
因此框舔，Curve中使用的Raft快照是輕量級(jí)的，即打快照的時(shí)候只保存當(dāng)前的Chunk文件的列表赎婚，不對(duì)Chunk本身做備份刘绣。具體流程如下：
這樣會(huì)導(dǎo)致Follower下載到的chunk文件不是打快照時(shí)的狀態(tài)，而是最新的狀態(tài)挣输，在回放日志的時(shí)候纬凤，會(huì)把這些新數(shù)據(jù)再寫一遍。但這對(duì)于我們的場景是可以接受的撩嚼，因?yàn)榈讓佣际歉采w寫是冪等的停士，即寫一次和寫多次結(jié)果是一致的。
本篇文章首先介紹了Raft一致性算法的一些基本概念完丽。隨后介紹了Raft算法新一代高性能分布式存儲(chǔ)系統(tǒng)Curve中的應(yīng)用恋技，分別從數(shù)據(jù)同步，系統(tǒng)調(diào)度和Raft快照三個(gè)角度介紹了Curve中使用Raft的細(xì)節(jié)舰涌。關(guān)于Curve的更進(jìn)一步介紹詳見我們的代碼倉庫：https://github.com/opencurve/curve猖任。另外，Curve開源分享也在火熱進(jìn)行中瓷耙，分享的ppt可以在https://github.com/opencurve/curve-meetup-slides倉庫中獲取。
作者：查日蘇刁赖，網(wǎng)易數(shù)帆存儲(chǔ)團(tuán)隊(duì)高級(jí)C++開發(fā)工程師搁痛，高性能分布式存儲(chǔ)系統(tǒng)Curve核心開發(fā)。
如有理解和描述上有疏漏或者錯(cuò)誤的地方宇弛，歡迎共同交流鸡典；參考已經(jīng)在參考文獻(xiàn)中注明，但仍有可能有疏漏的地方枪芒，有任何侵權(quán)或者不明確的地方彻况，歡迎指出，必定及時(shí)更正或者刪除舅踪；文章供于學(xué)習(xí)交流纽甘，轉(zhuǎn)載注明出處
[1] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14). 2014: 305-319.
相關(guān)視頻：
Curve核心組件之ChunkServer數(shù)據(jù)節(jié)點(diǎn)
相關(guān)文章：
