Timestamp Ordering Concurrency Control

Timestamp Ordering (T/O) concurrency control 是一種樂觀的並發控制協議，這種協議會假設衝突不常發生，因此不會在讀取或寫入資料庫之前獲取鎖。 T/O 的主要概念是為每個 transaction 分配一個 timestamp，如果 $TS(T_i) < TS(T_j)$，則 DBMS 需要確保執行計劃等價於一個交易順序為 $T_i, T_j$ 的序列。

而實現 T/O 需要單調遞增的 timestamp，通常有以下幾種方法 :

• system clock : 使用系統的時鐘來生成 timestamp，有可能會受到夏令時間 (Daylight Savings Time，會在夏令時調整時鐘) 等意外狀況的影響
• logical counter : 使用邏輯計數器來生成 timestamp，這種方法可能會有溢出問題，並且很難在分散式系統中維持一致性
• hybrid clock : 結合系統時鐘和邏輯計數器

Basic Timestamp Ordering (BASIC T/O)

Basic Timestamp Ordering (BASIC T/O) 是一種最基本的 T/O 協議。 在這個協議中，事務讀寫都不需要加鎖，且每條資料 $X$ 都會有兩個 timestamp，分別是 read timestamp ($R-TS(X)$) 和 write timestamp ($W-TS(X)$)，Basic T/O 會在每次操作時檢查這些時間戳。如果交易試圖讀取未來的資料，該交易將被中止並重新啟動。

Read

1. 檢查 $W-TS(X)$ 是否大於 $TS(T_i)$，如果小於則代表 $T_i$ 試圖讀取未來的資料，因此 $T_i$ 會被中止並重新啟動，否則 $T_i$ 可以讀取 $X$
2. 如果讀取成功，則更新 $R-TS(X)$ 為 $max(R-TS(X), TS(T_i))$
3. 為了確保可以重複讀取到相同的資料，DBMS 會儲存一個副本

Write

1. 檢查 $TS(T_i)$ 是否小於 $R-TS(X)$ 和 $W-TS(X)$，如果小於則代表 $T_i$ 試圖覆蓋未來的資料，因此 $T_i$ 會被中止並重新啟動，否則 $T_i$ 可以寫入 $X$
2. 如果寫入成功，則更新 $W-TS(X)$ 為 $max(W-TS(X), TS(T_i))$

Example

詳細的例子可以參考投影片的第 10 頁 CMU 15-445/645: Timestamp Ordering Concurrency Control。 這邊我們只解釋第二個例子。

我們可以看到 T1 在 T2 修改了 A 之後又修改了 A，因此 T1 會被中止並重新啟動。

Thomas Write Rule (TWR)

如果 $TS(T_i) < W-TS(X)$，根據 Thomas Write Rule，DBMS 可以選擇忽略這個寫入操作並繼續執行，雖然這違反了 T/O 的原則，但是由於沒有其他操作依賴於這個寫入操作 (會寫入到 local copy 中)，因此不會影響 schedule 的 serializability。

Summary

如果不使用 TWR，則 Basic T/O 可以保證 schedule 是 conflict serializable，

其優缺點如下:

• 優點
  • 無需加鎖
  • 不會造成死鎖
• 缺點
  • 長的 transaction 因為衝突而導致產生 starvation。
  • 複製資料、維護 timestamp 會增加系統的開銷
  • 可能產生無法恢復的 schedule (unrecoverable schedule)

Optimistic Concurrency Control (OCC)

Optimistic Concurrency Control (OCC) 是一種樂觀的並發控制協議，使用時間戳來驗證交易。 OCC 適合在衝突較少的情況下使用，比如當所有交易都是唯讀的，或者當交易訪問不重疊的資料子集時。

在 OCC 中，所有的交易都會被放在一個私有空間中，且所有的修改都會在裡面進行，主要分為三個階段 :

• Read Phase
  • 追蹤每個交易讀取和寫入的資料，並放到私有空間中，並在結束時獲得 timestamp
• Validation Phase
  • 當要提交的時候，檢查是否有衝突
• Write Phase
  • 如果驗證成功，則將修改寫入到資料庫中

Example

與 Basic T/O 相比，OCC 只需要儲存 $W-TS(X)$

接著 T1 跟 T2 會將資料放到私有空間中

T2 完成整個交易，由於沒有資料要寫入，因此跳過 write phase，並獲得 timestamp 1

