王冬慧,朱濤,錢衛(wèi)寧

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

面向高通量事務(wù)處理的事務(wù)編譯技術(shù)

王冬慧,朱濤,錢衛(wèi)寧

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

針對內(nèi)存數(shù)據(jù)庫中CPU利用率不高的問題,目前的研究工作集中在利用事務(wù)編譯技術(shù)提升事務(wù)的執(zhí)行效率和改進事務(wù)的并發(fā)控制以提升數(shù)據(jù)庫的性能.本文主要從以下幾個方面對內(nèi)存數(shù)據(jù)庫的事務(wù)編譯技術(shù)進行了綜述.第一,介紹了事務(wù)處理的一般流程,分析限制系統(tǒng)性能的因素.第二,分析了當前使用的事務(wù)編譯技術(shù),包括即時編譯技術(shù)、操作依賴分析技術(shù)和事務(wù)切片技術(shù).第三,結(jié)合實例分析事務(wù)編譯是如何提升數(shù)據(jù)庫性能的,介紹典型的內(nèi)存數(shù)據(jù)庫在事務(wù)編譯方面的研究工作,如Hekaton、VoltDB等.最后給出了研究展望.

事務(wù)編譯;并發(fā)控制;即時編譯技術(shù);操作依賴分析技術(shù);事務(wù)切片技術(shù)

0 引言

傳統(tǒng)的聯(lián)機事務(wù)處理(OLTP)數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)存放在磁盤中,主要是因為當時的內(nèi)存容量不足以保存所有的OLTP數(shù)據(jù).文獻［1］表明,執(zhí)行一個事務(wù),只有不到10%的指令是用在處理真正有用的工作,而其他90%的指令都用在了日志、并發(fā)控制和緩沖區(qū)管理上.因此,傳統(tǒng)的磁盤數(shù)據(jù)庫性能的主要瓶頸是磁盤的I/O,很多對事務(wù)執(zhí)行和事務(wù)調(diào)度的優(yōu)化都是圍繞這一點展開的.例如,設(shè)計合理的緩沖區(qū)管理策略保證事務(wù)訪問的數(shù)據(jù)已經(jīng)拉取到了內(nèi)存;設(shè)計并發(fā)控制協(xié)議來并發(fā)大量的事務(wù),從而充分利用硬件計算資源.

然而,近年來,隨著計算機技術(shù)特別是半導(dǎo)體技術(shù)的飛速發(fā)展,內(nèi)存的價格不斷下跌,而容量卻不斷上升.1MB內(nèi)存的價格由1980年的1萬美元降低到2010年的0.01美元[2].TB級的主存不再是遙不可及的事了.此外,由于關(guān)系型數(shù)據(jù)庫中數(shù)據(jù)冗余較少,幾乎可以將最大的數(shù)據(jù)庫放進內(nèi)存中[3,20].因此,磁盤I/O已經(jīng)漸漸的不再是數(shù)據(jù)庫系統(tǒng)性能的主要瓶頸,當前數(shù)據(jù)庫系統(tǒng)的性能主要受限于CPU利用率.確保CPU計算資源的高效利用,提升事務(wù)執(zhí)行的局部性才是當前提升數(shù)據(jù)庫系統(tǒng)性能的主要考慮方向.事務(wù)編譯的基本理念在于:將大量原本在執(zhí)行階段完成的任務(wù)提前到編譯階段完成,事務(wù)編譯能夠在此階段充分挖掘事務(wù)邏輯的內(nèi)在特點,并利用這些特點產(chǎn)生更好的執(zhí)行策略,減少事務(wù)執(zhí)行階段的指令開銷,極大地改善系統(tǒng)的性能.

本文后續(xù)內(nèi)容組織如下:第1節(jié)介紹目前事務(wù)處理的一般流程,分析其存在的問題及性能花銷;第2節(jié)討論事務(wù)編譯所用到的技術(shù)及其優(yōu)缺點;第3節(jié)介紹事務(wù)編譯如何改善系統(tǒng)的性能,結(jié)合目前事務(wù)處理以及存在的問題來展開,分析相關(guān)工作是如何優(yōu)化的,并介紹目前一些系統(tǒng)在事務(wù)編譯方面的設(shè)計以及探索,諸如VoltDB,MemSQL,Hekaton等;最后在第4節(jié)總結(jié)全文,給出研究展望.

1 事務(wù)處理流程與分析

