八分布式并發(fā)控制10

第八章

分布式并發(fā)控制兩段封鎖協(xié)議（2PL）基本的兩段封鎖協(xié)議嚴格的兩段封鎖協(xié)議（2PL）并發(fā)控制理論基礎(chǔ)事務(wù)執(zhí)行過程的形式化描述集中庫的可串行化問題

分布式事務(wù)的可串行化問題分布庫并發(fā)控制方法

牛牛文庫文檔分享

并發(fā)控制問題并發(fā)控制是分布式事務(wù)管理的基本任務(wù)之一，目的是保證分布式數(shù)據(jù)庫系統(tǒng)中的多個事務(wù)的高效并發(fā)執(zhí)行。多個事務(wù)并發(fā)執(zhí)行，就有可能產(chǎn)生操作沖突，如：出現(xiàn)重復(fù)讀錯誤或讀取了臟數(shù)據(jù)等，造成數(shù)據(jù)庫數(shù)據(jù)的不一致。并發(fā)控制確保事務(wù)滿足一致性和有效性?！?.1基本概念

牛牛文庫文檔分享（1）丟失修改錯誤初始x=100,若并行執(zhí)行，執(zhí)行結(jié)果為：T1：x=70；T2：x=70，最終結(jié)果x=70；結(jié)果導(dǎo)致T2的執(zhí)行結(jié)果破壞了T1執(zhí)行的結(jié)果，該種現(xiàn)象也稱丟失修改錯誤?！?.1基本概念

牛牛文庫文檔分享（2）重復(fù)讀錯誤例8.1.2有兩個并發(fā)執(zhí)行的事務(wù)T1和T2，其中x是數(shù)據(jù)庫中的一個屬性，T1和T2操作序列如下所示：如：一事務(wù)（如：T1）重復(fù)讀一數(shù)據(jù)項（x）時，得到不同的結(jié)果，該種現(xiàn)象稱重復(fù)讀錯誤。也稱一個事務(wù)的執(zhí)行受到了其它事務(wù)的干擾。§8.1基本概念

牛牛文庫文檔分享（3）讀臟數(shù)據(jù)錯誤例8.1.3有兩個并發(fā)執(zhí)行的事務(wù)T1和T2，其中x是數(shù)據(jù)庫中的一個屬性，

T1和T2操作序列如下所示：

可看到如下現(xiàn)象：事務(wù)T2讀取了T1廢棄的數(shù)據(jù)x，該種現(xiàn)象稱讀臟數(shù)據(jù)。應(yīng)盡量避免讀臟數(shù)據(jù)。因為，當事務(wù)T1廢棄時，T2也必須廢棄，即所謂的級聯(lián)廢棄。通常讀臟數(shù)據(jù)會導(dǎo)致級聯(lián)廢棄。

§8.1基本概念

牛牛文庫文檔分享

并發(fā)控制定義并發(fā)控制就是利用正確的方式調(diào)度并發(fā)操作，避免造成數(shù)據(jù)的不一致性，防止一個事務(wù)的執(zhí)行受到其它事務(wù)的干擾，保證事務(wù)并發(fā)執(zhí)行的可串行性。

§8.1基本概念鎖的基本思想是要求事務(wù)在對一數(shù)據(jù)項進行操作之前必須首先申請對該數(shù)據(jù)項進行加鎖，申請成功后才可對其操作。如果該數(shù)據(jù)項已被其它事務(wù)加鎖，則出現(xiàn)操作沖突，該事務(wù)必須等待，直到該數(shù)據(jù)項被解鎖為止?！?.2基本鎖的并發(fā)控制方法

牛牛文庫文檔分享

鎖的類型鎖一般分兩種類型，排它鎖（exclusive）和共享鎖（shared）。排它鎖常稱為X鎖或?qū)戞i；排它鎖指當事務(wù)T對數(shù)據(jù)A施加排它鎖之后，只允許事務(wù)T自己讀寫A，其它事務(wù)都不可讀寫A。共享鎖稱為S鎖或讀鎖。共享鎖指當事務(wù)T對數(shù)據(jù)A施加共享鎖之后，事務(wù)T和其它事務(wù)只能讀取A。即共享鎖允許多個事務(wù)同時訪問同一數(shù)據(jù)項A?！?.2基本鎖的并發(fā)控制方法

