胡爽,周歡,錢衛(wèi)寧

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

內(nèi)存數(shù)據(jù)庫事務(wù)提交的關(guān)鍵技術(shù)與挑戰(zhàn)

胡爽,周歡,錢衛(wèi)寧

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

ARIES作為傳統(tǒng)事務(wù)提交機(jī)制從20世紀(jì)90年代問世以來,一直是主流商業(yè)或開源數(shù)據(jù)庫系統(tǒng)普遍采用的方法.隨著應(yīng)用的高通量化,基于傳統(tǒng)硬件設(shè)備實(shí)現(xiàn)的事務(wù)提交機(jī)制成為了系統(tǒng)性能提升的首要瓶頸.然而大內(nèi)存、多核等高性能硬件技術(shù)的發(fā)展又為事務(wù)提交機(jī)制的優(yōu)化提供了新的契機(jī).本文詳細(xì)分析并總結(jié)了傳統(tǒng)事務(wù)提交機(jī)制中存在的問題,然后歸納并討論了現(xiàn)有基于新型硬件的事務(wù)提交技術(shù)的應(yīng)用現(xiàn)狀與優(yōu)缺點(diǎn),最后探討了事務(wù)提交優(yōu)化的未來發(fā)展與挑戰(zhàn).

內(nèi)存數(shù)據(jù)庫;事務(wù)提交;日志處理技術(shù)

0 引言

內(nèi)存數(shù)據(jù)庫是以內(nèi)存為主要存儲介質(zhì)的數(shù)據(jù)庫系統(tǒng),由于內(nèi)存讀寫速度非?？旌捅荛_了磁盤I/O操作,相對于傳統(tǒng)磁盤數(shù)據(jù)庫來說,其具有高吞吐量和低延遲的顯著優(yōu)勢[1].雖然內(nèi)存發(fā)展迅速,但容量遠(yuǎn)不及磁盤而不足以支持整個數(shù)據(jù)庫.所以,目前多數(shù)內(nèi)存數(shù)據(jù)庫系統(tǒng)是混合存儲介質(zhì)的,除了內(nèi)存它還需要磁盤存儲,讓部分?jǐn)?shù)據(jù)存在磁盤.另外,聯(lián)機(jī)事務(wù)處理(On-Line Transaction Processing,OLTP)是數(shù)據(jù)庫系統(tǒng)的重要內(nèi)容之一,在金融、互聯(lián)網(wǎng)、電信等領(lǐng)域應(yīng)用廣泛,也是當(dāng)前學(xué)術(shù)研究的熱門方向.針對這種新型的事務(wù)型內(nèi)存數(shù)據(jù)庫系統(tǒng)來說,在傳統(tǒng)單機(jī)環(huán)境下,內(nèi)存的讀寫訪問速度與磁盤相差太多,導(dǎo)致涉及磁盤I/O的日志結(jié)構(gòu)成為瓶頸.而在分布式的多機(jī)環(huán)境下多臺機(jī)器并發(fā)執(zhí)行事務(wù),日志仍然是集中式的結(jié)構(gòu),高并發(fā)的負(fù)載使其必然成為系統(tǒng)瓶頸.

日志是支持系統(tǒng)容災(zāi)恢復(fù)的基礎(chǔ)技術(shù)[2],也是內(nèi)存數(shù)據(jù)庫系統(tǒng)的一個重要結(jié)構(gòu),它和數(shù)據(jù)是緊密聯(lián)系的兩個部分.日志記錄于非易失性存儲器(磁盤等)上,以一種穩(wěn)定的方式記錄數(shù)據(jù)庫變更的歷史,不會因故障(如系統(tǒng)斷電,關(guān)機(jī)等)而丟失,以保證系統(tǒng)在重新啟動后進(jìn)行及時恢復(fù).事實(shí)上,日志不僅僅涉及I/O,它涉及事務(wù)提交的整個流程,與緩沖區(qū)管理,鎖管理等模塊緊密聯(lián)系.日志緩沖區(qū)沖突以及日志引發(fā)的鎖競爭等問題越來越嚴(yán)重,導(dǎo)致事務(wù)提交性能跟不上事務(wù)的執(zhí)行速度,從而使事務(wù)提交成為系統(tǒng)的性能瓶頸.

作為數(shù)據(jù)庫系統(tǒng)的一個核心服務(wù),事務(wù)提交是數(shù)據(jù)庫系統(tǒng)的研究熱點(diǎn).隨著計(jì)算機(jī)硬件的飛速發(fā)展,數(shù)據(jù)庫系統(tǒng)開始面向大容量內(nèi)存、多核處理器和高速網(wǎng)絡(luò)等,并試圖通過這些硬件基礎(chǔ)來提高事務(wù)提交性能.近幾年來,陸續(xù)有研究利用多核特性,充分協(xié)調(diào)每個核的調(diào)度請求以提高系統(tǒng)的并行度.在傳統(tǒng)成組提交[3]的基礎(chǔ)上,已有一系列優(yōu)化技術(shù)解決了不同瓶頸來提升事務(wù)提交的性能.新型存儲介質(zhì)的出現(xiàn)與快速發(fā)展,非易失內(nèi)存(Non-Volatile Memory,NVM)[4]以其數(shù)據(jù)的非易失性和高效的訪問性能,成為日志存儲介質(zhì)的不二選擇.現(xiàn)基于NVM日志存儲的事務(wù)提交機(jī)制的研究處于探索和原型階段[5-6].另外,利用快速讀寫、質(zhì)量輕以及能耗低特點(diǎn)的閃存(Flash)等固態(tài)存儲和高速網(wǎng)絡(luò)(High-Speed Data Center Networks),一些高性能日志服務(wù)系統(tǒng)相繼問世[7-9].

