跳至主要内容

Timestamp Ordering Concurrency Control

Timestamp Ordering (T/O) concurrency control 是一種樂觀的並發控制協議，這種協議會假設衝突不常發生，因此不會在讀取或寫入資料庫之前獲取鎖。 T/O 的主要概念是為每個 transaction 分配一個 timestamp，如果 TS(Ti)<TS(Tj)TS(T_i) < TS(T_j)，則 DBMS 需要確保執行計劃等價於一個交易順序為 Ti,TjT_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 協議。 在這個協議中，事務讀寫都不需要加鎖，且每條資料 XX 都會有兩個 timestamp，分別是 read timestamp (R−TS(X)R-TS(X)) 和 write timestamp (W−TS(X)W-TS(X))，Basic T/O 會在每次操作時檢查這些時間戳。如果交易試圖讀取未來的資料，該交易將被中止並重新啟動。

Read​

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

Write​

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

Example​

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

Example Example

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

Thomas Write Rule (TWR)​

如果 TS(Ti)<W−TS(X)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)W-TS(X)

Example

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

Example

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

Example

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

Example

Validation Phase​

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

  • Backward Validation
  • Forward Validation

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

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

  • TiT_i 在 TjT_j 開始執行之前完成了所有三個階段

Example

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

Example

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

Summary​

OCC 會有以下的問題 :

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

Dynamic Databases and Phantom Problem​

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

Example

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

  • 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：允許交易持有更廣泛的鍵範圍鎖，並使用不同的鎖定模式來減少鎖管理器的負擔。

Hierarchical Locking

Locking Without An Index​

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

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

Isolation Levels​

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

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

Isolation Levels

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

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

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

Isolation Levels

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

Isolation Levels

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

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

References​