牛牛文庫文檔分享

封鎖規(guī)則事務(wù)在執(zhí)行過程中需對其訪問的數(shù)據(jù)項進行加鎖，訪問結(jié)束要及時釋放其對數(shù)據(jù)項加的鎖，以便供其它事務(wù)訪問，保證多個事務(wù)高度正確并行執(zhí)行。具體封鎖規(guī)則為：(1)

事務(wù)T在對數(shù)據(jù)項A進行讀/寫操作之前，必須對數(shù)據(jù)項A施加讀/寫鎖，訪問后立即釋放已申請的鎖；(2)如果事務(wù)T申請不到希望的鎖，事務(wù)T需等待，直到申請到所需要的鎖，之后方可繼續(xù)執(zhí)行

§8.2基本鎖的并發(fā)控制方法

牛牛文庫文檔分享

鎖的兼容性鎖一般分讀鎖和寫鎖。讀鎖是進行讀操作時加的鎖，允許多個事務(wù)同時完成讀操作，即具有共享性；寫鎖是進行寫操作時加的鎖，只允許申請該鎖的事務(wù)進行寫操作，所以，寫鎖不具有共享性，而具有排它性。寫鎖和讀鎖的相容性見下表：§8.2基本鎖的并發(fā)控制方法

牛牛文庫文檔分享

鎖的粒度封鎖數(shù)據(jù)對象的單位稱鎖的粒度，即指被封鎖的數(shù)據(jù)對象的大小。鎖的粒度也稱鎖的大小。系統(tǒng)根據(jù)自己的實際情況確定鎖的粒度，鎖的粒度可以是關(guān)系的字段屬性、關(guān)系的元組、關(guān)系（也稱文件）或整個數(shù)據(jù)庫等。鎖粒度的大小對系統(tǒng)的并發(fā)度和開銷有一定影響，鎖粒度越大，系統(tǒng)的開銷越小，但降低了系統(tǒng)的并發(fā)度。針對并發(fā)控制，系統(tǒng)的并發(fā)度與鎖粒度成反比。如下表所示：§8.2基本鎖的并發(fā)控制方法粒度開銷并發(fā)度小大高大小低

牛牛文庫文檔分享兩段封鎖協(xié)議（2PL）是數(shù)據(jù)庫系統(tǒng)中解決并發(fā)控制的重要算法之一。遵循兩段鎖協(xié)議規(guī)則的系統(tǒng)可保證事務(wù)的可串行性調(diào)度。兩段封鎖協(xié)議的實現(xiàn)思想是將事務(wù)中的加鎖操作和解鎖操作分兩階段完成，并要求并發(fā)執(zhí)行的多個事務(wù)要在對數(shù)據(jù)操作之前進行加鎖，且每個事務(wù)中的所有加鎖操作要在解鎖操作以前完成。§8.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享通常兩段封鎖協(xié)議分為基本的兩段封鎖協(xié)議和嚴格的兩段封鎖協(xié)議。在兩段封鎖協(xié)議實現(xiàn)中，系統(tǒng)的加鎖方式分兩種：顯示鎖方式，由系統(tǒng)加封鎖命令實現(xiàn)；隱式鎖方式，由系統(tǒng)自動加鎖實現(xiàn)。

§8.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享

基本的兩段封鎖協(xié)議基本的兩段封鎖協(xié)議的內(nèi)容分兩階段，加鎖階段和解鎖階段。具體規(guī)則描述如下：階段1：加鎖階段

?事務(wù)在讀寫一個數(shù)據(jù)項之前，必須對其加鎖；

?如果該數(shù)據(jù)項被其它使用者已加上不相容的鎖，則必須等待。階段2：解鎖階段

?事務(wù)在釋放鎖之后，不允許再申請其它鎖；§8.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享在事務(wù)執(zhí)行過程中，兩段封鎖協(xié)議（2PL）的加鎖、解鎖示意圖（圖8.1）如下：

§8.3兩段封鎖協(xié)議（2PL）基本的兩段封鎖協(xié)議(2PL)