傳統(tǒng)數(shù)據(jù)庫系統(tǒng)事務(wù)執(zhí)行流程需要記錄兩方面的內(nèi)容,包括修改數(shù)據(jù)和日志.事務(wù)的數(shù)據(jù)操作在內(nèi)存中進(jìn)行,而操作被記錄在全局的日志結(jié)構(gòu).為了緩沖從內(nèi)存到磁盤的讀寫性能差異,日志先互斥地寫到集中式緩沖區(qū),并產(chǎn)生全局唯一的日志序列號LSN(Log Sequence Number),以保證日志有序性.當(dāng)有事務(wù)提交,緩沖區(qū)日志根據(jù)LSN被寫到磁盤,并在刷盤成功后響應(yīng)客戶端.其中,事務(wù)在數(shù)據(jù)操作時獲得的鎖會保留到日志刷盤成功后才釋放.圖1表示的是事務(wù)提交流程:①階段事務(wù)寫緩沖區(qū);②階段緩沖區(qū)日志刷磁盤;③階段釋放鎖并響應(yīng)客戶端.其中,前兩個階段頻繁涉及緩沖區(qū)管理、鎖管理以及磁盤I/O等,是主要產(chǎn)生瓶頸的階段.目前事務(wù)提交技術(shù)主要是對這兩個階段涉及的結(jié)構(gòu)和硬件存儲進(jìn)行優(yōu)化.

圖1 事務(wù)提交的流程Fig.1Process of transaction commit

本文主要從三個部分展開論述.第一部分針對目前新型內(nèi)存數(shù)據(jù)庫系統(tǒng)高并發(fā)的負(fù)載特點(diǎn),分析傳統(tǒng)事務(wù)提交機(jī)制存在的瓶頸;第二部分對利用不同硬件特性優(yōu)化的事務(wù)提交關(guān)鍵技術(shù)進(jìn)行整理,討論現(xiàn)有事務(wù)提交關(guān)鍵技術(shù)的應(yīng)用現(xiàn)狀和優(yōu)缺點(diǎn),以及歸納它們各自解決的傳統(tǒng)事務(wù)提交的瓶頸;第三部分對事務(wù)提交機(jī)制存在的挑戰(zhàn)與未來的發(fā)展趨勢進(jìn)行探討.

1 傳統(tǒng)事務(wù)提交流程與分析

內(nèi)存數(shù)據(jù)庫在處理數(shù)據(jù)庫恢復(fù)問題(Database Recovery)[10]時,目前大多數(shù)系統(tǒng)都基于數(shù)據(jù)庫日志[11].基于日志的ARIES傳統(tǒng)事務(wù)提交機(jī)制是大多數(shù)系統(tǒng)的選擇.然而,隨著可擴(kuò)展事務(wù)處理技術(shù)的發(fā)展,傳統(tǒng)事務(wù)提交機(jī)制已無法滿足新型數(shù)據(jù)庫系統(tǒng)的需求.下面對ARIES的事務(wù)提交機(jī)制進(jìn)行分析,歸納出其存在的瓶頸.

1.1 Write Ahead Logging方法

由IBM提出的ARIES算法是經(jīng)典的數(shù)據(jù)庫恢復(fù)原型算法,其中預(yù)寫日志(Write Ahead Logging,WAL)[12],自20世紀(jì)90年代問世一直是事務(wù)提交的標(biāo)準(zhǔn).盡管目前大量數(shù)據(jù)庫系統(tǒng)已使用多核硬件及大容量內(nèi)存,但這些系統(tǒng)仍使用這種集中式的ARIES預(yù)寫日志提交機(jī)制[2,13].

傳統(tǒng)事務(wù)提交機(jī)制的核心是數(shù)據(jù)落入磁盤必須發(fā)生在這些修改記錄日志,且日志被寫到磁盤之后.事務(wù)執(zhí)行過程中所有操作產(chǎn)生的日志先填寫到日志緩沖區(qū),直到發(fā)出事務(wù)提交請求時才會把緩沖區(qū)的日志寫到非易失性存儲器(磁盤),數(shù)據(jù)后于日志落盤.

