任 堃， 李戰(zhàn)懷

(西北工業(yè)大學 計算機學院， 西安 710129)

?

新型OLTP數(shù)據(jù)庫系統(tǒng)設計的關鍵技術及挑戰(zhàn)

任 堃， 李戰(zhàn)懷

(西北工業(yè)大學 計算機學院， 西安 710129)

傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)是根據(jù)20世紀70年代的硬件特點而設計. 隨著“云計算”和“大數(shù)據(jù)”時代的到來，應用需求對數(shù)據(jù)庫系統(tǒng)的事務吞吐量和可擴展性提出了更高的要求，同時內(nèi)存、多核等新型計算機硬件技術的發(fā)展為數(shù)據(jù)庫系統(tǒng)的發(fā)展提供了新的機遇，因此研究和設計新型數(shù)據(jù)庫系統(tǒng)也變得越來越重要. 本文針對新型計算機硬件和應用需求的特點，研究和分析了新型OLTP數(shù)據(jù)庫系統(tǒng)設計所涉及的關鍵技術，并探討了存在的挑戰(zhàn)性問題.

可擴展性； 計算機硬件； 事務處理; 確定性

0 引 言

現(xiàn)今的計算機硬件特點和20世紀70年代存在很大不同，在70年代，數(shù)據(jù)庫系統(tǒng)通常在單核處理器下運行，內(nèi)存容量非常有限，大多數(shù)數(shù)據(jù)庫系統(tǒng)是以磁盤作為主要存儲介質(zhì)[1-2]. 隨著計算機硬件的發(fā)展，目前單臺服務器的內(nèi)存容量已經(jīng)達到TB級，而大多數(shù)數(shù)據(jù)庫系統(tǒng)應用的大小僅有幾百GB，因此很多數(shù)據(jù)庫系統(tǒng)完全可以在內(nèi)存中運行[3]；同時計算機中的處理器核心越來越多，內(nèi)存、多核等硬件技術的發(fā)展為數(shù)據(jù)庫系統(tǒng)的發(fā)展提供了新的機遇. 相關研究[4-5]表明傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)策略不能充分發(fā)揮內(nèi)存和多核的硬件優(yōu)勢.

聯(lián)機事務處理(On-Line Transaction Processing,OLTP)是數(shù)據(jù)庫系統(tǒng)最重要的應用之一. 目前聯(lián)機事務處理在金融、電信、互聯(lián)網(wǎng)、游戲、交通、購物、醫(yī)療等關鍵領域起到非常重要的作用，也是學術界的研究熱點. 隨著“云計算”和“大數(shù)據(jù)”時代的到來，很多OLTP應用場景對數(shù)據(jù)庫的事務吞吐量和可擴展性提出了更高的要求.

事務的ACID屬性可以保證事務并發(fā)執(zhí)行的正確性，是數(shù)據(jù)庫系統(tǒng)中的一個重要概念. 通常情況下數(shù)據(jù)庫系統(tǒng)允許多個事務并發(fā)執(zhí)行. 當多個事務并發(fā)執(zhí)行時，傳統(tǒng)的策略是通過可串行化理論來保證ACID屬性[6-8]，尤其是隔離性屬性. 相關研究表明在分布式數(shù)據(jù)庫中保證事務的ACID屬性更具有挑戰(zhàn)[7-10]，保證分布式事務的ACID屬性限制了傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)的可擴展性[11,12]. 然而在“云計算”和“大數(shù)據(jù)”的背景下，數(shù)據(jù)庫系統(tǒng)的可擴展性顯得尤為重要.

為了數(shù)據(jù)的可靠性和提高系統(tǒng)的吞吐量，數(shù)據(jù)庫系統(tǒng)通常采取多副本策略[13-16]，如果保證副本間的強一致性，將增加事務的延遲和限制系統(tǒng)吞吐量. 有些系統(tǒng)采用最終一致性策略[17]，此策略能夠緩解強一致性所帶來的限制和缺點，但卻存在副本間不一致的情況，這在銀行等很多場景下是不允許出現(xiàn)的.

本文針對新型計算機硬件和應用需求的特點，研究和分析了新型OLTP數(shù)據(jù)庫系統(tǒng)設計所涉及的關鍵技術，同時也分析了分布式數(shù)據(jù)庫設計中的關鍵問題，并探討了存在的挑戰(zhàn)性問題及今后重點研究方向.

1 傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)設計框架及其問題

首先回顧一下傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)的設計框架，其主要基于20世紀70年代的計算機硬件特點而設計，主要包括以下幾個模塊.

(1) 緩存池管理(Buffer Pool Manager)[18-21]：因為傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)內(nèi)存比較小而無法存儲整個數(shù)據(jù)庫系統(tǒng)，所以數(shù)據(jù)庫系統(tǒng)用緩存池模塊在內(nèi)存中緩存一些磁盤塊數(shù)據(jù)，并設計各種緩存算法來提高緩存命中率. 每個數(shù)據(jù)庫查詢操作首先查詢所要操作的數(shù)據(jù)是否在緩存池中，如果命中就從緩存池中取出數(shù)據(jù)，否則就從磁盤中讀取. 同時需要設計緩存池的緩存置換策略.

(2) 并發(fā)控制機制(Concurrency Control Mechanism)：當一個線程執(zhí)行的事務嘗試訪問的數(shù)據(jù)在磁盤中的時候，此線程處于等待磁盤讀的阻塞狀態(tài). 為了提高系統(tǒng)CPU等資源的利用率，數(shù)據(jù)庫系統(tǒng)使用并發(fā)控制方法來同時執(zhí)行無沖突的多個事務[7-8]，因此執(zhí)行線程在等待某個事務磁盤操作的時候，可以執(zhí)行別的不沖突的事務. 最常用的并發(fā)控制方法是基于鎖的并發(fā)控制方法，例如System R[1,18]項目提出的兩階段加鎖協(xié)議，此外還有樂觀的并發(fā)控制方法和基于多版本的并發(fā)控制方法等[22-23].

