第3章分布式系統的同步

中國科技大學軟件學院丁箐1第3章分布式系統的同步中國科技大學軟件學院1主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖2主要內容3.1時鐘同步2主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖3主要內容3.1時鐘同步33.1時鐘同步分布式算法的特點相關信息散布在多個場地上每個進程只能基于本地信息做決定應避免因單點故障造成整個系統的失敗不存在公共時鐘或精確的全局時間43.1時鐘同步分布式算法的特點4時鐘同步問題例：makefile誤差時間output.o：cc–Coutput.c5時鐘同步問題例：makefile誤差時間output.o：邏輯時鐘計時器：石英晶體+計數器時鐘偏差（clockskew）邏輯時鐘：相對時間物理時鐘：真實時間“之前”關系:事件a在b之前出現，則aba為發送消息m，b為接收m，則ab具有傳遞性：ab,bc,則ac并發事件（concurrent）6邏輯時鐘計時器：石英晶體+計數器6Lamport算法對每一事件a，在所有進程中都認可給它分配一個時間值C(a）ifab;則C(a)<C(b)a,bC(a)C(b)C是遞增的校正算法ab，ifC(b)<C(a),則C(b)=C(a)+17Lamport算法對每一事件a，在所有進程中都認可給它分配一Lamport算法時間慢快慢快8Lamport算法時間慢快慢快8物理時鐘與現實時鐘（1）如何用現實世界的時鐘將它們同步起來；（2）如何使各時鐘之間保持同步。

太陽日：連續的兩次日中天的時間太陽秒：solar-day/86400平均太陽秒：如，格林威治時間9物理時鐘與現實時鐘（1）如何用現實世界的時鐘將它們同步起來；現實時鐘銫原子鐘：9192631770次躍遷=1秒TAI秒：國際原子時間UTC秒：世界時間（在TAI秒中加入閏秒）時間服務：WWV電臺、GEOS衛星102010現實時鐘銫原子鐘：9192631770次躍遷=1秒10201時鐘同步算法如何與現實時鐘同步如何使不同機器之間相互同步設機器時鐘值Cp(t),t為UTC時間最大偏移率精確時鐘：dC/dt=1快時鐘：dC/dt〉1慢時鐘：dC/dt<111時鐘同步算法如何與現實時鐘同步11Christian’s算法--逐步調整法時間服務器，可接受WWV的UTC時間每隔δ/2ρ校準時間（允許誤差δ，存在誤差ρ）兩個問題：時間決不能倒退,延遲假設：每秒產生100次中斷，每次中斷將時間加10毫秒若調慢時鐘，中斷服務程序每次只加9毫秒；若加快時鐘，則加11毫秒。傳播時間12Christian’s算法--逐步調整法時間服務器，Berkeley算法–主動式方法時間監控器定期查詢其他機器時間計算出平均值通知其他機器調整時間13Berkeley算法–主動式方法時間監控器定期查詢其他平均值算法–非集中式方法將時間劃分成固定長度的再同步間隔，第i次間隔開始于T0+iR，而結束于T0+(i+1)R所有機器廣播自己的時鐘時間啟動本地計時器收集在S時間間隔中到達的其他機器廣播的時間執行平均時間計算算法，得到新的時間值（取平均值，去掉兩端值）14平均值算法–非集中式方法將時間劃分成固定長度的再同步間隔多個外部時間源法例：OSFDCE方法接受所有時間源的當前UTC區間去掉與其他區間不相交的區間將相交部分的中點作為校準時間時間15多個外部時間源法例：OSFDCE方法時間15使用同步時鐘最多一次消息提交每個消息攜帶一個ID和一個時間印ts（timestamp）服務器的表T中，記錄每個連接C最近的時間印t如果到達的消息m，ts(m)<t,則拒絕m

服務器要一直保存一個全局變量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的時間印從表T中清除對于具有新的ID的到達消息m,如果ts(m)<G則拒絕m,否則，接受m按照一定時間間隔T，定期地將G寫入磁盤。當系統重啟后，G’=G+T16使用同步時鐘最多一次消息提交服務器要一直保存一個全使用同步時鐘基于時鐘的緩存一致性當客戶讀取一個副本到緩存時，設置一個租期（lease）在租期過期之前，客戶可更新副本，重續租期如果已經過期，緩存中的副本失效改進的一致性協議當客戶修改文件時，只需將所有沒有到期的緩存副本設為無效如果某個客戶崩潰，則等待直到該客戶的租期過期17使用同步時鐘基于時鐘的緩存一致性改進的一致性協議1主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖18主要內容3.1時鐘同步183.2互斥基本概念當一個進程使用某個共享資源，其他進程不允許對這個資源操作臨界區（CriticalSection）：對共享資源進行操作的程序段基本方法：信號量、管程問題：死鎖活鎖饑餓193.2互斥基本概念19集中式算法（仿照單處理機系統的方法）協調者：確定那個進程可進入臨界區通信量：3個消息：請求-許可-釋放缺點：單點失敗單協調者會成為執行的瓶頸

CCC20集中式算法（仿照單處理機系統的方法）協調者：確定那個進程可WinThread臨界區CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()21WinThread臨界區CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系統中所有事件都是全序的1.在一個進程P打算進入臨界區R之前，向所有其他進程廣播消息<臨界區R名、進程號、時間印>2.當一個進程P’收到消息后，做如下決定：若P’不在臨界區R中，也不想進入R，它就向P發送OK消息；若P’已經在臨界區R中，則不回答，并將P放入請求隊列；若P’也同時要進入臨界區R，但是還沒有進入時，則將發來的消息和它發送給其余進程的時間戳對比。如果P時間印小，則P發送OK消息;否則，不回答，并將P放入請求隊列；3.當P收到所有的OK消息后，進入R。否則，等待。4.當P退出R時，如果存在等待隊列，則取出請求者，向其發送OK消息。22分布式算法（Ricart-Agrawala算法）要求系統中所分布式算法舉例舉例：

共有0，1，2三個進程。進程0，2申請進入臨界區02002223分布式算法舉例舉例：共有0，1，2三個進程。0200222分布式算法評價缺點：n點失敗n點瓶頸2（n-1)個消息改進方案：超時重發組通信簡單多數同意比原來集中式算法慢，復雜，昂貴，而且不健壯。24分布式算法評價缺點：24令牌環算法構造一個邏輯環，得到令牌才可進入臨界區325令牌環算法構造一個邏輯環，得到令牌才可進入臨界區325三種互斥算法的比較算法每次進出需要的消息進入前的延遲（按消息次數）存在問題集中式32協調者崩潰分布式2（n-1）2（n-1）任何一個進程崩潰令牌環1到∞0到n-1丟失令牌，進程崩潰26三種互斥算法的比較算法每次進出進入前的延遲（按消息次數）存在主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖27主要內容3.1時鐘同步273.3選舉算法許多分布式算法需要一個進程充當協調者，發起者，排序者或其他特定的角色。作用：做出統一的的決定例如：確定協調者283.3選舉算法許多分布式算法需要一個進程充當協調者，發起欺負（Bully）算法將進程進行排序P向高的進程發E消息如果沒有響應，P選舉獲勝如果有進程Q響應,則P結束，Q接管選舉并繼續下去。45656465629欺負（Bully）算法將進程進行排序45656465629環算法所有進程按邏輯或物理次序排序，形成一個環當一個進程P發現協調者C失效后，向后續進程發送E消息每個進程繼續向后傳遞E消息，直到返回PP在將新確定的協調者C’傳給所有進程5230環算法所有進程按邏輯或物理次序排序，形成一個環5230主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖31主要內容3.1時鐘同步313.4原子性（Atomic）事務原子性：組成原子事務的一組操作要么全部執行，要么一個也不執行，并且事務失敗后能返回到最初狀態例1：老式磁帶系統（備份）例2：匯款（提款存款）323.4原子性（Atomic）事務原子性：組成原子事務的事務模型穩定存儲器（StableStorage）：通過一對雙工磁盤實現33事務模型穩定存儲器（StableStorage）：33事務原語（1）BEGIN_TRANSACTION：標記一個事務的開始；（2）END_TRANSACTION：結束事務并設法提交；（3）ABORT_TRANSACTION：取消事務并恢復舊值；（4）READ：從一個文件（或其他類型的對象，如數據庫）讀取數據；（5）WRITE：將數據寫入一個文件（或其他類型的對象，如數據庫）34事務原語（1）BEGIN_TRANSACTION：標記一個事務舉例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