傳統(tǒng)事務(wù)提交機(jī)制遵循“先寫日志”的原則,以確保數(shù)據(jù)安全.數(shù)據(jù)落盤和日志落盤是兩個不同的階段,這兩個階段之間有可能發(fā)生故障.如果數(shù)據(jù)先落盤,而日志沒有存下來,那么故障恢復(fù)時,日志與數(shù)據(jù)是不一致的,系統(tǒng)無法恢復(fù).如果先寫了日志,還沒來得及將數(shù)據(jù)更新到磁盤,那么在系統(tǒng)重啟后,根據(jù)日志文件中的記錄,重新將更新數(shù)據(jù)補(bǔ)錄,確保數(shù)據(jù)安全.因此,傳統(tǒng)事務(wù)提交機(jī)制嚴(yán)格地保持?jǐn)?shù)據(jù)和日志的一致性,系統(tǒng)出現(xiàn)故障后將已提交的事務(wù)根據(jù)日志文件進(jìn)行重做,而將未提交的事務(wù)恢復(fù)到事務(wù)開始前的狀態(tài).

1.2 事務(wù)提交的瓶頸分析

隨著多機(jī)、大內(nèi)存以及多核系統(tǒng)的發(fā)展,數(shù)據(jù)庫負(fù)載變得復(fù)雜和高并發(fā)化,系統(tǒng)無法達(dá)到足夠高的并行性以滿足硬件需要.日志作為全局的數(shù)據(jù)結(jié)構(gòu),被每個運(yùn)行的事務(wù)共享,在事務(wù)執(zhí)行中成為了一個全局互斥點(diǎn).事務(wù)執(zhí)行因日志的嚴(yán)格互斥性,在提交階段發(fā)生阻塞,大量事務(wù)為爭用日志結(jié)構(gòu)而不斷等待,降低事務(wù)并行速度從而嚴(yán)重影響系統(tǒng)的吞吐量.

Stonebraker等人對傳統(tǒng)數(shù)據(jù)庫系統(tǒng)做了一次分析[14].實(shí)驗(yàn)分析,系統(tǒng)只有約10%時間在實(shí)際處理事務(wù),而剩下巨大的90%都花費(fèi)在三大部分:緩沖區(qū)管理,鎖管理和日志管理.為強(qiáng)有力的說明事務(wù)提交已成為內(nèi)存數(shù)據(jù)系統(tǒng)的一大瓶頸,Johnson R等人對Shore-MT系統(tǒng)[15]進(jìn)行分析:Shore-MT隨事務(wù)線程數(shù)逐漸增加,事務(wù)執(zhí)行的時間分布情況,使用TATP Update Location transaction.其中Shore-MT是Shore[16]優(yōu)化的48核數(shù)據(jù)庫系統(tǒng).實(shí)驗(yàn)顯示:隨線程數(shù)增加,日志管理約占事務(wù)執(zhí)行總時間的20%,鎖管理約占10%,其他競爭約占5%,其他latch約占25%,而剩下40%都花費(fèi)在日志競爭上.由此看出,集中式的事務(wù)提交明顯成為了主要開銷.表1主要從4種延遲來分析與歸納其對事務(wù)提交的影響.

表1 事務(wù)提交瓶頸總結(jié)Tab.1Analysis and conclusions for bottlenecks of transaction commit

2 事務(wù)提交的關(guān)鍵技術(shù)

根據(jù)傳統(tǒng)事務(wù)提交的整個流程以及其存在的各種瓶頸,本文主要研究與討論基于多核、NVM和高速網(wǎng)絡(luò)等硬件設(shè)備的事務(wù)提交關(guān)鍵技術(shù).

2.1 基于?核的事務(wù)提交關(guān)鍵技術(shù)

面對多核在新型內(nèi)存數(shù)據(jù)庫系統(tǒng)中的廣泛應(yīng)用和高并發(fā)負(fù)載需求,已有一系列成熟的技術(shù)充分利用每個核的調(diào)度請求來提高系統(tǒng)的并行性,減少系統(tǒng)的性能瓶頸,主要分為緩沖區(qū)填寫日志階段和日志寫入磁盤階段的優(yōu)化.

2.1.1 成組提交(Group Commit)

事務(wù)每進(jìn)行一次提交,緩沖區(qū)中日志刷磁盤階段都會產(chǎn)生磁盤I/O.多數(shù)事務(wù)因處于等待狀態(tài)而增加延遲,從而造成了系統(tǒng)瓶頸.

為減少每次事務(wù)提交產(chǎn)生的磁盤I/O,成組提交提出了一種新的解決方案,即每隔時間T、或者每提交X個事務(wù)、或者提交的N個事務(wù)日志長度達(dá)到L字節(jié)時,才將緩沖區(qū)中的積累的所有日志統(tǒng)一刷磁盤.

成組提交的特點(diǎn)是打包多個事務(wù)日志進(jìn)行成組處理,將原本多次磁盤I/O減少為一次,降低磁盤I/O的開銷.雖然該技術(shù)優(yōu)化了傳統(tǒng)日志的I/O延遲,提高了系統(tǒng)性能,但系統(tǒng)仍存在上下文切換、鎖競爭和緩沖區(qū)競爭等問題.

