亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        一種基于裸閃存的Key-Value數(shù)據(jù)庫(kù)優(yōu)化方法

        2017-06-23 12:48:13秦雄軍張佳程陸游游舒繼武
        關(guān)鍵詞:內(nèi)存架構(gòu)調(diào)度

        秦雄軍 張佳程 陸游游 舒繼武

        (清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084)

        一種基于裸閃存的Key-Value數(shù)據(jù)庫(kù)優(yōu)化方法

        秦雄軍 張佳程 陸游游 舒繼武

        (清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084)

        (qinxiongjun2010@163.com)

        近年來(lái),非關(guān)系型的key-value數(shù)據(jù)庫(kù)得到越來(lái)越廣泛的應(yīng)用.然而,目前主流的key-value數(shù)據(jù)庫(kù)或者是基于磁盤設(shè)計(jì)的,或者是傳統(tǒng)的基于文件系統(tǒng)和閃存轉(zhuǎn)換層FTL來(lái)構(gòu)建的,難以發(fā)揮閃存存儲(chǔ)設(shè)備的特性,限制了I/O的并發(fā)性能,且垃圾回收過(guò)程復(fù)雜.設(shè)計(jì)并實(shí)現(xiàn)了一種基于裸閃存的key-value數(shù)據(jù)管理架構(gòu)Flashkv,通過(guò)用戶態(tài)下的管理單元進(jìn)行空間管理和垃圾回收,充分利用了閃存設(shè)備內(nèi)部的并發(fā)特性,并簡(jiǎn)化了垃圾回收過(guò)程,去除了傳統(tǒng)文件系統(tǒng)和FTL中的冗余功能,縮短了I/O路徑.提出了基于閃存特點(diǎn)的I/O調(diào)度技術(shù),優(yōu)化了閃存的讀寫(xiě)延遲,提高了吞吐率;提出了用戶態(tài)緩存管理技術(shù),降低了數(shù)據(jù)寫(xiě)入量和頻繁系統(tǒng)調(diào)用所帶來(lái)的開(kāi)銷.測(cè)試結(jié)果表明,F(xiàn)lashkv性能是levelDB的1.9~2.2倍,寫(xiě)入量減少60%~65%.

        key-value數(shù)據(jù)庫(kù);閃存;裸設(shè)備;數(shù)據(jù)存儲(chǔ);使用壽命

        基于鍵值對(duì)(key-value)的key-value數(shù)據(jù)庫(kù)是一種非關(guān)系型數(shù)據(jù)庫(kù),同傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)相比,它僅支持對(duì)主鍵的檢索查詢,不需要維護(hù)不必要的開(kāi)銷,因而效率很高.隨著Web2.0時(shí)代和大數(shù)據(jù)時(shí)代的到來(lái),數(shù)據(jù)庫(kù)等存儲(chǔ)系統(tǒng)對(duì)可擴(kuò)展性和可靠性的要求越來(lái)越高[1-2].傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)由于對(duì)SQL語(yǔ)句的嚴(yán)格支持和對(duì)事務(wù)的支持,性能表現(xiàn)不佳,且關(guān)系型數(shù)據(jù)庫(kù)的這些特性在當(dāng)前眾多的網(wǎng)絡(luò)應(yīng)用中不是必需的.key-value數(shù)據(jù)庫(kù)由于其內(nèi)部松散的耦合性,使得其具有傳統(tǒng)數(shù)據(jù)庫(kù)不具有的擴(kuò)展性[3].由于基于key-value的非關(guān)系型數(shù)據(jù)庫(kù)具有良好的擴(kuò)展性、可靠性以及較高的性能,使其在大數(shù)據(jù)時(shí)代得到了廣泛的應(yīng)用[4-5].另外,近年來(lái),閃存(flash memory)由于其遠(yuǎn)高于磁盤的I/O性能和不斷下降的成本也越來(lái)越普及[6-7],特別是閃存設(shè)備具有很多特性,比如其內(nèi)部豐富的并發(fā)讀寫(xiě)單元[8]、隨機(jī)讀寫(xiě)性能高,在閃存環(huán)境下部署key-value數(shù)據(jù)庫(kù)就成為一種選擇[9-10].然而,很多key-value數(shù)據(jù)庫(kù)系統(tǒng)都是基于傳統(tǒng)磁盤設(shè)計(jì)的,如levelDB,這些系統(tǒng)在設(shè)計(jì)之初就沒(méi)有考慮到閃存設(shè)備的并發(fā)特性和垃圾回收特性,使得這些系統(tǒng)還不能充分發(fā)揮底層閃存設(shè)備的性能.

        在閃存環(huán)境下,傳統(tǒng)的基于文件系統(tǒng)和閃存轉(zhuǎn)換層(flash translation layer, FTL)的key-value數(shù)據(jù)庫(kù)存在4個(gè)問(wèn)題:

        1) 閃存設(shè)備的并發(fā)性能難以得到充分利用.在傳統(tǒng)架構(gòu)中,數(shù)據(jù)在閃存設(shè)備上的物理布局由文件系統(tǒng)和FTL共同決定,對(duì)上層數(shù)據(jù)庫(kù)是透明的,這種情況下閃存設(shè)備內(nèi)部的并發(fā)特性很難被充分利用.

        2) 垃圾回收復(fù)雜.閃存具有2個(gè)重要特性:不能原地更新和讀寫(xiě)與擦除的不對(duì)稱性,因此閃存設(shè)備使用一段時(shí)間后需要垃圾回收.使用FTL的閃存設(shè)備進(jìn)行垃圾回收時(shí),需要先選擇目標(biāo)塊,然后讀出目標(biāo)塊中的有效頁(yè),寫(xiě)入到新的地址,修改映射表,最后才能擦除目標(biāo)塊.整個(gè)過(guò)程不僅復(fù)雜耗時(shí),而且容易造成嚴(yán)重的寫(xiě)放大[11].

        3) 文件系統(tǒng)和FTL中的某些功能重復(fù)冗余.文件系統(tǒng)和FTL中都有負(fù)責(zé)空間分配和垃圾回收的功能,這些功能存在冗余,帶來(lái)額外開(kāi)銷.

        4) I/O路徑過(guò)長(zhǎng)的問(wèn)題.基于通用文件系統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng),其讀寫(xiě)請(qǐng)求需要依次經(jīng)過(guò)內(nèi)核的虛擬文件系統(tǒng)(VFS)、頁(yè)高速緩存、文件系統(tǒng)管理層、通用塊層、驅(qū)動(dòng)層才能到達(dá)物理設(shè)備,整個(gè)過(guò)程十分復(fù)雜且耗時(shí).

        傳統(tǒng)的基于文件系統(tǒng)和FTL的key-value數(shù)據(jù)庫(kù)系統(tǒng)沒(méi)有考慮到閃存設(shè)備的特點(diǎn),在閃存設(shè)備上性能表現(xiàn)不佳[12-13],因此,針對(duì)閃存的特點(diǎn)設(shè)計(jì)一種key-value數(shù)據(jù)庫(kù)架構(gòu)具有重要意義.

        本文提出了一種基于裸閃存設(shè)備構(gòu)建key-value數(shù)據(jù)庫(kù)系統(tǒng)的方法,并基于該方法實(shí)現(xiàn)了一個(gè)key-value數(shù)據(jù)庫(kù)Flashkv.Flashkv結(jié)合閃存設(shè)備的具體特點(diǎn),綜合考慮了文件系統(tǒng)和FTL與數(shù)據(jù)庫(kù)的關(guān)系,克服了直接將傳統(tǒng)數(shù)據(jù)庫(kù)移植到閃存設(shè)備上的缺陷.Flashkv的主要思想是通過(guò)一個(gè)管理單元直接對(duì)裸閃存設(shè)備進(jìn)行管理,包括空間分配、垃圾回收、I/O請(qǐng)求調(diào)度.這種實(shí)現(xiàn)能夠使I/O請(qǐng)求繞過(guò)通用文件系統(tǒng)和閃存轉(zhuǎn)換層,減少了軟件棧帶來(lái)的開(kāi)銷,去除了傳統(tǒng)文件系統(tǒng)和FTL中的冗余功能,縮短了I/O路徑.Flashkv能夠充分利用閃存設(shè)備的并發(fā)特性,大大簡(jiǎn)化垃圾回收過(guò)程.本文還提出了基于閃存特點(diǎn)的I/O調(diào)度技術(shù),優(yōu)化了閃存的讀寫(xiě)延遲,提高了吞吐率;提出了用戶態(tài)緩存管理技術(shù),降低了數(shù)據(jù)寫(xiě)入量和頻繁系統(tǒng)調(diào)用所帶來(lái)的開(kāi)銷.

        1 相關(guān)工作

        key-value型數(shù)據(jù)庫(kù)是傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的一個(gè)簡(jiǎn)化,通過(guò)去掉很多不必要的特性,key-value數(shù)據(jù)庫(kù)能使自己的性能優(yōu)勢(shì)最大,數(shù)據(jù)之間的耦合度最低.key-value數(shù)據(jù)庫(kù)有3種流行的實(shí)現(xiàn)方式:1)通過(guò)B+樹(shù)實(shí)現(xiàn),例如Tokyocabinet[14].B+樹(shù)通過(guò)增加每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目來(lái)盡可能減小整棵樹(shù)的高度,從而減少外存設(shè)備的讀寫(xiě)次數(shù).其優(yōu)點(diǎn)是查詢效率較高;缺點(diǎn)是大量隨機(jī)寫(xiě)容易造成節(jié)點(diǎn)碎片化,導(dǎo)致性能下降.2)基于Hash表實(shí)現(xiàn),例如redis[15],SkimpyStash[16],基于Hash表實(shí)現(xiàn)的優(yōu)點(diǎn)是查詢效率高,缺點(diǎn)是不能支持范圍查詢,當(dāng)出現(xiàn)大量Hash值碰撞時(shí)會(huì)導(dǎo)致效率下降.3)基于Log-Structured-Merge tree[17](LSM tree)實(shí)現(xiàn),例如levelDB[18],Hbase[19],其優(yōu)點(diǎn)是寫(xiě)入性能很高,缺點(diǎn)是讀性能表現(xiàn)不佳且容易造成嚴(yán)重的寫(xiě)放大.

        基于SSD的key-value數(shù)據(jù)庫(kù),目前有很多工作.Shen Zhaoyan等人[12]提出了一種基于Hash表的key-value系統(tǒng),消除了Hash表和FTL的地址映射表存在的冗余映射的問(wèn)題.Flashkv消除了文件系統(tǒng)的空間管理和FTL的地址映射表的冗余.文獻(xiàn)[12]還提出了將數(shù)據(jù)庫(kù)的垃圾回收和FTL的垃圾回收過(guò)程相結(jié)合,但其垃圾回收過(guò)程仍然與傳統(tǒng)FTL中的垃圾回收過(guò)程類似,而Flashkv由于其特殊的數(shù)據(jù)布局,其垃圾回收過(guò)程異常簡(jiǎn)單.王鵬等人提出的LOCS[13]把levelDB移植到了SSD設(shè)備上,并使用了I/O調(diào)度等策略加速寫(xiě)請(qǐng)求.LOCS把一個(gè)數(shù)據(jù)庫(kù)文件存儲(chǔ)在一個(gè)閃存通道中,不同的文件分布在不同的通道上,達(dá)到并發(fā)讀寫(xiě)的目的.Flashkv采用的物理布局與LOCS不同,F(xiàn)lashkv把一個(gè)文件的數(shù)據(jù)分散在多個(gè)通道上,提高單個(gè)文件讀寫(xiě)的并發(fā)度;此外,LOCS的I/O調(diào)度是為了保證所有通道的利用率盡量均衡,而Flashkv的I/O調(diào)度技術(shù)則是為了保證數(shù)據(jù)庫(kù)中重要而緊迫的請(qǐng)求優(yōu)先得到執(zhí)行.

        LSM tree數(shù)據(jù)結(jié)構(gòu)采用日志更新的方式,將隨機(jī)寫(xiě)操作順序地寫(xiě)入磁盤.LSM tree具有良好的寫(xiě)入性能,但為了降低讀性能的開(kāi)銷,LSM tree引入了compaction操作,對(duì)亂序?qū)懭氲膋ey-value對(duì)進(jìn)行重新排序,這個(gè)操作會(huì)引起較大的寫(xiě)放大.Wu等人分析了LSM tree的寫(xiě)放大的特征,并提出了LSM-trie,可以極大地減少寫(xiě)入量,提升系統(tǒng)性能[20].Lu等人提出將key值和value值分離存放的策略[21],在每次compaction過(guò)程中只需要讀取key值即可,極大地減小了LSM tree的寫(xiě)放大,有效提高了基于LSM tree的系統(tǒng)性能.

        Fig. 1 levelDB illustration圖1 levelDB示意圖

        levelDB[18]是一個(gè)開(kāi)源的key-value數(shù)據(jù)庫(kù),其核心使用了LSM tree數(shù)據(jù)結(jié)構(gòu)[17].在levelDB中,用戶的插入首先寫(xiě)入到圖1的可變內(nèi)存表(mutable table)中,當(dāng)可變內(nèi)存表寫(xiě)滿時(shí),可變內(nèi)存表轉(zhuǎn)變?yōu)椴豢勺儍?nèi)存表(immutable table),同時(shí)levelDB重新生成一張可變內(nèi)存表,不可變內(nèi)存表中的數(shù)據(jù)會(huì)在后臺(tái)寫(xiě)入到磁盤的0層中.在levelDB的磁盤布局中,不同的數(shù)據(jù)文件分布在不同的層(level),如圖1所示.當(dāng)某一層文件過(guò)多時(shí),levelDB會(huì)進(jìn)行compaction操作,從該層選取若干文件,將這些文件中的key-value對(duì)讀入內(nèi)存,重新排序后再以文件的形式寫(xiě)入下一層.在處理查找請(qǐng)求時(shí),levelDB首先在mutable table中查找,然后在immutable table中查找,若沒(méi)有找到,則按照 level 0,level 1的順序依次查找每層文件,在以上過(guò)程中任一步驟找到指定key值時(shí)即可返回.

        和所有基于LSM的key-value數(shù)據(jù)庫(kù)一樣,levelDB是一個(gè)寫(xiě)友好的數(shù)據(jù)庫(kù),其寫(xiě)入操作只需直接寫(xiě)入內(nèi)存的可變內(nèi)存表中即可.但levelDB讀操作較慢,最壞情況下需要多次查找,涉及到多次磁盤操作.

        另外,levelDB是基于文件系統(tǒng)實(shí)現(xiàn)的,而文件系統(tǒng)運(yùn)行在閃存設(shè)備的FTL之上,這種模型的架構(gòu)如圖2所示.在該模型下,levelDB使用文件系統(tǒng)提供的POSIX API進(jìn)行文件讀寫(xiě)等操作,文件系統(tǒng)負(fù)責(zé)空間管理、地址映射、垃圾回收等功能,F(xiàn)TL通過(guò)空間管理、地址映射和垃圾回收等功能模塊,把裸閃存設(shè)備抽象成一個(gè)通用塊設(shè)備提供給上層文件系統(tǒng).

        Fig. 2 Architectue of traditional key-value database圖2 傳統(tǒng)key-value數(shù)據(jù)庫(kù)架構(gòu)

        這種存儲(chǔ)架構(gòu)存在著功能單元冗余、垃圾回收過(guò)程復(fù)雜、I/O路徑長(zhǎng)等缺點(diǎn).閃存設(shè)備的并發(fā)特性也難以被充分利用.由文件系統(tǒng)和FTL進(jìn)行空間分配,數(shù)據(jù)的物理布局對(duì)上層數(shù)據(jù)庫(kù)軟件是透明的,數(shù)據(jù)庫(kù)無(wú)法自己控制數(shù)據(jù)的物理布局,因此,SSD設(shè)備的并發(fā)特性難以被充分利用.其次是復(fù)雜的垃圾回收.由于閃存設(shè)備的特點(diǎn),導(dǎo)致這種傳統(tǒng)存儲(chǔ)架構(gòu)下的垃圾回收過(guò)程非常復(fù)雜,造成嚴(yán)重的寫(xiě)放大,影響閃存設(shè)備壽命.此外,該架構(gòu)下多個(gè)功能單元冗余.如圖2所示,上層文件系統(tǒng)中的垃圾回收單元和FTL中的垃圾回收模塊重復(fù);文件系統(tǒng)中負(fù)責(zé)空間管理的模塊和FTL中的空間管理模塊重復(fù);文件系統(tǒng)中的地址映射與FTL中的映射表也存在功能上的冗余.另外,該架構(gòu)下I/O路徑過(guò)長(zhǎng).從levelDB發(fā)出的讀寫(xiě)請(qǐng)求經(jīng)系統(tǒng)調(diào)用,依次經(jīng)由VFS、具體文件系統(tǒng)、FTL,I/O路徑較長(zhǎng),引入了不必要的軟件開(kāi)銷.

        總之,這些基于key-value的數(shù)據(jù)庫(kù)或者是基于磁盤設(shè)計(jì)的,或者是傳統(tǒng)的基于文件系統(tǒng)和閃存轉(zhuǎn)換層FTL來(lái)構(gòu)建的,難以發(fā)揮閃存存儲(chǔ)設(shè)備的特性,限制了I/O的并發(fā)性能.

        2 Flashkv架構(gòu)設(shè)計(jì)

        本文提出了一種基于裸閃存設(shè)備構(gòu)建key-value數(shù)據(jù)庫(kù)系統(tǒng)的方法,并基于該方法實(shí)現(xiàn)了一個(gè)key-value數(shù)據(jù)庫(kù)Flashkv,架構(gòu)如圖3所示.該架構(gòu)中,F(xiàn)lashkv繞過(guò)了文件系統(tǒng)層和SSD的FTL層,將levelDB直接構(gòu)建于裸閃存設(shè)備上.Flashkv整體架構(gòu)主要包含管理單元與I/O調(diào)度器兩大模塊,其中管理單元負(fù)責(zé)閃存空間管理、垃圾回收、讀寫(xiě)接口和緩存管理.

        Fig. 3 Architecture of Flashkv圖3 Flashkv架構(gòu)圖

        在管理單元中,空間管理負(fù)責(zé)物理地址的分配和文件名到物理地址的映射.Flashkv采用了塊對(duì)齊的分配方式,將文件以塊為單位分布到閃存的每個(gè)通道中,保證閃存設(shè)備內(nèi)部的并發(fā)特性得到充分利用.垃圾回收負(fù)責(zé)對(duì)無(wú)效的閃存塊進(jìn)行擦除與回收,由于物理地址的分配以塊對(duì)齊的方式進(jìn)行,因此垃圾回收過(guò)程十分簡(jiǎn)單.緩存系統(tǒng)是在用戶態(tài)模擬了虛擬文件系統(tǒng)中的頁(yè)高速緩存,對(duì)數(shù)據(jù)庫(kù)的讀寫(xiě)請(qǐng)求進(jìn)行緩存,可以避免用戶態(tài)和內(nèi)核態(tài)的頻繁切換.讀寫(xiě)接口負(fù)責(zé)與I/O調(diào)度器進(jìn)行交互,把數(shù)據(jù)庫(kù)產(chǎn)生的讀寫(xiě)請(qǐng)求交給內(nèi)核態(tài)的I/O調(diào)度器處理.管理單元整合了原來(lái)分別位于文件系統(tǒng)和FTL中的空間管理、垃圾回收等模塊的功能,避免了這些功能的冗余開(kāi)銷,縮短了I/O路徑.

        在管理單元之下,F(xiàn)lashkv使用一個(gè)I/O調(diào)度器,對(duì)I/O請(qǐng)求進(jìn)行有效調(diào)度.Flashkv在運(yùn)行過(guò)程中會(huì)產(chǎn)生很多讀寫(xiě)和擦除請(qǐng)求,這些請(qǐng)求的重要程度和緊急程度不同,I/O調(diào)度器接收用戶態(tài)的讀寫(xiě)接口模塊提交的讀寫(xiě)請(qǐng)求,根據(jù)請(qǐng)求的緊迫程度賦予它們不同的優(yōu)先級(jí),并優(yōu)先調(diào)度那些優(yōu)先級(jí)較高的請(qǐng)求,從而加速讀寫(xiě)過(guò)程,提升系統(tǒng)性能.

        在新的架構(gòu)下,F(xiàn)lashkv由管理單元和I/O調(diào)度器2部分組成.原來(lái)分別位于文件系統(tǒng)和FTL中的空間管理模塊和垃圾回收模塊得到整合,且SSD設(shè)備并發(fā)特性得到充分利用,垃圾回收過(guò)程大大簡(jiǎn)化.Flashkv的讀寫(xiě)請(qǐng)求只需要經(jīng)過(guò)管理單元和I/O調(diào)度器就可以到達(dá)裸閃存設(shè)備,I/O路徑也大大縮短.

        3 關(guān)鍵技術(shù)

        Flashkv主要采用了LSM tree的數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)并實(shí)現(xiàn)了用戶態(tài)的管理單元、I/O調(diào)度優(yōu)化和雙線程compaction三個(gè)關(guān)鍵技術(shù).通過(guò)用戶態(tài)管理單元,F(xiàn)lashkv可以在用戶態(tài)對(duì)物理閃存設(shè)備進(jìn)行空間管理和垃圾回收,從而能夠更好地利用閃存設(shè)備的并發(fā)特性,簡(jiǎn)化垃圾回收過(guò)程;通過(guò)I/O調(diào)度技術(shù),F(xiàn)lashkv可以優(yōu)先處理前臺(tái)的I/O請(qǐng)求,從而提高整體性能;通過(guò)雙線程技術(shù),F(xiàn)lashkv的compaction過(guò)程能夠得到加速處理,避免大量文件堆積在level 0造成阻塞.

        3.1 管理單元

        在Flashkv中,管理單元負(fù)責(zé)空間管理、緩存管理、垃圾回收、讀寫(xiě)接口等功能.LSM tree將用戶的插入、查詢請(qǐng)求轉(zhuǎn)換成文件的讀寫(xiě)請(qǐng)求,發(fā)送到管理單元上.管理單元通過(guò)空間管理對(duì)請(qǐng)求進(jìn)行物理地址分配和映射;通過(guò)用戶態(tài)的緩存對(duì)數(shù)據(jù)進(jìn)行管理,并通過(guò)讀寫(xiě)接口向I/O調(diào)度器發(fā)送讀寫(xiě)請(qǐng)求.當(dāng)levelDB發(fā)出刪除文件的請(qǐng)求時(shí),管理單元回收閃存設(shè)備上的物理地址,并向I/O調(diào)度器發(fā)送擦除請(qǐng)求擦除對(duì)應(yīng)的物理閃存塊.

        和levelDB使用文件系統(tǒng)進(jìn)行空間分配不同,F(xiàn)lashkv使用管理單元直接進(jìn)行物理閃存空間的分配和管理.這樣,F(xiàn)lashkv可以自己決定數(shù)據(jù)在閃存設(shè)備上的物理布局,從而可以更好地發(fā)揮設(shè)備內(nèi)部的并發(fā)特性,提升讀寫(xiě)速度;可以更有效率地進(jìn)行垃圾回收,且顯著減少寫(xiě)入量,延長(zhǎng)設(shè)備壽命.

        3.1.1 空間管理

        傳統(tǒng)數(shù)據(jù)庫(kù)由文件系統(tǒng)進(jìn)行邏輯空間管理,使用閃存轉(zhuǎn)換層進(jìn)行物理地址管理,上層數(shù)據(jù)庫(kù)軟件對(duì)底層的數(shù)據(jù)布局一無(wú)所知.在這種情況下,數(shù)據(jù)庫(kù)軟件很難根據(jù)自身的特點(diǎn)安排合理的數(shù)據(jù)布局.而數(shù)據(jù)布局的好壞對(duì)整個(gè)數(shù)據(jù)庫(kù)系統(tǒng)的性能有重要影響.這種影響主要體現(xiàn)在2個(gè)方面:

        1) 對(duì)并發(fā)度的影響,不恰當(dāng)?shù)臄?shù)據(jù)布局無(wú)法充分利用設(shè)備的并行特性,容易造成一部分閃存通道讀寫(xiě)繁忙、一部分閃存通道空閑的現(xiàn)象;

        2) 對(duì)垃圾回收的影響,不恰當(dāng)?shù)臄?shù)據(jù)布局會(huì)造成垃圾回收負(fù)擔(dān)加重,從而影響前臺(tái)的讀寫(xiě)性能,還導(dǎo)致嚴(yán)重的寫(xiě)放大,嚴(yán)重影響設(shè)備壽命.

        通過(guò)空間管理單元,F(xiàn)lashkv能夠在用戶態(tài)對(duì)物理空間進(jìn)行分配和管理,而不借助于文件系統(tǒng)和閃存轉(zhuǎn)換層.因?yàn)镕lashkv能夠完全感知和控制底層的數(shù)據(jù)布局,F(xiàn)lashkv能夠克服上述2個(gè)缺點(diǎn),即能夠充分利用多個(gè)數(shù)據(jù)通道,從而加速讀寫(xiě)過(guò)程;能夠簡(jiǎn)化垃圾回收過(guò)程,進(jìn)而減少后臺(tái)垃圾回收對(duì)前臺(tái)讀寫(xiě)的影響且降低寫(xiě)放大.

        現(xiàn)代SSD設(shè)備一般包含多個(gè)通道,通道之間可以并行執(zhí)行指令,互不影響,稱之為設(shè)備的內(nèi)部并發(fā)度(internal parallelism)[9].為了充分利用閃存設(shè)備的這種特性,F(xiàn)lashkv采用了一種條帶化的分配方式,文件的內(nèi)容以閃存頁(yè)大小(8 KB)為單位劃分成若干邏輯頁(yè).如圖4所示,文件的內(nèi)容被劃分為N=(k+1)n(k∈)個(gè)邏輯頁(yè),每個(gè)邏輯頁(yè)大小均為8 KB.第1個(gè)邏輯頁(yè)內(nèi)容寫(xiě)入到通道1中,第2個(gè)邏輯頁(yè)內(nèi)容寫(xiě)入到通道2中,以此類推,第i個(gè)邏輯頁(yè)被寫(xiě)入通道(i-1)%n+1中.

        為了簡(jiǎn)化垃圾回收過(guò)程,F(xiàn)lashkv的地址分配以行(line)為單位,按塊對(duì)齊.行是由每個(gè)通道內(nèi)偏移值相同的塊組成的,圖4中灰度相同的一組塊就稱為一行.由于LSM tree產(chǎn)生的每個(gè)數(shù)據(jù)文件大小基本一致,我們把每個(gè)文件大小設(shè)為一個(gè)定值,使其能夠以行為單位,分布在閃存的每個(gè)通道中.例如,F(xiàn)lashkv使用的裸閃存設(shè)備每個(gè)物理塊大小為2 MB,有32個(gè)通道,每個(gè)文件的大小設(shè)置為64 MB.空間的分配以塊對(duì)齊的方式進(jìn)行,這種對(duì)齊體現(xiàn)在每個(gè)通道上分配給該文件的閃存塊在各自通道上的偏移值都相同.

        Fig. 4 Data layout of Flashkv圖4 Flashkv數(shù)據(jù)布局

        采用這種塊對(duì)齊的方式,記錄物理地址時(shí)只需記錄一個(gè)偏移量值即可,大大減少了元數(shù)據(jù)的大小.且數(shù)據(jù)內(nèi)容順序分布在不同通道上,讀取和寫(xiě)入時(shí)所有通道能夠并行進(jìn)行處理,最大限度利用閃存設(shè)備內(nèi)部的并發(fā)特性.采用塊對(duì)齊分配方式的另一個(gè)好處是垃圾回收過(guò)程大大簡(jiǎn)化.由于以行為單位進(jìn)行空間分配,同一個(gè)塊內(nèi)的所有頁(yè)面都屬于同一個(gè)文件,因此它們要么同時(shí)為無(wú)效頁(yè),要么同時(shí)為有效頁(yè).當(dāng)該文件刪除時(shí),F(xiàn)lashkv只需直接擦除相應(yīng)的閃存塊即可.

        3.1.2 用戶態(tài)緩存系統(tǒng)

        在傳統(tǒng)的文件系統(tǒng)中,頁(yè)高速緩存(page cache)有十分重要的作用.由于訪問(wèn)的局部性原理,最近訪問(wèn)過(guò)的頁(yè)面未來(lái)有很大的概率會(huì)再被訪問(wèn).因此只需要使用少量的內(nèi)存作為緩存,即可大大提升文件系統(tǒng)的性能.

        Fig. 5 Cache system of Flashkv圖5 Flashkv緩存系統(tǒng)

        Flashkv在用戶態(tài)實(shí)現(xiàn)了一個(gè)緩存系統(tǒng),以降低讀寫(xiě)延遲.和頁(yè)高速緩存類似,F(xiàn)lashkv緩存系統(tǒng)中每個(gè)緩存單元大小為4 KB.如圖5所示,虛線框中的部分即為Flashkv的緩存系統(tǒng).緩存單元共分為2部分,未使用的緩存單元和已使用的緩存單元.未使用的所有緩存單元鏈接在一個(gè)鏈表中.每個(gè)文件以一棵基樹(shù)組織屬于該文件的所有緩存單元,以加速索引過(guò)程.每個(gè)文件從空閑緩存單元鏈表中獲取緩存單元,插入自己所管理的基樹(shù)中,當(dāng)內(nèi)存不足時(shí),動(dòng)態(tài)地選擇一些已經(jīng)使用的緩存單元進(jìn)行替換,將其內(nèi)容寫(xiě)入閃存中.

        使用用戶態(tài)緩存的好處之一在于避免頻繁地陷入內(nèi)核.levelDB的每次讀寫(xiě)請(qǐng)求都要經(jīng)過(guò)系統(tǒng)調(diào)用陷入內(nèi)核態(tài),然后在頁(yè)高速緩存中查找;而Flashkv的緩存系統(tǒng)實(shí)現(xiàn)于用戶態(tài)下,減少了不必要的系統(tǒng)調(diào)用開(kāi)銷,在大量讀寫(xiě)請(qǐng)求的情況下,避免了用戶態(tài)和內(nèi)核態(tài)的頻繁切換.使用用戶態(tài)緩存而不是系統(tǒng)頁(yè)高速緩存的另一個(gè)好處在于可以根據(jù)數(shù)據(jù)庫(kù)本身的特點(diǎn)自由選擇合適的緩存算法.

        3.1.3 垃圾回收

        Fig. 6 The process of garbage collection圖6 垃圾回收示意圖

        SSD設(shè)備具有不能原地更新、讀寫(xiě)請(qǐng)求和擦除請(qǐng)求不對(duì)稱的特點(diǎn),這導(dǎo)致SSD設(shè)備的垃圾回收過(guò)程十分復(fù)雜.垃圾回收一般由閃存轉(zhuǎn)換層(FTL)完成.如圖6所示,在垃圾回收過(guò)程中,F(xiàn)TL會(huì)先讀入目標(biāo)塊中的有效頁(yè);然后將它們寫(xiě)入到新的地址,改變映射表;最后才能擦除目標(biāo)塊.整個(gè)過(guò)程引入了額外的讀寫(xiě)操作,在垃圾回收負(fù)擔(dān)重時(shí)會(huì)嚴(yán)重阻礙前臺(tái)的讀寫(xiě)請(qǐng)求,不僅開(kāi)銷巨大,而且造成嚴(yán)重的寫(xiě)放大,影響閃存壽命.

        在Flashkv中,垃圾回收過(guò)程十分簡(jiǎn)單.如圖4所示,F(xiàn)lashkv的地址分配以閃存塊為單位,因此在每個(gè)通道中,分配給文件的都是一個(gè)完整的閃存塊.當(dāng)刪除文件時(shí),需要回收物理地址空間,此時(shí)不再需要讀入有效頁(yè),重新寫(xiě)入新的地址,改變映射表等冗余步驟,只需直接擦除目標(biāo)塊即可.與構(gòu)建于FTL之上的levelDB系統(tǒng)相比,F(xiàn)lashkv中的垃圾回收過(guò)程不僅高效,且避免了不必要的寫(xiě)放大.

        3.2 I/O調(diào)度器

        Flashkv中,I/O調(diào)度器處于內(nèi)核態(tài),I/O調(diào)度器接收由上層管理單元發(fā)送的讀、寫(xiě)、擦除請(qǐng)求,經(jīng)過(guò)優(yōu)先級(jí)調(diào)度后,把這些請(qǐng)求發(fā)送到閃存設(shè)備上.如圖7所示,對(duì)于讀請(qǐng)求和寫(xiě)請(qǐng)求,I/O調(diào)度器中各有3個(gè)優(yōu)先級(jí)隊(duì)列,分別對(duì)應(yīng)優(yōu)先級(jí)高、中和低的讀寫(xiě)請(qǐng)求.對(duì)于擦除請(qǐng)求,F(xiàn)lashkv中僅有一個(gè)請(qǐng)求隊(duì)列,對(duì)優(yōu)先級(jí)不做區(qū)分.

        Fig. 7 The I/O scheduler of Flashkv圖7 Flashkv I/O調(diào)度器

        在Flashkv中,存在2種讀請(qǐng)求:1)用戶查找的key而出發(fā)的讀請(qǐng)求,我們稱之為前臺(tái)讀請(qǐng)求;2)為了compaction而進(jìn)行的讀請(qǐng)求,我們稱之為后臺(tái)讀請(qǐng)求.我們給前臺(tái)讀請(qǐng)求最高優(yōu)先級(jí),因?yàn)橛脩舻牟檎艺?qǐng)求應(yīng)當(dāng)盡可能快地得到響應(yīng),這類讀請(qǐng)求會(huì)插入高優(yōu)先級(jí)隊(duì)列中;把level 0的后臺(tái)讀請(qǐng)求設(shè)置為中等優(yōu)先級(jí),因?yàn)楫?dāng)level 0文件過(guò)多會(huì)引起整個(gè)數(shù)據(jù)庫(kù)阻塞,所以對(duì)level 0的compaction請(qǐng)求設(shè)置為中;其余的后臺(tái)讀請(qǐng)求會(huì)插入低優(yōu)先級(jí)隊(duì)列中.

        同樣,F(xiàn)lashkv中存在2種類型寫(xiě)請(qǐng)求:1)把內(nèi)存中的不可變內(nèi)存表(immutable table)寫(xiě)入到level 0產(chǎn)生的寫(xiě)請(qǐng)求;2)進(jìn)行compaction產(chǎn)生的寫(xiě)請(qǐng)求.從內(nèi)存的immutable table寫(xiě)入level 0的寫(xiě)請(qǐng)求,F(xiàn)lashkv給予最高優(yōu)先級(jí),因?yàn)閮?nèi)存中的immutable table不宜過(guò)多,否則會(huì)造成阻塞,這類寫(xiě)請(qǐng)求會(huì)插入高優(yōu)先級(jí)隊(duì)列中;對(duì)于compaction操作要寫(xiě)入到level 1的寫(xiě)請(qǐng)求,F(xiàn)lashkv給予中度優(yōu)先級(jí),因?yàn)閘evel 0的文件數(shù)目不能過(guò)多;其余的寫(xiě)請(qǐng)求會(huì)插入低優(yōu)先級(jí)隊(duì)列.

        Flashkv中,擦除請(qǐng)求不做區(qū)分.Flashkv會(huì)優(yōu)先調(diào)度優(yōu)先級(jí)更高的請(qǐng)求.為了防止低優(yōu)先級(jí)的請(qǐng)求饑餓,F(xiàn)lashkv每隔一段時(shí)間會(huì)對(duì)中優(yōu)先級(jí)和低優(yōu)先級(jí)的請(qǐng)求單獨(dú)處理,全部處理完成后再執(zhí)行正常調(diào)度策略.

        3.3 雙線程技術(shù)

        在levelDB中,內(nèi)存中最多只能有2張表,即1張正在插入的可變內(nèi)存表(mutable table)和1張不可變內(nèi)存表(immutable table),immutable table由mutable table轉(zhuǎn)化而來(lái).由于內(nèi)存寫(xiě)入速度和外存之間存在數(shù)量級(jí)的差距,當(dāng)客戶端的插入請(qǐng)求頻繁時(shí),2張內(nèi)存表都會(huì)很快填滿,造成插入操作阻塞.因此只能有一張immutable table的條件嚴(yán)重限制了levelDB的性能.在Flashkv中,我們把這一限制放寬,即內(nèi)存中可以有多個(gè)immutable table同時(shí)存在.

        為了平衡讀寫(xiě)性能,levelDB會(huì)在適當(dāng)?shù)臈l件下觸發(fā)compaction操作.levelDB的compaction過(guò)程涉及到大量的文件讀寫(xiě)操作,是levelDB的瓶頸所在.而levelDB中的compaction操作是單線程的,因此極易造成性能惡化.

        Flashkv修改了levelDB的compaction邏輯,使用了雙線程進(jìn)行compaction.Flashkv首先對(duì)每一層compaction的優(yōu)先級(jí)進(jìn)行評(píng)估,然后選擇優(yōu)先級(jí)最高且互不影響的2層進(jìn)行并行compaction.所謂互不影響是指2個(gè)compaction不涉及相同的文件.

        4 實(shí)驗(yàn)測(cè)試

        4.1 測(cè)試環(huán)境

        實(shí)驗(yàn)在Linux 2.6.32內(nèi)核環(huán)境下進(jìn)行,所用服務(wù)器內(nèi)存為4 GB,CPU為Intel?Xeon E5-2620,2.10 GHz,12核,并配置有一塊PCIE裸閃存設(shè)備.該閃存設(shè)備的閃存塊大小為2 MB,頁(yè)大小為8 KB.實(shí)驗(yàn)環(huán)境配置如表1所示:

        Table 1 Experiment Configuration表1 實(shí)驗(yàn)環(huán)境配置

        測(cè)試工具采用了目前流行的YCSB benchmark[22],是由雅虎提出的一個(gè)測(cè)試框架,它提供了6種不同的負(fù)載來(lái)評(píng)估非關(guān)系型數(shù)據(jù)庫(kù)的性能.YCSB的測(cè)試過(guò)程分為load階段和run階段,load階段向數(shù)據(jù)庫(kù)中插入給定數(shù)量的key-value記錄,run階段完成給定數(shù)量的操作,這些操作包含讀取(read)、更新(update)、插入(insert)、讀后寫(xiě)(read modify write)等,不同負(fù)載各操作所占比例不同,如表2所示.我們使用YCSB的5種負(fù)載:a,b,c,d,f,分別對(duì)Flashkv和levelDB進(jìn)行了測(cè)試.由于YCSB的負(fù)載e涉及scan操作,而LSM tree數(shù)據(jù)結(jié)構(gòu)scan操作開(kāi)銷較大,因此沒(méi)有對(duì)負(fù)載e進(jìn)行測(cè)試.5種負(fù)載的特點(diǎn)如表2所示.其中,zipfian分布表示齊夫分布,latest分布表示最近插入的數(shù)據(jù)更可能被讀取.

        Table 2 YCSB Workloads Features表2 YCSB的5種負(fù)載特點(diǎn)

        4.2 Flashkv整體、架構(gòu)測(cè)試

        本節(jié)實(shí)驗(yàn)將測(cè)試Flashkv的整體性能和Flashkv在架構(gòu)上的優(yōu)勢(shì).YCSB的設(shè)置參數(shù)如表3所示,在load階段先向數(shù)據(jù)庫(kù)中插入10×106條記錄,run階段再完成10×106次操作.使用雙線程有I/O調(diào)度的Flashkv版本測(cè)試整體性能,使用單線程沒(méi)有I/O調(diào)度的Flashkv版本測(cè)試架構(gòu)優(yōu)勢(shì).以下表達(dá)中,雙線程Flashkv表示使用雙線程和I/O調(diào)度版本的Flashkv,用以測(cè)試Flashkv整體性能;單線程Flashkv表示使用單線程且沒(méi)有I/O調(diào)度的Flashkv,用以測(cè)試Flashkv的架構(gòu)優(yōu)勢(shì).作為對(duì)比,levelDB分別運(yùn)行在ext3和ext4文件系統(tǒng)之上.我們還實(shí)現(xiàn)了一個(gè)閃存轉(zhuǎn)換層oftl,oftl采用頁(yè)級(jí)映射,并緩存最近使用的部分映射表.

        Table 3 YCSB Parameter表3 YCSB參數(shù)

        4.2.1 時(shí)間

        run階段時(shí)間測(cè)試結(jié)果如表4所示,單位為s.除負(fù)載d外,單線程Flashkv的時(shí)間為使用ext4文件系統(tǒng)levelDB的50%~60%,為使用ext3文件系統(tǒng)levelDB的50%~60%.僅從架構(gòu)角度看,F(xiàn)lashkv性能是使用ext4文件系統(tǒng)levelDB的1.65~2.0倍,是使用ext3文件系統(tǒng)levelDB的1.66~2.0倍.

        Table 4 Runtime of Flashkv and levelDB表4 Flashkv和levelDB運(yùn)行時(shí)間對(duì)比 s

        除負(fù)載d外,雙線程Flashkv的時(shí)間為使用ext4文件系統(tǒng)levelDB的45%~50%,為使用ext3文件系統(tǒng)levelDB的44%~50%.Flashkv整體性能是使用ext4文件系統(tǒng)levelDB的1.99~2.25倍,是使用ext3文件系統(tǒng)levelDB的1.97~2.23倍.

        負(fù)載d采用了latest分布,訪問(wèn)最近寫(xiě)入的數(shù)據(jù),由于這些數(shù)據(jù)大部分在緩存中,所以Flashkv的提升不多.

        Flashkv和levelDB時(shí)間對(duì)比如圖8所示,可以看出,F(xiàn)lashkv的性能高于levelDB,有以下4點(diǎn)原因:

        1) Flashkv不借助于文件系統(tǒng)和FTL進(jìn)行空間分配,而是由管理單元采用塊對(duì)齊的方式來(lái)進(jìn)行物理地址分配,閃存設(shè)備的并發(fā)性能得到了充分利用;

        2) Flashkv特殊的塊對(duì)齊分配方式,使得垃圾回收過(guò)程大大簡(jiǎn)化;

        3) Flashkv整合了levelDB中分別位于文件系統(tǒng)和FTL中的空間分配模塊和垃圾回收模塊,避免了冗余;

        4) Flashkv繞過(guò)了通用文件系統(tǒng)和內(nèi)核的I/O路徑,減少了I/O軟件棧的開(kāi)銷.

        Flashkv性能較levelDB有明顯提高,證明了Flashkv架構(gòu)上的優(yōu)勢(shì).

        Fig. 8 Flashkv and levelDB runtime comparison圖8 Flashkv和levelDB運(yùn)行時(shí)間對(duì)比

        4.2.2 寫(xiě)入量

        在YCSB的5種負(fù)載下,我們分別測(cè)試了Flashkv和基于ext3,ext4文件系統(tǒng)的levelDB的寫(xiě)入量.結(jié)果如表5所示,單位為GB,該結(jié)果為load階段和run階段總的寫(xiě)入量.

        Table 5 Write Amount of Flashkv and levelDB表5 Flashkv和levelDB寫(xiě)入量對(duì)比 GB

        Flashkv和levelDB寫(xiě)入量對(duì)比如圖9所示,從圖9中可以看出,雙線程Flashkv的寫(xiě)入量比基于ext4,ext3文件系統(tǒng)的levelDB減少60%~65%;單線程Flashkv寫(xiě)入量比基于ext4,ext3文件系統(tǒng)levelDB減少55%~60%,寫(xiě)入量明顯減少.由于采用了塊對(duì)齊的物理地址分配方式,F(xiàn)lashkv的垃圾回收過(guò)程十分簡(jiǎn)單,只需要直接擦除無(wú)效地址即可,不再涉及讀出有效頁(yè)重新寫(xiě)入新的地址這一步驟,不會(huì)帶來(lái)額外的寫(xiě)放大,因此寫(xiě)入量較依賴FTL進(jìn)行垃圾回收的levelDB有明顯減少.

        Fig. 9 The write amount of Flashkv and levelDB圖9 Flashkv和levelDB寫(xiě)入量對(duì)比

        4.3 I/O調(diào)度測(cè)試

        本節(jié)我們將測(cè)試I/O調(diào)度技術(shù)對(duì)Flashkv的影響,作為對(duì)比的兩者分別是使用了I/O調(diào)度技術(shù)的Flashkv和沒(méi)有使用I/O調(diào)度技術(shù)的Flashkv,為了排除雙線程技術(shù)的影響,二者均采用了雙線程技術(shù).

        本節(jié)仍然使用YCSB作為測(cè)試集,由于I/O調(diào)度技術(shù)主要在run階段起作用,因此我們考察run階段.測(cè)試采用50個(gè)線程,我們首先向數(shù)據(jù)庫(kù)中插入2 000萬(wàn)條記錄,然后進(jìn)行2 000萬(wàn)次操作.實(shí)驗(yàn)結(jié)果如表6所示:

        Table 6 Impact of I/O Schedule on Flashkv表6 I/O調(diào)度對(duì)Flashkv時(shí)間的影響

        I/O調(diào)度對(duì)Flashkv時(shí)間的影響如圖10所示,從圖10中看出,使用了I/O調(diào)度器的Flashkv比沒(méi)有使用I/O調(diào)度器的Flashkv性能提升5%~21%,證明I/O調(diào)度技術(shù)的作用.I/O調(diào)度器優(yōu)先調(diào)度前臺(tái)和compaction的請(qǐng)求,保證前臺(tái)訪問(wèn)的低延遲的同時(shí),避免了整個(gè)數(shù)據(jù)庫(kù)因level 0層文件過(guò)多導(dǎo)致的頻繁阻塞,因此Flashkv整體性能得到提升.

        Fig. 10 Runtime comparison with and without I/O schedule圖10 有無(wú)I/O調(diào)度Flashkv時(shí)間對(duì)比

        4.4 雙線程技術(shù)測(cè)試

        本節(jié)我們將測(cè)試雙線程技術(shù)對(duì)Flashkv的影響.作為對(duì)比的兩者分別是沒(méi)有使用雙線程技術(shù)和使用了雙線程技術(shù)的Flashkv,為了排除I/O調(diào)度的影響,二者都沒(méi)有采用I/O調(diào)度.由于雙線程技術(shù)僅加速Flashkv的寫(xiě)入過(guò)程,因此我們僅考察數(shù)據(jù)load階段.測(cè)試用50個(gè)線程,我們分別向數(shù)據(jù)庫(kù)中插入500萬(wàn)、800萬(wàn)、1 000萬(wàn)、1 500萬(wàn)、2 000萬(wàn)條記錄.表7為單線程版本Flashkv和雙線程版本Flashkv的運(yùn)行時(shí)間對(duì)比結(jié)果.

        Table 7 Runtime of Flashkv with Single Thread and Two Threads

        Fig. 11 Time comparison between Flashkv with two threads and one thread圖11 雙線程和單線程下Flashkv時(shí)間對(duì)比

        雙線程版的Flashkv和單線程版的Flashkv時(shí)間對(duì)比如圖11所示,可以看出,在插入相同數(shù)量記錄的情況下,使用雙線程的Flashkv時(shí)間為單線程版Flashkv的57%~67%.雙線程技術(shù)使得compaction操作加速,避免了大量文件堆積在level 0,從而避免了插入操作的阻塞,起到了性能提升的作用.

        5 結(jié) 論

        本文設(shè)計(jì)實(shí)現(xiàn)了一種基于裸閃存的key-value數(shù)據(jù)庫(kù)系統(tǒng)Flashkv,通過(guò)用戶態(tài)下的管理單元,F(xiàn)lashkv繞過(guò)了文件系統(tǒng)和閃存轉(zhuǎn)換層(FTL),能夠在用戶態(tài)進(jìn)行高效的空間管理和垃圾回收,從而充分利用了閃存設(shè)備內(nèi)部的并發(fā)特性,大大簡(jiǎn)化垃圾回收過(guò)程,縮短I/O路徑;提出了基于閃存特點(diǎn)的I/O調(diào)度技術(shù),通過(guò)I/O調(diào)度器對(duì)I/O請(qǐng)求按其優(yōu)先級(jí)進(jìn)行調(diào)度,保證優(yōu)先級(jí)高的請(qǐng)求優(yōu)先得到執(zhí)行,并用雙線程加速了數(shù)據(jù)庫(kù)內(nèi)部的壓縮(compaction)操作,優(yōu)化了閃存的讀寫(xiě)延遲,提高了吞吐率;提出了用戶態(tài)緩存管理技術(shù),降低了數(shù)據(jù)寫(xiě)入量和頻繁系統(tǒng)調(diào)用所帶來(lái)的開(kāi)銷,提升了系統(tǒng)性能.測(cè)試結(jié)果表明,F(xiàn)lashkv性能是levelDB的1.9~2.2倍,寫(xiě)入量比levelDB減少了60%~65%,F(xiàn)lashkv表現(xiàn)出了明顯的性能優(yōu)勢(shì),且寫(xiě)入量也大大減少.

        [1]Lu Jiaheng. Big Data Challenge and NoSQL Technology[M]. Beijing: Publishiing House of Electronics Industry, 2013: 45-46 (in Chinese)

        (陸嘉恒. 大數(shù)據(jù)挑戰(zhàn)與NoSQL數(shù)據(jù)庫(kù)技術(shù)[M]. 北京: 電子工業(yè)出版社, 2013: 45-46)

        [2]Shen Derong, Yu Ge, Wang Xite, et al. Survey on NoSQL for management of big data[J]. Journal of Software, 2013, 24(8): 1786-1803 (in Chinese)

        (申德榮, 于戈, 王習(xí)特, 等. 支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J]. 軟件學(xué)報(bào), 2013, 24(8): 1786-1803)

        [3]Leavitt N. Will NoSQL databases live up to their promise?[J]. Computer, 2010, 43(2): 12-14

        [4]DeCandia G, Hastorun D, Jampani M, et al. Dynamo: Amazon’s highly available key-value store[J]. ACM SIGOPS Operating Systems Review, 2007, 41(6): 205-220

        [5]Chang F, Dean J, Ghemawat S, et al. Bigtable: A distributed storage system for structured data[C] //Proc of the 7th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2006: 205-218

        [6]Lu Youyou, Shu Jiwu. Survey on flash-based storage systems[J]. Journal of Computer Research and Development, 2013, 50(1): 49-59 (in Chinese)

        (陸游游, 舒繼武. 閃存存儲(chǔ)系統(tǒng)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 49-59)

        [7]Zheng Wenjing, Li Mingqiang, Shu Jiwu. Flash storage technology[J]. Journal of Computer Research and Development, 2010, 47(4): 716-726 (in Chinese)

        (鄭文靜, 李明強(qiáng), 舒繼武. Flash存儲(chǔ)技術(shù)[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(4): 716-726)

        [8]Chen Feng, Lee Rubao, Zhang Xiaodong. Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing[C] //Proc of the 17th IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2011: 266-277

        [9]Andersen D G, Franklin J, Kaminsky M, et al. FAWN: A fast array of wimpy nodes[C] //Proc of the 22nd ACM SIGOPS Symp on Operating Systems Principles. New York: ACM, 2009: 1-14

        [10]Lee S W, Moon B, Park C, et al. A case for flash memory SSD in enterprise database applications[C] //Proc of the 2008 ACM SIGMOD Int Conf on Management of data. New York: ACM, 2008: 1075-1086

        [11]Hu Xiaoyu, Eleftheriou E, Haas R, et al. Write amplification analysis in flash-based solid state drives[C] //Proc of the 2nd Int Systems and Storage Conf. New York: ACM, 2009: 10-19

        [12]Shen Zhaoyan, Chen Feng, Jia Yichen, et al. DIDACache: A deep integration of device and application for flash based key-value caching[C] //Proc of the 15th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2017: 391-405

        [13]Wang Peng, Sun Guangyu, Jiang Song, et al. An efficient design and implementation of LSM-tree based key-value store on open-channel SSD[C] //Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 16-29

        [14]FAL Labs. Tokyo Cabinet: A modern implementation of DBM[OL]. [2017-02-20]. http://fallabs.com/tokyocabinet/

        [15]Redis Labs. Redis[OL]. [2017-02-20]. http://redis.io/, 2009

        [16]Debnath B, Sengupta S, Li J. SkimpyStash: RAM space skimpy key-value store on flash-based storage[C] //Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 25-36

        [17]O’Neil P, Cheng E, Gawlick D, et al. The log-structured merge-tree (LSM-tree)[J]. Acta Informatica, 1996, 33(4): 351-385

        [18]Ghemawat S, Dean J. LevelDB, v1.14.0[OL]. [2015-03-20]. https://github.com/google/leveldb,http://leveldb.org

        [19]Apache Software Foundation. Apache HBase[OL]. [2017-02-20]. http://hbase.apache.org/

        [20]Wu Xingbo, Xu Yuehai, Shao Zili, et al. LSM-trie: An LSM-tree-based ultra-large key-value store for small data[C] //Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 71-82

        [21]Lu Lanyue, Pillai T S, Arpaci-Dusseau A C, et al. WiscKey: Separating keys from values in SSD-conscious Storage[C] //Proc of the 14th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2016: 133-148

        [22]Cooper B F, Silberstein A, Tam E, et al. Benchmarking cloud serving systems with YCSB[C] //Proc of the 1st ACM Symp on Cloud computing. New York: ACM, 2010: 143-154

        Qin Xiongjun, born in 1991. Master candidate. His main research interests include file system and key value database.

        Zhang Jiacheng, born in 1991. PhD candidate. His main research interests include file and storage systems and non-volatile memories.

        Lu Youyou, born in 1987. PhD, assistant researcher. Member of CCF. His main research interests include nonvolatile memories and file systems.

        Shu Jiwu, born in 1968. PhD, professor and PhD supervisor. Distinguished member of CCF. His main research interests include network storage system, cloud storage system, and big data storage system, storage security and reliability.

        A Key-Value Database Optimization Method Based on Raw Flash Device

        Qin Xiongjun, Zhang Jiacheng, Lu Youyou, and Shu Jiwu

        (DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

        In recent years, NoSQL key-value databases have been widely used. However, the current mainstream key-value databases are based either on disk, or on traditional file system and flash translation layer, which makes it difficult to utilize the characteristics of flash devices, and also limits I/O concurrency of flash devices. Moreover, garbage collection process under such kind of architecture is complex. This paper designs and implements Flashkv, a key-value data management architecture based on raw flash device. Flashkv doesn’t use file system and flash translation layer, instead, it’s space management and garbage collection are done by the management unit in the user mode. Flashkv makes full use of the concurrent features inside the flash device, and simplifies the garbage collection process and removes redundant function modules which exist in both traditional file system and flash translation layer, and also shortens the I/O path. This paper proposes I/O scheduling technology based on the characteristics of flash memory, which reduces read and write latency of flash memory and improves throughput. The user mode cache management technology is proposed, which reduces write amount and also the cost of frequent system calls. Test results show that Flashkv’s performance is 1.9 to 2.2 times that of levelDB and the write amount reduces by 60% to 65%.

        key-value database; flash memory; raw device; data storage; lifespan

        2017-02-17;

        2017-04-13

        國(guó)家自然科學(xué)基金項(xiàng)目(61327902,61433008);北京市科委課題(D151100000815003) This work was supported by the National Natural Science Foundation of China (61327902, 61433008) and Beijing Municipal Science and Technology Commission of China (D151100000815003).

        舒繼武(shujw@tsinghua.edu.cn)

        TP333

        猜你喜歡
        內(nèi)存架構(gòu)調(diào)度
        基于FPGA的RNN硬件加速架構(gòu)
        功能架構(gòu)在電子電氣架構(gòu)開(kāi)發(fā)中的應(yīng)用和實(shí)踐
        汽車工程(2021年12期)2021-03-08 02:34:30
        《調(diào)度集中系統(tǒng)(CTC)/列車調(diào)度指揮系統(tǒng)(TDCS)維護(hù)手冊(cè)》正式出版
        一種基于負(fù)載均衡的Kubernetes調(diào)度改進(jìn)算法
        “春夏秋冬”的內(nèi)存
        虛擬機(jī)實(shí)時(shí)遷移調(diào)度算法
        LSN DCI EVPN VxLAN組網(wǎng)架構(gòu)研究及實(shí)現(xiàn)
        一種基于FPGA+ARM架構(gòu)的μPMU實(shí)現(xiàn)
        基于內(nèi)存的地理信息訪問(wèn)技術(shù)
        SVC的RTP封裝及其在NS2包調(diào)度中的應(yīng)用研究
        成人aaa片一区国产精品 | 精品人妻系列无码一区二区三区| 综合91在线精品| 92自拍视频爽啪在线观看| 国产av在线观看久久| 任你躁国产自任一区二区三区| 国产成人精品三级麻豆 | 国产做爰又粗又大又爽动漫| 欧美三级乱人伦电影| 久久精品国产亚洲AⅤ无码剧情| 福利视频偷拍一区二区| 热re99久久精品国99热| 2019年92午夜视频福利| 亚洲人成网站在线播放小说| 亚洲av成人一区二区| 精品国内在视频线2019| 欧美一级欧美一级在线播放| 国产精品专区一区二区av免费看 | 久人人爽人人爽人人片av| 中文字幕精品久久久久人妻红杏1| 亚洲欧美国产成人综合不卡| 水蜜桃男女视频在线观看网站| 六月丁香综合在线视频| 国产精品视频牛仔裤一区| 日韩精品中文字幕人妻中出| 亚洲国产高清精品在线| 全免费a级毛片免费看网站| 欧美日韩中文亚洲另类春色| 丰满巨臀人妻中文字幕| 国产精品99无码一区二区| 国内精品久久久久久久久齐齐| 韩国美女主播国产三级| 亚洲国产高清精品在线| 天堂8中文在线最新版在线| 探花国产精品三级在线播放| 精品中文字幕在线不卡| 国产精品户外野外| 日韩AV有码无码一区二区三区| 亚洲一区二区三区18| 99无码熟妇丰满人妻啪啪| 91久久青青草原线免费|