在計算機科學領域，狀態機複製或狀態機方法是實現容錯服務的一種常規方法，主要通過複製伺服器，並協調客戶端和這些伺服器鏡像間的互動來達到目標。這個方法也同時提供了理解和設計複製管理協定的一套基本框架。
基本介紹
- 中文名：狀態機複製
- 外文名：State Machine Replication
- 方法：實現容錯服務的一種常規方法
- 套用：計算機科學領域
- 學科：信息工程
歷史背景,問題定義,分散式服務,狀態機,容錯,狀態機方法,
歷史背景
Leslie Lamport在1984年發表的關於“在分散式系統中使用時間而不是逾時”的論文中首次提出了狀態機方法。弗雷德·施耐德（Fred Schneider）後來在他的論文“使用狀態機方法實現容錯服務：教程”中闡述了這種方法。
Ken Birman在1985年到1987年間發表的一系列論文中發展了虛擬同步模型。這項工作的主要參考文獻是“利用分散式系統中的虛擬同步”，它描述了Isis Toolkit，一個用來建立紐約瑞士股票交易所，法國空中交通管制系統，美國海軍AEGIS戰艦等套用。
Miguel Castro和Barbara Liskov最近的工作是使用狀態機方法，他們稱之為“實用的拜占庭式容錯”架構，它使用Lamport的原始狀態機方法版本複製特別敏感的服務，但通過最佳化大大提高了性能。
最近，也有創造的BFT智慧型庫，高性能拜占庭容錯狀態機複製庫用Java開發。這個庫實現了一個非常類似於PBFT的協定，以及提供狀態轉移和主機重新配置（即JOIN和LEAVE操作）的互補協定。BFT-SMaRt是最近實現狀態機複製的努力，仍然在積極維護。
基於共識的算法Raft於2013年開發。Raft 是一種通過日誌複製來實現的一致性算法，提供了和(多重)Paxos 算法相同的功能和性能，但是它的算法結構和 Paxos 是不同的，因此Raft 算法更容易理解和套用。
問題定義
分散式服務
分散式軟體通常由客戶端和伺服器組成，每個服務包含一到多個伺服器，並提供可以由客戶端通過請求來調用的操作。儘管使用單箇中心化伺服器是實現服務的最簡單方式，但這種方式使得服務的容錯性最多能和運行伺服器的處理器相同。假如這種程度的容錯性是不可接受的，那么就必須引入多個故障無相關性的伺服器。通常而言，單一伺服器的多個服務鏡像運行在分散式系統的分離處理器上，並通過協定來保障客戶端和這些鏡像間的互動。在分散式系統中，物理和電子上被隔離開的處理器保障了伺服器之間故障沒有相關性，彼此獨立，這整合需求一致。
狀態機
在後文中，狀態機被定義為下面這些值元組：
- 一組狀態
- 一組輸入
- 一組輸出
- 一個轉換函式（輸入 x 狀態 → 狀態）
- 一個輸出函式（輸入 x 狀態 → 輸出）
- 被稱為“初始”的一個獨特狀態
一個狀態機從“初始”狀態開始，每一個輸入都被傳入轉換函式和輸出函式，以生成一個新的狀態和輸出。在新的輸入被接收到前，狀態保持不變，而輸出同時被傳輸給恰當的接受者。
在本文中，狀態機必須具備確定性：多個相同狀態機的拷貝，從同樣的“初始”狀態開始，經歷了相同的輸入序列後，會達到同樣的狀態，並且輸出同樣的結果。
通過恰當輸入流，狀態機可以實現任意的算法，包括完備圖靈機的各種算法。通常而言，基於狀態機複製的系統都會主動把它們的實現限制在有限狀態機的範疇，以簡化故障恢復。
容錯
決定性是提供容錯支持的理想特性。直觀而言，假如系統存在多分拷貝，其中一個的故障會因為與其它系統的狀態或者輸出有差異，而變得明顯。
只要簡單推理下，就可以知道實現容錯性需要最少三份拷貝，在一個系統出錯的情況下，其它兩個系統可以供我們比較狀態和輸出。而兩份拷貝顯然不夠，因為我們無從判別出錯的是哪一個。
再進一步推演，就可以知道具備三份拷貝的系統最多能支持單系統故障（隨後必須修復或者替換掉故障拷貝）。假如有多餘一個拷貝出現故障，那么三份狀態或者輸出都會互不相同，導致無法判斷正確的拷貝。
通常而言，一個支持F個故障的系統，必須至少包含2F+1份拷貝（也稱為鏡像）。多餘的拷貝被用作區分正確和故障拷貝的證據。特殊的情況也可以改良這些制約
目前的推理都預設這些鏡像僅僅是面臨隨機的獨立故障，比如記憶體錯誤或者硬碟崩潰。但源自某些鏡像嘗試欺騙系統而帶來的問題，也同樣能被狀態機複製通過隔離變化來處理。
值得一提的是，並不需要停掉故障鏡像的運行，它們可以繼續運作，即便會產出偽造或者錯誤的輸出。
狀態機方法
前面的直觀討論意味著一個簡單的技術來實現一個狀態機方面的容錯服務：
- 在多個獨立的伺服器上放置狀態機的副本。
- 接收客戶端請求，解釋為輸入到狀態機。
- 選擇輸入的順序。
- 在每台伺服器上按所選順序執行輸入。
- 通過狀態機的輸出回響客戶端。
- 監視狀態或輸出差異的副本。
