面向鍵值存儲的日志結(jié)構(gòu)合并樹優(yōu)化技術(shù)

吳尚宇 謝婧雯 王 毅

(深圳大學(xué)計算機與軟件學(xué)院 廣東深圳 518060)(shangyuwu1006@gmail.com)

大數(shù)據(jù)時代互聯(lián)網(wǎng)產(chǎn)生了海量多樣化的信息資產(chǎn)，對現(xiàn)有數(shù)據(jù)庫存儲以及管理數(shù)據(jù)的能力提出了更高的要求[1].傳統(tǒng)關(guān)系型數(shù)據(jù)庫難以再支持對海量數(shù)據(jù)的高效讀寫等需求，這使得具有優(yōu)異擴展性能的非關(guān)系型數(shù)據(jù)庫逐漸入駐存儲的世界.

鍵值存儲是非關(guān)系型存儲的一種常見方式，模式簡單、易于擴展[2].鍵值存儲通過去除關(guān)系型數(shù)據(jù)庫中一些不必要的特性，有效地提升了自身的存儲性能，降低了數(shù)據(jù)之間的耦合度[3]，越來越廣泛地應(yīng)用于現(xiàn)代數(shù)據(jù)中心.目前鍵值存儲系統(tǒng)采用的主流架構(gòu)是日志結(jié)構(gòu)合并樹(log-structured merge tree, LSM-Tree)[4].LSM-Tree的基本思想是通過聚合內(nèi)存中的多個寫操作，將它們以批處理的形式轉(zhuǎn)儲到文件中，再按順序?qū)⑦@些文件寫入磁盤.同時，LSM-Tree通過壓縮操作使這些文件按多級分層存儲，以便于快速查找.與傳統(tǒng)B-Tree[5]相比，LSM-Tree將隨機寫轉(zhuǎn)換為順序?qū)懀瑯O大地提高了寫效率.LSM-Tree是目前數(shù)據(jù)庫系統(tǒng)采用的主要存儲引擎之一，是眾多分布式組件的存儲基石[6].許多的企業(yè)都采用它來搭建存儲應(yīng)用，如谷歌的BigTable[7]和LevelDB[8]、Facebook的RocksDB[9]和Cassandra[10]、Apache的HBase[11]和雅虎的PNUTS[12]等.

在現(xiàn)實世界中，鍵值存儲的請求模式往往都是讀多寫少的，如在Facebook的Memcached系統(tǒng)中，請求的讀寫比已經(jīng)高達(dá)30∶1[13].LSM-Tree結(jié)構(gòu)為了提升寫效率犧牲了一部分讀效率，從而使得讀放大問題更為嚴(yán)重.現(xiàn)在國內(nèi)外面向LSM-Tree的研究主要都是針對寫性能的提升，在讀性能方面上的研究較少.Zhang等人[14]提出ElasticBF，為每個文件更細(xì)粒度地劃分了多個小過濾器.這些小過濾器通過動態(tài)算法載入內(nèi)存，減少了不必要的查找，提高了LSM-Tree的讀吞吐性能；Teng等人[15]提出LSbM-Tree，通過增加1個壓縮緩沖區(qū)來減少由壓縮操作引起的緩沖區(qū)的失效問題；Wu等人[16]提出LSM-trie，通過構(gòu)造1棵字典樹或前綴樹來加速查找.Sears等人[17]提出了bLSM，bLSM結(jié)合了B-Tree的優(yōu)點，通過增加彈簧和齒輪(spring and gear)調(diào)度器來決定LSM-Tree中不同層級的壓縮操作的執(zhí)行順序.bLSM有效地提高了LSM-Tree的讀性能，同時減緩了因壓縮操作導(dǎo)致的寫暫停問題.這些研究工作都增加了額外的數(shù)據(jù)結(jié)構(gòu)，顯著地提升LSM-Tree的讀效率.我們的方法旨在從LSM-Tree的數(shù)據(jù)流向上考慮，通過改變數(shù)據(jù)流向來減小讀放大問題.

