什麼是日誌複製狀態機？

2021-08-08 03:02:32

在電腦科學領域，狀態機複製或狀態機方法是實現容錯服務的一種常規方法，主要通過複製伺服器，並協調客戶端和這些伺服器映象間的互動來達到目標。這個方法也同時提供了理解和設計複製管理協議的一套基本框架。

日誌複製狀態機，也叫複製狀態機，是分散式資料庫領域最重要的基石之一. 當前市面上所有實用的分散式資料庫，幾乎都是用日誌複製狀態機技術來實現多副本. 像 MySQL 的主從同步， Redis 的主從同步等，是大家非常熟知日誌複製狀態機的例子. 而更復雜的共識演算法 Paxos, 以及最流行的分散式一致性協議 Raft, 前者的實現基本離不開日誌複製狀態機，後者則是直接以日誌複製狀態機作為其核心組成.

那麼，什麼是日誌複製狀態機呢？首先，我們先理解什麼 狀態機 . 狀態機基於一個定理，這個定理是顯然的，不需要證明的. 那就是，如果兩個被稱為狀態機的物件，它們按相同的順序執行(Apply)相同的指令序列，那麼，指令執行完畢後，這兩個狀態機的狀態將必然是相同的(一致的).

指令序列也稱為 日誌序列 , 一般每一條日誌帶有一個唯一整數編號以確定順序. 如果日誌序列被複制到不同的地方，然後由狀態機執行，那麼分佈在不同地方的狀態機的狀態就一致了. 這種技術便稱為日誌複製狀態機. 狀態機物件便是一個副本，例如是一個數據庫例項.

注意，按順序執行指令序列，也即序列化執行指令，是狀態機的必要屬性，一旦違反此規定，便不可稱為日誌複製狀態機，也無法保證狀態必然一致. 另外, 既然是序列 , 那就是 連續的 , 離散的多條日誌不構成日誌序列.

使用日誌複製狀態機技術的系統，其內部結構大同小異，基本都如圖所示：

一次請求處理的完整流程是：

主節點(Leader)收到客戶端請求(Request)
主節點往日誌序列末尾追加(Append)一條日誌(Log Entry)
主節點將日誌複製(Replicate)給所有從節點(Follower)
主節點計算公式結果(Consensus), 並確認(Commit)
主節點將確認結果通知(Broadcast)給所有從節點
對於已確認的日誌序列，所有節點的狀態機按順序執行(Apply)
主節點將狀態機執行的結果返回給客戶端(Response)

注意，在工程實踐上， 5 和 6 一般是"併發執行"的.

日誌複製狀態機在實踐上遇到的第一個問題是，由哪個節點來追加日誌到日誌序列中？經典的主從同步架構，由人來指定主節點，只有主節點才能追加日誌. Paxos 是另一個極端，理論上在追加每一條日誌前，每一個節點需要先和其它節點協商(選主), 選出的節點作為"主"節點，追加日誌.

一條日誌是否達成共識，需要主節點根據與所有從節點通訊交換資訊之後進行計算才能發現，例如對於多數派共識演算法，超過半數節點擁有一條日誌即表示達成共識. 主節點計算得出結果之後，把共識結果廣播給所有從節點.

一種正確的共識演算法，應該能及時發現共識，同時，如果確實沒有達成(穩定的)共識則不能報假. 例如，某些錯誤的共識演算法，在不同的時間會計算出不同的共識結果，這顯然是不行的.

什麼是日誌複製狀態機？

熱門文章