使用時間戳的并發(fā)控制

?專欄內(nèi)容：

• 手寫數(shù)據(jù)庫toadb
  本專欄主要介紹如何從零開發(fā)，開發(fā)的步驟，以及開發(fā)過程中的涉及的原理，遇到的問題等，讓大家能跟上并且可以一起開發(fā)，讓每個需要的人成為參與者。
  本專欄會定期更新，對應(yīng)的代碼也會定期更新，每個階段的代碼會打上tag，方便階段學(xué)習(xí)。

?開源貢獻(xiàn)：

• toadb開源庫

個人主頁：我的主頁
管理社區(qū)：開源數(shù)據(jù)庫
座右銘：天行健，君子以自強不息；地勢坤，君子以厚德載物.

前言

隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)已經(jīng)滲透到各個領(lǐng)域，成為現(xiàn)代社會最重要的資產(chǎn)之一。在這個大數(shù)據(jù)時代，數(shù)據(jù)庫理論在數(shù)據(jù)管理、存儲和處理中發(fā)揮著至關(guān)重要的作用。然而，很多讀者可能對數(shù)據(jù)庫理論感到困惑，不知道如何選擇合適的數(shù)據(jù)庫，如何設(shè)計有效的數(shù)據(jù)庫結(jié)構(gòu)，以及如何處理和管理大量的數(shù)據(jù)。因此，本專欄旨在為讀者提供一套全面、深入的數(shù)據(jù)庫理論指南，幫助他們更好地理解和應(yīng)用數(shù)據(jù)庫技術(shù)。

數(shù)據(jù)庫理論是研究如何有效地管理、存儲和檢索數(shù)據(jù)的學(xué)科。在現(xiàn)代信息化社會中，數(shù)據(jù)量呈指數(shù)級增長，如何高效地處理和管理這些數(shù)據(jù)成為一個重要的問題。同時，隨著云計算、物聯(lián)網(wǎng)、大數(shù)據(jù)等新興技術(shù)的不斷發(fā)展，數(shù)據(jù)庫理論的重要性日益凸顯。

因此，本專欄的分享希望可以提高大家對數(shù)據(jù)庫理論的認(rèn)識和理解，對于感興趣的朋友帶來幫助。

概述

在數(shù)據(jù)庫中如何保證并發(fā)事務(wù)時，數(shù)據(jù)的一致性，也就是可串行化，會有采用調(diào)度器來進(jìn)行協(xié)調(diào)各事務(wù)中動作的順序，以衣是否可以執(zhí)行等。調(diào)度器采用的模型主要有幾種：

• 基于封鎖的調(diào)度模型
• 基于時間戳的調(diào)度模型
• 基于有效性確認(rèn)的調(diào)度模型

前幾篇博文中分享了基于封鎖的調(diào)度模型，本文主要介紹基于時間戳的調(diào)度模型，主要從時間戳的概念，可以保證的行為和存在的問題，調(diào)度規(guī)則，以及多版本的優(yōu)化，與封鎖模型的聯(lián)合使用等方面進(jìn)行介紹。

時間戳介紹

也就是記錄上次讀和寫每個數(shù)據(jù)庫元素的事務(wù)時間點，同時每個事務(wù)也有一個時間戳，記錄它的開始時間點。

當(dāng)有事務(wù)要請求該數(shù)據(jù)庫元素時，比較這兩個時間，根據(jù)事務(wù)的時間戳來調(diào)度，來確保串行調(diào)度。

記錄時間戳的方法

• 理論上當(dāng)多個事務(wù)開始的時間間隔大于時間最小計數(shù)時，使用時間來記錄是可以達(dá)到目標(biāo)的，但是往往時間的精度不足以記錄多個同時開始的事務(wù)。

• 調(diào)度器維護(hù)一個計時器。每當(dāng)一個事務(wù)開始時，計數(shù)器就加1，而新值成為該事務(wù)的時間戳。這種方法與時間無關(guān)，但是它們具有時間的特性，單調(diào)遞增，不會重復(fù)，總是保證晚的事務(wù)比開始早的事務(wù)具有更高的時間戳；

事務(wù)提交的記錄

當(dāng)一個事務(wù)T讀到另一事務(wù)U所寫的數(shù)據(jù)，這一行為也是符合串行化規(guī)則，但是事務(wù)U最后中止了，并沒有提交，這樣事務(wù)T讀到的是臟數(shù)據(jù)，這一問題肯定會導(dǎo)致數(shù)據(jù)庫狀態(tài)變得不一致，這是任何調(diào)度器都要防止的臟讀。

除了兩個事務(wù)和數(shù)據(jù)庫元素上的時間戳外，還需要記錄一個事務(wù)的提交狀態(tài)位，當(dāng)事務(wù)沒有提交時，調(diào)度器也需要阻止其它事務(wù)的訪問請求。

可以解決的問題

假如事務(wù)在開始的那一時刻就立即執(zhí)行結(jié)束，那也就不會發(fā)生非可串行化的問題。往往事務(wù)中的各個動作都會持續(xù)一段時間，這就會過晚讀和過晚寫的問題發(fā)生，而當(dāng)事務(wù)中止時，讀取的此事務(wù)寫的數(shù)據(jù)，就會發(fā)生臟讀的情況。

