紀錄工作經驗、相關知識,解決技術相關問題。

資訊相關

Raft 成員變更、日誌壓縮與唯讀請求怎麼處理?

Raft 成員變更、日誌壓縮與唯讀請求怎麼處理? 特色圖片

Raft 成員變更、日誌壓縮與唯讀請求,是把核心演算法做成實際系統時一定會碰到的三件事。先給結論:

  • 成員變更:不能讓每台伺服器各自直接從舊設定換成新設定,否則可能同時出現兩組過半數。做法有兩種:一次只增減一台(博士論文的單節點變更),或先經過 joint consensus 過渡設定(原始論文)。
  • 日誌壓縮:每台伺服器各自把已 committed 的部分寫成 snapshot,再刪掉被涵蓋的 log;落後太多的 follower 由 leader 用 InstallSnapshot 補上。
  • 唯讀請求:可以不寫進 log,但 leader 讀之前必須先確認自己沒被取代(ReadIndex,與過半數交換心跳),或改靠時鐘租約(lease read),後者的安全性要靠時間假設。

Leader Election、Log Replication 與 quorum 的基本概念請先看Raft 共識演算法主篇。本文以 Raft 原始論文與 Diego Ongaro 的博士論文為主,etcd 的文件與 Raft 函式庫當作實作對照。

Raft 成員變更:一次只動一台,或先過 joint consensus

成員變更指叢集的伺服器名單(論文稱為 configuration,設定)改變,例如換掉壞機器、增加或減少複製份數。

為什麼不能直接切換

各台伺服器不可能在同一瞬間改用新設定。如果各自直接切換,中間會出現舊設定的過半數與新設定的過半數互不重疊,同一個 term 就可能選出兩個 leader。論文的 Figure 10 用三台擴成五台說明這個情況。

用數字看更清楚:三台的過半數是 2 台,五台的過半數是 3 台,2 加 3 剛好等於 5,所以 S1、S2 與 S3、S4、S5 可以各自湊成過半數且完全不重疊。三台變四台時,2 加 3 等於 5,大於 4 台,兩組過半數一定有交集。

下面這支 Node.js 腳本把舊、新設定各自所有的過半數組合列出來,逐一檢查有沒有不重疊的組合:

// 列舉舊、新設定各自所有「過半數」子集合,檢查任兩組是否一定有交集
function majorities(servers) {
  const need = Math.floor(servers.length / 2) + 1;
  const result = [];
  for (let mask = 1; mask < 1 << servers.length; mask++) {
    const subset = servers.filter((_, i) => mask & (1 << i));
    if (subset.length >= need) result.push(subset);
  }
  return result;
}

function checkOverlap(oldCfg, newCfg) {
  for (const a of majorities(oldCfg)) {
    for (const b of majorities(newCfg)) {
      if (!a.some((s) => b.includes(s))) return { ok: false, a, b };
    }
  }
  return { ok: true };
}

const S = (n) => Array.from({ length: n }, (_, i) => `S${i + 1}`);
const cases = [
  ['3 台 → 4 台(加 1 台)', 3, 4],
  ['4 台 → 3 台(減 1 台)', 4, 3],
  ['4 台 → 5 台(加 1 台)', 4, 5],
  ['5 台 → 4 台(減 1 台)', 5, 4],
  ['3 台 → 5 台(一次加 2 台)', 3, 5],
];

for (const [label, from, to] of cases) {
  const r = checkOverlap(S(from), S(to));
  console.log(
    r.ok
      ? `${label}:任兩組過半數一定有交集`
      : `${label}:可能出現不重疊的兩組過半數,例如 [${r.a}] 與 [${r.b}]`
  );
}

以 Node.js v22 執行的輸出如下:

3 台 → 4 台(加 1 台):任兩組過半數一定有交集
4 台 → 3 台(減 1 台):任兩組過半數一定有交集
4 台 → 5 台(加 1 台):任兩組過半數一定有交集
5 台 → 4 台(減 1 台):任兩組過半數一定有交集
3 台 → 5 台(一次加 2 台):可能出現不重疊的兩組過半數,例如 [S1,S2] 與 [S3,S4,S5]

只增減一台時,新舊設定的過半數一定重疊;一次改兩台以上就可能不重疊。這正是下面兩種做法的分界。

做法一:單節點變更

博士論文提出的較簡單做法,是限制每次只能新增或移除一台伺服器;要做大幅度的調整,就拆成一連串的單節點變更。因為過半數一定重疊,新設定可以直接生效,不需要過渡階段。

