第九章-分布式事務(wù)處理

1、COMPANY LOGO第九章第九章 分布式事務(wù)處理分布式事務(wù)處理袁帥袁帥 何杰濤何杰濤Company Logo第九章第九章 分布式事務(wù)處理分布式事務(wù)處理 9.1 概述概述 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù) 9.3 原子提交協(xié)議原子提交協(xié)議 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 9.5 分布式事務(wù)的死鎖分布式事務(wù)的死鎖 9.6 帶復(fù)制數(shù)據(jù)的事務(wù)帶復(fù)制數(shù)據(jù)的事務(wù) 9.7 小結(jié)小結(jié)Company Logo9.1 9.1 概述概述 事務(wù)事務(wù) 用于訪問和修改各種數(shù)據(jù)項的一個程序單位。用于訪問和修改各種數(shù)據(jù)項的一個程序單位。 數(shù)據(jù)庫管理系統(tǒng)中的事務(wù)是訪問數(shù)據(jù)庫的一個程

2、數(shù)據(jù)庫管理系統(tǒng)中的事務(wù)是訪問數(shù)據(jù)庫的一個程序的執(zhí)行。序的執(zhí)行。 分布式系統(tǒng)中，事務(wù)是指一組客戶請求的執(zhí)行。分布式系統(tǒng)中，事務(wù)是指一組客戶請求的執(zhí)行。從客戶角度看，事務(wù)是組成一個步驟的一組操作，從客戶角度看，事務(wù)是組成一個步驟的一組操作，它將服務(wù)器的數(shù)據(jù)從一個一致性狀態(tài)轉(zhuǎn)換到另一它將服務(wù)器的數(shù)據(jù)從一個一致性狀態(tài)轉(zhuǎn)換到另一個一致性狀態(tài)。個一致性狀態(tài)。Company Logo9.1 9.1 概述概述 分布式事務(wù)分布式事務(wù) 活動涉及多個服務(wù)器的事務(wù)。活動涉及多個服務(wù)器的事務(wù)。Company Logo9.2 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù) 簡單分布式事務(wù)：又稱為平面分布式事務(wù)，

3、一個簡單分布式事務(wù)：又稱為平面分布式事務(wù)，一個客戶可請求多臺服務(wù)器，但每接收客戶請求的服客戶可請求多臺服務(wù)器，但每接收客戶請求的服務(wù)器并不調(diào)用其他服務(wù)器的操作。務(wù)器并不調(diào)用其他服務(wù)器的操作。XYZTCompany Logo9.2 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù) 嵌套事務(wù)：一個服務(wù)器的一個操作可能觸發(fā)另一嵌套事務(wù)：一個服務(wù)器的一個操作可能觸發(fā)另一個服務(wù)器的某個操作，通常后者可能又進(jìn)一步請個服務(wù)器的某個操作，通常后者可能又進(jìn)一步請求操作，依次類推。同層次的子事務(wù)可以并發(fā)執(zhí)求操作，依次類推。同層次的子事務(wù)可以并發(fā)執(zhí)行。行。Company Logo9.2 9.2 簡單分布式事

4、務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù)TT1T2T11T12T21T22XYMNPCompany Logo9.2 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù)事務(wù)的第一個服務(wù)器成為事務(wù)的協(xié)調(diào)者，負(fù)責(zé)終止或提交事務(wù)。事務(wù)的第一個服務(wù)器成為事務(wù)的協(xié)調(diào)者，負(fù)責(zé)終止或提交事務(wù)。管理分布式事務(wù)訪問的對象的每個服務(wù)器都是該事務(wù)的參與者，每個管理分布式事務(wù)訪問的對象的每個服務(wù)器都是該事務(wù)的參與者，每個事務(wù)參與者負(fù)責(zé)跟蹤所有參與分布式事務(wù)的可恢復(fù)對象。事務(wù)參與者負(fù)責(zé)跟蹤所有參與分布式事務(wù)的可恢復(fù)對象。事務(wù)執(zhí)行過程中，協(xié)調(diào)者在列表中記錄所有對參與者的引用，每一個事務(wù)執(zhí)行過程中，協(xié)調(diào)者在列表中記錄所有對