目前有不少商業(yè)或開源數(shù)據(jù)庫系統(tǒng)使用成組提交,其中包括MySQL[17]和Oracle[18]等.其中,Hekaton[19]對成組提交進(jìn)行了改進(jìn)以適用于自身的架構(gòu).Hekaton是微軟為大內(nèi)存和多核CPU研發(fā)的新型內(nèi)存事務(wù)引擎,現(xiàn)已集成到了SQL Server.Hekaton日志流是存儲在磁盤的數(shù)據(jù),與常規(guī)SQL Server日志相同.不同的是,Hekaton每個事務(wù)只生成單一日志,日志記錄有關(guān)該事務(wù)插入和刪除操作的所有版本,足以在故障恢復(fù)時重做.事務(wù)日志流作為事務(wù)提交的重要結(jié)構(gòu),減少日志生成數(shù)量和空間可提高效率.因此Hekaton在每個事務(wù)提交時才生成日志填入緩沖區(qū),并成組寫入磁盤以減少多次磁盤I/O切換.

2.1.2 異步提交(Asynchronous Commit)

針對磁盤I/O的延遲問題,異步提交[20-21]對成組提交進(jìn)行了擴(kuò)展.相比與傳統(tǒng)的事務(wù)提交,它增加了日志提交線程(Commit Threads),專門進(jìn)行日志刷盤活動.每個事務(wù)提交時,處理線程(Handle Threads)填完緩沖區(qū)日志后就響應(yīng)客戶端.緩沖區(qū)日志成組(每隔時間T、每X個事務(wù)或提交的N個事務(wù)日志長度達(dá)到L字節(jié))后,提交線程將緩沖區(qū)成組的日志刷盤.圖2是異步提交的基本流程:①處理線程填寫緩沖區(qū)日志;②處理線程響應(yīng)客戶端,③提交線程將成組的緩沖區(qū)日志刷盤.

圖2 異步提交流程Fig.2Process of asynchronous commit

異步提交的特點(diǎn)是事務(wù)不等待日志刷盤成功就響應(yīng)客戶端,商業(yè)和開源數(shù)據(jù)庫系統(tǒng)Oracle[20]和PostgreSQL[21]就采用了這種提交方式.異步提交將耗時較長的日志刷盤階段完全隱藏不僅縮短了響應(yīng)客戶端的時間,還減少了鎖競爭和過度的上下文切換.但該提交下的數(shù)據(jù)是不安全,如果系統(tǒng)故障而崩潰,已提交的日志可能因還沒有被刷到磁盤而丟失.

2.1.3 提前釋放鎖(Early Lock Release,ELR)

日志寫入磁盤階段除了磁盤I/O的延遲,還存在的問題是事務(wù)直到日志持久化成功后才能釋放鎖.事務(wù)長期持鎖使得其他并行事務(wù)阻塞而產(chǎn)生鎖沖突,因此增加事務(wù)提交的延遲,并導(dǎo)致系統(tǒng)的并行度無法提高.

針對這一問題,DeWitt等人[1]早在20世紀(jì)80年代就提出了在一定條件下事務(wù)可在日志刷盤前安全釋放鎖的觀點(diǎn).事務(wù)被分為兩種類型:預(yù)提交事務(wù)和依賴事務(wù).提前釋放鎖的事務(wù)稱為預(yù)提交事務(wù);訪問預(yù)提交事務(wù)的更新數(shù)據(jù)的事務(wù)稱為依賴事務(wù),依賴于預(yù)提交事務(wù).在緩沖區(qū)填寫階段之前,事務(wù)就已確定全局的提交順序.提交過程中,未依賴于其他事務(wù)的預(yù)提交事務(wù)可提前釋放鎖,無依賴關(guān)系的事務(wù)得到鎖后就可繼續(xù)執(zhí)行,提高了事務(wù)提交效率.只有少數(shù)依賴事務(wù)被阻塞,需等到預(yù)提交事務(wù)日志刷盤成功并響應(yīng)客戶端.過了十多年,觀點(diǎn)的正確性才被文獻(xiàn)[22]證明.另外,提前釋放鎖必須滿足兩個條件才能維持系統(tǒng)的可恢復(fù)性.

(1)每個依賴事務(wù)必須在它依賴的預(yù)提交事務(wù)日志刷盤完成后進(jìn)行刷盤.

(2)當(dāng)一個預(yù)提交事務(wù)被終止了,那么所有該預(yù)提交事務(wù)的依賴事務(wù)也將被終止.

提前釋放鎖的特點(diǎn)是消除了日志刷盤帶給其他事務(wù)的延遲,只有依賴事務(wù)必須等待其刷盤后才能完成提交操作,其他事務(wù)可立即獲得鎖繼續(xù)執(zhí)行.早在正確性被驗(yàn)證之前,文獻(xiàn)［23］和IBM的IVS[24]事務(wù)處理工具就已采用了這種技術(shù).對于鎖競爭激烈的負(fù)載,提前釋放鎖使系統(tǒng)性能顯著提升.與異步提交比較,它能夠保證數(shù)據(jù)安全.

2.1.4 流水線提交(Flush Pipelining)

近幾年已有一些研究[25-26]通過閃存優(yōu)化來減少I/O延遲,但閃存不能完全消除日志刷盤的高延遲.在多核數(shù)據(jù)庫系統(tǒng)中,日志寫入磁盤階段仍存在著頻繁的上下文切換延遲.