(3) 恢復機制(Recovery Mechanism)：為了保證事務的持久性，使數(shù)據(jù)庫系統(tǒng)在出現(xiàn)軟硬件等系統(tǒng)錯誤的時候仍然能夠恢復，數(shù)據(jù)庫系統(tǒng)使用恢復機制來維護正確的數(shù)據(jù)庫狀態(tài). 大多數(shù)恢復機制都是基于事務日志的實現(xiàn)，需要記錄元組修改前和修改后的狀態(tài)，這些日志最終都需要寫入磁盤[24-27]，在業(yè)界和學術界最經(jīng)典和最廣泛使用的的恢復機制是ARIES恢復機制.

為了測試傳統(tǒng)數(shù)據(jù)庫設計的幾個模塊的開銷，S. Harizopoulos等[4]在開源數(shù)據(jù)庫系統(tǒng)Shore[28]上，測試了數(shù)據(jù)庫系統(tǒng)在執(zhí)行事務的過程中各個模塊所執(zhí)行的CPU指令數(shù)量，從而計算出每個模塊的開銷. 測試集使用的是TPC-C[29]中的New Order事務，測試中使用的數(shù)據(jù)庫的容量小于內(nèi)存容量，因此整個數(shù)據(jù)庫完全在內(nèi)存中存儲，從而模擬了傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)架構(gòu)運行在內(nèi)存數(shù)據(jù)庫的環(huán)境. 圖1顯示的是其測試結(jié)果，其中顯示只有大約12%的CPU時間在實際處理事務，其他時間都花費在緩存池管理、并發(fā)控制和事務恢復模塊上. Postgre、MySQL等數(shù)據(jù)庫系統(tǒng)的測試結(jié)果與之類似. 這充分說明了傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)設計方案難以直接遷移到內(nèi)存數(shù)據(jù)庫系統(tǒng)中，因此非常有必要重新設計數(shù)據(jù)庫系統(tǒng)框架.

圖1 數(shù)據(jù)庫各個模塊的開銷

2 新硬件環(huán)境下的數(shù)據(jù)庫系統(tǒng)設計的關鍵技術及挑戰(zhàn)

針對傳統(tǒng)數(shù)據(jù)庫系統(tǒng)設計存在的問題，本文主要從以下幾個方面來探討新型OLTP數(shù)據(jù)庫系統(tǒng)設計所要考慮的關鍵技術及其挑戰(zhàn).

2.1 針對內(nèi)存的并發(fā)控制方法研究

計算機硬件的發(fā)展特點是內(nèi)存容量越來越大以及價格越來越便宜，這引起了學術界和工業(yè)界對內(nèi)存數(shù)據(jù)庫系統(tǒng)的研究熱潮. 現(xiàn)在有很多針對于內(nèi)存數(shù)據(jù)庫環(huán)境下的并發(fā)控制的研究. 例如Stavros Harizopoulos等[4]通過統(tǒng)計數(shù)據(jù)庫模塊的CPU執(zhí)行指令數(shù)研究發(fā)現(xiàn)，在內(nèi)存環(huán)境下，基于傳統(tǒng)鎖管理器的并發(fā)控制方法占用了大概21%的CPU時間，而實際的事務執(zhí)行時間僅占12%左右，實驗結(jié)果如圖1所示；H-Store[30-31]和Hyper[32]系統(tǒng)提出，在內(nèi)存數(shù)據(jù)庫中不使用任何并發(fā)控制方法，在每個分區(qū)上由單個線程順序執(zhí)行事務的策略，這種策略避免了并發(fā)控制開銷，但卻限制了分布式事務的并發(fā)執(zhí)行；Hekaton系統(tǒng)[33]指出了在內(nèi)存環(huán)境下，傳統(tǒng)的并發(fā)控制方法都不適用，并研究和提出了兩種高效的基于多版本的并發(fā)控制方法，一種是悲觀的，一種是樂觀的，在這種并發(fā)控制策略中，事務不會出現(xiàn)阻塞的現(xiàn)象；I.Pandis等[34]重新設計了并發(fā)控制方法，通過劃分分區(qū)，每個分區(qū)分配一個線程專門負責這個分區(qū)的所有鎖操作，每個事務由其需要訪問的分區(qū)的線程來協(xié)作進行鎖操作；R. Johnson等[35]也發(fā)現(xiàn)傳統(tǒng)的鎖管理器的開銷比較大，他們重新設計了鎖管理器，通過減少鎖操作的次數(shù)來減少鎖開銷；Ren Kun 等[36]研究指出：鎖管理器的操作都是內(nèi)存操作，對于以磁盤為存儲介質(zhì)的數(shù)據(jù)庫系統(tǒng)來說，這些內(nèi)存操作的開銷很小，然而對于內(nèi)存數(shù)據(jù)庫來說，其操作開銷顯著增加，因此其研究了一種針對于內(nèi)存數(shù)據(jù)庫的輕量級鎖機制技術VLL，實驗結(jié)果表明此機制可以顯著地減少鎖開銷.

總體來說，很多研究表明，最常用的基于鎖的并發(fā)控制方法其鎖開銷相對于內(nèi)存數(shù)據(jù)庫比較大，而Heckton[33]、NuoDB[37]、SAP HANA[38-40]等使用的基于多版本的并發(fā)控制方法雖然可以避免鎖開銷，但卻需要額外的內(nèi)存來保存數(shù)據(jù)的多個版本，并且需要額外的操作來管理維護多個版本. 還有一些系統(tǒng)如Google的Spanner[41]、F1[42]等適用的是樂觀的并發(fā)控制方法，沒有以上提到的各種開銷，但需要額外的驗證步驟，可能會導致事務重啟，尤其在沖突率比較高的場景下. 因此針對內(nèi)存數(shù)據(jù)庫的特點，非常有必要研究新型的并發(fā)控制方法，這也是未來的一個研究熱點和挑戰(zhàn).

2.2 針對多核的并發(fā)控制方法研究

