可串行性(數(shù)據(jù)庫)

時間：2022-12-31 00:30:01 | 來源：信息時代

時間：2022-12-31 00:30:01 來源：信息時代

    可串行性 : 度量事務并發(fā)調度的一個屬性,被用于作為事務并發(fā)調度正確與否的標準。如果一個事務并發(fā)調度的結果與某個串行調度的結果是一樣的,就稱這個調度滿足可串行性。
讓多個數(shù)據(jù)庫事務同時執(zhí)行,無疑會提高數(shù)據(jù)庫系統(tǒng)的事務處理吞吐量。但是,多個事務的交叉執(zhí)行,意味著多個事務可以同時存取數(shù)據(jù)庫中的數(shù)據(jù),彼此之間可能產生相互干擾,從而可能破壞數(shù)據(jù)庫的一致性。為此,需要為事務并發(fā)執(zhí)行定義一個正確性標準。事務的隔離性要求事務在有其他事務干擾下的執(zhí)行效果和沒有其他事務存在下的執(zhí)行效果是一樣的,這意味著事務的任何串行執(zhí)行的結果都是正確的。因此,一個合適的正確性調度的定義可以是: 如果n個事務的某個并發(fā)執(zhí)行調度的效果和這n個事務的某個串行調度的執(zhí)行效果是一樣的,那么這個并發(fā)調度就是正確的,也稱這個調度滿足可串行性或是可串行化調度。但是,由于n個事務有n!種可能的串行調度,不可能事先計算所有不同的串行調度的結果,因此,事物調度的正確性還需要其他可操作更強的定義,這就是沖突可串行性的。可以通過一個基于優(yōu)先圖的簡單算法來判定一個并發(fā)調度是否正確。必須說明的是,沖突可串行性是事務并發(fā)調度正確性的充分條件,并不是必要條件。因此,尋找那些比沖突可串行化更弱的條件或者給出并發(fā)調度的充分必要條件是有意義的,視圖可串行化是在這個方面的一個嘗試。
1. 可串行化調度
滿足可串行性的事務并發(fā)調度就稱為可串行化調度(seralizable schedule)。例說,考慮銀行中的轉賬業(yè)務。設事務T₁從賬戶A轉5000元到賬戶B,事務T₂從賬戶A轉其余額的10%到賬戶B。兩個事務的操作序列如下:

T1:Read(A); A:=A-5000; Write(A); Read(B); B:=B+5000; Write(B);

T2:Read(A); temp:=A*0.1; A:=A-temp; Write(A); Read(B); B:=B+temp; Write(B);

設賬戶A和B的初值分別為10000元和20000元。先執(zhí)行T₁后執(zhí)行T₂的串行調度如圖1所示,賬戶A和B的最終余額分別為4500元和25500元。

T1	T2
Read(A) A:=A-5000 Write(A) Read(B) B:=B+5000 Write (B)
	Read (A) temp:=A*0.1 A:=A-temp Write (A) Read(B) B:=B+temp Write (B)

圖1 串行調度1: 先T₁后T₂

先執(zhí)行T₂后執(zhí)行T₁的串行調度如圖2所示,賬戶A和B的最終余額分別為4000元和26000元。雖然兩種調度的結果(賬戶余額)不同,但是這兩種串行調度方式都保持了賬戶A和B的資金總和(30000元)不變。

T1	T2
	Read(A) temp:=A*0.1 A:=A-temp Write (A) Read (B) B:=B+temp Write (B)
Read (A) A:=A-5000 Write(A) Read(B) B:=B+5000 Write (B)

圖2 串行調度2: 先T₂后T₁

這兩種串行執(zhí)行結果都是正確的。但當事務并發(fā)調度時,情況就變得復雜得多。一種可能的并發(fā)調度如圖3所示,它的執(zhí)行結果與圖1的串行調度結果一致,賬戶A和B的終值分別為4500元和25500元。即圖3所示的并發(fā)調度與圖1所示的串行調度是結果等價的。

T1	T2
Read(A) A:=A-5000 Write(A)
	Read(A) temp:=A*0.1 A:=A-temp Write (A)
Read (B) B:=B+5000 Write (B)
	Read(B) B:=B+temp Write(B)

圖3 可串行化的并發(fā)調度