Johnson.R等人提出了流水線提交[27]:流水線提交是將傳統(tǒng)的事務(wù)處理分成兩個階段:事務(wù)處理階段和事務(wù)提交階段,分別對應(yīng)多個事務(wù)代理線程(Agent Threads)和一個事務(wù)守護(hù)線程(Daemon Threads).事務(wù)代理線程負(fù)責(zé)負(fù)責(zé)寫緩沖區(qū)、響應(yīng)客戶端;守護(hù)線程負(fù)責(zé)刷盤.事務(wù)提交時,代理線程寫完緩沖區(qū)日志就將當(dāng)前待提交任務(wù)壓入響應(yīng)客戶端隊(duì)列,而自己執(zhí)行其他事務(wù).每隔時間T、每X個事務(wù)或提交的N個事務(wù)日志長度達(dá)到L字節(jié)后,守護(hù)線程將那部分緩沖區(qū)日志刷磁盤.日志刷盤后,守護(hù)線程通知代理線程最新一批已完成的事務(wù).代理線程喚醒隊(duì)列中的待提交任務(wù),完成提交并響應(yīng)客戶端.圖3是流水線提交的基本流程.

流水線提交的特點(diǎn)是將事務(wù)處理拆分成兩個階段進(jìn)行,長時間的日志刷盤階段交給專門線程執(zhí)行.Johnson R等人在Shore-MT的Aether日志組件中對它進(jìn)行了實(shí)現(xiàn),對比傳統(tǒng)機(jī)制,系統(tǒng)性能提高了22%.流水線提交不僅減少了頻繁的上下文切換的瓶頸,還能保證數(shù)據(jù)安全,從而大大提高了系統(tǒng)的吞吐量.

圖3 流水線提交流程Fig.3Process of flush pipelining

2.1.5 可擴(kuò)展的緩沖區(qū)(Scalable Log Buffer)

傳統(tǒng)事務(wù)提交機(jī)制的每個日志都分配全局唯一的日志序列號LSN,作為數(shù)據(jù)存入磁盤的時間戳,緩沖區(qū)寫日志階段必須是互斥的.并且傳統(tǒng)事務(wù)處理采用的是集中式日志緩沖區(qū).

為永久地消除日志緩沖區(qū)競爭,并且使其不受日志大小和線程數(shù)量的影響,Johnson R等人提出兩種可擴(kuò)展的日志緩沖區(qū)設(shè)計(jì)[27]:合并緩沖區(qū)分配(Consolidating Buffer Allocation)和解耦緩沖區(qū)填寫(Decoupling Buffer Fill).

合并緩沖區(qū)分配的優(yōu)化目的是減少競爭,并使事務(wù)提交不受線程數(shù)的影響.多個線程同時競爭鎖,獲得鎖的線程生成LSN并填寫緩沖區(qū)日志.未獲得鎖的多線程搶占一個固定大小的“合并數(shù)組”(Consolidation Array)[28].搶占成功的多個線程成組等待鎖釋放.一旦釋放鎖,第一個成員將獲得鎖并生成LSN,并將LSN、緩沖區(qū)位置和偏移通知下一成員.所有成員依次推算出LSN和緩沖區(qū)位置后,并行填寫緩沖區(qū)日志.所有成員填寫完后清空數(shù)組,并由該數(shù)組最后一個成員的線程負(fù)責(zé)緩沖區(qū)日志刷盤和緩沖區(qū)空間的釋放.

解耦緩沖區(qū)填寫進(jìn)一步提高了日志緩沖區(qū)填寫的并行度.在傳統(tǒng)事務(wù)提交機(jī)制基礎(chǔ)上,生成LSN的線程在獲得緩沖區(qū)位置的同時釋放鎖,另一個線程就可獲得鎖并確定緩沖區(qū)位置.確定緩沖區(qū)位置的線程可填寫緩沖區(qū)日志,使得日志進(jìn)行流水線式的填寫.防止創(chuàng)建空白日志而丟失可恢復(fù)性,緩沖區(qū)空間必須按LSN順序釋放,使日志按LSN依次寫入磁盤.

雖然在合并緩沖區(qū)分配的優(yōu)化下,填寫緩沖區(qū)日志的時間開銷與組內(nèi)成員日志大小和釋放緩沖區(qū)空間成正比,但對于組內(nèi)的多個事務(wù)提交性能得到了一定的提升.而解耦緩沖區(qū)填寫的優(yōu)化技術(shù),雖然使得大量線程可同時對緩沖區(qū)進(jìn)行日志填寫,提高了事務(wù)提交的并發(fā)性,但是順序釋放緩沖區(qū)的操作成為了關(guān)鍵延遲.

2.2 基于NVM的事務(wù)提交關(guān)鍵技術(shù)

