摘要：實(shí)現(xiàn)線性一致讀最常規(guī)的辦法是走協(xié)議，將讀請(qǐng)求同樣按照處理，通過復(fù)制和狀態(tài)機(jī)執(zhí)行來獲取讀結(jié)果，然后再把讀取的結(jié)果返回給。使用發(fā)起線性一致讀請(qǐng)求，當(dāng)安全讀取時(shí)傳入的將被調(diào)用，正常情況下從狀態(tài)機(jī)中讀取數(shù)據(jù)返回給客戶端，將保證讀取的線性一致性。

SOFAStack
Scalable?Open?Financial?Architecture?Stack
是螞蟻金服自主研發(fā)的金融級(jí)分布式架構(gòu)，包含了構(gòu)建金融級(jí)云原生架構(gòu)所需的各個(gè)組件，是在金融場(chǎng)景里錘煉出來的最佳實(shí)踐。

本文為《剖析 | SOFAJRaft 實(shí)現(xiàn)原理》第三篇，本篇作者米麒麟，來自陸金所。《剖析 | SOFAJRaft 實(shí)現(xiàn)原理》系列由 SOFA 團(tuán)隊(duì)和源碼愛好者們出品，項(xiàng)目代號(hào)：，目前領(lǐng)取已經(jīng)完成，感謝大家的參與。

SOFAJRaft?是一個(gè)基于?Raft?一致性算法的生產(chǎn)級(jí)高性能?Java?實(shí)現(xiàn)，支持?MULTI-RAFT-GROUP，適用于高負(fù)載低延遲的場(chǎng)景。

SOFAJRaft?：https://github.com/sofastack/sofa-jraft

線性一致讀是在分布式系統(tǒng)中實(shí)現(xiàn)?Java?volatile?語義，當(dāng)客戶端向集群發(fā)起寫操作的請(qǐng)求并且獲得成功響應(yīng)之后，該寫操作的結(jié)果要對(duì)所有后來的讀請(qǐng)求可見。實(shí)現(xiàn)線性一致讀常規(guī)手段是走?Raft?協(xié)議，將讀請(qǐng)求同樣按照?Log?處理，通過日志復(fù)制和狀態(tài)機(jī)執(zhí)行獲取讀結(jié)果返回給客戶端，SOFAJRaft?采用?ReadIndex?替代走?Raft?狀態(tài)機(jī)的方案。本文將圍繞?Raft Log Read，ReadIndex Read?以及?Lease Read?等方面剖析線性一致讀原理，闡述?SOFAJRaft?如何使用?ReadIndex?和?Lease Read?實(shí)現(xiàn)線性一致讀：

什么是線性一致讀？共識(shí)算法只能保證多個(gè)節(jié)點(diǎn)對(duì)某個(gè)對(duì)象的狀態(tài)是一致的，以?Raft?為例只能保證不同節(jié)點(diǎn)對(duì)?Raft Log?達(dá)成一致，那么?Log?后面的狀態(tài)機(jī)的一致性呢？

基于?ReadIndex?和?Lease Read?方式?SOFAJRaft?如何實(shí)現(xiàn)高效的線性一致讀？

什么是線性一致讀? 所謂線性一致讀，一個(gè)簡(jiǎn)單的例子是在?t1 的時(shí)刻我們寫入了一個(gè)值，那么在?t1 之后，我們一定能讀到這個(gè)值，不可能讀到?t1?之前的舊值(想想?Java?中的?volatile?關(guān)鍵字，即線性一致讀就是在分布式系統(tǒng)中實(shí)現(xiàn)?Java?volatile?語義)。簡(jiǎn)而言之是需要在分布式環(huán)境中實(shí)現(xiàn)?Java?volatile?語義效果，即當(dāng)?Client?向集群發(fā)起寫操作的請(qǐng)求并且獲得成功響應(yīng)之后，該寫操作的結(jié)果要對(duì)所有后來的讀請(qǐng)求可見。和?volatile?的區(qū)別在于?volatile?是實(shí)現(xiàn)線程之間的可見，而?SOFAJRaft?需要實(shí)現(xiàn)?Server?之間的可見。

