徐書海

摘 要：所謂分布式，就是將要處理的業(yè)務(wù)進(jìn)行拆分，然后將拆分的子服務(wù)部署到不同的服務(wù)器上進(jìn)行處理。在分布式中，我們必須要解決服務(wù)可用性和數(shù)據(jù)一致性問題，然而根據(jù)CAP定理知道，兩者是互相矛盾的，本文主要介紹分布式數(shù)據(jù)一致性的概念與解決一致性問題的協(xié)議和算法。

關(guān)鍵詞：Paxos算法;分布式;數(shù)據(jù)一致性

1 分布式數(shù)據(jù)一致性

分布式服務(wù)就是將一個(gè)大的服務(wù)拆分成若干個(gè)子服務(wù)，我們將拆分的子服務(wù)部署到不同的服務(wù)器上運(yùn)行。在分布式設(shè)計(jì)中，為了數(shù)據(jù)可擴(kuò)展性，我們將數(shù)據(jù)放在不同的分布式節(jié)點(diǎn)上，必然遇到可用性和數(shù)據(jù)一致性的矛盾問題。舉個(gè)例子，我們把某個(gè)班級(jí)作為整個(gè)分布式服務(wù)，而班里的所有學(xué)生作為各個(gè)子服務(wù)。某日，學(xué)生張三和李四因?yàn)槊艽蚣芰耍@個(gè)消息被班里的小明知道了，于是迅速在班里傳播開來。在消息傳播過程中你詢問班里的某個(gè)學(xué)生，如果他回答“不知道”，則說明整個(gè)班級(jí)里出現(xiàn)了數(shù)據(jù)不一致，（因?yàn)樾∶魇侵赖模?如果某個(gè)學(xué)生直接沒有回答你，（為了保持?jǐn)?shù)據(jù)一致性，需要班里所有的同學(xué)都知道了才可以服務(wù)），在“寫數(shù)據(jù)”過程中，無法提供服務(wù)，這就是可用性問題。在“秒殺”服務(wù)中，下訂單和增積分兩個(gè)服務(wù)的數(shù)據(jù)表在不同的機(jī)器上，完成下訂單后必須要進(jìn)行增積分，所以要保證兩邊的數(shù)據(jù)的一致性。

2 數(shù)據(jù)一致性協(xié)議

2.1 2PC（兩階段提交）

兩階段提交協(xié)議是一種簡(jiǎn)單的保證分布式數(shù)據(jù)一致性的協(xié)議。它的主要思想是在分布式服務(wù)中，所有的服務(wù)的數(shù)據(jù)操作要么都成功，要么都失敗，也就是分布式數(shù)據(jù)操作必須具有原子性。

該協(xié)議分為兩個(gè)階段，其中涉及了兩個(gè)角色，即協(xié)調(diào)者和參與者。

第一階段，當(dāng)要執(zhí)行一個(gè)分布式事務(wù)時(shí)，事務(wù)發(fā)起者向協(xié)調(diào)者發(fā)送請(qǐng)求，然后協(xié)調(diào)者會(huì)向所有的參與者發(fā)送prepare請(qǐng)求（其中包含事務(wù)內(nèi)容），告訴參與者要執(zhí)行事務(wù)了，如果能執(zhí)行發(fā)送的事務(wù)就先執(zhí)行但不提交，執(zhí)行完后回復(fù)協(xié)調(diào)者。然后參與者執(zhí)行事務(wù)但不提交，并將 Undo 和 Redo 信息記入事務(wù)日志中，之后參與者向協(xié)調(diào)者回復(fù)消息。

第二階段是協(xié)調(diào)者根據(jù)參與者的回復(fù)決定接下來是否進(jìn)行事務(wù)的提交操作。這里可能做事務(wù)的提交操作或者做回滾操作。如果所有的參與者都返回了準(zhǔn)備好消息，這個(gè)時(shí)候協(xié)調(diào)者向所有的參與者發(fā)送commit請(qǐng)求，參與者接到commit請(qǐng)求會(huì)將前面執(zhí)行的事務(wù)進(jìn)行提交操作，提交完成后給協(xié)調(diào)者發(fā)送提交成功確認(rèn)消息。而不是所有的參與者都返回了準(zhǔn)備好消息，這個(gè)時(shí)候協(xié)調(diào)者會(huì)向所有的參與者發(fā)送回滾事務(wù)的請(qǐng)求，參與者接收到這個(gè)請(qǐng)求之后將回滾前面所做的事務(wù)處理，然后向協(xié)調(diào)者發(fā)送回滾的處理情況，最后協(xié)調(diào)者向事務(wù)發(fā)起者發(fā)送事務(wù)處理失敗的回復(fù)。

2.2 3PC（三階段提交）

2PC不能跟上解決一致性問題，而且存在嚴(yán)重的阻塞問題。引入3PC（三階段提交解決阻塞問題）。

第一階段，協(xié)調(diào)者向所有的參與者發(fā)送CanCommit請(qǐng)求，參與者接到CanCommit請(qǐng)求以后查看自己是否可以執(zhí)行事務(wù)，如果可以則回復(fù)yes，否則回復(fù)no。