本文從LSM-Tree的數(shù)據(jù)流向出發(fā)，對冷熱數(shù)據(jù)進行區(qū)分，提出一種基于訪問頻率的上浮式鍵值存儲結(jié)構(gòu)(floating key-value, FloatKV).FloatKV在內(nèi)存中提出了一種新的數(shù)據(jù)存儲結(jié)構(gòu)LRFO(LRU and FIFO).LRFO能夠使高頻訪問的數(shù)據(jù)在內(nèi)存中駐留更長的時間，以減少不必要的IO操作.FloatKV在外存中統(tǒng)計了數(shù)據(jù)的訪問頻率，并設(shè)計了一種基于訪問頻率的上浮式鍵值存儲策略.它能夠根據(jù)數(shù)據(jù)當(dāng)前的訪問頻率自適應(yīng)地調(diào)整數(shù)據(jù)存儲的位置，以減少讀延遲和讀放大問題.為了驗證FloatKV的可行性及性能，我們使用標(biāo)準(zhǔn)數(shù)據(jù)庫性能測試工具YCSB(yahoo! cloud serving benchmark)來進行評估，并將FloatKV與當(dāng)前主流的鍵值數(shù)據(jù)庫LevelDB及顯著提升LSM-Tree性能的Wisckey算法進行了比較.實驗結(jié)果顯示，相比LevelDB和Wisckey，F(xiàn)loatKV顯著地提升了讀效率，平均減少了77%的操作總延遲，有效地減少了讀放大問題，平均減少了95%的讀放大.

1 背景知識

1.1 LSM-Tree

LSM-Tree的基本結(jié)構(gòu)為多棵樹的集合，其中最小的1棵在內(nèi)存中，其他都在外存中.如圖1所示，以2棵樹為例，較小的1棵C0樹在內(nèi)存中，而磁盤上較大的1棵C1樹則由內(nèi)存部分持久化得到.C0樹和C1樹的具體結(jié)構(gòu)類似于B-Tree.C1樹所有節(jié)點的大小為磁盤塊大小.C0樹和C1樹共同維護一個鍵值有序的鍵空間.

Fig. 1 The architecture of LSM-Tree

當(dāng)寫入1條新數(shù)據(jù)到LSM-Tree中時，根據(jù)數(shù)據(jù)的索引值將數(shù)據(jù)插入C0樹中.內(nèi)存中C0樹的大小存在一個閾值.當(dāng)C0樹的大小達(dá)到閾值時，一部分?jǐn)?shù)據(jù)將從C0樹通過滾動合并的方式被持久化到C1樹中，即批量地把這些數(shù)據(jù)寫入磁盤.

LSM-Tree對比傳統(tǒng)B-Tree來說，它的優(yōu)勢在于在一定程度上優(yōu)化了磁盤寫入問題，但在進行讀操作的時候可能要訪問比較多的磁盤文件[11].

1.2 LevelDB

Fig. 2 The architecture and operations of LevelDB

LevelDB是基于LSM-Tree實現(xiàn)的非常高效的鍵值存儲系統(tǒng).它將隨機寫請求轉(zhuǎn)換為順序?qū)懻埱螅３至藬?shù)據(jù)高效的持久化存儲.圖2展示了經(jīng)典的LevelDB結(jié)構(gòu).LevelDB將內(nèi)存分為2個部分：MemTable，Immutable MemTable.它們都是基于跳表實現(xiàn)的，均能達(dá)到O(logn)的查詢和插入效率；外存主要以SSTable(sorted string table)文件的形式來存儲鍵值對，同時還包括了一些輔助文件：Log文件、Manifest文件以及Current文件.外存中的SSTable文件在邏輯上被分為多層結(jié)構(gòu)，稱為L0,L1,…,L6.每層都設(shè)有文件的上限個數(shù)或大小，除L0層以外，其他各層的SSTable之間均不存在鍵值范圍的重疊.Log文件記錄了已經(jīng)進行的所有操作，用于恢復(fù)崩潰的LevelDB；Manifest文件記錄了所有SSTable文件的meta信息；Current文件記錄了當(dāng)前最新的數(shù)據(jù)庫狀態(tài).