5、參與者的引用，每一個參與者也記錄一個對協(xié)調(diào)者的引用。參與者也記錄一個對協(xié)調(diào)者的引用。join(Trans, Server-id of coordinator) 事務(wù)標(biāo)識符事務(wù)標(biāo)識符TID分為創(chuàng)建該事務(wù)的服務(wù)器標(biāo)識符（分為創(chuàng)建該事務(wù)的服務(wù)器標(biāo)識符（IP）和對該服務(wù)）和對該服務(wù)器來說是唯一的數(shù)字兩部分。器來說是唯一的數(shù)字兩部分。Company Logo9.2 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù) 銀銀行事行事務(wù)務(wù)涉及服涉及服務(wù)務(wù)器器Branch X、Y、Z上的上的賬戶賬戶A、B、C、D，客，客戶戶事事務(wù)務(wù)T從從A轉(zhuǎn)賬轉(zhuǎn)賬$4到到C，從從B轉(zhuǎn)賬轉(zhuǎn)賬$3到到D。 T=openTra

6、nsaction A.withdraw(4); C.deposit(4); B.withdraw(3); D.deposit(3); closeTransaction Company Logo9.2 9.2 簡單分布式事務(wù)和嵌套事務(wù)簡單分布式事務(wù)和嵌套事務(wù)TABCDA.withdraw(4);B.withdraw(3);C.deposit(4);D.deposit(3);BranchX BranchY BranchZ協(xié)調(diào)者協(xié)調(diào)者joinjoinjoinopenTransactioncloseTransactionb.withdraw(T,3)協(xié)調(diào)者在其中某一服務(wù)器上，例如BranchX。Com

7、pany Logo9.3 原子提交協(xié)議 事務(wù)的原子性事務(wù)的原子性:要求當(dāng)一個分布式事務(wù)結(jié)束時，它要求當(dāng)一個分布式事務(wù)結(jié)束時，它的操作要么全部執(zhí)行的操作要么全部執(zhí)行,要么全部沒執(zhí)行。要么全部沒執(zhí)行。 原子提交協(xié)議：以原子方式完成事務(wù)的方式。原子提交協(xié)議：以原子方式完成事務(wù)的方式。Company Logo9.3 原子提交協(xié)議 兩階段提交協(xié)議：準(zhǔn)備和執(zhí)行兩個階段。兩階段提交協(xié)議：準(zhǔn)備和執(zhí)行兩個階段。CanCommit? (Trans) Yes/No 由協(xié)調(diào)者發(fā)給參與者，詢問它是否提交事務(wù)。參與者將其表決作應(yīng)答。由協(xié)調(diào)者發(fā)給參與者，詢問它是否提交事務(wù)。參與者將其表決作應(yīng)答。DoCommit（Trans

8、） 由協(xié)調(diào)者發(fā)給參與者，通知所有參與者提交事務(wù)。由協(xié)調(diào)者發(fā)給參與者，通知所有參與者提交事務(wù)。HaveCommitted（Trans,Woker） 由參與者發(fā)給協(xié)調(diào)者，以證實它已提交了它的事務(wù)。由參與者發(fā)給協(xié)調(diào)者，以證實它已提交了它的事務(wù)。GetDecision（Trans） Yes/No 當(dāng)參與者已表決當(dāng)參與者已表決Yes，而一段延遲后無應(yīng)答時，由參與者發(fā)給協(xié)調(diào)者詢問關(guān)于，而一段延遲后無應(yīng)答時，由參與者發(fā)給協(xié)調(diào)者詢問關(guān)于事務(wù)的決定。用于故障或超時恢復(fù)。事務(wù)的決定。用于故障或超時恢復(fù)。 Company Logo9.3 原子提交協(xié)議階段階段1（表決階段）：（表決階段）：（1）協(xié)調(diào)者向事務(wù)的每個參與

9、者發(fā)送一個）協(xié)調(diào)者向事務(wù)的每個參與者發(fā)送一個CanCommit？請求；？請求；（2）當(dāng)參與者受到）當(dāng)參與者受到CanCommit？請求，將其表決（？請求，將其表決（Yes或或No）應(yīng)答傳遞給協(xié)調(diào)者。若表決為應(yīng)答傳遞給協(xié)調(diào)者。若表決為No，參與者立即中止。，參與者立即中止。階段階段2 （根據(jù)表決結(jié)果完成）（根據(jù)表決結(jié)果完成）（3）協(xié)調(diào)者收集表決（包括自己的）；）協(xié)調(diào)者收集表決（包括自己的）； （a）若無故障且所有表決均為）若無故障且所有表決均為Yes，則協(xié)調(diào)者決定提交事務(wù)，則協(xié)調(diào)者決定提交事務(wù)且向每個參與者發(fā)送一個且向每個參與者發(fā)送一個DoCommit請求；請求； （b）否則，協(xié)調(diào)者決定中止事務(wù)