磁盤數(shù)據(jù)庫系統(tǒng)事務(wù)處理的主要性能瓶頸是低速的磁盤訪問.然而,內(nèi)存數(shù)據(jù)庫系統(tǒng)天然的避免了這個問題.在新環(huán)境下,系統(tǒng)性能的提升主要依賴于對CPU的利用.這導(dǎo)致了傳統(tǒng)的事務(wù)處理技術(shù)存在許多設(shè)計的局限性.本節(jié)主要從以下兩個方面:(1)事務(wù)邏輯的執(zhí)行; (2)事務(wù)語義的管理探討傳統(tǒng)技術(shù)的設(shè)計及其在新環(huán)境下的不足之處.

1.1 事務(wù)執(zhí)行

傳統(tǒng)數(shù)據(jù)庫,如Oracle、MySQL等,都存在一個SQL解析引擎,將客戶端輸入的SQL命令序列轉(zhuǎn)換成一個可執(zhí)行的操作序列[4].如圖1所示,主要包括以下3個步驟:(1)詞法語法分析.(2)生成邏輯查詢.(3)生成物理查詢.

圖1 SQL引擎間的調(diào)用關(guān)系Fig.1Call relationship between SQL engine

主流數(shù)據(jù)庫通常采用迭代器模型封裝SQL的執(zhí)行邏輯,或者稱為Volcano模型[5].數(shù)據(jù)庫系統(tǒng)內(nèi)部實現(xiàn)了大量的物理操作符,對應(yīng)不同的執(zhí)行邏輯.查詢引擎通過組合不同的物理操作符以實現(xiàn)復(fù)雜的查詢邏輯.每一個物理操作符有3個方法,這3個方法允許物理操作符結(jié)果的使用者一次一個元組的得到這個結(jié)果,實現(xiàn)了流水化操作.這3個方法為:open().該方法分配并初始化物理操作符中所用到的各種數(shù)據(jù)結(jié)構(gòu)等;getnext().該方法返回結(jié)果中的下一個元組,通過反復(fù)調(diào)用該函數(shù)以獲取全部的元組;close().該方法釋放執(zhí)行當前操作符申請的所有資源.

迭代模型的優(yōu)點是,接口非常簡單,通過組合任意的物理操作符可以表達復(fù)雜的執(zhí)行邏輯.元組根據(jù)需求在操作符之間傳遞,減少了數(shù)據(jù)物化要求.這種流水化操作節(jié)省了磁盤的I/O.

然而,在內(nèi)存數(shù)據(jù)庫下,迭代模型存在著以下問題,第一,較高的維護開銷.在OLTP應(yīng)用中,實際用于數(shù)據(jù)訪問的指令開銷只占很小的一個部分,大量的計算周期耗費在了資源的分配和釋放上.第二,高昂的表達式計算.查詢執(zhí)行過程中,需要頻繁地進行表達式計算,產(chǎn)生了大量的指令開銷.第三,較高的指令緩存缺失.在執(zhí)行過程中,迭代器需要頻繁地在多個物理操作的接口函數(shù)間跳轉(zhuǎn),這會導(dǎo)致CPU的指令緩存頻繁缺失.指令緩存的缺失會阻塞CPU的執(zhí)行,從而降低每周期執(zhí)行的指令數(shù)量.總體而言,采用迭代器描述查詢計劃一方面增大了完成每次操作需要的指令數(shù)量,另一方面降低了CPU每周期執(zhí)行的指令數(shù)量.

1.2 事務(wù)管理

并發(fā)控制協(xié)議是在事務(wù)執(zhí)行過程中調(diào)度不同事務(wù)的沖突訪問,使得多個事務(wù)按照合理的順序操作數(shù)據(jù)庫.然而,磁盤式數(shù)據(jù)庫對并發(fā)控制策略的實現(xiàn)都具有較高的維護代價.在事務(wù)處理過程中,并發(fā)請求的調(diào)度產(chǎn)生了較多的指令開銷.

經(jīng)典兩階段鎖(two-phase locking,2PL)[4]的實現(xiàn)是采用集中式鎖表.在加鎖階段,所有的事務(wù)在鎖表上申請對應(yīng)的數(shù)據(jù)鎖.在解鎖階段,事務(wù)釋放數(shù)據(jù)鎖,并從等待隊列中喚醒被阻塞的請求.此外,兩階段鎖可能導(dǎo)致死鎖的發(fā)生,系統(tǒng)需要設(shè)計死鎖檢測策略.集中式的鎖表并不適用于內(nèi)存數(shù)據(jù)庫.一方面,加鎖、解鎖以及死鎖檢測都產(chǎn)生了大量的CPU指令.另一方面,集中式鎖表存在限制多核性能的問題[20].當多個執(zhí)行線程共同訪問鎖表時,共享對象需要使用臨界區(qū)來同步多核的并發(fā)訪問,隨著物理核心的不斷增加,對共享對象的并發(fā)訪問沖突將持續(xù)增加.

