分布式系統常見的事務處理機制

為保障系統的可用性、可靠性以及性能，在分布式系統中，往往會設置數據冗余，即對數據進行復制。舉例來說，當一個數據庫的副本被破環以后，那么系統只需要轉換到其他數據副本就能繼續運行下去。另外一個例子，當訪問單一服務器管理的數據的進程數不斷增加時，系統就需要對服務器的數量進行擴充，此時，對服務器進行復制，隨后讓它們分擔工作負荷，就可以提高性能。但同時，如何保障多個數據節點之間數據的一致以及如何處理分布式事務，將成為為一個復雜的話題。本文將介紹常用的事務處理機制。

CAP 定理
CAP 定理（也稱為 Brewer 定理），是由計算機科學家 Eric Brewer 提出的，即在分布式計算機系統不可能同時提供以下全部三個保證：

一致性（Consistency）：所有節點同一時間看到是相同的數據；
可用性（Availability）：不管是否成功，確保每一個請求都能接收到響應；
分區容錯性（Partition tolerance）：系統任意分區后，在網絡故障時，仍能操作
顯然，為了保障性能和可靠性，我們將數據復制多份，分布到多個節點上，同時也帶來了一個難點，那就是如何保持各個副本數據的一致性。換句話說，我們選擇了 AP ，則必須要犧牲掉 C 了。

但是，在實際的應用場景中，數據的一致性往往也是需要保證的。那么這是否違背了 CAP 定理呢？

一致性模型
其實，數據的一致性也分幾種情況，大致可以分為：

Weak 弱一致性：當你寫入一個新值后，讀操作在數據副本上可能讀出來，也可能讀不出來。比如：某些存儲系統，搜索引擎，實時游戲，語音聊天等，這些數據本文對完整性要求不高，數據是否一致關系也不大。
Eventually 最終一致性：當你寫入一個新值后，并不一定能馬上讀出來，但在某個時間窗口之后保證最終能讀出來。比如：DNS，電子郵件，消息中間件等系統，大部分分布式系統技術都采用這類模式。
Strong 強一致性：新的數據一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統，RDBMS都是強一致性的。
也就是說，在設計分布式系統時，我們并不一定要求是強一致性的，根據應用場景可以選擇弱一致性或者是最終一致性。

事務的作用
事務有如下作用：

保證執行結果的正確性
保證數據的一致性
ACID
常見的事務處理機制
Master-Slave 復制
Slave 一般是 Master 的備份。在這樣的系統中，一般是如下設計的：

讀寫請求都由 Master 負責。
寫請求寫到 Master 上后，由 Master 同步到 Slave 上。
這種機制的特點是：

數據同步通常是異步的
有良好的吞吐量，低延遲 *　在大多數　RDBMS　中支持，比如　MySQL二進制日志
弱/最終一致性
這種機制的缺點是，如果 Master 掛了，Slave 只能提供讀服務，而沒有寫服務。

Master-Master 多主復制
指一個系統存在兩個或多個Master，每個Master都提供讀寫服務。這個機制是Master-Slave的加強版，數據間同步一般是通過Master間的異步完成，所以是最終一致性。 Master-Master的好處是，一臺Master掛了，別的Master可以正常做讀寫服務，他和Master-Slave一樣，當數據沒有被復制到別的Master上時，數據會丟失。很多數據庫都支持Master-Master的Replication的機制。

這種機制的特點是：

異步
最終的一致性
多個節點間需要序列化協議
兩階段提交
兩階段提交協議 （Two-phase commit protocol，2PC）的過程涉及到協調者和參與者。協調者可以看做成事務的發起者，同時也是事務的一個參與者。對于一個分布式事務來說，一個事務是涉及到多個參與者的。具體的兩階段提交的過程如下：