牛牛文庫文檔分享（1）

避免丟失修改錯誤下圖描述了事務(wù)T1和T2并行執(zhí)行時產(chǎn)生了丟失修改錯誤。若采用兩段封鎖協(xié)議進行并行控制：

當事務(wù)T1、T2申請寫鎖時，均申請不到，必須等待，直到另一事務(wù)釋放對數(shù)據(jù)項x的鎖為止。如：T2廢棄，釋放讀鎖；則T1得到寫鎖，完成寫操作。事務(wù)T2重啟動后，讀取x(事務(wù)T1執(zhí)行的結(jié)果)，直至完成操作。因此，不會出現(xiàn)丟失修改錯誤?！?.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享

（2）

避免重復(fù)讀錯誤下圖描述了事務(wù)T1和T2并行執(zhí)行時產(chǎn)生了重復(fù)讀錯誤。若采用兩段封鎖協(xié)議進行并行控制：從上圖可見，當事務(wù)T2申請寫鎖時，不能申請成功，必等待，當事務(wù)T1再次讀數(shù)據(jù)項x時，讀取的x值與第一次讀到的值相同，不會出現(xiàn)重復(fù)讀錯誤。

§8.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享§8.3兩段封鎖協(xié)議（2PL）2PL不能避免級聯(lián)廢棄,為什么？

牛牛文庫文檔分享

嚴格的兩段封鎖協(xié)議（2PL）嚴格的兩段封鎖協(xié)議與基本的兩段封鎖協(xié)議內(nèi)容基本上是一致的，只是解鎖時刻不同。嚴格的兩段封鎖協(xié)議（2PL）是在事務(wù)結(jié)束時才啟動解鎖，保證了事務(wù)所更新數(shù)據(jù)的耐久性。采用兩段封鎖協(xié)議（2PL）的事務(wù)執(zhí)行過程為：begin_transaction→加鎖→操作→提交/廢棄（commit/abort）→解鎖?！?.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享提交/廢棄（commit/abort）時解鎖過程具體如下：（1）

對commit的處理?釋放讀鎖；?寫日志；?釋放寫鎖。（2）

對abort的處理?釋放讀鎖；?(反做)undo；?釋放寫鎖；§8.3兩段封鎖協(xié)議（2PL）

牛牛文庫文檔分享§8.3兩段封鎖協(xié)議（2PL）嚴格的兩段封鎖協(xié)議(2PL)

牛牛文庫文檔分享

事務(wù)執(zhí)行過程的形式化描述并發(fā)控制的主要目的是保證分布事務(wù)及分布式數(shù)據(jù)庫的一致性。并發(fā)控制既要實現(xiàn)分布事務(wù)的可串行性，又要保持事務(wù)具有良好的并發(fā)度。無論集中式數(shù)據(jù)庫，還是分布式數(shù)據(jù)庫的并發(fā)控制均是以串行化理論為基礎(chǔ)，并以它為模型來檢驗方法的正確性。按串行化理論，一個在數(shù)據(jù)庫上運行的事務(wù)的所有操作，按其性質(zhì)分為讀和寫兩類。通常，一個事務(wù)Ti對數(shù)據(jù)項x的讀操作和寫操作記為Ri(x)和Wi(x)。一個事務(wù)Ti所讀取數(shù)據(jù)項的集合，稱為Ti的讀集，所寫的數(shù)據(jù)項的集合，稱為的寫集，分別記為R(Ti)和W(Ti)?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享例8.4.1設(shè)有事務(wù)T1，完成的操作如下：T1：x=x+1；y=y+1；其中x、y為數(shù)據(jù)庫中的兩個數(shù)據(jù)項。則：T1的操作可表示為：R1(x)W1(x)R1(y)W1(y)；

R（T1）={x，y}；