在多版本并發(fā)控制技術(shù)[4]中,調(diào)度器為每個數(shù)據(jù)項的寫操作創(chuàng)建一個時間戳作為該數(shù)據(jù)項的一個版本,當發(fā)出讀該數(shù)據(jù)項的請求時,調(diào)度度選擇一個版本進行讀取.多版本需要保證數(shù)據(jù)項版本的選擇能夠使得事務(wù)可串行化.然而,在并發(fā)事務(wù)頻繁訪問某一元素時,所產(chǎn)生的沖突就會較高,系統(tǒng)會因此而出現(xiàn)頻繁的回滾操作,導(dǎo)致產(chǎn)生更多的延遲和更多的指令操作,此外,維護多個版本同樣會產(chǎn)生大量的指令開銷.

有效性確認是一種樂觀的并發(fā)控制技術(shù)[4].該技術(shù)在事務(wù)完成所有的執(zhí)行邏輯后,驗證所有的讀取內(nèi)容是否發(fā)生了更新.若驗證通過,則事務(wù)會原子性的寫入所有的待提交數(shù)據(jù);若失敗,事務(wù)需要被重試.當處理沖突較少的負載是,樂觀并發(fā)控制策略具有非常好的性能,維護開銷極低.然而,當事務(wù)間頻繁發(fā)生沖突時,大量的CPU時間將耗費在事務(wù)的重試上,沖突處理的開銷將大大增高.當前的許多內(nèi)存數(shù)據(jù)庫都采用了改進的有效性確認,這是因為事務(wù)在內(nèi)存數(shù)據(jù)庫下執(zhí)行速度得到了大大的提升,事務(wù)與事務(wù)之間的發(fā)生沖突的頻率也隨著下降.因此可以采用更加樂觀的策略.

基于時間戳的并發(fā)控制技術(shù)[4]在事務(wù)開始時為其分配一個全局遞增的時間戳.此外,數(shù)據(jù)記錄需要維護一個讀取時間戳和寫入時間戳,保存最近一次讀寫該記錄的事務(wù).在事務(wù)執(zhí)行過程中,通過判斷事務(wù)的時間戳和被訪問記錄的最近讀寫時間戳來判定是否發(fā)生訪問沖突.當發(fā)生訪問沖突時,事務(wù)需要回滾并申請一個更新的時間戳重新執(zhí)行.然而,該策略的維護代價較高.由于數(shù)據(jù)記錄需要維護最后一次讀取時間,每個讀操作都會造成數(shù)據(jù)頁面的修改,帶來了更高的維護代價.此外,當負載中存在較多的訪問沖突時,該策略會頻繁重試事務(wù),造成較高的調(diào)度代價.

確定性執(zhí)行[5]是一種服務(wù)于內(nèi)存數(shù)據(jù)庫的調(diào)度策略.由于磁盤I/O不是內(nèi)存數(shù)據(jù)庫的瓶頸,因此系統(tǒng)不需要通過并發(fā)執(zhí)行多個事務(wù)來提升CPU的利用率.內(nèi)存數(shù)據(jù)庫可以在事務(wù)執(zhí)行前確定調(diào)度策略,并在單線程上串行執(zhí)行每個請求.該策略能夠大大的避免系統(tǒng)在并發(fā)控制上耗費的計算資源.在新型的內(nèi)存數(shù)據(jù)庫VoltDB[12,18],Hyper[22]等中得到了應(yīng)用.然而,該策略需要集中式的確定事務(wù)的調(diào)度次序,并且需要通過數(shù)據(jù)分區(qū)的方式提升多核并行能力.前者會導(dǎo)致調(diào)度瓶頸.后者會引入分布式事務(wù),由此導(dǎo)致的多核間協(xié)調(diào)會降低CPU的利用率.

主流磁盤數(shù)據(jù)庫(Orcale,MySQL,PostgreSQL)都采用了多版本并發(fā)控制和兩階段鎖混合的策略.多版本隔離了只讀事務(wù)與讀寫事務(wù)之間的沖突,兩階段鎖確保了讀寫事務(wù)間的正確調(diào)度順序.然而,這種并發(fā)控制策略產(chǎn)生了大量的計算CPU開銷.內(nèi)存數(shù)據(jù)庫(Hekaton等)主要采用了樂觀并發(fā)控制策略與多版本相結(jié)合的管理方式,這主要是得益于樂觀并發(fā)控制具有更好的多核擴展性以及較小的指令開銷.

2 事務(wù)編譯技術(shù)

2.1 即時編譯技術(shù)

即時編譯技術(shù)(Just-in-time Compilation,JIT)[6]是一種將中間語言轉(zhuǎn)換成機器碼的技術(shù).JIT的具體做法是,當載入一個新類型時,公共語言運行庫為該類型分配一個內(nèi)部數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的函數(shù),當該函數(shù)被第一次調(diào)用時,JIT將其翻譯成機器語言,當再次調(diào)用這個函數(shù)時,則直接從緩存中獲取已編譯好的機器語言.