流程如下:

  1. leader 收到變更請求後,把新設定(Cnew)當成一筆特殊的 log entry,用一般的複製機制送出去。
  2. 每台伺服器只要把這筆設定寫進自己的 log,就開始用它,不必等它 committed;判斷 Cnew 這筆 entry 有沒有過半數,也用新設定來算。
  3. Cnew entry committed 後,變更才算完成:leader 可以回報成功,被移除的伺服器可以關機,下一次變更也可以開始。

在上一筆設定 committed 之前,不可以開始下一筆,否則重疊的變更可能回到前面那種不安全的情況。另外,這筆設定 entry 有可能因為換 leader 被丟掉,所以伺服器要能退回 log 裡更早的那一份設定。

做法二:joint consensus

原始論文的做法適用於一次改變任意台數。它分成兩個階段:叢集先切換到一個同時包含新舊設定的過渡設定,論文稱為 joint consensus(Cold,new);這筆過渡設定 committed 之後,再切換到新設定(Cnew)。

過渡期間的規則有三條:

  • log entry 要複製給新舊兩個設定裡的所有伺服器。
  • 新舊設定裡的任何一台伺服器都可以當 leader。
  • 選舉與 commit 都要分別取得舊設定與新設定各自的過半數。博士論文舉的例子:從 3 台換成 9 台時,需要舊設定 3 台中的 2 台,以及新設定 9 台中的 5 台。

過渡設定 committed 之後,舊設定與新設定都不能單獨做決定,而且只有持有這筆過渡設定的伺服器才可能當選 leader,所以這時 leader 可以放心送出 Cnew。Cnew 依新設定的過半數 committed 之後,舊設定就不再有作用,不在新設定裡的伺服器可以關掉。整個過程中,沒有任何時間點讓新舊設定各自獨立決定,叢集也可以持續處理用戶端請求。

示意圖:會議桌中央有一道打開的木閘門,左側擺藍色代幣、右側擺綠色代幣,各有部分代幣立起
圖:過渡期間,新舊兩組都同意,閘門才會打開

兩種做法怎麼選

項目單節點變更joint consensus
一次可改幾台1 台任意台數
過渡階段沒有,新設定直接生效有,先 Cold,new 再 Cnew
判斷過半數的方式只看目前這份設定新舊兩份設定要各自過半數
實作複雜度較簡單較複雜,投票與 commit 的判斷都要改

博士論文把 joint consensus 當作為了完整性才保留的原始做法,並明講知道單節點做法之後,建議採用單節點變更,理由是實務系統用一連串單節點變更就能達到想要的任何設定。

成員變更的三個實務問題

論文與博士論文另外處理三個會影響可用性的狀況:

  1. 新伺服器的 log 是空的:直接加進來的話,要追上進度需要一段時間,期間可能無法 commit 新的 entry。做法是先讓新伺服器以不投票成員的身分加入,leader 把 log 複製給它,但不把它算進過半數;追上之後才進行設定變更。
  2. leader 不在新設定裡:leader 要等 Cnew committed 之後才退回 follower。在這段期間,它管理的是一個不含自己的叢集:照常複製 entry,但不把自己算進過半數。
  3. 被移除的伺服器擾亂叢集:被移除的伺服器收不到心跳,會逾時並發起選舉,帶著更大的 term 逼目前的 leader 退位。解法是讓伺服器在距離上次聽到現任 leader 的時間還沒超過最小 election timeout 時,收到 RequestVote 就不更新 term、也不投票。

etcd 與它的 Raft 函式庫怎麼做

etcd 的官方文件(v3.6)說明,叢集成員的變更必須依序進行:從 3 台增加到 5 台要做兩次新增,從 5 台減少到 3 台要做兩次移除。文件也建議加入新成員時,先以 learner(不投票成員)身分加入,等它的 Raft log 追上 leader 之後再升級為投票成員;還沒追上就要求升級,請求會失敗。

etcd 使用的 Raft 函式庫(etcd-io/raft)在設定變更的訊息中,同時支援一次一台的簡單做法與 joint consensus。預設的轉換模式會在能用簡單做法時就用,其餘情況才使用 joint consensus。

補充說明:這個函式庫的 README 指出,它的設定變更是在 entry 被「套用」(applied)到狀態機時才生效,而不是像論文那樣寫進 log 就生效;README 的說法是因為新舊設定保證有重疊,所以在安全性上等價。要在自己的系統接這個函式庫時,這個差異需要注意。

