分布式系統(tǒng)常見的事務(wù)處理機(jī)制

為保障系統(tǒng)的可用性、可靠性以及性能，在分布式系統(tǒng)中，往往會(huì)設(shè)置數(shù)據(jù)冗余，即對(duì)數(shù)據(jù)進(jìn)行復(fù)制。舉例來說，當(dāng)一個(gè)數(shù)據(jù)庫(kù)的副本被破環(huán)以后，那么系統(tǒng)只需要轉(zhuǎn)換到其他數(shù)據(jù)副本就能繼續(xù)運(yùn)行下去。另外一個(gè)例子，當(dāng)訪問單一服務(wù)器管理的數(shù)據(jù)的進(jìn)程數(shù)不斷增加時(shí)，系統(tǒng)就需要對(duì)服務(wù)器的數(shù)量進(jìn)行擴(kuò)充，此時(shí)，對(duì)服務(wù)器進(jìn)行復(fù)制，隨后讓它們分擔(dān)工作負(fù)荷，就可以提高性能。但同時(shí)，如何保障多個(gè)數(shù)據(jù)節(jié)點(diǎn)之間數(shù)據(jù)的一致以及如何處理分布式事務(wù)，將成為為一個(gè)復(fù)雜的話題。本文將介紹常用的事務(wù)處理機(jī)制。

CAP 定理
CAP 定理（也稱為 Brewer 定理），是由計(jì)算機(jī)科學(xué)家 Eric Brewer 提出的，即在分布式計(jì)算機(jī)系統(tǒng)不可能同時(shí)提供以下全部三個(gè)保證：

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

但是，在實(shí)際的應(yīng)用場(chǎng)景中，數(shù)據(jù)的一致性往往也是需要保證的。那么這是否違背了 CAP 定理呢？

一致性模型
其實(shí)，數(shù)據(jù)的一致性也分幾種情況，大致可以分為：

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

事務(wù)的作用
事務(wù)有如下作用：

保證執(zhí)行結(jié)果的正確性
保證數(shù)據(jù)的一致性
ACID
常見的事務(wù)處理機(jī)制
Master-Slave 復(fù)制
Slave 一般是 Master 的備份。在這樣的系統(tǒng)中，一般是如下設(shè)計(jì)的：

讀寫請(qǐng)求都由 Master 負(fù)責(zé)。
寫請(qǐng)求寫到 Master 上后，由 Master 同步到 Slave 上。
這種機(jī)制的特點(diǎn)是：

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

Master-Master 多主復(fù)制
指一個(gè)系統(tǒng)存在兩個(gè)或多個(gè)Master，每個(gè)Master都提供讀寫服務(wù)。這個(gè)機(jī)制是Master-Slave的加強(qiáng)版，數(shù)據(jù)間同步一般是通過Master間的異步完成，所以是最終一致性。 Master-Master的好處是，一臺(tái)Master掛了，別的Master可以正常做讀寫服務(wù)，他和Master-Slave一樣，當(dāng)數(shù)據(jù)沒有被復(fù)制到別的Master上時(shí)，數(shù)據(jù)會(huì)丟失。很多數(shù)據(jù)庫(kù)都支持Master-Master的Replication的機(jī)制。

這種機(jī)制的特點(diǎn)是：

異步
最終的一致性
多個(gè)節(jié)點(diǎn)間需要序列化協(xié)議
兩階段提交
兩階段提交協(xié)議 （Two-phase commit protocol，2PC）的過程涉及到協(xié)調(diào)者和參與者。協(xié)調(diào)者可以看做成事務(wù)的發(fā)起者，同時(shí)也是事務(wù)的一個(gè)參與者。對(duì)于一個(gè)分布式事務(wù)來說，一個(gè)事務(wù)是涉及到多個(gè)參與者的。具體的兩階段提交的過程如下：

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

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

二段式提交協(xié)議的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：原理簡(jiǎn)單，實(shí)現(xiàn)方便；

缺點(diǎn)：

同步阻塞問題。執(zhí)行過程中，所有參與節(jié)點(diǎn)都是事務(wù)阻塞型的。
單點(diǎn)故障。由于協(xié)調(diào)者的重要性，一旦協(xié)調(diào)者發(fā)生故障，參與者會(huì)一直阻塞下去。尤其在第二階段，協(xié)調(diào)者發(fā)生故障，那么所有的參與者還都處于鎖定事務(wù)資源的狀態(tài)中，而無法繼續(xù)完成事務(wù)操作。
數(shù)據(jù)不一致。在階段二中，當(dāng)協(xié)調(diào)者向參與者發(fā)送 commit 請(qǐng)求之后，發(fā)生了局部網(wǎng)絡(luò)異?；蛘咴诎l(fā)送 commit 請(qǐng)求過程中協(xié)調(diào)者發(fā)生了故障，這回導(dǎo)致只有一部分參與者接受到了 commit 請(qǐng)求。而在這部分參與者接到 commit 請(qǐng)求之后就會(huì)執(zhí)行 commit 操作。但是其他部分未接到 commit 請(qǐng)求的機(jī)器則無法執(zhí)行事務(wù)提交。于是整個(gè)分布式系統(tǒng)便出現(xiàn)了數(shù)據(jù)部一致性的現(xiàn)象。
二階段無法解決的問題：協(xié)調(diào)者再發(fā)出 commit 消息之后宕機(jī)，而唯一接收到這條消息的參與者同時(shí)也宕機(jī)了。那么即使協(xié)調(diào)者通過選舉協(xié)議產(chǎn)生了新的協(xié)調(diào)者，這條事務(wù)的狀態(tài)也是不確定的，沒人知道事務(wù)是否被已經(jīng)提交。
為了解決兩階段提交協(xié)議的種種問題，研究者們?cè)诙A段提交的基礎(chǔ)上做了改進(jìn)，提出了三階段提交。

