原文標題: High-Performance Concurrency Control Mechanisms for Main-Memory Databases原文鏈結:http://arxiv.org/pdf/1201.0228.pdf
摘要
將資料庫放在主記憶體中可以提供更多的平行交易能力。然而,傳統的同步控制方法無法讓其平行交易能力有顯著的提升。故,本篇論文介紹兩種針對記憶體式資料庫較有效率的同步控制方法。
這兩種方法目標都是讓唯讀型的交易從修改式交易中獨立出來,而其中不同之處在於:
1. 樂觀
2. 悲觀
為了避免上下文切換所帶來的效能損耗,交易在一般流程(Normal Process)絕對不會阻斷(Block),但為了確保交易的循序性,故,採用等待提交的機制。
為了要進行比較,也實做了單版本鎖定式的主記憶體式資料庫。從實驗結果來看,單版本鎖定式在交易短的時候有較佳的效能表現,但是它卻會在許多較苛刻的環境下效能表現不佳。多版本式雖然會有較高的成本但它對於熱點和長交易有較穩定的表現。
1. 導引
當前的資料庫管理系統都是設計成將資料儲放在硬碟中。然而,主記憶體的價格持續下跌;在過去30年中,每5年價格下降10%。最近Oracle Exadata X2-8的資料庫伺服器挾帶2TB大小的主記憶體,而在近幾年相信就能看到普通的伺服器挾帶Tera級的主記憶體。大多數的OLTP資料庫將會放到主記憶體中,並且甚至會將許多工作集都放到主記憶體中,只有在其很久沒被使用時才會被移出記憶體。會越來越少去外部儲存體存取資料。
DBMS優化成記憶體式且執行在多核心處理器伺服器,可以提供高交易率。在這樣的硬體環境下要如何有效的隔離同步執行的交易是一件極有挑戰性的事情。在Johnson et al的論文中提及當前的DBMS是藉由分割鎖定管理器來達成多交易隔離,而鎖定管理器就成了高交易數這個目標的瓶頸了。除此之外,較長的唯讀型交易亦會阻塞到寫入式交易。
本篇論文針對記憶體式OLTP資料庫研究出一套高效能的同步控制機制。我們發現傳統單版本式鎖定是脆弱的。它只有在短且沒有熱點交易的情況下有較好的表現,但是當多交易進行資源搶占或是某個耗資源的長交易都會造成效能急速下降。
研究發現,多版本的同步控制機制較強健且在高工作量的情況仍有不錯的表現。這讓我們想要研究如何將多版本同步控制放到記憶體式資料庫。我們設計兩種多版本同步控制機制:基於驗證的樂觀,另一個是基於鎖定的悲觀。這兩個機制是相容的,故, 可以讓這兩個機制同時存在於同一個資料庫中。我們系統化的探索和評估這兩個機制的優缺點。實驗證實,多版本式比單版本鎖定式要來的強健。
本篇論文有三點重大貢獻。首先,我們提出一個針對記憶體常駐資料優化型的多版本同步控制方法。第二,我們重新設計兩個基於鎖定的同步控制方法,一者為單版本一者為多版本式,並且兩者皆是應用在記憶體式資料庫上。第三,我們使用不同的工作壓力來評估這三種同步控制方法的效益。本次在高效能主記憶體資料庫研究的成果為:單版本鎖定式只有在當交易都是短暫並且資源競爭情發生較少時有著較佳的表現;高資源競爭或是高工作量的長時間交易則是多版本式表現較佳。並且樂觀式的效能要比悲觀式更好。
論文餘下部份的組成為:第二段包含了多版本式的初步概觀和描述版本的可視和可異動是決定於版本的時間戳記。樂觀和悲觀的描述分別在第三和第四段。第五段是效能實驗結果。相關作業在第六中述及,而第七段則為結語。正確性驗證在線上補遺中提供。[27]
2. 多版本儲存引擎
交易即為當多個寫入和讀取同時發生時仍能依順序執行完成。最簡單且常用的的多版本式同步控制即為快照式隔離(Snapshot Isolation, SI)。但是快照式隔離無法保障循序性,這是因為讀取和寫入邏輯是發生在不同時間點上,讀取是在交易開始而寫入則是在結束時才開始。然而,交易是否能循序端賴於我們能否保障縱使到了交易尾聲讀取所看到的仍是同樣的資料。
為確保交易T是循序的,我們必須守住下列兩個條件:
1. 讀取穩定性: 假若交易T讀取某個版本V1的資料,我們必須保障直到交易的尾聲V1仍可被交易T所視。意思是說,V1並不會到了交易尾聲時因其它交易提交(Commit)而變成了版本V2。實做上可以藉由在V1上施加讀取鎖定來預防資料異動,或是藉由驗證在交易要提交前驗證V1是否有被異動過。這可確保資料不會有不正常的操作-資料遺失。
2. 避免幽靈資料: 我們亦必須確保交易在掃描時不會有一個新版本突然跑出來。這可藉由兩個方法來達成:鎖定欲掃描的索引和資料表,或是在交易提交前重新再掃描一次檢查是否有新版本出現。這可確保資料不會有不正常的操作-資料多一筆。
較低的交易隔離等級較容易實做,是因為:
1. 重覆讀取(Repeatable Read): 我們只需保障讀取的穩定性。
2. 讀取已提交(Read Committed): 不需要鎖定或驗證,永遠只讓它讀取最後一個版本的資料。
3. 快照式(Snapshot): 不需要鎖定或驗證,只需要讓它都在交易啟始時讀取資料。
我們已經實做出一個主記憶體式資料庫引擎的雛型。我們先將視野拉到最高底來觀察資料該怎麼被儲存,資料該怎麼讀和異動,以及如何判定那一個版本的資料是可被讀取或異動的。
圖1. 範例為帳戶資料表。交易編號75從帳戶Larry移轉20元到帳戶John,但尚未提交交易。
2.1 儲存和索引
我們的雛型系統目前僅支援雜湊索引,實作上是使用非鎖定式的雜湊表。一張雜湊表可以有多個索引,並且任何紀錄不允許直接存取,全部都需要藉由查找索引。(i.e. 對資料表掃描這個動作來說,僅需要掃描雜湊表上所有索引桶即可)。所有使用到的技術都很一般並且可以藉由資料結構中的樹或跳躍式串列來實做出有序的索引。 圖1展示了一個簡單的銀行帳戶表,其包含了6個版本的紀錄。先暫時忽略掉紅色方框中的數字100。資料表擁有兩個欄位:姓名和存款。每個紀錄版本都有個可視時間,可視時間期間為儲放在啟始(Begin)和終止(End)兩個欄位中的時間戳記。一張雜湊表可以擁有許多索引,每個索引都有一個雜湊指標欄位。範例資料表擁有一個姓名索引。為了簡單化,我們假設雜湊函數將姓名第一個單字作為索引。同一個索引桶中的紀錄版本彼此會使用雜湊指標欄位鏈結。
雜湊桶J包含了4筆紀錄:John有三個版本而Jane有一個。紀錄鏈結的順序不是重點。Jane的單版本(Jane, 150)擁有的可視時間為:從15到無限(Infinity),亦即這筆紀錄是交易在時間15時提交的,並且它仍是可視的。John最舊的紀錄版本(John ,100)其可視時間為:從10到20。更新會建立一個新版本紀錄(John ,110),這筆新紀錄初始可視時間為20到無限。待會我們將來討論最後一個版本的紀錄(John , 130)。
2.2 讀取
每個讀取都會指定邏輯讀取時間和唯一版本,這個唯一版本指的是該版本的可視時間與讀取的邏輯讀取時間有重疊;而其它的版本都會被忽略掉。紀錄其餘的版本都沒有與邏輯讀取時間重疊,故,最多只會有一個版本的資料是可視的。要查詢John時,舉個例來說,先掃描索引桶J中的紀錄版本,但僅會回傳一個與邏輯讀取時間重疊的紀錄版本。
2.3 更新
索引桶L包含兩筆紀錄,這兩筆都是屬於帳戶Larry的。交易75是將Larry帳戶中的20元移轉到帳戶John中。也因此建立兩個新版本的資料,一個是為Larry建的(Larry, 150);另一個則是為John所建的(John, 130),並且將這兩個新版的紀錄插入到適當的索引桶。
注意,編號為75的交易已先將自己的交易編號儲放在新版本紀錄的啟始(Begin)欄位,而舊版本紀錄則是儲放在其終止(End)欄位。(在啟始和終止欄位上使用一個bit來標示當前資料性質)。交易編號儲放在舊版本的終止欄位中,其目的是將其作為寫入鎖並且預防其它交易會異動到此版本的資料,除此之外,還能起到標示目前是那個交易正在操作這個紀錄的版本。交易編號儲放在啟始欄位是在告知讀取者,這個版本的紀錄尚未提交並且它標示了目前是那個交易正在操作這個版本的紀錄。
現在,假設編號為75的交易提交在時間100。它接著會回傳這個時間戳記給舊的和新的版本紀錄,讓它們分別將這個時間戳記值取代原本的交易編號值。欄位最後的數值展示在舊版本和新版本紀錄的紅色方框中。舊版的紀錄(John, 110)現在已經擁有了它的可視時間為:從20到100；而新版本紀錄(John, 130)則是從100到無限。
每次異動都會建立一個新版的紀錄,故,我們需要將舊版紀錄做妥善的回收處理以避免記憶體空間耗盡。紀錄的版本只有在它已經不可視持續一段時間了才可以被刪除。在我們的雛型系統中,一旦版本已經被標示為垃圾,所有的執行緒都可以回收它的空間。雖然垃圾回收相當有效益並且可平行化,但是追蹤舊版本紀錄仍是會消耗掉許多CPU資源。關於垃圾回收演算法的細節已超過本篇論文的討論範圍。
2.4 交易階段
交易階段一共有四個狀態:
1. 活動(Active)
2. 準備(Preparation)
3. 已提交(Committed)
4. 中止(Abort)
圖2展示了交易的狀態移轉。
圖2. 交易的狀態移轉
任一個交易至少都會經歷三個狀態。我們先概略性的描述每個狀態;更多的相關細街在第三、四段落。
1. 交易開始;交易會取得一個啟始時間戳記並且將交易狀態設定為活動(Active)。
2. 一般性處理階段: 交易會將所有一般交易基本的相關處理都在此一階段完成。交易絕不會在此階段阻塞任何其它交易。以更新這個動作來說,交易複製它的交易編號到新版本紀錄的啟始欄位以及舊版本紀錄的終止欄位;刪除時亦是將交易編號放到可視版本紀錄的終止欄位。若此交易中止了,它會改變它的狀態為中止(Abort)並且直接跳到步驟4。當交易完成了一般性處理並且請求提交,交易會取得一個終止的時間戳記並且切換成準備階段。
3. 準備階段: 當處於這個階段,交易會判斷是否已符合提交的資格抑或是要中止交易。假如交易必需要中止,它會切換它的狀態為中止並且進入下一個階段(i.e. 後處理階段)。假如交易具提交資格,它會將所有相關的新版本紀錄和已刪除的版本寫入到重做(Redo)紀錄檔中並且等待其寫入到非易動式儲存容器(i.e. 硬碟或Storage)中。
4. 後處理階段: 假如交易已提交,交易會將時間戳記替換掉它在新版本紀錄的啟始欄位,以及舊版本的終止欄位(i.e. 刪除時也是將時間戳記寫到終止欄位)。假如交易已中止,交易會標記所有新版本紀錄為垃圾並且設定它們的啟始欄位和終止欄位為無限(Infinity),藉此標示它們是不可視的。
5. 交易結束。舊版本紀錄且長時間不可視會在此階段被回收。
時間戳記是全域且循序加值的計數器。交易取得唯一的時間戳記是藉由不可分割的讀取和計數器加值來達成。
2.5 版本可視性
在多版本下,讀取要先指定邏輯讀取時間。只有可視時間與邏輯讀取時間重疊的版本可被讀取。讀取時間可以是任意一個介於交易的啟始時間和當前時間的值。讀取時間的選擇是依同步控制方法的不同以及交易的隔離等級的不同而有所不同。更多細節在第三、四段落。
判斷可視版本時若也要避免讓交易在一般性處理階段阻塞其它交易是一個相當困難的事情。回想一下,當進行異動操作時,啟始和終止欄位可以暫時性的儲存交易編號。假如讀取者讀到同一個版本的紀錄,判定可視且無阻塞就需要檢查其它交易的狀態以及終止時間戳記並且更甚是要限制交易的處理順序。
我們檢視所有可能的情況,從簡單的和一般性的情況;啟始和終止欄位都儲放時間戳記,一直到啟始或終止欄位儲放交易編號。
啟始和終止欄位都儲放時間戳記
令RT標示為交易T的邏輯讀取時間。要判定紀錄版本V是否是交易T可視版本,我們檢查V的啟始和終止欄位。若兩個欄位都儲放時間戳記,我們就可以直接判斷RT是否介於啟始和終止欄位所儲放的時間戳記之間。若為真,V即為交易T的可視版本;反之,則否。
啟始欄位儲放交易編號
假設交易T讀取紀錄版本V並且找到其V的啟始欄位儲放另一個交易Tb的交易編號。版本V或許當前仍是可視的,但前題是交易Tb的狀態以及Tb的終止欄位所儲放的時間戳記。Tb或許,舉個例來說,若已提交了但尚未更改其最新版本紀錄的啟始欄位。如果是這個情況,V是一個已提交的版本並擁有啟始欄位的時間戳記值。表1簡述各種不同不同的狀況:
表1. 案例分析以及依版本V的啟始欄位包含Tb的交易編號相對應的動作
Tb的狀態
|
Tb的終止時間戳記
|
交易T檢查版本V是否可視的對應動作
|
活動
|
未設定
|
只有在T等於Tb且終止時間戳記為無限大的情況下版本V才可被T可視。
|
準備
|
TS
|
V的啟始時間戳記將會是TS,但版本V尚未提交。在判斷是否為可視時,將TS設定為V的啟始欄位值。若測試為真,則T可嘗試讀取V。
|
已提交
|
TS
|
V的啟始欄位會設定為TS,並且V已提交。將TS設定到V的啟始欄位來測試是否可視。
|
中止
|
無
|
忽略T;因為它已成了垃圾。
|
結束或找不到
|
無
|
重讀V的啟始欄位。Tb已結束所以它必定有最後的時間戳記。
|
若Tb依然在活動狀態,版本是未提交並且因此除了Tb外的交易都不可視。假如Tb多次修改紀錄,則只有最後一個版本是可視的。最後版本V只有在其終止欄位的值是無限時才是可視版本。
假若交易Tb處於準備階段,它已經擁有了結束時間戳記TS,且當Tb提交時,這個值將會是新版本紀錄啟始欄位的值。在此狀況下一個較穩當的方法就是交易T等待Tb提交。然而,我們希望避免在一般性處理階段有阻塞的動作,所以我們接下來會進行可視性測試;若測試結果為真,則允許T可嘗試讀取V。交易T的提交相依於Tb;藉此限制兩者的交易順序。即是,交易T只有在Tb提交後才可以提交。提交相依在段落2.7中有詳細的討論。
表1中剩餘的三個情況很直觀。
終止欄位儲放交易編號
一旦它需要決定版本V的可視時間早於交易T的讀取時間RT,我們直接去檢查V的終止欄位。若終止欄位儲放T的時間戳記,判定可視很直觀:V是否是交易T可視版本,只有在RT小於時間戳記。然而,若終止欄位儲放的是交易Te的交易編號,我們就必須去檢查Te的狀態和時間戳記。表2簡述了各種不同的狀況和相對應的動作,假設我們已判定V的啟始時間戳記小於或將會小於RT。
第一個例子(Te的狀態是活動)之前就討論過了。若Te的狀態是準備,它會擁有一個終止時間戳記TS,此值會在Te提交時設定到終止欄位。若TS大於讀取時間RT,很顯然的,當Te提交時V就成為可視版本。若Te中止了,V仍是可視版本,因為任一個交易在Te中止後對其進行異動都會獲得一個大於TS的時間戳記。若TS小於RT時,狀況就變得很複雜了:若Te提交了,交易T無法看到版本V,若Te是中止,則版本V就可視了。我們可以藉由強迫T等待Te提交或中止來解決這個問題,但是我們希望避免在一般性處理階段中阻塞任何交易。取而代之的是,我們允許T可以嘗試讀取V並且繼續往下一階段邁進。交易T會取得Te的交易相依,即為,T只有在Te提交後才能提交。
表2. 案例分析當V的終止欄位儲放Te的交易編號及相應動作
Te的狀態
|
Te的終止時間戳記
|
交易T檢查版本V是否在讀取時間RT下是可視的且其相對應動作
|
活動
|
未設定
|
V只有在V是交易T所新增的並且V的終止欄位所儲放的時間戳記為無限。
|
準備
|
TS
|
V的終止欄位所儲放的時間戳記將會是Te所提供的TS。若TS大於RT,則V為T的可視版本。若TS小於RT,則T可嘗試讀取V。
|
已提交
|
TS
|
V的終止欄位所儲放的將會是TS,並且V是已提交的。在測試可視性時,將TS設定為V的終止時間戳記。
|
中止
|
無
|
V為可視版本
|
結束或未找到
|
無
|
重讀V的終止欄位。Te已結束,因此它必定會擁有最終的時間戳記。
|
當Te的狀態為提交時是很直觀的,但當處於中止狀態時存在著一些溪竅。當Te已中止了,某些其它交易例如To,它或許會在交易T讀取V的終止欄位後潛進來,並發現到Te已中止且異動過資料。然而,To異動V的終止欄位在T讀取之後,並且To必定是已進入活動狀態。這意味著To會在T讀取V之後取得終止時間戳記,並且該值會晚於T的邏輯讀取時間, 這其實是沒關係的,因為只要Te是中止狀態T就能看見V。
若Te已結束或找不到,Te不是已提交了就是中止,最終,V的終止欄位絕對會有時間戳記,因此,僅需再重讀一次終止欄位且重試即可。
2.6 更新版本
假設交易T想要更新版本V。V只有是最後版本才可以被異動,所謂的最後版本亦即V擁有終止時間戳記為無限或它的終止欄位的值為Te的交易編號,並且Te的狀態為中止。若交易Te的狀態是活動或是準備,V就必須要是最後被提交的版本,但會出現一個未提交的最後版本。這就是寫入衝突。我們遵循先寫先贏的策略並且強迫T中止交易。
假設交易T找到的V是可異動版本。T接下來會新增一個版本並且將其插入資料庫中。第一步為原子式的儲存T的交易編號到V的終止欄位,藉此預防其它交易異動V。若插入新版本紀錄時發現到V的終止欄位已被修改過,則T就必須中止交易;其原因為:其它交易潛入並且在T將新版本紀錄插入到資料庫之前修改了V。假若儲存成功,T接下來會將新版本紀錄與其它同一個索引桶的紀錄鏈結。T亦儲存指向舊版本和新版本的指標;這會在後處理階段中完成這個動作。
2.7 提交相依
交易T1與交易T2有著提交相依,則T1只有在T2提交後才能夠提交。若T2中止,T1亦必需中止,故串接式中止是有可能做到的。T1只有是嘗試讀取或嘗試忽略版本時才會需要進行提交相依;而這是為了要取代等待T2提交的機制。
我們實做的提交相依是藉由註冊且回報的方式:T1註冊它的相於為T2,且T2在它提交或中止時會通知T1。每個交易都擁有一個計數器CommitDepCounter,它是用來計數還有多少尚未提交的相依個數。交易只有當CommitDepCounter為0時才可以提交,交易T亦有一個布林資料型別的變數:AbortNow,該變數是用來讓其它交易可以藉由設定它來告知交易T已中止。交易T亦有個用來儲存與T有相依的交易其交易編號集合: CommitDepSet。
當T1提交相依於T2時,T1會將自己身上的CommitDepCounter加1,並且將自己的交易編號加入到T2的CommitDepSet。當T2提交後,T2會輪詢每個在CommitDepSet中的交易,並且將它們的CommitDepCounter值減1。若T2中止,則T2會藉由設定它們的AbortNow旗標來告知它們交易已中止。若相依的交易已檢索不到了,這意味著這個找不到的交易早就中止了。
要注意的是需交易相依的交易T並不一定都是會等所有相依的交易,因為很多相依的交易很可能在交易T要提交之前就已經提交了。提交相依將所有等待濃縮成一個並且將其挪移到交易T提交之前。
某些交易需在提交前等待。等待有可能會引起死結。然而,死結不會發生,這是因為舊的交易不會等新交易。在等待圖(wait-for graph)中,每個邊的箭頭指向只會是新的交易(高結束時間戳記)指向舊的交易(較低的結束時間戳記),故,不可能在圖上看到迴圈。
3. 樂觀交易
這個段落描述更多關於在不同處理階段關於樂觀交易的細節。我們首先考慮循序(Serilizable)交易隔離等級,再討論較低的隔離等級。
在Kung和Robinson原本的論文中介紹了兩個驗證方法:後測和前測。我們採用後測,但將其針對記憶體式儲存方式進行優化。我們不採用驗證讀取集是否抵觸了其它交易的寫入集,而是採用檢查紀錄的版本是否一直到交易的尾聲都仍是可視的。拆分讀寫成不同階段其實並不需要;某交易修改後的紀錄版本是否可以被其它交易看到其先決條件是交易的狀態是已提交狀態。
循序式的樂觀交易會紀錄它的讀取/掃描/寫入。故,交易物件會有下列三個集合變數:
1. 讀取集: 內部儲放每個讀取的紀錄版本的指標。
2. 掃描集: 內部儲放每次重覆掃描時所需要的資訊。
3. 寫入集: 內部儲放異動後的紀錄版本(新和舊版本)、刪除後的紀錄版本(舊版本)、新增後的版本(新版本)。
3.1 一般性處理階段
一般性處理即為掃描索引(見段落2.1)來定位那個版本可讀取/更新/刪除。新增或是異動現存某個紀錄的版本都會增加紀錄版本,並且會將這個新的紀錄版本加到索引中。 索引掃描其實就是交易T指定一個索引I,和一個陳述句P以及邏輯讀取時間RT。陳述句的邏輯為
,而這裡的Ps指的就是搜尋陳述句,用於決定要掃描索引的那個區域,而Pr即為可選的陳述句。對於雜湊索引來說,Ps可說是欄位的雜湊鍵。而對於有序索引來說,Ps即為索引的有序鍵值的範圍陳述句。
我們概略描述在交易T以循序交易隔離等級進行掃描這個情境。所有的讀取都設定為交易T的邏輯讀取時間。
開始掃描: 當開始掃描後,它會註冊到交易T的掃描集中,故,交易T就可以在驗證時檢查是否有幽靈紀錄。為了要能夠反覆掃描,因此需要紀錄足夠的資訊。這些資訊大致上需要:索引I和陳述句Ps及Pr。實際上陳述句的指定和實做的方式有關。
檢查陳述句: 若紀錄版本V不滿足P,則掃描述會忽略這個版本並且繼續往下掃描。若掃描是區域式掃描且索引鍵值超出了區域的上限,掃描就會終止。
檢查可視性: 接下來我們會檢查版本V對於交易T的RT來說是否是可視的(見段落2.5)。測試結果或許是要看交易T2是否提交。如果是,T會註冊提交相依到T2上(見段落2.7)。若可視性測試結果為否,會忽略這個版本並接著往下一個版本掃描。
讀取版本: 若交易T只是想要讀取V,則沒有進一步檢查的必要。T紀錄讀取的方式即為新增指向V的指標到它自己的讀取集中。該指標將會在驗證時用到。
檢查可異動性: 若交易T是想要更新或刪除V,我們就必須檢查版本是否是可異動的。可視的紀錄版本判斷是藉由終止欄位值為無限或它儲放的是某個交易的編號且該交易已中止。一個未提交的版本其實亦可以被嘗試異動的,唯該交易已經完成了一般性處理階段後。
更新版本: 要更新版本V,交易T首先會新增一個新版的紀錄Vn,並且將Vn以原子式的設定V(i.e. 舊版本紀錄)的終止欄位值為T的交易編號。當T2已經先異動過V的終止欄位值,交易T此時就算是交易失敗。這就是典型的寫入式衝突,而交易T會被強迫中止。若T設定V的終止欄位成功,以另一個角度來說這就像是在V上加了寫入式互斥鎖,因為它可以用來預防其它交易去異動V。T紀錄更新的方式為添加兩個指標到寫入集:其一為指向V(i.e. 舊版本)的指標,另一個則是指向Vn(i.e. 新版本)的指標。這些指標會在接下應用在多個目的上:
1. 於提交時紀錄(Log)新版本,
2. 在提交或中止後進行後續處理,
3. 檢索某些已經可以被回收的舊版本紀錄。
新版本Vn直到交易T預提交後才可以被其它交易看見,接著T可以將Vn加入到雜湊表中。
刪除版本: 刪除就像是更新版本但不新增一個新紀錄版本。會先檢查V的終止時間戳記,設定終止時間戳計的流程和更新的流程一樣。若設定成功(i.e. 舊版本沒有被其它交易更動終止欄位),會將指向V的指標添加到交易T的寫入集,而整個刪除動作至此已完成。
圖3. 驗證時可能發生的狀況
當交易T執行到一般性處理的尾聲時,它會預提交並且開始它的準備階段。預提交的動作其實就只是取得終止時間戳記以及設定交易狀態為準備。
3.2 準備階段
樂觀交易的準備階段是由以下三個步驟所組成:
1. 驗證讀取
2. 等待所有的提交相依
3. 紀錄(Log)
驗證是由兩個步驟所組成:
1. 檢查版本是否可讀取
2. 檢查是否有幽靈
交易T會掃描它自己讀取集中的紀錄版本,藉此用來檢查這些版本一直到了交易尾聲是否仍是可視的。為了檢查幽靈資料,交易T走訪它自己的掃描集並且反覆掃描查找是否有版本在交易T的整個生命週期中可以被T直到交易尾聲都能看見。(交易T只有在嘗試忽略某個版本時,會在驗證時期註冊提交相依到別的交易)。
圖3描述了各種不同可能發生的案例。圖中展示了交易T的生命週期,和不同紀錄的版本V1~V4其可視時間,與讀取驗證與幽靈偵測預期中的結果。我們假設這四個版本滿足了搜尋的交易T的陳述句,並且它們都是由非T的交易所創建和結束。
(1) 版本V1對於T來說從啟始到結束都是可視的。若V1被T添加入它的讀取集,它會通過讀取驗證和幽靈偵測。
(2) 版本V2對於T來說只有在啟時是可視的,但到了尾聲就不可視了。若V2被T加入到它的讀取集,則讀取驗證會發生錯誤,但V2會通過幽靈偵測。
(3) 版本V3的啟始晚於T的開始時間,而結束卻早於T的終止時間,故,T從頭到尾都看不到它。它不會被T添加到讀取集,當然它也就不會被T驗證讀取。T根本看不到V3,故V3對於T來說也不會是幽靈。
(4) 版本V4是在T開始一段時間後才誕生,而T即便到了尾聲也能一直看到它存在,故,V4對於T來說是一個幽靈。它並不會被T添加到讀取集中,因為它在T開始時並不存在。
若T沒有通過驗證,它就不符合循序的規則,它必需被中止。若T通過驗證,它就需要等到所有提交相依完成,若無則無需等待。T可以前往下一階段-後處理階段,除非是T的CommitDepCount為0且AbortNow旗標值被設定了(i.e. 意味著交易中止)。
為了要完成提交,T會掃描它的寫入集並且將它自創建的紀錄版本寫到紀錄檔中。紀錄檔紀錄交易的順序是依交易的終止時間戳記來決定的,故,想要做到讓不同交易串流儲放到不同裝置上是可行的。刪除是藉由寫入唯一鍵來達成,在最糟的狀況下,可能需要將所有欄位都寫入。在紀錄檔寫入完畢後,T會設定它自己的狀態為已提交,藉此通知提交已完成。
3.3 後處理
在這個階段,一個已提交的交易TC會傳遞它自己的終止時間戳記到寫入集中新舊版本的啟始和終止欄位。已中止的交易TA設定它新版本的啟始欄位為無限藉此讓其它交易都無法看到這個版本,並且重設舊版的終止欄位為無限大;若已經有某個交易偵測到TA交易已中止並且創建了一個新版本還重設了舊版本的終止欄位,則TA就不需要再去修改舊版本的終止欄位值。
交易接下來會處理所有CommitDepSet有註冊的交易。假若交易中止,它會藉由設定CommitDepSet所有註冊的交易其AbortNew旗標來強迫它們也中止交易。假若交易提交完成,他會檢索所有註冊的交易並且將它們的CommitDepCount減1,除此之外,若某個交易的CommitDepCount為0則喚醒他。
一旦後處理完成,則這個交易已經不被需要了,它會從交易表中移除,但這不代表它已完全消失了;它身上的寫入集中指向舊版本的指標可被用於垃圾回收。
3.4 低交易隔離等級
採用較低階的交易隔離等級代價較低廉。交易採用高隔離等級就需要承擔高隔離等級所帶來的-懲罰無辜的旁觀者。
反覆讀取: 反覆讀取是用於當需要讀取的穩定性但不強調預防幽靈。我們在實做反覆讀取是藉由在提交前驗證讀取集來達成。由於幽靈讀取並不需要,交易的掃描就不須要紀錄。交易的啟始時間即為邏輯讀取時間。
讀取已提交: 讀取已提交只保障了所有讀取的版本都是已提交的。我們藉由使用當前時間作為邏輯讀取時間來達成。沒有任何驗證,故,交易的讀取和掃描都不需要紀錄。
快照隔離: 實做快照隔離對我們的案例來說是相當直觀: 總是只在交易開始時讀取。不需要驗證,故,掃描和讀取都不需要被紀錄。
唯讀交易: 假若此交易已知是一個唯讀交易,採用快照隔離或讀取已提交能夠有最佳的效能表現;要採用快照隔離還是讀取已提交全賴於交易是否需要看到一致性的資料。
4. 悲觀交易
悲觀交易是藉由讀取鎖定來預防它會讀到不正確的紀錄。本段落描述我們所設計的針對主記憶體資料庫優化的多版本鎖定。
循序式悲觀交易需追蹤它所讀取的版本,需追蹤的有:交易掃描過的雜湊桶和新舊版本,交易會維護三個集合:
1. 讀取集: 其內儲放指向交易讀取鎖定版本的指標。
2. 雜湊桶鎖定集: 其內儲放指向已走訪過的雜湊桶並且被交易鎖定的指標。
3. 寫入集: 其內儲放參照的已更新版本(舊和新),已刪除版本(舊),新增的版本(新)。
4.1 鎖的類型
我們使用兩種鎖: 紀錄鎖和雜湊桶鎖。紀錄鎖被置放在版本上,用於確保讀取的穩定性。雜湊桶鎖定被置放於雜湊桶上,用於預防幽靈紀錄。在我們的雛型系統中相對應的名稱對應到它們在雜湊鎖引上的使用,而有序索引的區域鎖可以使用同樣的方法來實做。
4.1.1 紀錄鎖
更新或刪除只能操作在紀錄的最終版本上;舊版本不準更新。因此,紀錄鎖只會被用在紀錄上最後一個版本;絕不會是用在舊版本上。故,需要一個多讀取單一寫入的鎖。
我們不想要儲存紀錄鎖到不同的表上-這會讓系統變慢。取而代之的是,我們將紀錄鎖嵌入到版本的終止欄位上,故需要額外的空間來儲放。在我們的雛型系統中,版本的終止欄位其大小為64bit。如上所述,這個欄位是用來儲放時間戳記或是交易的編號,並使用一個bit來標示目前是儲放那一個。我們需要改變其儲放格式讓它能構儲放紀錄鎖。
1. 內容型別(1 bit): 標示內容型別僅使用63bit。
2. 時間戳記(63bit): 當內容型別為0時。
3. 紀錄鎖(63bit): 當內容型別為1。
3.1. 讀取上限鎖(1 bit): 用這個旗標來標示不再接受更多的讀取鎖了。被用於預防饑餓現象。
3.2. 讀取鎖計數器(8 bits): 讀取鎖的個數。
3.3. 寫入鎖(54 bits): 交易編號(註: 用來作為版本的寫入鎖)或是無限大(註: 54bits的最大值)。
我們不去追蹤交易是否有版本的讀取鎖。每個交易都會紀錄它的讀取集,故,我們可以藉由每個交易的讀取集去找出目前是那個交易擁有紀錄版本的讀取鎖。這是為了要處理不常發生的死結偵測。
交易藉由原子式增加紀錄版本V的讀取鎖計數器來變相取得讀取鎖。當讀取鎖計數器達到設定的最大值(註: 255)或是讀取上限鎖這個旗標被設定時,其餘交易就不能再取得這個紀錄版本的讀取鎖。
交易藉由原子式複製它自己的交易編號到紀錄版本的寫入鎖欄位變相取得寫入鎖。此舉做到了寫入的鎖定以及識別此紀錄版本當前是那個交易擁有其寫入鎖。
4.1.2 雜湊桶鎖(區域鎖)
雜湊桶鎖定只有在採用循序式交易隔離等級時才會使用來預防幽靈現象。當交易TS啟動雜湊桶掃描後,它會鎖住雜湊桶。雜湊桶鎖可以被多個交易持有,雜湊桶鎖資訊由以下欄位構成:
1. 鎖定計數器: 雜湊桶上的鎖定數量。
2. 鎖列表: 擁有此雜湊桶鎖定的交易列表。(註:採循序紀錄)
以當前的實做來說,在雜湊桶上儲放鎖定計數器可以讓檢查這個雜湊桶是否被鎖定更加快速。鎖列表使用陣列這個資料結構來實做,儲放在紀錄雜湊桶鍵值的雜湊表中。
交易TS增加B的鎖定計數器的值並且由雜湊表定位到鎖列表再將自己的交易編號加入到鎖列表中,完成這幾個動作後才算是取得雜湊桶B的鎖定。交易TS在釋放鎖定時,則是從鎖列表中移除自己的交易編號並且將雜湊桶的鎖定計數器值減1。
在有序索引中的區域鎖定可以採用相同的方式來實做。若索引是採用樹狀結構來儲放,放一個鎖在一個節點上即可鎖定由此節點為根節點的整顆子樹。若索引是採用跳躍式列表來實做,則是藉由取得層級鎖來達成;而層級鎖僅包含與之相同高度的下一層級。
4.2 迫切更新, 等待相依
在傳統的多版本鎖定實做中,假若是企圖更新/刪除一個已有讀取鎖的版本或是插入/異動一個新紀錄版本到已被鎖定的雜湊桶中,都會讓交易TU阻塞其它交易。這或許造成常態性的阻塞和執行緒切換。執行緒切換是相當昂貴的,會花費到上千行的指令碼。於主記憶體型系統來說,只需要幾條執行緒的切換就能造成執行交易上的重大效能損耗。
為避免阻塞,我們允許交易TU可以快速更新/刪除被讀取鎖定的紀錄版本V,但是,為確保執行的順序,TU不能在紀錄版本V上所有的讀取鎖釋放前預提交。同樣地,交易TR可以取得紀錄版本的讀取鎖,即便這個版本已經被交易TU取得了寫入鎖。若是這樣,TU不能在TR釋放讀取鎖之前預提交。
要注意的是,迫切更新/刪除並非是嘗試性的,因為它根本不管TR是提交或是中止狀態;它只管TR是不是釋放了讀取鎖。
雜湊桶鎖定同樣也是如此。假設雜湊桶B由交易TS1和TS2所鎖定。TU在更新時是被允許插入一個新版本紀錄到雜湊桶B的,但是不允許在TS1和TS2完成交易並釋放其手上的雜湊桶鎖之前提交。
我們藉由等待相依來守住交易執行順序。等待相依強迫異動資料型交易TU在取得終止時間戳記和提交之前要等待其它交易。等待相依有兩種方式:讀取鎖相依和雜湊桶鎖相依;兩者不同之處在於它們等的是什麼。
交易T需持續追蹤得到和釋出的等待相依。T只要在它等待其它交易時即為得到等待相依,並且當有其它交易在等待T時即為釋出等待相依。為達成等待相依在每個交易中都具有下列屬性: 與得到等待相依相關的屬性:
1. 等待計數器: 指示交易目前得到多少等待相依。
2. 最大等待: 為避免後續得到的等待相依發生饑餓現象,當設定此值時就不允許再添加新的等待相依。
與釋出等待相依相關的屬性:
1. 等待中的交易列表: 紀錄所有在等待此交易完成的所有交易編號。
4.2.1 讀取鎖定相依
交易TU更新/刪除了一個版本V時,若版本V有讀取鎖定就需要等待。TU除非是V的讀取鎖計數器為0,否則無法獲得終止時間戳記並開始提交流程。
當交易TU更新/刪除版本V時,它會藉由複製交易編號到寫入鎖欄位來取得V的寫入鎖。若V的讀取鎖計數器大於0,則TU便藉由增加V的等待計數器來取得V的等待相依。
TU或許也有可能是因為其它交易TR已取得V的讀取鎖,故TU得到了V的等待相依。交易TR想要讀取版本V就必須先藉由增加V的讀取鎖計數器來取得V的讀取鎖。若V的最大讀取鎖旗標值被設定或讀取鎖計數器已達到最大值(註:255)時,TR將無法取得讀取鎖並且TR會被強迫中止。另一種狀況是,若V沒有寫入鎖定並且V的鎖定計數器大於0,則TR會累增V的讀取鎖計數器並且接著處理後續事宜。然而,若V有被TU持有寫入鎖,並且V的讀取鎖僅TR持有,則TR必須強迫TU等待。TR檢核TU的最大等待旗標。若已被設定,TU便無法進行等待相依並且被強迫中止。另一種狀況則是所有交易都依順序執行並且TR藉由增加V的讀取鎖計數器來取得讀取鎖,且藉由增加TU的等待計數器來取得等待相依。
當交易TR釋放了版本V上的讀取鎖,它亦需釋放相關的等待相依。若V身上並沒有寫入鎖,TR會遞減V的讀取鎖計數器並且接著執行相關事宜。若V被寫入鎖定並且V的讀取鎖計數器大於1也是同樣的處理方式。然而,若V被TU持有寫入鎖並且V的讀取鎖計數器為1,TR被強迫中止並釋放V上最後一個讀取鎖,並也因此亦需釋放TU在V上的等待相依。TR原子式的設定V的讀取所計數器為0而最大讀取鎖為true。若設定成功,TR找出TU並且遞減TU的等待計數器。
在釋放等待相依前設定最大讀取鎖旗標是有其必要的,因為這或許是TU的最後一個等待相依。假如是這樣,TU就可以自由地取得終止時間戳記並且開始它的提交流程。當V上已無讀取鎖的情況下,TU的提交是無法被遞延的。換句話說,在V上加讀取鎖也不會有任何影響。
4.2.2 雜湊桶鎖定相依
循序式的交易TS藉由累增雜湊桶B的鎖定計數器和添加交易編號到B的鎖定列表來取得B的鎖定。TR進行雜湊桶鎖定的目的並非是要拒絕雜湊B加入新紀錄版本,而是要預防讓那些新版本紀錄被TR看見。這指的是,其它交易TU可以添加一個新版本到雜湊桶B,但,若這麼做,TU便無法預提交直到TS已完成了它的所有交易動作並且釋放B的鎖。要這麼做就需要讓TU獲得TS的等待相依。
TU可以藉由它自己或是由TS強加的方式來處理等待相依事宜。我們將會討論這兩種方式。
假設在新增/更新時TU中止了添加新版本V到雜湊桶B。TU檢查B是否有雜湊桶鎖,TU會藉由添加它自己的交易編號到雜湊桶B的鎖定列中所有的交易TS的等待列表並且累增它們的等待計數器來取得等待相依。若TU的最大等待旗標被設定,TU就無法取得等待相依並且會被強迫中止。
假設循序式交易S正在掃描雜湊桶B並且發現版本V滿足TS的搜尋陳述句,但是該版本對TS來說是不可視的,這是因為V正在被TU持有寫入鎖並且它尚未結束交易。若TU在TS提交前就已提交,V對TS來說就會變成幽靈。為預防此一狀況,TS藉由增加TU的交易編號到它自己的等待交易串列並且累增TU的等待計數器來達到註冊等待相依到TU的效果。假如TU的最大等待旗標被設定,則TS就無法強加等待相依並且會被強迫中止。
當循序式交易TS已預提交了並且取得了終止時間戳記,它接著會釋放它的釋出型等待相依。它會掃描它自己的等待交易列表並且遍歷每一個交易T,找到它們,並將它們的等待計數器減1。
4.3 處理階段
本段落描述鎖定對於交易在各個不同處理階段中所造成的影響。
4.3.1 一般處理階段
回想一下一般處理是由掃描索引取得欲讀取的紀錄版本/修改/刪除所組成。新增或是修改會建構一個新的紀錄版本,並且依紀錄類型的不同加入到對應的索引中。 我們現在已知悲觀交易T與樂觀交易不同之處在於掃描方式,並且這是基於T的交易隔離等級而定。以快照交易隔離等級來說,邏輯讀取時間總是交易的啟始時間。對於其餘交易隔離等級來說,邏輯讀取是它們在找到可視紀錄版本的那個時間點。
開始掃描: 假如T是循序交易隔離等級,它會取得雜湊桶B的鎖用以預防幽靈,並且會紀錄在它自己身上的雜湊桶鎖定集合。其它交易隔離等級則不會取走雜湊桶B的鎖。
檢查陳述句: 和樂觀交易相同。
檢查可視性: 做法和樂觀交易一致,不同之處在悲觀交易會在特定狀況下進行提交相依。若版本V是不可視,版本V會被忽略並且會接著繼續掃描,這是為了要達成交易隔離等級所期望的循序性。若T是循序交易隔離等級並且V被交易TU取得寫入鎖,而TU目前尚未結束的狀況下,V將成為幽靈,因此T會強加等待相依到TU身上藉此延遲TU的預提交。
讀取版本: 如果T是循序或反覆讀取交易隔離等級,並且V是最終版本,T會試著去取得V的讀取鎖。若T無法取得讀取鎖,則T會中止交易。若T是採用更低的交易隔離等級或是V並非是最終版本,就不需要讀取鎖了。
更新版本: 如同樂觀交易一樣,T建構一個新版本N,設定V的寫入鎖;若V已被讀取鎖定,則累增V的等待計數器藉此達成等待相依。T接著會將新版本N插入到索引中。若T要加入的鎖引雜湊桶B已被其它交易鎖定,則T會和所有在雜湊桶B鎖定的交易註冊等待相依。
刪除版本: 刪除某種層面來說是一種更新,但是並不會建構一個新的版本。T設定版本V的寫入鎖並且若V已被讀取鎖定,藉由累增V的等待計數器達成等待相依。
當交易T到了一般處理階段的尾聲,它會釋放讀取鎖和雜湊桶鎖。若T有等待相依(註: 它的等待計數器大於0),則它會開始等待。一旦它的等待計數器為0時T會預提交,亦即取得了終止時間戳記且設定它的狀態為檢驗。
4.3.2 準備階段
悲觀交易不需要檢驗-只需要關注鎖。然而,悲觀交易T在這個階段或許會有提交相依。如果有,T就要等到那些等待的對象結束交易才能接著去寫入紀錄檔並且提交。若提交相依失敗,則T會被中止。
4.3.3 後處理階段
和樂觀交易相同。不同的是不需要顯式的釋放寫入鎖;因為在更新啟始和終止欄位時就達到類似的效果了。
4.4 死結偵測
提交相依只會發生在交易已預提交且正在檢驗中。如上所述(註: 段落2.7)提交相依無法導致或造成死結。
等待相依卻會導致死結。為了要偵測死結,我們建立了一個等待圖的標準,藉由分析當前正在阻塞中的所有交易其等待相依。一旦等待相依圖被建構出來,任何用來找出圖中是否有迴圈的演算法都可以套用。我們的雛型使用Tarjan的演算法來找出強連結元件。
等待圖是一種有向圖,交易為圖中的節點而等待關係為邊。若T2在等待T1完成,則在等待圖中T2到T1會有一個邊。這個圖由下列三步驟建構:
1. 產生節點: 掃描交易表,若T已完成它的一般處理階段並且因為等待相依而被阻塞中,則將此交易T建構成節點N(T)。
2. 由顯式相依產生邊: 因為雜湊桶鎖定導致的等待相依其等待交易列表中必定有值。對每個在等待圖上的節點T1,將其等待交易列表中所有的交易T2都添加從T2到T1的邊。
3. 由隱式相依產生邊: 在已被讀取鎖定的版本V上的等待相依即為隱式相依,所有持有V讀取鎖的交易都被阻塞。我們可以藉由檢查交易的讀取集來找出那個交易正持有讀取鎖。建構由隱式相依的邊可以採用如下步驟。遍歷每個已在等待圖上的交易T1和T1身上的讀取鎖定集: 若V已被T2持有寫入鎖,且T2也在等待圖中,則添加從T2到T1的邊。
當等待圖正在繪製的時候,一般處理階段也正在進行中,故,等待相依可能會是:建立/已處理,而交易可能會阻塞或解除阻塞。為此,當一般處理終止時,最終的等待圖可能會不準確。但這無所謂,因為若真的有死結,不處於死結的交易不會出現在等待圖中。仍是有些許狀況會讓死結偵測失誤,但這可以藉驗證參與死結的交易是否仍處於阻塞,並且邊是否仍被未結束的等待相依所覆蓋。
4.5 和平共處
在我們的設計中有一個有趣的地方即為樂觀和悲觀交易可以被混合使用。會需要讓樂觀交易和悲觀交易共存是因為:樂觀交易必須進行讀取鎖定和雜湊桶鎖定。為了讓交易T可以取得讀取鎖和雜湊桶鎖,需進行一些修改:
1. T會使用54bit的交易編號對版本進行寫入鎖定,並且不會覆寫讀取鎖。
2. T修改或刪除已讀取鎖定的版本V,交易T會對V進行等待相依。
3. T新增版板到雜湊桶B,它會檢查雜湊桶鎖並且若有需要會進行等待相依。
5. 實驗成果
我們的雛型儲存引擎實做了樂觀和悲觀機制。我們亦實做了一個同步控制鎖的單版本儲存引擎。實做都是針對主記憶體式資料庫優化並且不使用中央鎖定管理,因為它有可能會變成是系統的瓶頸。取而代之的是,我們嵌入一個鎖定表到每一個索引中,並且對分割的鎖定表中的鎖定都指派一個雜湊鍵值給它。鎖定覆蓋相同雜湊鍵值的所有的紀錄,這可以被用來預防幽靈。我們使用逾時的機制來偵測且中斷死結。
實驗跑在Intel Xeon X5650 @ 2.67GHz(Nehalem) 每個槽都有6核心的機器上。啟動超執行緒。系統的主記憶體大小為48GB,每個槽都有12MB大小的L3快取,每個核心都有256KB大小的L2快取,以及分離式的32KB L1-I和L1-D快取。採用NUMA並且記憶體延遲是非對稱式: 存取遠端槽的記憶體比本地記憶體約莫會慢個30%。我們調整雜湊表適當大小,故,沒有碰撞。作業系統採用Windows Server 2008 R2。
每個交易都會產出交易紀錄,但會採用非同步的方式寫入到持久式儲存裝置;交易不會等待紀錄檔的I/O完成。非同步交易紀錄可以讓我們提交交易紀錄時採用批次的方式(群組式提交),大幅降低I/O操作的數量。所需的I/O頻寬還是少不了: 每次更新都會產生交易紀錄,它會儲存新和舊版本的紀錄,超過8bytes以上的超資料。即便每秒有近百萬的更新,I/O頻寬的量連一般桌機都可以應付。這個選擇讓我們可以更專注在同步控制所造成的影響。
傳統的硬碟式交易處理系統需要幾百個同步交易來達到最大吞吐量。這讓系統在等待硬碟I/O時能有更好的效能。我們的主記憶體引擎不需要等待硬碟I/O,故,不需要額外的執行緒。我們觀察CPU在多重程式(註: 程序不需要CPU時,就讓給下一個程序)程度相等於硬體執行緒數量時CPU的利用率是最高的;這讓同步交易其吞吐量下降。我們因此限制了同步交易的數量為最多24個,這讓執行緒的數量是在我們機器能夠負荷的範圍內。
我們實驗三個CC機制: 單版本鎖定引擎(標記為1V),多版本引擎且採用樂觀交易(標記為MV/O),而多版本引擎且採用悲觀交易(標記為MV/L)。
5.1 同質性的負載
我們首先展示參數化假資料負載的成果。藉由各種不同的負載參數,我們系統化的探索並且描述在不同的機制下的負載其敏感度為何。我們專注在短更新交易,這類交易是OLTP常見的類型。負載是由單交易類型的讀取R和寫入W於N筆具唯一鍵的資料表上所產生。
各種不同同步控制機的資料庫記憶體使用狀況都不同。在1V中,每筆資料列都會消耗雜湊表24bytes以上的資料內容大小以及8bytes以上大小的"下一個(Next)"指標。兩種多版本機制都會額外用掉16bytes在儲存啟始和終止欄位(註: 參考圖1),但總資料大小和負載所需的版本平均數量有關。比較兩個多版本機制,MV/L用到的記憶體較多,這是因為要維護雜湊桶鎖的關係。
5.1.1 彈性(讀取已提交)
我們首先展示交易吞吐量與多重程式層級的刻度。在這個實驗中每個交易都進行10讀取2寫入(R=10, W=2)於擁有一千萬筆資料的資料。交易隔離等級為讀取已提交。
圖4. 低資源競爭的彈性
圖4的Y軸為交易吞吐量X軸為多重程式層級。在低資源競爭下,吞吐量於三者來說都是線性的成長到6個執行緒。超過6個執行緒後,我們可以看到由於資料分散到兩個NUMA節點的關係造成存取延遲,在超過12條執行緒後我們看到超執行緒的效果了。
對1V來說,超執行緒會讓它的加速緩下來,但是仍是以線性成長,直達到了最大2M的每秒交易量。多版本機制有較低的吞吐量,這是因為版本管理和垃圾搜集會有一些額外的負擔。每次更新創建一個新版並且清除舊版本這些不常做的動作其實比單純更新消耗還要多的資源。
比較兩個多版本機制,MV/L比MV/O還要低30%。這是因為有額外的寫入相依追蹤和鎖定所致,這些都會提高記憶體使用量。這兩個動作會銷耗掉MV/L其相較於執行相同指令數量20%以上的CPU週期,並且每個交易附帶的控制邏輯還會再銷耗10%以上的CPU週期。
5.1.2 調整為資源競爭(讀取已讀取)
紀錄更新變得更頻繁(熱點)造成三種CC機制的問題。在鎖定機制中,高資源競爭會導致交易等待,因為鎖定衝突以及死結的關係。在樂觀機制中,熱點會造成檢驗錯誤以及寫入式衝突,這會提高交易中止率並且浪費很多資源。於硬體層來說,某些存取頻繁的資料項目實際上是放置在每個核心裡私有的L1或L2快取中。要讓硬體發揮到極致,只需要產生非常高的核心對核心流量就能保持快取的一貫性。
我們藉由執行相同的R=10和W=2的交易於擁有1000筆資料的資料來製造熱點效應。交易隔離等級為讀取已提交。圖5展示在高資源競爭下的吞吐量。即便是在這種情境下,所有的機制仍能達到每秒百萬的交易量,MV/O略略超過其它兩個。1V在6個執行緒時達到它最高的吞吐量,然後在執行緒數達到8之後開始下降。
圖5. 在高資源競爭情況下
5.1.3 高交易隔離等級
上述的實驗是跑在讀取已提交這個交易隔離等級,它在許多商業資料庫引擎是預設的交易隔離等級,它可以預防髒讀取並且提供高同步能力。更高的交易隔離等級預防更多的異常現象,但也降低了吞吐量。在這個實驗中,我們使用與5.1.1中相同的負載,我們修正了多重程式層級為24,並改變交易隔離等級。
表3. 在更高的交易隔離等級下的吞吐量,以及與讀取已提交相比的效能下降百分比
在表3中,我們描述了每個機制的交易吞吐量及其交易隔離等級。我們亦描述了與採用讀取已提交相較之下吞吐量下降的百分比。
反覆讀取對單版本或雙版本所造成的負擔較小,低於2%。MV/O需要反覆的在交易尾聲時讀取,這會造成8%的吞吐量下降。對於循序交易隔離等級來說,1V機制使用鎖定來保護雜湊鍵值,並且也保障了幽靈現象不會發生,且下降2%的吞吐量。兩種多版本機制採用循序後下降10~19%的吞吐量: MV/L取得讀取和雜湊桶鎖,MV/O需要在檢驗時反覆每次的掃描。MV/O的交易請求更高的交易隔離等級會承載所有的成本。這和一般鎖定機制的狀況不太一樣。
5.2 異質性負載
在前面段落的負載是針對高異動的情境。在本段落,我們修正多重程式層級為24並且我們探索添加唯讀交易到負載中會有什麼影響。
圖6. 唯讀交易所造成的影響(低資源競爭)
圖7. 唯讀交易所造成的影響(高資源競爭)
5.2.1 短讀取交易所造成的影響
在本實驗中,我們改變讀取和修改交易的比例。有兩種交易類型並採用讀取已提交交易隔離等級: 修改交易產生10讀取和2寫入(R=10, W-2),唯讀交易產生10讀取(R=10, W=0)。
圖6的Y轴為吞吐量X軸則為負載中唯讀交易的不同比例並且實驗是針對資料表資料有1千萬筆資料。最左邊的指標(x=0%)代表是僅有修改式交易如同使用24條執行緒的5.1.1。當我們加入唯讀交易後,效能在三種機制的差異較小。這主要是因為異動活動被減少了,減少了垃圾搜集的工作。
多版本機制在唯讀交易比例較高時效能會比1V高。當交易是唯讀,兩種多版本機制行為變得單一:交易讀取一個一致的快照並且不需要進行鎖定或檢驗。就比較來看,1V為了指標(Cursor)的隱定性,即便是唯讀交易也要取得或釋放短讀取鎖,這對效能產生了不好的影響。
圖7中,我們反覆相同的實驗,但模擬熱點的資料表只有1000筆資料。最左邊的座標(x=0%)代表的是僅修改負載如在高資源競爭且僅24條執行緒的5.1.12一樣。同步控制多版本機制比1V的吞吐量還要高出63%和73%。
5.2.2 長讀取交易造成的影響
OLTP中並非所有的交易都是短交易。使用者通常會需要執行例行性的報表查詢於現行系統上。這些長時間的唯讀交易或許在資料庫中占較大的比例。少量長時間查詢的存在應該是不會對一般的OLTP交易造成吞吐量的影響。
這個實驗旨在研究三種同步控制方法在這種情境下的表現。我們使用擁有一千萬筆資料的資料表,並且修正同步交易數量為24。負載由兩種交易類型組成: (a) 長的, 交易一致的(循序交易隔離), 唯讀查詢10%的資料量(R=1百萬, W=0) (b) 短修改交易(R=10, W=2)。
圖8. 修改混合長讀取交易的吞吐量
圖9. 讀取混合長讀取交易的吞吐量
圖8和圖9的Y軸為修改和讀取吞吐量,X軸為各種不同數量的同步長唯讀交易。在最左邊的座標(x=0%)代表所有的交易都是短的修改交易,最右邊的座標(x=24)所有的交易都是唯讀交易。在x=6上,舉個例來說,有6個唯讀和(24-6)個短修改交易同時間執行。
關注圖7上修改的吞吐量,我們可以看到1V比多版本快了近兩倍,當所有的交易都是短修改交易,於x=0上(這和我們在同質性負載的實驗5.1段落是一致的)。然而,在長時間唯讀交易加入之後發生了很大的改變。在X=1時,1V的修改吞吐量掉了75%。相對地,多版本的修改吞吐量只掉了5%,多版本的吞吐量已經比1V快了兩倍。效能的差距將會隨著唯讀交易的量而變大。當50%的交易都是長讀取交易,在X=12時,多版本已經比1V快了將近80倍。在讀取吞吐量方面(註: 圖8),兩個多版本機制都和1V一樣。
5.3 TATP結果
在前面段落所使用的負載可以讓我們找到三種同步控制機制最基本的不同點。然而,實際的應用程式會是在單一索引上隨機的讀取和修改一個值。我們藉由一個簡單但是貼近真實的OLTP應用程式的模型作為評量基準來總結我們的實驗評估。 TATP基準模擬一個電話通訊應用程式。資料庫是由四張資料表且每張資料表都擁有兩個索引組成。評量基準跑在一個隨機混合七個短交易所組成: 每一個交易產生平均最少5個操作。80%的交易僅查詢,16%修改,2%新增,2%刪除。我們調整資料庫有2億個使用者,並且產生的鍵值是使用由評量基準所指定的非均勻隨機分佈。所有的交易都採用讀取已提交交易隔離等級。
表4. TATP結果
| | 1V | MV/L | MV/O |
| 每秒交易量 | 4,220,119 | 3,129,816 | 3,121,494 |
表4展示了三種機制每秒提交的交易量。我們的同步控制機制可以讓低階伺服器承受每秒幾百萬交易量的吞吐量。這比先前提出的TATP硬碟式系統或主記憶體式系統還要高。
6. 相關工作
同步控制擁有一個長且豐富的歷史可回溯及資料庫系統的起源。某些優秀的在同步控制的概念和書都是可用的。
多版本同步控制方法亦擁有一個很長的淵源。三種多版本方法:多版本時間戳記排序(MVTO),雙版本雙階段鎖定(2V2PL),以及多版本混合方法。2V2PL使用最多兩個版本:最後提交以及已異動但未提交。他們亦描繪了一個允許多個未提交版本和允許讀取者讀取未提交版本的草圖。混合方法使用MVTO於唯讀交易和嚴格2PL於修改型交易。
同步控制的樂觀方法是由Kung和Robinson所提出,但是他們只考量到單版本資料庫。許多多版本同步控制機制已經被提出,但是我們發現只有兩個有採用樂觀方法: Carey提出的多版本嚴格檢驗(MVSV),Agrawal et al提出的多版本平行檢驗。這兩種機制都是樂觀且多版本,他們與我們的機制有很大的不同。他們的交易隔離等級是反覆讀取;其它交易隔離等都沒有討論。MVSV在檢驗時是循序的,故,檢驗是否快速就成了瓶頸。MVPV檢驗採用平行式,但檢驗後修改是循序的。比較上,只有我們方法中的臨界空間才會取得時間戳記;所有動作都是採用平行處理。取得時間戳記是單一指令(註: 單元式累增),故,臨界空間實際上非常短。
快照式交易隔離(SI)是一種多版本機制,被用在許多資料庫系統中。許多商用資料庫系統都支援快照隔離於隔離唯讀交易與異動型交易:Oracle/Postgres/SQL Server和一堆其它的。然而,SI並非循序並且許多論文都有討論到怎樣的狀況下SI是循序的或是讓它循序。Cahill et al發布了一個完整且實務的解決方案於2008。他們的技術需要交易檢查讀寫相依。他們實做是使用標準的鎖定管理器且交易需取得鎖定並且在每個讀取或寫入都檢查讀寫相依性。鎖定是非阻塞式並且只用在偵測讀寫相依。他們的方法在主記憶體資料庫系統上是否能被實做得更有效率,到如今仍是一個開放性問題。反覆檢驗讀取和陳述句這類的技術過去已經用過了。
Oracle的TimesTen和IBM的SolidDB這兩個都是商業型主記憶體式關聯式資料庫系統。TimesTen使用單版本鎖定但擁有各種類型的鎖定(例: 共享,互斥,更新)和多種粒度(資料列/資料表/資料庫)。對於主記憶體資料表,solidDB亦使用單版本鎖定與多鎖定類型(例:共享/互斥/更新)並且兩種粒度(資料列/資料表)。以硬碟式資料表來說,solidDB支援樂觀和悲觀兩種同步控制機制。
7. 總結評量
本篇論文我們研究了同步控制機制針對主記憶體資料庫的優化。傳統的鎖定方式讓我們思考基於多版本的解決方案。我們設計並且實做了兩個多版本同步控制方法,其一為樂觀;使用檢驗,另一個則是悲觀;使用鎖定。為了比較我們所提出的方法,我們亦實做了一個針對主記憶體資料庫優化的單版本鎖定機制。我們接著實驗性評估三種方法的效能。某些總結可以由實驗的結果擘劃。
(1) 單版本鎖定可以被實做成更有效率,並且不讓鎖定成為瓶頸。
(2) 單版本鎖定是脆弱的;它只有在交易是短暫並且資源競爭低的狀況才會有好的表現,但是當處於更嚴苛的條件下就不行了。
(3) 多版本同步控制機制有更高的負擔,但是卻有了更多的彈性,即便是在熱點且長唯讀交易下仍有不錯的吞吐量。
(4) 樂觀多版本控制機制比起悲觀有更高的吞吐量。
8. 致謝
我們感謝Phil Bernstein, Marcel van der Holst和Dismitris Tsirogiannis他們的貢獻。這個研究工作的部份是由微軟的Jim Gray系統研究室提供協助。
