設(shè)計：小艾

審核：丁奇

編輯：宇亭

作者：羅中天（花名：德里克）
浙江大學(xué)在讀碩士、StoneDB 內(nèi)核研發(fā)實習(xí)生

ANSI SQL-92 標(biāo)準(zhǔn)中規(guī)定了四種事務(wù)隔離級別和三種異象：讀未提交（Read Uncommitted）、讀已提交（Read Committed，簡稱 RC）、可重復(fù)讀（Repeatable Read，簡稱 RR）和串行化（Serializable），其中讀已提交解決了臟讀，可重復(fù)讀解決了臟讀和不可重復(fù)讀，串行化解決了臟讀、不可重復(fù)讀和幻讀。上述這些內(nèi)容是為人所熟知的，故不是本文的主角。本文的主角是快照隔離級別（Snapshot Isolation，簡稱 SI），同時引入新的異象寫偏斜（Write Skew）。SI 不屬于 SQL 標(biāo)準(zhǔn)的一部分，是對 SQL 標(biāo)準(zhǔn)的補充。

在將 SI 考慮進(jìn)去以后，可以得到如下表格中的內(nèi)容

「隔離級別」「寫寫關(guān)系」「寫讀關(guān)系」「讀寫關(guān)系」「存在的問題」丟失更新寫不阻塞寫寫不阻塞讀讀不阻塞寫臟寫/臟讀/不可重復(fù)讀/幻讀/寫偏斜讀未提交寫阻塞寫寫不阻塞讀讀不阻塞寫臟讀/不可重復(fù)讀/幻讀/寫偏斜讀已提交寫阻塞寫寫阻塞讀讀不阻塞寫不可重復(fù)讀/幻讀/寫偏斜可重復(fù)讀寫阻塞寫寫阻塞讀讀阻塞寫幻讀快照寫阻塞寫寫不（完全）阻塞讀讀不（完全）阻塞寫寫偏斜串行化寫阻塞寫寫阻塞讀讀間隙阻塞寫無

注意，上表中的讀已提交、可重復(fù)讀中的部分內(nèi)容和 innodb 中的有些不符，原因是 innodb 中的 RC 和 RR 包括快照讀和當(dāng)前讀兩種情況，具體會在下面進(jìn)行分析。

接下來本文主要圍繞 SI，闡述 SI 的實現(xiàn)方式 MVCC、SI 的異象寫偏斜、將 SI 和 RR 混在一起的“罪魁禍?zhǔn)住薄狪nnodb 中的 RR 等內(nèi)容。

SI 的實現(xiàn)方式

一般而言，SI 是用多版本并發(fā)控制（Multi-Version Concurrency Control，簡稱 MVCC）實現(xiàn)的。MVCC 本身有多種實現(xiàn)方式，并不是所有的 MVCC 都能實現(xiàn)理論上的 SI，比如 Innodb 中的 MVCC 其實就沒有完全實現(xiàn) SI，因為它沒有完全解決幻讀，關(guān)于 Innodb 中的 MVCC 的具體分析請見本文下面的小節(jié)。除了 MVCC 之外，SI 中的每個事務(wù)需要分配 2 個時間戳，一個在事務(wù)開始的時候分配，一個在事務(wù)結(jié)束的時候分配。

一個完整的 MVCC 協(xié)議包括并發(fā)控制協(xié)議、多版本的存儲、垃圾回收和索引管理四個部分。本文主要對并發(fā)控制協(xié)議進(jìn)行闡述。

記錄元數(shù)據(jù)

一種并發(fā)控制協(xié)議的實現(xiàn)方式

在上圖的記錄元數(shù)據(jù)的基礎(chǔ)上新增 READ-TS 字段表示讀取這條記錄最大的事務(wù) ID。

對于讀來說，事務(wù)??讀取沒加寫鎖（TRX-ID 為 0）且滿足??的記錄，顯然這樣的記錄最多只有一條，如果 READ-TS 小于?，就 CAS 將 READ-TS 變成?，如果 CAS 失敗，繼續(xù)比較，如果還是小于，繼續(xù) CAS，如果大于的話，就可以結(jié)束了。

