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

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

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

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

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

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

ARIES作為傳統(tǒng)事務(wù)提交機(jī)制從20世紀(jì)90年代問(wèn)世以來(lái),一直是主流商業(yè)或開(kāi)源數(shù)據(jù)庫(kù)系統(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ī)制中存在的問(wèn)題,然后歸納并討論了現(xiàn)有基于新型硬件的事務(wù)提交技術(shù)的應(yīng)用現(xiàn)狀與優(yōu)缺點(diǎn),最后探討了事務(wù)提交優(yōu)化的未來(lái)發(fā)展與挑戰(zhàn).

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

0 引言

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

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

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

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

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

本文主要從三個(gè)部分展開(kāi)論述.第一部分針對(duì)目前新型內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)高并發(fā)的負(fù)載特點(diǎn),分析傳統(tǒng)事務(wù)提交機(jī)制存在的瓶頸;第二部分對(duì)利用不同硬件特性優(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ù)提交的瓶頸;第三部分對(duì)事務(wù)提交機(jī)制存在的挑戰(zhàn)與未來(lái)的發(fā)展趨勢(shì)進(jìn)行探討.

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

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

1.1 Write Ahead Logging方法

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

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

傳統(tǒng)事務(wù)提交機(jī)制遵循“先寫(xiě)日志”的原則,以確保數(shù)據(jù)安全.數(shù)據(jù)落盤(pán)和日志落盤(pán)是兩個(gè)不同的階段,這兩個(gè)階段之間有可能發(fā)生故障.如果數(shù)據(jù)先落盤(pán),而日志沒(méi)有存下來(lái),那么故障恢復(fù)時(shí),日志與數(shù)據(jù)是不一致的,系統(tǒng)無(wú)法恢復(fù).如果先寫(xiě)了日志,還沒(méi)來(lái)得及將數(shù)據(jù)更新到磁盤(pán),那么在系統(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ù)開(kāi)始前的狀態(tài).

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

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

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

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

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

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

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

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

2.1.1 成組提交(Group Commit)

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

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

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

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

2.1.2 異步提交(Asynchronous Commit)

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

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

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

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

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

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

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

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

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

2.1.4 流水線提交(Flush Pipelining)

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

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

流水線提交的特點(diǎn)是將事務(wù)處理拆分成兩個(gè)階段進(jìn)行,長(zhǎng)時(shí)間的日志刷盤(pán)階段交給專(zhuān)門(mén)線程執(zhí)行.Johnson R等人在Shore-MT的Aether日志組件中對(duì)它進(jìn)行了實(shí)現(xiàn),對(duì)比傳統(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ī)制的每個(gè)日志都分配全局唯一的日志序列號(hào)LSN,作為數(shù)據(jù)存入磁盤(pán)的時(shí)間戳,緩沖區(qū)寫(xiě)日志階段必須是互斥的.并且傳統(tǒng)事務(wù)處理采用的是集中式日志緩沖區(qū).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

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

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

［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ù)庫(kù)內(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

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

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

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