新興的NVM技術(shù)從根本上改變了事務(wù)提交的設(shè)計(jì)原則.NVM因其數(shù)據(jù)非易失和高效訪問的特性,使得事務(wù)日志不再需要暫存緩沖區(qū)后刷到磁盤的緩慢流程,以保證事務(wù)的持久性.但由于NVM的成本較高,且訪問模式與傳統(tǒng)的內(nèi)存和二級存儲都不相同,加上目前NVM技術(shù)本身仍然不夠成熟,基于NVM日志存儲的事務(wù)提交機(jī)制研究處于起步階段.

基于NVM的分布式日志提交(NVM-based Distributed Logging)[6]是一種基于NVM日志存儲的事務(wù)提交原型.多核數(shù)據(jù)庫系統(tǒng)的每個核都分配一個NVM緩沖區(qū).事務(wù)填完NVM緩沖區(qū)日志就完成事務(wù)提交,這是因?yàn)镹VM的非易失性保證了事務(wù)的持久性.當(dāng)NVM緩沖區(qū)的日志填滿時,系統(tǒng)再將這些日志轉(zhuǎn)存入磁盤.如何對日志分區(qū)和保證日志次序成為了難點(diǎn).該提交技術(shù)采用兩種策略:事務(wù)分區(qū)和頁分區(qū),分別依據(jù)事務(wù)和數(shù)據(jù)頁的相關(guān)性來分配.相對于傳統(tǒng)事務(wù)提交機(jī)制的LSN,該提交技術(shù)采用基于邏輯時鐘[29]的全局序列號(Global Sequence Number)以保證生成日志的順序.另外,日志從易失性CPU寫到NVM緩沖區(qū)的階段采用被動的成組提交(Passive Group Commit)以保證系統(tǒng)的可恢復(fù)性.

基于NVM的分布式日志提交解決了磁盤I/O延遲和日志緩沖區(qū)競爭的瓶頸,實(shí)驗(yàn)證明其具有低沖突和高吞吐的性能.隨著NVM技術(shù)的日益成熟,基于NVM的事務(wù)提交技術(shù)將越來越熱門.

2.3 基于高速網(wǎng)絡(luò)與高性能固態(tài)存儲的事務(wù)提交關(guān)鍵技術(shù)

高速網(wǎng)絡(luò)的發(fā)展使網(wǎng)絡(luò)延遲變得越來越小,目前網(wǎng)絡(luò)傳輸已能夠達(dá)到100 Gb/s.閃存等固態(tài)存儲設(shè)備也發(fā)展迅速,其讀寫性能與磁盤相比高出約104IOPS.越來越多的學(xué)者開始研究基于高速網(wǎng)絡(luò)與高性能固態(tài)存儲的存儲系統(tǒng).基于這兩種硬件的事務(wù)提交技術(shù)應(yīng)運(yùn)而生.

Hyder[30]事務(wù)提交是基于高速網(wǎng)絡(luò)與閃存硬件,面向具有共享的網(wǎng)絡(luò)尋址存儲(Network-Addressable Storage)的集群.Hyder事務(wù)提交的流程如下:分布式系統(tǒng)的一個站點(diǎn)的事務(wù)執(zhí)行產(chǎn)生的更新操作暫存在本地緩存,并廣播給所有站點(diǎn);同時該站點(diǎn)將生成的日志通過高速網(wǎng)絡(luò)存入閃存優(yōu)化的共享可擴(kuò)展日志結(jié)構(gòu)(Shared Striped Log);其他站點(diǎn)接收消息后,更新到本地緩存以保證全局日志的連續(xù)性.

Hyder事務(wù)提交目前應(yīng)用于Hyder系統(tǒng),微軟研究的一個多版本的日志文件/數(shù)據(jù)庫系統(tǒng).該提交技術(shù)不僅解決了鎖競爭,還降低了日志緩沖區(qū)的沖突,使系統(tǒng)性能大大提升.除了Hyder,還有Flash-log[7]、CORFU[8]、Tango[9],也利用專門的大容量固態(tài)存儲服務(wù)器,配以定制的事務(wù)提交機(jī)制,提供共享的高性能日志服務(wù).但是這些系統(tǒng)要求高性能的網(wǎng)絡(luò)和存儲服務(wù)器,無法直接在現(xiàn)有的新型內(nèi)存數(shù)據(jù)庫系統(tǒng)中使用.

2.4 事務(wù)提交關(guān)鍵技術(shù)的小結(jié)

本文分析的事務(wù)提交關(guān)鍵技術(shù)利用新型數(shù)據(jù)庫系統(tǒng)不同硬件特點(diǎn),針對性地解決了傳統(tǒng)事務(wù)提交機(jī)制存在的一些瓶頸.這些事務(wù)提交關(guān)鍵技術(shù)各自存在優(yōu)缺點(diǎn).表2是對事務(wù)提交技術(shù)解決不同的瓶頸進(jìn)行的歸納.

表2 事務(wù)提交關(guān)鍵技術(shù)各自解決的瓶頸Tab.2The bottlenecks that key techniques of transaction commit respectively have resolved

3 總結(jié)