第一階段（準備階段）
協調者節點向所有參與者節點詢問是否可以執行提交操作(vote)，并開始等待各參與者節點的響應。
參與者節點執行詢問發起為止的所有事務操作，并將 Undo 信息和 Redo 信息寫入日志。（注意：若成功這里其實每個參與者已經執行了事務操作）
各參與者節點響應協調者節點發起的詢問。如果參與者節點的事務操作實際執行成功，則它返回一個“同意”消息；如果參與者節點的事務操作實際執行失敗，則它返回一個“中止”消息。
第二階段（提交階段）
如果協調者收到了參與者的失敗消息或者超時，直接給每個參與者發送回滾(Rollback)消息；否則，發送提交(Commit)消息；參與者根據協調者的指令執行提交或者回滾操作，釋放所有事務處理過程中使用的鎖資源。(注意:必須在最后階段釋放鎖資源)

當協調者節點從所有參與者節點獲得的相應消息都為“同意”時:
協調者節點向所有參與者節點發出“正式提交(commit)”的請求。
參與者節點正式完成操作，并釋放在整個事務期間內占用的資源。
參與者節點向協調者節點發送“完成”消息。
如果任一參與者節點在第一階段返回的響應消息為”中止”，或者 協調者節點在第一階段的詢問超時之前無法獲取所有參與者節點的響應消息時：
協調者節點向所有參與者節點發出”回滾操作(rollback)”的請求。
參與者節點利用之前寫入的Undo信息執行回滾，并釋放在整個事務期間內占用的資源。
參與者節點向協調者節點發送”回滾完成”消息。
協調者節點受到所有參與者節點反饋的”回滾完成”消息后，取消事務。
協調者節點受到所有參與者節點反饋的”完成”消息后，完成事務
不管最后結果如何，第二階段都會結束當前事務。

二段式提交協議的優缺點：

優點：原理簡單，實現方便；

缺點：

同步阻塞問題。執行過程中，所有參與節點都是事務阻塞型的。
單點故障。由于協調者的重要性，一旦協調者發生故障，參與者會一直阻塞下去。尤其在第二階段，協調者發生故障，那么所有的參與者還都處于鎖定事務資源的狀態中，而無法繼續完成事務操作。
數據不一致。在階段二中，當協調者向參與者發送 commit 請求之后，發生了局部網絡異常或者在發送 commit 請求過程中協調者發生了故障，這回導致只有一部分參與者接受到了 commit 請求。而在這部分參與者接到 commit 請求之后就會執行 commit 操作。但是其他部分未接到 commit 請求的機器則無法執行事務提交。于是整個分布式系統便出現了數據部一致性的現象。
二階段無法解決的問題：協調者再發出 commit 消息之后宕機，而唯一接收到這條消息的參與者同時也宕機了。那么即使協調者通過選舉協議產生了新的協調者，這條事務的狀態也是不確定的，沒人知道事務是否被已經提交。
為了解決兩階段提交協議的種種問題，研究者們在二階段提交的基礎上做了改進，提出了三階段提交。

三階段提交
三階段提交協議（Three-phase commit protocol，3PC），是二階段提交（2PC）的改進版本。與兩階段提交不同的是，三階段提交有兩個改動點：

引入超時機制。同時在協調者和參與者中都引入超時機制。
在第一階段和第二階段中插入一個準備階段。保證了在最后提交階段之前各參與節點的狀態是一致的。
即 3PC 把 2PC 的準備階段再次一分為二，這樣三階段提交就有 CanCommit、PreCommit、DoCommit 三個階段。

CanCommit 階段
CanCommit 階段其實和 2PC 的準備階段很像。協調者向參與者發送 commit 請求，參與者如果可以提交就返回 Yes 響應，否則返回 No 響應。

事務詢問：協調者向參與者發送 CanCommit 請求。詢問是否可以執行事務提交操作。然后開始等待參與者的響應。
響應反饋：參與者接到 CanCommit 請求之后，正常情況下，如果其自身認為可以順利執行事務，則返回 Yes 響應，并進入預備狀態。否則反饋 No
PreCommit 階段
協調者根據參與者的反應情況來決定是否可以記性事務的 PreCommit 操作。根據響應情況，有以下兩種可能。