W（T1）={x，y}；在一個數(shù)據(jù)庫上，各個事務(wù)所執(zhí)行的操作組成的序列，稱為事務(wù)的歷程，記為H，有時也稱調(diào)度（Schedule,也稱歷史history）。用于記錄各事務(wù)的操作順序。對于一個歷程上的任何兩個事務(wù)，Ti和Tj，如果Ti的最后一個操作在Tj的第一個操作之前完成，或反之，則稱該歷程為串行執(zhí)行的歷程，簡稱為串行歷程，否則稱為并行歷程。系統(tǒng)通常希望事務(wù)歷程中的各個事務(wù)是并發(fā)的，但同時又等價于一個串行的事務(wù)歷程，即事務(wù)歷程是可串行化的?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享例8.4.2設(shè)有事務(wù)T1和T2，T1和T2完成的操作為：T1：R1(x)R1(y)W1(x)W1(y)；T2：R2(x)W2(y)；設(shè)有：歷程H1和H2，H1和H2分別為：H1：R1(x)R1(y)W1(x)W1(y)R2(x)W2(y)H2：R1(x)R2(x)R1(y)W1(x)W1(y)W2(y)歷程H1和H2也可用下圖等價表示：在歷程H1中，事務(wù)T1的所有操作都是在事務(wù)T2的操作之前完成的，因此該歷程是串行歷程。而在歷程H2不滿足串行歷程的定義，因此是并行歷程。§8.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享

集中庫的可串行化問題無論在集中式數(shù)據(jù)庫系統(tǒng)中，還是在分布式數(shù)據(jù)庫系統(tǒng)中，事務(wù)的并發(fā)調(diào)度都要解決并行執(zhí)行事務(wù)對數(shù)據(jù)庫的沖突操作，使沖突操作串行執(zhí)行，非沖突操作并行執(zhí)行。只是在分布式數(shù)據(jù)庫系統(tǒng)中，事務(wù)是分解為各個場地上的子事務(wù)的執(zhí)行實現(xiàn)的。因此，分布式事務(wù)之間的沖突操作，轉(zhuǎn)化為了同一場地上的子事務(wù)的沖突操作，分布事務(wù)的可串行性調(diào)度轉(zhuǎn)化為了子事務(wù)的可串行性調(diào)度。下面先介紹可串行化涉及的概念，然后介紹集中庫的可串行化問題。 （1）可串行化定義定義在集中式數(shù)據(jù)庫系統(tǒng)中的一個歷程H，如果等價于一個串行歷程，則稱歷程H是可串行化的。由可串行化歷程H所決定的事務(wù)執(zhí)行順序，記為SR(H)?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享（2）事務(wù)的執(zhí)行順序事務(wù)的并發(fā)調(diào)度就是要解決并行執(zhí)行事務(wù)對數(shù)據(jù)庫的沖突操作。定義如果分別屬于兩個事務(wù)的兩個操作Oi和Oj，操作同一個數(shù)據(jù)項，且至少其中一個操作為寫操作，則Oi和Oj這兩個操作是沖突的。如：R1(x)W2(x)和W1(x)W2(x)均為沖突操作。若在一個串行歷程中，“<”表示先于關(guān)系，對分別屬于Ti和Tj的兩個沖突操作Oi和Oj，若存在Oi<Oj，則Ti<Tj?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享（3）

歷程等價的判別方法如果一個歷程H等價于一個串行歷程，則稱歷程H是可串行化的。判斷兩個歷程等價的定理和引理如下：定理8.1

對于任意兩個歷程H1和H2等價的充要條件為：①

在H1和H2中，每個讀操作讀出的數(shù)據(jù)是由相同的寫操作完成的；②

在H1和H2中，每個數(shù)據(jù)項上最后的寫操作是相同的。引理對于兩個歷程H1和H2，如果每一對沖突操作Oi和Oj，在H1中有Oi<Oj，在H2中也有Oi<Oj，則H1和H2是等價的?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享例8.4.3設(shè)有三個歷程H1、H2和H3，分別為：H1：R1(x)R1(y)W1(x)W1(y)R2(x)W2(x)；H2：R1(x)R1(y)W1(x)R2(x)W1(y)W2(x)；H3：R1(x)R1(y)R2(x)W1(x)W1(y)W2(x)。要求：判斷歷程H2和H3是否為可串行化的歷程。從上面的歷程H1中可看出，事務(wù)T1的所有操作都是在事務(wù)T2的操作之前完成的，因此可判斷，歷程H1是串行歷程。

