實時數(shù)據(jù)庫并發(fā)控制(數(shù)據(jù)庫)

時間：2022-11-12 22:30:01 | 來源：信息時代

時間：2022-11-12 22:30:01 來源：信息時代

    實時數(shù)據(jù)庫并發(fā)控制 : 實時數(shù)據(jù)庫中事務(wù)集的各數(shù)據(jù)操作執(zhí)行的排序,亦稱數(shù)據(jù)操作調(diào)度。與傳統(tǒng)數(shù)據(jù)庫一樣,實時數(shù)據(jù)庫并發(fā)控制是防止并發(fā)執(zhí)行的實時事務(wù)彼此相互干擾的一種功能,所不同的是其正確性準(zhǔn)則或協(xié)議不一樣。對實時數(shù)據(jù)庫而言,放松可串行化是必要的,其理由一方面如實時事務(wù)正確性所述; 另一方面來自實時應(yīng)用的數(shù)據(jù)往往是“短命”的,故可斷定由并發(fā)事務(wù)所引入的不一致性不會在數(shù)據(jù)庫中擴(kuò)展太大,即數(shù)據(jù)庫不會被廣泛地“污染”,而對局部的不一致性可使用像“補(bǔ)償事務(wù)”這樣的技術(shù)來補(bǔ)救,使得能很快恢復(fù)到一致狀態(tài)。因此,對于實時數(shù)據(jù)庫,并發(fā)控制技術(shù)分為可串行化和放寬可串行化兩種。
1.鎖式并發(fā)控制
傳統(tǒng)的鎖式協(xié)議2PL對實時數(shù)據(jù)庫是不夠的,可能遇到的兩個主要問題就是“優(yōu)先級顛倒”(低優(yōu)先阻塞高優(yōu)先)和死鎖。為此,人們開發(fā)了多種策略來解決這些問題,其典型的有:
(1)優(yōu)先級繼承: 當(dāng)發(fā)生優(yōu)先級顛倒時,讓“占有者”T_H獲得(即繼承)“請求者”T_R的優(yōu)先級,從而繼續(xù)執(zhí)行直到結(jié)束(提交或夭折)。它的問題是T_R被阻塞的時間可能會任意長,因為這種繼承性是傳遞的,潛在地存在對于T_R的阻塞鏈。
(2)低優(yōu)先級夭折:當(dāng)發(fā)生優(yōu)先級顛倒時,夭折低優(yōu)先級的T_H而讓高優(yōu)先級的T_R執(zhí)行。這種策略的問題是: ①對那些已執(zhí)行很長時間而還需執(zhí)行很短時間的T_H,夭折的代價很大,且重啟可能使T_H超截止期; ②重啟的T_H又可能(因優(yōu)先級被動態(tài)升高)夭折T_R,這樣就導(dǎo)致循環(huán)夭折。
(3)優(yōu)先級頂:其思想是為每一個數(shù)據(jù)設(shè)置一個“優(yōu)先級頂”,它為要存取該數(shù)據(jù)的所有事務(wù)的優(yōu)先級最高者。一個事務(wù)要獲得對一個數(shù)據(jù)的鎖,它的優(yōu)先級必須嚴(yán)格地高于當(dāng)前由其他事務(wù)鎖住的所有數(shù)據(jù)的最高優(yōu)先級頂,否則它被阻塞。該策略假定在每一事務(wù)執(zhí)行前就知道其要存取的數(shù)據(jù),并且對每一數(shù)據(jù)維護(hù)一個要存取它的各事務(wù)的ID及其優(yōu)先級的表。
(4)有序共享: 引入鎖之間的第三種(除共享、排他外)“有序共享”關(guān)系。例如,若事務(wù)T_i已具有數(shù)據(jù)對象O的一個讀鎖RL_{T_((i))}(O),現(xiàn)事務(wù)T_j請求加寫鎖WL_{T_((j))}(O),則建立了一個“有序共享關(guān)系”,而后允許WL_{T_((j))}(O)請求。為了保證可串行化,事務(wù)必須遵循有序共享規(guī)則: 若事務(wù)T_j獲得一個對于T_i具有有序共享關(guān)系的鎖,則對應(yīng)的T_j操作必須在T_i的以后執(zhí)行,且只有T_i結(jié)束(提交或夭折)后,T_j才能提交。
2. 時間戳排序并發(fā)控制
時間戳排序(timestamp ordering,TO)法的基本思想是:
(1)按系統(tǒng)時鐘或計數(shù)器為每一事務(wù)T_i賦一時間戳t_s(T_i)。所以,時間戳集是一全序集。
(2)若事務(wù)T_i請求的操作與T_j已在處理的一操作沖突,且t_s(T_i)<t_s(T_j),則T_i夭折。
(3)當(dāng)一事務(wù)夭折時,它必須以一新(即更大)的時間戳重新開始。
3. “樂觀”并發(fā)控制
“樂觀”并發(fā)控制法(optimistic concurrency control,OPT)假定事務(wù)很難發(fā)生沖突,因此讓其無阻礙地運行到全部操作完成,然后在提交時進(jìn)行檢驗,看是否曾發(fā)生過沖突并違反了可串行化要求。若通過了檢驗則提交; 否則就夭折。為此將一事務(wù)T_i的執(zhí)行分成三階段: 讀、驗證、寫。該策略的關(guān)鍵是如何驗證事務(wù),有兩種類型的驗證方法: ①向后驗證: 針對已提交的事務(wù)驗證; ②向前驗證: 針對活躍(尚在運行)的事務(wù)驗證,著名的OPTBC(OPTimistic Broadcasting Commit)就是其典型代表。還有一些變種策略,如OPT-WAIT-50(等待優(yōu)先級比它高的沖突事務(wù)的50%)。
4. ε-可串行化并發(fā)控制
ε-可串行化并發(fā)控制策略的關(guān)鍵是控制不一致性的允許度,稱為散度控制(divergence control,DC)。典型的DC方法有: ①兩段鎖散度控制(DC-2PL):擴(kuò)展2PL的鎖相容矩陣; ②時間戳排序散度控制(DC-TO):放寬按事務(wù)時間戳的大小來排序沖突操作的處理,并考慮其不一致性累計是否超限而決定沖突處理策略;③樂觀散度控制法(DC-OPT):基于通常的OPT方法,為每一數(shù)據(jù)維護(hù)一鎖表來控制不一致性。