目前很多的研究工作[7-9]都用到了這一技術(shù),相比于解釋執(zhí)行SQL請求,JIT轉(zhuǎn)換成機器碼的方式能夠智能地對代碼進行優(yōu)化與重復(fù)利用.對于多次調(diào)用的函數(shù),JIT會通過查表或者緩存的策略來取代重復(fù)計算,減少指令集大小,加快運行效率.

2.2 操作依賴分析技術(shù)

操作依賴(Dependence Theory)是指數(shù)據(jù)庫事務(wù)操作之間存在依賴關(guān)系,這種關(guān)系可能是由于操作間的時序性,或者數(shù)據(jù)庫表間的參照完整度造成的.正是由于這些依賴關(guān)系的存在,使得一些操作之間難以并行.操作片段可以通過這些依賴關(guān)系來構(gòu)成拓撲序關(guān)系.兩個操作可以并行當且僅當這兩個操作都不存在拓撲序在他們之前且未執(zhí)行的操作.操作依賴分析操作之間的依賴關(guān)系,給出較好的運算順序,從而增大并行率,提高效率.

文獻［10］提出了這樣的操作依賴分析算法:首先將所有的操作按時間排序,p1, p2,···,pn,接著將所有的操作做笛卡爾積,得到序列(p1,p2),(p1,p3),···,(pn-1,pn),并分析每兩個操作之間的依賴關(guān)系,如存在依賴,則在兩操作之間建立一條有向邊,表示該操作依賴于另一個操作,由此建立為一個有向無環(huán)圖.接著遍歷該圖,所有不依賴其他任何操作的點為第代點,如果存在依賴關(guān)系,則該點的代數(shù)為它所依賴的點的最大代數(shù)+1.最后,可以發(fā)現(xiàn),相同代數(shù)的操作點之間不存在依賴關(guān)系,是可以并發(fā)執(zhí)行的.如圖2所示,每個節(jié)點代表一個事務(wù),結(jié)點上的數(shù)字代表該事務(wù)的代數(shù).

解釋執(zhí)行時事務(wù)間若發(fā)生沖突,事務(wù)將被阻塞.操作依賴分析能夠在事務(wù)預(yù)編譯階段挖掘出事務(wù)間的依賴關(guān)系,從而將相互沖突的事務(wù)放在不同的時間片執(zhí)行,減小了事務(wù)因阻塞而等待的時間.然而,在靜態(tài)分析兩個操作之間是否存在沖突時,操作依賴分析算法通常根據(jù)其訪問的是否是同一個表來判斷,而不能具體的分析出操作確切的訪問的是哪些數(shù)據(jù)行,因此,原本可以并行的事務(wù)可能被分析為有沖突關(guān)系,事務(wù)的并行性降低.

圖2 操作依賴分析算法Fig.2Operation dependency analysis algorithm

Calvin[15]在執(zhí)行前分析事務(wù)的讀寫操作集合確定多個事務(wù)之間的是否存在沖突,相互沖突的事務(wù)按照時間順序被放在不同的時間點執(zhí)行,不存在沖突關(guān)系的事務(wù)可以多核并行執(zhí)行,從而在保證事務(wù)可串行化的同時減少了事務(wù)調(diào)度的代價.

2.3 事務(wù)分片技術(shù)

事務(wù)分片技術(shù)(Transaction Chopping)[11]是指,系統(tǒng)將事務(wù)切割成一些片段來并發(fā)執(zhí)行,以期獲得更好的性能.事務(wù)分片技術(shù)基于如果分片之后的事務(wù)片段是可串行化的,那么事務(wù)集也是可串行化的的性質(zhì).該方法確保了用戶在事務(wù)執(zhí)行正確性的前提下獲得更高的事務(wù)并行度.如何找到事務(wù)的最優(yōu)分片,是事務(wù)分片技術(shù)最核心的問題.

1.1 對象 2009年6月，選擇上海地區(qū)5個街道60歲以上2型糖尿病患者73例，其中男30例，女43例，平均年齡69.5歲。文化程度:小學(xué)及以下14例，初中14例，高中25例，大專及以上20例。病程5年以上，血糖波動較大的患者。診斷依據(jù)，按世界衛(wèi)生組織制定的糖尿病診斷標準由上海市、區(qū)級醫(yī)院確認的病例。