當(dāng)往LevelDB寫入1對鍵值對時，LevelDB首先將操作日志寫入Log文件，然后再將鍵值對插入MemTable.為了能夠快速存儲新數(shù)據(jù)以支持內(nèi)存中的高吞吐量寫入[18]，MemTable在大小達(dá)到閾值后會被轉(zhuǎn)換成1個Immutable MemTable.同時，LevelDB會創(chuàng)建1個新的MemTable來迎接新請求.當(dāng)有2個Immutable MemTable同時存在或其他主動觸發(fā)的情況發(fā)生時，Immutable MemTable中的鍵值對將被以SSTable的形式持久化到磁盤中.隨后，LevelDB會將新產(chǎn)生的SSTable插入到多層文件結(jié)構(gòu)的L0層中.當(dāng)存儲在L0層中的SSTable文件的個數(shù)達(dá)到上限時，LevelDB開始進行壓縮(compaction)操作，將鍵值對往低層移動.具體來說，對Li層的壓縮操作，首先從Li層選擇出1個目標(biāo)SSTable，再從Li+1層中選擇與其鍵值范圍重疊的所有SSTable；然后，將這些SSTable都讀入到內(nèi)存，通過多路合并算法得到新的SSTable；最后，將這些新的SSTable重新插入到Li+1層中.當(dāng)LevelDB需要讀取1個鍵對應(yīng)的值時，它需要依次從MemTable，Immutable MemTable以及L0～L6層的SSTable中查找.

LevelDB中最突出的問題就是寫放大和讀放大問題.寫(讀)放大倍數(shù)被定義為寫入(讀取)底層存儲設(shè)備數(shù)據(jù)量與用戶請求的數(shù)據(jù)量之比.造成寫放大的原因是：1)SSTable文件中的索引部分以及其他加速查找的部分如過濾器造成了額外的寫開銷；2)壓縮操作寫入的新SSTable也會帶來額外的寫開銷.造成讀放大的原因是：1)LevelDB的試探性查找機制需要檢查多個文件才能找到真正包含鍵的SSTable；2)確定SSTable后仍需要讀取索引等部分才能確定鍵值對；3)壓縮操作讀取的SSTable會造成額外的讀開銷.最差情況下，LevelDB需要檢查14個SSTable(在L0層檢查8個SSTable，L1～L6層每層各檢查1個)才能找到真正的鍵[19].同時，壓縮操作在一般情況下會讀取至少5個甚至更多的SSTable[20].

1.3 鍵值分離

Lu等人[19]認(rèn)為不斷重新排序SSTable的壓縮操作是影響LSM-Tree性能的主要原因.在壓縮操作的進行過程中，SSTable被讀進內(nèi)存，重新排序，再寫回外存，這一系列操作極大地影響了LevelDB的讀寫性能.通過觀察這一系列操作，Lu等人發(fā)現(xiàn)壓縮操作只是根據(jù)鍵(key)來進行的，值(value)并不影響壓縮操作的進行.同時，在多數(shù)情況下值的大小都遠(yuǎn)遠(yuǎn)大于鍵的大小.所以，Lu等人得出結(jié)論：壓縮操作所帶來的額外的寫開銷主要是因為值在壓縮過程中的反復(fù)讀取和寫入.

根據(jù)觀察得出的結(jié)論，Lu等人提出Wisckey，一種鍵和值分開存儲的思想.它主張將鍵存在LSM-Tree中，將值單獨存在1個日志形式的文件vLog中.當(dāng)往數(shù)據(jù)庫插入1個鍵值對時，Wisckey首先將值追加在vLog尾部，記錄值在vLog中對應(yīng)的地址.然后，Wisckey將值的地址與原來的鍵組成新的“鍵值對”.最后，將這個“鍵值對”插入LSM-Tree中.當(dāng)讀取1個鍵對應(yīng)的值時，Wisckey首先在LSM-Tree中查找到對應(yīng)的“鍵值對”，再根據(jù)“值”(地址)去vLog中查找真正的值.由于地址的大小很小，基本可以忽略不計，這使得Wisckey中LSM-Tree遠(yuǎn)遠(yuǎn)小于LevelDB中的LSM-Tree.LSM-Tree大小的減小顯著地降低了壓縮操作的開銷，也減小了寫放大和讀放大問題.當(dāng)運行一段時間后，Wisckey中的vLog會包含許多無效數(shù)據(jù)，這時候Wisckey就需要對它進行垃圾回收操作.對vLog的垃圾回收操作需要將vLog頭部已經(jīng)過期的值刪除，并重新在LSM-Tree中更新這些值里的有效值的地址.特別地，當(dāng)vLog回收的所有值均為無效值時，Wisckey的吞吐量將會有10%的降低.