10、，且向所有表決為）否則，協(xié)調(diào)者決定中止事務(wù)，且向所有表決為Yes的參的參與者發(fā)送與者發(fā)送AbortTransaction請求。請求。（4）表決為）表決為Yes的參與者等待協(xié)調(diào)者的的參與者等待協(xié)調(diào)者的DoCommit或或AbortTransaction請求。當(dāng)參與者收到某一消息，按其執(zhí)行。若請求。當(dāng)參與者收到某一消息，按其執(zhí)行。若是提交，發(fā)一個是提交，發(fā)一個HaveCommitted給協(xié)調(diào)者作為確認(rèn)。給協(xié)調(diào)者作為確認(rèn)。Company Logo9.3 原子提交協(xié)議兩階段提交協(xié)議中的超時兩階段提交協(xié)議中的超時預(yù)備提交（等待表決）已提交完成協(xié)調(diào)者步驟 狀態(tài)參與者步驟 狀態(tài)預(yù)備提交（不確定）已提交Can

11、Commit?YesDoCommitHaveCCompany Logo9.3 原子提交協(xié)議 兩階段提交協(xié)議中的性能兩階段提交協(xié)議中的性能有有N個參與者需要傳遞個參與者需要傳遞N個個canCommit?消息和應(yīng)答，消息和應(yīng)答，然后再有然后再有N個個doCommit消息。消息。消息開銷與消息開銷與3N成正比，時間開銷是成正比，時間開銷是3次消息往返。次消息往返。由于協(xié)議在沒有由于協(xié)議在沒有haveCommitted消息時仍然能正確運(yùn)消息時仍然能正確運(yùn)行行-它們的作用只是通知服務(wù)器刪除過時的協(xié)調(diào)者信息它們的作用只是通知服務(wù)器刪除過時的協(xié)調(diào)者信息，所以不算在估計開銷中。，所以不算在估計開銷中。Comp

12、any Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 每個服務(wù)器要管理很多對象，它必須保證在并發(fā)每個服務(wù)器要管理很多對象，它必須保證在并發(fā)事務(wù)訪問這些對象時，這些對象仍保持一致性。事務(wù)訪問這些對象時，這些對象仍保持一致性。因此，每個服務(wù)器需要對自己的對象應(yīng)用并發(fā)控因此，每個服務(wù)器需要對自己的對象應(yīng)用并發(fā)控制機(jī)制。制機(jī)制。 分布式事務(wù)所有服務(wù)器共同保證事務(wù)以串行等價分布式事務(wù)所有服務(wù)器共同保證事務(wù)以串行等價方式執(zhí)行。這就意味著，如果事務(wù)方式執(zhí)行。這就意味著，如果事務(wù)T對某一服務(wù)對某一服務(wù)器對象沖突訪問在事務(wù)器對象沖突訪問在事務(wù)U之前，那么在所有服務(wù)之前，那么在所有服務(wù)器上對對

13、象的沖突操作，事務(wù)器上對對象的沖突操作，事務(wù)T都在都在U之前。之前。Company Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 鎖機(jī)制鎖機(jī)制 在一個分布式事務(wù)中，每個服務(wù)器都為其數(shù)據(jù)項在一個分布式事務(wù)中，每個服務(wù)器都為其數(shù)據(jù)項保留鎖。本地鎖管理者可以決定是授予鎖還是讓保留鎖。本地鎖管理者可以決定是授予鎖還是讓請求的事務(wù)等待。當(dāng)它知道事務(wù)已在參加該事務(wù)請求的事務(wù)等待。當(dāng)它知道事務(wù)已在參加該事務(wù)的所有服務(wù)器上提交或者中止之前不能釋放鎖。的所有服務(wù)器上提交或者中止之前不能釋放鎖。 由于服務(wù)器彼此獨(dú)立地設(shè)置它們的鎖，有可能不由于服務(wù)器彼此獨(dú)立地設(shè)置它們的鎖，有可能不同服務(wù)器將不同

14、的次序加于事務(wù)上，就可能出現(xiàn)同服務(wù)器將不同的次序加于事務(wù)上，就可能出現(xiàn)分布式死鎖的情況。分布式死鎖的情況。Company Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 T UWrite(A)在服務(wù)器X上對A加鎖Write(B)在服務(wù)器Y上對B加鎖 Read(B)在服務(wù)器Y上等待U Read(A)在服務(wù)器X上等待TCompany Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 分布式事務(wù)中的時間戳定序并發(fā)控制分布式事務(wù)中的時間戳定序并發(fā)控制 在分布式事務(wù)中，每個服務(wù)器可以分配全局唯一的時戳。在分布式事務(wù)中，每個服務(wù)器可以分配全局唯一的時戳。事務(wù)第一次訪問的服