計算機硬件的另一個發(fā)展特點是CPU上的核越來越多. 因此近些年，針對于多核環(huán)境下的數(shù)據(jù)庫系統(tǒng)研究得到了廣泛關注. 本小節(jié)主要關注針對多核的并發(fā)控制方法研究. Hyungsoo Jung等[43]針對傳統(tǒng)鎖管理器的并發(fā)控制方法在多核環(huán)境下的可擴展性不佳的問題，提出了一種可擴展的鎖管理器設計，通過使用同步原語操作，在MySQL源代碼上進行修改，實驗表明此策略顯著提高了鎖管理器的可擴展性. Takashi Horikawa[44]同樣發(fā)現(xiàn)了傳統(tǒng)的數(shù)據(jù)庫設計在多核環(huán)境下的可擴展性問題，并重新設計了數(shù)據(jù)庫的很多數(shù)據(jù)結(jié)構(gòu)，主要提出和設計了Latch-Free的數(shù)據(jù)結(jié)構(gòu)，實驗結(jié)果表明此設計顯著提高了數(shù)據(jù)庫的并發(fā)性. Stephen Lyle Tu[45]和Hatem A. Mahmoud[46]等研究了新型硬件環(huán)境下的并發(fā)控制方法，提出了針對內(nèi)存環(huán)境下高效的樂觀的并發(fā)控制方法，同時此并發(fā)控制方法在多核環(huán)境下的可擴展性也非常好. Yu Xiangyao等[47]詳細測試了傳統(tǒng)的各種并發(fā)控制方法在多核環(huán)境下的性能，在Intel的仿真器上完成實驗，仿真測試到1 024個CPU Core，其實驗結(jié)果如圖2，總結(jié)得出當前所有的并發(fā)控制方法在多核環(huán)境下的可擴展性比較差，大多數(shù)并發(fā)控制方法在大于8個Core的時候總吞吐量沒有隨著CPU Core的增加而增加. 因此非常有必要研究針對于多核環(huán)境下數(shù)據(jù)庫系統(tǒng)設計策略，尤其是并發(fā)控制策略.

圖2 各種并發(fā)控制方法在多核環(huán)境下的性能

2.3 內(nèi)存數(shù)據(jù)庫支持磁盤、NVM等存儲介質(zhì)的研究

內(nèi)存技術雖然發(fā)展很快，但相比于磁盤，內(nèi)存的容量還是有限，在很多場景下可能會出現(xiàn)數(shù)據(jù)庫大小大于內(nèi)存容量的情形. 在這種情況下，內(nèi)存數(shù)據(jù)庫系統(tǒng)還需要支持磁盤存儲，使一部分數(shù)據(jù)存儲在磁盤中. 微軟的Per-Ake Larson等[48]研究了如果數(shù)據(jù)量超過內(nèi)存大小，需要把一些“冷”數(shù)據(jù)轉(zhuǎn)移到磁盤中，利用數(shù)據(jù)挖掘的算法分析“冷熱”數(shù)據(jù)，從而設計出了高效的數(shù)據(jù)替換算法來置換“冷”數(shù)據(jù)至磁盤中，并把此算法應用到了Heckton數(shù)據(jù)庫中. 在H-Store系統(tǒng)中，也進行了這方面的研究. 布朗大學的J DeBrabant等人研究了Anti-Caching策略[49]，同樣是把一些“冷”數(shù)據(jù)在磁盤中保存，和傳統(tǒng)的緩存策略相反，H-Store系統(tǒng)中內(nèi)存作為主存，磁盤作為輔助存儲，和傳統(tǒng)的緩存策略的另一個不同點是所有數(shù)據(jù)要么保存在內(nèi)存中，要么保存在磁盤中，僅僅保存一份,從而減少了維護數(shù)據(jù)一致性的復雜度. 其基本思想是當遇到需要訪問磁盤的事務的時候，延遲執(zhí)行此事務而在后臺進行讀磁盤操作，當所需元組都在內(nèi)存中的時候再執(zhí)行此事務. Thomson等[50]針對確定性數(shù)據(jù)庫系統(tǒng)提出了Prefetch策略來支持磁盤存儲，基本思想和Anti-Caching比較類似，也是延遲執(zhí)行需要訪問磁盤的事務.

近年來，非易失內(nèi)存(NVM)技術越來越成熟[51]，NVM存儲可以獲得內(nèi)存的讀寫性能，但同時也可以獲得類似于SSD的數(shù)據(jù)持久性保存功能. 所以如果使用NVM作為數(shù)據(jù)庫的存儲介質(zhì)，必將會使得數(shù)據(jù)庫系統(tǒng)的很多模塊設計發(fā)生變化，將會引出很多非常有研究價值的研究課題，例如如何組織數(shù)據(jù)庫存儲的層次關系、如何維護內(nèi)存和NVM存儲的緩存關系、如何設計基于NVM的并發(fā)控制方法等等. Brown、CMU、MIT和Intel合作的研究，在這方面進行了前沿研究[52]，在Intel提供的NVM仿真器上進行實驗(仿真NVM的讀寫延遲分別是內(nèi)存的5倍和10倍)，測試了數(shù)據(jù)庫系統(tǒng)運行在NVM上的情況. 主要測試了兩種數(shù)據(jù)庫構(gòu)架：① 主要存儲和輔助存儲都使用NVM；②主要存儲使用內(nèi)存，輔助存儲采用NVM.

因此研究內(nèi)存數(shù)據(jù)庫系統(tǒng)支持磁盤存儲以及NVM等新型存儲器件，也是新型OLTP數(shù)據(jù)庫系統(tǒng)的關鍵技術及挑戰(zhàn).

2.4 內(nèi)存數(shù)據(jù)庫系統(tǒng)的恢復機制研究