一個典型的事務(wù)分片算法,將事務(wù)分片后構(gòu)造一個圖,稱為SC圖,圖的頂點為事務(wù)的一個片,邊分為兩種,一種是S邊,表示連接的兩個片屬于同一個事務(wù),一種是C邊,表示連接的兩個片之間存在沖突,如修改同一個數(shù)據(jù),且這兩個片不屬于同一個事務(wù).定義SC環(huán)為包含至少一條S邊和一條C邊的簡單環(huán).如果事務(wù)的SC圖中包含SC環(huán),則該事務(wù)是不可串行化的.下面是一種尋找最優(yōu)分片的算法,對于每個事務(wù),首先將其按照存取操作劃分為多個片,接著對于該事務(wù)的每個片尋找其它與其有沖突的事務(wù),將其連C邊,接著尋找C邊連通圖,將存在同一個連通圖中的片合并為一個片,因為將它們切割會產(chǎn)生SC環(huán).尋找完最優(yōu)分片后將會產(chǎn)生一個無SC環(huán)的圖,無沖突的片之間可以并行執(zhí)行.如圖3所示,將事務(wù)T5按照存取操作分為(a),(b),(c),(d),(e),(f)6個片,接著尋找與其他4個事務(wù)的沖突關(guān)系,可以看出(b),(d),(f)3個片在同一個連通圖中,應(yīng)合并為一個片.

圖3 事務(wù)分片算法Fig.3Transaction chopping algorithm

事務(wù)分片技術(shù)通常與操作依賴分析相結(jié)合.如何確定更優(yōu)的執(zhí)行順序,提升事務(wù)的并行性是一個重要的課題.此外,限制分片執(zhí)行順序還存在很多因素,如分片執(zhí)行的時間等.

3 事務(wù)編譯

3.1 編譯對事務(wù)執(zhí)行的影響

事務(wù)邏輯執(zhí)行的主要問題在于物理查詢計劃的表示以及解釋執(zhí)行的方式產(chǎn)生了巨大的指令操作,CPU開銷較大.而事務(wù)編譯能夠挖掘事務(wù)邏輯的內(nèi)在特點,改善物理計劃的表示以及執(zhí)行方式,從而提升事務(wù)邏輯執(zhí)行的效率.

文獻［7-8］主要介紹了SQL Server的事務(wù)處理數(shù)據(jù)庫引擎Hekaton是如何編譯事務(wù)的. Hekaton將表分為內(nèi)存優(yōu)化表和基于磁盤的表,其中內(nèi)存優(yōu)化表放在內(nèi)存中,將存儲過程分為本地編譯存儲過程和解析性存儲過程,其中本地編譯存儲過程是將存儲過程轉(zhuǎn)換為機器碼,通過執(zhí)行本地編譯存儲過程提升事務(wù)執(zhí)行的性能.轉(zhuǎn)換成機器碼的過程是:首先使用SQL Server內(nèi)部翻譯機制將原始SQL指令序列轉(zhuǎn)換為MAT(mixed abstract tree);接著由于T-SQL和C語義的差異,將MAT轉(zhuǎn)換為PIT(pure imperative tree);接著生成C語言代碼.由于迭代模型自上而下通過調(diào)用getnext接口獲取子節(jié)點的輸入元組,調(diào)用函數(shù)的方式使得代碼失去了很好的本地性,產(chǎn)生巨大的指令集.因此,Hekaton大量使用label和goto語句,將其放在一個方法中替代調(diào)用函數(shù)接口的方式;接著使用編譯器將C語言轉(zhuǎn)換成機器碼.實驗證明,使用本地編譯存儲過程并且訪問內(nèi)存優(yōu)化表執(zhí)行的指令條數(shù)減少了94%.

Hekaton減少了迭代模型由于頻繁調(diào)用接口而產(chǎn)生的指令花銷,然而,以迭代器為中心的模型即使使用goto語句,執(zhí)行的方式仍然是自上而下的方式,指令緩存缺失嚴重的問題仍然存在[7,9,21].Thomas Neumann[9]提出了一種高效的查詢計劃編譯方式.該方法的主要策略有以下3點:

(1)事務(wù)處理以數(shù)據(jù)為中心而不是以迭代器為中心.處理的數(shù)據(jù)盡可能的存放在CPU寄存器中,使得訪問數(shù)據(jù)較快.

(3)使用LLVM編譯框架將事務(wù)編譯成機器碼,極大地減少了指令集大小.

此外,Thomas Neumann在該論文中還提出了一些優(yōu)化技術(shù),例如,減少分支預(yù)測對指令執(zhí)行的影響;使用SIMD指令集,指令部件同時訪問內(nèi)存,一次性獲得所有需要的數(shù)據(jù)集,減少訪問數(shù)據(jù)的指令開銷.論文的實驗基于HyPer內(nèi)存數(shù)據(jù)庫,使用LLVM編譯器將C++代碼轉(zhuǎn)換成機器碼,實驗顯示,以數(shù)據(jù)為中心的查詢處理是一種非常有效的查詢執(zhí)行模型, DBMS可以獲得更高的效率.