§8.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享下面根據(jù)兩歷程等價引理分別判斷H2和H3是否與歷程H1等價，若等價，則該歷程是可串行化的歷程。判別如下：①

首先找出歷程H1、H2和H3的沖突操作；②

分別找出歷程H2和H3中與歷程H1的等價沖突操作，用“”表示。則結(jié)果有如下所示：H2的沖突操作H1的沖突操作H3的沖突操作

R1(x)<W2(x)R1(x)<W2(x)R1(x)<W2(x)W1(x)<

R2(x)W1(x)<

R2(x)

R2(x)

<W1(x)W1(x)<

W2(x)W1(x)<W2(x)W1(x)<

W2(x)

可知，歷程H2與歷程H1等價，因此歷程H2是可串行化的歷程；歷程H3與歷程H1不等價，因此歷程H3不是可串行化的歷程?！?.4并發(fā)控制理論基礎(chǔ)H1：R1(x)R1(y)W1(x)W1(y)R2(x)W2(x)；H2：R1(x)R1(y)W1(x)R2(x)W1(y)W2(x)；H3：R1(x)R1(y)R2(x)W1(x)W1(y)W2(x)。

牛牛文庫文檔分享3、分布式事務(wù)的可串行化問題定義在分布式事務(wù)執(zhí)行過程中，每個場地Si上的子事務(wù)執(zhí)行序列，稱為局部歷程，用H（Si）表示。在分布式數(shù)據(jù)庫系統(tǒng)中，將分布事務(wù)的可串行性調(diào)度轉(zhuǎn)化為了以場地為基礎(chǔ)的子事務(wù)的可串行性調(diào)度。用下面定理或引理判斷分布式事務(wù)是否是可串行化的?！?.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享定理

對于n個分布式事務(wù)T1、T2、…

Tn在m個場地上S1、S2、…

Sm上的并發(fā)執(zhí)行，記為E。如果E是可串行化的，則必須滿足以下條件：（1）

每個場地Si上局部歷程H（Si）是可串行化的；（2）存在E的一個總序，使得在總序中，如果有Ti<Tj，則在各局部歷程中必須有Ti<Tj。引理

設(shè)T1、T2、…

Tn是n個分布式事務(wù)，E是這組事務(wù)在m個場地上的并發(fā)執(zhí)行，H（S1）、H（S2）、…

H（Sm）是在這些場地上事務(wù)的局部歷程，如果E是可串行化的，則必須存在一個總序，使得對Ti和Tj的任兩個沖突操作Oi和Oj，如果在H（S1）、H（S2）、…

H（Sm）中有Oi<Oj，當且僅當在總序中有Ti<Tj。§8.4并發(fā)控制理論基礎(chǔ)

牛牛文庫文檔分享并發(fā)控制既要實現(xiàn)分布事務(wù)的可串行性，同時又要保持事務(wù)具有良好的并發(fā)度，保證分布事務(wù)及分布式數(shù)據(jù)庫的一致性。在分布式數(shù)據(jù)庫系統(tǒng)中，常常采用嚴格的兩段封鎖協(xié)議（2PL）實現(xiàn)并發(fā)控制，另外，還有多版本的時間印方法及樂觀方法。下面介紹兩段封鎖協(xié)議（2PL）的幾種封鎖方法。1、

集中式實現(xiàn)方法集中式實現(xiàn)方法是在分布庫中設(shè)立一個2PL調(diào)度器，所有封鎖請求均由該調(diào)度器完成。該種實現(xiàn)方法實現(xiàn)簡單，但存在易受調(diào)度器所在場地故障影響和需要大量通訊費用的不足。§8.5分布庫并發(fā)控制方法

牛牛文庫文檔分享

集中式實現(xiàn)方法只有一個2PL調(diào)度器，鎖由集中式封鎖管理器提供數(shù)據(jù)處理在參與者場地§8.5分布庫并發(fā)控制方法ParticipatingsitesCoordinatingTMCentralSiteLM(1)LockRequest(2)LockGranted(3)Operation(4)EndofOperation(5)ReleaseLocks

牛牛文庫文檔分享

