Transaction management：可串列性（serializability）

（原文發佈於我的博客：HW311）

距離上次更新已經很久了，過年的這段時間剛好是學期中，重度拖延症拖下來的projects和midterms堆在一起，實在忙得不可開交。這個週末閑下來一點，眼看著又一次寫博客的嘗試又要半途而廢，就抽出時間來總結記錄一下最近的學習歷程和心得吧。這一篇文章以及後續（可能會有）的一系列文章會簡單介紹一下資料庫事務管理（database transaction management）和分散式數據管理（distributed data management）。

前言

我們可能沒有意識到，資料庫已經滲透到我們生活中的點點滴滴，無處不在：早上起牀打開手機放一首喜歡的歌，播放器需要訪問資料庫調取歌曲信息；出門到銀行取錢，賬戶和交易信息都由銀行的資料庫保存和處理；晚上回到家打開網頁瀏覽新聞，網站後臺也一定會使用資料庫...... 我們也很難意識到，這個系統究竟有多麼複雜：想像你正在打一通美國到中國的跨洋長途電話，你的撥號請求會被附近你的服務商基站處理，並找出一條到中國目的基站的線路。這條線路會途徑許多層級的電話線路交換機。為了計算費用，每一處都有相應的資料庫記錄線路連接的數據，比如時長信息等等。更複雜的是，這樣規模的電話線路肯定不會為一家電信服務商單獨所有，電信服務商也會租用第三方線路提供商提供的線路，這些提供商也要根據線路使用情況向電信服務商收費。在你撥通太平洋另一端的電話號碼的短短几秒鐘內，十幾家公司的上百個資料庫被同時調動、十幾個不同的計費信息開始處理，要是電話沒能接通，這些數據也應當被相應地取消...... 作為一個程序員，單單是想像正確地實現這樣一次通話的數據處理都覺得複雜到頭疼，更別提現實情景中，這樣一個資料庫每秒需要並行處理上萬次通話了。

然而這樣複雜的一個系統，還對正確性有非常苛刻的要求。沒人希望自己被一通沒有撥通的長途電話收費，也沒人會接受一筆銀行轉賬扣了錢卻不知所蹤。在其他領域，保證正確性的做法通常是犧牲一部分的性能，但是在資料庫的很多使用場景中，每秒能夠處理的請求數量也非常關鍵，尤其是之前提到過的國際長途或者互聯網之類的全球性服務，犧牲了高並行的性能甚至可能完全無法使用。

綜上所述，如何在大規模、甚至分佈在全球的資料庫系統中保證高度並行處理中的正確性，絕對不是一個瑣碎容易（trivial）的問題。希望以上的介紹和例子能夠成功勾起讀者的興趣和注意。這個問題也許在當今的計算機科學研究中沒有很大熱度，但它還是非常有趣，也有很高的實用價值。如果不能清楚地瞭解問題是什麼就沒法給出優秀的解決方案，所以這篇文章還不會跳到具體的演算法和實現，我們先簡單瞭解一下如何為這個問題建立模型。

問題模型

在開始之前我覺得有必要給大家提醒一下這一篇文章和後續（可能會有）的一系列文章所討論的範疇：儘管我們感興趣的這個問題是一個工程上的實際問題，但是為了更好的理解它的性質我們還是要從簡化抽象的理論分析開始。所以我們在這一節裏提出的模型跟現實世界有一些落差。我們會先定義什麼是一個資料庫以及在資料庫上的操作；基於這個資料庫的模型，我們會介紹事務（transaction）和調度（schedule）的概念。

還有一點題外話，鑒於我學習這些概念的時候就是學的英文，而且我個人覺得有些概念的中文翻譯不是很到位（事務是什麼鬼啊喂！），我還是習慣在提及這些概念的時候使用英文。對，沒錯，我就是辭彙匱乏，看不慣中英夾雜的中文警察可以散了。

我們的目標

不知道目的地就不能合理地規劃路線，不清楚追求的目標就沒法設計出正確的演算法。在一切分析開始之前，我們先來仔細思考一下我們的目的是什麼、對於一個資料庫系統來說，「正確性」意味著什麼。

從直覺上說，一個資料庫就是用來保存數據，那隻要數據能按我們的預期被讀取寫入並且不出錯，這個資料庫就可以被認為是「正確」的。那「數據不出錯」又意味著什麼呢？這個簡單問題的答案並不是非常顯然。從語義上（syntactic）來看，一條數據擁有一個值，但是這個值是什麼並沒有具體的要求。但是大部分人很可能會認為存入一百塊錢錢之後銀行賬戶餘額變成了負數並不正確。於是我們發現，資料庫的正確性實際上跟context有關，不同的資料庫可能會有不同的constraints。比如在機票預訂或者座位預訂系統中，我們會要求剩餘票數或者座位數不能小於零；在銀行轉賬中轉賬雙方賬戶總額應當不變等等。這樣的正確性要求看起來似乎很簡單，但是在並行的情況下就沒這麼簡單了。舉個例子：程序A想要從賬戶x轉一百塊錢到賬戶y；程序B想要計算賬戶x和賬戶y的資產總額。假設賬戶x和賬戶y初始各有一千塊錢。如果A和B並行執行，那麼有可能B先讀取了x的餘額1000，然後A將100從x轉到y，最後B又讀取了y的餘額1100，計算得出x+y=2100！一個正確的資料庫系統應當避免這種情況的發生。

