多版本時間戳排序

---

多版本時間戳排序 (MVTO) 是一種流行的併發控制技術，用於資料庫管理系統 (DBMS)。MVTO 允許資料項的多個版本同時共存，提供高併發性和資料一致性，同時防止衝突和死鎖。

在本文中，我們將討論 MVTO 的定義和組成部分，以及它的工作原理。

多版本時間戳排序 (MVTO)

在 MVTO 中，資料項的每個版本都有一個與之關聯的唯一時間戳。訪問資料項的事務也會被分配時間戳。

MVTO 有三個組成部分：時間戳、版本和排序 -

• 時間戳分配給事務和資料項版本以確定操作順序。

• 版本在修改資料項時建立，每個版本都有一個唯一的時間戳。

• 排序確保事務僅根據其時間戳訪問資料項的相應版本。

MVTO 的工作原理

讀取操作

有兩種型別的讀取操作。它們是隻讀事務和讀寫事務。

• 只讀事務可以訪問資料項的任何版本。它存在於事務啟動時。

• 讀寫事務只能訪問資料項的最新版本。該版本是在事務提交之前建立的。

二、寫入操作

有三種類型的寫入操作：插入、刪除和更新。

• 對於資料項插入的情況。它會得到一個新的時間戳。

• 對於資料項刪除的情況。它被標記為已刪除，但不會物理地從資料庫中刪除。

• 對於資料項更新的情況。將建立一個具有新時間戳的新版本，並將舊版本標記為已刪除。

用於可序列化的多版本時間戳排序技術

在多版本時間戳排序技術中，為每個事務分配唯一的時間戳，併為每個資料項維護多個版本。該技術透過遵循兩條規則來確保可序列化。

規則 1

如果事務 T 發出 Read(X) 請求，並且 Read_TS(Xi) < TS(T)，則系統將 Xi 的值返回給事務 T 並將 Read_TS(Xi) 更新為 TS(T)。

規則 2

如果事務 T 發出 Write(X) 請求並且 TS(T) < Read_TS(X)，則系統中止事務 T。如果 TS(T) = Write_TS(X)，則系統覆蓋 X 的內容；如果 TS(T) > Write_TS(X)，則它建立 X 的新版本。

為資料項的每個版本維護的欄位 -

• 該版本的價值。

• Read_TS(Xi)：Xi 的讀取時間戳是成功讀取版本 Xi 的任何事務的最大時間戳。

• Write_TS(Xi)：Xi 的寫入時間戳是成功寫入版本 Xi 的任何事務的最大時間戳。

示例

考慮以下包含事務 T1 和 T2 的排程，其中 T1 的時間戳為 5，T2 的時間戳為 10。

T1	T2
Read(X)
Write(X)
	Read(X)
	Write(X)
Read(X)
Write(X)
	Write(X)

• 最初，資料項 X 的狀態為 X0，Read_TS(X0) = Write_TS(X0) = 0。

• T1 執行 Read(X)，讀取 X0 的值，並將 Read_TS(X0) 設定為 TS(T1) = 5。

• T1 執行 Write(X)，建立一個新版本 X1 並設定 Read_TS(X1) = Write_TS(X1) = TS(T1) = 5。

• T2 執行 Read(X)，讀取 X1 的值，並將 Read_TS(X1) 設定為 TS(T2) = 10。

• T2 執行 Write(X)，建立一個新版本 X2 並設定 Read_TS(X2) = Write_TS(X2) = TS(T2) = 10。

• T1 執行 Read(X)，讀取 X1，讀取成功。

• T1 執行 Write(X)，但由於 T2 已經讀取了 X1，系統中止 T1。

• T1 的中止級聯到 T2，T2 也中止。

多版本時間戳排序流程圖

MVTO 的優點和缺點

以下是多版本時間戳排序 (MVTO) 的優點和缺點：

優點

• 高併發性

• 防止衝突和死鎖

• 資料一致性

• 支援長時間執行的事務

缺點

• 儲存開銷

• 計算複雜度增加

• 可擴充套件性有限

結論

總之，多版本時間戳排序是一種併發控制技術。它允許儲存和使用事務的資料項的多個版本。每個事務都分配一個唯一的時間戳。對於資料項的每個版本，系統維護值、讀取時間戳和寫入時間戳。

透過允許儲存資料項的多個版本，多版本時間戳排序避免了不必要的事務中止。它減少了對同一資料項版本的競爭。但是，它也需要更多的儲存空間，並且由於維護多個版本而可能導致開銷增加。