事務(wù)編譯同樣對分布式數(shù)據(jù)庫系統(tǒng)事務(wù)執(zhí)行有著重要的意義.分布式數(shù)據(jù)庫的事務(wù)處理能力通常受限于跨節(jié)點的事務(wù)執(zhí)行和事務(wù)提交.前者在執(zhí)行階段需要節(jié)點間頻繁的交換中間結(jié)果,后者在提交階段需要在節(jié)點間進行兩階段提交.事務(wù)編譯能夠在編譯階段分析不同操作之間的聯(lián)系,產(chǎn)生更優(yōu)的執(zhí)行計劃.在Oceanbase上執(zhí)行事務(wù),Mergeserver需要頻繁的與Updateserver以及Chunkserver進行網(wǎng)絡(luò)交互.這些交互一方面大大增加了事務(wù)的延遲;另一方面也破壞了任務(wù)在多個節(jié)點上的連續(xù)執(zhí)行,導(dǎo)致了更高的指令開銷.在事務(wù)編譯階段,根據(jù)事務(wù)中每個操作網(wǎng)絡(luò)節(jié)點交互的特點,利用數(shù)據(jù)緩存,RPC合并以及即時編譯等技術(shù)大大縮減了事務(wù)延遲和執(zhí)行的指令開銷.

3.2 編譯對事務(wù)管理的影響

事務(wù)管理主要利用并發(fā)控制技術(shù).主流并發(fā)控制技術(shù)主要依賴于運行時收集到的信息來隔離多個請求的沖突訪問.實際上,給定事務(wù)邏輯,在編譯階段就可以挖掘事務(wù)訪問的數(shù)據(jù)區(qū)域、操作與操作之間沖突的可能性以及依賴關(guān)系等,利用這些信息可以改善事務(wù)調(diào)度的設(shè)計,主要有分片并發(fā)控制,分片并發(fā)控制主要包括兩種:①數(shù)據(jù)分片,每個數(shù)據(jù)分片單線程調(diào)用;②事務(wù)分片,通過將事務(wù)分片,并行執(zhí)行分片.

3.2.1 數(shù)據(jù)分片

VoltDB/H-store[13-14]為了充分利用了大內(nèi)存和多核CPU優(yōu)勢,提出了采用單線程式的執(zhí)行引擎依次調(diào)度隊列中的事務(wù)請求.此外,系統(tǒng)將數(shù)據(jù)分片到多個執(zhí)行引擎實例上,以提升并行處理能力.單線程式的設(shè)計大大簡化了事務(wù)管理的工作.基于以上設(shè)計,在事務(wù)編譯階段,系統(tǒng)通過分析分區(qū)模式以及事務(wù)的執(zhí)行邏輯,確定各個請求需要訪問的分區(qū)集合, VoltDB根據(jù)事務(wù)是否需要訪問多個分區(qū)上的數(shù)據(jù),多個分區(qū)之間是否需要協(xié)調(diào),將事務(wù)分為Single-Sited,One-Shot或者General 3種類型.在運行時,調(diào)度器根據(jù)事務(wù)類型請求路由到正確的分區(qū)上執(zhí)行,針對不同類型的事務(wù)采用了特定的執(zhí)行策略,減少事務(wù)執(zhí)行過程中多個分區(qū)的交互.單線程式的事務(wù)調(diào)度徹底規(guī)避了在線式的并發(fā)控制技術(shù),大大減少了并發(fā)控制引入的指令開銷.

DORA[17]是一個面向數(shù)據(jù)的事務(wù)處理引擎.一些系統(tǒng)是將一個線程和一個事務(wù)耦合,這樣的做法會因為事務(wù)頻繁地訪問數(shù)據(jù)而造成沖突,導(dǎo)致數(shù)據(jù)頻繁地被上鎖和解鎖,從而浪費了大量的時間在鎖管理上,多核的優(yōu)勢在這個地方產(chǎn)生了瓶頸.而DORA是將一個線程與不相交的數(shù)據(jù)庫子集耦合,一個線程通常只訪問一個數(shù)據(jù)集,避免了鎖的開銷.為了將每個事務(wù)的工作分發(fā)給合適的執(zhí)行線程,DORA在事務(wù)編譯階段將事務(wù)解釋為事務(wù)流圖,事務(wù)流圖是指對數(shù)據(jù)集的操作圖,一個操作是事務(wù)的一段代碼,操作的標識符代表了這個操作訪問的數(shù)據(jù)區(qū)域.接著DORA根據(jù)操作的標識符找到相應(yīng)的線程,將操作發(fā)放給該線程.不同的操作之間可能存在依賴,DORA的解決方法是在相互依賴的操作中加入一個共享對象RVP, RVP將相互依賴的操作放在不同的階段執(zhí)行,從而協(xié)調(diào)事務(wù)的分布式運行.DORA面向數(shù)據(jù)的設(shè)計方式減少了管理鎖所耗費的性能,能夠充分利用多核處理器的優(yōu)勢.