過晚的讀

• 問題描述
  事務(wù)執(zhí)行的時間軸是這樣的

如圖所示，事務(wù)T的讀在事務(wù)U的寫之后，而事務(wù)U的開始時間晚于事務(wù)T，這就導(dǎo)致事務(wù)T讀到的數(shù)據(jù)不一致。

• 解決方法
  當(dāng)事務(wù)T的進(jìn)行讀請求時，發(fā)現(xiàn)當(dāng)前數(shù)據(jù)元素上的時間戳晚于自己的事務(wù)開始時間戳?xí)r，事務(wù)T應(yīng)該是需要中止，它什么都不能做了。

過晚的寫

• 問題描述
  事務(wù)執(zhí)行的時間軸是這樣的

如圖所示，事務(wù)U開始時間晚于事務(wù)T，而事務(wù)U的讀操作早于事務(wù)T，本應(yīng)該事務(wù)U可以讀到T寫入的值，但是T的寫入更晚。

• 解決方法
  事務(wù)T因為時間戳晚于數(shù)據(jù)元素上的時間戳，也就是事務(wù)U訪問的時間戳，應(yīng)該中止事務(wù)T，讓事務(wù)U可以讀取正確的數(shù)據(jù)。

臟數(shù)據(jù)的問題

事務(wù)提交標(biāo)志的設(shè)置，就是用來解決這個問題的，先來看兩個問題。

• 問題一
  |事務(wù)U | 事務(wù)T|
  |:–|:–|
  |begin; ||
  |write(X) | |
  || begin;|
  ||read(X)|
  |abort||
  ||commit;|

• 問題二
  |事務(wù)U | 事務(wù)T|
  |:–|:–|
  |begin; ||
  |write(X) | |
  || begin;|
  ||write(X)|
  ||commit;|
  |abort||

對于問題一，因為事務(wù)U在事務(wù)T之前啟動，并寫入X，所有事務(wù)T讀取X是符合上面時間戳的規(guī)則，但是當(dāng)事務(wù)U最終中止時，事務(wù)T讀取的X就是臟數(shù)據(jù)，是數(shù)據(jù)庫中本不存在的數(shù)據(jù)；

對于問題二，有趣的事情來了，此時事務(wù)T提交后，其實它是基于事務(wù)U的，比如X=1，事務(wù)U寫入后X=2, 事務(wù)T寫入后X=3，那么提交成功后X=3；而事務(wù)U回滾后，好像什么都不需要做，還是事務(wù)U回滾為X=1，事務(wù)T重新再做一遍呢？

• 解決方法
  對于問題一的此類問題，請求讀操作時，需要看當(dāng)前數(shù)據(jù)元素是否已經(jīng)提交，如果沒有提交，需要中止當(dāng)前請求，或推遲到該數(shù)據(jù)庫元素提交之后再處理。

而對于問題二的此類問題，寫操作請求時，也同樣需要判斷當(dāng)前數(shù)據(jù)元素是否已經(jīng)提交，如果沒有提交，需要中止當(dāng)前請求，或推遲到該數(shù)據(jù)庫元素提交之后再處理。 當(dāng)然，更晚的寫也可以什么都不做，這被稱為Thomas寫法則，最后事務(wù)U中止后，它要回退它的寫入和數(shù)據(jù)庫元素上的時間戳，但是事務(wù)T的寫入被跳過了，同時也提交完成了，此時想恢復(fù)事務(wù)T的操作已經(jīng)不可能了。

mysql中的表現(xiàn)

mysql> show variables like 'transaction%';
+----------------------------------+-----------------+
| Variable_name                    | Value           |
+----------------------------------+-----------------+
| transaction_alloc_block_size     | 8192            |
| transaction_allow_batching       | OFF             |
| transaction_isolation            | REPEATABLE-READ |
| transaction_prealloc_size        | 4096            |
| transaction_read_only            | OFF             |
| transaction_write_set_extraction | XXHASH64        |
+----------------------------------+-----------------+
6 rows in set (0.00 sec)
mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from test_concurrent;
+------+
| i    |
+------+
|    5 |
+------+
1 row in set (0.00 sec)
-- 這此時另外啟動一個事務(wù)，將i修改為6,并提交事務(wù)
mysql> select * from test_concurrent;
+------+
| i    |
+------+
|    5 |
+------+
1 row in set (0.00 sec)

mysql> update test_concurrent set i = 3 where i = 5;
Query OK, 0 rows affected (0.00 sec)
Rows matched: 0  Changed: 0  Warnings: 0

mysql> commit;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from test_concurrent;
+------+
| i    |
+------+
|    6 |
+------+
1 row in set (0.00 sec)

可以看到mysql中，當(dāng)前事務(wù)可以看到i=5，但確修改不成功，返回0 rows被updated，這就是一個很迷惑的現(xiàn)象。

基于時間戳調(diào)度的規(guī)則

經(jīng)過上面問題的分析，現(xiàn)在我們概括基于時間戳調(diào)度的規(guī)則。