ARIES算法[7]被認為是數(shù)據(jù)庫恢復的一個經(jīng)典算法，別的很多數(shù)據(jù)庫恢復機制都是和ARIES類似或基于ARIES修改的改進算法. 近些年，針對內(nèi)存數(shù)據(jù)庫系統(tǒng)的恢復機制得到了很多學者的研究. 康奈爾大學的Tuan Cao等[53]研究針對于內(nèi)存數(shù)據(jù)庫的頻繁更新應用,提出了一種高效Checkpoint恢復算法以保證數(shù)據(jù)的持久性. Levy等[54]針對內(nèi)存數(shù)據(jù)庫研究了一種增量的恢復算法，通過獨立的恢復數(shù)據(jù)庫的頁，因此可以并發(fā)的進行恢復. D.Lomet等[55]提出了邏輯日志的概念，通過應用邏輯日志而非物理日志來進行數(shù)據(jù)庫的恢復. Malviya等[56]研究了針對內(nèi)存數(shù)據(jù)庫的輕量級的數(shù)據(jù)恢復機制command logging，也是應用了邏輯日志的概念. 其基本思想是在日志中僅僅保存事務本身，而不保存事務所涉及的元組更改前和更改后的狀態(tài)，并和傳統(tǒng)的ARIES-style的write-ahead logging并行對比. 實驗結(jié)果表明這種恢復機制的開銷更小，適合內(nèi)存數(shù)據(jù)庫系統(tǒng). Calvin[50]研究了針對確定性數(shù)據(jù)庫框架下的數(shù)據(jù)恢復機制，提出了一種高效的Checkpoint策略，即數(shù)據(jù)恢復不需要日志機制，僅僅需要在某個時刻的Checkpoint上進行重新執(zhí)行事務操作即可.因此也非常有必要研究針對內(nèi)存數(shù)據(jù)庫系統(tǒng)的恢復機制.

3 新型分布式數(shù)據(jù)庫系統(tǒng)設計的關鍵技術及挑戰(zhàn)

由于待處理數(shù)據(jù)量的快速增長以及應用對事務高吞吐量的要求，單機數(shù)據(jù)庫已經(jīng)不能滿足需求，分布式數(shù)據(jù)庫是應對上述挑戰(zhàn)的可行方式[57-58]. 本小節(jié)主要討論分布式數(shù)據(jù)庫系統(tǒng)設計中所涉及的關鍵技術及挑戰(zhàn)，主要包括分布式事務處理策略和副本一致性策略.

3.1 CAP及PACELC定理介紹

在研究和設計系分布式數(shù)據(jù)庫系統(tǒng)框架的時候主要參考CAP理論和PACELC理論，因此本小節(jié)主要介紹下CAP及PACELC理論.

首先介紹分布式系統(tǒng)中的一個重要的理論：CAP理論[59]. 很多分布式數(shù)據(jù)庫系統(tǒng)的設計都是參考著名的CAP理論. 1998年，Eric Brewer教授提出了著名的CAP理論，后來Seth Gilbert和Nancy lynch兩人證明了CAP理論的正確性. 簡單地說，CAP(Consistency(一致性)，Availability(可用性)，Partition tolerance(分區(qū)容錯性))理論表明：一個分布式系統(tǒng)不可能同時滿足一致性，可用性和分區(qū)容錯性這三個需求，最多只能同時滿足其中的兩個. 因此會出現(xiàn)AP(滿足可用性和分區(qū)容錯性，而不滿足一致性)，CA(滿足一致性和可用性而不滿足分區(qū)容錯性)以及CP(滿足一致性和分區(qū)容錯性而不滿足可用性)系統(tǒng).

耶魯大學學者Daniel Abadi教授對CAP理論做了補充，提出了PACELC理論[60]，即如果考慮分區(qū)容錯性，和CAP理論一樣，必須在可用性和一致性之間進行權(quán)衡；如果不考慮分區(qū)容錯性，必須在延遲(Latency)和一致性之間來權(quán)衡. PACELC理論主要是考慮到了如果不會出現(xiàn)分區(qū)錯誤的情況下，系統(tǒng)一直是可用的，所以系統(tǒng)的設計不需要考慮可用性，但這種情況下保持一致性又會增加事務請求延遲. 考慮到硬件和基礎設施越來越好，分區(qū)容錯會變得很少. 因此PACELC引出了一個重要的權(quán)衡，即必須在延遲和一致性之間來權(quán)衡，有些系統(tǒng)為了獲得很強的一致性，但增加了事務請求的延遲，有些系統(tǒng)為了獲得很小的系統(tǒng)延遲而犧牲了一致性.

3.2 分布式事務處理策略

分布式事務的處理策略最早在System R*[57]系統(tǒng)上實現(xiàn)，后面的商用或?qū)W術界的數(shù)據(jù)庫系統(tǒng)基本都是參照或繼承System R*的處理策略. 主要的處理策略包括：為了保證分布式事務的原子性，需要執(zhí)行兩階段提交協(xié)議(2PC)；為了保證隔離性，事務在執(zhí)行兩階段提交協(xié)議期間必須保持加鎖狀態(tài),即執(zhí)行兩階段加鎖協(xié)議(2PL).

相關研究表明[50,61]，在執(zhí)行兩階段提交協(xié)議期間加鎖所帶來的問題是：由于兩階段提交協(xié)議需要多次網(wǎng)絡信息傳輸，因此執(zhí)行兩階段提交協(xié)議的時間要比事務在本地的執(zhí)行時間要長，而加鎖時間的增長大幅增加了事務的沖突率，特別是對于一些熱門的數(shù)據(jù)進行加鎖，導致吞吐量的嚴重下降；同時也會增加分布式死鎖的概率，檢測和處理分布式死鎖同樣也會嚴重影響吞吐量. 雖然有一些并發(fā)控制協(xié)議不使用加鎖協(xié)議，而使用樂觀的并發(fā)控制協(xié)議或多版本控制協(xié)議(MVCC)，但事務的沖突率增加依然會導致事務回滾的概率增大從而使吞吐量嚴重下降.