除了正確性之外，我們對資料庫可能還有很多其他的要求，比如支持操作回滾等等。限於篇幅，這篇文章只討論正確性，其他的內容會在後續（可能會有）的文章中討論。

資料庫模型

提到資料庫，很多人的第一想法可能就是 SELECT ... FROM ... WHERE ... 的SQL語句。這樣的關係資料庫模型在現實系統中非常常見，但是讀者之後可以看到，對於我們的分析來說這種模型並沒有反映出資料庫最底層最關鍵的不可分割的原子操作（atomic operations）。除此之外，這種基於關係的數據模型引入了我們不需要的概念：關係，在key-value store的資料庫中我們同樣會有正確性的問題。所以我們重新定義一個簡化的資料庫模型：

一個資料庫系統由一個不可再分（indivisible）的、互不重疊（non-overlapping）的數據對象（data objects）的集合構成： ${o_1, o_2,dots,o_n}$ ，每一個object都有一個取值範圍（domain of values）。這個系統的一個狀態（state） 就是一個從object到value的映射。資料庫的操作有（）和（）。[1]

簡單來說，在這個模型中我們只關心最原始的、不可再分的數據的讀和寫，比如銀行賬戶的餘額，或者航班上的剩餘座位。在這個模型中單獨一條SQL語句也可能會被分拆成很多項操作。

資料庫事務（database transactions）

Transaction 是對資料庫系統中讀寫操作的更高一層抽象，代表了「一個單位」的資料庫操作。一個transaction可能包含對多個數據對象的多個讀寫操作，但是這些操作被視為一個整體、一個「transaction」。舉個例子，之前提到的銀行轉賬涉及了分別讀寫x和y兩個賬戶，在我們的資料庫模型中可能被表示為，但是這四個操作應當被視為一個整體。

Transaction必須滿足ACID特性[1][2][3]：

Atomicity: 一個transaction就是一個不可再分的單位操作，要麼完全執行成功、要麼完全不執行。如果transaction中的某一項讀寫操作失敗了，那麼整個transaction都應該失敗，之前執行過的讀寫操作也應該回滾，整個系統應該恢復到執行這個transaction之前的狀態。
Consistency: 一個transaction應當使資料庫從一個合法的狀態變化到另一個合法的狀態，保證數據正確性和完整性。在我們之前舉的銀行轉賬和計算總額的例子中，最終的狀態就不合法，因為計算得出的總額並不正確，不滿足銀行賬戶這個資料庫系統的implied constraints.
Isolation: 並發執行的transactions不會觀察到其他transactions執行中的中間結果或者說副作用（partial effects）。還是之前的銀行轉賬的例子，導致數據不正確、consistency被破壞的原因就是A、B兩個程序沒有滿足isolation，B看到了A的partial effect.
Durability: 一旦一個transaction成功執行，那執行的結果就應當是（相對）永久性的。

Transaction這個概念放在資料庫的使用情景中看非常自然，比如銀行交易（transaction）本身就是一個transaction。ACID的要求也是現實生活中非常普遍的，比如預訂聯程航班時，要麼就成功預訂所有航段的機票、要麼就一張機票都不預訂。更加重要的是，transaction這個概念為資料庫的用戶和程序員提供了一層非常方便的抽象，用戶只需要使用transaction來編寫業務邏輯就可以享受其ACID性質，而不需要自己處理複雜的正確性需求。我個人認為這樣的層層抽象（還比如網路的OSI多層模型）是計算機科學非常優雅的美感之一。

為了方便描述和使用transaction模型，這裡給出正式定義[1]：

一個transaction 是一個偏序：
$T_isubseteq{r_i(x), w_i(x)mid x~mathrm{is~an~object}}cup{a_i, c_i}cup{b_i}$ 其中，代表abort；代表commit；代表begin。由開始，和只能存在一個，並且是的最終操作。為了簡潔，和經常被省略。如果操作和屬於，那要麼，要麼。中寫操作寫入數據對象的值是一個關於之前（由定義）所有讀取的值的函數。比如在中，的值是關於和的某個函數，也就是說我們沒有對寫操作做任何假設，寫入的值可能會取決於觀察到的所有值。

事務調度（schedule）

明白了transaction的概念，理解schedule就很簡單了：一個schedule就是多個transactions的交錯，就是多個transaction中的多個數據操作用什麼順序執行的一個「計劃」（或者執行過的歷史，所以有時也叫history）。

最簡單的schedule就是按順序執行多個transactions：

類似這樣的schedule叫做 serial schedule（串列調度）。Serial schedule在我們的分析中非常重要，但是就執行效率來說並不理想：如果被某個數據操作block了，那麼等待數據的這段時間就會被浪費，從而增加了和的響應時間，所以schedule中不同的transaction很可能是交錯執行的：

