SOFAStack
Scalable Open Financial Architecture Stack 是螞蟻金服自主研發的金融級分布式架構，包含了建構金融級雲原生架構所需的各個元件，是在金融場景裡錘煉出來的最佳實踐。
本文為《剖析 | SOFAJRaft 實作原理》第三篇，本篇作者米麒麟，來自陸金所。《剖析 | SOFAJRaft 實作原理》系列由 SOFA 團隊和源碼愛好者們出品，項目代号：，目前領取已經完成，感謝大家的參與。
SOFAJRaft 是一個基于 Raft 一緻性算法的生産級高性能 Java 實作，支援 MULTI-RAFT-GROUP，适用于高負載低延遲的場景。
SOFAJRaft ：
https://github.com/sofastack/sofa-jraft前言
線性一緻讀是在分布式系統中實作 Java volatile 語義，當用戶端向叢集發起寫操作的請求并且獲得成功響應之後，該寫操作的結果要對所有後來的讀請求可見。實作線性一緻讀正常手段是走 Raft 協定，将讀請求同樣按照 Log 處理，通過日志複制和狀态機執行擷取讀結果傳回給用戶端，SOFAJRaft 采用 ReadIndex 替代走 Raft 狀态機的方案。
本文将圍繞 Raft Log Read，ReadIndex Read 以及 Lease Read 等方面剖析線性一緻讀原理，闡述 SOFAJRaft 如何使用 ReadIndex 和 Lease Read 實作線性一緻讀：
- 什麼是線性一緻讀？共識算法隻能保證多個節點對某個對象的狀态是一緻的，以 Raft 為例隻能保證不同節點對 Raft Log 達成一緻，那麼 Log 後面的狀态機的一緻性呢？
- 基于 ReadIndex 和 Lease Read 方式 SOFAJRaft 如何實作高效的線性一緻讀？
線性一緻讀
什麼是線性一緻讀? 所謂線性一緻讀，一個簡單的例子是在 t1 的時刻我們寫入了一個值，那麼在 t1 之後，我們一定能讀到這個值，不可能讀到 t1 之前的舊值(想想 Java 中的 volatile 關鍵字，即線性一緻讀就是在分布式系統中實作 Java volatile 語義)。簡而言之是需要在分布式環境中實作 Java volatile 語義效果，即當 Client 向叢集發起寫操作的請求并且獲得成功響應之後，該寫操作的結果要對所有後來的讀請求可見。和 volatile 的差別在于 volatile 是實作線程之間的可見，而 SOFAJRaft 需要實作 Server 之間的可見。
如上圖 Client A、B、C、D 均符合線性一緻讀，其中 D 看起來是 Stale Read，其實并不是，D 請求橫跨 3 個階段，而 Read 可能發生在任意時刻，是以讀到 1 或 2 都行。
Raft Log read
實作線性一緻讀最正常的辦法是走 Raft 協定，将讀請求同樣按照 Log 處理，通過 Log 複制和狀态機執行來擷取讀結果，然後再把讀取的結果傳回給 Client。因為 Raft 本來就是一個為了實作分布式環境下線性一緻性的算法，是以通過 Raft 非常友善的實作線性 Read，也就是将任何的讀請求走一次 Raft Log，等此 Log 送出之後在 apply 的時候從狀态機裡面讀取值，一定能夠保證這個讀取到的值是滿足線性要求的。
當然，因為每次 Read 都需要走 Raft 流程，Raft Log 存儲、複制帶來刷盤開銷、存儲開銷、網絡開銷，走 Raft Log不僅僅有日志落盤的開銷，還有日志複制的網絡開銷，另外還有一堆的 Raft “讀日志” 造成的磁盤占用開銷，導緻 Read 操作性能是非常低效的，是以在讀操作很多的場景下對性能影響很大，在讀比重很大的系統中是無法被接受的，通常都不會使用。
在 Raft 裡面，節點有三個狀态：Leader，Candidate 和 Follower，任何 Raft 的寫入操作都必須經過 Leader，隻有 Leader 将對應的 Raft Log 複制到 Majority 的節點上面認為此次寫入是成功的。是以如果目前 Leader 能确定一定是 Leader，那麼能夠直接在此 Leader 上面讀取資料，因為對于 Leader 來說，如果确認一個 Log 已經送出到大多數節點，在 t1 的時候 apply 寫入到狀态機，那麼在 t1 後的 Read 就一定能讀取到這個新寫入的資料。
那麼如何确認 Leader 在處理這次 Read 的時候一定是 Leader 呢？在 Raft 論文裡面，提到兩種方法：
- ReadIndex Read
- Lease Read
第一種是 ReadIndex Read，當 Leader 需要處理 Read 請求時，Leader 與過半機器交換心跳資訊确定自己仍然是 Leader 後可提供線性一緻讀：
Leader 将自己目前 Log 的 commitIndex 記錄到一個 Local 變量 ReadIndex 裡面；
接着向 Followers 節點發起一輪 Heartbeat，如果半數以上節點傳回對應的 Heartbeat Response，那麼 Leader就能夠确定現在自己仍然是 Leader；
Leader 等待自己的 StateMachine 狀态機執行，至少應用到 ReadIndex 記錄的 Log，直到 applyIndex 超過 ReadIndex，這樣就能夠安全提供 Linearizable Read，也不必管讀的時刻是否 Leader 已飄走；
Leader 執行 Read 請求，将結果傳回給 Client。
使用 ReadIndex Read 提供 Follower Read 的功能，很容易在 Followers 節點上面提供線性一緻讀，Follower 收到 Read 請求之後：
Follower 節點向 Leader 請求最新的 ReadIndex；
Leader 仍然走一遍之前的流程，執行上面前 3 步的過程(确定自己真的是 Leader)，并且傳回 ReadIndex 給 Follower；
Follower 等待目前的狀态機的 applyIndex 超過 ReadIndex；
Follower 執行 Read 請求，将結果傳回給 Client。
不同于通過 Raft Log 的 Read，ReadIndex Read 使用 Heartbeat 方式來讓 Leader 确認自己是 Leader，省去 Raft Log 流程。相比較于走 Raft Log 方式，ReadIndex Read 省去磁盤的開銷，能夠大幅度提升吞吐量。雖然仍然會有網絡開銷，但是 Heartbeat 本來就很小，是以性能還是非常好的。
雖然 ReadIndex Read 比原來的 Raft Log Read 快很多，但畢竟還是存在 Heartbeat 網絡開銷，是以考慮做更進一步的優化。Raft 論文裡面提及一種通過 Clock + Heartbeat 的 Lease Read 優化方法，也就是 Leader 發送 Heartbeat 的時候首先記錄一個時間點 Start，當系統大部分節點都回複 Heartbeat Response，由于 Raft 的選舉機制，Follower 會在 Election Timeout 的時間之後才重新發生選舉，下一個 Leader 選舉出來的時間保證大于 Start+Election Timeout/Clock Drift Bound，是以可以認為 Leader 的 Lease 有效期可以到 Start+Election Timeout/Clock Drift Bound 時間點。Lease Read 與 ReadIndex 類似但更進一步優化，不僅節省 Log，而且省掉網絡互動，大幅提升讀的吞吐量并且能夠顯著降低延時。
Lease Read 基本思路是 Leader 取一個比 Election Timeout 小的租期（最好小一個數量級），在租約期内不會發生選舉，確定 Leader 不會變化，是以跳過 ReadIndex 的第二步也就降低延時。由此可見 Lease Read 的正确性和時間是挂鈎的，依賴本地時鐘的準确性，是以雖然采用 Lease Read 做法非常高效，但是仍然面臨風險問題，也就是存在預設的前提即各個伺服器的 CPU Clock 的時間是準的，即使有誤差，也會在一個非常小的 Bound 範圍裡面，時間的實作至關重要，如果時鐘漂移嚴重，各個伺服器之間 Clock 走的頻率不一樣，這套 Lease 機制可能出問題。
Lease Read 實作方式包括：
定時 Heartbeat 獲得多數派響應，确認 Leader 的有效性；
在租約有效時間内，可以認為目前 Leader 是 Raft Group 内的唯一有效 Leader，可忽略 ReadIndex 中的 Heartbeat 确認步驟(2)；
Leader 等待自己的狀态機執行，直到 applyIndex 超過 ReadIndex，這樣就能夠安全的提供 Linearizable Read。
SOFAJRaft 線性一緻讀實作
SOFAJRaft 采用 ReadIndex 替代走 Raft 狀态機的方案，簡而言之是依靠 ReadIndex 原則直接從 Leader 讀取結果：所有已經複制到多數派上的 Log（可視為寫操作）被視為安全的 Log，Leader 狀态機隻要按照順序執行到此條 Log之後，該 Log 所展現的資料就能對用戶端 Client 可見，具體分解為以下四個步驟：
Client 發起 Read 請求；
Leader 确認最新複制到多數派的 LogIndex；
Leader 确認身份；
在 LogIndex apply 後執行 Read 操作。
通過 ReadIndex 優化，SOFAJRaft 能夠達到 RPC 上限的 80%。上面的步驟中發現第 3 步仍然需要 Leader 通過向 Followers 發送心跳确認自己的 Leader 身份，因為 Raft 叢集中的 Leader 身份随時可能發生改變。是以 SOFAJRaft 采用 Lease Read 的方式把第 3 步 RPC 省略掉。租約了解為 Raft 叢集給 Leader 一段租期 Lease 的身份保證，在此期間不會剝奪 Leader 的身份，這樣當 Leader 收到 Read 請求之後，如果發現租期尚未到期，無需再通過和 Followers 通信來确認自己的 Leader 身份，這樣跳過第 3 步的網絡通信開銷。通過 Lease Read 優化，SOFAJRaft 幾乎已經能夠達到 RPC 的上限。然而通過時鐘維護租期本身并不是絕對的安全（時鐘漂移問題），是以 SOFAJRaft 預設配置是線性一緻讀，因為通常情況下線性一緻讀性能已足夠好。
ReadIndex Read 實作
預設情況下，SOFAJRaft 提供的線性一緻讀是基于 Raft 協定的 ReadIndex 實作，三副本的情況下 Leader 讀的吞吐接近于 RPC 的吞吐上限，延遲取決于多數派中最慢的一個 Heartbeat Response。使用
Node#readIndex(byte [] requestContext, ReadIndexClosure done) 發起線性一緻讀請求，當安全讀取時傳入的 Closure 将被調用，正常情況下從狀态機中讀取資料傳回給用戶端， SOFAJRaft 将保證讀取的線性一緻性。線性一緻讀在任何叢集内的節點發起，并不需要強制要求放到 Leader 節點上，允許在 Follower 節點執行，是以大大降低 Leader 的讀取壓力。
RaftServerService#handleReadIndexRequest 接口根據目前節點狀态為 STATE_LEADER，STATE_FOLLOWER 或者 STATE_TRANSFERRING 情況處理 ReadIndex 請求：
1、目前節點狀态是 STATE_LEADER 即為 Leader 節點，接收 ReadIndex 請求調用 readLeader(request, ReadIndexResponse.newBuilder(), done) 方法提供線性一緻讀：
- 檢查目前 Raft 叢集節點數量，如果叢集隻有一個 Peer 節點直接擷取投票箱 BallotBox 最新送出索引 lastCommittedIndex 即 Leader 節點目前 Log 的 commitIndex 建構 ReadIndexClosure 響應；
- 日志管理器 LogManager 基于投票箱 BallotBox 的 lastCommittedIndex 擷取任期檢查是否等于目前任期，如果不等于目前任期表示此 Leader 節點未在其任期内送出任何日志，需要拒絕隻讀請求；
- 校驗 Raft 叢集節點數量以及 lastCommittedIndex 所屬任期符合預期，那麼響應構造器設定其索引為投票箱 BallotBox 的 lastCommittedIndex，并且來自 Follower 的請求需要檢查 Follower 是否在目前配置；
- 擷取 ReadIndex 請求級别 ReadOnlyOption 配置，ReadOnlyOption 參數預設值為 ReadOnlySafe，ReadOnlySafe 通過與 Quorum 通信來保證隻讀請求的可線性化。按照 ReadOnlyOption 配置為ReadOnlySafe 調用 Replicator#sendHeartbeat(rid, closure) 方法向 Followers 節點發送 Heartbeat 心跳請求，發送心跳成功執行 ReadIndexHeartbeatResponseClosure 心跳響應回調；
- ReadIndex 心跳響應回調檢查是否超過半數節點包括 Leader 節點自身投票贊成，半數以上節點傳回用戶端Heartbeat 請求成功響應，即 applyIndex 超過 ReadIndex 說明已經同步到 ReadIndex 對應的 Log 能夠提供 Linearizable Read。
2、目前節點狀态是 STATE_FOLLOWER 即為 Follower 節點，接收 ReadIndex 請求通過 readFollower(request, done) 方法支援線性一緻讀：
- 檢查目前 Leader 節點是否為空，如果 Leader 節點為空表示當然任期沒有 Leader 節點；
- Follower 節點調用 - RpcService#readIndex(leaderId.getEndpoint(), newRequest, -1, closure) 方法向 Leader 發送 ReadIndex 請求，Leader 節點調用 readIndex(requestContext, done) 方法啟動可線性化隻讀查詢請求，隻讀服務添加請求釋出 ReadIndex 事件到隊列 readIndexQueue 即 Disruptor 的 Ring Buffer；
- ReadIndex 事件處理器 ReadIndexEventHandler 通過 MPSC Queue 模型攢批消費觸發使用 executeReadIndexEvents(events) 執行 ReadIndex 事件，輪詢 ReadIndex 事件封裝 ReadIndexState 狀态清單建構 ReadIndexResponseClosure 響應回調送出給 Leader 節點處理 ReadIndex 請求；
- Leader 節點調用 handleReadIndexRequest(request, readIndexResponseClosure) 方法進行 readLeader 線性一緻讀過程，傳回投票箱 BallotBox 的 lastCommittedIndex。ReadIndex 響應回調周遊狀态清單記錄目前送出日志 Index，檢查申請狀态機最新 Log Entry 的 committedIndex 是否已經申請即比較狀态機 appliedIndex 是否大于等于目前 committedIndex。由于 Leader 節點處理添加 Log Entry 請求發送心跳後投票箱 BallotBox 更新 lastCommittedIndex，當 Leader 節點的 lastCommittedIndex 大于目前的 lastCommittedIndex 就會建立送出 Log Entry 異步任務釋出到 taskQueue 隊列，申請任務處理器 ApplyTaskHandler 執行送出 LogEntry 申請任務，通知 Follower 節點最新申請的 committedIndex 已經更新。如果目前申請狀态機的 applyIndex 超過 ReadIndex，那麼通知 ReadIndex 請求成功傳回給用戶端。目前 Follower 節點落後于 Leader 時把 Leader 節點傳回的committedIndex 放到 pendingNotifyStatus 緩存等待 Leader 節點同步完日志更新 applyIndex。
SOFAJRaft 基于 Batch+Pipeline Ack+ 全異步機制的 ReadIndex 核心邏輯：
Lease Read 實作
SOFAJRaft 針對更高性能要求場景保證叢集内機器的 CPU 時鐘同步需求，采用 Clock+Heartbeat 的 Lease Read 優化，通過設定 RaftOptions 的 ReadOnlyOption 參數為 ReadOnlyLeaseBased 實作，ReadOnlyLeaseBased 通過依賴 Leader 租約確定隻讀請求的可線性化，可能受時鐘漂移的影響。如果時鐘漂移無限制，Leader 節點可能保持租約長于應有的時間（時鐘可以向後移動/暫停而沒有任何限制），此種情況下 ReadIndex 是不安全的。
SOFAJRaft 基于 Lease Read 線性一緻讀實作是通過 Leader 節點調用 handleReadIndexRequest 接口接收 ReadIndex 請求擷取 ReadIndex 請求級别 ReadOnlyOption 配置，當 ReadOnlyOption 配置為 ReadOnlyLeaseBased 時确認 Leader 租約是否有效即檢查 Heartbeat 間隔是否小于 election timeout 時間，Leader 租約逾時需要轉變為 ReadIndex 模式。Leader 租約有效期間認為目前 Leader 是 Raft Group 内的唯一有效 Leader，忽略 ReadIndex 發送 Heartbeat 确認身份步驟，直接傳回 Follower 節點和本地節點 Read 請求成功響應。Leader 節點繼續等待狀态機執行，直到 applyIndex 超過 ReadIndex 安全提供 Linearizable Read。
SOFAJRaft 基于時鐘和心跳實作的線性一緻讀 Lease Read 優化邏輯：
總結
本文圍繞 Raft Log Read，ReadIndex Read 以及 Lease Read 線性一緻讀實作細節方面剖析 SOFAJRaft 線性一緻讀基本原理，闡述 SOFAJRaft 如何使用 Batch+Pipeline Ack+全異步機制和 Clock+Heartbeat 手段優化 ReadIndex 和 Lease Read 線性一緻讀具體實作。