可擴展性(Scalabiliy)是指當數(shù)據(jù)庫系統(tǒng)要處理更多的數(shù)據(jù)量和更高的事務吞吐量的時候，可以通過增加機器的線性擴展機制來達到要求. 近年來，大數(shù)據(jù)環(huán)境應用對事務吞吐量的要求越來越高，所以對系統(tǒng)可擴展性提出了更高的要求. 由于分布式系統(tǒng)中對于分布式事務ACID屬性的支持比較困難，相關研究表明保持事務特別是分布式事務的ACID屬性是限制分布式數(shù)據(jù)庫可擴展性的主要原因[50,61].

分布式數(shù)據(jù)庫系統(tǒng)的一個設計趨勢是為了獲得更好的線性可擴展性，減少或者不支持事務ACID屬性. 一些系統(tǒng)包括Amazon的Dynamo[62]、MongoDB[63]、CouchDB[64]以及Cassandra系統(tǒng)[65]等不支持事務ACID屬性; 另一些系統(tǒng)僅僅對事務ACID屬性提供有限制的支持，例如僅支持單行或單分區(qū)的事務ACID屬性，而不支持跨行或者跨分區(qū)的事務ACID實行，這些系統(tǒng)包括Google 的Bigtable[66]、Megastore[67]、微軟的Azure[68]以及Oracle的NoSQL[69]等系統(tǒng). 這些系統(tǒng)不支持事務ACID的最主要原因是為了獲得很好的線性可擴展性. 減少對事務ACID屬性的支持可以降低高可擴展性的分布式數(shù)據(jù)庫的設計難度，然而卻把保證事務ACID屬性的任務留給了上層應用程序員，極大增加了代碼的復雜度，同時延緩了應用開發(fā)的進度. 而且事務的ACID屬性是數(shù)據(jù)庫領域的一個重要概念，數(shù)據(jù)庫幾十年的發(fā)展也事實證明了保證事務的ACID屬性的重要性.

另一些最新的系統(tǒng)例如H-Store、HyPer、VoltDB等新型內(nèi)存數(shù)據(jù)庫系統(tǒng)，支持強的事務ACID屬性，采取的是在一個分區(qū)中單線程順序執(zhí)行事務的策略，對于大多數(shù)事務是單分區(qū)事務的場景下，可擴展性非常好，可以獲得很高的吞吐量，然而在分布式事務比較多的場景下，吞吐量較低，因為當處理分布式事務的時候，限制了別的事務的并發(fā)執(zhí)行. 因此這些系統(tǒng)只適用于上層應用容易分區(qū)的業(yè)務場景.

綜上所述，在設計新型的分布式數(shù)據(jù)庫系統(tǒng)的時候，需要研究如何在保證事務的ACID屬性的同時可以獲得很好的線性可擴展性.

3.3 分布式數(shù)據(jù)庫系統(tǒng)副本一致性研究

大多數(shù)數(shù)據(jù)庫系統(tǒng)選擇采取多副本策略，即一份數(shù)據(jù)有多個副本，具體實現(xiàn)通常為在同一物理位置和不同的物理位置放置多個副本，這樣的好處是：首先可以確保數(shù)據(jù)庫系統(tǒng)的安全和容錯性，例如某個物理位置的副本發(fā)生錯誤，可以從別的物理位置的副本進行拷貝恢復；其次多副本策略增加了數(shù)據(jù)庫系統(tǒng)的性能和吞吐量，例如只讀事務可以在任何一個副本上執(zhí)行，實現(xiàn)了任務分流，提高了系統(tǒng)的吞吐量和性能. 然而如何保證副本間的一致性是一個研究熱點.

由于很多分布式數(shù)據(jù)庫系統(tǒng)的設計是參照CAP理論，最常見的一個權(quán)衡就是在允許分區(qū)容錯性的基礎上，在高可用性和多副本一致性之間進行權(quán)衡. 部分系統(tǒng)為了保證24/7的高可用性，甚至在出現(xiàn)網(wǎng)絡或分區(qū)錯誤的情況下，依然要保證高可用性，然而卻犧牲了多副本間的一致性，提供最終一致性(eventually consistency)或類似的弱一致性級別[70]，即屬于CAP理論的AP(滿足分區(qū)容錯性和可用性，而不滿足一致性)系統(tǒng). 這些系統(tǒng)包括Dynamo[62]、SimpleDB[71]、Cassandra[65]、Voldemort[72]、Riak[73]以及PNUTS[74]. 但是近些年，這個趨勢有所改變，很多數(shù)據(jù)庫系統(tǒng)的設計保證了副本間的強一致性，根據(jù)PACELC理論，強一致性策略增加了事務延遲，這些系統(tǒng)采取這種設計策略是因為網(wǎng)絡傳輸?shù)然A構(gòu)架設施的不斷改善減少了網(wǎng)絡延遲(Latency)，降低了網(wǎng)絡錯誤的概率，因此即使為了獲得副本間的強一致性而使得事務延遲增加，但事務延遲也在可接受的范圍之內(nèi). 這些系統(tǒng)包括Google的Megastore[67]、F1(Spanner)[41,42]、IBM的Spinnaker系統(tǒng)[75]等，這些系統(tǒng)通過Paxos協(xié)議[76,77]來保證副本間的強一致性.

因此，在設計新型的分布式數(shù)據(jù)庫系統(tǒng)的時候，需要研究如何保證副本間的一致性策略.

4 新型的確定性事務執(zhí)行策略研究

事務執(zhí)行策略是OLTP數(shù)據(jù)庫系統(tǒng)中的一個重要研究方向. 近些年，隨著內(nèi)存數(shù)據(jù)庫的普及以及事務執(zhí)行特點的變化，確定性事務執(zhí)行策略這種新型的事務執(zhí)行策略得到了研究者的廣泛關注.

4.1 基本原理及相關研究

Thomson等[50,78]提出了確定性事務執(zhí)行策略的概念，是指在數(shù)據(jù)庫系統(tǒng)開始執(zhí)行事務之前，提前指定事務的執(zhí)行順序，并發(fā)執(zhí)行事務的結(jié)果要等價于這個提前制定的事務執(zhí)行順序. 和傳統(tǒng)的可串行化理論的區(qū)別是：可串行化理論要求事務并發(fā)執(zhí)行后的狀態(tài)等價于某一種(而不是事先確定的一種)事務串行執(zhí)行后的狀態(tài)，因此傳統(tǒng)的事務執(zhí)行策略是非確定的.