面對越來越復(fù)雜的高并發(fā)事務(wù)處理,目前新型內(nèi)存數(shù)據(jù)庫系統(tǒng)已無法達(dá)到足夠的高吞吐量以滿足應(yīng)用需求.傳統(tǒng)事務(wù)提交機(jī)制因存在局限性而逐漸成為了系統(tǒng)的性能瓶頸.本文重點(diǎn)整理和分析了利用多核特性的成組提交、異步提交、提前釋放鎖和流水線提交等事務(wù)提交技術(shù),基于NVM的分布式事務(wù)提交技術(shù)以及基于高速網(wǎng)絡(luò)和高性能固態(tài)存儲的事務(wù)提交技術(shù),這些關(guān)鍵技術(shù)在不同程度上地解決傳統(tǒng)事務(wù)提交機(jī)制的瓶頸.此外,本文對它們各自的應(yīng)用現(xiàn)狀和優(yōu)缺點(diǎn)進(jìn)行分析與歸納.

隨著海量數(shù)據(jù)事務(wù)處理的復(fù)雜化,以及計(jì)算機(jī)硬件設(shè)備的極速更新,傳統(tǒng)事務(wù)提交機(jī)制無法滿足系統(tǒng)需求.越來越多的學(xué)者利用新型內(nèi)存數(shù)據(jù)庫系統(tǒng)的多核和大內(nèi)存等特性來研究事務(wù)提交的優(yōu)化方法.而事務(wù)提交涉及數(shù)據(jù)庫系統(tǒng)的多種模塊管理結(jié)構(gòu),包括緩沖區(qū)管理,鎖管理等,這些模塊需要相互權(quán)衡.日志不是一個全序關(guān)系,而是一個偏序關(guān)系,如何對事務(wù)提交進(jìn)行解耦合是目前事務(wù)提交優(yōu)化的困難之一.對提交事務(wù)進(jìn)行預(yù)處理是優(yōu)化的趨勢,但由于事務(wù)間復(fù)雜的依賴關(guān)系,事務(wù)的合理分區(qū)成為難點(diǎn).而在解耦合過程中,提高事務(wù)并發(fā)度使得各階段的校驗(yàn)變得更加復(fù)雜.另外,傳統(tǒng)事務(wù)提交機(jī)制并沒有考慮數(shù)據(jù)庫系統(tǒng)所處的網(wǎng)絡(luò)環(huán)境,分布式數(shù)據(jù)庫系統(tǒng)的日志同步代價和成本是巨大的,需進(jìn)一步改進(jìn)才能在實(shí)際環(huán)境中應(yīng)用.所以設(shè)計(jì)出一種能夠同時解決所有傳統(tǒng)事務(wù)提交機(jī)制的瓶頸,又能適應(yīng)于多種環(huán)境的事務(wù)提交新技術(shù)面臨著巨大的挑戰(zhàn).

同時NVM等一些非易失性內(nèi)存的發(fā)展和SSD、Flash等一些非易失性固態(tài)存儲器成本的不斷降低,將有力推動事務(wù)提交優(yōu)化技術(shù)的發(fā)展.采用這些新型硬件設(shè)備,可以減少事務(wù)提交中日志持久化過程,大大提高事務(wù)提交效率.作為未來研究熱點(diǎn)的可擴(kuò)展事務(wù)提交將是避免產(chǎn)生瓶頸的有效手段,其中采用lock-free和latch-free的數(shù)據(jù)結(jié)構(gòu)可減少事務(wù)提交過程中的鎖競爭;采用CAS原子操作可實(shí)現(xiàn)日志串行化以提高吞吐量.此外,解耦傳統(tǒng)數(shù)據(jù)庫架構(gòu),將日志單獨(dú)作為服務(wù)系統(tǒng)也是事務(wù)提交技術(shù)未來研究的方向之一.

［1］DEWITT D J,KATZ R H,OLKEN F,et al.Implementation techniques for main memory database systems[J]. Acm Sigmod Record,1984,14(2):1-8.

［2］RAGHU R,JOHANNES G.Database Management Systems.[M].3th ed.New York:McGraw-Hill,2003.

［3］HELLAND P,SAMMER H,LYON J,et al.Group commit timers and high volume transaction systems[C]//High Performance Transaction Systems.USA:Springer Berlin Heidelberg,1987:301-329.

［4］PELLEY S,CHEN P M,WENISCH T F.Memory persistency[J].Acm Sigarch Computer Architecture News, 2014,42(3):265-276.

［5］FANG R,HSIAO H I,HE B,et al.High performance database logging using storage class memory[C]//IEEE International Conference on Data Engineering.[S.l.]:IEEE,2011:1221-1231.

［6］WANG T,JOHNSON R.Scalable logging through emerging non-volatile memory[J].Proceedings of the VLDB Endowment,2014,7(10):865-876.

［7］BALAKRISHNAN M,BERNSTEIN P A,MALKHI D,et al.Brief Announcement Flash-Log-A High Throughput Log[J].Lecture Notes in Computer Science,2010,1(6343):401-403.

［8］BALAKRISHNAN M,MALKHI D,DAVIS J D,et al.CORFU:A distributed shared log[J].Acm Transactions on Computer Systems(TOCS),2013,31(4):879-889.