另一種可能的并發(fā)調度如圖4所示,當它執(zhí)行完后,賬戶A和B的終值分別為5000元和21000元,A和B之和為26000元。兩個事務執(zhí)行后賬戶A和B的總和未能保持不變,因此,這個調度是不正確的。

T1	T2
Read(A) A:=A-5000
	Read(A) temp:=A*0.1 A:=A-temp Write(A) Read(B)
Write(A) Read (B) B:=B+5000 Write (B)
	B:=B+temp Write(B)

圖4 不可串行化的并發(fā)調度

2. 沖突可串行化
沖突可串行化(conflict serializability)是判斷某一個并發(fā)調度是否正確的操作性定義。它通過調換操作序列中不沖突操作對來變換調度,如果能夠通過這樣的變換形成一個串行調度,那么這個并發(fā)調度就是沖突可串行化調度。
考慮到事務中對數(shù)據(jù)庫有影響的操作是read和write語句,因此可以把事務抽象成只有read和write語句組成的操作序列,同樣并發(fā)調度也可以抽象為讀寫操作的序列。例如,圖3所示的調度S₁可以簡單表達為如下的操作序列:S₁＝R₁(A)W₁(A)R₂(A)W₂(A)R₁(B)W₁(B)R₂(B)W₂(B)。
其中,read操作簡寫為R,write操作簡寫為W,下標表示該操作所屬事務號,操作的數(shù)據(jù)對象寫在括號中。
不同事務的一對操作,如果作用在同一個數(shù)據(jù)對象上,就可能造成沖突(conflict)。有兩種類型的沖突: 讀-寫沖突(即R_i(x)和W_j(x)之間)和寫-寫沖突(即W_i(x)和W_j(x)之間)。沖突操作的執(zhí)行次序會影響執(zhí)行的結果,例如,如果R_i(x)在W_j(x)之前,則事務S_i讀的是S_j寫前x的舊值; 如果R_i(x)在W_j(x)之后,則S_i讀的是S_j寫后x的新值。
不沖突的操作對也可以分為兩類: 一是讀操作對,如R_i(x)和R_j(x);二是雖然有寫操作,但作用的數(shù)據(jù)對象不同,如R_i(x)和W_j(y)。顯然事務調度中相鄰的不沖突操作的次序可以互相調換,不會影響執(zhí)行的結果。注意,假定同一個事務中的操作順序是不能調換次序的。
如果調度S′是從調度S通過調換一系列相鄰的不沖突操作的次序得到,那么稱S′和S是一對“沖突等價”的調度。如果調度S與某個串行調度是“沖突等價”的,那么稱調度S是“沖突可串行化”的調度。
例如,對圖3中的并發(fā)調度S₁可以按下列步驟通過調換相鄰的不沖突操作得到一個沖突等價的串行調度S₁′:
S₁→R₁(A)W₁(A)R₂(A)R₁(B)W₂(A)W₁(B)R₂(B)W₂(B)→R₁(A)W₁(A)R₁(B)R₂(A)W₂(A)W₁(B)R₂(B)W₂(B) →R₁(A)W₁(A)R₁(B)R₂(A)W₁(B)W₂(A)R₂(B)W₂(B) →R₁(A)W₁(A)R₁(B)W₁(B)R₂(A)W₂(A)R₂(B)W₂(B)=S₁′。S₁′是先執(zhí)行事務T₁再執(zhí)行事務T₂的一個串行調度(即圖1對應的調度),故并發(fā)調度S₁是沖突可串行化的。
3.沖突可串行化調度的判斷
將調度S轉化成有向圖表示,稱為優(yōu)先圖(precedence graph),記為G(S)=(V,E),其中V是結點的集合,它包含所有參與調度的事務; E是邊的集合,可以通過分析S中的沖突操作來確定每條邊。如果下列條件之一成立,則在E中添加一條邊T_i→T_j:
調度S中,沖突操作R_i(x)在W_j(x)之前;
調度S中,沖突操作W_i(x)在R_j(x)之前;
調度S中,沖突操作W_i(x)在W_j(x)之前。
如此構成的優(yōu)先圖中若有回路,則S顯然不可能沖突等價于任何串行調度;如果優(yōu)先圖中無回路,則可以采用拓撲排序,得到一個等價的串行調度。
拓撲排序的方法如下: 由于圖中無回路,必然存在入度為0的結點,可將這個結點及其發(fā)出的邊從圖中移去,并且把這個結點存放在一個先進先出隊列中(若有多個這樣的結點,其存放次序任意)。對所剩的圖作相同的處理,如此繼續(xù)進行,直到所有結點都移入隊列為止。按隊列中結點次序串行安排相應各事務的操作,就可以得到一個沖突等價的串行調度。
例如,判定由四個事務構成的調度S₂＝W₃(y)R₁(x)R₂(y)W₃(x)W₂(x)W₃(z)R₄(z)W₄(x)的沖突可串行化的步驟如下: 首先分別分析對數(shù)據(jù)對象x,y,z的所有操作。對每一對沖突操作,按其在S₂中執(zhí)行的先后順序,在優(yōu)先圖中添加相應的邊。如此可得圖5所示的優(yōu)先圖。