對于寫來說，事務(wù)??找到最新的記錄，如果不可見，就 abort，否則，如果該記錄沒加寫鎖（TRX-ID 為 0）且??大于等于 READ-TS，就將 TRX-ID CAS 為?，即加寫鎖，然后生成新的版本，新版本 BEGIN-TS 設(shè)為?，將 END-TS 設(shè)為無窮大，然后將加鎖版本（舊版本）的 END-TS 改為?（原來為無窮大）。在事務(wù)提交的時候，會為事務(wù)新分配一個時間戳，將新記錄版本的 BEGIN-TS 和舊記錄版本的 END-TS 修改為該時間戳，最后釋放鎖。
為什么寫的時候會有??大于等于 READ-TS 的條件？這是為了 ID 更大的事務(wù)的快照的前后一致性。這個條件表示已經(jīng)有 ID 更大的事務(wù)讀取了該條記錄，如果事務(wù)??生成了新的版本，那么原來那個版本的 END-TS 就會被改為?，如果 ID 為 READ-TS 的事務(wù)再次讀取這個記錄，那么讀到的記錄就會變成最新版本的了（根據(jù)范圍），前后就不一致了。、

發(fā)生寫寫或者讀寫沖突后會發(fā)生事務(wù)的回滾（也有可能是阻塞），在上層的應(yīng)用中可以進(jìn)行自旋重試的操作。

SI 的異象

從文章開頭的表格中可以看出 SI 會出現(xiàn)寫偏斜的異象，并且解決了幻讀，這里可能會有一些反常識，至于為什么有些人會產(chǎn)生 SI 沒有解決的 MVCC 的誤解，我們會在下一小節(jié)中進(jìn)行分析。

寫偏斜

如上圖所示，事務(wù) 1 想要將所有的球變黑，它會先查詢出有哪些球是白的，然后更新這些球為黑球，事務(wù) 2 想要將所有的球變白，它會先查詢出哪些球是黑的，然后更新這些球為白球，由于兩個事務(wù)都是基于快照進(jìn)行修改的，所以最后的結(jié)果不是串行化能形成的狀態(tài)（全黑或者全白）中的任意一個，這就是寫偏斜的異常。用更加 hign level 的語言來表述的話，寫偏斜是指兩個事務(wù)并發(fā)讀取一個數(shù)據(jù)集，然后各自利用讀到的信息修改數(shù)據(jù)集中不相交的數(shù)據(jù)項，最后并發(fā)提交事務(wù)。

如何解決的幻讀

假設(shè)有兩個事務(wù) A 和 B，當(dāng)前事務(wù) A 已經(jīng)進(jìn)行了一個范圍的查詢，之后按順序會發(fā)生事務(wù) B 進(jìn)行一次插入操作，事務(wù) A 進(jìn)行一次同樣條件的查詢操作，由于事務(wù) B 的插入操作涉及的記錄的 BEGIN-TS 會在事務(wù) B 提交的時候被改為為事務(wù) B 的結(jié)束時間戳，那么該時間戳肯定大于事務(wù) A 的 trx_id（在事務(wù) A 開始的時候分配），所以事務(wù) B 的插入對事務(wù) A 是不可見的。

SI 和 RR 的主要區(qū)別

大家總是會將 SI 和 RR 搞混，甚至認(rèn)為這兩個是相同的東西，這背后的罪魁禍?zhǔn)资?Innodb（其實 Postgress 也是，但在互聯(lián)網(wǎng)行業(yè)中 Innodb 還是占比更重的那一位），具體的原因是 Innodb 的 RR 包括了快照讀和當(dāng)前讀兩種方式。

快照讀

Innodb 中的普通讀（select ...）就是快照讀，通過 MVCC 的方式實現(xiàn)。

Innodb 中的 MVCC

版本鏈

innodb 中的 undo log 被分為兩大類，TRX_UNDO_INSERT 和 TRX_UNDO_UPDATE。其中 TRX_UNDO_UPDATE 類型的 undo log 有一個 roll pointer 字段，指向該條記錄上一次修改對應(yīng)的 undo log。同時每條數(shù)據(jù)記錄也有一個 roll pointer 的隱藏字段，指向該條記錄上一次修改對應(yīng)的 undo log。這樣通過 roll pointer，每條記錄都能形成一個版本鏈。另外，每條記錄和 undo log 里都存著造成這次修改的 trx id。每條數(shù)據(jù)記錄是最新的，順著版本鏈，可以追溯到之前的修改版本，以及每次修改對應(yīng)的事務(wù) id。