如上圖?Client A、B、C、D?均符合線性一致讀，其中?D?看起來是?Stale Read，其實(shí)并不是，D?請(qǐng)求橫跨 3 個(gè)階段，而?Read?可能發(fā)生在任意時(shí)刻，所以讀到 1 或 2 都行。

實(shí)現(xiàn)線性一致讀最常規(guī)的辦法是走?Raft?協(xié)議，將讀請(qǐng)求同樣按照?Log?處理，通過?Log?復(fù)制和狀態(tài)機(jī)執(zhí)行來獲取讀結(jié)果，然后再把讀取的結(jié)果返回給?Client。因?yàn)?Raft?本來就是一個(gè)為了實(shí)現(xiàn)分布式環(huán)境下線性一致性的算法，所以通過?Raft?非常方便的實(shí)現(xiàn)線性?Read，也就是將任何的讀請(qǐng)求走一次?Raft Log，等此?Log?提交之后在?apply?的時(shí)候從狀態(tài)機(jī)里面讀取值，一定能夠保證這個(gè)讀取到的值是滿足線性要求的。

當(dāng)然，因?yàn)槊看?Read?都需要走?Raft?流程，Raft?Log?存儲(chǔ)、復(fù)制帶來刷盤開銷、存儲(chǔ)開銷、網(wǎng)絡(luò)開銷，走?Raft Log不僅僅有日志落盤的開銷，還有日志復(fù)制的網(wǎng)絡(luò)開銷，另外還有一堆的?Raft?“讀日志” 造成的磁盤占用開銷，導(dǎo)致?Read?操作性能是非常低效的，所以在讀操作很多的場(chǎng)景下對(duì)性能影響很大，在讀比重很大的系統(tǒng)中是無法被接受的，通常都不會(huì)使用。

在?Raft?里面，節(jié)點(diǎn)有三個(gè)狀態(tài)：Leader，Candidate?和?Follower，任何?Raft?的寫入操作都必須經(jīng)過?Leader，只有?Leader?將對(duì)應(yīng)的?Raft Log?復(fù)制到?Majority?的節(jié)點(diǎn)上面認(rèn)為此次寫入是成功的。所以如果當(dāng)前?Leader?能確定一定是?Leader，那么能夠直接在此?Leader?上面讀取數(shù)據(jù)，因?yàn)閷?duì)于?Leader?來說，如果確認(rèn)一個(gè)?Log?已經(jīng)提交到大多數(shù)節(jié)點(diǎn)，在?t1?的時(shí)候?apply?寫入到狀態(tài)機(jī)，那么在?t1?后的?Read?就一定能讀取到這個(gè)新寫入的數(shù)據(jù)。

那么如何確認(rèn)?Leader?在處理這次?Read?的時(shí)候一定是?Leader?呢？在?Raft?論文里面，提到兩種方法：

ReadIndex Read

Lease Read

第一種是?ReadIndex?Read，當(dāng)?Leader?需要處理?Read?請(qǐng)求時(shí)，Leader?與過半機(jī)器交換心跳信息確定自己仍然是?Leader?后可提供線性一致讀：

Leader?將自己當(dāng)前?Log?的?commitIndex?記錄到一個(gè)?Local?變量?ReadIndex?里面；

接著向?Followers?節(jié)點(diǎn)發(fā)起一輪 Heartbeat，如果半數(shù)以上節(jié)點(diǎn)返回對(duì)應(yīng)的?Heartbeat?Response，那么?Leader就能夠確定現(xiàn)在自己仍然是?Leader；

Leader?等待自己的?StateMachine?狀態(tài)機(jī)執(zhí)行，至少應(yīng)用到?ReadIndex?記錄的?Log，直到?applyIndex?超過?ReadIndex，這樣就能夠安全提供?Linearizable?Read，也不必管讀的時(shí)刻是否?Leader?已飄走；

Leader?執(zhí)行?Read?請(qǐng)求，將結(jié)果返回給?Client。

使用?ReadIndex Read?提供?Follower?Read?的功能，很容易在?Followers?節(jié)點(diǎn)上面提供線性一致讀，F(xiàn)ollower?收到?Read?請(qǐng)求之后：

Follower?節(jié)點(diǎn)向?Leader?請(qǐng)求最新的?ReadIndex；