2 FloatKV

2.1 設(shè)計目標(biāo)與動機

LevelDB以及Wisckey已經(jīng)具有極高的寫性能，但讀性能仍有待提升.而現(xiàn)實世界中大部分應(yīng)用的請求模式都是讀多寫少的，我們希望能夠在不損失大量寫效率的基礎(chǔ)上，提高LSM-Tree的讀效率，減少讀放大問題.

通過對LSM-Tree結(jié)構(gòu)以及查找機制的分析，我們得出2個限制LSM-Tree讀性能的因素：一是LSM-Tree的查找機制決定了在查找1個鍵時需要額外檢查多個文件；二是壓縮操作也會退化LSM-Tree的讀效率.而更換查找機制或壓縮操作可能需要改變整個LSM-Tree的結(jié)構(gòu)，這樣做的開銷過大.于是，我們考慮通過往LSM-Tree結(jié)構(gòu)中添加新的操作和策略，在保留原有結(jié)構(gòu)和操作的基礎(chǔ)上減少LSM-Tree的讀放大，提高讀效率.以LevelDB為例，我們觀察到在LSM-Tree中的數(shù)據(jù)流動方向是單向的：數(shù)據(jù)從MemTable流動到Immutable MemTable，再從Immutable MemTable被持久化到外存，在外存中漸漸向L6層移動.LSM-Tree這樣的數(shù)據(jù)流動方向能在新舊數(shù)據(jù)同時存在的情況下保證數(shù)據(jù)讀取的正確性.但是，不同數(shù)據(jù)的訪問頻率是不同的，新加入的數(shù)據(jù)靠近內(nèi)存，但不一定具有高訪問頻率.因此，我們在內(nèi)存中提出一個新的存儲結(jié)構(gòu)，在外存中添加了一個新的策略.它們既能保證數(shù)據(jù)讀取的正確性，又能夠根據(jù)數(shù)據(jù)訪問頻率來自適應(yīng)地調(diào)整數(shù)據(jù)的位置，使得高頻數(shù)據(jù)盡可能長時間地駐留在內(nèi)存中或盡可能地靠近內(nèi)存.

2.2 內(nèi)存結(jié)構(gòu)

對內(nèi)存部分來說，原來的結(jié)構(gòu)中Immutable MemTable的數(shù)據(jù)在觸發(fā)持久化操作之前仍可以被訪問.當(dāng)持久化后，對之前在Immutable MemTable中熱數(shù)據(jù)的訪問需要產(chǎn)生IO操作到外存進行讀取.針對這種數(shù)據(jù)單向流動的特點，我們提出LRFO，即使用1個最近最少使用(LRU)隊列和1個先進先出(FIFO)隊列來替換原來的結(jié)構(gòu)，以增加數(shù)據(jù)在內(nèi)存中的駐留時間.LRFO占用的內(nèi)存空間和原來的MemTable和Immutable MemTable占用的內(nèi)存空間相同，其中LRU和FIFO分別占用的內(nèi)存空間相同.

當(dāng)有新數(shù)據(jù)插入到內(nèi)存中時，LRFO首先將其插入到LRU隊列的頭部；當(dāng)LRU隊列的大小達(dá)到閾值時，LRFO從LRU隊列的尾部淘汰數(shù)據(jù).同時，LRFO將被淘汰的數(shù)據(jù)加入到FIFO隊列的頭部.當(dāng)FIFO隊列的大小達(dá)到閾值時，持久化操作被觸發(fā)，此時的FIFO隊列和Immutable MemTable一樣被限制寫操作.同時，LRFO創(chuàng)建1個新的FIFO隊列用于接收LRU隊列淘汰的數(shù)據(jù).當(dāng)查詢數(shù)據(jù)時，LRFO依次在LRU隊列、FIFO隊列中查詢.若在內(nèi)存中查找到數(shù)據(jù)，LRFO返回結(jié)果，并將被查詢的數(shù)據(jù)移動到LRU隊列的頭部.通過這樣易實現(xiàn)的結(jié)構(gòu)，LRFO算法有效地提高了熱數(shù)據(jù)在內(nèi)存中的駐留時間，減少了到外存查找的讀延遲.特別地，LRU隊列并不是固定的，它可以被其他的緩存替換算法所替代，如LRU2Q或LIRS[21]等.

