第九章-分布式事務處理

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

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

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

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

5、參與者的引用，每一個參與者也記錄一個對協(xié)調(diào)者的引用。參與者也記錄一個對協(xié)調(diào)者的引用。join(Trans, Server-id of coordinator) 事務標識符事務標識符TID分為創(chuàng)建該事務的服務器標識符（分為創(chuàng)建該事務的服務器標識符（IP）和對該服務）和對該服務器來說是唯一的數(shù)字兩部分。器來說是唯一的數(shù)字兩部分。Company Logo9.2 9.2 簡單分布式事務和嵌套事務簡單分布式事務和嵌套事務 銀銀行事行事務務涉及服涉及服務務器器Branch X、Y、Z上的上的賬戶賬戶A、B、C、D，客，客戶戶事事務務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 簡單分布式事務和嵌套事務簡單分布式事務和嵌套事務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)者在其中某一服務器上，例如BranchX。Com

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

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

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

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

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

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

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

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

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

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

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

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