當第三個航班的機票預定失敗后事務中止預定三個航班機票：中轉站是JFK、Nairobi35事務舉例BEGINTRANSACTION預定三個航班機票：事務的特性

原子性（Atomic）：對外部世界來說，事務的發生是不可分割的；一致性（Consistent）：事務不會破壞系統的恒定；隔離性（Isolated）：并發的事務之間不會互相干擾；可串行性（Serializable）:多個事務并發執行的結果，與它們順序地執行效果相同。持久性（Durable）：一旦一個事務提交，它的更新結果不會因故障而丟失。36事務的特性原子性（Atomic）：對外部世界來說，事務的發隔離性（Isolated）37隔離性（Isolated）37事務的實現

私有工作空間與影子更新：當進程啟動事務T時，分配一個私有工作空間W，在提交或中止T前所有的讀寫操作都是在W中進行0‘3‘影子塊38事務的實現私有工作空間與影子更新：0‘3‘影子塊38先寫日志（WAL）就地更新（in-place）日志紀錄〈事務標識，文件標識，塊號，前像，后像〉例：39先寫日志（WAL）就地更新（in-place）39先寫日志協議回滾（Rollback）:反做（undo）廢棄事務的更新結果只有當日志成功地寫入穩存之后，才可以修改文件。如果事務執行成功并被提交，則它的提交記錄將被寫入日志。如果事務異常中止，則用日志來備份初始狀態。從日志的未尾開始，向回逐個讀取日志記錄，反做記錄中描述的修改，即回滾處理。在系統崩潰后,日志也可用來進行的恢復。40先寫日志協議回滾（Rollback）:40示例(a)一個事務(b)-(d)每條語句執行前的日志41示例(a)一個事務(b)-(d)每條語句執行前的兩階段提交協議（two-phasecommitprotocol）