Fig. 3 Example of read and write in memory

圖3展示了LevelDB和LRFO在內(nèi)存中的讀寫操作.圖3(a)首先讀取鍵c.不同于LevelDB，當(dāng)讀完鍵c后，LRFO將FIFO隊列中鍵c移動到LRU隊列的頭部.同時，LRU隊列尾部的鍵e被淘汰到FIFO隊列中.圖3(b)依次更新鍵b和鍵c.LRFO更新完后，依次將鍵b和鍵c挪到LRU隊列頭部，同時按照規(guī)則淘汰尾部鍵值對.在LevelDB中，因為舊的鍵b存儲在Immutable MemTable中，所以新的鍵b被插入至MemTable.又因為MemTable的大小已經(jīng)達(dá)到了閾值，所以LevelDB需要先將Immutable MemTable持久化到外存，同時，將當(dāng)前的Mem-Table轉(zhuǎn)換為Immutable MemTable，并創(chuàng)建1個新的MemTable接收新的鍵b.接著，鍵c直接被插入MemTable中.圖3(c)依次讀取鍵f和鍵d.對于LRFO，讀取完成后，將它們依次移動到LRU隊列的頭部，并按規(guī)則淘汰尾部數(shù)據(jù).LevelDB在Immutable MemTable中讀取到鍵f，但鍵d已經(jīng)隨著之前的持久化操作進入到了外存，所以需要通過IO操作到外存中讀取.

2.3 外存部分

通過觀察外存中的存儲機制，我們發(fā)現(xiàn)了導(dǎo)致LSM-Tree讀效率下降的關(guān)鍵因素：LSM-Tree中的多級存儲結(jié)構(gòu)和壓縮操作.LSM-Tree的多級存儲結(jié)構(gòu)決定了LSM-Tree的查找機制，而壓縮操作逐漸將文件往低層移動，使得這些文件的讀開銷逐漸增加.針對這些機制，我們提出通過增加新的操作來改變數(shù)據(jù)的流向，使LSM-Tree中低層的部分文件能夠向高層移動，以降低讀開銷.

在我們提出的策略中，有2個主要問題需要被解決：

1) 如何確定需要被上浮的文件?

2) 如何進行上浮操作?

(1)

在進行上浮操作之前，我們觀察到LevelDB的存儲結(jié)構(gòu)中具有2個重要的性質(zhì)：

1) SSTable中數(shù)據(jù)的新舊程度從L0層到L6層依次遞減，L0層的數(shù)據(jù)最新，L6層中的數(shù)據(jù)最舊.

2) 除了L0層以外，其余各層中的SSTable之間不存在鍵值范圍重疊.

這2個性質(zhì)分別保證了數(shù)據(jù)讀取的正確性和高效性.若要將上浮1個SSTable，這2個性質(zhì)不能被破壞，否則將產(chǎn)生更大的開銷甚至是錯誤讀取.在上浮的過程中，上浮操作每次都將與目標(biāo)SSTable存在鍵值范圍重疊的SSTable均讀出來，根據(jù)它們過濾掉自己所存儲的舊數(shù)據(jù).具體對于Li層的操作為：1)找出所有與目標(biāo)SSTable存在鍵值范圍重疊的該層的所有SSTable；2)使用類似多路合并的方法，去除目標(biāo)SSTable中重復(fù)鍵的舊鍵值對；3)當(dāng)去除完目標(biāo)SSTable中所有舊鍵值后，繼續(xù)往上一層進行重復(fù)操作，直至到目標(biāo)層，則直接將目標(biāo)SSTable以多路合并的方式插入目標(biāo)層中.