近年來，很多系統(tǒng)實現(xiàn)了確定性事務執(zhí)行策略或接近于確定性的事務執(zhí)行策略. Postgres-R[79]提出了一種復制協(xié)議來保證多個副本間的一致性，按照此復制協(xié)議，首先對事務進行排序，然后整個系統(tǒng)按照這個次序?qū)κ聞者M行加鎖及執(zhí)行，然而這種協(xié)議需要運行高開銷的Group Communication協(xié)議來協(xié)調(diào)事務的執(zhí)行，同時此協(xié)議在事務執(zhí)行的過程中可能會出現(xiàn)事務回滾的現(xiàn)象，因此也不是嚴格的確定性事務執(zhí)行策略. Ricardo Jimenez-Peris等[80]提出了一種基于中間件的確定性執(zhí)行方案，此方案設計了一種確定性的多線程執(zhí)行器，即各個副本對其上的每個線程進行相同的調(diào)度，可以獲得多個副本間的強一致性，但是此種策略嚴格規(guī)定了線程在各個副本上的調(diào)度必須一致，極大限制了調(diào)度的靈活性. H-Store和VoltDB是按照處理器核心進行分區(qū)的內(nèi)存數(shù)據(jù)庫，各個事務在各個分區(qū)上順序執(zhí)行，而不采用并發(fā)控制方法，也是一種接近于確定性事務執(zhí)行的策略，但不是嚴格的確定性事務執(zhí)行策略，因為也可能會產(chǎn)生事務回滾. Garcia-Molina和Salem[81]提出在內(nèi)存數(shù)據(jù)庫環(huán)境下，沒有磁盤I/O的瓶頸，大多數(shù)情況下不采用加鎖等并發(fā)控制機制，而是事務完全的順序執(zhí)行可以獲得最高的性能，但他們使用的仍然是傳統(tǒng)的非確定性事務執(zhí)行策略，因此也不是嚴格的確定性事務執(zhí)行策略.

4.2 確定性事務執(zhí)行策略的分析與評價

Ren Kun等[82]通過理論分析與實驗驗證對確定性事務執(zhí)行策略進行了客觀的分析與評價，總結(jié)其相對于傳統(tǒng)的非確定性事務執(zhí)行策略的優(yōu)缺點. 研究結(jié)果表明確定性事務執(zhí)行策略易獲得數(shù)據(jù)庫副本間的強一致性、可避免死鎖和提交協(xié)議、具有更好的可擴展性和更高的吞吐量等優(yōu)點；然而此策略所帶來的缺點是喪失了事務執(zhí)行的靈活性、限制了并發(fā)性以及增加了事務延遲等. 研究成果為數(shù)據(jù)庫用戶在不同應用場景下選擇不同的事務執(zhí)行策略提供了更多的參考. 表1是根據(jù)確定性事務執(zhí)行策略的特點來歸納其優(yōu)缺點.

表1 確定性事務執(zhí)行策略的優(yōu)缺點

5 總 結(jié)

針對新型應用需求和現(xiàn)代計算機硬件的發(fā)展特點，以及對分布式數(shù)據(jù)庫系統(tǒng)可擴展性和一致性的新要求，有必要重新研究和設計新型OLTP數(shù)據(jù)庫系統(tǒng). 本文研究和分析了設計新型數(shù)據(jù)庫系統(tǒng)所涉及的關鍵技術，重點研究了內(nèi)存、多核、非易失內(nèi)存等條件下數(shù)據(jù)庫系統(tǒng)設計問題，以及分布式事務處理、多副本一致性等問題，最后介紹了確定性的事務執(zhí)行策略.

[1] CHAMBERLIN D D, ASTRAHAN M M, BLASGEN M W, et al.A history and evaluation of System R[J]. CommunicationACM, 1981(24):632-646.

[2] GRAY J N, LORIE R A, PUTZOLU G R, et al. Modelling in data base management systems [J]. Chapter Granularity of locks and degrees of consistency in a shared data base,1976：365-393.

[3] STONEBRAKER M, MADDEN S, ABADI D J, S, et al. The end of an architectural era: (it’s time for a complete rewrite) [C]//VLDB, 2007：1150-1160,

[4] HARIZOPOULOS S, ABADI D J, MADDEN S, et al. OLTP through the looking glass, and what we found there [C]//SIGMOD,2008: 981-992.

[5] JUNG H, HAN H, FEKETE A D, et al. A scalable lock manager for multicores [C]//SIGMOD, 2013.

[6] BERNSTEIN P A, NEWCOMER E. Principles of Transaction Processing [M]. San Francisco: Morgan Kaufmann Publishers, 2009.

[7] BERNSTEIN P A, HADZILACOS V, GOODMAN N. Concurrency Control and Recovery in DatabaseSystems, chapter 7 [M]. Boston: Addison Wesley Publishing Company, 1987.

[8] GRAY J. Concurrency Control and Recovery in Database Systems [M].Berlin: Springer, 1978：393-481.

[9] BERNSTEIN P A, GOODMAN N. Concurrency control in distributed database systems [J]. ACM Computer.Survey, 1981，13(2):185-221.

[10] O’NEIL P E.The escrow transactional method [J]. ACM Trans Database Syst, 1986(11): 405-430.

[11] SHOUP R, PRITCHETT D. The ebay architecture [R]. SD Forum, November 2006.

[12] SOBEL J. Scaling Out (Facebook) [R]. http://on.fb.me/p7i7eK, April 2006.

[13] KING R P, HALIM N, GARCIA-MOLINA H, et al. Management of a remote backup copy for disaster recovery[J]. ACM Trans Database Syst, 1991, 16(2): 338-368.

[14] POLYZOIS C A, GARC′IA-MOLINA H. Evaluation of remote backup algorithms for transactionprocessing systems [J]. ACM Trans Database Syst, 1994, 19(3): 423-449.