Leader?仍然走一遍之前的流程，執(zhí)行上面前 3 步的過程(確定自己真的是?Leader)，并且返回?ReadIndex?給?Follower；

Follower?等待當(dāng)前的狀態(tài)機(jī)的?applyIndex?超過?ReadIndex；

Follower?執(zhí)行?Read?請(qǐng)求，將結(jié)果返回給?Client。

不同于通過?Raft?Log?的?Read，ReadIndex Read?使用?Heartbeat?方式來讓?Leader?確認(rèn)自己是?Leader，省去?Raft?Log?流程。相比較于走?Raft?Log?方式，ReadIndex?Read?省去磁盤的開銷，能夠大幅度提升吞吐量。雖然仍然會(huì)有網(wǎng)絡(luò)開銷，但是?Heartbeat?本來就很小，所以性能還是非常好的。

雖然?ReadIndex?Read?比原來的?Raft?Log?Read?快很多，但畢竟還是存在?Heartbeat?網(wǎng)絡(luò)開銷，所以考慮做更進(jìn)一步的優(yōu)化。Raft?論文里面提及一種通過?Clock +?Heartbeat?的?Lease?Read?優(yōu)化方法，也就是?Leader?發(fā)送?Heartbeat?的時(shí)候首先記錄一個(gè)時(shí)間點(diǎn)?Start，當(dāng)系統(tǒng)大部分節(jié)點(diǎn)都回復(fù)?Heartbeat?Response，由于?Raft?的選舉機(jī)制，F(xiàn)ollower?會(huì)在?Election Timeout?的時(shí)間之后才重新發(fā)生選舉，下一個(gè)?Leader?選舉出來的時(shí)間保證大于?Start+Election?Timeout/Clock Drift Bound，所以可以認(rèn)為?Leader?的?Lease?有效期可以到?Start+Election?Timeout/Clock Drift Bound?時(shí)間點(diǎn)。Lease?Read?與?ReadIndex?類似但更進(jìn)一步優(yōu)化，不僅節(jié)省?Log，而且省掉網(wǎng)絡(luò)交互，大幅提升讀的吞吐量并且能夠顯著降低延時(shí)。

Lease?Read?基本思路是?Leader?取一個(gè)比?Election Timeout?小的租期（最好小一個(gè)數(shù)量級(jí)），在租約期內(nèi)不會(huì)發(fā)生選舉，確保?Leader?不會(huì)變化，所以跳過?ReadIndex?的第二步也就降低延時(shí)。由此可見?Lease?Read?的正確性和時(shí)間是掛鉤的，依賴本地時(shí)鐘的準(zhǔn)確性，因此雖然采用?Lease?Read?做法非常高效，但是仍然面臨風(fēng)險(xiǎn)問題，也就是存在預(yù)設(shè)的前提即各個(gè)服務(wù)器的?CPU Clock?的時(shí)間是準(zhǔn)的，即使有誤差，也會(huì)在一個(gè)非常小的?Bound?范圍里面，時(shí)間的實(shí)現(xiàn)至關(guān)重要，如果時(shí)鐘漂移嚴(yán)重，各個(gè)服務(wù)器之間?Clock?走的頻率不一樣，這套?Lease?機(jī)制可能出問題。

Lease?Read?實(shí)現(xiàn)方式包括：

定時(shí)?Heartbeat?獲得多數(shù)派響應(yīng)，確認(rèn)?Leader?的有效性；

在租約有效時(shí)間內(nèi)，可以認(rèn)為當(dāng)前?Leader?是?Raft?Group?內(nèi)的唯一有效?Leader，可忽略?ReadIndex?中的?Heartbeat?確認(rèn)步驟(2)；

Leader?等待自己的狀態(tài)機(jī)執(zhí)行，直到?applyIndex?超過?ReadIndex，這樣就能夠安全的提供?Linearizable?Read。

SOFAJRaft?采用?ReadIndex?替代走?Raft?狀態(tài)機(jī)的方案，簡(jiǎn)而言之是依靠?ReadIndex?原則直接從?Leader?讀取結(jié)果：所有已經(jīng)復(fù)制到多數(shù)派上的?Log（可視為寫操作）被視為安全的?Log，Leader?狀態(tài)機(jī)只要按照順序執(zhí)行到此條?Log之后，該?Log?所體現(xiàn)的數(shù)據(jù)就能對(duì)客戶端?Client?可見，具體分解為以下四個(gè)步驟：