圖4展示了LevelDB和FloatKV在外存中的讀取鍵值對的示例.圖4(a)首先讀取鍵e，F(xiàn)loatKV經(jīng)過多級查找，最終在L6層中找到了對應(yīng)的SSTable.FloatKV返回鍵e的結(jié)果，同時，更新鍵e所在SSTable的訪問頻率.然后，F(xiàn)loatKV判斷該SSTable的訪問頻率是否滿足上浮條件，若滿足，則觸發(fā)上浮操作.該SSTable開始上浮，分別與每層比較，刪除其中的舊數(shù)據(jù).例如，在L1層，鍵f已經(jīng)存在，則該SSTable去除其中的鍵f.最后，該SSTable合并插入到L0層中.圖4(b)讀取鍵g，LevelDB依舊是經(jīng)過多級查找，最終在L6層中找到了對應(yīng)的SSTable.而FloatKV因為前一步將鍵e所在的SSTable上浮到了L0層，所以只需1次文件檢查就找到鍵g.

Fig. 4 Example of read in external memory

2.4 開銷分析

本節(jié)將分析本文提出的內(nèi)存結(jié)構(gòu)及上浮過程可能會產(chǎn)生的額外開銷.對于內(nèi)存結(jié)構(gòu)LRFO，在LRU隊列及FIFO隊列中查找鍵值對的時間復(fù)雜度是O(n)，高于LevelDB中基于跳表實現(xiàn)的Mem-Table的時間復(fù)雜度O(logn).雖然我們可以通過增加額外的Hash表來降低LRFO的時間復(fù)雜度，達(dá)到O(1)的時間復(fù)雜度，但這會占用額外的內(nèi)存空間，從而提高空間復(fù)雜度.同時，考慮到內(nèi)存中的查找時間遠(yuǎn)遠(yuǎn)小于進行IO操作的時間以及在外存查找的時間，故FloatKV僅僅采用簡單的LRFO結(jié)構(gòu).對于外部部分，額外開銷主要來自于FloatKV提出的上浮操作.相比LevelDB，F(xiàn)loatKV每進行1次上浮操作，都需要消耗IO和計算資源.為了避免過多的IO操作引發(fā)寫暫停問題，類比LevelDB，F(xiàn)loatKV也可以通過一定的策略來提高系統(tǒng)性能.具體的做法是當(dāng)上浮操作被觸發(fā)時，F(xiàn)loatKV創(chuàng)建1個后臺進程單獨進行上浮操作.這個后臺進程不會立即修改當(dāng)前的數(shù)據(jù)庫，而是根據(jù)LevelDB中的Current文件，創(chuàng)建1個包含該上浮操作改變當(dāng)前數(shù)據(jù)庫所需要進行的所有操作的集合.當(dāng)上浮操作完成后，這個集合再與當(dāng)前的數(shù)據(jù)庫進行合并，得到新的數(shù)據(jù)庫.最后，Current文件中的內(nèi)容將被更新，指向最新的數(shù)據(jù)庫.這樣的策略可以隱式地執(zhí)行上浮操作，同時又不會破壞數(shù)據(jù)讀取的正確性，盡可能小地減少了對數(shù)據(jù)庫前端操作所產(chǎn)生的影響.

3 實驗與結(jié)果

為了評估我們提出的FloatKV的性能，我們設(shè)計了一系列實驗和6個評價指標(biāo)(讀寫放大、操作總延遲、內(nèi)存中讀取鍵值的數(shù)量、壓縮總數(shù)據(jù)量和查找1個鍵所需平均檢查的文件次數(shù)、從內(nèi)存向LSM-Tree刷入的數(shù)據(jù)量)來檢驗FloatKV.我們選擇了當(dāng)前主流的數(shù)據(jù)庫LevelDB和顯著提升LSM-Tree性能的Wisckey作為對照組.

3.1 實驗配置及環(huán)境

我們采用阿里云的服務(wù)器進行本次的仿真實驗，基本參數(shù)為1核、2 GB內(nèi)存、64位的Ubuntu16.04.我們使用標(biāo)準(zhǔn)數(shù)據(jù)庫性能測試工具YCSB[22]進行測試.YCSB可以用于評估新生代數(shù)據(jù)庫及云數(shù)據(jù)服務(wù)的性能.數(shù)據(jù)的測試分為2個階段：加載階段和運行階段.YCSB通過設(shè)置read，update，insert等參數(shù)來調(diào)節(jié)不同測試樣例的讀寫比例，如表1所示，我們共設(shè)計了8個不同的測試樣例.