[15] KRIKELLAS K, ELNIKETY S, VAGENA Z, et al. Strongly consistent replication for a bargain [C]//ICDE, 2010, 52-63.

[16] PLATTNER C, ALONSO G. Ganymed: scalable replication for transactional web applications [C]//Middleware, 2004: 155-174.

[17] VOGELS W. Eventually consistent [J]. Queue, 2008, 6: 14-19.

[18] ASTRAHAN M M, BLASGEN M W, CHAMBERLIN D D, et al. System r: relational approach to database management [J]. ACM Trans Database Syst, 1976, 1(2): 97-137.

[19] STONEBRAKER M, HELD G, WONG E, et al. The design and implementation of INGRES [J]. ACM Trans Database Syst, 1976, 1(3):189-222.

[20] COPELAND G, FRANKLIN M, WEIKUM G. Uniform object management [C]//EDBT, 1990(416): 253-268.

[21] GRAEFE G. The five-minute rule twenty years later, and how flash memory changes the rules [C]. DaMoN, 2007, 6:1-9.

[22] BERNSTEIN P A, GOODMAN N. Multiversion concurrency control - theory and algorithms [J]. ACM Trans. Database Syst, 1983, 8(4): 465-483.

[23] CHAN A, FOX S, LIN K, et al.The implementation of an integrated concurrency control and recovery scheme [C]//SIGMOD, 1982, 184-191.

[24] HELLAND P, SAMMER H, LYON J, et al. Group commit timers and high volume transaction systems [C]//Proceedings of the 2nd International Workshop on High Performance Transaction Systems. 1989, 301-329.

[25] HELLERSTEIN J M, STONEBRAKER M. Readings in Database Systems [M].San Francisco: Morgan Kaufmann Publisher, 1998: 238-243.

[26] MOHAN C, HADERLE D, LINDSAY B, et al. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging [J]. ACM Trans. Database Syst, 1992, 17(1):94-162.

[27] O’NEIL P, CHENG E, GAWLICK D, et al. The log-structured merge-tree (LSM-tree) [J].Acta Inf, 1996, 33(4): 351-385.

[28] JOHNSON R, PANDIS I, HARDAVELLAS N, et al. Shore-mt:a scalable storage manager for the multicore era [C]//EDBT, 2009.

[29] The Transaction Processing Council. TPC-C Benchmark (Revision 5.9.0) [R].http://www.tpc.org/tpcc/spec/tpcc_current.pdf, June 2007.

[30] KALLMAN R, KIMURA H, NATKINS J, et al. H-Store: a high-performance, distributed main memory transaction processing system [C]//VLDB Endow. 2008, 1(2): 1496-1499.

[31] H-STORE [J/OL].http://hstore.cs.brown.edu.

[32] KEMPER A, NEUMANN T. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots [C]//ICDE, 2011, 195-206.

[33] DIACONU C, FREEDMAN C, ISMERT E, et al. Hekaton: Sql server’s memory-optimized oltp engine [C]//SIGMOD, 2013: 1243-1254.

[34] PANDIS I, JOHNSON R, HARDAVELLAS N. Data-oriented transaction execution [J]. PVLDB, 2010, 3(1): 928-939.

[35] JOHNSON R etc. Improving oltp scalability using speculative lock inheritance [C]//VLDB, 2009.

[36] REN K, THOMSON A, ABADI D J. Lightweight locking for main memory database systems [J]. PVLDB, 2013: 145-156.

[37] NUODB [J/OL].http://www.nuodb.com.

[38] FARBER F, CHA S K, PRIMSCH J, et al. SAP HANA database: data management for modern business applications [J]. SIGMOD Rec, 2012, 40(4): 45-51.

[39] LEE J, MUEHLE M, MAY N, et al. High-performance transaction processing in SAP HANA [J]. IEEE Data Eng Bull, 2013, 36(2): 28-33.

[40] SIKKA V, FARBER F, LEHNER W, et al. Efficient transaction processing in SAP HANA database: the end of a column store myth [C]//SIGMOD, 2012: 731-742.

[41] CORBETT J C, DEAN J, EPSTEIN M, et al. Spanner: Google’s globally-distributed database [C]//OSDI, 2012.

[42] SHUTE J, VINGRALEK R, SAMWEL B, et al. F1: A distributed sql database that scales [C]//VLDB, 2013.

[43] JUNG H, HAN H, FEKETE A D, et al. A scalable lock manager for multicores [C]. SIGMOD 2013.

[44] HORIKAWA T. Latch-free data structures for DBMS:design, implementation,and evaluation [C]//SIGMOD, 2013.

[45] STEPHEN T, ZHENG W T, KOHLER E, et al. Speedy transactions in multicore in-memory databases [C]//SOSP, 2013.

[46] MAHMOUD H A, ARORA V, NAWAB F, et al. MaaT: Effective and scalable coordination of distributed transactions in the cloud [J]. PVLDB, 2014, 7.

[47] YU X Y, BEZERRA G, STONEBRAKER M, et al. Concurrency control in the many-core era: scalability and limitations [R]. Blog:http://istc-bigdata.org/index.php/concurrency-control-in-the-many-core-era-scalability-and-limitations/.

[48] LEVANDOSKI J J, LARSON P A, STOICA R. Identifying hotand cold data in main-memory databases [C]//ICDE, 2013: 26-37.

[49] DEBRABANT J, PAVLO A, TU S, et al. Anti-Caching: A new approach to database management system architecture [J]. PVLDB, 2013, 6.

[50] THOMSON A, DIAMOND T, WENG S C, et al. Calvin: fast distributed transactions for partitioned database systems [C]//SIGMOD, 2012.

[51] ROBERTS D, CHANG J, RANGANATHAN P, et al. Is storage hierarchy dead? co-located compute-storage nvram-based architectures for data-centric workloads [R]. Technical Report HPL-2010-119, HP Labs, 2010.