準備階段：取得一致決定執行階段：執行命令（提交或廢棄）42兩階段提交協議（two-phasecommitproto并發控制(ConcurrencyControl)加鎖法正確性標準：可串行性（serializable）封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖封鎖的類型和相容性讀鎖(R)寫鎖(W)鎖的粒度細粒度：如字段粗粒度：如文件RWR√?W??43并發控制(ConcurrencyControl)加鎖法RW兩階段封鎖協議(2PL)恰好在需要或不再需要鎖時去請求或釋放鎖可能會導致不一致和死鎖？

加鎖階段開鎖階段嚴格的2PL與2PC結合避免級聯廢棄（cascadedabort)死鎖：等待圖（WFG）

檢查是否有環路

超時檢測（timeout)44兩階段封鎖協議(2PL)恰好在需要或不再需要鎖時去請求或釋放樂觀法(Optimistic)最適合于基于私有工空間的情況讀階段：將文件讀入私有工作區確認階段：提交前，檢查是否有沖突有，則廢棄事務，重啟。無，則提交事務寫階段：如可以提交，則將修改內容從私有工作區，寫入文件。45樂觀法(Optimistic)最適合于基于私有工空間的情況時間戳(Timestamp)每個事務的操作帶有該事務的時間戳每個文件帶有對它操作的最后一個提交事務的讀時間戳、寫時間戳算法：如果當前事務T的時間戳〉文件的時間戳，則執行；否則，廢棄T;46時間戳(Timestamp)每個事務的操作帶有該事務的時間戳時間戳法示例設有三個事務α，β，γ。T(α)<T(β)<T(γ)TT(φ)47時間戳法示例設有三個事務α，β，γ。T(α)<T(β)<T(三種方法比較并發度死鎖性能2PL低有中樂觀法高無高（廢棄度低時）時間印法較高無較高48三種方法比較并發度死鎖性能2PL低有中樂觀法高無高（廢棄度低主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖49主要內容3.1時鐘同步493.5分布式系統的死鎖處理通信死鎖和資源死鎖死鎖解決策略鴕鳥法：（忽略問題，留給用戶考慮）檢測法：（允許死鎖發生，在檢測到后想辦法恢復）預防法：（靜態的使死鎖在結構上是不可能發生的）避免法：（在運行中，通過仔細的分配資源以避免死鎖）實際在分布式系統中從來都不采用

銀行家算法[Dijkstra,1965]P<has,max>,free503.5分布式系統的死鎖處理通信死鎖和資源死鎖50檢測方法：集中式一臺中心機器擁有整個系統（所有資源圖的集合）的資源圖

進程-資源等待圖節點：進程P、資源R有向邊:(1)PR請求關系;(2)RP擁有關系;死鎖檢測協調者負責檢測死鎖資源圖的維護策略：當資源圖中，有一條邊加入/刪除時，通知協調者每個進程周期性地向協調者發送圖的更新消息協調者在需要時，向參入者請求51檢測方法：集中式一臺中心機器擁有整個系統（所有資源圖的集合）檢測方法：集中式舉例假死鎖問題：B釋放R,請求T。若請求T消息先到達協調者(a)機器0初始資源圖(b)機器1初始資源圖(c)協調者對系統的觀察(d)延遲信息后的系統情況

解決方案一：協調者確認（消息的全局時序）52檢測方法：集中式舉例假死鎖問題：B釋放R,請求T。若請求T消檢測方法：分布式Chandy－Misra－Haas分布式死鎖檢測算法，探測消息：〈阻塞Pid，請求Pid，接收Pid〉e.g.（0,2,3）,（0,4,6）,（0,5,7）,（0,8,0）構成死鎖53檢測方法：分布式Chandy－Misra－Haas分布式死鎖分布式深度限制算法（DWDL）90%的死鎖發生在兩個進程之間算法：//p1為請求者;L(p1)為p1的壽命1)if(waitQueue=p2->p1->p0)thenif(L(p1)<L(p2)orL(p1))<L(p0)thenrestartp1;elserestartp0;2)if(waitQueue=p1->p1'->p0)thenif(L(p'1)<L(p1)orL(p'1)<L(p0))thenrestartp'1;elserestartp0;3)if(waitQueue=p2->p1->p'1->p0)thenif(L(p1)<L(p2)orL(p1)<L(p0))thenrestartp1;elserestartp'1;54分布式深度限制算法（DWDL）90%的死鎖發生在兩個進程之間等-死算法(wait-die)設請求進程0的時間印t0,擁有資源的進程1的時間印t1如果t0<t1,0等待;否則，撤銷0分布式死鎖預防55等-死算法(wait-die)分布式死鎖預防55分布式死鎖的預防傷-等算法（wound-wait)設請求進程0的時間印t0,擁有資源的進程1的時間印t1如果t0<t1，撤銷1;否則，0等待56分布式死鎖的預防傷-等算法（wound-wait)56第3章分布式系統的同步

中國科技大學軟件學院丁箐57第3章分布式系統的同步中國科技大學軟件學院1主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖58主要內容3.1時鐘同步2主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖59主要內容3.1時鐘同步33.1時鐘同步分布式算法的特點相關信息散布在多個場地上每個進程只能基于本地信息做決定應避免因單點故障造成整個系統的失敗不存在公共時鐘或精確的全局時間603.1時鐘同步分布式算法的特點4時鐘同步問題例：makefile誤差時間output.o：cc–Coutput.c61時鐘同步問題例：makefile誤差時間output.o：邏輯時鐘計時器：石英晶體+計數器時鐘偏差（clockskew）邏輯時鐘：相對時間物理時鐘：真實時間“之前”關系:事件a在b之前出現，則aba為發送消息m，b為接收m，則ab具有傳遞性：ab,bc,則ac并發事件（concurrent）62邏輯時鐘計時器：石英晶體+計數器6Lamport算法對每一事件a，在所有進程中都認可給它分配一個時間值C(a）ifab;則C(a)<C(b)a,bC(a)C(b)C是遞增的校正算法ab，ifC(b)<C(a),則C(b)=C(a)+163Lamport算法對每一事件a，在所有進程中都認可給它分配一Lamport算法時間慢快慢快64Lamport算法時間慢快慢快8物理時鐘與現實時鐘（1）如何用現實世界的時鐘將它們同步起來；（2）如何使各時鐘之間保持同步。

太陽日：連續的兩次日中天的時間太陽秒：solar-day/86400平均太陽秒：如，格林威治時間65物理時鐘與現實時鐘（1）如何用現實世界的時鐘將它們同步起來；現實時鐘銫原子鐘：9192631770次躍遷=1秒TAI秒：國際原子時間UTC秒：世界時間（在TAI秒中加入閏秒）時間服務：WWV電臺、GEOS衛星102066現實時鐘銫原子鐘：9192631770次躍遷=1秒10201時鐘同步算法如何與現實時鐘同步如何使不同機器之間相互同步設機器時鐘值Cp(t),t為UTC時間最大偏移率精確時鐘：dC/dt=1快時鐘：dC/dt〉1慢時鐘：dC/dt<167時鐘同步算法如何與現實時鐘同步11Christian’s算法--逐步調整法時間服務器，可接受WWV的UTC時間每隔δ/2ρ校準時間（允許誤差δ，存在誤差ρ）兩個問題：時間決不能倒退,延遲假設：每秒產生100次中斷，每次中斷將時間加10毫秒若調慢時鐘，中斷服務程序每次只加9毫秒；若加快時鐘，則加11毫秒。傳播時間68Christian’s算法--逐步調整法時間服務器，Berkeley算法–主動式方法時間監控器定期查詢其他機器時間計算出平均值通知其他機器調整時間69Berkeley算法–主動式方法時間監控器定期查詢其他平均值算法–非集中式方法將時間劃分成固定長度的再同步間隔，第i次間隔開始于T0+iR，而結束于T0+(i+1)R所有機器廣播自己的時鐘時間啟動本地計時器收集在S時間間隔中到達的其他機器廣播的時間執行平均時間計算算法，得到新的時間值（取平均值，去掉兩端值）70平均值算法–非集中式方法將時間劃分成固定長度的再同步間隔多個外部時間源法例：OSFDCE方法接受所有時間源的當前UTC區間去掉與其他區間不相交的區間將相交部分的中點作為校準時間時間71多個外部時間源法例：OSFDCE方法時間15使用同步時鐘最多一次消息提交每個消息攜帶一個ID和一個時間印ts（timestamp）服務器的表T中，記錄每個連接C最近的時間印t如果到達的消息m，ts(m)<t,則拒絕m

服務器要一直保存一個全局變量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的時間印從表T中清除對于具有新的ID的到達消息m,如果ts(m)<G則拒絕m,否則，接受m按照一定時間間隔T，定期地將G寫入磁盤。當系統重啟后，G’=G+T72使用同步時鐘最多一次消息提交服務器要一直保存一個全使用同步時鐘基于時鐘的緩存一致性當客戶讀取一個副本到緩存時，設置一個租期（lease）在租期過期之前，客戶可更新副本，重續租期如果已經過期，緩存中的副本失效改進的一致性協議當客戶修改文件時，只需將所有沒有到期的緩存副本設為無效如果某個客戶崩潰，則等待直到該客戶的租期過期73使用同步時鐘基于時鐘的緩存一致性改進的一致性協議1主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖74主要內容3.1時鐘同步183.2互斥基本概念當一個進程使用某個共享資源，其他進程不允許對這個資源操作臨界區（CriticalSection）：對共享資源進行操作的程序段基本方法：信號量、管程問題：死鎖活鎖饑餓753.2互斥基本概念19集中式算法（仿照單處理機系統的方法）協調者：確定那個進程可進入臨界區通信量：3個消息：請求-許可-釋放缺點：單點失敗單協調者會成為執行的瓶頸

CCC76集中式算法（仿照單處理機系統的方法）協調者：確定那個進程可WinThread臨界區CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()77WinThread臨界區CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系統中所有事件都是全序的1.在一個進程P打算進入臨界區R之前，向所有其他進程廣播消息<臨界區R名、進程號、時間印>2.當一個進程P’收到消息后，做如下決定：若P’不在臨界區R中，也不想進入R，它就向P發送OK消息；若P’已經在臨界區R中，則不回答，并將P放入請求隊列；若P’也同時要進入臨界區R，但是還沒有進入時，則將發來的消息和它發送給其余進程的時間戳對比。如果P時間印小，則P發送OK消息;否則，不回答，并將P放入請求隊列；3.當P收到所有的OK消息后，進入R。否則，等待。4.當P退出R時，如果存在等待隊列，則取出請求者，向其發送OK消息。78分布式算法（Ricart-Agrawala算法）要求系統中所分布式算法舉例舉例：

共有0，1，2三個進程。進程0，2申請進入臨界區02002279分布式算法舉例舉例：共有0，1，2三個進程。0200222分布式算法評價缺點：n點失敗n點瓶頸2（n-1)個消息改進方案：超時重發組通信簡單多數同意比原來集中式算法慢，復雜，昂貴，而且不健壯。80分布式算法評價缺點：24令牌環算法構造一個邏輯環，得到令牌才可進入臨界區381令牌環算法構造一個邏輯環，得到令牌才可進入臨界區325三種互斥算法的比較算法每次進出需要的消息進入前的延遲（按消息次數）存在問題集中式32協調者崩潰分布式2（n-1）2（n-1）任何一個進程崩潰令牌環1到∞0到n-1丟失令牌，進程崩潰82三種互斥算法的比較算法每次進出進入前的延遲（按消息次數）存在主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖83主要內容3.1時鐘同步273.3選舉算法許多分布式算法需要一個進程充當協調者，發起者，排序者或其他特定的角色。作用：做出統一的的決定例如：確定協調者843.3選舉算法許多分布式算法需要一個進程充當協調者，發起欺負（Bully）算法將進程進行排序P向高的進程發E消息如果沒有響應，P選舉獲勝如果有進程Q響應,則P結束，Q接管選舉并繼續下去。45656465685欺負（Bully）算法將進程進行排序45656465629環算法所有進程按邏輯或物理次序排序，形成一個環當一個進程P發現協調者C失效后，向后續進程發送E消息每個進程繼續向后傳遞E消息，直到返回PP在將新確定的協調者C’傳給所有進程5286環算法所有進程按邏輯或物理次序排序，形成一個環5230主要內容3.1時鐘同步3.2互斥3.3選舉算法3.4原子性事務3.5分布式系統中的死鎖87主要內容3.1時鐘同步313.4原子性（Atomic）事務原子性：組成原子事務的一組操作要么全部執行，要么一個也不執行，并且事務失敗后能返回到最初狀態例1：老式磁帶系統（備份）例2：匯款（提款存款）883.4原子性（Atomic）事務原子性：組成原子事務的事務模型穩定存儲器（StableStorage）：通過一對雙工磁盤實現89事務模型穩定存儲器（StableStorage）：33事務原語（1）BEGIN_TRANSACTION：標記一個事務的開始；（2）END_TRANSACTION：結束事務并設法提交；（3）ABORT_TRANSACTION：取消事務并恢復舊值；（4）READ：從一個文件（或其他類型的對象，如數據庫）讀取數據；（5）WRITE：將數據寫入一個文件（或其他類型的對象，如數據庫）90事務原語（1）BEGIN_TRANSACTION：標記一個事務舉例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

當第三個航班的機票預定失敗后事務中止預定三個航班機票：中轉站是JFK、Nairobi91事務舉例BEGINTRANSACTION預定三個航班機票：事務的特性

原子性（Atomic）：對外部世界來說，事務的發生是不可分割的；一致性（Consistent）：事務不會破壞系統的恒定；隔離性（Isolated）：并發的事務之間不會互相干擾；可串行性（Serializable）:多個事務并發執行的結果，與它們順序地執行效果相同。持久性（Durable）：一旦一個事務提交，它的更新結果不會因故障而丟失。92事務的特性原子性（Atomic）：對外部世界來說，事務的發隔離性（Isolated）93隔離性（Isolated）37事務的實現

私有工作空間與影子更新：當進程啟動事務T時，分配一個私有工作空間W，在提交或中止T前所有的讀寫操作都是在W中進行0‘3‘影子塊94事務的實現私有工作空間與影子更新：0‘3‘影子塊38先寫日志（WAL）就地更新（in-place）日志紀錄〈事務標識，文件標識，塊號，前像，后像〉例：95先寫日志（WAL）就地更新（in-place）39先寫日志協議回滾（Rollback）:反做（undo）廢棄事務的更新結果只有當日志成功地寫入穩存之后，才可以修改文件。如果事務執行成功并被提交，則它的提交記錄將被寫入日志。如果事務異常中止，則用日志來備份初始狀態。從日志的未尾開始，向回逐個讀取日志記錄，反做記錄中描述的修改，即回滾處理。在系統崩潰后,日志也可用來進行的恢復。96先寫日志協議回滾（Rollback）:40示例(a)一個事務(b)-(d)每條語句執行前的日志97示例(a)一個事務(b)-(d)每條語句執行前的兩階段提交協議（two-phasecommitprotocol）

準備階段：取得一致決定執行階段：執行命令（提交或廢棄）98兩階段提交協議（two-phasecommitproto并發控制(ConcurrencyControl)加鎖法正確性標準：可串行性（serializable）封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖封鎖的類型和相容性讀鎖(R)寫鎖(W)鎖的粒度細粒度：如字段粗粒度：如文件RWR√?W??99并發控制(ConcurrencyControl)加鎖法RW兩階段封鎖協議(2PL)恰好在需要或不再需要鎖時去請求或釋放鎖可能會導致不一致和死鎖？

加鎖階段開鎖階段嚴格的2PL與2PC結合避免級聯廢棄（cascadedabort)死鎖：等待圖（WFG）

檢查是否有環路

超時檢測（timeout)100兩階段封鎖協議(2PL)恰好在需要或不再需要鎖時去請求或釋放樂觀法(Optimistic)最適合于基于私有工空間的情況讀階段：將文件讀入私有工作區確認階段：提交前，檢查是否有沖突有，則廢棄事務，重啟。無，則提交事務寫階段：如可以提交，則將修改內容從私有工作區，寫入文件。101樂觀法(Optimistic)最適合于基于私有工空間的情況時間戳(Timestamp)每個事務的操作帶有該事務的時間戳每個文件帶有對它操作的最后一個提交事務的讀時間戳、寫時間戳算法：如果當前事務T的時間戳〉文件的時間戳，則執行；否則，廢棄T;102時間戳(Timestamp)每個事務的操作帶有該事務的時間戳時間戳法示例設有三個事務α，β，γ。T(α)<T(β)<T(γ)TT(φ)103時間戳法示例設有三個事務α，β，γ。T(α)<T(β)<T(三種方法比較并發度死鎖性能2PL低有中