在所有的測試樣例中，鍵的大小均為16 B，值的大小均為1 KB.對于每個測試樣例，我們均預(yù)先加載了100 000條鍵值對，隨后進行1 000 000次操作，并記錄1 000 000次操作后對應(yīng)的實驗結(jié)果.我們的實驗?zāi)M了單片Intel 3D NAND flash.該flash包含2 192個塊，每個塊包含1 024個頁，每個塊的大小是16 MB.該flash讀取1個頁、寫入1個頁和擦除1個塊的時間分別是75μs，1,250μs和5 ms.分配給MemTable和Immutable MemTable或LRFO的內(nèi)存大小模擬為8 MB.LevelDB的SSTable大小設(shè)置為2 MB.FloatKV和Wisckey均采用了鍵值分離，故它們的SSTable大小會遠(yuǎn)遠(yuǎn)小于LevelDB的SSTable大小，為了適應(yīng)鍵值分離后的SSTable大小，我們減小了采用鍵值分離策略時對應(yīng)算法的SSTable大小，默認(rèn)設(shè)置為8 KB.

Table 1 Benchmarks

3.2 實驗結(jié)果及分析

讀寫放大問題是我們首要關(guān)心的結(jié)果，它們反映了寫入(讀取)底層存儲設(shè)備數(shù)據(jù)量與用戶請求的數(shù)據(jù)量之比.圖5展示了FloatKV，Wisckey，LevelDB在不同測試樣中的讀寫放大.

Fig. 5 The read and write amplification of FloatKV, Wisckey, LevelDB

實驗結(jié)果可以發(fā)現(xiàn)，F(xiàn)loatKV顯著地減少了讀放大，相比Wisckey和LevelDB分別平均減少了66.49%和90.36%的讀放大.在寫放大方面，F(xiàn)loatKV有所增加，平均是Wisckey的2.29倍，但平均僅是LevelDB的0.24倍.FloatKV通過調(diào)整文件的存儲位置以減少了LSM-Tree檢查文件讀取的數(shù)據(jù)量，從而有效地降低了讀放大.但因為上浮移動的原因，F(xiàn)loatKV將會觸發(fā)更多的壓縮操作，這些壓縮操作所帶來的額外寫開銷會增加FloatKV的寫放大.

我們通過比較查找1個鍵平均所需檢查的文件次數(shù)來反映FloatKV, Wisckey, LevelDB在查找1個鍵時所進行的試探次數(shù).每次的試探需要讀取文件的多個部分(過濾器部分、索引部分等)才能確定鍵是否存在或在文件中的位置，減少試探次數(shù)能夠有效地提高讀效率.

表2展示了3種算法查找1個鍵平均所需檢查的文件次數(shù).實驗結(jié)果反映FloatKV極大地減少了查找1個鍵平均需要檢查的文件次數(shù)，平均僅僅需要檢查2.00次文件就可以查找到結(jié)果，而Wisckey和LevelDB分別需要平均檢查4.75次和4.87次.測試樣例G和H為寫多讀少的情況，F(xiàn)loatKV的上浮頻率相對降低，所以對應(yīng)的平均查找次數(shù)也與Wisckey和LevelDB相差不多.

Table 2 Average Time to Check Files When Looking up a Key

我們還比較了FloatKV, Wisckey, LevelDB在不同測試樣例上的操作總延遲.操作總延遲反映了算法執(zhí)行完所有操作的時間花費，包括讀操作延遲和寫操作延遲.圖6展示了FloatKV, Wisckey, LevelDB在不同測試樣例中的操作總延遲.

Fig. 6 Operation latency of FloatKV, Wisckey, LevelDB

實驗結(jié)果表明，F(xiàn)loatKV有效地降低了操作總延遲，相比Wisckey和LevelDB平均降低了26.18%和66.34%的操作總延遲.FloatKV將高頻訪問的數(shù)據(jù)在向高層移動，使其更靠近內(nèi)存，查詢到真正數(shù)據(jù)時所需要花費的IO操作更少，從而使得操作總延遲更低.