日誌壓縮:snapshot 與 InstallSnapshot

Raft 的 log 會隨著用戶端請求一直變長。論文指出實際系統不能讓它無限成長:log 越長,佔用的空間越多,重新啟動時重播也越花時間,最後會影響可用性。

snapshot 裡面有什麼

快照(snapshot)是最簡單的做法:把狀態機目前的完整狀態寫到穩定儲存,然後丟棄到那個位置為止的整段 log。論文提到 Chubby 與 ZooKeeper 也用快照。

快照除了狀態機的狀態,還附帶三項中繼資料:

  • last included index:快照取代的最後一筆 log entry 的 index。
  • last included term:那筆 entry 的 term。這兩項是為了讓快照之後第一筆 entry 仍能通過 AppendEntries 的一致性檢查,因為那筆 entry 需要前一筆的 index 與 term。
  • 最新的叢集設定:截至 last included index 的設定,讓成員變更在快照之後仍然成立。

伺服器寫完快照後,就可以刪除到 last included index 為止的所有 log entry,以及更早的舊快照。

每台伺服器各自做快照

每台伺服器獨立做快照,而且只涵蓋已 committed 的 entry。這稍微偏離了 Raft 的強 leader 原則,因為 follower 不需要 leader 同意就能做快照。論文認為這樣合理:做快照時共識已經達成,不會有決定互相衝突,資料仍然只從 leader 流向 follower,只是 follower 可以自己整理手上的資料。

論文也考慮過只讓 leader 做快照、再送給每個 follower 的做法,但有兩個缺點:把快照送給每個 follower 會浪費網路頻寬並拖慢快照;leader 的實作也更複雜,因為它得一邊送快照、一邊繼續複製新 entry,不能擋住新的用戶端請求。

InstallSnapshot:補上落後太多的 follower

多數時候 follower 跟得上 leader,不需要收快照。但 leader 可能已經丟掉某個 follower 還需要的下一筆 entry,例如這個 follower 慢得特別多,或是剛加入叢集的新伺服器。這時 leader 改用 InstallSnapshot 這個 RPC,把快照分成多個區塊(chunk)依序送給它。

論文 Figure 13 列出的參數如下:

參數意思
term、leaderIdleader 的 term 與 ID,讓 follower 可以轉導用戶端
lastIncludedIndex、lastIncludedTerm快照取代的最後一筆 entry 的 index 與 term
offset、data[]這個區塊在快照檔中的位置與原始位元組
done是否為最後一個區塊

follower 收到快照後,要決定怎麼處理自己現有的 log:

  • 快照含有新資訊(通常如此):follower 丟掉整份 log,因為已被快照取代,而且可能有與快照衝突的未 committed entry;再用快照的內容重設狀態機。
  • 快照只是它 log 的前一段(因重送或誤送):被快照涵蓋的 entry 刪掉,快照之後的 entry 仍然有效,必須保留。

論文也說明,快照分區塊傳送,是為了讓 follower 每收到一塊就有一個「還活著」的訊號,可以重設自己的 election timer。

示意圖:輸送帶把一本厚書從堆滿帳冊的辦公桌送往只有幾張散頁的辦公桌,比喻快照取代落後的 log
圖:落後太多的 follower 直接收一份快照

什麼時候做快照

論文列出兩個影響效能的問題:

  1. 什麼時候做:太頻繁會浪費磁碟頻寬與電力,太少則可能把儲存空間用完,而且重新啟動後重播 log 的時間更長。簡單的策略是 log 達到固定的位元組大小就做快照;把這個大小設得比預期的快照大得多,快照的磁碟頻寬負擔就會很小。
  2. 寫快照會不會卡住正常運作:寫快照可能花不少時間。解法是用 copy-on-write 技術,讓新的更新在快照寫入期間仍能進來。例如用 functional data structure 實作的狀態機天然支援;也可以用作業系統的 copy-on-write(例如 Linux 的 fork),論文的實作就採用這種做法。

論文另外提到 log cleaning、LSM tree 這類漸進式的壓縮方式,每次只處理一部分資料,但機制比快照複雜;快照每次處理整份資料,所以較單純。

補充說明:etcd 的 Raft 函式庫把 log compaction 列在功能清單裡。它的內部文件描述,leader 在取不到要送給某個 follower 的 term 或 entry 時,會改送 MsgSnap 訊息請對方安裝快照,對應論文裡的 InstallSnapshot。

