還在為數(shù)據(jù)庫事務(wù)一致性檢測而苦惱？讓Elle幫幫你 | DB·洞見

數(shù)據(jù)庫用戶通常依賴隔離級別來確保數(shù)據(jù)一致性，但很多數(shù)據(jù)庫卻并未達(dá)到其所表明的級別。主要原因是：一方面，數(shù)據(jù)庫開發(fā)者對各個(gè)級別的理解有細(xì)微差異；另一方面，實(shí)現(xiàn)層面沒有達(dá)到理論上的要求。

用戶在使用或開發(fā)者在交付數(shù)據(jù)庫前，需要對隔離級別進(jìn)行快速的正確性驗(yàn)證，并且希望驗(yàn)證是可靠的（沒有誤差）、快速的（多項(xiàng)式時(shí)間）、有效的（找出異常）、通用的（任意數(shù)據(jù)庫）、可解釋的（可以debug，可以復(fù)現(xiàn)）。

Elle 就是針對以上問題提出的一個(gè)基于 Adya 模型的黑盒一致性檢測工具。Elle 通過精心設(shè)計(jì)的讀寫操作和版本控制，可以檢驗(yàn)出 Adya 提出的所有非謂詞異常，并且具有一定可解釋性和復(fù)現(xiàn)性。在實(shí)踐中，Elle 在所測的四個(gè)數(shù)據(jù)庫上都測出了數(shù)據(jù)不一致。

探索前沿研究，聚焦技術(shù)創(chuàng)新。本期由騰訊云數(shù)據(jù)庫高級工程師陳育興為大家介紹數(shù)據(jù)庫事務(wù)一致性檢測的技術(shù)原理及相關(guān)實(shí)現(xiàn)，包括背景、動(dòng)機(jī)、解決方案等內(nèi)容。

1.1 數(shù)據(jù)異常

我們熟知的數(shù)據(jù)異常有臟讀、臟寫、丟失更新等很多種類，如果從數(shù)據(jù)異常的角度來解釋一致性，即一致性是保證不出現(xiàn)數(shù)據(jù)異常。

我們以一個(gè)經(jīng)典案例數(shù)據(jù)異常（寫偏序（Write Skew））對此進(jìn)行說明。某用戶有兩個(gè)投資賬戶，允許其中一個(gè)賬戶暫時(shí)虧損，但兩個(gè)賬戶總額不能為虧損。轉(zhuǎn)賬前兩個(gè)賬戶各有$100，兩個(gè)事務(wù)同時(shí)開啟，A事務(wù)查詢總余額發(fā)現(xiàn)有$200，并在第一個(gè)賬戶取出$200，B事務(wù)查詢總余額也是$200，并且在第二個(gè)賬戶取$200，兩個(gè)事務(wù)都提交成功。各取出$200、總共取出$400，但按正常理解，超額取錢是不允許的，這種情況就是數(shù)據(jù)異常。然而這種操作在絕大部分?jǐn)?shù)據(jù)庫的默認(rèn)配置中都會(huì)出現(xiàn)。

該例子的寫偏序的標(biāo)準(zhǔn)測試樣例如上圖所示：初始數(shù)據(jù)庫有兩行數(shù)據(jù)，兩個(gè)事務(wù)都各自讀一行數(shù)據(jù)，兩個(gè)事務(wù)分別更新對方讀的數(shù)據(jù)，最后兩個(gè)事務(wù)都提交成功，這就是標(biāo)準(zhǔn)的寫偏序。這在很多數(shù)據(jù)庫的默認(rèn)級別和快照級別都會(huì)出現(xiàn)，用戶通常需要額外的約束或需要數(shù)據(jù)庫開啟可串行級別才能避免該異常。

1.2 隔離級別 VS 數(shù)據(jù)異常

一致性有強(qiáng)弱之分，數(shù)據(jù)庫中滿足強(qiáng)/弱一致性需要通過隔離級別來實(shí)現(xiàn)。在某些弱級別下，異常的出現(xiàn)被視為正常，因?yàn)橛行┊惓Ｔ诓糠謽I(yè)務(wù)場景下是可以被接受的。那我們?yōu)楹我试S數(shù)據(jù)異常的出現(xiàn)，而不是禁止所有異常出現(xiàn)從而保證正確性？因?yàn)檎_性和性能之間需要權(quán)衡，正確性越高，性能越差，允許一些數(shù)據(jù)異常，性能也會(huì)有所提升。