第二階段，如果第一階段所有的參與者返回了yes，則協(xié)調(diào)者向所有的參與者發(fā)送PreCommit預(yù)提交請(qǐng)求，所有參與者接到PreCommit請(qǐng)求后，進(jìn)行事務(wù)的執(zhí)行，執(zhí)行完以后不進(jìn)行提交，并將Undo和Redo信息記入事務(wù)日志中，返回執(zhí)行成功的信息。如果在第一階段有參與者返回了no或者是有參與者沒有返回消息，則協(xié)調(diào)者會(huì)向所有的參與者發(fā)送中斷事務(wù)的請(qǐng)求，所有參與者收到中斷請(qǐng)求后則進(jìn)行中斷事務(wù)的操作。如果在一定時(shí)間內(nèi)，協(xié)調(diào)者沒有發(fā)送PreCommit請(qǐng)求，所有的參與者也會(huì)執(zhí)行中斷事務(wù)的操作。

第三階段，如果第二階段所有的參與者返回了對(duì)PreCommit預(yù)提交請(qǐng)求的yes回復(fù)，那么協(xié)調(diào)者會(huì)向所有的參與者發(fā)送DoCommit請(qǐng)求，請(qǐng)求所有的參與者進(jìn)行提交操作。所有參與者收到DoCommit請(qǐng)求之后進(jìn)行提交操作，之后返回響應(yīng)，協(xié)調(diào)者收到所有的參與者的提交完成消息后，事務(wù)執(zhí)行完成。如果協(xié)調(diào)者收到了第二階段PreCommit預(yù)提交請(qǐng)求的no回復(fù)或者有參與者沒有對(duì)PreCommit預(yù)提交請(qǐng)求回復(fù)，則協(xié)調(diào)者會(huì)向所有的參與者發(fā)送中斷事務(wù)的請(qǐng)求，參與者收到中斷請(qǐng)求后則按照事務(wù)日志記錄進(jìn)行事務(wù)的回滾操作，并向協(xié)調(diào)者會(huì)送回滾操作情況，協(xié)調(diào)者收到參與者的回滾情況后中斷事務(wù)。

3 Paxos算法

Paxos算法是一種基于消息傳遞的一致性算法。該算法中一共有三種角色。

3.1 第一階段（prepare階段）

Proposer負(fù)責(zé)提出Proposal，獲取一個(gè)全局性、唯一的、遞增的變量N。然后把N賦予提案，然后向所有的Acceptor發(fā)送編號(hào)為N的Prepare請(qǐng)求。記為Pareper（N）。

Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，它會(huì)將編號(hào)為N記錄在本地，這樣在每個(gè)Acceptor中已經(jīng)被接受的請(qǐng)求編號(hào)中有一個(gè)最大的記為maxN。如果N小于Acceptor已經(jīng)響應(yīng)過的請(qǐng)求，則拒絕，不予回應(yīng)或回復(fù)error。若N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請(qǐng)求的最大編號(hào)（maxN），那么它就會(huì)將它已經(jīng)接受過（已經(jīng)經(jīng)過第二階段accept的提案）的編號(hào)最大的提案（如果還沒有的accept提案的話返回{id，null，null}）作為響應(yīng)反饋給Proposer，同時(shí)該Acceptor承諾不再接受任何編號(hào)小于N的提案。

3.2 第二階段（accept階段）

如果Proposer收到半數(shù)以上Acceptor對(duì)其發(fā)出的編號(hào)為N的Prepare請(qǐng)求的yes響應(yīng)，那么它就會(huì)發(fā)送一個(gè)包含內(nèi)容和編號(hào)的提案給半數(shù)以上的Acceptor。

如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求，如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求，只要該 Acceptor沒有對(duì)編號(hào)大于N的Prepare請(qǐng)求做出過響應(yīng)，它就接受該提案（此時(shí)執(zhí)行提案內(nèi)容但不提交），隨后將情況返回給Proposer。如果不滿足則不回應(yīng)或者返回NO。如果N小于Acceptor已經(jīng)響應(yīng)過的prepare請(qǐng)求編號(hào)，則拒絕，不給回應(yīng)或回復(fù)error。當(dāng)proposer沒有收到過半的回應(yīng)，那么他會(huì)重新進(jìn)入第一階段，遞增提案號(hào)，重新提出prepare請(qǐng)求。

上邊描述的過程只有半數(shù)以上的Acceptor接受并執(zhí)行了提案，還有Acceptor沒有執(zhí)行提案。所以這個(gè)時(shí)候需要向未批準(zhǔn)的acceptor發(fā)送提案內(nèi)容和提案編號(hào)并讓它無條件執(zhí)行和提交，而對(duì)于前面已經(jīng)批準(zhǔn)過該提案的acceptor來說僅僅需要發(fā)送該提案的編號(hào)，讓 acceptor執(zhí)行提交就行了。

4 結(jié)束語

上面的2PC、3PC操作都是在安全可靠的信道上進(jìn)行傳遞消息來保證數(shù)據(jù)一致性的。其中3PC操作解決了消息阻塞帶來的資源占用問題，而Paxos算法解決了網(wǎng)絡(luò)中節(jié)點(diǎn)故障引起的數(shù)據(jù)不一致問題，從根本上解決了一致性問題。

參考文獻(xiàn)

[1]倪超.從Paxos到ZooKeeper分布式一致性原理與實(shí)踐[M].北京：電子工業(yè)出版社，2015.2.

[2]柳偉衛(wèi).分布式一致性算法開發(fā)實(shí)戰(zhàn)大型互聯(lián)網(wǎng)架構(gòu)實(shí)戰(zhàn)[M].北京：北京出版社，2020.5.

[3]趙辰.分布式一致性算法開發(fā)實(shí)戰(zhàn)[M].北京：北京大學(xué)出版社，2020.5.