三階段提交
三階段提交協(xié)議（Three-phase commit protocol，3PC），是二階段提交（2PC）的改進(jìn)版本。與兩階段提交不同的是，三階段提交有兩個(gè)改動(dòng)點(diǎn)：

引入超時(shí)機(jī)制。同時(shí)在協(xié)調(diào)者和參與者中都引入超時(shí)機(jī)制。
在第一階段和第二階段中插入一個(gè)準(zhǔn)備階段。保證了在最后提交階段之前各參與節(jié)點(diǎn)的狀態(tài)是一致的。
即 3PC 把 2PC 的準(zhǔn)備階段再次一分為二，這樣三階段提交就有 CanCommit、PreCommit、DoCommit 三個(gè)階段。

CanCommit 階段
CanCommit 階段其實(shí)和 2PC 的準(zhǔn)備階段很像。協(xié)調(diào)者向參與者發(fā)送 commit 請(qǐng)求，參與者如果可以提交就返回 Yes 響應(yīng)，否則返回 No 響應(yīng)。

事務(wù)詢問：協(xié)調(diào)者向參與者發(fā)送 CanCommit 請(qǐng)求。詢問是否可以執(zhí)行事務(wù)提交操作。然后開始等待參與者的響應(yīng)。
響應(yīng)反饋：參與者接到 CanCommit 請(qǐng)求之后，正常情況下，如果其自身認(rèn)為可以順利執(zhí)行事務(wù)，則返回 Yes 響應(yīng)，并進(jìn)入預(yù)備狀態(tài)。否則反饋 No
PreCommit 階段
協(xié)調(diào)者根據(jù)參與者的反應(yīng)情況來決定是否可以記性事務(wù)的 PreCommit 操作。根據(jù)響應(yīng)情況，有以下兩種可能。

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

執(zhí)行提交
發(fā)送提交請(qǐng)求：協(xié)調(diào)接收到參與者發(fā)送的 ACK 響應(yīng)，那么他將從預(yù)提交狀態(tài)進(jìn)入到提交狀態(tài)。并向所有參與者發(fā)送 doCommit 請(qǐng)求。
事務(wù)提交：參與者接收到 doCommit 請(qǐng)求之后，執(zhí)行正式的事務(wù)提交。并在完成事務(wù)提交之后釋放所有事務(wù)資源。
響應(yīng)反饋：事務(wù)提交完之后，向協(xié)調(diào)者發(fā)送 ACK 響應(yīng)。
完成事務(wù)：協(xié)調(diào)者接收到所有參與者的 ACK 響應(yīng)之后，完成事務(wù)。
中斷事務(wù)：協(xié)調(diào)者沒有接收到參與者發(fā)送的 ACK 響應(yīng)（可能是接受者發(fā)送的不是 ACK 響應(yīng)，也可能響應(yīng)超時(shí)），那么就會(huì)執(zhí)行中斷事務(wù)。
發(fā)送中斷請(qǐng)求：協(xié)調(diào)者向所有參與者發(fā)送 abort 請(qǐng)求
事務(wù)回滾：參與者接收到 abort 請(qǐng)求之后，利用其在階段二記錄的undo 信息來執(zhí)行事務(wù)的回滾操作，并在完成回滾之后釋放所有的事務(wù)資源。
反饋結(jié)果：參與者完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送 ACK 消息
中斷事務(wù)：協(xié)調(diào)者接收到參與者反饋的 ACK 消息之后，執(zhí)行事務(wù)的中斷。
在 doCommit 階段，如果參與者無法及時(shí)接收到來自協(xié)調(diào)者的 doCommit 或者 rebort 請(qǐng)求時(shí)，會(huì)在等待超時(shí)之后，會(huì)繼續(xù)進(jìn)行事務(wù)的提交。即當(dāng)進(jìn)入第三階段時(shí)，由于網(wǎng)絡(luò)超時(shí)等原因，雖然參與者沒有收 到 commit 或者 abort 響應(yīng)，事務(wù)仍然會(huì)提交。

三階段提交不會(huì)一直持有事務(wù)資源并處于阻塞狀態(tài)。但是這種機(jī)制也會(huì)導(dǎo)致數(shù)據(jù)一致性問題，因?yàn)椋捎诰W(wǎng)絡(luò)原因，協(xié)調(diào)者發(fā)送的 abort 響應(yīng)沒有及時(shí)被參與者接收到，那么參與者在等待超時(shí)之后執(zhí)行了 commit 操作，這樣就和其他接到 abort 命令并執(zhí)行回滾的參與者之間存在數(shù)據(jù)不一致的情況。

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

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

Proposer ：提議者
Acceptor：決策者
Client：產(chǎn)生議題者
Learner：最終決策學(xué)習(xí)者
算法可以分為兩個(gè)階段來執(zhí)行：

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