標(biāo)準(zhǔn)定義下存在四種異常，從P0到P3，逐步禁止，比如P0是臟寫，在所有級別中都不允許出現(xiàn)；P1是臟讀，在讀未提交允許出現(xiàn)，幻讀則允許在RR級別下出現(xiàn)；可串行級別理論上不允許任何異常出現(xiàn)。隔離級別越強(qiáng)，允許的異常就越少，且通常隔離級別為逐級疊加，即弱隔離級別不允許出現(xiàn)的異常，在更強(qiáng)的隔離級別也不允許出現(xiàn)。

四種標(biāo)準(zhǔn)的異常只是數(shù)據(jù)異常中的一小部分，還有更多數(shù)據(jù)異常的形式。在四種標(biāo)準(zhǔn)的級別之上也有更多的隔離級別。

上表顯示的是新的異常和新的隔離級別之間的允許/不允許關(guān)系，但并非時(shí)時(shí)刻刻都如此嚴(yán)格。一方面，各廠商的數(shù)據(jù)庫產(chǎn)品會(huì)因理解和實(shí)現(xiàn)的不同致使部分異常沒有按預(yù)期出現(xiàn)或禁止。另一方面，上述異常僅僅是一小部分，理論上存在的級別也還有很多。因此很多數(shù)據(jù)庫新用戶不知道哪些異常會(huì)出現(xiàn)或不應(yīng)該出現(xiàn)，以及如何去理解這些級別和異常。

2.1 非傳統(tǒng)隔離級別

下圖所示是部分非傳統(tǒng)的隔離級別。比較常見的是快照隔離級別，如圖所示的部份廠商，從名字上我們無法直接判斷這些級別的具體表現(xiàn)，相關(guān)文檔的描述也比較模糊，因此就會(huì)引申出一個(gè)問題，即它們應(yīng)該等價(jià)于哪些級別、對比當(dāng)前級別它們是強(qiáng)或弱。

2.2 用戶層面

從用戶角度來看，主要存在以下三方面問題：

• 如何針對自身業(yè)務(wù)選擇隔離級別，如何理解這些（新）隔離級別。比如哪些異常允許出現(xiàn)，哪些異常不允許出現(xiàn)？

• 數(shù)據(jù)庫申明的隔離級別沒有達(dá)到標(biāo)準(zhǔn)。比如Oracle申明支持可串行級別，但它只消除了四種標(biāo)準(zhǔn)的異常，沒有消除所有異常，存在寫偏序。在串行級別存在寫偏序異常，這種申明現(xiàn)象在很多數(shù)據(jù)庫中都會(huì)出現(xiàn)。

• 對隔離級別的定義標(biāo)準(zhǔn)不同，不單是可串行級別，其他弱隔離級別也是如此。比如在可重復(fù)讀級別，PostgreSQL不存在幻讀但存在寫偏序，SQL Server則不存在寫偏序異常但存在幻讀。

2.3 廠商層面

從廠商角度來看，主要存在以下兩方面問題：

一方面，數(shù)據(jù)庫需要迭代版本，但回歸測試樣例一般都不完整，只能在一定程度上進(jìn)行驗(yàn)證。比如PostgreSQL在2011年推出的9.1版本中已經(jīng)實(shí)現(xiàn)可串行化的快照隔離（SSI），但因?yàn)槟承┎襟E優(yōu)化導(dǎo)致在第三方事務(wù)插入后馬上更新干擾的情況下，出現(xiàn)G2異常（寫偏序），正常情況下不應(yīng)出現(xiàn)，直到2019年推出12.4版本才對此進(jìn)行修復(fù)。

另一方面，廠商需要研發(fā)新型事務(wù)數(shù)據(jù)庫，需要驗(yàn)證開發(fā)的正確性，確保沒有缺陷或者沒有程序上的bugs影響。

3.1 Jepsen/Elle事務(wù)一致性測試框架

對上述問題，我們可以利用一個(gè)事務(wù)一致性檢測方案——Jepsen/Elle方案進(jìn)行解決。Jepsen是一個(gè)更強(qiáng)大的框架，可以檢測分布式一致性、線性一致性等多種一致性級別，Elle是其中的一個(gè)事務(wù)驗(yàn)證模塊，Elle方案目前已經(jīng)在VLDB 2020會(huì)議中發(fā)表。