3.2.2 事務(wù)分片

Wang[16]等人提出了并發(fā)控制技術(shù)IC3來對事務(wù)并行進行管理,由于相互沖突的事務(wù)必須等待其中一個事務(wù)完成,另一個事務(wù)才能開始,這樣的方式會導(dǎo)致較長時間的阻塞,因此, IC3通過事務(wù)分片的方式,將事務(wù)切割為很多片段,通過靜態(tài)分析不同分片間的依賴關(guān)系,使得被依賴片段執(zhí)行完成后,另一個事務(wù)的部分片段就可以開始執(zhí)行,而不必等到被依賴片段所在的事務(wù)全部執(zhí)行完.從而提高了事務(wù)處理的并行度.

3.3 事務(wù)編譯在不同系統(tǒng)中的實踐

目前有很多數(shù)據(jù)庫利用事務(wù)編譯提升了事務(wù)處理和事務(wù)調(diào)度的性能,表1是其中一些系統(tǒng)利用不同的編譯技術(shù)、事務(wù)執(zhí)行和管理優(yōu)化方法達到的優(yōu)化目標.

表1 事務(wù)編譯在不同系統(tǒng)中的實踐Tab.1Application of transaction compilation in different systems

4 總結(jié)

傳統(tǒng)的磁盤數(shù)據(jù)庫因為大量讀寫磁盤而產(chǎn)生了巨大的性能消耗,而內(nèi)存數(shù)據(jù)庫避免了這一問題,其事務(wù)執(zhí)行主要的性能瓶頸在于CPU利用率.本文主要分析了傳統(tǒng)事務(wù)執(zhí)行方式和事務(wù)管理在內(nèi)存數(shù)據(jù)庫中的性能花銷,介紹主流優(yōu)化系統(tǒng)如何利用事務(wù)編譯技術(shù)改進事務(wù)執(zhí)行和事務(wù)調(diào)度.

事務(wù)編譯的主要優(yōu)勢在于:①更少的指令數(shù)量和更高的指令緩存命中率.相對于解釋執(zhí)行,編譯執(zhí)行可以在編譯階段完成大量的工作,并產(chǎn)生更加緊致的執(zhí)行代碼.②更優(yōu)的事務(wù)調(diào)度計劃.通過分析事務(wù)的執(zhí)行邏輯,系統(tǒng)可以在編譯階段確定部分事務(wù)請求之間的調(diào)度策略,從而產(chǎn)生更優(yōu)的調(diào)度計劃,并減輕在線調(diào)度的壓力.然而,事務(wù)編譯同樣存在以下局限性:①編譯需要更高的計算代價.這導(dǎo)致了編譯通常需要離線完成.②編譯缺少靈活性.產(chǎn)生的執(zhí)行計劃不能進行微調(diào),單個操作的修改需要整體重新編譯.③編譯結(jié)果占據(jù)更多的存儲空間.當事務(wù)類型過多時,編譯產(chǎn)生的執(zhí)行計劃將會占據(jù)大量的存儲空間.

針對事務(wù)編譯,未來的研究趨勢主要包括以下方面:①數(shù)據(jù)庫特征感知的編譯技術(shù).當前的編譯圍繞在利用JIT將源碼轉(zhuǎn)換為機器碼.然而,數(shù)據(jù)庫的一些負載特征同樣會影響執(zhí)行計劃的運行效果.我們可以引入這些信息來改進編譯結(jié)果.②高效的編譯技術(shù).當前的編譯需要較高的計算代價,因此是離線完成.然而,當源碼或者數(shù)據(jù)庫Schema發(fā)生變化后,執(zhí)行計劃需要完全重新編譯.當系統(tǒng)部署的應(yīng)用較多時,重新編譯將產(chǎn)生很大的計算代價.因此需要考慮更加高效的編譯方式.

［1］AILAMAKI A G,DEWITT D J,HILL M D,et al.DBMSs on a modern processor:Where does time go?[C]//Proceedings of International Conference on Very Large Data Bases.UK:VLDB.1999:266-277.

［2］哈索,亞歷山大·蔡爾.內(nèi)存數(shù)據(jù)庫管理[M].SAP,譯.北京:清華大學(xué)出版社,2013.