調(diào)度器選擇

對于來自事務(wù)的讀寫操作請求，調(diào)度器有幾種選擇：

• 同意該請求
• 推遲請求
• 中止請求事務(wù)

讀寫請求的處理

調(diào)度器收到讀寫操作請求，

1. 收到讀操作請求時，檢查當(dāng)前數(shù)據(jù)庫元素上次操作事務(wù)的提交狀態(tài)，

• 如果已經(jīng)提交，則再檢查時間戳的先后順序，如果請求事務(wù)的時間戳大于當(dāng)前數(shù)據(jù)元素的時間戳，則可以同意請求，并將時間戳更新為當(dāng)前事務(wù)；如果事務(wù)時間戳小于當(dāng)前數(shù)據(jù)元素的時間戳，則需要中止；
• 如果尚未提交，則請求事務(wù)需要推遲；

2. 當(dāng)收到寫操作請求時，先檢查當(dāng)前事務(wù)與數(shù)據(jù)庫元素上的時間戳，

• 如果請求事務(wù)的時間戳大于當(dāng)前數(shù)據(jù)元素的時間戳，再檢查數(shù)據(jù)元素上次操作的事務(wù)是否提交，如果已經(jīng)提交，則同意本次寫請求；如果未提交，則需要推遲本次請求；
• 如果事務(wù)時間戳小于當(dāng)前數(shù)據(jù)元素的時間戳，本次請求事務(wù)需要中止；

3. 當(dāng)收到事務(wù)提交請求時，更新數(shù)據(jù)元素上的提交狀態(tài)；同時喚醒等待的事務(wù)請求；

4. 當(dāng)收到事務(wù)T中止請求時，那么回退事務(wù)T對應(yīng)的所有操作數(shù)據(jù)；等待的事務(wù)需要重新發(fā)起讀或?qū)懻埱螅驗樾枰獧z查事務(wù)T的寫被中止后是否合法。

多版本時間戳

基于時間戳的并發(fā)控制調(diào)度器，如上面介紹的，會存在讀寫之間沖突，所以在這個基礎(chǔ)上進(jìn)行了一個重要的演進(jìn)，就是同時保留數(shù)據(jù)庫元素的多個帶不同時間戳的版本，使得讀寫可以同時進(jìn)行。

多版本時間戳的流程與上面流程類似：

1. 當(dāng)收到寫操作請求時WT(X)，如果請求被同意，那么X的一個新版本Xi被創(chuàng)建，它的時間戳為Ti(X);
2. 此時收到一個讀操作請求時RU(X)時，最新版本檢查不通過時，查找時間戳小于事務(wù)U的版本X；也是就WT(X)執(zhí)行前的版本，就是當(dāng)前可讀的版本，同意RU(X)在版本X上的讀請求；
3. 數(shù)據(jù)元素的時間戳與對應(yīng)的版本有關(guān)；
4. 當(dāng)然再有事務(wù)的寫請求來時，還是需要在最后的版本Xi上處理；
5. 舊版本的清理，當(dāng)X的某個版本上的時間戳小于任何當(dāng)前活躍事務(wù)的時間戳?xí)r，就可以清理掉它了。

多版本時間戳的方式，解決了讀寫并發(fā)時的性能問題。

時間戳與封鎖

在大多數(shù)只讀事務(wù)或者并發(fā)讀寫同一元素的情況不頻繁時，基于時間戳的調(diào)度比較有優(yōu)勢；

而當(dāng)讀寫并發(fā)比較高，而且對同一數(shù)據(jù)庫元素競爭較大時，封鎖調(diào)度反而比較優(yōu)，因為此種情況下基于時間戳的調(diào)度，需要進(jìn)行頻繁的回退操作。

在現(xiàn)代商用數(shù)據(jù)庫中，會將事務(wù)分為只讀事務(wù)和讀寫事務(wù)，在只讀事務(wù)時，只使用時間戳的方式，而只讀事務(wù)時采用兩階段鎖的方式。

總結(jié)

基于時間戳的調(diào)度模型可以說是一種樂觀的模型，它假設(shè)沒有非可串行化行為發(fā)生，并且只有在違例發(fā)生時才會進(jìn)行修正或者中止。與此相反，封鎖的調(diào)度模型是假設(shè)非可串行化行為一定會發(fā)生，那么提前進(jìn)行預(yù)防，并且推遲可能發(fā)生的事務(wù)，但不中止它們，它是一種悲觀模型。

這兩種模型，如果對于大量只讀操作時，樂觀型好于悲觀型調(diào)度器。

結(jié)尾

非常感謝大家的支持，在瀏覽的同時別忘了留下您寶貴的評論，如果覺得值得鼓勵，請點贊，收藏，我會更加努力！

作者郵箱：study@senllang.onaliyun.com
如有錯誤或者疏漏歡迎指出，互相學(xué)習(xí)。文章來源地址http://www.zghlxwxcb.cn/news/detail-780638.html

到了這里，關(guān)于【數(shù)據(jù)庫】基于時間戳的并發(fā)訪問控制，樂觀模式，時間戳替代形式及存在的問題，與封鎖模式的對比的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！