整體來看，Jepsen/Elle事務(wù)一致性測試框架的作用如下：

• 測試出各種級別下存在的異常，幫助理解當(dāng)前級別的表現(xiàn)；

• 通過理解當(dāng)前級別，可以驗(yàn)證當(dāng)前隔離級別是否達(dá)到要求；

• 測試結(jié)果可解釋、可溯源、可復(fù)現(xiàn)。

3.2 定義數(shù)據(jù)異常

在解決上述問題之前，我們需要知道如何定義數(shù)據(jù)異常，以及學(xué)術(shù)界又如何看待數(shù)據(jù)庫異常。

前文提到最簡單的一致性是不存在任何數(shù)據(jù)異常，但如何判斷發(fā)生了數(shù)據(jù)異常呢？比如正常要讀提交的值但卻讀到未提交的寫，一個(gè)事務(wù)兩次讀但卻讀到不一樣的值，這些能否歸為數(shù)據(jù)異常？其實(shí)，這些異常在一定程度上都算是數(shù)據(jù)異常，只是表述不夠正式且無法總結(jié)規(guī)律，因此我們需要用更規(guī)范的方式來定義數(shù)據(jù)異常。

在判斷有無數(shù)據(jù)異常前，我們需要把數(shù)據(jù)庫執(zhí)行后的數(shù)據(jù)抽象地表示出來。Elle方案里采用Adya表示模型，這是一個(gè)比較標(biāo)準(zhǔn)通用的表示模型，可以將數(shù)據(jù)庫操作對象以及操作方式抽象出來。比如對象通常有x、y、z, 可以對應(yīng)不同key，再用R、W、C、A對應(yīng)讀、寫、提交和回滾。在數(shù)據(jù)庫執(zhí)行完操作后，我們把一組事務(wù)操作記錄下來成為歷史（history），調(diào)度（schedule）是歷史的前綴（prefix）。兩者的區(qū)別在于，調(diào)度里仍有未完成的事務(wù)，但歷史里全是已完成的事務(wù)。

現(xiàn)階段寫偏序的執(zhí)行可以描述成一個(gè)調(diào)度，其中讀寫操作的下角標(biāo)表示事務(wù)，對象的下角標(biāo)表示版本數(shù)。以下圖為例，寫偏序的調(diào)度為：事務(wù)1進(jìn)行了讀操作，讀取了對象為x的0版本數(shù)據(jù)，事務(wù)2讀了對象為y的0版本數(shù)據(jù)，事務(wù)1改了y對象的值，事務(wù)2修改了x對象的值。

有了調(diào)度和歷史的概念后，我們可以去構(gòu)建沖突圖。沖突圖是以事務(wù)為點(diǎn)、沖突為邊的圖模型。比如上圖右邊的寫偏序例子，事務(wù)1的讀和事務(wù)2的寫作用在同一個(gè)對象x上，從版本來看事務(wù)1的版本更小、事務(wù)2的版本更大，因此存在從事務(wù)1到事務(wù)2的RW沖突邊。同理在y對象上，存在由事務(wù)2到事務(wù)1的RW邊。我們可以看到，該圖是一個(gè)環(huán)結(jié)果，我們可以通過環(huán)的存在來判斷數(shù)據(jù)異常的存在。因?yàn)槲覀冋J(rèn)為串行執(zhí)行的結(jié)果是一個(gè)沒有問題的數(shù)據(jù)狀態(tài)，比如事務(wù)1先做，再做事務(wù)2，就不會(huì)有數(shù)據(jù)異常，而沖突圖有環(huán)的情況，其實(shí)就是不可串行的執(zhí)行結(jié)果，它的結(jié)果不等價(jià)于任何一個(gè)串行執(zhí)行的結(jié)果。因此，我們認(rèn)為執(zhí)行的狀態(tài)或結(jié)果為不可串行的就存在異常。

如果我們把數(shù)據(jù)庫執(zhí)行轉(zhuǎn)成歷史，通過歷史去建模沖突圖，再去判斷沖突圖是否有環(huán)，就可以輕易判斷是否存在數(shù)據(jù)異常。因?yàn)闅v史或調(diào)度模型里可以確定讀寫版本，從而確定沖突依賴關(guān)系，容易做判斷。