表3展示了FloatKV，Wisckey，LevelDB在內(nèi)存中讀取鍵值對的個數(shù).這個評價指標(biāo)能夠直接反映出查詢數(shù)據(jù)時內(nèi)存的命中率，在內(nèi)存中讀取鍵值對的個數(shù)越多，說明命中率越高.

Table 3 Number of Key-Value Pairs Read in Memory

實驗結(jié)果表明，在讀取操作個數(shù)相同的情況下，F(xiàn)loatKV能夠有效地提高在內(nèi)存中的命中次數(shù)，反映了熱數(shù)據(jù)被盡可能久地留在內(nèi)存中.Wisckey和LevelDB在內(nèi)存中采用相同的結(jié)構(gòu)，它們的實驗結(jié)果是相同的.FloatKV相比它們平均增加了3.08倍的內(nèi)存命中次數(shù).FloatKV采用LRU+FIFO隊列的形式，有效區(qū)分出冷熱數(shù)據(jù)，提高數(shù)據(jù)在內(nèi)存的駐留時間.

表4展示了FloatKV，Wisckey，LevelDB在運行階段從內(nèi)存向LSM-Tree刷入的數(shù)據(jù)量.這個指標(biāo)能夠有效地反映內(nèi)存結(jié)構(gòu)對LSM-Tree的壓縮操作減少的效果.若內(nèi)存結(jié)構(gòu)的緩存能力高，則從內(nèi)存向LSM-Tree刷入的數(shù)據(jù)量將會有所降低，從而減少LSM-Tree中的數(shù)據(jù)量，降低了壓縮操作的觸發(fā)次數(shù)及涉及的數(shù)據(jù)量.

Table 4 The Total Amount of Data Flushed from Memory into LSM-Tree

實驗結(jié)果表明，F(xiàn)loatKV有效地降低了從內(nèi)存向LSM-Tree刷入的數(shù)據(jù)量，相比Wisckey，平均減少了3.87%的數(shù)據(jù)量.FloatKV和Wisckey均采用了鍵值分離的策略，鍵值對中的值均以日志文件的形式存儲，不參與LSM-Tree中的壓縮操作，僅僅只有鍵被刷入LSM-Tree，所以刷入的數(shù)據(jù)量比LevelDB有極大地減少.

最后，我們比較了3種算法在壓縮操作進行時涉及的總數(shù)據(jù)量.其中，F(xiàn)loatKV算法的實驗結(jié)果包括了上浮操作進行時涉及的數(shù)據(jù)量.當(dāng)壓縮操作被觸發(fā)時，大量的計算和IO資源將被用于合并、排序、持久化數(shù)據(jù).表5展示了FloatKV，Wisckey，LevelDB在進行壓縮操作時涉及的總數(shù)據(jù)量.若總數(shù)據(jù)量越大，則說明算法因壓縮操作而產(chǎn)生的讀寫開銷越大.實驗結(jié)果顯示，F(xiàn)loatKV相比LevelDB顯著減少了壓縮時涉及的總數(shù)據(jù)量，平均僅僅為LevelDB的0.15倍，但相比Wisckey卻增加了3.16倍.主要原因是FloatKV添加的上浮操作會產(chǎn)生額外的IO操作，同時，在讀比例大的情況下，頻繁的上浮操作將多次觸發(fā)向下的壓縮操作.但對高頻文件的上浮操作將有效地減少后續(xù)讀這些文件產(chǎn)生的讀開銷，這些讀優(yōu)化足以抵消額外的壓縮操作所帶來的開銷.

Table 5 The Total Amount of Data Involved with Compaction Operation

4 總 結(jié)

本文提出了一種基于訪問頻率分布的上浮式鍵值存儲結(jié)構(gòu)FloatKV，不僅在內(nèi)存中提出了新的數(shù)據(jù)存儲結(jié)構(gòu)，在外存中也設(shè)計了一種基于訪問頻率分布的上浮式鍵值存儲策略.實驗結(jié)果表明FloatKV能夠在不惡化寫放大問題的情況下極大地減少讀放大問題，同時有效地降低了操作總延遲.未來我們將針對LSM-Tree中的其他限制進行重新設(shè)計靈活可變的自適應(yīng)存儲結(jié)構(gòu)和策略，并將我們的技術(shù)置于其他不同特性的應(yīng)用之上.