《雲數據管理：挑戰與機遇》2.1.6　一致性問題

一致性問題

一致性是一個基本的分布式係統問題，在出現故障的情況下，需要多個步驟來達成一致[Pease et al., 1980]。該問題經常出現在如下場景中：通信是可靠的，但是由於係統崩潰或認為惡意破壞等原因（即未按照指定的協議或代碼進行響應），站點可能會失效。一般而言，該問題可以使用一個單獨的協調者，或稱general，協調者給n-1個參與者發送一個二進製值，並滿足下列條件：

一致：所有參與者都認同一個值。

正確：如果general是正確的，那麼每一個參與者都認同general發送的值。

接下來介紹兩個不可能出現的結果。在異步係統中，如果進程由於崩潰而失效，並且進程是通過消息傳遞來進行通信的，Fischer et al. [1983, 1985]證明一致性是不可能解決的。另一方麵，在一個存在惡意故障的同步係統中，Dolev [1982] 證明了如果一個係統的進程數量小於3f+1，其中，f是故障（惡意）進程的最大值，那麼該係統也無法解決一致性問題。

已經有多種協議可以用來解決同步係統和異步係統中的一致性問題。同步係統需要指定惡意故障站點的最大數量的上界，如三分之一。另一方麵，異步係統可能無法確保係統能夠終止。近來，Lamport [1998, 2001]為異步係統開發的Paxos協議廣受歡迎。抽象地講，Paxos是一個以領導者為基礎的（leader-based）的協議，每一個進程都可以估計當前的領導者是誰。當一個進程希望在某個值上達成一致時，進程就把該值發送給領導者。領導者對操作進行排序並通過一致性算法來實現一致。通常情況下，該協議經曆兩個階段。在每一個階段，領導者會與大部分站點進行聯係，往往會有多個並發的領導者。用投票來區分不同領導者提供的值。兩個階段的具體過程可以總結如下：第一階段，又稱為準備階段，認為自己是領導者的節點可以選擇一個新的唯一的投票號碼，並把該號碼發送給所有的站點，然後等待來自大部分站點的較小的投票號碼的結果。第二階段，又稱接受階段，領導者根據自己的投票號碼建議一個值。如果領導者能夠獲得大多數支持，那麼該值就會被接受，其他站點也會用對應的投票號碼對該值進行判斷。圖2-7展示了基於Paxos協議的不同進程之間的通信模式。

 

圖2-7　基於Paxos協議的通信