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

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

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

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

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

(qinxiongjun2010@163.com)

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

Fig. 1 levelDB illustration圖1 levelDB示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 管理單元

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

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

3.1.1 空間管理

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.3 垃圾回收

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

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

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

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

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

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

在Flashkv中，存在2種讀請求：1)用戶查找的key而出發(fā)的讀請求，我們稱之為前臺讀請求;2)為了compaction而進行的讀請求，我們稱之為后臺讀請求.我們給前臺讀請求最高優(yōu)先級，因為用戶的查找請求應(yīng)當(dāng)盡可能快地得到響應(yīng)，這類讀請求會插入高優(yōu)先級隊列中；把level 0的后臺讀請求設(shè)置為中等優(yōu)先級，因為當(dāng)level 0文件過多會引起整個數(shù)據(jù)庫阻塞，所以對level 0的compaction請求設(shè)置為中；其余的后臺讀請求會插入低優(yōu)先級隊列中.

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

Flashkv中，擦除請求不做區(qū)分.Flashkv會優(yōu)先調(diào)度優(yōu)先級更高的請求.為了防止低優(yōu)先級的請求饑餓，F(xiàn)lashkv每隔一段時間會對中優(yōu)先級和低優(yōu)先級的請求單獨處理，全部處理完成后再執(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)化而來.由于內(nèi)存寫入速度和外存之間存在數(shù)量級的差距，當(dāng)客戶端的插入請求頻繁時，2張內(nèi)存表都會很快填滿，造成插入操作阻塞.因此只能有一張immutable table的條件嚴(yán)重限制了levelDB的性能.在Flashkv中，我們把這一限制放寬，即內(nèi)存中可以有多個immutable table同時存在.

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

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

4 實驗測試

4.1 測試環(huán)境

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

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

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

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

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

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

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

4.2.1 時間

run階段時間測試結(jié)果如表4所示，單位為s.除負(fù)載d外，單線程Flashkv的時間為使用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運行時間對比 s

除負(fù)載d外，雙線程Flashkv的時間為使用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分布，訪問最近寫入的數(shù)據(jù)，由于這些數(shù)據(jù)大部分在緩存中，所以Flashkv的提升不多.

Flashkv和levelDB時間對比如圖8所示，可以看出，F(xiàn)lashkv的性能高于levelDB，有以下4點原因：

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

2) Flashkv特殊的塊對齊分配方式，使得垃圾回收過程大大簡化；

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

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

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

Fig. 8 Flashkv and levelDB runtime comparison圖8 Flashkv和levelDB運行時間對比

4.2.2 寫入量

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

Table 5 Write Amount of Flashkv and levelDB表5 Flashkv和levelDB寫入量對比 GB

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

Fig. 9 The write amount of Flashkv and levelDB圖9 Flashkv和levelDB寫入量對比

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

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

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

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

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

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

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

本節(jié)我們將測試雙線程技術(shù)對Flashkv的影響.作為對比的兩者分別是沒有使用雙線程技術(shù)和使用了雙線程技術(shù)的Flashkv，為了排除I/O調(diào)度的影響，二者都沒有采用I/O調(diào)度.由于雙線程技術(shù)僅加速Flashkv的寫入過程，因此我們僅考察數(shù)據(jù)load階段.測試用50個線程，我們分別向數(shù)據(jù)庫中插入500萬、800萬、1 000萬、1 500萬、2 000萬條記錄.表7為單線程版本Flashkv和雙線程版本Flashkv的運行時間對比結(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時間對比

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

5 結(jié) 論

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

[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ù)庫技術(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é)報, 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)

(陸游游, 舒繼武. 閃存存儲系統(tǒng)綜述[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)

(鄭文靜, 李明強, 舒繼武. Flash存儲技術(shù)[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

國家自然科學(xué)基金項目(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