分布式實現(xiàn)方法分布式實現(xiàn)方法是在每個場地上都有一個2PL調(diào)度器，每個調(diào)度器處理本場地上的封鎖請求。該種實現(xiàn)方法避免了集中式實現(xiàn)方法存在的不足，但同時也增加了實現(xiàn)全局調(diào)度的復(fù)雜性。Communicationstructure:§8.5分布庫并發(fā)控制方法CoordinationTMParticipatingLMsParticipatingDPs(1)LockRequest(2)Operation(3)EndofOperation(5)ReleaseLocks

牛牛文庫文檔分享

對復(fù)制數(shù)據(jù)的封鎖方法在分布式數(shù)據(jù)庫中，為提高系統(tǒng)的有效性、可靠性及存取效率，常在多個場地上存放多個數(shù)據(jù)庫的副本，當系統(tǒng)的某一或多個場地發(fā)生故障時，可通過其它場地上的數(shù)據(jù)副本完成數(shù)據(jù)處理。但同時也增加了系統(tǒng)選擇副本及處理多副本更新等相應(yīng)處理功能，即增加了系統(tǒng)的復(fù)雜性。通常多副本的并發(fā)控制方法分為基于特定副本的封鎖方法和基于投票的封鎖方法。基于特定副本的封鎖方法又分為主副本法、主場地法和后備場地的主場地法；基于投票的封鎖方法分為讀—寫全法和多數(shù)副本法。

§8.5分布庫并發(fā)控制方法

牛牛文庫文檔分享

(1)基于特定副本的封鎖方法①主副本法主副本法規(guī)定每一數(shù)據(jù)項在某個場地上的副本為主副本，通常主副本選擇在用戶申請封鎖某數(shù)據(jù)項較多的場地，該場地也稱為主場地。所有封鎖申請由主副本所在場地的鎖管理器LM（lockmanager）完成。采用主副本法，降低了通信費用，但也降低了并發(fā)程度?！?.5分布庫并發(fā)控制方法

牛牛文庫文檔分享②主場地法主場地法規(guī)定保存副本的某個場地為主場地，所有封鎖申請由主場地的鎖管理器LM（lockmanager）完成。即系統(tǒng)中的所有封鎖申請都要傳到主場地，由主場地決定是否同意封鎖請求。由于在主場地法中，所有鎖申請由一個場地處理，易形成瓶頸，當主場地出故障時，整個系統(tǒng)將癱瘓。③后備場地的主場地法為防止主場地故障，設(shè)立另一個場地為后備主場地，當主場地發(fā)生故障后，由后備主場地頂替主場地。

§8.5分布庫并發(fā)控制方法

牛牛文庫文檔分享(2)基于投票的封鎖方法①讀—寫全法讀—寫全法指當事務(wù)對某一數(shù)據(jù)項加鎖時，若為讀鎖，只需封鎖其中一個副本，即只需向選中的副本所在場地發(fā)送鎖申請報文；若為寫鎖，必須封鎖所有副本，即需要向所有存有該數(shù)據(jù)項的副本所在場地發(fā)送鎖申請報文。因此，在寫鎖情況下通信費用較大，為避免該不足，提出了多數(shù)法。②多數(shù)副本法多數(shù)副本法是指在對數(shù)據(jù)項進行加鎖時，必須封鎖數(shù)據(jù)項一半以上的副本。無論讀鎖還是寫鎖申請，都要向n個副本中的至少(n+1)/2個副本所在場地發(fā)加鎖請求。申請成功后，若為讀鎖，讀取一個副本的值；若為寫鎖，需向n個副本發(fā)送新值?！?.5分布庫并發(fā)控制方法

牛牛文庫文檔分享并發(fā)控制算法分類§8.5分布庫并發(fā)控制方法

牛牛文庫文檔分享

鎖方法通過鎖的互斥維護可串行性.Timestampmethodmaintainsserializabilitybyassigningauniquetimestamptoeverytransactionandexecutingtransactionsaccordingly.Whatisatimestamp?l

anidentifierfortransactionl

usedtopermitorderingl

monotonicity–timestampsgeneratedbythesameTMaremonotonicallyincreasedinvalues.

§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享Howtoassignatimestampvalue

l

useamonotinicallyincreasingcounter,butthisisdifficultindistributedenvironmentl