3.3 問題與挑戰(zhàn)

在現(xiàn)實(shí)中，數(shù)據(jù)庫執(zhí)行結(jié)果有時(shí)很難獲取統(tǒng)計(jì)，即使可以獲取統(tǒng)計(jì)，也很難直接轉(zhuǎn)化為確定的歷史或者調(diào)度。這主要有兩方面的問題：一方面，依賴關(guān)系有時(shí)可能性很多，很難決定；另一方面，如果并發(fā)事務(wù)較多，不確定的依賴關(guān)系就會(huì)更多，需要分析和決定的成本很高，導(dǎo)致驗(yàn)證速度慢或可能性太多，內(nèi)存和計(jì)算資源不足以在短時(shí)間內(nèi)驗(yàn)證太多可能性。

數(shù)據(jù)讀寫之間的依賴判斷存在以下難點(diǎn)：

• 兩個(gè)事務(wù)都對K=1更新值，從兩個(gè)事務(wù)的歷史數(shù)據(jù)無法得知誰先誰后；

• 兩個(gè)事務(wù)都對K=1更新V=5，其他事務(wù)讀到K=1、V=5時(shí)，無法得知是哪個(gè)事務(wù)的寫的數(shù)據(jù)；

• 事務(wù)讀寫后是否參與沖突依賴判斷，需要兩個(gè)事務(wù)在時(shí)間上有交叉。但很多分布式時(shí)間不可信、不對齊，時(shí)間不一定對等；

如果考慮將所有可串行的結(jié)果去匹配執(zhí)行結(jié)果，本質(zhì)上是NP-complete問題，是一個(gè)非多項(xiàng)式時(shí)間的驗(yàn)證，計(jì)算成本非常高。

3.4 Jepsen/Elle解決方案

Jepsen/Elle解決方案首先要保證得到可靠的歷史，需要執(zhí)行結(jié)果滿足兩個(gè)特性：

• 可追溯性，需要知道版本之間的順序，決定ww依賴，誰先寫、誰后寫需要確認(rèn)。

• 可復(fù)原性，需要知道讀的是哪個(gè)版本、誰的寫，從而決定寫讀依賴；讀寫依賴可以根據(jù)寫寫依賴和寫讀依賴進(jìn)行推導(dǎo)。

Jepsen/Elle的輸入設(shè)置分為三種操作：

• 讀操作，select語句。

• 插入操作，insert語句。

• 更新操作，update語句。該update語句與普通update不同，需要在更新值時(shí)附帶原有值，把原有值和更新值都保留。

具體示例如下：首先往t1表里插入新值K=1，V=1。R1讀表里的內(nèi)容，讀到k=1、 v=1。W1更新行的內(nèi)容，讓值更新為2。因?yàn)楦聲r(shí)我們會(huì)將原有值加進(jìn)來，所以當(dāng)R2再次讀時(shí)，我們讀到的是k=1，v=“1 2”。以此類推，當(dāng)再次更新值為3時(shí)，我們讀到的是“1 2 3”。同一個(gè)變量上的更新使其保持唯一則不會(huì)有歧義，我們也知道更新版本順序，再通過讀數(shù)據(jù)，可以輕易推導(dǎo)出這些操作的讀寫依賴關(guān)系。

上圖是論文中給出的例子。R1中間的事務(wù)，讀了K=255的值2，3，4，5；R2上面的事務(wù)，讀了K=255的值為2，3，4，5， 8；W3下面的事務(wù)在K=255上寫了值為8，我們可以得到從W3到R2的WR依賴和R1到W3的RW依賴，從最上面的事務(wù)到中間的時(shí)間依賴（real-time 依賴），可以用作嚴(yán)格一致性的判斷。

Elle檢測模型基本遵循Adya文章定義的環(huán)分類，比如G0異常為全是WW邊的環(huán)，G1c為WW或WR組合的環(huán)，加上G-single和G2，這些異常環(huán)的組合類似于四種異?，F(xiàn)象，所以也有逐步不允許的限制。我們驗(yàn)證隔離級別是否達(dá)標(biāo)，就從最簡單的四種異常驗(yàn)證轉(zhuǎn)化為四大類環(huán)的檢測。

