基於時間戳的並發控制

在計算機科學中，基於時間戳的並發控制算法是一種樂觀的並發控制方法。它在某些數據庫中用於使用時間戳安全處理交易。

手術

假設

  • 每個時間戳值都是唯一的，並且準確地表示時間瞬間。
  • 高價值的時間戳時間比低價值的時間戳更晚。

產生時間戳

已經使用了多種不同的方式來生成時間戳

  • 在交易開始時，將系統時鐘的值作為時間戳。
  • 使用在交易開始時將其作為時間戳的線程安全的共享計數器。
  • 上述兩種方法的組合。

正式的

每次交易（ ）是一個有序的操作列表（ ）。在交易執行第一個訴訟之前（ ），它標有當前的時間戳或任何其他嚴格有序的順序： 。每次交易也都會給出一組空的交易集，以依賴於此 ，以及最初更新的舊對象集 。

每個對象在數據庫中，給出了兩個時間戳字段，除了並發控制以外，沒有使用： 是通過事務上次讀取對象值的時間， 是對象的值最後更新的時間。

對全部 ：

對於每個動作 ：
如果希望閱讀的價值 ：
如果然後流產（最近的線程已覆蓋了該值），
否則更新依賴項集並設置 ;
如果希望更新的價值 ：
如果然後流產（最近的線程已經依靠舊值），
如果然後跳過（托馬斯寫規則），
否則存儲以前的值， ， 放 ，並更新 。
雖然有交易尚未結束：等等
如果有交易流產然後中止
否則：提交。

流產：

每個在
如果等於然後還原和

非正式

每當啟動交易時，它都會收到時間戳。交易的時間戳指示何時開始交易。這些時間戳確保交易以相同的時間戳的相同順序影響每個對象。因此，給定兩個操作，這些操作會影響不同交易的同一對象，因此交易與較早的時間戳的操作必須在使用後期時間戳進行交易之前執行。但是，如果實際上首先提出了錯誤的交易的操作，則該交易將被中止，並且必須重新啟動交易。

數據庫中的每個對像都有一個讀取時間戳，每當讀取對象的數據時會更新，並且在對象的數據更改時會更新的寫入時間戳。

如果交易想讀取對象，

  • 但是事務開始在對象寫入時間戳之前，這意味著事務開始後有些東西更改了對象的數據。在這種情況下，交易將被取消，必須重新啟動。
  • 交易開始於對象的寫入時間戳之後，這意味著讀取對像是安全的。在這種情況下，如果事務的時間戳是對象的讀取時間戳之後，則將讀取時間戳設置為交易時間戳。

如果交易想寫入對象，

  • 但是交易開始於對象的讀取時間戳之前，這意味著某些東西已經查看了對象，我們假設它拿了對像數據的副本。因此，我們無法將其寫入對象，因為這將使任何復制的數據無效，因此交易被中止，必須重新啟動。
  • 交易開始於對象的寫入時間戳之前，這意味著自我們開始交易以來，某些東西改變了對象。在這種情況下，我們使用托馬斯寫規則，只是跳過我們的寫操作並按照正常狀態繼續；交易不必流產或重新啟動
  • 否則，事務將寫入對象，並且對象的寫入時間戳設置為交易時間戳。

身體上無法實現

如果交易的結果如果交易是瞬時的，則該行為在物理上是無法實現的。以下是導致身體上無法實現的行為的僅有的兩種情況：

  1. 事務t嘗試讀取x，但ts（t）<wt（x）。原因：這意味著X開始後由另一筆交易寫信。
  2. 交易t試圖寫x，但ts（t）<rt（x）。原因：這意味著以後的交易讀取X之前。

可恢復性

有關可回收（ RC ）術語的說明，請避免級聯的中止（ ACA ）和嚴格（ ST ），請參見數據庫交易時間表。

請注意，以其基本形式的時間戳訂購不會產生可回收的歷史。例如，考慮以下交易歷史記錄和 ：

這可能是由調度程序生產的，但無法恢復，因為即使從未進行的交易中閱讀。為了確保其產生可恢復的歷史記錄，調度程序可以保留每個交易已讀取的其他交易的列表，而不是在此列表之前讓交易提交僅由僅由承諾的交易組成。為了避免級聯流產，調度程序可以將不承諾的交易編寫的數據標記為骯髒，並且在未標記之前，切勿讓讀取操作開始對此類數據項開始。為了獲得嚴格的歷史記錄，調度程序不應允許對臟項目進行任何操作。

實施問題

時間戳分辨率

這是兩個相鄰時間戳之間經過的最小時間。如果時間戳的分辨率太大（粗糙），則增加兩個或多個時間戳相等的可能性將增加，從而使某些交易能夠超出正確的順序。例如，假設我們有一個可以每秒創建一百個獨特時間戳的系統，並且給出了兩個相距2毫秒的事件，即使它們實際上發生在不同的時間，它們也可能會得到相同的時間戳。

時間戳鎖定

即使此技術是一種無鎖定的技術，在交易期間，對象並未從並發訪問中鎖定，但對物體記錄每個時間戳的行為需要對像或其對象的持續時間鎖定。代理人。

也可以看看