useatwo-tupleform<local-counter-value,site-identifier>l

use<local-system-clock,site-identifier>NotesiteIDisputintheleastsignificantpositiontoavoidthesituationthattimestampsfromasitewillalwaysbelarger/smallerthantimestampsfromanothersite.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享ts(Ti)–thetimestampvalueoftransactionTi.

HowtoschedulebytheTORule:Checkeachnewoperationagainstconflictingoperationsthathavebeenscheduled.IfthenewoperationbelongstoayoungertransactionthanALLconflictingones,thenacceptit;otherwiserejectitandtheentiretransactionhastorestartwithanewtimestamp.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享Thismeansthesystemmaintainstheexecutionorderaccordingtothetimestampsorder.

TMisresponsibleforassigningatimestamptoeachtransactionandattachittoeachdatabaseoperation.

TwotimestampsmaintainedbyDBMSforeachdataitemxforscheduling:

[rts(x)]:thelargestoftimestampsoftransactionsthathavereadx.

[wts(x)]:thelargestoftimestampsoftransactionsthathavewrittenx.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享Principleofbasictimestampalgorithm

§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享Principleofbasictimestampalgorithm

HowtomaintaintimestampsamongsitesWhents(T)<rts(x),thereadisrejected.

Site2adjustsitstimestampbymakingitlargerthanrts(x)andrestart.

Why?Avoidts(site1)>>ts(site2)whichmaymakeoperationsfromsite2nevergetexecuted.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享ConservativeTOAlgorithmBasicTOalgorithm:deadlockfreebuttoomanyrestarts.ConservativeTOalgorithmdelayseachoperationuntilthereisanassurancethatnooperationwithsmallertimestampscanarriveatthatscheduler.Basictechnique

atsitei,eachschedulerihasonequeueQijforeachTMatsitejinthesystemanoperationfromTMjisplacedinQijinincreasingtimestamporder.ScheduleriexecutesoperationfromALLqueuesinthisorderalso.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享ConservativeTOAlgorithmThisreducesthenumberofrestarts.Butrestartmayoccurwhenaqueueisempty.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享ConservativeTOAlgorithmSupposeQ23isemptyandscheduler2choosesanoperationopfromQ21andQ22.Butlateraconflictingoperationwithsmallertimestampthants(op)fromsite3arrives,thenthisoperationmustberejectedandrestarted!Toimprove,useextremelyconservativealgorithmcomplementedbyineachqueuethereisatleastoneoperation,orifaTMdoesnothaveatransactiontoprocess,ithastosendamessageperiodicallytoinformthatinthefutureitwillsendtimestamplargerthanthatofthemessage.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享ConservativeTOAlgorithmExtremelyconservativealgorithmactuallyexecutestransactionseriallyateachsite.Tooconservative!Anoperationmayhavetowaitforthecomingofayoungeroperationofanemptyqueue–

adelayproblem!Improvement:definetransactionclassesandsetaqueueforeachclassinsteadofeachTM.Transactionclassesaredefinedbytheirreadsetandwriteset.Ifatransaction’sreadsetandwritesetaresubsetofaclass,thenthetransactionbelongstothatclass.

Itisdifficulttodefinetransactionclasses!§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享MultiversionTOAlgorithm

Eachwritecreatesanewversionofthedataitemtobeupdated.Versionsaretransparenttousers.

Transactionsareprocessedonastateofdatabasethatitwouldhaveseeniftheywereexecutedseriallyintimestamporder.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享MultiversionTOAlgorithm§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享OPTIMISTICCONCURRENCYCONTROLALGORITHMS悲觀算法假設(shè)沖突經(jīng)常發(fā)生，而樂觀算法等到寫階段開始時，才進行沖突驗證.§8.6基于時間印的并發(fā)算法悲觀算法樂觀算法

牛牛文庫文檔分享OPTIMISTICCONCURRENCYCONTROLALGORITHMSConceptsofoptimisticalgorithms

Timestampsareonlyassociatedwithtransactions,butnotwithdataitems.Timestampsareassignedatthebeginningofvalidationphase,butnottheinitializationoftransactions.§8.6基于時間印的并發(fā)算法

牛牛文庫文檔分享OPTIMIST