$egin{align} T_1&: r_1(x)~w_1(y)\ T_2&: w_2(z)~w_2(x)\[0.6em] S&: r_1(x)~w_2(z)~w_1(y)~w_2(x) end{align}$

Schedule的正式定義是[1]：

一個schedule ，其中：是transaction的集合；是中transactions中的數據操作的偏序，並滿足：，也就是說，schedule會保持每個transaction中操作自己的順序。

可串列性（serializability）

簡單來說，transaction就是具有意義的資料庫操作最小單位，可能包含多個具體的數據讀寫操作；schedule描述了多個transaction如何穿插執行。有了基本的模型，我們的目標也更加明確了：如何得出高並發並且正確的schedule？或者在現實應用中由於複雜度和機能限制，如何辨別並拒絕錯誤的、可能會破壞數據consistency的schedule？

要回答這兩個問題，我們首先需要回答「正確」對於schedule來說意味著什麼（déjà vu!）。

直覺上分析，schedule可能出現的「錯誤」來源於多個transaction的並發執行。再回顧我們之前提到的銀行轉賬的例子，在我們的模型中可以描述為：

$egin{align}T_A&: r_A(x)~w_A(x)~r_A(y)~w_A(y)\ T_B&: r_B(x)~r_B(y)~w_B(sum)\[0.6em] S&: r_B(x)~r_A(x)~w_A(x)~r_A(y)~w_A(y)~r_B(y)~w_B(sum) end{align}$

在schedule 中，讀取了執行的中間結果，ACID中的isolation被破壞了，所以產生了inconsistent的結果。既然問題出在並發執行上，那我們確保順序執行不就好了嗎？在這個例子中，或者都可以保證結果的正確性。但是我們上文也提到，這樣的serial schedule性能非常差，respond time和throughput都不理想，在某些應用中甚至完全不可用。但起碼我們思考的方向是對的：我們既想要高並發的速度，又想要串列執行的isolation和正確性。那我們只需要保證一個schedule是「等價於」某個serial schedule的就行了，這就是 serializability（可串列性/化） 的概念[1][4]：

如果一個schedule 等價於 某個serial schedule $S=( au, prec_{S})$ ，那麼就是serializable（可串列）的。

那麼問題又來了：對於兩個schedule來說，什麼叫做等價呢？這就是我們要討論的關鍵問題了。接下來的幾個小節會討論三種不同的定義，並相應地得出 final state serializability、view serializability、和 conflict serializability 的概念。（我並沒有找到這些概念合適的中文翻譯，網路上的一些翻譯在我感覺也不是很貼切，所以我鬥膽自行翻譯了這三個概念，但還是會主要使用英文原文。）

終態可串列（final state serializability）

提起「等價」的定義，我們可能首先會想到function中「external equivalence」的概念：把兩個function當作黑盒，如果它們把所有相同的輸入都映射到相同的輸出，那從一個使用者的視角來看，這兩個function就是等價的——我們在外部並不能觀察到任何區別。同樣地，我們也可以從這個角度定義schedule之間的等價關係，如果兩個schedule在所有相同的資料庫狀態下執行都會使資料庫轉移到相同的最終狀態，那它們對我們來說就是等價的。正式地說[1]：

我們說兩個schedule 和是 終態等價的（final state equivalent），如果它們滿足：它們涉及的transactions相同；以及在所有對寫操作的解讀下（可能是任何關於之前讀取的數據的函數），對於所有的初始狀態， $Ixrightarrow{S_1}ILeftrightarrow Ixrightarrow{S_2}I$

我們可以相應地給出final state serializability的定義：

如果一個schedule final state equivalent to 某個serial schedule $S=( au, prec_{S})$ ，那麼就是final state serializable的。

這個定義非常直觀，可是我們該怎麼檢查兩個schedule是不是final state equivalent的呢？根據定義來檢查肯定不現實，我們沒法去檢查每一種可能的初始狀態，但是我們可以通過給schedule中的數據操作構建一個圖來進行驗證[1]：

對於每個schedule ，定義一個 augmented schedule 。除了包括中的所有transaction之外，還包含兩個輔助transaction 和 :

只有寫操作，寫入所有的object，相當於資料庫中所有object的初始值；
只有讀操作，讀取所有的object，相當於資料庫中所有object的最終值。

保留中的操作的順序，並保證在之前，在之後。（ $hat{S}equiv T_0~S~T_alpha$ ）
根據這個augmented schedule ，構建一個有向圖：

節點是中所有的數據操作（e.g., ）；
邊包含，如果 $o_1prec_{hat{S}}o_2$ ，以及：

在某個transaction 中，；或者
和屬於不同的transaction，並且從 中讀取（read from）。

我們說從 中讀取（ reads from ），如果：對於某個數據對象，；並且，並且和之間沒有其他操作也寫入了

舉個例子，對於以下兩個schedule ：

$egin{align} T_1&: r_1(x)~w_1(y)\ T_2&: r_2(x)~w_2(x)~w_2(y)\[0.6em] S_1&: r_2(x)~w_2(x)~r_1(x)~w_1(y)~w_2(y)\ S_2&: r_1(x)~w_1(y)~r_2(x)~w_2(x)~w_2(y) end{align}$