[52] ARULRAJ J, DEBRABANT J, PAVLO A, et al. OLTP database systems for non-volatile memory [R]. Blog: http://istc-bigdata.org/index.php/oltp-database-systems-for-non-volatile-memory/.

[53] CAO T, VAZSALLES M, SOWELL B, et al. Fast checkpoint recovery algorithms for frequently consistent applications [C]//Proceedings of the 2011 international conference on Management of data. SIGMOD ’11, 2011: 265-276.

[54] LEVY E, SILBERSCHATZ A. Incremental recovery in main memory database systems [J]. IEEE Trans on Knowl and Data Eng, 1992, 4: 529-540.

[55] LOMET D, TZOUMAS K, ZWILLING M. Implementing performance competitive logical recovery [J]. Proc VLDB Endow , 2011, 4: 430-439.

[56] MALVIYA N, WEISBERG A, MADDEN S, et al. Rethinking main memory OLTP recovery [C]//Data Engineering (ICDE). 2014 IEEE 30th International Conference on, 2014: 604-615.

[57] DEWITT D, GRAY J. Parallel database systems: the future of high performance database systems [J].Commun ACM, 1992, 35(6): 85-98.

[58] MOHAN C, LINDSAY B, OBERMARCK R. Transaction management in the r*distributed databasemanagement system [J]. ACM Trans Database Syst, 1986, 11(4): 378-396.

[59] GILBERT S, LYNCH N A. Perspectives on the CAP theorem [J]. Computer, 2012, 45(2): 30-36.

[60] ABADI D J. Consistency tradeoffs in modern distributed database system design: CAP is only part of the story [J]. IEEE Computer, 2012, 45(2).

[61] Thomson A, DIAMEND T, WENG SH CH, REN K, et al. Fast distributed transactions and strongly consistent replication for OLTP database systems [J]. ACM Transactions on Database Systems (TODS)，2013，39(4):1337-1371.

[62] DECANDIA G, HASTORUN D, JAMPANI M, et al. Dynamo: amazon’s highly available key-value store [J]. SIGOPS Oper Syst Rev, 2007(41): 205-220.

[63] MONGODB [J/OL].http://mongodb.org.

[64] ANDERSON J C, LEHNARDT J, SLATER N. CouchDB: the definitive guide [J]. CouchDB Homepage, 2010.

[65] LAKSHMAN A, MALIK P. Cassandra: a decentralized structured storage system [J]. SIGOPS Oper Syst Rev, 2010, 44(2): 35-40.

[66] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: A distributed storage system for structured data [J]. ACM Trans Comput Syst, 2008, 26(4):1-26.

[67] BAKER J, BOND C, CORBETT J, et al. Megastore: Providing scalable, highly available storage for interactive services [C]//CIDR, 2011.

[68] CAMPBELL D, KAKIVAYA G, ELLIS N. Extreme scale with full sql language support in microsoftsql azure [C]//SIGMOD, 2010.

[69] SELTZER M. Oracle nosql database [R]. Oracle White Paper, 2011.

[70] DAVIDSON S B, GARCIA-MOLINA H, SKEEN D. Consistency in a partitioned network: a survey [J]. ACM Computing Surveys , 1985, 17(3): 341-370.

[71] Amazon simpledb [J/OL].http://aws.amazon.com/simpledb/.

[72] Project voldemort [J/OL]. http://project-voldemort.com/.

[73] Riak [J/OL].http://wiki.basho.com/riak.html.

[74] COOPER B F, RAMAKRISHNAN R, SRIVASTAVA U, et al. Pnuts: Yahoo!’s hosted data serving platform [C]//Proc VLDB Endow. 2008, 1(2): 1277-1288.

[75] RAO J, SHEKITA E J, TATA S. Using paxos to build a scalable, consistent, and highly available datastore [C]//VLDB, 2011.

[76] LAMPORT L.The part-time parliament [J]. ACM Trans on Comput Syst, 1998.

[77] LAMPORT L. Paxos made simple [J]. ACM SIGACT News, 2001.

[78] THOMSON A, ABADI D J. The case for determinism in database systems [J]. PVLDB, 2010, 3(1).

[79] KEMME B, ALONSO G. Don't be lazy, be consistent:Postgres-r, a new way to implement database replication [C]//VLDB, 2000.

[80] JIMENEZ-PERIS R, PATINO-MARTINEZ P, AREVALO S. Deterministic scheduling for transactional multithreaded replicas [C]//IEEE SRDS, 2000.

[81] GARCIA-MOLINA H, SALEM K. Main memory database systems: An overview [J]. IEEE Transactions on Knowledge and Data Engineering, 1992: 4(6).

[82] REN K, THOMSON A, ABADI D.An evaluation of the advantages and disadvantages of deterministic database systems [J].40th International Conference on Very Large Data (VLDB 2014), 2014, 7: 821-832.

(責任編輯 李 藝)

Key techniques and challenges of designing new OLTP database systems

REN Kun, LI Zhan-huai

(DepartmentofComputerScience,NorthwesternPolytechnicalUniversity,Xi’An710129,China)

Traditional database systems were designed based on the hardware environment in 1970s. However, with the era of “Cloud Computing” and “Big Data”, On-Line Transaction Processing requires database systems to provide more transaction throughput and better scalability. Meanwhile, the development of Computer hardware, in particular memory and multiple CPU Cores offer new opportunity for database systems evolution. Therefore, researching and designing new distributed database systems becomes more and more crucial. This paper researched on the key techniques and challenges of designing new OLTP Database systems.

scalability; computer hardware; transaction processing； determinism

1000-5641(2014)05-0031-12

2014-06

國家“973”計劃課題(2012CB316203)；國家自然科學基金重點項目(61033007)

任堃，男，博士研究生，研究方向為分布式數(shù)據(jù)庫系統(tǒng)、事務處理. E-mail: renkun_nwpu@mail.nwpu.edu.cn.

李戰(zhàn)懷，男，教授，博士生導師，研究方向為數(shù)據(jù)管理技術. E-mail: lizhh@nwpu.edu.cn.

TP311

A

10.3969/j.issn.1000-5641.2014.05.003