cctg: 分散式系統一致性演算法

分散式系統透過網路互相連接，但由於網路的時間延遲，再加上各節點可能的失效或異常，需要一個適當的演算法達到資料一致性，如果其中有些節點，可能會刻意造假以混淆資料的一致性結果，那麼需要更有效的演算法來解決這樣的問題。

一致性問題

資料一致性通常指關聯數據之間的邏輯關係是否正確和完整。而資料存儲的一致性模型則可以認為是存儲系統和資料使用者之間的一種約定。如果使用者遵循這種約定，則可以得到系統所承諾的訪問結果，常用的一致性模型有：

嚴格一致性（linearizability, strict/atomic Consistency）

讀出的數據始終為最近寫入的數據。這種一致性只有當全域時鐘存在時才有可能達成，在分散式網路環境不可能實現。
順序一致性（sequential consistency）

對同一資料的操作，所有使用者都看到同樣的操作順序，但是該順序不一定是即時的。
因果一致性（causal consistency）

只有存在因果關係的寫入操作才要求所有使用者看到相同的操作順序，對於無因果關係的寫入則並行進行，不保證操作順序。因果一致性可以看做對順序一致性性能的一種優化，但在實現時必須建立與維護因果依賴圖，這是相當困難的。
管道一致性（PRAM/FIFO consistency）

在因果一致性模型上的進一步弱化，要求由某一個使用者完成的寫入操作可以被其他所有的使用者按照順序的感知到，而從不同使用者中來的寫操作則無需保證順序，就像一個一個的管道一樣。相對來說比較容易實現。
弱一致性（weak consistency）

只要求對共享的資料結構的訪問保證順序一致性。對於同步變數的操作具有順序一致性，是全局可見的，且只有當沒有寫操作等待處理時才可進行，以保證對於臨界區域的訪問順序進行。在同一時間，所有使用者可以看到相同的資料。
釋放一致性（release consistency）

弱一致性無法區分使用者是要進入臨界區還是要出臨界區，釋放一致性使用兩個不同的操作語句進行了區分。需要寫入時，使用者先acquire該對象，寫完後release，acquire-release之間形成了一個臨界區，提供釋放一致性也就意味著當release操作發生後，所有使用者應該可以看到該操作。
最終一致性（eventual consistency）

在沒有新的更新的情況下，更新最終會通過網路傳播到所有副本點，所有副本點最終會一致，也就是說使用者在最終某個時間點前的中間過程中無法保證看到的是新寫入的數據。可以採用最終一致性模型有一個關鍵要求：可以接受讀取到舊的資料狀態。
delta consistency

系統會在delta時間內達到一致。這段時間內會存在一個不一致的窗口，該窗口可能是因為log shipping的過程導致。資料庫完整性（Database Integrity）是指資料庫中數據的正確性和相容性。資料庫完整性由各種各樣的完整性約束來保證，因此可以說資料庫完整性設計就是資料庫完整性約束的設計。

共識演算法 consensus problem

要保障系統滿足不同程度的一致性，往往需要通過共識演算法來達成。共識算法解決的是對某個提案（Proposal），大家達成一致意見的過程。

提案的含義在分佈式系統中十分寬泛，例如多個事件發生的順序、某個鍵對應的值、誰是領導...，可以認為任何需要達成一致的信息都是一個提案。通過訪問足夠多個服務節點來驗證確保獲取共識後結果。

如果分佈式系統中各個節點都能保證以十分強大的性能（即時響應）無故障的運行，則實現共識過程並不複雜，簡單通過投票即可。但實際上每個資料 request 會有網路的傳輸時間延遲，節點可能會故障，甚至存在了惡意的節點要故意破壞系統。

如果只有故障（不響應）的情況，沒有惡意節點，稱為「非拜占庭錯誤」，針對非拜占庭錯誤的情況，一般使用 Paxos、Raft 這一類的演算法。
如果有惡意響應的情況，稱為「拜占庭錯誤」，對於要能容忍拜占庭錯誤的情況，一般使用 PBFT 系列、PoW 系列演算法。

拜占庭將軍問題是一個協議問題，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。但這些將軍在地理上是分隔開來的，並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標：欺騙某些將軍採取進攻行動，促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是註定要失敗的，只有完全達成一致的努力才能獲得勝利。

由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效，並且這些協議還要滿足所要解決的問題要求的規範。

FLP 不可能性原理

在網絡可靠情況下，如果存在節點失效（即便只有一個）的最小化異步模型系統中，不存在一個可以解決一致性問題的確定性算法。

有個實例可以解釋這個原理，三個人在不同房間，進行投票（投票結果是 0 或者 1）。三個人彼此可以通過電話進行溝通，但經常會有人突然睡著。比如某個時候，A 投票 0，B 投票 1，C 收到了兩人的投票，然後 C 睡著了。A 和 B 永遠無法在有限時間內獲知最終的結果。逾時的時候，可以重新投票，如果類似情形每次在取得結果前發生，就永遠無法取得共識。

但加上一些條件限制，就可以達到共識。

CAP 原理

分佈式計算系統不可能同時達到一致性（Consistency）、可用性（Availablity）和分區容忍性（Partition），設計中往往需要弱化對某個特性的保證。

一致性（Consistency）

任何操作應該都是原子的(不能被中斷)，發生在後面的事件能看到前面事件發生導致的結果，注意這裡指的是強一致性
可用性（Availablity）

在有限時間內，任何非失敗節點都能能夠回應請求的結果
分區容忍性（Partition）

網路可能發生分區，不保障節點之間的通信。

