基于時間戳的并發(fā)控制(數據庫)

時間：2022-12-27 08:30:01 | 來源：信息時代

時間：2022-12-27 08:30:01 來源：信息時代

    基于時間戳的并發(fā)控制 : 利用時間戳機制來控制多個事務的并發(fā)執(zhí)行,以保證該多個事務并發(fā)執(zhí)行的正確性。
時間戳(timestamp)是記錄計算機系統(tǒng)時間的一種方法,在計算機的操作系統(tǒng)、分布式系統(tǒng)、數據庫等多個領域中都有應用。在數據庫管理系統(tǒng)中時間戳是系統(tǒng)賦予事務的唯一的時間,以標記該事務開始執(zhí)行。時間戳可以是系統(tǒng)時鐘值,也可以是邏輯計數器的值。采用系統(tǒng)時鐘值時,要確保在一個時鐘周期內不會產生兩個相同的時間戳的值。采用計數器時,要設計好一種機制確保計數器能夠安全地重置。在集中式系統(tǒng)中,時間戳的設置比較簡單。但在分布式系統(tǒng)中,要維護一個全局一致的時間戳要復雜得多。
基于時間戳的并發(fā)控制方法的基本原理是: 系統(tǒng)以事先選定的事務次序(即按照事務時間戳的升序順序)作為串性化的判定標準,然后判定事務調度是否和這個串行執(zhí)行結果一致。如果某個事務的操作會違反這個次序,就迫使該事務“回滾”而不是等待。因此,也稱該方法為時間戳排序協議。
所謂“事務回滾”,就是終止事務,并采用一系列措施,消除該事務已經執(zhí)行的操作對數據庫造成的影響。直觀上看,采用回滾的辦法來進行事務調度的代價挺大,并發(fā)度不會高。但是,實際應用中真正產生沖突的還是少數情況,回滾現象并不多。
基于時間戳的協議,相關的記號如下:
TS(T): 表示事務T的時間戳。
TS(T_i)<TS(T_j):表示事務T_i在事務T_j之前開始執(zhí)行。
W-timestamp(Q):表示在數據項Q上成功執(zhí)行write(Q)操作的所有事務中的最大時間戳。
R-timestamp(Q):表示在數據項Q上成功執(zhí)行read(Q)操作的所有事務中的最大時間戳。
這是兩個系統(tǒng)全局變量,當系統(tǒng)成功執(zhí)行新的write(Q)或者read(Q)操作時,這些變量的值會被更新。
時間戳排序協議如下:
(1)假定事務T執(zhí)行操作read(Q),若TS(T)<W-timestamp(Q),表示事務T要讀入的數據項Q的值已經被執(zhí)行序列中更后面的事務寫過了,這時,應強迫T回滾; 若TS(T)≥W-timestamp(Q),這表明事務T可以讀這個Q的值,因此,執(zhí)行read(Q)操作,R-timestamp(Q)=max{R-timestamp(Q),TS(T)}。
(2)假定事務T執(zhí)行操作write(Q),若TS(T)<Rtimestamp(Q),表明數據項Q已經被執(zhí)行序列中更后面的事務讀過了,不能再執(zhí)行write(Q)操作了,因此,強迫T回滾; 若TS(T)<W-timestamp(Q),表明數據項Q已經被執(zhí)行序列中更后面的更新事務寫過了,不能再寫write(Q)了,因此,也要強迫T回滾。否則,執(zhí)行write(Q)操作,并令W-timestamp(Q)=TS(T)。
(3)被回滾的事務,系統(tǒng)重新賦予它新的時間戳,并重新啟動。
按照這個協議進行調度,結果一定和事務的時間戳順序一致,因為所有可能產生不一致的事務都被強制回滾了。在上述時間戳協議中,當TS(T)<Wtimestamp(Q)時,事務T的讀操作read(Q)因為它要讀取的值已被覆蓋而被拒絕執(zhí)行,系統(tǒng)強迫T回滾。如果每一個數據項的舊值副本被保存在系統(tǒng)中,這個問題就可以解決了。這個方案被稱為多版本并發(fā)控制(multiversion concurrency control)。