［3］BERNSTEIN P,BRODIE M,CERI S,et al.The asilomar report on database research[J].Acm Sigmod Record, 1998,27(4):44-113.

［4］GARCIA-MOLINA H,ULLMAN J D,WIDOM J.Database System Implementation[M].USA:Prentice Hall, 2010,132-179.

［5］ALEXANDER T,DANIEL I A.The Case for Determimism in Database Systems[J].VLDB,2010:70-80.

［6］WIKIPEDIA.Just-in-time manufacturing[EB/OL].[2016-06-01].https://en.wikipedia.org/wiki/Just-in-time manufacturing.

［7］DIACONU C,FREEDMAN C,ISMERT E,et al.Hekaton:SQL server’s memory-optimized OLTP engine[J]. SIGMOD,2013:1-13.

［8］DIACONU C,ISMERT E,LARSON P A,et al.Compilation in the microsoft SQL server hekaton engine[J]. IEEE,2014:22-32.

［9］NEUMANN T.Efficiently compiling efficient query plans for modern hardware[J].PVLDB,2011,4(9):539-550.

［10］吳亞鑫,孫靜.基于數(shù)據(jù)庫操作的相關(guān)性模型及應(yīng)用[J].計算機工程與設(shè)計,2011,32(1):183-187.

［11］SHASHA D,LLIRBAT F,SIMON E,et al.Transaction chopping:Algorithms and performance studies[J].ACM Transactions on Database Systems(TODS),1995,20(3):325-363.

［12］TU S,ZHENG W T,KOHLER E,et al.Speedy transactions in multicore in-memory databases[J].Twentyfourth ACM Symposium on Operating Systems Principles,2013:18-34.

［13］STONEBRAKER M,WEISBERG A.The VoltDB main memory DBMS[J].IEEE DEBull,2013,36(2):21-27.

［14］KALLMAN R,KIMURA H,NATKINS J,et al.H-store:A high-performance,distributed main memory transaction processing system[J].PVLDB,2008,1(2):1496-1499.

［15］THOMSON A,DIAMOND T,WENG S C,et al.Calvin:Fast distributed transactions for partitioned database systems[C]//ACM SIGMOD International Conference on Management of Data.2012:1-12.

［16］WANG Z G,MU S,CUI Y,et al.Scaling multicore databases via constrained parallel execution[C]//?ICAN F,KOVTRIKE G,MADDEN S.SIGMOD Conference.New York:ACM,2016:1643-1658.［17］PANDIS I,JOHNSON R,HARDAVELLAS N,et al.Data-oriented transaction execution[J].PVLDB,2010,3(1): 928-939.

［18］In-Memory Operational Database,SQL and Scale-Out.VoltDB[EB/OL].[2016-06-03].http://voltdb.com.

［19］Introduction to MemSQL.MemSQL[EB/OL].[2016-06-03].http://www.dbms2.com/2012/06/18/introductionto-memsql/

［20］STONEBRAKER M,MADDEN S,ABADI D J,et al.The end of an architectural era it’s time for a completerewrite[J].VLDB,2007:1150-1160.

［21］HELLERSTEIN J M,STONEBRAKER M,HAMILTON J.Architecture of a database system[J].Foundations and Trends Databases,2007,1(2):141-259.

［22］KEMPER A,NEUMANN T.HyPer:A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots[J].ICDE,2011:195-206.

(責任編輯:張晶)

Compilation techniques for high throughput transaction processing

WANG Dong-hui,ZHU Tao,QIAN Wei-ning
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

Because of the problem of low utilization of CPU in memory database,the present research work is focused on improving the execution efficiency and concurrency control by transaction compilation technology to improve the performance of database. This article mainly introduces the following aspects of the memory database transaction compilation technology.First,this paper introduces the general process of transaction processing and analyzes the factors that limit the performance of the system.Second, we analyze the compilation techniques,including Just-in-time Compilation,Dependence Theory and Transaction Chopping.Third,we analyze the database and show how to improve the performance combined with the introduction of typical memory database,such as VoltDB,Hekaton and so on.Finally,the research prospects are given.

transaction compilation;concurrency control;just-in-time compilation; dependence theory;transaction chopping

TP391

A

10.3969/j.issn.1000-5641.2016.05.002

1000-5641(2016)05-0010-08

2016-05

國家863計劃項目(2015AA015307);國家自然科學(xué)基金(61432006)

王冬慧,女,博士研究生,研究方向為分布式數(shù)據(jù)庫.E-mail:zjnuwangdonghui@163.com.

錢衛(wèi)寧,男,教授,研究方向為可擴展事務(wù)處理和海量數(shù)據(jù)分析與挖掘. E-mail:wnqian@sei.ecnu.edu.cn.