圖5 優(yōu)先圖

由于優(yōu)先圖中無回路,調度S₂是沖突可串行化的調度。按照拓撲排序算法,可以得到結點的隊列為T₁,T₃,T₂,T₄。因此得到S₂的沖突等價串行調度S₂′:S₂′=R₁(x)W₃(x)W₃(x)W₃(z)R₂(y)W₂(x)R₄(z)W₄(x)。
必須說明的是,盡管運用優(yōu)先圖判定辦法能檢驗給定調度是否沖突可串行化,但是在實際運行時,由于事務是隨機到達的,而且還和事務的執(zhí)行情況(例如等待CPU還是等待I/O等)等諸多因素有關,不可能事先制定好一個調度然后交給系統(tǒng)執(zhí)行。因此,沖突可串行化的意義還是限于事務理論上的研究。比較實際的方法是讓DBMS按一定的并發(fā)控制協(xié)議調度事務,只要保證按照這個協(xié)議生成的調度能夠保證其執(zhí)行是可串行化就可以了,而不必關心其具體的調度。
4.視圖可串行化
如果將沖突可串行化調度和可串行化調度記為兩個集合Sc和S,那么Sc是S的真子集。是否存在比Sc大但是比S小的集合呢?顯然尋找這樣的集合是有意義的。先看一個例子:
設有并發(fā)調度S₃＝R₁(x)W₂(x)W₁(x)W₃(x)。在S₃中,三個事務之間的操作都是沖突的,不可能通過交換不沖突操作次序而獲得串行調度,因而S₃不是沖突可串行化的。但是卻可以找到一個串行調度S₃′=R₁(x)W₁(x)W₂(x)W₃(x),比較S₃和S₃′可見,兩個調度中的R₁(x)讀的值是相同的,W₁(x)和W₂(x)在次序上調換了,雖然會影響x的中間值,但x的終值仍由W₃(x)決定,與x在W₃(x)之前所取的值無關。調度S₃和S₃′的執(zhí)行效果是完全一樣的,因此是等價的調度。這種等價性稱之為視圖等價。
如果兩個調度S和S′,在數(shù)據(jù)庫的任何初始狀態(tài)下,所有讀出的數(shù)據(jù)都是一樣的,同時最后寫數(shù)據(jù)庫中數(shù)據(jù)對象的事務也是一樣的,則稱S和S′是“視圖等價”的調度。如果調度S與某個串行調度是“視圖等價”的,那么稱調度S是視圖可串行化(view serializability)調度。視圖可串行化調度是一種比“沖突可串行化”定義要寬松一些的另一種可串行化調度。
可以證明: 每個沖突可串行化的調度都是視圖可串行化的調度; 但每個視圖可串行化的調度不一定是沖突可串行化的調度。
雖然,視圖可串行化比沖突可串行化更加普遍,但是其測試卻是NP完全問題,而且也沒有找到可保證視圖可串行化的簡單的生成規(guī)則或協(xié)議,因而并不實用。沖突可串行化覆蓋了絕大部分可串行化的實例,且測試方法簡單,在DBMS中也很容易實現(xiàn),因此是目前商用DBMS中普遍采用的并發(fā)控制的正確性準則。在一般文獻中,若不特別聲明,可串行化都指沖突可串行化。