［9］BALAKRISHNAN M,MALKHI D,WOBBER T,et al.Tango:Distributed data structures over a shared log[C]//Twenty-Fourth ACM Symposium on Operating Systems Principles.New York:ACM,2013:325-340.

［10］MALVIYA N,WEISBERG A,MADDEN S,et al.Rethinking main memory oltp recovery[C]//International Conference on Data Engineering.[S.l.]:IEEE,2014:604-615.

［11］GRAY J,REUTER A.Transaction Processing:Concepts and Techniques[M].San Francisco:Margan Kaufmann, 2015.

［12］MOHAN C,HADERLE D,LINDSAY B,et al.ARIES:A transaction recovery method supporting finegranularity locking and partial rollbacks using write-ahead logging[J].Acm Transactions on Database Systems (TODS),1992,17(1):94-162.

［13］MOHAN C.Repeating history beyond ARIES[J].VLDB,1999,99:1-17.

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

［15］JOHNSON R,PANDIS I,HARDAVELLAS N,et al.Shore-MT:a scalable storage manager for the multicore era[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.New York:ACM,2009:24-35.

［16］CAREY M J,DEWITT D J,FRANKLIN M J,et al.Shoring Up Persistent Applications[M].New York:ACM, 1994.

［17］MySQL A B.MySQL:The world’s most popular open source database[EB/OL].(2005-12-01)[2016-05-23]. http://www.mysql.com.

［18］LONEY K,MCCLAIN L.Oracle Database 10g:The Complete Reference[M]//Oracle 8:The Complete Reference.New York:Osbome/McGraw-Hill,1997,10(6):179.

［19］DIACONU C,FREEDMAN C,ISMERT E,et al.Hekaton:SQL server’s memory-optimized OLTP engine[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.New York: ACM,2013:1243-1254.

［20］THOME B,GAWLICK D,PRATT M.Event processing with on oracle database[C]//Proceedings of the 2005 ACM SIGMOD Interational Conference on Management of Data.New York:ACM,2005:863-867.

［21］彭智勇,彭煜煒.PostgreSQL數(shù)據(jù)庫內(nèi)核分析[M].北京:機(jī)械工業(yè)出版,2011:343-404.

［22］SOISALON-SOININEN E,YL?NEN T.Partial strictness in two-phase locking[C]//Intemational Conference on Database Theory.USA:Springer Berlin Heidelberg,1995:139-147.

［23］LIU C C,MINOURA T.Effect of update merging on reliable storage performance[C]//Second International Conference on Data Engineering.[S.l.]:IEEE,1986:208-213.

［24］GAWLICK D,KINKADE D.Varieties of concurrency control in IMS/VS fast path[J].IEEE Database Eng Bull, 1985,8(2):3-10.

［25］CHEN S.FlashLogging:Exploiting flash devices for synchronous logging performance[C]//Proceedings of the International Conference on Management of Data.New York:ACM,2009:73-86.

［26］LEE S W,MOON B,PARK C,et al.A case for flash memory ssd in enterprise database applications[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.New York: ACM,2008:1075-1086.

［27］JOHNSON R,PANDIS I,STOICA R,et al.Aether:A scalable approach to logging[J].Proceedings of the VLDB Endowment,2010,3(1-2):681-692.

［28］MOIR M,NUSSBAUM D,SHALEV O,et al.Using elimination to implement scalable and lock-free fifo queues[C]//Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures.New York:ACM,2005:253-262.

［29］LAMPORT L.Time,clocks,and the ordering of events in a distributed system[J].Communications of the ACM, 1978,21(7):558-565.

［30］BERNSTEIN P A,REID C W,DAS S.Hyder-A transactional record manager for shared flash[J].CIDR,2011(11): 9-20.

(責(zé)任編輯:張晶)

Key techniques and challenges of transaction commit in main-memory database systems

HU Shuang,ZHOU Huan,QIAN Wei-ning
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

Since its debut in the 1990s,ARIES,as the traditional transaction commit, has been widely adopted by the mainstream commercial or open source database systems. With the performance of applications increasingly improved,transaction commit based on the traditional hardwares has become the first bottleneck for performance of systems. However,the developments of high-performance hardwares,such as memory and multiple CPU cores,offer a new opportunity for the optimization of transaction commit.In this paper,we analyze and summarize the existing bottlenecks of traditional transaction commit in detail.Furthermore,key techniques of transaction commit based on new hardwares are discussed and concluded,including their application status,advantages and disadvantages. Finally,challenges and future developments for optimization of transaction commit are discussed.

main-memory database systems;transaction commit;techniques of log processing

TP391

A

10.3969/j.issn.1000-5641.2016.05.003

1000-5641(2016)05-0018-09

2016-05

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61332006);國家863計(jì)劃項(xiàng)目(2015AA015307)

胡爽,女,碩士研究生,研究方向?yàn)榉植际綌?shù)據(jù)庫系統(tǒng).E-mail:hu621000@sina.com.

錢衛(wèi)寧,男,教授,博士生導(dǎo)師,研究方向?yàn)榭蓴U(kuò)展事務(wù)處理和海量數(shù)據(jù)管理與分析. E-mail:wnqian@sei.ecnu.edu.cn.