Client?發(fā)起?Read?請(qǐng)求；

Leader?確認(rèn)最新復(fù)制到多數(shù)派的?LogIndex；

Leader?確認(rèn)身份；

在?LogIndex apply?后執(zhí)行?Read?操作。

通過?ReadIndex?優(yōu)化，SOFAJRaft?能夠達(dá)到?RPC?上限的 80%。上面的步驟中發(fā)現(xiàn)第 3 步仍然需要?Leader?通過向?Followers?發(fā)送心跳確認(rèn)自己的?Leader?身份，因?yàn)?Raft?集群中的?Leader?身份隨時(shí)可能發(fā)生改變。所以?SOFAJRaft?采用?Lease Read?的方式把第 3 步?RPC?省略掉。租約理解為?Raft?集群給?Leader?一段租期?Lease?的身份保證，在此期間不會(huì)剝奪?Leader?的身份，這樣當(dāng)?Leader?收到?Read?請(qǐng)求之后，如果發(fā)現(xiàn)租期尚未到期，無需再通過和?Followers?通信來確認(rèn)自己的?Leader?身份，這樣跳過第 3 步的網(wǎng)絡(luò)通信開銷。通過?Lease Read?優(yōu)化，SOFAJRaft?幾乎已經(jīng)能夠達(dá)到?RPC?的上限。然而通過時(shí)鐘維護(hù)租期本身并不是絕對(duì)的安全（時(shí)鐘漂移問題），所以?SOFAJRaft?默認(rèn)配置是線性一致讀，因?yàn)橥ǔＧ闆r下線性一致讀性能已足夠好。

默認(rèn)情況下，SOFAJRaft?提供的線性一致讀是基于?Raft?協(xié)議的?ReadIndex?實(shí)現(xiàn)，三副本的情況下?Leader?讀的吞吐接近于?RPC?的吞吐上限，延遲取決于多數(shù)派中最慢的一個(gè)?Heartbeat?Response。使用?Node#readIndex(byte?[]?requestContext,?ReadIndexClosure?done)?發(fā)起線性一致讀請(qǐng)求，當(dāng)安全讀取時(shí)傳入的?Closure?將被調(diào)用，正常情況下從狀態(tài)機(jī)中讀取數(shù)據(jù)返回給客戶端，?SOFAJRaft?將保證讀取的線性一致性。線性一致讀在任何集群內(nèi)的節(jié)點(diǎn)發(fā)起，并不需要強(qiáng)制要求放到?Leader?節(jié)點(diǎn)上，允許在?Follower?節(jié)點(diǎn)執(zhí)行，因此大大降低?Leader?的讀取壓力。

SOFAJRaft?基于?Raft?協(xié)議的?ReadIndex?線性一致讀實(shí)現(xiàn)是調(diào)用?RaftServerService#handleReadIndexRequest?接口根據(jù)當(dāng)前節(jié)點(diǎn)狀態(tài)為?STATE_LEADER，STATE_FOLLOWER?以及?STATE_TRANSFERRING?情況處理?ReadIndex?請(qǐng)求：

1、當(dāng)前節(jié)點(diǎn)狀態(tài)是?STATE_LEADER?即為?Leader?節(jié)點(diǎn)，接收?ReadIndex?請(qǐng)求調(diào)用?readLeader(request,?ReadIndexResponse.newBuilder(),?done)?方法提供線性一致讀：

檢查當(dāng)前?Raft?集群節(jié)點(diǎn)數(shù)量，如果集群只有一個(gè)?Peer?節(jié)點(diǎn)直接獲取投票箱?BallotBox?最新提交索引?lastCommittedIndex?即?Leader?節(jié)點(diǎn)當(dāng)前?Log?的?commitIndex?構(gòu)建?ReadIndexClosure?響應(yīng)；

