狀態機複製
在計算機科學領域，狀態機複製是實現容錯服務的一種常規方法，主要通過複製服務器，並協調客戶端和這些服務器鏡像間的交互來達到目標。這個方法也同時提供了理解和設計複製管理協議的一套基本框架。
問題定義
[編輯]分布式服務
[編輯]分布式軟件通常由客戶端和服務器組成，每個服務包含一到多個服務器，並提供可以由客戶端通過請求來調用的操作。儘管使用單個中心化服務器是實現服務的最簡單方式，但這種方式使得服務的容錯性最多能和運行服務器的處理器相同。假如這種程度的容錯性是不可接受的，那麼就必須引入多個故障無相關性的服務器。通常而言，單一服務器的多個服務鏡像運行在分布式系統的分離處理器上，並通過協議來保障客戶端和這些鏡像間的交互。在分布式系統中，物理和電子上被隔離開的處理器保障了服務器之間故障沒有相關性，彼此獨立，這整合需求一致
狀態機
[編輯]在後文中，狀態機被定義為下面這些值元組[1]（參見Mealy machine和Moore Machine）：
- 一組狀態
- 一組輸入
- 一組輸出
- 一個轉換函數（輸入 x 狀態 → 狀態）
- 一個輸出函數（輸入 x 狀態 → 輸出）
- 被稱為「初始」的一個獨特狀態
一個狀態機從「初始」狀態開始，每一個輸入都被傳入轉換函數和輸出函數，以生成一個新的狀態和輸出。在新的輸入被接收到前，狀態保持不變，而輸出同時被傳輸給恰當的接受者。
在本文中，狀態機必須具備確定性：多個相同狀態機的拷貝，從同樣的「初始」狀態開始，經歷了相同的輸入序列後，會達到同樣的狀態，並且輸出同樣的結果。
通過恰當輸入流，狀態機可以實現任意的算法，包括完備圖靈機的各種算法（參見圖靈機）。通常而言，基於狀態機複製的系統都會主動把它們的實現限制在有限狀態機的範疇，以簡化故障恢復。
容錯
[編輯]決定性是提供容錯支持的理想特性。直觀而言，假如系統存在多分拷貝，其中一個的故障會因為與其它系統的狀態或者輸出有差異，而變得明顯。
只要簡單推理下，就可以知道實現容錯性需要最少三份拷貝，在一個系統出錯的情況下，其它兩個系統可以供我們比較狀態和輸出。而兩份拷貝顯然不夠，因為我們無從判別出錯的是哪一個。
再進一步推演，就可以知道具備三份拷貝的系統最多能支持單系統故障（隨後必須修復或者替換掉故障拷貝）。假如有多餘一個拷貝出現故障，那麼三份狀態或者輸出都會互不相同，導致無法判斷正確的拷貝。
通常而言，一個支持F個故障的系統，必須至少包含2F+1份拷貝（也稱為鏡像）[2]。多餘的拷貝被用作區分正確和故障拷貝的證據。特殊的情況也可以改良這些制約[3]
目前的推理都預設這些鏡像僅僅是面臨隨機的獨立故障，比如內存錯誤或者硬盤崩潰。但源自某些鏡像嘗試欺騙系統而帶來的問題，也同樣能被狀態機複製通過隔離變化來處理。
值得一提的是，並不需要停掉故障鏡像的運行，它們可以繼續運作，即便會產出偽造或者錯誤的輸出。
參考資料
[編輯]- ^ Lamport, Leslie. The Implementation of Reliable Distributed Multiprocess Systems. Computer Networks. 1978, 2: 95–114 [2008-03-13]. doi:10.1016/0376-5075(78)90045-4. （原始內容存檔於2007-08-16）.
- ^ Lamport, Leslie. Lower Bounds for Asynchronous Consensus. 2004 [2016-06-10]. （原始內容存檔於2007-08-16）.
- ^ Lamport, Leslie; Mike Massa. Cheap Paxos. Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004). 2004 [2016-06-10]. （原始內容存檔於2007-08-16）.
外部連結
[編輯]- Replicated state machines video on MIT TechTV
- Apache Bookkeeper a replicated log service which can be used to build replicated state machines