這篇文章是我閱讀論文《 The Design of a Practical System for Fault-Tolerant Virtual Machines 》時的筆記，這篇論文是 VMware 發表的論文，使用虛擬機來設計一個分布式容錯系統。

在分布式系統中，容錯方法有很多種，常見的傳統方法有：主/副服務器方法(當主服務器宕機之后，由副服務器來接管它的工作)，這種方法通常需要機器之間的高帶寬。

另外還有確定(deterministic)狀態機方法：將另一臺服務器初始化為和主服務器一樣的狀態，然后讓它們都接受到同樣的輸入，這樣它們的狀態始終保持一致，但是這種方法對于非確定的(non-deterministic)操作并不適用。

本文中討論的方法是使用虛擬機作為狀態機，它具有以下優點：

• 操作全部被虛擬化
• 虛擬機本身就支持 non-deterministic 操作
• 虛擬機管理程序(Hypervision)能夠記錄所有在虛擬機上的操作，所以能夠記錄主服務器(Primary)所有操作，然后在副服務器(Backup)上進行演繹

基本設計方案

如圖就是本文提到的容錯系統的架構，一個 Primary，一個 Backup，Primary 和 Backup 之間通過 Logging Channel 進行通信，Primary 和 Backup 基本保持同步，Backup 稍稍落后，它們兩個之間會通過 heartbeat 進行 fail 檢測，并且它們使用共享磁盤(Shared Disk)。

確定(deterministic)操作的演繹

讓兩臺機器初始狀態相同，它們接受相同的輸入，順序相同，兩臺機器執行的任務的結果就會相同。

但是如果存在非確定的(non-deterministic)操作(比如中斷事件、讀取CPU時鐘計數器的值操作就是非確定的)，它會影響狀態機的執行。

難點在于：

• 需要捕捉全部的輸入和 non-deterministic 操作在保證 Backup 是deterministic 的
• 需要準確將全部輸入和 non-deterministic 操作應用到 Backup 中
• 需要保證系統高效

設計方案為：將所有的 input 和 non-deterministic 操作寫入到 log 中(file)，對于 non-deterministic 操作還要記錄和它相關的狀態信息等，確保 non-deterministic 操作后Backup狀態還是和 Primary 一致

FT(Fault-Tolerance)協議

FT 協議是應用于 logging channel 的協議，協議的基本要求為：

如果 Primary 宕機了，Backup 接替它的工作，Backup 之后向外界發出所有的 Output 要和 Primary 原本應當發送的一致。

為了保證以上的要求，設計如下系統：

• Primary會在所有關于本次Output 的所有信息都發送給 Backup 之后(并且要確保 Backup 收到)才會把 output 發送給外界
• Primary 只是推遲將 output 發送給外界，而不會暫停執行后邊的任務

流程如圖所示：

但是這種方法不能保證 output 只發出一次，如果 primary 宕機了，backup 不能判斷它是在發送了 output 之前還是之后宕機的，因此 backup 會再發送一次 output。但是這個問題很容易解決，因為：

• output 是通過網絡進行發送的，例如 TCP 之類的網絡協議能夠檢測重復的數據包
• 即使 output 被發送了2次其實也沒關系。如果 output 是一個寫操作，它會在同一個位置寫入兩次，結果不會發生變化;如果 output 是讀取操作，讀的內容會被放入 bounce buffer(為了消除 DMA 競爭)，數據會在 IO 中斷之后被送到

宕機檢測

如何知道有機器宕機，在該系統中是十分重要的。該設計使用的是UDP heartbeat 機制來檢測 Primary 與 Backup 之間的通信是否正常。

但是使用這種方法會存在裂腦問題(split-brain，Primary 和 Backup 同時宕機)，該怎么解決呢?

該設計中使用了共享存儲(Shared Storage)，對它的操作是原子的，Primary 和 Backup不能同時進行一個操作(提供原子的 test-and-set 操作)

如果檢測出 Primary 宕機，Backup 會成為 Primary，接替之前的工作，然后再尋找一個 Backup。

具體實現

啟動/重啟 Virtual Machine

如何啟動一個和 Primary 狀態一樣的 Backup?

VMware Vmotion 操作能夠將一臺 VM 從一個 Server 完整的遷移到另一個 Server(只需要很短的中斷)，在該設計中的方法對 Vmotion 做了一點修改，不是進行遷移，而是直接克隆。

管理 Logging Channel

如圖，該設計使用了一個大的 buffer，來保存 logging entries，Primary 把自己的 entry 存到 buffer 中，由 logging channel 發送給Backup 的 buffer，然后 Backup 從 buffer 讀取命令執行。

• 如果 Backup 的 buffer 空了，沒有命令執行了，Backup 會等待新的 entry
• 如果 Primary 的 buffer 滿了，Primary 會等待，等 buffer 中有空余空間再繼續執行

Disk I/O問題

disk 操作是并行的，同時對 disk 的同一位置進行操作會導致 non-deterministic

解決方案：檢測 IO 競爭，使這些操作串行執行

Disk IO 使用 DMA(Direct Memory Access)，同時訪問內存同一位置的操作會導致 non-deterministic

解決方案：對 disk 操作的內存設置內存的頁保護，但是這種方法代價太高;該設計中使用了 bounce buffer，它的大小和 disk 所操作的內存部分大小是一致的，read 操作直接將內容讀入 buffer，當其他操作完成，寫入內存，write 操作將寫內容寫入 buffer，之后再寫入磁盤。

總結

Vmware 提出的這種 Primary/Backup 方法是分布式容錯方法中非常重要的一部分，可以用在許多系統中，不僅僅是分布式存儲(GFS 的容錯方法)，也可以用在分布式計算中，因為它是將所有的操作都記錄下來，將它們重新在 Backup 上進行演繹，從而起到了備份的作用，能夠做到容錯(Fault-Tolerance)。