基于存儲(chǔ)技術(shù)的數(shù)據(jù)庫(kù)建設(shè)研究

1存儲(chǔ)特性與存儲(chǔ)轉(zhuǎn)換隨著社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等新技術(shù)和應(yīng)用的快速發(fā)展，數(shù)據(jù)的大小和速度呈指數(shù)級(jí)增長(zhǎng)，大量數(shù)據(jù)處理給計(jì)算機(jī)系統(tǒng)帶來(lái)了巨大挑戰(zhàn)。作為主要存儲(chǔ)介質(zhì)的磁盤(pán)，它已成為人們無(wú)法滿足實(shí)際應(yīng)用對(duì)存儲(chǔ)帶寬的需求。在過(guò)去的幾十年里，cpu的處理速度幾乎提高了600倍，磁盤(pán)讀取速度僅提高了10倍。低存儲(chǔ)容量已經(jīng)成為制約系統(tǒng)性能提高的瓶頸。隨著多核、gpu等高性能處理器的出現(xiàn)，這種現(xiàn)象不可避免地會(huì)更加突出。由于磁盤(pán)本身的機(jī)械捕獲功能，很難顯著提高性能。數(shù)據(jù)采集系統(tǒng)需要新有效的高效存儲(chǔ)設(shè)備來(lái)提高存儲(chǔ)系統(tǒng)的性能。存儲(chǔ)內(nèi)存是一種完整的電子設(shè)備。通過(guò)電子電路讀取數(shù)據(jù)，具有非容易丟失、讀取速度快、抗疲勞耗、體積小等特點(diǎn)。現(xiàn)在廣泛應(yīng)用于嵌入式系統(tǒng)、航空航天、消費(fèi)電子等領(lǐng)域。閃存讀速度超過(guò)100萬(wàn)次。隨著生產(chǎn)技術(shù)的發(fā)展，存儲(chǔ)能力的能力不斷增強(qiáng)，應(yīng)用領(lǐng)域逐漸擴(kuò)展到與磁盤(pán)相關(guān)的高吞咽和密集訪問(wèn)的時(shí)代應(yīng)用環(huán)境。圖靈獎(jiǎng)的創(chuàng)始人格雷德（gryd）預(yù)測(cè)，“隨著磁盤(pán)取代磁帶，閃存將取代磁盤(pán)?！睌?shù)據(jù)庫(kù)是管理體系的重要技術(shù)?，F(xiàn)有的數(shù)據(jù)庫(kù)主要基于磁盤(pán)存儲(chǔ)進(jìn)行設(shè)計(jì)和優(yōu)化。雖然存儲(chǔ)與磁盤(pán)不同，但網(wǎng)絡(luò)系統(tǒng)不能完全穿透磁盤(pán)。在目前的管理制度領(lǐng)域，討論適合存儲(chǔ)特性的數(shù)據(jù)庫(kù)技術(shù)是當(dāng)今管理體系領(lǐng)域的研究熱點(diǎn)。本文第2節(jié)介紹閃存存儲(chǔ)特性、固態(tài)硬盤(pán)和閃存轉(zhuǎn)換層;第3節(jié)對(duì)閃存數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)進(jìn)行分析歸類(lèi);第4節(jié)介紹基于閃存的混合系統(tǒng)數(shù)據(jù)管理相關(guān)研究;第5節(jié)展望未來(lái)研究工作;第6節(jié)對(duì)全文做出總結(jié).2閃存盤(pán)2.1dd存儲(chǔ)sdp根據(jù)制作工藝,閃存存儲(chǔ)器可以分為NOR型和NAND型兩種.NOR型閃存可以按位進(jìn)行訪問(wèn),具有可靠性高、隨機(jī)讀取速度快的優(yōu)勢(shì),但擦除和寫(xiě)操作速度較慢、容量小,主要用于存儲(chǔ)可執(zhí)行的程序代碼.NAND閃存的容量大,適合進(jìn)行數(shù)據(jù)存儲(chǔ).根據(jù)芯片晶胞所能存儲(chǔ)的比特位數(shù),NAND閃存又可分為單級(jí)晶胞(SLC)和多級(jí)晶胞(MLC)兩類(lèi),SLC每單元存儲(chǔ)1個(gè)比特位,MLC每單元存儲(chǔ)多個(gè)比特位.文中提及的閃存設(shè)備若不是特別注明都是指NAND型閃存.2.2sd與存儲(chǔ)的性能對(duì)比一個(gè)NAND型閃存芯片通常由若干個(gè)塊組成,每個(gè)塊又由若干頁(yè)組成.例如,容量為1GB的三星K9WAG08U1A(1)閃存芯片包含8192個(gè)塊,每個(gè)塊由64個(gè)頁(yè)組成,每一個(gè)頁(yè)由數(shù)據(jù)區(qū)和備用區(qū)組成,2KB的數(shù)據(jù)區(qū)用于存儲(chǔ)用戶數(shù)據(jù),64B的備用區(qū)用來(lái)存儲(chǔ)校驗(yàn)、邏輯頁(yè)地址等信息.閃存具備讀、寫(xiě)和擦除3種操作,頁(yè)是閃存的基本讀寫(xiě)單位,重寫(xiě)數(shù)據(jù)前必須進(jìn)行擦除,擦除操作以塊為單位,執(zhí)行時(shí)間和能耗遠(yuǎn)高于讀寫(xiě)操作.在頁(yè)被擦除前,SLC型閃存可以對(duì)同一個(gè)數(shù)據(jù)頁(yè)進(jìn)行多次寫(xiě)操作,最小寫(xiě)單元為512個(gè)字節(jié).閃存芯片的讀寫(xiě)方式與磁盤(pán)截然不同,二者的I/O操作性能對(duì)比見(jiàn)表1.總的來(lái)說(shuō),閃存不同于磁盤(pán)的特性包括以下幾點(diǎn):(1)無(wú)機(jī)械延遲.作為一種純電子設(shè)備,閃存沒(méi)有機(jī)器延遲,隨機(jī)訪問(wèn)和順序訪問(wèn)的開(kāi)銷(xiāo)相當(dāng),具有很高的隨機(jī)讀性能;(2)讀寫(xiě)不對(duì)稱.閃存對(duì)不同類(lèi)型訪問(wèn)操作表現(xiàn)的性能差別很大.一般來(lái)說(shuō),讀速度很快,寫(xiě)入數(shù)據(jù)時(shí),因?yàn)樾枰ㄟ^(guò)加壓的方式對(duì)存儲(chǔ)單元進(jìn)行電子填充,所以速度較慢;(3)異位更新.與磁盤(pán)的原位更新不同,對(duì)閃存數(shù)據(jù)進(jìn)行重寫(xiě)需要先執(zhí)行擦除操作,即便是只更新數(shù)據(jù)塊中的一條數(shù)據(jù)也需要將整個(gè)塊擦除.頻繁的擦除操作會(huì)使系統(tǒng)性能顯著降低.因此,閃存設(shè)備在更新數(shù)據(jù)時(shí)并不會(huì)直接在原位進(jìn)行更新,而是先將原數(shù)據(jù)置為無(wú)效,然后把修改后的數(shù)據(jù)寫(xiě)到一個(gè)新的空閑頁(yè);(4)擦除次數(shù)有限.閃存芯片的塊擦除次數(shù)是有限制的.通常SLC閃存支持10萬(wàn)次擦除操作,MLC閃存數(shù)據(jù)存儲(chǔ)密度高,可擦除次數(shù)在1萬(wàn)次左右.超過(guò)一定擦除次數(shù)的閃存單元將不再可用;(5)低能耗.與磁盤(pán)相比,閃存的能耗更低,每GB讀數(shù)據(jù)能耗只有磁盤(pán)的2%,寫(xiě)操作能耗不足磁盤(pán)的30%.閃存的出現(xiàn)為建設(shè)綠色數(shù)據(jù)中心以及低能耗數(shù)據(jù)管理系統(tǒng)提供了有力支持.閃存有比磁盤(pán)更加復(fù)雜的硬件特性,傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)技術(shù)在閃存上并不適用,設(shè)計(jì)適用于閃存的結(jié)構(gòu)、算法和應(yīng)用是閃存數(shù)據(jù)管理必須要解決的一個(gè)重要問(wèn)題.2.3存儲(chǔ)模塊和存儲(chǔ)層基于閃存的固態(tài)硬盤(pán)(SolidStateDrive,SSD)由閃存芯片、控制器和閃存轉(zhuǎn)換層(FlashTranslationLayer,FTL)組成.它對(duì)外提供和磁盤(pán)相同的I/O接口,存儲(chǔ)性能遠(yuǎn)超過(guò)磁盤(pán).近十年來(lái)隨著閃存芯片容量的增加和價(jià)格的下降,集成了多塊閃存芯片的固態(tài)硬盤(pán)已經(jīng)被認(rèn)為是最有可能替代磁盤(pán)的新一代數(shù)據(jù)存儲(chǔ)載體.個(gè)人計(jì)算機(jī)、服務(wù)器和企業(yè)級(jí)數(shù)據(jù)管理中心大量使用固態(tài)硬盤(pán)來(lái)提高數(shù)據(jù)存儲(chǔ)性能(1)(2).為了屏蔽閃存與磁盤(pán)不同的操作特性,固態(tài)硬盤(pán)通過(guò)閃存轉(zhuǎn)換層為上層文件系統(tǒng)提供通用的讀寫(xiě)接口,系統(tǒng)應(yīng)用不需要任何修改便可直接在固態(tài)硬盤(pán)上運(yùn)行.閃存轉(zhuǎn)換層是封裝在閃存芯片和文件系統(tǒng)之間的一個(gè)軟件層,其結(jié)構(gòu)如圖1所示.閃存轉(zhuǎn)換層包括3個(gè)基本功能:閃存轉(zhuǎn)換層的Allocator模塊負(fù)責(zé)為I/O請(qǐng)求分配可用的空閑空間,解決閃存異位更新造成的地址變換問(wèn)題;閃存單元的擦除次數(shù)是有限制的,超過(guò)限定擦除次數(shù)的單元將成為磨損塊而無(wú)法使用.數(shù)據(jù)訪問(wèn)的不均衡性可能導(dǎo)致閃存局部存儲(chǔ)區(qū)因更新頻繁而變成磨損塊.閃存轉(zhuǎn)換層中的WearLeveler模塊采用數(shù)據(jù)遷移等方法平衡存儲(chǔ)單元的擦除次數(shù)實(shí)現(xiàn)閃存整體的損耗均衡;閃存轉(zhuǎn)換層的Cleaner模塊用于回收無(wú)效的舊數(shù)據(jù)頁(yè).垃圾回收首先選擇待回收的塊,把塊中有效的數(shù)據(jù)寫(xiě)入新的塊,然后擦除無(wú)效塊實(shí)現(xiàn)空間的循環(huán)再利用.3基于存儲(chǔ)的系統(tǒng)設(shè)計(jì)閃存有與磁盤(pán)完全不同的物理特性,用閃存直接替換磁盤(pán)進(jìn)行數(shù)據(jù)管理不能最大化發(fā)揮閃存的優(yōu)良性能,因此有必要設(shè)計(jì)基于閃存的數(shù)據(jù)庫(kù)系統(tǒng).本節(jié)首先闡述研究閃存數(shù)據(jù)庫(kù)系統(tǒng)的必要性,然后分別討論閃存數(shù)據(jù)庫(kù)系統(tǒng)研究的幾個(gè)關(guān)鍵技術(shù).3.1存儲(chǔ)特性對(duì)數(shù)據(jù)庫(kù)的影響為了對(duì)比閃存設(shè)備對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的影響,我們將PostgreSQL8.4.9數(shù)據(jù)庫(kù)系統(tǒng)遷移至固態(tài)硬盤(pán)并進(jìn)行TPC-C測(cè)試.測(cè)試環(huán)境:CPU為2DuoCPUE83002.8GHz,內(nèi)存2GB,緩沖區(qū)為400MB,操作系統(tǒng)為Ubuntu,操作系統(tǒng)和數(shù)據(jù)集分別安裝在兩塊80GBIntelSSD上,測(cè)試結(jié)果見(jiàn)表2.實(shí)驗(yàn)表明PostgreSQL在固態(tài)硬盤(pán)上的事務(wù)處理性能提高10倍左右,相比固態(tài)硬盤(pán)對(duì)磁盤(pán)百倍以上的讀寫(xiě)速度,數(shù)據(jù)庫(kù)系統(tǒng)顯然沒(méi)能充分發(fā)揮閃存優(yōu)良的存儲(chǔ)性能.文獻(xiàn)基于閃存對(duì)數(shù)據(jù)庫(kù)查詢處理性能進(jìn)行了測(cè)試,結(jié)果只提高了幾倍.造成這一現(xiàn)象的根本原因在于現(xiàn)有的數(shù)據(jù)庫(kù)系統(tǒng)都是基于磁盤(pán)設(shè)計(jì),直接運(yùn)行在閃存上不能充分發(fā)揮閃存的物理特性.以查詢優(yōu)化為例,磁盤(pán)隨機(jī)讀操作代價(jià)是順序讀的130倍,查詢優(yōu)化算法優(yōu)先選擇順序讀寫(xiě)來(lái)代替隨機(jī)讀操作,閃存寫(xiě)操作比讀操作的代價(jià)高,而其隨機(jī)讀代價(jià)只是順序讀的2.5倍,現(xiàn)有查詢優(yōu)化算法無(wú)法發(fā)揮其極佳的隨機(jī)讀性能.設(shè)計(jì)并實(shí)現(xiàn)適合閃存讀寫(xiě)特性的數(shù)據(jù)庫(kù)系統(tǒng)十分必要.目前IBM、Oracle和微軟等許多知名數(shù)據(jù)庫(kù)廠商都在它們的數(shù)據(jù)庫(kù)產(chǎn)品中添加了針對(duì)閃存的應(yīng)用(3)(4).閃存數(shù)據(jù)庫(kù)系統(tǒng)研究必須分析現(xiàn)有技術(shù)在閃存數(shù)據(jù)管理上的缺陷,從系統(tǒng)性和通用性等角度設(shè)計(jì)適合閃存特性的算法、結(jié)構(gòu)和應(yīng)用,以充分發(fā)揮閃存的性能優(yōu)勢(shì).基于此,我們提出閃存數(shù)據(jù)庫(kù)系統(tǒng)框架,如圖2所示.查詢處理應(yīng)該設(shè)計(jì)基于閃存的代價(jià)模型并對(duì)查詢編譯、查詢計(jì)劃生成、路徑選擇等環(huán)節(jié)進(jìn)行優(yōu)化;存儲(chǔ)和索引管理應(yīng)針對(duì)寫(xiě)前擦除特性對(duì)數(shù)據(jù)進(jìn)行有效組織,提高數(shù)據(jù)檢索的效率;緩沖區(qū)管理需要考慮閃存讀寫(xiě)不對(duì)稱等特性,在保證較高訪問(wèn)命中率的同時(shí)盡量減少對(duì)閃存的寫(xiě)操作;事務(wù)處理應(yīng)該發(fā)揮閃存高速隨機(jī)讀性能,在日志、恢復(fù)和并發(fā)控制處理過(guò)程中既能保證事務(wù)的ACID特性,又能細(xì)化并發(fā)粒度提高事務(wù)處理的吞吐量.緩沖區(qū)管理、索引技術(shù)、查詢處理、事務(wù)處理等是構(gòu)建閃存數(shù)據(jù)庫(kù)系統(tǒng)的關(guān)鍵技術(shù).3.2頁(yè)p的置換代價(jià)緩沖區(qū)是數(shù)據(jù)庫(kù)系統(tǒng)的核心組件,利用數(shù)據(jù)訪問(wèn)存在局部性特征將最近和經(jīng)常訪問(wèn)的數(shù)據(jù)存儲(chǔ)在內(nèi)存上,以快速響應(yīng)CPU的讀寫(xiě)請(qǐng)求.CPU發(fā)出對(duì)數(shù)據(jù)頁(yè)p的訪問(wèn)請(qǐng)求,緩沖區(qū)管理做如下處理:(1)查閱頁(yè)表判斷p是否在緩沖區(qū),若存在則訪問(wèn)命中,讀取p并執(zhí)行對(duì)該頁(yè)的操作;否則訪問(wèn)脫靶(缺頁(yè))執(zhí)行(2);(2)系統(tǒng)檢查緩沖區(qū)當(dāng)前可用空間,若有空間則為請(qǐng)求頁(yè)分配一個(gè)空閑頁(yè),然后從磁盤(pán)讀入頁(yè)p,執(zhí)行對(duì)p的操作,否則執(zhí)行(3);(3)由替換算法選擇一犧牲頁(yè)q置換出內(nèi)存,若q是修改頁(yè)(臟頁(yè)),則需寫(xiě)回外存,讀p進(jìn)內(nèi)存.在可用緩沖區(qū)大小確定的情況下,置換代價(jià)是衡量緩沖區(qū)算法性能的首要因素.頁(yè)p的置換代價(jià)可由式(1)來(lái)表示:Cost(p)=Pmiss×Cread+Pmiss×Pdirty×Cwrite(1)其中,Pmiss代表p脫靶的概率;Cread和Cwrite分別表示在外存上讀取和寫(xiě)入p的時(shí)間;Pdirty表示p為臟頁(yè)的概率.式(1)可轉(zhuǎn)換為式(2)其中ω表示對(duì)外存執(zhí)行寫(xiě)和讀操作的代價(jià)比.Pmiss、Pdirty和ω是影響置換代價(jià)的要素,對(duì)磁盤(pán)而言,ω取值近似等于1,因此基于磁盤(pán)的緩沖區(qū)管理算法主要關(guān)注Pmiss對(duì)置換代價(jià)的影響,保持高訪問(wèn)命中率是緩沖區(qū)管理策略的主要目標(biāo).經(jīng)典緩沖區(qū)管理算法根據(jù)數(shù)據(jù)訪問(wèn)頻度和最近性設(shè)計(jì)頁(yè)面替換策略.閃存的讀寫(xiě)代價(jià)是不對(duì)稱的,其ω的取值受產(chǎn)品類(lèi)型和訪問(wèn)形式的影響比較大,大小通常超過(guò)5.閃存數(shù)據(jù)庫(kù)緩沖區(qū)管理必須同時(shí)考慮Pmiss和Pdirty對(duì)置換代價(jià)的影響,單純追求高命中率的設(shè)計(jì)原則對(duì)閃存未必有效,高命中率不一定帶來(lái)高I/O性能.設(shè)計(jì)高效的閃存緩沖區(qū)管理算法應(yīng)該滿足以下3個(gè)原則:(1)適當(dāng)減少對(duì)臟頁(yè)的置換,降低I/O代價(jià);(2)保持相對(duì)較高的命中率,減少缺頁(yè);(3)優(yōu)化寫(xiě)操作,避免大范圍的隨機(jī)寫(xiě)操作,提高閃存的使用壽命.根據(jù)置換代價(jià)的粒度,現(xiàn)有閃存數(shù)據(jù)庫(kù)緩沖區(qū)替換策略可分為基于頁(yè)級(jí)和基于塊級(jí)兩類(lèi).3.2.1產(chǎn)品類(lèi)別基于頁(yè)級(jí)代價(jià)的替換策略在選擇犧牲頁(yè)時(shí)考慮置換一頁(yè)的開(kāi)銷(xiāo),代價(jià)低的數(shù)據(jù)頁(yè)優(yōu)先被置換.(1)減少置換代價(jià)CFLRU是最早提出的閃存數(shù)據(jù)庫(kù)緩沖區(qū)管理算法.CFLRU在緩沖區(qū)發(fā)生缺頁(yè)中斷時(shí)優(yōu)先選擇干凈頁(yè)(CleanPage)進(jìn)行替換,臟頁(yè)(DirtyPage)被留在緩沖區(qū)以減少置換代價(jià).算法思想見(jiàn)圖3.CFLRU將緩沖區(qū)中的數(shù)據(jù)頁(yè)以LRU方式組織成隊(duì)列,在隊(duì)列的LRU端選擇部分?jǐn)?shù)據(jù)頁(yè)作為優(yōu)先置換區(qū),替換算法從優(yōu)先置換區(qū)按LRU順序選擇一干凈頁(yè)作犧牲頁(yè),如果沒(méi)有干凈頁(yè)則選擇位于LRU端的臟頁(yè),優(yōu)先置換區(qū)的大小由參數(shù)ω來(lái)控制.CFLRU方法可以有效減少臟頁(yè)寫(xiě)回閃存的次數(shù),但緩沖區(qū)中冷的臟數(shù)據(jù)頁(yè)可能會(huì)因?yàn)殚L(zhǎng)時(shí)間占據(jù)緩存而造成內(nèi)存污染.這里的冷熱指的是數(shù)據(jù)在最近時(shí)間內(nèi)被訪問(wèn)的情況.針對(duì)CFLRU的問(wèn)題,文獻(xiàn)[10-13]通過(guò)設(shè)置冷熱標(biāo)識(shí)位等方法優(yōu)化了替換策略對(duì)臟頁(yè)的選擇,命中率有所提高.(2)頻度和最近性僅從訪問(wèn)的最近性或訪問(wèn)頻度來(lái)區(qū)分?jǐn)?shù)據(jù)頁(yè)的冷熱程度不能很好地反映實(shí)際應(yīng)用中數(shù)據(jù)訪問(wèn)模式的變化.FOR基于最近性和訪問(wèn)頻度提出了一個(gè)數(shù)據(jù)冷熱模型:其中,IODp和ORp分別表示數(shù)據(jù)頁(yè)p的訪問(wèn)頻度和最近性;α是一個(gè)可控參數(shù),用于動(dòng)態(tài)調(diào)節(jié)頻度和最近性在熱度模型中所占的比重;IODp是指對(duì)p最近的兩次訪問(wèn)之間不同數(shù)據(jù)頁(yè)操作的次數(shù);ORp是指對(duì)p的最近一次訪問(wèn)距離當(dāng)前訪問(wèn)之間不同數(shù)據(jù)頁(yè)的操作次數(shù).數(shù)據(jù)訪問(wèn)列表記錄數(shù)據(jù)訪問(wèn)和替換的歷史信息,由列表可以計(jì)算出IODp和ORp.FOR根據(jù)Hotness(p)將緩沖區(qū)分為冷熱兩個(gè)區(qū),二者長(zhǎng)度比滿足Cread/Cwrite.置換算法先從冷數(shù)據(jù)區(qū)選擇犧牲頁(yè),為了避免數(shù)據(jù)在變熱前頻繁被換出內(nèi)存,FOR通過(guò)冷數(shù)據(jù)閾值Rcold來(lái)保證最少冷數(shù)據(jù)頁(yè)的數(shù)量,當(dāng)冷數(shù)據(jù)頁(yè)的數(shù)量低于Rcold,熱區(qū)中較冷的數(shù)據(jù)頁(yè)將補(bǔ)充到冷數(shù)據(jù)區(qū).3.2.2隨機(jī)寫(xiě)操作性能下降的原因閃存對(duì)讀寫(xiě)操作是非常敏感的,對(duì)于不同負(fù)載訪問(wèn)模式表現(xiàn)出極大的性能差異.為此,我們分別測(cè)試了5款不同品牌或型號(hào)固態(tài)硬盤(pán)的讀寫(xiě)性能.圖4給出了其中一款產(chǎn)品的性能對(duì)比.從實(shí)驗(yàn)結(jié)果可以看出,閃存隨機(jī)寫(xiě)操作的性能遠(yuǎn)不及順序?qū)?造成這一問(wèn)題的主要原因包括:(1)隨機(jī)寫(xiě)操作會(huì)觸發(fā)更多的塊擦除操作,擦除操作的代價(jià)昂貴;(2)閃存是通過(guò)內(nèi)部FTL軟件層對(duì)塊內(nèi)原數(shù)據(jù)進(jìn)行異位更新,無(wú)效舊數(shù)據(jù)導(dǎo)致塊內(nèi)產(chǎn)生大量存儲(chǔ)碎片,垃圾回收的代價(jià)比較大,而存儲(chǔ)碎片也會(huì)使邏輯地址與物理地址不再連續(xù)進(jìn)而影響數(shù)據(jù)預(yù)讀性能.文獻(xiàn)曾指出存有大量存儲(chǔ)碎片的閃存其讀寫(xiě)性能只有原來(lái)的30%.頁(yè)級(jí)替換策略可能導(dǎo)致閃存產(chǎn)生較多存儲(chǔ)碎片而引發(fā)頻繁的隨機(jī)寫(xiě)操作.塊級(jí)替換策略考慮到閃存良好的順序?qū)懶阅?以聚簇的方式將緩沖區(qū)中地址相近的數(shù)據(jù)頁(yè)分組,然后以組為單位批量將數(shù)據(jù)換出內(nèi)存.(1)基于fab的隨機(jī)訪問(wèn)FAB基于LRU算法以數(shù)據(jù)塊的形式組織緩沖區(qū)數(shù)據(jù),每一個(gè)塊聚集屬于同一閃存塊的數(shù)據(jù)頁(yè),當(dāng)緩沖區(qū)可用空間低于設(shè)定的閾值,聚集最多數(shù)據(jù)頁(yè)的塊將被換出內(nèi)存.FAB適用于裝有閃存芯片的PDA、媒體播放器、移動(dòng)電話和數(shù)碼相機(jī)等設(shè)備,這類(lèi)設(shè)備的數(shù)據(jù)管理具有典型的順序訪問(wèn)比較密集特性,FAB難以適用隨機(jī)訪問(wèn)頻繁的負(fù)載.針對(duì)FAB存在的問(wèn)題,BPLRU和REF在選擇犧牲塊時(shí)通過(guò)數(shù)據(jù)頁(yè)填充和標(biāo)記臟頁(yè)置換歷史等方法減少隨機(jī)寫(xiě)操作的代價(jià).(2)置換高效.CFDC將數(shù)據(jù)頁(yè)以簇的形式組織到一起,每一個(gè)簇由邏輯地址相近的n個(gè)數(shù)據(jù)頁(yè)構(gòu)成并賦予置換權(quán)值,權(quán)值低的簇放置在優(yōu)先置換區(qū).替換算法選擇優(yōu)先置換區(qū)中權(quán)值最小的簇替換出內(nèi)存.置換權(quán)值公式為其中,n表示一個(gè)簇所包含的數(shù)據(jù)頁(yè)的數(shù)量;pi-pi-1的絕對(duì)值表示簇內(nèi)相鄰兩個(gè)頁(yè)的邏輯頁(yè)號(hào)差,通常邏輯上越接近的數(shù)據(jù)頁(yè)物理上也相近,Age(c)反映簇的新舊程度.CFDC充分考慮簇的訪問(wèn)最近性和訪問(wèn)頻度,聚集數(shù)據(jù)頁(yè)時(shí)表現(xiàn)出更強(qiáng)的靈活性,避免了對(duì)閃存進(jìn)行大范圍的隨機(jī)寫(xiě)操作.表3列出了目前閃存數(shù)據(jù)庫(kù)主要的緩沖區(qū)管理算法.3.2.3運(yùn)行效率分析為了對(duì)比已有閃存緩沖區(qū)管理策略的性能,本文基于Flash-DBsim模擬器實(shí)現(xiàn)了LRU、CF-LRU、FAB、CFDC等替換算法.實(shí)驗(yàn)環(huán)境配置:數(shù)據(jù)頁(yè)大小為2KB,每個(gè)閃存塊包含64個(gè)頁(yè).閃存芯片的讀、寫(xiě)和擦除延遲分別為20μs,200μs和1.5ms.實(shí)驗(yàn)所用數(shù)據(jù)集基于TPC-C標(biāo)準(zhǔn),采用BenchmarkSQL運(yùn)行PostgreSQL數(shù)據(jù)庫(kù)獲得.數(shù)據(jù)請(qǐng)求次數(shù)為2087142,讀和寫(xiě)操作所占比例分別為71.3%和28.7%.CF-LRU算法的優(yōu)先置換窗口大小設(shè)置為可用緩沖區(qū)的60%,CFDC算法優(yōu)先置換區(qū)的大小設(shè)為40%,每一個(gè)簇的大小與閃存物理塊大小相同.實(shí)驗(yàn)主要分析數(shù)據(jù)集的運(yùn)行時(shí)間和閃存物理寫(xiě)次數(shù),結(jié)果如圖5所示.在運(yùn)行時(shí)間方面,從圖5(a)可以看出基于閃存的緩沖區(qū)替換策略的總體性能勝過(guò)LRU算法,其中FAB算法采用聚簇的方式替換數(shù)據(jù)頁(yè),對(duì)于順序訪問(wèn)特征不明顯的負(fù)載,FAB可能會(huì)導(dǎo)致一些頻繁訪問(wèn)的數(shù)據(jù)過(guò)早地被替換出內(nèi)存,在小容量?jī)?nèi)存環(huán)境下其性能不如LRU算法.在閃存物理寫(xiě)操作方面,從圖5(b)可以看出,基于閃存的緩沖區(qū)替換策略因?yàn)榭紤]了讀寫(xiě)不對(duì)稱特性,替換策略為臟頁(yè)賦予更高的置換權(quán)限,數(shù)據(jù)集運(yùn)行過(guò)程中產(chǎn)生的閃存物理寫(xiě)次數(shù)明顯降低,CFDC算法采用聚簇的方式將臟頁(yè)批量寫(xiě)回閃存,置換過(guò)程避免了大范圍的隨機(jī)寫(xiě)操作,在所有對(duì)比算法中引發(fā)的物理寫(xiě)次數(shù)最少.3.3查詢節(jié)省的i/o代價(jià)gain索引記錄了數(shù)據(jù)和其存儲(chǔ)地址的映射關(guān)系,利用索引可以快速定位相關(guān)數(shù)據(jù),降低I/O操作代價(jià)、提高查詢效率.索引必須能夠反映數(shù)據(jù)存儲(chǔ)位置發(fā)生的變化,當(dāng)數(shù)據(jù)發(fā)生更新時(shí)索引需要做及時(shí)更新.對(duì)于由n條記錄組成的數(shù)據(jù)集T,為T(mén)創(chuàng)建的索引為T(mén)index,通過(guò)索引對(duì)T進(jìn)行查詢節(jié)省的I/O代價(jià)gain(T)可簡(jiǎn)單的表示為式中,α×Cread表示掃描T和Tindex的代價(jià),α是查詢T所需總I/O數(shù),Cread是一次讀I/O代價(jià);索引維護(hù)代價(jià)update(Tindex)大小為β×Cwrite,其中β表示更新索引產(chǎn)生的I/O總數(shù),Cwrite是一次寫(xiě)I/O代價(jià).與磁盤(pán)相比,閃存的Cwrite遠(yuǎn)高于Cread,因此閃存索引更新需要付出相對(duì)更大的代價(jià).以B+-Tree索引為例,B+-Tree結(jié)點(diǎn)更新通常只需修改小部分?jǐn)?shù)據(jù),由于閃存最小以頁(yè)為單位進(jìn)行讀寫(xiě),少量數(shù)據(jù)更新也需要重寫(xiě)整個(gè)頁(yè)面,索引更新引發(fā)的大量擦除操作將極大降低索引性能和閃存壽命,減少索引更新代價(jià)是閃存數(shù)據(jù)庫(kù)索引管理需要解決的主要問(wèn)題.批量延時(shí)更新和索引結(jié)構(gòu)優(yōu)化是目前解決這一問(wèn)題使用較為廣泛的技術(shù).3.3.1延遲更新.對(duì)于數(shù)據(jù)更新引發(fā)的索引變化,延時(shí)更新不是將更新傳播至已有索引,而是把更新操作緩存在內(nèi)存,當(dāng)緩存的數(shù)據(jù)滿足設(shè)定條件再執(zhí)行批量更新操作.延遲更新通過(guò)消除冗余操作和批量提交的方法減少了寫(xiě)傳播的代價(jià).(1)la-前問(wèn)系的檢查Agrawal等人提出了一種基于樹(shù)的索引結(jié)構(gòu)——LA-Tree.LA-Tree以樹(shù)根為起點(diǎn),邏輯上將樹(shù)劃分為一系列高度相同的子樹(shù),每一棵子樹(shù)在內(nèi)存都有專用的緩沖區(qū)用于記錄對(duì)該子樹(shù)所有結(jié)點(diǎn)的更新.執(zhí)行查詢操作時(shí),LA-Tree檢查結(jié)點(diǎn)所在子樹(shù)的專用緩沖區(qū)是否滿足設(shè)定的更新條件,若滿足則清空緩沖區(qū)并對(duì)該子樹(shù)以及與它關(guān)聯(lián)的后代子樹(shù)進(jìn)行批量更新.LA-Tree優(yōu)化了對(duì)閃存的寫(xiě)操作,缺點(diǎn)是對(duì)每一子樹(shù)都需要維護(hù)特定的內(nèi)存空間,這增加了緩沖區(qū)管理的復(fù)雜性.(2)layn-東南角—Lazy-UpdateB+-Tree文獻(xiàn)提出的Lazy-UpdateB+-Tree將緩沖區(qū)劃分為兩部分,一部分用于緩存B+-Tree結(jié)點(diǎn),另一部分緩存對(duì)B+-Tree相應(yīng)結(jié)點(diǎn)的更新請(qǐng)求(更新緩沖池).更新緩沖池用十字鏈表結(jié)構(gòu)組織數(shù)據(jù),結(jié)點(diǎn)結(jié)構(gòu)為{key,recptr,type},其中key存儲(chǔ)元組的主鍵,recptr指針指向被更新的元組的地址,recptr為null代表該元組被刪除,type表示更新操作的類(lèi)型(刪除、插入和修改).Lazy-UpdateB+-Tree把對(duì)同一結(jié)點(diǎn)的更新請(qǐng)求聚集成一個(gè)序列,聚集可以消除對(duì)B+-Tree結(jié)點(diǎn)冗余的更新操作,進(jìn)而減少索引更新的寫(xiě)代價(jià).更新緩沖池被填滿后,代價(jià)最小的序列被更新,更新代價(jià)由gain(g)=cost(R)+cost(R′)-cost(R∪R′)來(lái)衡量,R表示序列g(shù)當(dāng)前更新請(qǐng)求,R′表示延時(shí)g到t時(shí)刻時(shí)的更新請(qǐng)求,cost(R)和cost(R′)代表在當(dāng)前時(shí)刻和t時(shí)刻兩次單獨(dú)提交g的寫(xiě)代價(jià).cost(R∪R′)則是聚集到t時(shí)刻批量提交的代價(jià).簡(jiǎn)單地說(shuō),代價(jià)最小指的就是某一索引結(jié)點(diǎn)更新引發(fā)B+-Tree結(jié)點(diǎn)分裂或合并的數(shù)量最少.(3)um-b+-東北部文獻(xiàn)提出了一種基于B+-tree的索引結(jié)構(gòu)——UM-B+-tree.UM-B+-tree把索引結(jié)點(diǎn)分成數(shù)據(jù)區(qū)和更新區(qū),數(shù)據(jù)區(qū)存儲(chǔ)記錄的鍵值和地址,更新區(qū)存儲(chǔ)對(duì)該結(jié)點(diǎn)的更新記錄.如果索引結(jié)點(diǎn)需要被換出內(nèi)存,對(duì)該結(jié)點(diǎn)的全部更新記錄都將遷移到父結(jié)點(diǎn)暫存,當(dāng)結(jié)點(diǎn)再次讀入內(nèi)存,暫存在父結(jié)點(diǎn)的更新記錄將與原數(shù)據(jù)合并產(chǎn)生版本數(shù)據(jù).當(dāng)更新記錄達(dá)到設(shè)定的閾值,新數(shù)據(jù)將被寫(xiě)入閃存.UM-B+-tree結(jié)點(diǎn)更新過(guò)程見(jiàn)圖6.舉例說(shuō)明,圖6中結(jié)點(diǎn)A和B讀入內(nèi)存并分別執(zhí)行一次插入和刪除操作,更新記錄保存在各自的更新區(qū),換出內(nèi)存時(shí)A和B將更新記錄上移至各自的父結(jié)點(diǎn).UM-B+-tree通過(guò)暫存更新記錄的方式延遲對(duì)閃存的更新,一定程度上減少了對(duì)閃存的寫(xiě)次數(shù),但每個(gè)結(jié)點(diǎn)都需要預(yù)留保存更新記錄的區(qū)域,空間利用率相對(duì)較低.延遲更新是犧牲讀代價(jià)來(lái)?yè)Q取寫(xiě)代價(jià)的,這對(duì)數(shù)據(jù)查詢、事務(wù)恢復(fù)及并發(fā)控制等會(huì)有一定程度的影響.3.3.2索引結(jié)構(gòu)優(yōu)化優(yōu)化索引結(jié)構(gòu)是提高索引性能的另一種有效途徑.結(jié)構(gòu)優(yōu)化不僅可以降低索引更新代價(jià),還可以提高數(shù)據(jù)查詢效率.(1)-前存出的錯(cuò)誤,容易造成檢查出錯(cuò)誤閃存異位更新會(huì)引發(fā)B+-Tree索引在閃存上代價(jià)昂貴的級(jí)聯(lián)更新.所謂級(jí)聯(lián)更新指的是任何一索引結(jié)點(diǎn)的更新可能都會(huì)導(dǎo)致根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所有結(jié)點(diǎn)的更新.級(jí)聯(lián)更新會(huì)產(chǎn)生大量的隨機(jī)寫(xiě)操作,嚴(yán)重影響索引性能.μ-Tree索引將根到目標(biāo)結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)存儲(chǔ)在同一閃存塊,數(shù)據(jù)更新產(chǎn)生的新路徑將被存儲(chǔ)在新的閃存塊,舊塊中原路徑結(jié)點(diǎn)無(wú)效.μ-Tree結(jié)點(diǎn)大小由閃存頁(yè)面大小和結(jié)點(diǎn)所在層次決定.μ-Tree結(jié)點(diǎn)更新過(guò)程見(jiàn)圖7.舉例說(shuō)明,結(jié)點(diǎn)F發(fā)生更新操作,新路徑A到F的所有結(jié)點(diǎn)存儲(chǔ)在新數(shù)據(jù)塊,原來(lái)的路徑結(jié)點(diǎn)(A,C,F)無(wú)效.μ-Tree每次數(shù)據(jù)更新都發(fā)生在同一閃存塊,這有利于降低隨機(jī)寫(xiě)操作代價(jià),但這種方式也會(huì)導(dǎo)致閃存內(nèi)出現(xiàn)許多無(wú)效結(jié)點(diǎn),空間利用率低,需要不斷地進(jìn)行垃圾回收,μ-Tree結(jié)構(gòu)無(wú)法支持范圍查詢.(2)基于存儲(chǔ)的索引結(jié)構(gòu)MicroHash是一種基于Hash的閃存索引結(jié)構(gòu).MicroHash在內(nèi)存維護(hù)一個(gè)能有效存取閃存數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),閃存中的記錄以循環(huán)數(shù)組方式被組織成堆結(jié)構(gòu),內(nèi)容包括目錄和索引頁(yè).每個(gè)目錄包含一系列的桶,每個(gè)桶存放映射到該桶的最新索引頁(yè)地址,每個(gè)索引頁(yè)存放數(shù)據(jù)記錄的地址,這些頁(yè)存放在閃存上,僅當(dāng)被請(qǐng)求時(shí)才調(diào)入內(nèi)存.MicroHash適合小容量的閃存設(shè)備,在較小內(nèi)存開(kāi)銷(xiāo)的情況下實(shí)現(xiàn)了對(duì)閃存友好的寫(xiě)操作.文獻(xiàn)也提出了一種基于閃存的新索引結(jié)構(gòu)——HashTree.HashTree混合了散列和樹(shù)兩種索引結(jié)構(gòu).它選擇合適的Hash函數(shù)將數(shù)據(jù)均勻的散列到不同的桶中,其中Hash表駐留內(nèi)存,每一個(gè)Hash桶存儲(chǔ)在閃存,每個(gè)桶中的數(shù)據(jù)采用類(lèi)似于FD-Tree樹(shù)形結(jié)構(gòu)進(jìn)行組織.HashTree將樹(shù)以Hash桶為單位劃分成有序的子樹(shù),有效減少了樹(shù)結(jié)點(diǎn)級(jí)聯(lián)更新的代價(jià).(3)pbfi觀察索引PBFilter是基于醫(yī)療領(lǐng)域數(shù)據(jù)特點(diǎn)設(shè)計(jì)的一種高效索引結(jié)構(gòu).醫(yī)療USB卡記錄一般都是插入和查詢操作,很少存在刪除和更新.PBFilter按照時(shí)間順序?qū)⒂涗泴?xiě)入閃存,并為這些記錄建立(Key,Value)索引項(xiàng).因?yàn)樗饕?xiàng)是無(wú)序存放的,為了提高查詢效率,PBFilter對(duì)key值建立BloomFilter索引.查找記錄時(shí),通過(guò)查找BloomFilter獲取所需記錄.BloomFilter所需空間比索引項(xiàng)要小得多,相比于其它索引結(jié)構(gòu),PBFilter具有更加優(yōu)秀的隨機(jī)查詢能力.表4列出了幾種典型的閃存數(shù)據(jù)庫(kù)索引.3.4實(shí)驗(yàn)結(jié)果與分析查詢處理是數(shù)據(jù)庫(kù)系統(tǒng)最重要的任務(wù)之一.為了提高系統(tǒng)性能,對(duì)查詢處理進(jìn)行優(yōu)化非常必要.在基于磁盤(pán)的數(shù)據(jù)庫(kù)系統(tǒng)中,已有的查詢優(yōu)化技術(shù)主要考慮磁盤(pán)I/O代價(jià)對(duì)查詢處理的影響.比如在處理多表連接時(shí),許多連接算法采用塊級(jí)I/O訪問(wèn)來(lái)減少磁盤(pán)尋道時(shí)間,降低磁盤(pán)I/O數(shù)量.避免或降低對(duì)磁盤(pán)的隨機(jī)訪問(wèn)是眾多經(jīng)典查詢優(yōu)化算法考慮的一個(gè)通用原則.閃存與磁盤(pán)的I/O特性不同,傳統(tǒng)的查詢優(yōu)化技術(shù)是否能夠發(fā)揮閃存的存儲(chǔ)特性便成為閃存數(shù)據(jù)庫(kù)系統(tǒng)需要考慮的一個(gè)重要問(wèn)題.文獻(xiàn)用固態(tài)硬盤(pán)替換磁盤(pán)對(duì)循環(huán)嵌套、排序-合并、GraceHash和混合Hash等連接算法進(jìn)行了性能測(cè)試.實(shí)驗(yàn)結(jié)果表明這4種連接操作的執(zhí)行時(shí)間均低于在磁盤(pán)上執(zhí)行的時(shí)間,但性能提升的幅度卻不足2倍.分析算法特征和實(shí)驗(yàn)結(jié)果,我們認(rèn)為現(xiàn)有連接算法在查詢處理過(guò)程中引發(fā)的I/O操作不適合閃存的存儲(chǔ)特性,閃存優(yōu)良的隨機(jī)讀性能沒(méi)有得到充分的發(fā)揮.具體表現(xiàn)在兩方面:(1)傳統(tǒng)連接算法需要保存大量中間結(jié)果而產(chǎn)生較多的寫(xiě)操作,頻繁的寫(xiě)操作會(huì)使查詢性能急劇惡化;(2)傳統(tǒng)算法著重考慮磁盤(pán)I/O代價(jià)對(duì)查詢性能的影響,很少考慮CPU代價(jià)因素,對(duì)于固態(tài)硬盤(pán)來(lái)說(shuō),讀寫(xiě)數(shù)據(jù)需要通過(guò)閃存轉(zhuǎn)換層完成地址轉(zhuǎn)換,所以耗費(fèi)CPU資源比磁盤(pán)相對(duì)要高,CPU代價(jià)在某種程度上制約了連接性能的進(jìn)一步提升.文獻(xiàn)還測(cè)試了閃存I/O大小對(duì)連接性能的影響,實(shí)驗(yàn)表明塊級(jí)I/O訪問(wèn)有利于提高查詢性能,大塊的數(shù)據(jù)請(qǐng)求可以充分利用固態(tài)硬盤(pán)實(shí)時(shí)的空閑通道,通過(guò)發(fā)揮固態(tài)硬盤(pán)內(nèi)部并行讀寫(xiě)機(jī)制來(lái)提高性能.文獻(xiàn)基于PostgreSQL數(shù)據(jù)庫(kù)系統(tǒng)對(duì)查詢性能進(jìn)行了對(duì)比評(píng)測(cè).與磁盤(pán)相比,固態(tài)硬盤(pán)存儲(chǔ)環(huán)境下單點(diǎn)查詢性能最高有近50倍的提升,但不同掃描操作符性能提升的幅度差距比較大.在查詢選擇率較低的情況下,索引掃描因?yàn)槌浞职l(fā)揮了固態(tài)硬盤(pán)良好的隨機(jī)讀性能,性能表現(xiàn)最為突出.多表連接操作在固態(tài)硬盤(pán)上的性能差異也比較大,以循環(huán)嵌套連接為例,如果對(duì)大表進(jìn)行索引掃描,查詢性能提升的幅度較明顯,這是因?yàn)榇蟊碓M多,內(nèi)存命中率低,需要更多地隨機(jī)讀操作.Hash連接算法因?yàn)樾枰嗟碾S機(jī)訪問(wèn),所以在固態(tài)硬盤(pán)上性能提升較大,但與其它連接算法相比,需要的查詢執(zhí)行時(shí)間最多,這主要是因?yàn)閷?duì)元組進(jìn)行Hash分桶會(huì)觸發(fā)許多隨機(jī)寫(xiě)操作,而隨機(jī)寫(xiě)操作是閃存最不擅長(zhǎng)的一種訪問(wèn)模式.從已有的測(cè)試結(jié)果不難看出,適用于磁盤(pán)的經(jīng)典連接算法在固態(tài)硬盤(pán)上的性能表現(xiàn)并不突出.因此,現(xiàn)有查詢優(yōu)化算法必須針對(duì)閃存獨(dú)有的I/O特性重新設(shè)計(jì).目前研究者主要從代價(jià)模型修改和優(yōu)化查詢連接算法兩個(gè)角度展開(kāi)研究.3.4.1基于性能分析的代價(jià)評(píng)估模型數(shù)據(jù)庫(kù)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)和算法優(yōu)化與存儲(chǔ)介質(zhì)的I/O特性緊密相關(guān),在查詢規(guī)劃過(guò)程中,不同的查詢生成樹(shù)通過(guò)代價(jià)模型對(duì)相應(yīng)的查詢路徑進(jìn)行估算,代價(jià)最小的執(zhí)行方案將被轉(zhuǎn)換成最終查詢計(jì)劃并由執(zhí)行器執(zhí)行.查詢路徑的代價(jià)估計(jì)主要考慮CPU代價(jià)和磁盤(pán)I/O代價(jià).比如,PostgreSQL數(shù)據(jù)庫(kù)系統(tǒng)的代價(jià)模型將順序存取一個(gè)磁盤(pán)頁(yè)的代價(jià)作為基本單位(取值為1),隨機(jī)存取操作的代價(jià)取值為4.查詢優(yōu)化算法在代價(jià)評(píng)估和生成查詢計(jì)劃樹(shù)等環(huán)節(jié)只區(qū)分磁盤(pán)順序和隨機(jī)操作代價(jià),多采用排序、延遲物化等手段減少對(duì)磁盤(pán)的隨機(jī)I/O訪問(wèn).閃存的隨機(jī)讀操作與順序讀操作性能相差不大,將現(xiàn)有的代價(jià)估計(jì)模型運(yùn)用于閃存數(shù)據(jù)庫(kù)系統(tǒng)可能會(huì)影響最優(yōu)查詢計(jì)劃的生成.因此,針對(duì)閃存特有的I/O特性對(duì)現(xiàn)有代價(jià)模型進(jìn)行優(yōu)化可以提高查詢代價(jià)估計(jì)的準(zhǔn)確性,進(jìn)而提升數(shù)據(jù)庫(kù)的查詢性能.文獻(xiàn)基于PostgreSQL提出了一個(gè)適用于閃存的代價(jià)評(píng)估模型.新的代價(jià)模型區(qū)分讀寫(xiě)操作,I/O代價(jià)參數(shù)設(shè)置為順序讀操作、順序?qū)懖僮?、隨機(jī)讀操作和隨機(jī)寫(xiě)操作等4種.掃描操作代價(jià)估計(jì)只區(qū)分順序讀和隨機(jī)讀,物化操作則只對(duì)順序?qū)懞碗S機(jī)寫(xiě)進(jìn)行分別處理.通過(guò)分析排序連接和Hash連接等操作產(chǎn)生的I/O訪問(wèn)序列,新模型將原有模型的讀寫(xiě)代價(jià)比進(jìn)行了調(diào)整.針對(duì)連接過(guò)程中讀寫(xiě)操作混合的情況,新模型通過(guò)一個(gè)啟發(fā)式迭代校正算法適時(shí)地對(duì)代價(jià)參數(shù)進(jìn)行調(diào)整.該文獻(xiàn)將新的代價(jià)模型應(yīng)用于PostgreSQL并進(jìn)行了TPC-H測(cè)試,TPC-H22個(gè)查詢的執(zhí)行時(shí)間大部分都有所減少,平均性能提高48%,部分查詢性能有5倍的提高,個(gè)別查詢的執(zhí)行時(shí)間有略微增加.結(jié)合閃存的讀寫(xiě)特性,設(shè)計(jì)適合閃存的代價(jià)評(píng)估模型是提高查詢性能的一個(gè)有效途徑.3.4.2re-toin連接連接查詢通常只需要輸出連接表的部分屬性列,Ailamaki等人為了避免讀取與查詢不相關(guān)的屬性列,提出了一種新的存儲(chǔ)模型PAX.每一個(gè)PAX數(shù)據(jù)頁(yè)存儲(chǔ)一定數(shù)量的元組,數(shù)據(jù)頁(yè)按元組屬性列緊湊堆放,這種存儲(chǔ)模型兼有按行存儲(chǔ)和按列存儲(chǔ)的優(yōu)點(diǎn).文獻(xiàn)[33-34]基于PAX提出RARE-join連接算法,RARE-join首先根據(jù)連接條件創(chuàng)建一個(gè)連接結(jié)果表,元組結(jié)構(gòu)為{id1,id2,…,idi,…},其中idi表示第i張表某一元組的存儲(chǔ)地址;然后為存儲(chǔ)在結(jié)果表中的元組地址構(gòu)建索引,根據(jù)索引從原表中讀取數(shù)據(jù)并生成查詢結(jié)果.RARE-join只選擇與查詢結(jié)果相關(guān)的屬性列,這減少了數(shù)據(jù)的讀取量,避免了大量中間結(jié)果的生成,物化過(guò)程放在查詢的最后階段,閃存的寫(xiě)操作比較少.RARE-join存在的主要問(wèn)題是維護(hù)底層PAX存儲(chǔ)和索引的代價(jià)較大.(2)digest表的生成為了減少排序-合并等連接算法產(chǎn)生的中間結(jié)果,Li等人提出針對(duì)閃存特性的DigestJoin查詢優(yōu)化算法.DigestJoin算法將查詢過(guò)程分為兩個(gè)階段:第1階段抽取待連接表元組的鍵值和連接屬性構(gòu)建Digest表,由Digest表根據(jù)連接屬性通過(guò)排序或者Hash的方式連接產(chǎn)生結(jié)果表,結(jié)果表存儲(chǔ)與查詢結(jié)果相關(guān)聯(lián)的元組在原始表中的地址;第2階段是實(shí)體化查詢結(jié)果,根據(jù)結(jié)果表記錄的元組地址從閃存讀取原始表的相關(guān)屬性列生成最終的查詢結(jié)果.實(shí)體化過(guò)程需要大量的隨機(jī)讀操作,這是影響查詢性能的關(guān)鍵因素.為了盡量避免反復(fù)讀取某一數(shù)據(jù)頁(yè),DigestJoin通過(guò)構(gòu)建數(shù)據(jù)頁(yè)之間的連接關(guān)系圖對(duì)實(shí)體化的過(guò)程進(jìn)行了優(yōu)化,有效解決了反復(fù)讀取同一數(shù)據(jù)頁(yè)產(chǎn)生的內(nèi)存抖動(dòng)問(wèn)題.(3)存儲(chǔ)關(guān)聯(lián)算法文獻(xiàn)提出的Sub-Join算法首先將執(zhí)行連接操作的相關(guān)數(shù)據(jù)表在主鍵和連接列上進(jìn)行投影,根據(jù)連接列進(jìn)行排序形成連接子表;然后在子表上進(jìn)行連接操作,連接過(guò)程需要的其它結(jié)果數(shù)據(jù)由原始表回取獲得.Sub-Join對(duì)子表采用基于列的存儲(chǔ)形式,閃存隨機(jī)讀操作相對(duì)較少.Myers提出基于閃存的排序-合并連接算法.排序-合并算法通常先將連接表讀入內(nèi)存并分段排序,然后將排序后的元組寫(xiě)回磁盤(pán)形成有序片段.Myers針對(duì)閃存寫(xiě)性能相對(duì)較差和壽命有限的特點(diǎn)對(duì)中間結(jié)果的存取過(guò)程進(jìn)行了優(yōu)化,只將連接列寫(xiě)入閃存,在排序結(jié)束后,再?gòu)脑急慝@取其它數(shù)據(jù),完成最初的排序過(guò)程.閃存不對(duì)稱的讀寫(xiě)代價(jià)是影響閃存數(shù)據(jù)庫(kù)查詢性能的關(guān)鍵因素.設(shè)計(jì)基于閃存的查詢優(yōu)化策略時(shí)必須盡量減少寫(xiě)操作尤其是隨機(jī)寫(xiě)操作,同時(shí)應(yīng)充分利用閃存很好的隨機(jī)讀性能,犧牲讀代價(jià)以降低寫(xiě)代價(jià)是提高查詢性能的有效手段.表5列出了幾種典型的閃存數(shù)據(jù)庫(kù)連接算法.3.4.3不同選擇率對(duì)連接算法的影響為了對(duì)比固態(tài)硬盤(pán)環(huán)境下查詢處理的性能,我們分別對(duì)傳統(tǒng)Hash連接、DigestJoin和Sub-Join3種連接算法進(jìn)行了實(shí)驗(yàn)比較.實(shí)驗(yàn)平臺(tái)配置:IntelCorei5-2400@3.10GHz處理器,內(nèi)存8GB,操作系統(tǒng)是Ubuntu12.10,數(shù)據(jù)集采用TPC-H的CUS-TOMER表和ORDERS表并做等值連接,其中CUSTOMER由150萬(wàn)條記錄組成,大小為256MB,ORDERS表由1.5億條記錄組成,大小為2GB.實(shí)驗(yàn)測(cè)試了選擇率和緩沖區(qū)大小對(duì)連接算法的影響.(1)選擇率.選擇率反映了結(jié)果數(shù)據(jù)的規(guī)模,選擇率越大生成的結(jié)果數(shù)據(jù)越多,許多查詢連接算法都通過(guò)變化選擇率來(lái)評(píng)估查詢性能.對(duì)比實(shí)驗(yàn)中選擇率的取值為0.01%~10%.可用內(nèi)存是8MB,圖8(a)描述了不同選擇率下的查詢執(zhí)行時(shí)間.從實(shí)驗(yàn)結(jié)果可以看出,當(dāng)選擇率低于0.1%時(shí),DigestJoin和Sub-Join的性能優(yōu)于HashJoin.隨著選擇率的增大,DigestJoin和Sub-Join因?yàn)樾枰４娓嗟闹虚g結(jié)果,查詢執(zhí)行時(shí)間增長(zhǎng)幅度比較大.Sub-Join因?yàn)閷?duì)子表采用基于列的存儲(chǔ),在一定程度上減少了對(duì)SSD的寫(xiě)操作,其查詢性能略優(yōu)于DigestJoin;(2)緩沖區(qū).緩沖區(qū)大小是影響查詢連接性能的重要因素,圖8(b)描述了不同緩沖區(qū)大小下3種連接算法的性能.DigestJoin受緩沖區(qū)大小的影響比較明顯,在緩沖區(qū)大小超過(guò)16MB后,查詢連接性能提升幅度較大.Sub-Join基于循環(huán)嵌套連接算法,在生成連接子表時(shí)對(duì)內(nèi)存大小要求較低,在緩存區(qū)較小的情況下,查詢性能勝過(guò)DigestJoin.3.5基于影子頁(yè)的事務(wù)恢復(fù)機(jī)制事務(wù)恢復(fù)機(jī)制用于保障系統(tǒng)發(fā)生異常時(shí)將數(shù)據(jù)庫(kù)系統(tǒng)恢復(fù)到之前的穩(wěn)定狀態(tài).現(xiàn)有的恢復(fù)方法主要包括預(yù)寫(xiě)日志和影子頁(yè)兩類(lèi).日志記錄了事務(wù)對(duì)數(shù)據(jù)的更新并被順序追加到日志文件尾部,恢復(fù)操作根據(jù)日志完成對(duì)某一事務(wù)的撤銷(xiāo)或重做.恢復(fù)過(guò)程通常會(huì)產(chǎn)生大量小的隨機(jī)寫(xiě)操作,閃存處理小范圍隨機(jī)寫(xiě)的代價(jià)比較高,然而現(xiàn)有的日志處理技術(shù)難以充分利用閃存的存儲(chǔ)特性,優(yōu)化日志結(jié)構(gòu)和恢復(fù)策略是提高閃存數(shù)據(jù)庫(kù)事務(wù)處理性能的關(guān)鍵.基于影子頁(yè)的事務(wù)恢復(fù)機(jī)制采用異位更新方式,更新操作會(huì)將數(shù)據(jù)存儲(chǔ)在新的物理頁(yè),系統(tǒng)維護(hù)兩張頁(yè)地址映射表來(lái)保存邏輯頁(yè)號(hào)和物理頁(yè)號(hào)的對(duì)應(yīng)關(guān)系.影子頁(yè)技術(shù)不會(huì)產(chǎn)生日志來(lái)記錄對(duì)數(shù)據(jù)庫(kù)的操作,沒(méi)有顯式的回滾機(jī)制對(duì)數(shù)據(jù)庫(kù)的操作進(jìn)行撤銷(xiāo).如果當(dāng)前事務(wù)正確提交,則可以將當(dāng)前頁(yè)表寫(xiě)入外存.如果事務(wù)未能提交,則丟棄當(dāng)前頁(yè)表并恢復(fù)到該事務(wù)執(zhí)行前的狀態(tài).影子頁(yè)在事務(wù)提交或撤銷(xiāo)時(shí)要執(zhí)行修改映射信息、回收無(wú)效數(shù)據(jù)等操作,頻繁的隨機(jī)讀操作使得影子頁(yè)技術(shù)并不適合磁盤(pán)數(shù)據(jù)庫(kù)系統(tǒng).閃存的物理特性與影子頁(yè)數(shù)據(jù)管理十分吻合,在閃存數(shù)據(jù)庫(kù)系統(tǒng)中使用影子頁(yè)有助于提升事務(wù)處理能力.3.5.1事務(wù)回滾管理模塊tHV-recovery基于閃存異位更新和高速的隨機(jī)讀特性設(shè)計(jì)實(shí)現(xiàn)了適用于閃存的數(shù)據(jù)庫(kù)恢復(fù)方法.閃存在執(zhí)行更新時(shí)會(huì)自動(dòng)保存同一數(shù)據(jù)頁(yè)的多個(gè)不同版本,HV-recovery根據(jù)這一特性提出了一種新型的基于地址的日志處理策略——HV-Logging.HV-Logging機(jī)制的日志結(jié)構(gòu)為{Tid,element,PreAddress,PreValue},其中Tid唯一標(biāo)識(shí)某一事務(wù),element是事務(wù)操作的對(duì)象元素,PreAddress指向舊版本歷史數(shù)據(jù),PreValue記錄被更改元素的舊值.事務(wù)回滾管理模塊通過(guò)讀取日志獲得各元素舊版本地址,根據(jù)地址取出數(shù)據(jù)并判斷是否與日志保存的舊值相同,若相同,將新的數(shù)據(jù)頁(yè)置為無(wú)效,恢復(fù)原數(shù)據(jù)頁(yè)為有效狀態(tài);若不同,則重新寫(xiě)入新數(shù)據(jù).HV-Logging優(yōu)化了日志結(jié)構(gòu),減少了冗余日志和垃圾數(shù)據(jù)的存在,提高了空間利用率,利用閃存快速隨機(jī)讀的特性大幅減少恢復(fù)時(shí)間.LB-Logging采用鏈表結(jié)構(gòu)來(lái)記錄日志.同一事務(wù)更新的各個(gè)元素和每個(gè)元素的不同版本都分別建立指針鏈,這保證了事務(wù)和被修改元素之間的關(guān)聯(lián)性,恢復(fù)操作根據(jù)指針鏈可以準(zhǔn)確、快速地找出該事務(wù)所有操作日志.FlashLogging從系統(tǒng)代價(jià)的角度提出了一種性價(jià)比較高的日志處理方案.FlashLogging用價(jià)格低廉的USB閃存存儲(chǔ)器專門(mén)存儲(chǔ)記錄日志.日志通常以順序追加的方式寫(xiě)入外存,這符合閃存順序?qū)憥捀叩拇鎯?chǔ)特性.FlashLogging將許多USB閃存設(shè)備以陣列的形式來(lái)組織,解決了單塊設(shè)備容量有限的問(wèn)題.3.5.2數(shù)據(jù)安全更新SLC型閃存允許對(duì)同一頁(yè)在擦除之前多次寫(xiě)入數(shù)據(jù).FlagCommit針對(duì)SLC閃存這一特性提出一種基于影子頁(yè)的事務(wù)處理機(jī)制.FlagCommit在閃存頁(yè)的備用區(qū)存儲(chǔ)和事務(wù)相關(guān)的元數(shù)據(jù),這些元數(shù)據(jù)包括事務(wù)ID、事務(wù)狀態(tài)、事務(wù)更新的前一個(gè)數(shù)據(jù)頁(yè)地址、提交標(biāo)記等.鏈表指針把同一事務(wù)關(guān)聯(lián)的數(shù)據(jù)頁(yè)邏輯上連在一起,事務(wù)提交或回滾時(shí)通過(guò)這些元數(shù)據(jù)進(jìn)行數(shù)據(jù)更新或恢復(fù).FlagCommit中被更新的數(shù)據(jù)頁(yè)可被看作影子頁(yè),備用區(qū)中的元數(shù)據(jù)構(gòu)成了眾多分散的地址映射表.事務(wù)提交協(xié)議根據(jù)存儲(chǔ)在備用區(qū)的提交標(biāo)記執(zhí)行提交或回滾操作.當(dāng)數(shù)據(jù)更新或垃圾回收導(dǎo)致鏈表斷裂時(shí),修改提交標(biāo)記可以保證事務(wù)和該事務(wù)相關(guān)的多個(gè)分裂鏈表邏輯上關(guān)聯(lián)在一起.影子頁(yè)在1977年被提出.事務(wù)處理因?yàn)椴恍枰A(yù)寫(xiě)日志而變得更加有效,但影子頁(yè)在處理過(guò)程中會(huì)產(chǎn)生很多隨機(jī)讀操作,因此在磁盤(pán)存儲(chǔ)時(shí)代影子頁(yè)技術(shù)未能得到廣泛應(yīng)用.閃存異位更新的特性天然地保存了事務(wù)更新的歷史版本數(shù)據(jù),這為影子頁(yè)恢復(fù)機(jī)制提供了很好的支持.表6列出了幾種主要的閃存數(shù)據(jù)庫(kù)恢復(fù)方法.4sd的運(yùn)行成本盡管基于閃存的固態(tài)硬盤(pán)(SSD)比磁盤(pán)具有更大的性能優(yōu)勢(shì),但是短期內(nèi)SSD不會(huì)完全取代磁盤(pán)成為主流存儲(chǔ)介質(zhì).將SSD和磁盤(pán)共存形成混合存儲(chǔ)系統(tǒng)是未來(lái)一段時(shí)期數(shù)據(jù)管理的研究熱點(diǎn).混合存儲(chǔ)主要考慮到以下幾個(gè)因素:(1)SSD使用壽命.閃存容量的不斷增大是通過(guò)犧牲可用壽命的代價(jià)來(lái)獲得的,頻繁的數(shù)據(jù)訪問(wèn)會(huì)極大縮短SSD的壽命,SSD完全取代磁盤(pán)對(duì)系統(tǒng)運(yùn)行的可靠性和穩(wěn)定性是一大考驗(yàn);(2)價(jià)格成本.盡管SSD的價(jià)格在不斷走低,但即便是低端產(chǎn)品其單位容量的價(jià)格仍然是磁盤(pán)的十倍,基于閃存的混合存儲(chǔ)系統(tǒng)性價(jià)比高;(3)數(shù)據(jù)訪問(wèn)的局部性.數(shù)據(jù)訪問(wèn)通常呈現(xiàn)不均衡特性,一段時(shí)間內(nèi)只有部分?jǐn)?shù)據(jù)是頻繁被訪問(wèn)的,約有40%的數(shù)據(jù)訪問(wèn)頻度較低.根據(jù)SSD和磁盤(pán)的物理特性將二者組合,有選擇地把數(shù)據(jù)分配到不同存儲(chǔ)介質(zhì)(比如將最熱數(shù)據(jù)或讀操作密集的數(shù)據(jù)交由SSD來(lái)處理),不僅能滿足大數(shù)據(jù)、高吞吐等應(yīng)用需求,也可以有效降低企業(yè)成本.考慮SSD和磁盤(pán)混合存儲(chǔ)的結(jié)構(gòu)特性,混合存儲(chǔ)數(shù)據(jù)管理目前研究點(diǎn)包括:(1)SSD和磁盤(pán)同作二級(jí)存儲(chǔ);(2)SSD作為內(nèi)存的擴(kuò)展緩存.4.1盤(pán)在混合存儲(chǔ)信息管理中的應(yīng)用結(jié)合硬件特性和數(shù)據(jù)訪問(wèn)特征,SSD和磁盤(pán)在混合存儲(chǔ)數(shù)據(jù)管理中分別承擔(dān)不同的存儲(chǔ)任務(wù):(1)磁盤(pán)緩存上層應(yīng)用對(duì)SSD的寫(xiě)操作;(2)SSD存儲(chǔ)特定類(lèi)型數(shù)據(jù).4.1.1sd/存儲(chǔ)策略配置為了降低隨機(jī)寫(xiě)操作對(duì)SSD壽命和系統(tǒng)性能的影響,Griffin選擇用磁盤(pán)緩存上層應(yīng)用對(duì)SSD的寫(xiě)操作,Griffin以日志的方式將內(nèi)存換出的臟頁(yè)順序?qū)懭氪疟P(pán),后臺(tái)進(jìn)程有條件地將存儲(chǔ)在SSD上的原始數(shù)據(jù)和磁盤(pán)上的日志數(shù)據(jù)進(jìn)行合并生成新數(shù)據(jù).文獻(xiàn)基于頁(yè)面分類(lèi)思想將系統(tǒng)對(duì)SSD的隨機(jī)寫(xiě)操作暫存于磁盤(pán),通過(guò)磁盤(pán)將這些隨機(jī)寫(xiě)序列轉(zhuǎn)換為順序操作序列并最終寫(xiě)回SSD.將磁盤(pán)用作SSD寫(xiě)緩存的存儲(chǔ)策略發(fā)揮了磁盤(pán)或磁盤(pán)陣列順序訪問(wèn)性能較好的特點(diǎn),利用SSD高速隨機(jī)讀性能對(duì)數(shù)據(jù)進(jìn)行合并后順序?qū)懭隨SD.需要注意的是,磁盤(pán)I/O瓶頸和頻繁的數(shù)據(jù)合并使得這種混合系統(tǒng)難以應(yīng)對(duì)更新操作密集和訪問(wèn)模式多變的負(fù)載.4.1.2sd存儲(chǔ)及讀取特征數(shù)據(jù)基于SSD優(yōu)良的隨機(jī)讀性能,通過(guò)分析負(fù)載訪問(wèn)特征和數(shù)據(jù)類(lèi)型,將讀操作密集的數(shù)據(jù)、索引文件、臨時(shí)表等存儲(chǔ)在SSD有利于提高系統(tǒng)的數(shù)據(jù)處理能力.文獻(xiàn)提出了基于頁(yè)面I/O統(tǒng)計(jì)信息的頁(yè)面遷移模型.該模型根據(jù)I/O統(tǒng)計(jì)信息計(jì)算數(shù)據(jù)存放在SSD和磁盤(pán)的代價(jià),根據(jù)代價(jià)對(duì)頁(yè)面進(jìn)行分類(lèi)并動(dòng)態(tài)地對(duì)SSD和磁盤(pán)數(shù)據(jù)進(jìn)行遷移.遷移的目的是將讀操作密集的負(fù)載放在SSD上存儲(chǔ),而寫(xiě)操作密集的數(shù)據(jù)則保留在磁盤(pán)上.I-CASH提出將SSD和磁盤(pán)進(jìn)行成對(duì)組合,采用智能算法將較長(zhǎng)時(shí)間不被修改的數(shù)據(jù)和讀操作密集的數(shù)據(jù)存放在SSD,以日志的方式記錄對(duì)SSD數(shù)據(jù)的修改并增量存儲(chǔ)于磁盤(pán),I-CASH盡量避免對(duì)SSD產(chǎn)生隨機(jī)寫(xiě)操作,讀數(shù)據(jù)時(shí)通過(guò)相似度探測(cè)獲得數(shù)據(jù)的最新版本;數(shù)據(jù)庫(kù)系統(tǒng)中通常包含許多訪問(wèn)特征明顯的特定類(lèi)型數(shù)據(jù).比如,為了保證數(shù)據(jù)庫(kù)的一致性,日志需要在事務(wù)提交之前先行寫(xiě)入外存,預(yù)寫(xiě)日志引發(fā)頻繁的磁盤(pán)訪問(wèn),將嚴(yán)重影響數(shù)據(jù)庫(kù)系統(tǒng)整體性能的提升.用SSD存儲(chǔ)這些特定類(lèi)型數(shù)據(jù)可以減輕磁盤(pán)的I/O壓力.Hystor系統(tǒng)通過(guò)識(shí)別算法發(fā)現(xiàn)影響系統(tǒng)性能的關(guān)鍵數(shù)據(jù)塊并將它們備份到SSD,待SSD完成對(duì)這些數(shù)據(jù)塊的修改再將新數(shù)據(jù)重新寫(xiě)回磁盤(pán).用SSD存儲(chǔ)查詢連接操作過(guò)程中生成的臨時(shí)表、中間結(jié)果等數(shù)據(jù)也可以有效提升循環(huán)嵌套、Hash、排序-合并等連接算法的性能;為了對(duì)比混合存儲(chǔ)的系統(tǒng)性能,我們搭建了基于三星MZ-7PD型SSD和磁盤(pán)的混合存儲(chǔ)平臺(tái),并在磁盤(pán)、混合存儲(chǔ)和SSD3種不同的存儲(chǔ)架構(gòu)下對(duì)PostgreSQL數(shù)據(jù)庫(kù)系統(tǒng)的性能進(jìn)行了測(cè)試.SSD在混合存儲(chǔ)環(huán)境中的作用是存儲(chǔ)日志文件和系統(tǒng)表數(shù)據(jù).TPC-C測(cè)試采用BenchmarkSQL分別對(duì)10個(gè)和200個(gè)數(shù)據(jù)倉(cāng)庫(kù)進(jìn)行事務(wù)處理性能測(cè)試,實(shí)驗(yàn)結(jié)果如圖9(a)所示,在混合存儲(chǔ)環(huán)境下,PostgreSQL數(shù)據(jù)庫(kù)每秒處理的事務(wù)數(shù)(tpmC)比磁盤(pán)存儲(chǔ)提高近1倍.數(shù)據(jù)庫(kù)系統(tǒng)的日志操作多以順序讀寫(xiě)為主,而對(duì)系統(tǒng)表的訪問(wèn)更多的是讀操作,因此,將日志和系統(tǒng)表分離存儲(chǔ)在SSD可以發(fā)揮SSD良好的順序讀寫(xiě)和快速隨機(jī)讀性能.3種存儲(chǔ)架構(gòu)下的TPC-H測(cè)試結(jié)果如圖9(b)所示,查詢數(shù)據(jù)流由22個(gè)復(fù)雜查詢和2個(gè)更新操作隨機(jī)組成,數(shù)據(jù)庫(kù)包含8張表,數(shù)據(jù)量為1GB.實(shí)驗(yàn)結(jié)果顯示,將特種數(shù)據(jù)存儲(chǔ)到SSD,多并發(fā)用戶下查詢處理吞吐提升的幅度為48.9%.4.2sd技術(shù)擴(kuò)展存儲(chǔ)層隨著內(nèi)存讀寫(xiě)速度的不斷提升,內(nèi)存和磁盤(pán)之間的性能鴻溝在持續(xù)變大.盡管大型數(shù)據(jù)中心配置的內(nèi)存容量越來(lái)越高,但數(shù)據(jù)的增長(zhǎng)遠(yuǎn)超過(guò)內(nèi)存容量的增長(zhǎng),簡(jiǎn)單的擴(kuò)充內(nèi)存容量不僅需要昂貴的財(cái)力支出,還要消耗大量能源.SSD的出現(xiàn)彌合了內(nèi)存和磁盤(pán)之間的性能差距,在內(nèi)存和磁盤(pán)之間添加SSD作擴(kuò)展緩存層可大幅提升緩沖區(qū)訪問(wèn)性能,緩解磁盤(pán)I/O壓力,縮短系統(tǒng)恢復(fù)時(shí)間.SSD作內(nèi)存擴(kuò)展的系統(tǒng)架構(gòu)見(jiàn)圖10.圖中SSD的作用是暫存從內(nèi)存置換出的數(shù)據(jù),當(dāng)內(nèi)存缺頁(yè)中斷時(shí),系統(tǒng)首先訪問(wèn)SSD中的數(shù)據(jù),若命中則將數(shù)據(jù)讀入內(nèi)存,否則從磁盤(pán)讀取數(shù)據(jù).SSD作擴(kuò)展緩存層最需要解決以下兩個(gè)核心問(wèn)題:(1)內(nèi)存中哪些數(shù)據(jù)在何時(shí)緩存到SSD.不同于單一類(lèi)型介質(zhì)的緩沖區(qū)管理,在異質(zhì)多級(jí)緩存環(huán)境下,緩沖區(qū)替換算法必須考慮數(shù)據(jù)頁(yè)的讀寫(xiě)狀態(tài)、數(shù)據(jù)訪問(wèn)形式和硬件自身特征等因素;(2)SSD中的數(shù)據(jù)怎樣組織并如何換出或?qū)懟卮疟P(pán).SSD暫存了從內(nèi)存被驅(qū)逐出的數(shù)據(jù),合理地組織存儲(chǔ)這些數(shù)據(jù)有助于內(nèi)存缺頁(yè)時(shí)快速識(shí)別并讀取SSD中的數(shù)據(jù).當(dāng)SSD可用空間低于設(shè)定條件時(shí),需要將部分?jǐn)?shù)據(jù)頁(yè)換出SSD,其中的臟頁(yè)需要寫(xiě)回磁盤(pán).設(shè)計(jì)適合SSD讀寫(xiě)特性的替換策略對(duì)系統(tǒng)性能的影響至關(guān)重要.4.2.1sd存儲(chǔ)特性文獻(xiàn)基于IBM的DB2數(shù)據(jù)庫(kù)系統(tǒng)提出了TAC緩存策略.TAC考慮數(shù)據(jù)訪問(wèn)的冷熱特性,以塊(32個(gè)數(shù)據(jù)頁(yè))為熱度計(jì)算單位,每次從磁盤(pán)讀數(shù)據(jù)都會(huì)計(jì)算該數(shù)據(jù)所在的塊是否滿足一定的熱度條件,若滿足則被緩存在SSD,如果SSD可用空間不足則選擇熱度最低的數(shù)據(jù)換出SSD.對(duì)于內(nèi)存換出的臟頁(yè),TAC同時(shí)寫(xiě)入SSD和磁盤(pán).文獻(xiàn)提出的LC緩存策略區(qū)別對(duì)待從內(nèi)存換出的干凈頁(yè)和臟頁(yè),提出了Clean-Write(CW)、Dual-Write(DW)、Lazy-Cleaning(LC)3種緩存策略.這里CW表示SSD只緩存從內(nèi)存置換出的干凈頁(yè);DW表示緩存內(nèi)存換出的臟頁(yè)和干凈頁(yè),臟頁(yè)被同時(shí)寫(xiě)入SSD和磁盤(pán);LC與DW的區(qū)別在于處理臟頁(yè)的策略不同,LC先將臟頁(yè)寫(xiě)入SSD,隨后再批量寫(xiě)入磁盤(pán).3種緩存策略對(duì)不同類(lèi)型訪問(wèn)負(fù)載表現(xiàn)出的性能有較大差異:(1)對(duì)于更新操作密集的負(fù)載,LC算法的性能相對(duì)較好.這是因?yàn)長(zhǎng)C能夠?qū)?duì)同一數(shù)據(jù)頁(yè)的多次修改經(jīng)過(guò)SSD的暫存而變成對(duì)磁盤(pán)的一次寫(xiě)操作,磁盤(pán)寫(xiě)操作的數(shù)量較少;(2)對(duì)于讀操作密集的負(fù)載,CW表現(xiàn)出更高的命中率,DW省去了LC處理臟頁(yè)的復(fù)雜管理代價(jià),所以在性能上要優(yōu)于LC.FaCE系統(tǒng)綜合考慮了SSD價(jià)格、隨機(jī)寫(xiě)操作性能差等因素,提出了一種經(jīng)濟(jì)有效的緩存管理策略.FaCE選擇SSD作為擴(kuò)展緩存,利用SSD的高速隨機(jī)讀性能和非易失性提高數(shù)據(jù)訪問(wèn)的吞吐量,降低系統(tǒng)恢復(fù)時(shí)間.FaCE系統(tǒng)的主要特點(diǎn)包括:(1)對(duì)于從內(nèi)存被驅(qū)逐進(jìn)入SSD的數(shù)據(jù),FaCE以順序追加的方式寫(xiě)入SSD,對(duì)于SSD已經(jīng)存在的舊版本數(shù)據(jù)FaCE予以保留,這避免了對(duì)SSD的隨機(jī)寫(xiě)操作;(2)FaCE擴(kuò)充了事務(wù)檢查點(diǎn)機(jī)制和恢復(fù)模塊,以組提交的方式周期性地將記錄緩存數(shù)據(jù)的元信息寫(xiě)入SSD,通過(guò)快速掃描存儲(chǔ)在SSD中的元數(shù)據(jù),使系統(tǒng)恢復(fù)時(shí)間顯著降低.OracleExadata(1)采用統(tǒng)計(jì)的方法將數(shù)據(jù)表、索引等熱數(shù)據(jù)緩存至SSD,內(nèi)存換出的干凈頁(yè)也緩存在SSD以提高命中率,數(shù)據(jù)庫(kù)系統(tǒng)性能提升較大.hStorage-DB實(shí)現(xiàn)了一個(gè)基于混合系統(tǒng)的數(shù)據(jù)存儲(chǔ)管理應(yīng)用框架.hStorage-DB底層采用SSD和磁盤(pán)的混合存儲(chǔ),SSD用作內(nèi)存的擴(kuò)展緩存.hStorage-DB為每一次I/O請(qǐng)求都賦予特定的語(yǔ)義信息,存儲(chǔ)管理器響應(yīng)I/O請(qǐng)求時(shí)根據(jù)語(yǔ)義信息執(zhí)行緩存策略.hStorage-DB為操作系統(tǒng)、文件系統(tǒng)以及數(shù)據(jù)庫(kù)系統(tǒng)添加了一個(gè)訪問(wèn)優(yōu)先級(jí)生成模塊,該模塊提取I/O請(qǐng)求攜帶的語(yǔ)義信息生成并特定的服務(wù)質(zhì)量——QoS(QualityofService),這里QoS實(shí)際上指的是頁(yè)面進(jìn)入或換出SSD的優(yōu)先級(jí).存儲(chǔ)管理器根據(jù)QoS對(duì)SSD和磁盤(pán)中的數(shù)據(jù)進(jìn)行寫(xiě)入、讀取、遷移等操作.hStorage-DB彌補(bǔ)了存儲(chǔ)系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)之間I/O語(yǔ)義信息的缺失,存儲(chǔ)處理不受負(fù)載訪問(wèn)動(dòng)態(tài)變化的影響.hStorage-DB對(duì)數(shù)據(jù)庫(kù)系統(tǒng)特別是復(fù)雜的OLAP應(yīng)用和高并發(fā)負(fù)載訪問(wèn)性能提升幅度比較大,對(duì)不同類(lèi)型負(fù)載的查詢處理性能均有提升.表7列出了目前主要的幾個(gè)緩存系統(tǒng).4.2.2sd存儲(chǔ)策略為了驗(yàn)證多級(jí)緩存系統(tǒng)的性能,本文對(duì)已有的部分緩存策略進(jìn)行了實(shí)驗(yàn)對(duì)比,我們基于disksim4.0(2)和SSDModel設(shè)計(jì)實(shí)現(xiàn)了一個(gè)多級(jí)緩存實(shí)驗(yàn)仿真平臺(tái).實(shí)驗(yàn)代碼使用C實(shí)現(xiàn),操作系統(tǒng)為Ubuntu12.10,頁(yè)面大小4KB,緩沖區(qū)大小4MB.驗(yàn)證緩存策略包括LRU-Through、CW、LC和FaCE.其中LRU-Through部分實(shí)現(xiàn)了Exadata的管理策略,內(nèi)存置換出的臟數(shù)據(jù)將被同步寫(xiě)回閃存和磁盤(pán),CW和LC是文獻(xiàn)提到的兩種策略.實(shí)驗(yàn)所用的兩個(gè)數(shù)據(jù)集基于TPC-C標(biāo)準(zhǔn),采用BenchmarkSQL運(yùn)行PostgreSQL獲得.數(shù)據(jù)集的統(tǒng)計(jì)信息如表8所示.在不同的SSD和內(nèi)存的容量比下,實(shí)驗(yàn)統(tǒng)計(jì)了T1和T2的運(yùn)行時(shí)間,圖11(a)描述了數(shù)據(jù)集T1在4種緩存架構(gòu)下的運(yùn)行時(shí)間.從結(jié)果來(lái)看,FaCE緩存策略的性能相對(duì)較好,因?yàn)镕aCE系統(tǒng)采用順序追加的方式處理從內(nèi)存置換出的數(shù)據(jù),SSD數(shù)據(jù)管理的代價(jià)相對(duì)較低.其它3種緩存策略的差異并不是很大,特別是CW和LC替換策略,原因在于數(shù)據(jù)集T1是讀操作比較密集的負(fù)載,基于干凈頁(yè)的緩存策略降低了算法執(zhí)行的復(fù)雜度,系統(tǒng)資源消耗少.LRU-Through以LRU方式管理SSD中數(shù)據(jù),緩存性能不如CW的LRU-K算法.數(shù)據(jù)集T2比T1有更多的寫(xiě)操作,正如圖11(b)所示,LC和FaCE策略在處理臟頁(yè)方面的性能優(yōu)勢(shì)體現(xiàn)得更加明顯.特別是FaCE系統(tǒng),隨著SSD容量的增大,系統(tǒng)運(yùn)行時(shí)間顯著減少,當(dāng)SSD和內(nèi)存的容量比超過(guò)20之后,性能提升幅度開(kāi)始變小,這是因?yàn)镾SD對(duì)無(wú)效數(shù)據(jù)頁(yè)回收的代價(jià)影響了系統(tǒng)性能的提升.5未來(lái)工作的展望結(jié)合新硬件發(fā)展趨勢(shì)和現(xiàn)有的閃存數(shù)據(jù)管理特點(diǎn),我們認(rèn)為以下幾個(gè)方面是未來(lái)的研究方向.5.1存儲(chǔ)層密度結(jié)構(gòu)隨著越來(lái)越多應(yīng)用技術(shù)的出現(xiàn)和發(fā)展,數(shù)據(jù)的增長(zhǎng)已經(jīng)完全失去控制,對(duì)業(yè)務(wù)運(yùn)行也造成了影響,構(gòu)建面向企業(yè)級(jí)應(yīng)用的超大數(shù)據(jù)管理系統(tǒng)是解決海量數(shù)據(jù)存儲(chǔ)和管理等問(wèn)題的必由之路.主要研究?jī)?nèi)容包括如下幾個(gè)方面:基于閃存的新硬件特性和大數(shù)據(jù)呈現(xiàn)的多樣性,合理的數(shù)據(jù)分布會(huì)加快數(shù)據(jù)的訪問(wèn)性能.數(shù)據(jù)管理體系的各個(gè)環(huán)節(jié)必須相應(yīng)的調(diào)整管理策略以適應(yīng)新型存儲(chǔ)的特性.關(guān)系數(shù)據(jù)庫(kù)技術(shù)在可擴(kuò)展性方面存在不足.近年來(lái),在超大數(shù)據(jù)管理系統(tǒng)方面,基于閃存的NoSQL數(shù)據(jù)庫(kù)技術(shù)成為熱門(mén)的研究點(diǎn);低能耗已逐漸成為計(jì)算機(jī)存儲(chǔ)系統(tǒng)的一項(xiàng)關(guān)鍵挑戰(zhàn).將閃存引入大規(guī)模據(jù)管理系統(tǒng)非常有助于解決能耗和高吞吐等方面的嚴(yán)峻挑戰(zhàn).一方面,引入閃存使得緩存空間顯著增大,能獲得更高的緩存命中率從而顯著降低對(duì)磁盤(pán)的訪問(wèn)密度,在存儲(chǔ)層內(nèi)部可以通過(guò)傾斜的數(shù)據(jù)分布,使部分磁盤(pán)存儲(chǔ)冷門(mén)數(shù)據(jù)來(lái)增加空閑時(shí)間達(dá)到節(jié)能的目的,另一方面,引入閃存可以顯著減少內(nèi)存的使用,從而降低緩存層自身的能耗;閃存有限的使用壽命是構(gòu)建大數(shù)據(jù)管理必須要考慮的問(wèn)題.設(shè)計(jì)閃存友好的算法和應(yīng)用有利于保證系統(tǒng)的可靠性和可用性.5.2高效動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)基于閃存的混合存儲(chǔ)系統(tǒng)為構(gòu)建高性能、可擴(kuò)展的海量數(shù)據(jù)管理提供了一種經(jīng)濟(jì)有效的途徑.文獻(xiàn)中,作者基于閃存構(gòu)建的多級(jí)緩存系統(tǒng)極大提升了數(shù)據(jù)庫(kù)系統(tǒng)的恢復(fù)性能.混合存儲(chǔ)數(shù)據(jù)管理必須能夠動(dòng)態(tài)的調(diào)整外存系統(tǒng)中保存的數(shù)據(jù),根據(jù)數(shù)據(jù)和閃存特性合理地分配數(shù)據(jù)存儲(chǔ)位置來(lái)獲得性能和價(jià)格的最佳比.數(shù)據(jù)分類(lèi)、數(shù)據(jù)分布、數(shù)據(jù)遷移等是混合數(shù)據(jù)庫(kù)系統(tǒng)需要解決的關(guān)鍵技術(shù).在混合存儲(chǔ)數(shù)據(jù)管理系統(tǒng)中,閃存設(shè)