15、務(wù)器分配一個全局唯一的時戳給客戶，事務(wù)第一次訪問的服務(wù)器分配一個全局唯一的時戳給客戶，該時戳被傳給事務(wù)中執(zhí)行了操作的每個服務(wù)器。該時戳被傳給事務(wù)中執(zhí)行了操作的每個服務(wù)器。 例如，在一個服務(wù)器上由事務(wù)例如，在一個服務(wù)器上由事務(wù)U訪問的數(shù)據(jù)項在由事務(wù)訪問的數(shù)據(jù)項在由事務(wù)T訪問該數(shù)據(jù)項后提交，則當(dāng)訪問該數(shù)據(jù)項后提交，則當(dāng)U和和T在另外的服務(wù)器上訪問在另外的服務(wù)器上訪問相同數(shù)據(jù)項時，它們也必須按照相同的次序提交。相同數(shù)據(jù)項時，它們也必須按照相同的次序提交。 為實現(xiàn)在所有服務(wù)器相同次序，必須在時戳次序上達(dá)成一為實現(xiàn)在所有服務(wù)器相同次序，必須在時戳次序上達(dá)成一致。時間戳是一個二元組致。時間戳是一個二元組C

16、ompany Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制 分布式事務(wù)中的樂觀并發(fā)控制分布式事務(wù)中的樂觀并發(fā)控制 樂觀并發(fā)控制盡管放心去做你想做的事，不用在意其他人樂觀并發(fā)控制盡管放心去做你想做的事，不用在意其他人正在做什么。如果有問題，那么以后再考慮。正在做什么。如果有問題，那么以后再考慮。 每個事務(wù)在允許提交前都是有效的。服務(wù)器在驗證開始時每個事務(wù)在允許提交前都是有效的。服務(wù)器在驗證開始時分配事務(wù)號，事務(wù)根據(jù)事務(wù)號的次序排序。分配事務(wù)號，事務(wù)根據(jù)事務(wù)號的次序排序。Company Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制TU讀（A） 在X上讀（B）

17、 在Y上寫（A）寫（B）讀（B） 在Y上讀（A） 在X上寫（B）寫（A）Company Logo9.4 9.4 分布式事務(wù)的并發(fā)控制分布式事務(wù)的并發(fā)控制并發(fā)度死鎖性能鎖低有中樂觀法高無高（廢棄度低時）時間戳法較高無較高Company Logo9.59.5分布式事務(wù)的死鎖分布式事務(wù)的死鎖UVW交錯事務(wù)U、V、W，涉及到服務(wù)器X、Y管理的數(shù)據(jù)項A、B，和服務(wù)器Z管理的數(shù)據(jù)項C、DCompany Logo9.59.5分布式事務(wù)的死鎖分布式事務(wù)的死鎖WCDZAXUVB 被占用等待被占用被占用被占用等待等待WVU YCompany Logo9.59.5分布式事務(wù)的死鎖分布式事務(wù)的死鎖 邊追逐法邊追逐法

18、這種方法中，不需要構(gòu)造全局等待圖，但是每個服務(wù)器都有很多關(guān)于邊的信息。服務(wù)器通過稱為探針（probe）的正向消息沿著整個分布式系統(tǒng)的有向圖的邊傳送來發(fā)現(xiàn)環(huán)路。 當(dāng)服務(wù)器1發(fā)現(xiàn)某個事務(wù)T開始等待事務(wù)U時，而U在等待服務(wù)器2上對象時，服務(wù)器1發(fā)送一個T U的探針消息來啟動一次檢測過程，這個消息發(fā)給阻塞U的服務(wù)器2。Company Logo9.59.5分布式事務(wù)的死鎖分布式事務(wù)的死鎖WUVCBA 探針傳遞被占用被占用等待等待等待發(fā)起W UW U VW U V W死鎖被死鎖被檢測到檢測到服務(wù)器X服務(wù)器Y服務(wù)器ZCompany Logo 事務(wù)優(yōu)先級事務(wù)優(yōu)先級 在上面的算法中，死鎖涉及的每個事務(wù)都可能發(fā)起死鎖檢在上面的算法中，死鎖涉及的每個