假如協調者從所有的參與者獲得的反饋都是 Yes 響應，那么就會執行事務的預執行。
發送預提交請求：協調者向參與者發送 PreCommit 請求，并進入Prepared 階段。
事務預提交：參與者接收到 PreCommit 請求后，會執行事務操作，并將undo 和 redo 信息記錄到事務日志中。
響應反饋：如果參與者成功的執行了事務操作，則返回 ACK 響應，同時開始等待最終指令。
假如有任何一個參與者向協調者發送了 No 響應，或者等待超時之后，協調者都沒有接到參與者的響應，那么就執行事務的中斷。
發送中斷請求：協調者向所有參與者發送 abort 請求。
中斷事務：參與者收到來自協調者的 abort 請求之后（或超時之后，仍未收到協調者的請求），執行事務的中斷。
doCommit 階段
該階段進行真正的事務提交，也可以分為以下兩種情況。

執行提交
發送提交請求：協調接收到參與者發送的 ACK 響應，那么他將從預提交狀態進入到提交狀態。并向所有參與者發送 doCommit 請求。
事務提交：參與者接收到 doCommit 請求之后，執行正式的事務提交。并在完成事務提交之后釋放所有事務資源。
響應反饋：事務提交完之后，向協調者發送 ACK 響應。
完成事務：協調者接收到所有參與者的 ACK 響應之后，完成事務。
中斷事務：協調者沒有接收到參與者發送的 ACK 響應（可能是接受者發送的不是 ACK 響應，也可能響應超時），那么就會執行中斷事務。
發送中斷請求：協調者向所有參與者發送 abort 請求
事務回滾：參與者接收到 abort 請求之后，利用其在階段二記錄的undo 信息來執行事務的回滾操作，并在完成回滾之后釋放所有的事務資源。
反饋結果：參與者完成事務回滾之后，向協調者發送 ACK 消息
中斷事務：協調者接收到參與者反饋的 ACK 消息之后，執行事務的中斷。
在 doCommit 階段，如果參與者無法及時接收到來自協調者的 doCommit 或者 rebort 請求時，會在等待超時之后，會繼續進行事務的提交。即當進入第三階段時，由于網絡超時等原因，雖然參與者沒有收 到 commit 或者 abort 響應，事務仍然會提交。

三階段提交不會一直持有事務資源并處于阻塞狀態。但是這種機制也會導致數據一致性問題，因為，由于網絡原因，協調者發送的 abort 響應沒有及時被參與者接收到，那么參與者在等待超時之后執行了 commit 操作，這樣就和其他接到 abort 命令并執行回滾的參與者之間存在數據不一致的情況。

Paxos 算法
Paxos 算法是 Leslie Lamport 于1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法。Paxos 算法目前在 Google 的 Chubby、MegaStore、Spanner 等系統中得到了應用，Hadoop 中的 ZooKeeper 也使用了 Paxos 算法。

在 Paxos 算法中，分為4種角色：

Proposer ：提議者
Acceptor：決策者
Client：產生議題者
Learner：最終決策學習者
算法可以分為兩個階段來執行：

階段1
Proposer 選擇一個議案編號 n，向 acceptor 的多數派發送編號也為 n 的 prepare 請求。
Acceptor：如果接收到的 prepare 請求的編號 n 大于它已經回應的任何prepare 請求，它就回應已經批準的編號最高的議案（如果有的話），并承諾不再回應任何編號小于 n 的議案；
階段2
Proposer：如果收到了多數 acceptor 對 prepare 請求（編號為 n）的回應，它就向這些 acceptor 發送議案{n, v}的 accept 請求，其中 v 是所有回應中編號最高的議案的決議，或者是 proposer 選擇的值，如果回應說還沒有議案。
Acceptor：如果收到了議案{n, v}的 accept 請求，它就批準該議案，除非它已經回應了一個編號大于 n 的議案。
Proposer 可以提出多個議案，只要它遵循上面的算法。它可以在任何時刻放棄一個議案。（這不會破壞正確性，即使在議案被放棄后，議案的請求或者回應消息才到達目標）如果其它的 proposer 已經開始提出更高編號的議案，那么最好能放棄當前的議案。因此，如果 acceptor 忽略一個 prepare 或者 accept 請求（因為已經收到了更高編號的 prepare 請求），它應該告知 proposer 放棄議案。這是一個性能優化，而不影響正確性。