ReadView

查詢流程

順著版本鏈依次進(jìn)行判斷

1. 如果被訪問版本的 trx_id 和 ReadView 中的 creator_trx_id 相同，就查詢到當(dāng)前版本

2. 如果被訪問版本的 trx_id 小于 ReadView 中的 min_trx_id，該版本可以被當(dāng)前事務(wù)訪問

3. 如果被訪問版本的 trx_id 大于等于 ReadView 中的 max_trx_id，該版本不可以被當(dāng)前事務(wù)訪問

4. 如果如果被訪問版本的 trx_id 大于等于 ReadView 中的 min_trx_id，且小于 ReadView 中的 max_trx_id，需要判斷 trx_id 是否在 m_ids 中，如果在的話，該版本不可以被當(dāng)前事務(wù)訪問，否則，可以訪問

5. 如果該版本不可以被當(dāng)前事務(wù)訪問，順著版本鏈繼續(xù)判斷下一個

快照讀不是 SI

Innodb 中的快照讀不是 SI，因為快照讀引入了部分的幻讀問題，而 SI 按前面所講，不會有幻讀的問題，但是有寫偏斜的問題。

引入部分幻讀

在上圖所示的情況下會引入幻讀，因為在第三步的時候會講 id=5 的那條記錄的 trx_id 修改為事務(wù) A 的事務(wù) id，所以在第四步的時候會根據(jù)上面查詢流程中的第一條，即訪問版本的 trx_id 和 ReadView 中的 trx_id 相同，所以會“無中生有”地查到 id=5 的這條記錄。
這里可能讀者會有一個疑問，那么如果在上面分析 SI 的 MVCC 解決幻讀的那個例子中也加入事務(wù) A update 的這個操作，會怎么樣？在 SI 的 MVCC 中，事務(wù)在生成新版本的時候的時間戳一定要比舊版本更大才行，由于事務(wù) A 看不到事務(wù) B 插入的記錄，所以將無法執(zhí)行 update 操作。

本質(zhì)原因

在 innodb 中

1. 事務(wù)只有一個 trx_id，沒有開始和結(jié)束都分配一個時間戳。

2. 版本鏈按從新到就來看，它的時間戳（或者 trx_id）不是從大到小的（innodb 這樣設(shè)計的原因個人認(rèn)為是為了減少事務(wù)的阻塞和回滾，如果按 SI 中的 MVCC 來看，可能會出現(xiàn)不少這種讀寫沖突的情況）

當(dāng)前讀

Innodb 中的 update、select...for share mode、select...for update 等語句是當(dāng)前讀。當(dāng)前讀不走 MVCC 的邏輯，而是通過兩階段鎖（Two Phase Lock，簡稱 2PL）的方式實現(xiàn) RR，其實如果拋開快照讀，Innodb 的 RR 其實就是串行化，通過間隙鎖的方式解決了幻讀的問題。

2PL

Innodb 中的 2PL 是強兩階段鎖（strong 2PL），即所有鎖（包括 X 鎖和 S 鎖）的釋放都需要放到事務(wù)提交之后，這樣就可以解決臟讀和不可重復(fù)讀的問題。

間隙鎖

Innodb 通過間隙鎖解決了幻讀的問題，所以 2PL+間隙鎖解決了所有的異象，也就是 Innodb 串行化的實現(xiàn)方式。
間隙鎖雖然是鎖住前后兩條記錄之間的間隙的，但是在實現(xiàn)上將其歸于后面那條記錄。間隙鎖也分為 X 鎖和 S 鎖，間隙鎖與間隙鎖之間，無論是 X 鎖還是 S 鎖，都不會阻塞，但在插入一條記錄的時候，如果存在間隙鎖，就會生成一個插入意向鎖，并阻塞。

小結(jié)

這篇文章我們介紹了快照隔離級別 SI 以及和 RR 的區(qū)別，SI 是對四種常見隔離級別的補充，能夠有效解決幻讀的問題，是對 SQL 標(biāo)準(zhǔn)的重要補充。更多精彩硬核技術(shù)，歡迎關(guān)注StoneDB開源社區(qū)，我們后續(xù)會更新更多技術(shù)研發(fā)干貨~