CAP 三個可以弱化某一個條件，用以設計系統。

弱化一致性 AP

對結果一致性不敏感的應用，可以允許在新版本的資料上線後過一段時間才更新成功，在更新過程中，不保證一致性。
例如網站靜態頁面內容、實時性較弱的查詢類數據庫等，CouchDB、Cassandra 等為此設計。
弱化可用性 CP

對結果一致性很敏感的應用，例如銀行取款機，當系統故障時候會拒絕服務。MongoDB、Redis 等為此設計。Paxos、Raft 等算法，主要處理這種情況。
弱化分區容忍性 CA

網絡分區出現概率減小，但較難避免。某些關聯式資料庫、ZooKeeper 即為此設計。網絡可透過雙路由等機制增強可靠性，達到高穩定的網路通信。

ACID 原則強調一致性 C，失去了可用性

資料庫管理系統（DBMS）在寫入/更新資料的過程中，為保證事務（transaction）是正確可靠的，所必須具備的四個特性：原子性（atomicity，或稱不可分割性）、一致性（consistency）、隔離性（isolation，又稱獨立性）、持久性（durability）。

原子性：一個事務（transaction）中的所有操作，要麼全部完成，要麼全部失敗，不會結束在中間某個環節。事務在執行過程中發生錯誤，會被 Rollback 到事務開始前的狀態，就像這個事務從來沒有執行過一樣。
一致性：在事務開始之前和事務結束以後，資料庫的完整性沒有被破壞。這表示寫入的資料必須完全符合所有的預設規則，這包含資料的精確度、串聯性以及後續資料庫可以自發性地完成預定的工作。
隔離性：資料庫允許多個並發事務同時對齊數據進行讀寫和修改的能力，隔離性可以防止多個事務並發執行時由於交叉執行而導致數據的不一致。事務隔離分為不同級別，包括讀未提交（Read uncommitted）、讀提交（read committed）、可重複讀（repeatable read）和串行化（Serializable）。
持久性：transaction 處理結束後，對數據的修改就是永久的，即便系統故障也不會遺失資料。

BASE 原則強調可用性，但失去了一致性

Base: 一種 Acid 的替代方案

BASE（Basic Availiability，Soft state，Eventually Consistency）

BA Basic Availiability

基本可用性
S Soft state

server 在有限度的資源（一般是時間）內維持上下文 context，逾時則拋棄狀態回復到默認狀態。
E Eventually Consistency

允許因延時等出現臨時的數據不一致現象，只要數據最終是一致的就可以。

Paxos 與 Raft

Paxos 是 1990 年由 Leslie Lamport 提出的演算法，針對分散式系統，其中存在著故障的節點，但不存在惡意節點的狀況下，如何達成共識的處理方法。

古希臘 Paxon 島上的多個法官在一個大廳內對一個議案進行表決，但要達成一致的結果。法官之間通過服務人員來傳遞紙條，但法官可能離開或進入大廳，服務人員可能偷懶去睡覺。

Paxos 是以 two-phase commit 的方式來解決問題。

演算法中將節點分為

Proposer: 負責提案，等待大家同意並結案，通常是客戶端 client 擔任這個角色
Acceptor: 對提案進行投票，通常是 server 擔任這個角色
Learner: 被告知投票的結果，並與結果同步，但不參與投票的過程，client 或是 server 都有可能擔任這個角色

phase1（準備階段）

Proposer向超過半數（n/2+1）Acceptor發起prepare消息(發送編號)
如果prepare符合協議規則，Acceptor回覆promise消息，否則拒絕

phase2（決議階段或投票階段）

如果超過半數Acceptor回覆promise，Proposer向Acceptor發送accept消息
Acceptor檢查accept消息是否符合規則，消息符合則批准accept請求

以實際上三個 server 推舉 leader 的議案為例

細節可參閱一致性算法Paxos詳解

Raft 是 Paxos 的簡化實現，是由Stanford提出的一種更易理解的一致性演算法，意在取代目前廣為使用的Paxos演算法。

包含了三種角色：leader、candiate 和 follower，其基本過程為

Leader 選舉：每個 candidate 隨機經過一定時間都會提出選舉方案，最近階段中得票最多者被選為 leader；
同步 log：leader 會找到系統中 log 最新的記錄，並強制所有的 follower 來刷新到這個記錄 (log 是各種事件的發生記錄)

PBFT

PBFT Practical Byzantine Fault Tolerance 實用拜占庭容錯算法，是 Miguel Castro 和 Barbara Liskov 在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題，將算法複雜度由指數級降低到多項式級。

PBFT的一致性協議如下圖所示，每一個客戶端的請求需要5個階段才能完成。PBFT通過採用兩次兩兩交互的方式在服務器達成一致之後再執行客戶端的請求，由於客戶端不能從服務器端獲得任何服務器運行狀態的信息，因此PBFT 協議中主節點是否發生錯誤只能由服務器監測。如果服務器在一段時間內都不能完成客戶端的請求，則會觸發視圖更換協議。

PBFT的熱門應用是在IBM主導的區塊鏈超級賬本項目中，除了PBFT之外，超級賬本項目還引入了基於PBFT的自用共識協議Sieve，它的目的是希望在PBFT基礎之上能夠對節點的輸出也做好共識，這是因為超級賬本項目的一個重要功能是提供區塊鏈之上的智能合約——就是在區塊鏈上執行的一段代碼，因此它會帶來區塊鏈賬本上最終狀態的不確定，為此Sieve會在PBFT實現的基礎之上引入代碼執行結果簽名進行驗證。