日志管理器?LogManager?基于投票箱?BallotBox?的?lastCommittedIndex?獲取任期檢查是否等于當(dāng)前任期，如果不等于當(dāng)前任期表示此?Leader?節(jié)點(diǎn)未在其任期內(nèi)提交任何日志，需要拒絕只讀請(qǐng)求；

校驗(yàn)?Raft?集群節(jié)點(diǎn)數(shù)量以及?lastCommittedIndex?所屬任期符合預(yù)期，那么響應(yīng)構(gòu)造器設(shè)置其索引為投票箱?BallotBox?的?lastCommittedIndex，并且來自?Follower?的請(qǐng)求需要檢查?Follower?是否在當(dāng)前配置；

獲取?ReadIndex?請(qǐng)求級(jí)別?ReadOnlyOption?配置，ReadOnlyOption?參數(shù)默認(rèn)值為?ReadOnlySafe，ReadOnlySafe?通過與?Quorum?通信來保證只讀請(qǐng)求的可線性化。按照?ReadOnlyOption?配置為ReadOnlySafe?調(diào)用?Replicator#sendHeartbeat(rid,?closure) 方法向?Followers?節(jié)點(diǎn)發(fā)送?Heartbeat?心跳請(qǐng)求，發(fā)送心跳成功執(zhí)行?ReadIndexHeartbeatResponseClosure?心跳響應(yīng)回調(diào)；

ReadIndex?心跳響應(yīng)回調(diào)檢查是否超過半數(shù)節(jié)點(diǎn)包括?Leader?節(jié)點(diǎn)自身投票贊成，半數(shù)以上節(jié)點(diǎn)返回客戶端Heartbeat?請(qǐng)求成功響應(yīng)，即?applyIndex?超過?ReadIndex?說明已經(jīng)同步到?ReadIndex?對(duì)應(yīng)的?Log?能夠提供?Linearizable?Read。

2、當(dāng)前節(jié)點(diǎn)狀態(tài)是?STATE_FOLLOWER?即為?Follower?節(jié)點(diǎn)，接收?ReadIndex?請(qǐng)求通過?readFollower(request,??done)?方法支持線性一致讀：

檢查當(dāng)前?Leader?節(jié)點(diǎn)是否為空，如果?Leader?節(jié)點(diǎn)為空表示當(dāng)然任期沒有?Leader?節(jié)點(diǎn)；

Follower?節(jié)點(diǎn)調(diào)用?RpcService#readIndex(leaderId.getEndpoint(),?newRequest,?-1,?closure)?方法向?Leader?發(fā)送?ReadIndex?請(qǐng)求，Leader?節(jié)點(diǎn)調(diào)用?readIndex(requestContext,?done)?方法啟動(dòng)可線性化只讀查詢請(qǐng)求，只讀服務(wù)添加請(qǐng)求發(fā)布?ReadIndex?事件到隊(duì)列?readIndexQueue?即?Disruptor?的?Ring Buffer；

ReadIndex?事件處理器?ReadIndexEventHandler?通過?MPSC?Queue?模型攢批消費(fèi)觸發(fā)使用?executeReadIndexEvents(events) 執(zhí)行?ReadIndex?事件，輪詢?ReadIndex?事件封裝?ReadIndexState?狀態(tài)列表構(gòu)建?ReadIndexResponseClosure?響應(yīng)回調(diào)提交給?Leader?節(jié)點(diǎn)處理?ReadIndex?請(qǐng)求；