Elle檢測可以保證正確性，只要測出異常，則該異常一定存在。只要出現(xiàn)異常，理論上可以復(fù)現(xiàn)，也說明數(shù)據(jù)庫在該模型下不一致。另一方面，Elle不能保證完整性，Elle檢測后不代表系統(tǒng)完全滿足一致性，因?yàn)橛行┊惓２荒苡铆h(huán)表示，比如臟讀、臟寫、中間讀以及有些需要狀態(tài)確認(rèn)的異常，Elle也不能檢測謂詞異常。

Elle通過初期寫的特殊處理，所有的依賴關(guān)系都是確定性的，通過事務(wù)執(zhí)行結(jié)果來判斷依賴關(guān)系的復(fù)雜度，基本上都是線性。我們可以看到，隨著并發(fā)增大，粉色線的時(shí)間基本是平穩(wěn)線性增長，而傳統(tǒng)做法需要比對任意事務(wù)之間的順序，復(fù)雜度是階乘于事務(wù)個(gè)數(shù)，隨著并發(fā)增大，驗(yàn)證時(shí)間為指數(shù)增長。

上圖是用Elle工具在PostgreSQL老版本上測出的異常，在可串行級別下存在寫偏序異常。右邊的可復(fù)現(xiàn)的例子中， 共有三個(gè)事務(wù)，兩個(gè)事務(wù)新插入數(shù)據(jù)，且相互沒有讀到新插入的數(shù)據(jù)，從而形成一個(gè)寫偏序的環(huán)。出現(xiàn)該異常的原因是，第三個(gè)事務(wù)對某個(gè)插入進(jìn)行更新導(dǎo)致后面的讀依賴沒有作用在插入值上。

3.5 Test  on TDSQL

我們在TDSQL上進(jìn)行測試。結(jié)果顯示，可串行級別不存在任何異常，RR級別的表現(xiàn)屬于快照隔離級別水平。

綜上所述，Elle事務(wù)一致性檢測框架主要解決兩個(gè)問題：

• 通過寫版本疊加，在更新時(shí)保留舊值，從而確定版本順序以及把執(zhí)行結(jié)果變?yōu)闅v史調(diào)度。

• 通過沖突圖的環(huán)檢測，從歷史調(diào)度判斷有無數(shù)據(jù)異常。此外，Elle也可通過疊加時(shí)間要求來檢測嚴(yán)格一致性，比如T2是T1 commit之后才開始的，那么串行執(zhí)行時(shí)必須為T1->T2，不允許出現(xiàn)T2->T1。

上述情況只涉及部分級別，我們還可以根據(jù)實(shí)際情況細(xì)分出更多的級別和一致性模型，用Elle進(jìn)行更多的驗(yàn)證。

最后，我們還可以從以下四方面對Jepsen/Elle事務(wù)一致性測試框架進(jìn)行優(yōu)化：

• 框架本身并不簡單，需要很多參數(shù)調(diào)節(jié)才能達(dá)到效果。比如有些情況壓測不充分，小概率異常難于發(fā)現(xiàn)，有時(shí)不易復(fù)現(xiàn)。

• 不支持Delete，不支持謂詞范圍查詢。無法檢驗(yàn)幻讀（Phantom），無法判別Repeatable Read和Serializable之間的區(qū)別。

• 采用新數(shù)據(jù)格式，而非傳統(tǒng)回歸測試的SQL語句，分析和debug都比較困難。

• Jepsen有額外錯(cuò)誤注入功能，但作者在Elle文章中并沒有細(xì)說。比如很多異常是因?yàn)槟承┕?jié)點(diǎn)重啟斷聯(lián)導(dǎo)致的，正常情況下允許并無異常。

參考文獻(xiàn)

[1] Atul Adya, Barbara Liskov, Patrick E. O'Neil: Generalized Isolation Level Definitions. ICDE 2000: 67-78

[2] Peter Alvaro, Kyle Kingsbury: Elle: Inferring Isolation Anomalies from Experimental Observations. Proc. VLDB Endow. 14(3): 268-280 (2020)

向量化執(zhí)行從理論到實(shí)現(xiàn)，僅需五步！| DB·洞見

節(jié)省30%磁盤空間的同時(shí)如何保障數(shù)據(jù)安全？｜DB·洞見