唯讀請求:怎麼確保讀到最新的資料

問題在哪裡

唯讀請求只查詢狀態機、不改變它,所以可以不寫進 log。這樣省掉同步寫入磁碟的時間,效能比較好;但如果沒有額外措施,可能讀到舊資料。

舉例來說,leader 被網路分割到少數那一邊,多數那邊已經選出新 leader 並 commit 了新的 entry。被隔開的舊 leader 如果不問其他伺服器就直接回答讀取,回傳的是舊結果。這種結果不滿足線性一致性(linearizability,每次讀取都必須看到最新已 committed 的寫入),只能算是較弱的 serializability。

ReadIndex:與過半數確認後再讀

博士論文描述的做法,讓 leader 在不寫 log 的情況下仍保持線性一致性,步驟如下:

  1. 如果 leader 還沒有任何屬於目前 term 的 entry committed,就先等。為此 Raft 讓每個 leader 在 term 開始時,先 commit 一筆空白的 no-op entry;它 committed 之後,leader 的 commit index 就不會比其他伺服器的小。
  2. leader 把目前的 commit index 存成區域變數 readIndex,當作這次讀取所依據的狀態的下限。
  3. leader 發出新一輪心跳,等過半數伺服器回應。收到後,它就知道心跳送出的那一刻不存在 term 更大的 leader,所以 readIndex 當時是整個叢集見過最大的 commit index。
  4. leader 等自己的狀態機套用到至少 readIndex 的位置。
  5. leader 對狀態機執行查詢,並把結果回給用戶端。

這比把讀取也當成 log entry 複製更有效率,因為省掉同步寫磁碟。leader 還可以用同一輪心跳來確認多個累積的讀取請求,攤平成本。

follower 也可以分擔讀取:follower 向 leader 要一個目前的 readIndex(leader 執行上面的步驟 1 到 3),之後在自己的狀態機執行步驟 4 與 5。etcd 的 Raft 函式庫 README 列出的功能也包含這種由 leader 與 follower 都能處理的線性一致讀取:follower 先向 leader 取得安全的 read index。

示意圖:機房中一座亮綠燈的檢查站連著一排伺服器,左側是排隊的請求卡片,比喻 leader 先與過半數確認再回應讀取
圖:讀取前先向伺服器確認,檢查站才放行

Lease read:用時鐘省掉心跳

另一種做法是靠時鐘而不是訊息。leader 的心跳被過半數伺服器確認後,可以假設在大約一個 election timeout(博士論文的圖示還要依時鐘漂移上限折算)內,不會有其他伺服器成為 leader,這段租約期間就能直接回答讀取,完全不需要通訊。

代價是它要假設各台伺服器的時鐘漂移有上限。博士論文指出,要找出並維持這個上限在實務上不容易,例如垃圾回收暫停、虛擬機遷移、時鐘速率調整都可能破壞它;一旦假設不成立,系統可能回傳任意舊的資訊。所以博士論文不建議使用,除非效能需求真的需要。

做法讀取時要與過半數通訊嗎安全性依賴
讀取也當成 log entry 複製要,走完整的複製流程不依賴時間
ReadIndex要,一輪心跳,可由多個讀取共用不依賴時間
Lease read不用時鐘漂移有上限

etcd 的 Raft 函式庫把這兩種做法做成設定:ReadOnlySafe 是預設,也是函式庫建議的選項,靠與過半數通訊來保證線性一致性;ReadOnlyLeaseBased 則依賴 leader 租約,會受時鐘漂移影響,而且啟用時必須同時開啟 CheckQuorum。

實際系統的取捨

etcd 的 API 保證文件說明,預設所有其他操作都是線性一致的,代價是這類請求必須經過 Raft 共識流程;要取得較低延遲與較高吞吐量,用戶端可以把讀取的一致性模式設為 serializable,但可能讀到相對於過半數而言的舊資料。這個取捨與論文討論的是同一件事:要不要為了新鮮度付出與過半數通訊的代價。

補充說明:寫入也有類似但不同的問題。leader 可能在 commit 一筆指令之後、回覆用戶端之前當機,用戶端重試會讓同一個指令被執行兩次。論文的解法是讓用戶端替每個指令附上唯一序號,狀態機記錄每個用戶端最後處理的序號與回應,遇到重複的序號就直接回覆先前的結果,不再執行。

參考資料與延伸閱讀

發佈留言