T1 將值修改為 456，由於還不知道 timestamp，因此暫時為無限大。 接著進行 validation phase，由於 $W-TS(A) = 1$，因此 T1 可以提交，並將 $W-TS(A)$ 更新為 2。

Validation Phase

DBMS 會檢查交易之間的 RW 衝突以及 WW 衝突，並確保所有衝突都朝同一個方向發生， 主要有兩種檢查方向

• Backward Validation
• Forward Validation

DBMS 檢查提交中的交易與所有其他正在運行的交易的順序。尚未進入驗證階段的交易會被分配一個無限大的 timestamp。

如果 $TS(T_i) < TS(T_j)$，則交易必須滿足以下條件之一

• $T_i$ 在 $T_j$ 開始執行之前完成了所有三個階段

• $T_i$ 在 $T_j$ 開始寫入階段之前完成，且 $T_i$ 沒有寫入 $T_j$ 讀取過的任何物件

• $T_i$ 在 $T_j$ 完成讀取階段之前完成了其讀取階段，且 $T_i$ 沒有寫入 $T_j$ 讀取或寫入過的任何物件

Summary

OCC 會有以下的問題 :

• 將資料複製到私有空間會增加系統的開銷
• validation / write phase 需要在全局的 critical section 中執行，這可能會造成瓶頸
• 由於交易只有在執行完成後才會進行驗證，因此 abort 會浪費大量已完成的工作
• timestamp 的分配在分散式系統中可能會有問題

Dynamic Databases and Phantom Problem

到目前為止，我們只討論了資料庫的讀取以及更新，而沒有考慮到插入和刪除等等的操作，這些操作可能會帶來新的問題，其中一個問題就是 Phantom Problem。

幻影問題是指在交易執行期間，其他交易插入了新的資料，導致同樣的查詢產生了不同的結果，解決方式大致有以下三種 :

• Re-Execute Scans
• Predicate Locking
• Index Locking

Re-Execute Scans

在交易提交時，DBMS 會重新執行所有查詢，確保結果與第一次執行時一致。 如果有任何新增或刪除的記錄導致結果不同，DBMS 可以檢測到這種情況並適當處理。

缺點是在資料庫規模較大時，這種方法會增加系統的開銷。

Predicate Locking

這種方法基於查詢的條件 (如 WHERE 子句) 來鎖定滿足條件的所有資料。 通過鎖定與查詢條件匹配的所有潛在資料，防止其他交易對這些資料進行修改。

幾乎沒有 DBMS 使用這種方法，因為對每條新插入的資料進行檢測會導致性能嚴重下降。

Index Locking

通過索引來鎖定特定範圍內的資料，防止在鎖定範圍內插入新資料，從而避免幻影問題。

• Key-Value Locks：對索引中的單個鍵值進行鎖定，包括對不存在的鍵值進行虛擬鎖定。
• Gap Locks：鎖定鍵值之間的間隙，防止在這些間隙中插入新資料。
• Key-Range Locks：鎖定從一個現有鍵到下一個鍵的範圍。
• Hierarchical Locking：允許交易持有更廣泛的鍵範圍鎖，並使用不同的鎖定模式來減少鎖管理器的負擔。

Locking Without An Index

如果查詢的欄位沒有索引，那麼我們需要獲取

• table 上每個 page 的鎖
• table 本身的鎖

Isolation Levels

serializability 是一種很實用的特性，它可以讓寫程式的人不用擔心併發所帶來的問題， 但由於它的嚴格性，因此會導致性能下降，因此有時候我們需要降低 isolation level 來提高性能。

更弱的 isolation level 會導致更高的性能，但也會帶來更多的問題， 如 dirty read、non-repeatable read、phantom read 等等。

如果要更詳細的了解，可以參考 這篇筆記

在 SQL-92 中，我們可以自己定義 isolation level

SET TRANSACTION ISOLATION LEVEL <isolation-level>;
BEGIN TRANSACTION ISOLATION LEVEL <isolation-level>;

但並非所有的資料庫都支持所有的 isolation level，因此需要查看相應的文件。

除了 SQL-92 定義的四種 isolation level 外，還有其他的 isolation level，如 :

• Cursor Stability : 介於可重複讀和讀已提交之間，避免了丟失更新異常 (Lost Update Anomaly)。
• Snapshot Isolation : 保證交易在執行過程中讀到的是交易開始時的數據快照。只有當寫入集不與其他同時進行的更新衝突時，交易才能提交，但有可能遇到 Write Skew 問題 (兩個快照對同一個地方進行修改)。