Leader?節(jié)點(diǎn)調(diào)用?handleReadIndexRequest(request,?readIndexResponseClosure) 方法進(jìn)行?readLeader?線性一致讀過程，返回投票箱?BallotBox?的?lastCommittedIndex。ReadIndex?響應(yīng)回調(diào)遍歷狀態(tài)列表記錄當(dāng)前提交日志?Index，檢查申請(qǐng)狀態(tài)機(jī)最新?Log Entry?的?committedIndex?是否已經(jīng)申請(qǐng)即比較狀態(tài)機(jī)?appliedIndex?是否大于等于當(dāng)前?committedIndex。由于?Leader?節(jié)點(diǎn)處理添加?Log Entry?請(qǐng)求發(fā)送心跳后投票箱?BallotBox?更新?lastCommittedIndex，當(dāng)?Leader?節(jié)點(diǎn)的?lastCommittedIndex?大于當(dāng)前的?lastCommittedIndex?就會(huì)創(chuàng)建提交?Log Entry?異步任務(wù)發(fā)布到?taskQueue?隊(duì)列，申請(qǐng)任務(wù)處理器?ApplyTaskHandler?執(zhí)行提交?LogEntry?申請(qǐng)任務(wù)，通知?Follower?節(jié)點(diǎn)最新申請(qǐng)的?committedIndex?已經(jīng)更新。如果當(dāng)前申請(qǐng)狀態(tài)機(jī)的?applyIndex?超過?ReadIndex，那么通知?ReadIndex?請(qǐng)求成功返回給客戶端。當(dāng)前?Follower?節(jié)點(diǎn)落后于?Leader?時(shí)把?Leader?節(jié)點(diǎn)返回的committedIndex?放到?pendingNotifyStatus?緩存等待?Leader?節(jié)點(diǎn)同步完日志更新?applyIndex。

SOFAJRaft?基于?Batch+Pipeline?Ack+ 全異步機(jī)制的?ReadIndex?核心邏輯：

SOFAJRaft?針對(duì)更高性能要求場(chǎng)景保證集群內(nèi)機(jī)器的?CPU?時(shí)鐘同步需求，采用?Clock+Heartbeat?的?Lease Read?優(yōu)化，通過服務(wù)端設(shè)置?RaftOptions?的?ReadOnlyOption?參數(shù)為?ReadOnlyLeaseBased?實(shí)現(xiàn)，ReadOnlyLeaseBased?通過依賴?Leader?租約確保只讀請(qǐng)求的可線性化，可能受時(shí)鐘漂移的影響。如果時(shí)鐘漂移無限制，Leader?節(jié)點(diǎn)可能保持租約長(zhǎng)于應(yīng)有的時(shí)間（時(shí)鐘可以向后移動(dòng)/暫停而沒有任何限制），此種情況下?ReadIndex?是不安全的。

SOFAJRaft?基于?Lease Read?線性一致讀實(shí)現(xiàn)是通過?Leader?節(jié)點(diǎn)調(diào)用?handleReadIndexRequest?接口接收?ReadIndex?請(qǐng)求獲取?ReadIndex?請(qǐng)求級(jí)別?ReadOnlyOption?配置，當(dāng)?ReadOnlyOption?配置為?ReadOnlyLeaseBased?時(shí)確認(rèn)?Leader?租約是否有效即檢查?Heartbeat?間隔是否小于?election?timeout?時(shí)間，Leader?租約超時(shí)需要轉(zhuǎn)變?yōu)?ReadIndex?模式。Leader?租約有效期間認(rèn)為當(dāng)前?Leader?是?Raft Group?內(nèi)的唯一有效?Leader，忽略?ReadIndex?發(fā)送?Heartbeat?確認(rèn)身份步驟，直接返回?Follower?節(jié)點(diǎn)和本地節(jié)點(diǎn) Read 請(qǐng)求成功響應(yīng)。Leader?節(jié)點(diǎn)繼續(xù)等待狀態(tài)機(jī)執(zhí)行，直到 applyIndex 超過?ReadIndex?安全提供?Linearizable?Read。

SOFAJRaft?基于時(shí)鐘和心跳實(shí)現(xiàn)的線性一致讀?Lease Read?優(yōu)化邏輯：

本文圍繞?Raft Log Read，ReadIndex Read?以及?Lease Read?線性一致讀實(shí)現(xiàn)細(xì)節(jié)方面剖析?SOFAJRaft?線性一致讀基本原理，闡述?SOFAJRaft?如何使用?Batch+Pipeline?Ack+全異步機(jī)制和?Clock+Heartbeat?手段優(yōu)化?ReadIndex?和?Lease Read?線性一致讀具體實(shí)現(xiàn)。

SOFAJRaft-RheaKV 是如何使用 Raft 的 | SOFAJRaft 實(shí)現(xiàn)原理

螞蟻金服生產(chǎn)級(jí) Raft 算法庫 SOFAJRaft 存儲(chǔ)模塊剖析 | SOFAJRaft 實(shí)現(xiàn)原理