基于SCM與SSD的混合高效鍵值存儲(chǔ)系統(tǒng)研究

詹 玲，張藝文

1.文華學(xué)院 信息學(xué)部 計(jì)算機(jī)系，武漢 430074

2.華中科技大學(xué) 武漢光電國家研究中心，武漢 430074

隨著信息時(shí)代的高速發(fā)展，各個(gè)領(lǐng)域數(shù)據(jù)都呈現(xiàn)爆發(fā)式增長[1]，同時(shí)人們對(duì)存儲(chǔ)服務(wù)的要求越來越高，許多應(yīng)用（如微信、微博、推特等）都要求以微秒級(jí)的讀寫延遲完成同步響應(yīng)。因此，存儲(chǔ)系統(tǒng)在容量和性能上都受到了前所未有的挑戰(zhàn)。越來越多的各種新型存儲(chǔ)設(shè)備（如固態(tài)存儲(chǔ)、瓦記錄存儲(chǔ)和非易失性內(nèi)存等）以及新型數(shù)據(jù)庫被提出來，以滿足日益增長的存儲(chǔ)系統(tǒng)需求。

存儲(chǔ)設(shè)備方面，固態(tài)硬盤（SSD）逐漸成熟并在某些對(duì)存儲(chǔ)性能有著更高要求的場景替代HDD。SSD的數(shù)據(jù)存儲(chǔ)原理不同于HDD，其內(nèi)部使用的是非移動(dòng)的閃存芯片進(jìn)行數(shù)據(jù)存儲(chǔ)而不是HDD 所使用的轉(zhuǎn)動(dòng)磁盤，節(jié)省了磁盤尋道時(shí)間，因此在性能上優(yōu)于HDD。與此同時(shí)，存儲(chǔ)級(jí)內(nèi)存（Storage Class Memory，SCM）作為一種新型的存儲(chǔ)設(shè)備逐漸人們的視野。SCM也被稱為非易失性內(nèi)存（Non-Volatile Memory，NVM），從物理存儲(chǔ)介質(zhì)上，主要有相變存儲(chǔ)器（PCM）[2]、阻變存儲(chǔ)器（ReRAM）[3]，除此之外還有Intel所開發(fā)的3D XPoint等。SCM擁有字節(jié)可尋址、高讀寫性能以及相對(duì)于DRAM 更高的容量等優(yōu)異的特性，但是其寫性能相對(duì)于DRAM仍有約100倍的差異[4]。Intel基于3D XPoint的SCM存儲(chǔ)設(shè)備Intel Optane DC 已于2019 年正式向市場發(fā)布，可供實(shí)際使用。然而，由于目前SCM的單位存儲(chǔ)價(jià)格高昂，因此在短時(shí)間內(nèi)，通過配置少量SCM 提升系統(tǒng)性能，并通過SSD 提升存儲(chǔ)容量以構(gòu)建混合異構(gòu)存儲(chǔ)系統(tǒng)的方式是一個(gè)經(jīng)濟(jì)可行的方案。

存儲(chǔ)系統(tǒng)方面，鍵值（Key-Value）存儲(chǔ)作為NoSQL的一種，不同于傳統(tǒng)的SQL數(shù)據(jù)庫使用固定的表格模式以及SQL語句進(jìn)行數(shù)據(jù)存儲(chǔ)。KV存儲(chǔ)接口定義更加簡單并且數(shù)據(jù)結(jié)構(gòu)組織更加靈活，能夠根據(jù)不同應(yīng)用場景選擇不同數(shù)據(jù)結(jié)構(gòu)以適應(yīng)相應(yīng)的存儲(chǔ)需求。相關(guān)應(yīng)用主要有Google 開發(fā)的分布式KV 存儲(chǔ)系統(tǒng)BigTable[5]、單機(jī)KV 存儲(chǔ)引 擎LevelDB[6]、Facebook 的Cassandra[7]、基于Hadoop 分布式文件系統(tǒng)的HBase[8]、基于LevelDB優(yōu)化開發(fā)的RocksDB[9]、Yahoo 的PNUTS[10]以及Basho的Riak[11]等。

基于日志結(jié)構(gòu)合并樹（LSM-Tree）[12]的KV 存儲(chǔ)系統(tǒng)因?yàn)槠湎鄬?duì)良好的讀寫性能，被用于許多寫敏感負(fù)載的應(yīng)用場景。KV存儲(chǔ)引擎諸如LevelDB和RocksDB采用了LSM-Tree 的數(shù)據(jù)結(jié)構(gòu)作為KV 存儲(chǔ)引擎的基本數(shù)據(jù)結(jié)構(gòu)。LSM-tree 通過將隨機(jī)寫合并為順序?qū)懙姆绞奖ＷC了出色的寫性能，其多層結(jié)構(gòu)如圖1所示，主要分為內(nèi)存中的有序結(jié)構(gòu)MemTable 和Immutable MemTable以及磁盤上的日志以及分層的SSTable。一個(gè)鍵值對(duì)的寫入操作過程如下：首先鍵值對(duì)會(huì)被順序?qū)懭肴罩?，保證寫入內(nèi)存的鍵值對(duì)不會(huì)因?yàn)橄到y(tǒng)掉電而丟失；然后插入內(nèi)存中基于跳表實(shí)現(xiàn)的有序數(shù)據(jù)結(jié)構(gòu)MemTable中；當(dāng)MemTable 的鍵值數(shù)達(dá)到其容量上限時(shí)，轉(zhuǎn)換為只讀的Immutable MemTable，并創(chuàng)建另一個(gè)MemTable來接收新寫入的鍵值對(duì)；最后將不可變MemTable 通過compact構(gòu)建SSTable并寫入磁盤。

圖1 LSM-Tree結(jié)構(gòu)Fig.1 Structure of LSM-Tree

LSM-Tree 設(shè)計(jì)的目的主要是為了解決HDD 隨機(jī)訪問性能較低的問題，將隨機(jī)訪問轉(zhuǎn)換成了順序訪問。但是這樣的批量寫的方式下，為了保證分層結(jié)構(gòu)的有序引入了compact 操作來保證分層的有序性。compact 操作會(huì)將Li層的1 個(gè)SSTable 與Li+1的10 個(gè)SSTable（默認(rèn)為10）讀入內(nèi)存，然后排序合并再寫回磁盤，因此造成大量的數(shù)據(jù)IO。SCM 與SSD 由于采用基于電路的存儲(chǔ)介質(zhì)，存儲(chǔ)設(shè)備性能相比于HDD有了極大提升，順序訪問與隨機(jī)訪問性能差異也大大降低，LSM-Tree 的compact 操作會(huì)影響新型存儲(chǔ)設(shè)備性能的發(fā)揮，LSMTree 結(jié)構(gòu)不再適用于基于SCM 與SSD 的系統(tǒng)。因此，基于新型存儲(chǔ)設(shè)備設(shè)計(jì)KV 存儲(chǔ)系統(tǒng)需要針對(duì)存儲(chǔ)設(shè)備的特性，優(yōu)化存儲(chǔ)系統(tǒng)的數(shù)據(jù)組織方式以及數(shù)據(jù)結(jié)構(gòu)的選擇。

針對(duì)SCM和SSD的特點(diǎn)，本文設(shè)計(jì)了基于SCM與SSD的混合式高效鍵值存儲(chǔ)系統(tǒng)（SCM and SSD Hybrid Key-Value store，SSHKV）。SSHKV 基于SCM 與SSD異構(gòu)混合存儲(chǔ)架構(gòu)進(jìn)行構(gòu)建。首先，SSHKV在SCM中構(gòu)建SCMHash用于存儲(chǔ)元數(shù)據(jù)，利用SCM的字節(jié)尋址以及低訪問延遲特性實(shí)現(xiàn)元數(shù)據(jù)的快速訪問。其次，為了降低SSD 垃圾回收帶來的數(shù)據(jù)遷移，SSHKV 采用了邏輯空間放大策略，通過放大邏輯空間以及重映射邏輯塊，降低垃圾回收頻率。最后，SSHKV基于半異步半同步式IO 模型實(shí)現(xiàn)，充分利用了現(xiàn)有系統(tǒng)多核的優(yōu)勢。經(jīng)過測試，對(duì)比傳統(tǒng)基于LSM-Tree 的LevelDB 實(shí)現(xiàn)隨機(jī)寫性能20倍的提升。

1 相關(guān)研究

為了解決LSM-Tree的讀寫放大問題，有許多的研究方案通過設(shè)計(jì)新的數(shù)據(jù)組織方案有效減小了讀寫放大。

Lu等人[13]提出了WiscKey，通過將KV存儲(chǔ)中的key和value分離，key以LSM-Tree的形式存儲(chǔ)，而value則以log 的方式管理，有效減少了因?yàn)関alue 參與LSM-Tree的數(shù)據(jù)合并引起的寫放大，提升了系統(tǒng)性能。然而由于采用log存儲(chǔ)value，因此帶來了額外的垃圾回收的開銷。Chan 等人[14]基于WiscKey 的工作進(jìn)而提出了HashKV，將KV數(shù)據(jù)按照Hash進(jìn)行分組，不同組之間通過統(tǒng)計(jì)信息確定GC時(shí)機(jī)，避免了WiscKey中直接GC整個(gè)log帶來的寫放大。同時(shí)根據(jù)數(shù)據(jù)的冷熱，將value log分成了hot和cold兩個(gè)log，進(jìn)一步減少了對(duì)冷數(shù)據(jù)的GC開銷。Yao等人[15]提出的Light-Weight Compaction Tree從另一個(gè)方向優(yōu)化了LSM-Tree的讀寫放大問題，在compaction的時(shí)候LWC 不再將下一層的數(shù)據(jù)讀出，而是直接將上一層的數(shù)據(jù)追加到下一層的Table，并通過更新元數(shù)據(jù)避免多段數(shù)據(jù)帶來的讀開銷，從而提升整體的寫性能。

在結(jié)合存儲(chǔ)設(shè)備特性優(yōu)化KV 存儲(chǔ)系統(tǒng)方面也有很多研究，一類是基于SSD的優(yōu)化，另一類是基于SCM構(gòu)建多存儲(chǔ)設(shè)備混合KV 存儲(chǔ)系統(tǒng)。Kang 等人[16]以及Yang 等人[17]提出一種新型SSD 映射策略以及基于此的RocksDB 優(yōu)化策略，名為multi-stream SSD[16-17]，該方法的主要切入點(diǎn)是減少GC（Garbage Collection）帶來的開銷從而提升訪問效率。通過預(yù)測文件的生命周期從而將生命周期相近的文件通過同一個(gè)數(shù)據(jù)流寫入同一NAND閃存塊中，這樣閃存塊中的數(shù)據(jù)被刪除的時(shí)間相近，就能夠直接將這一個(gè)閃存塊標(biāo)記為無效并直接擦除，避免了有效頁的拷貝過程，從而減少了GC過程中拷貝數(shù)據(jù)帶來的開銷以及帶寬占用。劉峪竹等人[18]提出SSD 友好的鍵值存儲(chǔ)系統(tǒng)SSDKV，該系統(tǒng)跳過了復(fù)雜的中間層，將上層應(yīng)用程序與底層存儲(chǔ)程序相結(jié)合，使用分段地址空間來對(duì)鍵值對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，充分利用存儲(chǔ)設(shè)備的特性來提升總體性能。為了能夠充分利用SSD 內(nèi)部的并行性，出現(xiàn)了Open-Channel SSD[19]，該SSD 使用了特殊的系統(tǒng)，將其內(nèi)部閃存通道暴露給應(yīng)用程序，而上層應(yīng)用即可利用SSD 的多個(gè)通道來提高其并行性，通過優(yōu)化I/O 請(qǐng)求的調(diào)度策略提高數(shù)據(jù)訪問效率。Wang 等人[20]針對(duì)此提出了基于Open-Channel SSD 的KV 存儲(chǔ)。Kannan 等人[21]與Kaiyrakhmet 等人[22]分別提出了NoveLSM 和SLM-DB，均為構(gòu)建SCM 與SSD的混合KV存儲(chǔ)系統(tǒng)，兩者都認(rèn)為SCM與SSD混合存儲(chǔ)在今后一段時(shí)間內(nèi)是有必要存在的。NoveLSM通過構(gòu)建NVM MemTable，實(shí)現(xiàn)DRAM 與NVM Mem-Table的交互使用，減少因?yàn)镸emTable滿了而帶來的系統(tǒng)請(qǐng)求處理中斷，但是當(dāng)數(shù)據(jù)量增大之后，下層的compaction 仍會(huì)造成較大的系統(tǒng)停頓。SLM-DB 基于SCM構(gòu)建單層的KV存儲(chǔ)，將原來多層的LSM-Tree結(jié)構(gòu)改為只有一層，同時(shí)在SCM中新增一個(gè)全局的B+樹進(jìn)行索引，減少系統(tǒng)讀放大。

這些研究工作中，大部分[10-17]是針對(duì)傳統(tǒng)塊設(shè)備（HDD 和SSD）優(yōu)化LSM-Tree 的數(shù)據(jù)組織，其優(yōu)化策略并不能直接應(yīng)用于SCM 設(shè)備上。NoveLSM[18]與SLB-DB[19]針對(duì)SCM于SSD混合架構(gòu)優(yōu)化LSM-Tree，但是由于LSM-Tree 本身的寫放大問題，使得它們并不能充分發(fā)揮SCM 的性能。本文針對(duì)SCM 與SSD 混合的存儲(chǔ)架構(gòu)，考慮了SCM與SSD的性能與容量特性，設(shè)計(jì)了新的鍵值存儲(chǔ)結(jié)構(gòu)SSHKV，充分發(fā)揮不同存儲(chǔ)設(shè)備的優(yōu)勢，實(shí)現(xiàn)性能與容量的兼顧。

2 系統(tǒng)設(shè)計(jì)

2.1 總體結(jié)構(gòu)

SSHKV系統(tǒng)總體架構(gòu)如圖2所示。SSHKV通過將鍵值存儲(chǔ)中元數(shù)據(jù)信息存儲(chǔ)到SCM 中，將數(shù)據(jù)部分以日志方式存儲(chǔ)到SSD 中，實(shí)現(xiàn)性能與容量的兼顧。SCM 設(shè)備具有傳統(tǒng)存儲(chǔ)設(shè)備的掉電非易失特性，并且擁有接近于DRAM的訪問速度。同時(shí)key作為元數(shù)據(jù)，數(shù)量較少而且會(huì)被頻繁訪問。因此，將鍵值對(duì)的key以及相關(guān)元數(shù)據(jù)存儲(chǔ)到SCM設(shè)備中。對(duì)于value數(shù)據(jù)，由于其數(shù)量較大，并且并不是所有數(shù)據(jù)都會(huì)被頻繁訪問，因此將value 數(shù)據(jù)存儲(chǔ)到SSD 中，能夠更好地降低能耗以及存儲(chǔ)成本。

圖2 SSHKV總體結(jié)構(gòu)Fig.2 Overall structure of SSHKV

對(duì)于每個(gè)到達(dá)系統(tǒng)的鍵值請(qǐng)求，key 數(shù)據(jù)直接寫入SCM，由于SCM 具有非易失的特性，所以key 數(shù)據(jù)不用擔(dān)心丟失。由于SSD 需要以塊為單位進(jìn)行寫入，所以value 先寫入內(nèi)存中的緩沖區(qū)，此時(shí)在SCM 中的key 中記錄Value 狀態(tài)為In-Memory，等到緩沖區(qū)的大小超過SSD 的塊大小之后再一并寫入SSD 中的log，同時(shí)修改SCM 中的value 狀態(tài)，并記錄value 在valuelog 中的偏移。

2.2 SCM元數(shù)據(jù)存儲(chǔ)

為了能夠更好地利用SCM 的非易失、字節(jié)可尋址以及高帶寬的特性，SCM 中的元數(shù)據(jù)以哈希的形式進(jìn)行組織。元數(shù)據(jù)包含key值、value偏移、value的大小以及value所在位置等基本信息。為此SSHKV提出了SCMHash結(jié)構(gòu)。

如圖3 所示，SCMHash 將SCM 空間分成大小相等的slot用于存儲(chǔ)元數(shù)據(jù)，每個(gè)slot對(duì)應(yīng)一個(gè)key以及其相關(guān)的元數(shù)據(jù)。為了解決哈希沖突，SSHKV將SCM空間均分為兩段，前半段為正常哈?？臻g，后半段作為沖突空間用于容納所有發(fā)生哈希沖突的key。沖突空間基于bitmap 進(jìn)行空間管理，當(dāng)發(fā)生沖突的時(shí)候，選擇沖突空間中未被使用的一個(gè)slot將元數(shù)據(jù)寫入。

圖3 SCMHash原理示意圖Fig.3 Schematic design of SCMHash

為了對(duì)沖突空間中的元數(shù)據(jù)進(jìn)行尋址，SCMHash定義了沖突鏈，將與哈?？臻g中同一個(gè)slot中所有發(fā)生沖突的key鏈接起來。沖突鏈中前一個(gè)key結(jié)構(gòu)存儲(chǔ)了下一個(gè)沖突key的slot地址，所有的key形成一個(gè)類似鏈表一樣的結(jié)構(gòu)。同時(shí)，存儲(chǔ)slot地址也避免了在SCM中傳統(tǒng)指針因?yàn)橄到y(tǒng)重啟導(dǎo)致虛擬空間地址映射發(fā)生變化而無法訪問原始數(shù)據(jù)的情況。如圖3 的B 所示為一個(gè)沖突鏈的例子，key a～key b 即為一個(gè)沖突鏈，通過key a 可以獲取key b 的地址。寫入key b 時(shí)發(fā)生哈希沖突，則從沖突空間選擇一個(gè)未被使用的slot作為新的key的存儲(chǔ)空間，并寫入這個(gè)key以及對(duì)應(yīng)的value的元數(shù)據(jù)。然后在這個(gè)key的沖突鏈上最后一個(gè)key記錄當(dāng)前key的slot地址。

在SCMHash中進(jìn)行查找的時(shí)候首先計(jì)算哈希值定位正常哈?？臻g中的起始key，然后則按照沖突鏈的順序，逐一進(jìn)行查找并比較key 是否相等，直到找到對(duì)應(yīng)的key或者查找失敗。

2.3 SSD邏輯空間放大管理方法

SSHKV 中的value 數(shù)據(jù)采用日志方式存儲(chǔ)到SSD。SSHKV 采用基于Zone 的方式管理SSD 的空間。SSD空間被分成多個(gè)大小相等的Zone，這些Zone 由多個(gè)連續(xù)的SSD Block 組成。當(dāng)需要寫入value 數(shù)據(jù)的時(shí)候，SSHKV 分配一個(gè)空閑Zone 來容納新寫入的數(shù)據(jù)。當(dāng)沒有空閑Zone 時(shí)，則觸發(fā)垃圾回收，選擇部分Zone，遷移其中的有效數(shù)據(jù)并回收Zone的空間。

SSHKV使用的SSD空間是屬于SSD提供給用戶的邏輯空間，邏輯空間地址通過FTL層映射到一塊物理空間地址上。通常的情況下，SSD邏輯地址空間大小等于SSD物理空間除掉部分內(nèi)部保留空間。

如圖4 是傳統(tǒng)日志結(jié)構(gòu)空間管理的示意圖。一個(gè)Zone 中包含無效數(shù)據(jù)以及有效數(shù)據(jù)，此時(shí)邏輯空間已經(jīng)寫滿，對(duì)于新的數(shù)據(jù)i 就無法寫入，此時(shí)需要觸發(fā)垃圾回收，將有效數(shù)據(jù)從old Zone 遷移到新分配的new Zone，然后在new Zone 寫入數(shù)據(jù)i，最后釋放old Zone的空間。

圖4 傳統(tǒng)日志結(jié)構(gòu)空間管理Fig.4 Traditional log-structured space management

這種垃圾回收需要遷移有效數(shù)據(jù)，帶來一定的寫放大，而觸發(fā)垃圾回收的主要原因是沒有空閑邏輯空間。因此，本文設(shè)計(jì)了一種邏輯地址空間放大的管理策略，邏輯空間放大的策略是在保持物理地址空間不變的情況下，而將邏輯地址空間放大為物理空間的N倍的策略。該策略通過邏輯空間地址重映射，降低因?yàn)檫壿嬁臻g不夠?qū)е碌膽?yīng)用層GC的頻率，達(dá)到減少SSD垃圾回收開銷的目的。

邏輯空間放大策略中，邏輯地址空間的Block 被標(biāo)記為無效后，系統(tǒng)通過TRIM指令標(biāo)記物理空間對(duì)應(yīng)的Block為無效數(shù)據(jù)，SSD則會(huì)在內(nèi)部GC的時(shí)候直接回收這些Block。邏輯空間進(jìn)行寫入的時(shí)候，由于邏輯空間大于物理空間，超出實(shí)際大小的邏輯空間直接映射到被回收的物理空間上，寫入擴(kuò)展Block的數(shù)據(jù)直接被映射到被回收的物理Block 上。由于邏輯空間的大小是原來的N倍，因此垃圾回收的次數(shù)降低了N倍，以此減少了因?yàn)槔厥斩斐傻臄?shù)據(jù)遷移以及邏輯空間整理開銷。

基于邏輯空間放大策略的SSD 空間布局如圖5 所示，其中a、d、f 和g 數(shù)據(jù)塊為無效數(shù)據(jù)，新插入數(shù)據(jù)為i。根據(jù)前面的分析，對(duì)于傳統(tǒng)的日志結(jié)構(gòu)存儲(chǔ)，邏輯空間大小等于物理空間，此時(shí)邏輯空間消耗完，則數(shù)據(jù)i的插入會(huì)觸發(fā)垃圾回收。在邏輯空間放大策略中，無效數(shù)據(jù)塊a 可以直接擦除回收，然后通過重映射，可以直接將放大的邏輯空間映射到被回收的a 數(shù)據(jù)塊占用的空間。此時(shí)可以直接寫入數(shù)據(jù)i，避免了垃圾回收的發(fā)生。

圖5 邏輯空間放大策略Fig.5 Logical space amplification strategy

邏輯空間放大倍數(shù)N的大小可以調(diào)節(jié)，當(dāng)N為1的時(shí)候退化為沒有邏輯空間放大的情況。另外，使用邏輯地址空間放大方法，實(shí)際存儲(chǔ)的數(shù)據(jù)必須不能夠超過物理空間的大小。

2.4 垃圾回收算法

SSHKV邏輯空間被劃分為以塊（Block）為基本單位的空間，多個(gè)Block組成一個(gè)區(qū)（Zone），邏輯空間以Block為單位進(jìn)行寫入，同時(shí)以Zone為單位進(jìn)行垃圾回收。

垃圾回收的時(shí)候需要考慮有效數(shù)據(jù)遷移所帶來的開銷，為了盡可能降低這個(gè)開銷減小對(duì)系統(tǒng)性能的影響，則需要盡可能減少對(duì)有效數(shù)據(jù)的遷移。垃圾回收過程如圖6所示，當(dāng)一個(gè)Zone被寫滿之后可以則加入待回收隊(duì)列，在總的空間使用超過80%（可調(diào)節(jié)）之后觸發(fā)垃圾回收進(jìn)程回收無效空間。進(jìn)行空間整理的時(shí)候首先選擇無效數(shù)據(jù)最多的一個(gè)Zone 作為待回收Zone，然后分配一個(gè)新的Zone，依次讀取Zone 內(nèi)的有效數(shù)據(jù)到內(nèi)存。當(dāng)內(nèi)存中的有效數(shù)據(jù)達(dá)到一個(gè)Block大小的時(shí)候，將內(nèi)存中的數(shù)據(jù)寫到新的Zone 內(nèi)，同時(shí)修改對(duì)應(yīng)的數(shù)據(jù)在SCM中的key記錄的value地址。直到所有數(shù)據(jù)都回收完成之后回收整個(gè)待回收Zone的空間。

圖6 垃圾回收過程Fig.6 Process of garbage collection

3 系統(tǒng)實(shí)現(xiàn)

如圖7 所示，SSHKV 基于半異步半同步式IO 模型進(jìn)行實(shí)現(xiàn)?；谠撃Ｐ偷腟SHKV 總體分為三層：異步任務(wù)層、請(qǐng)求隊(duì)列以及同步任務(wù)層。異步任務(wù)層以異步的方式從外部接收鍵值請(qǐng)求，然后根據(jù)哈希將鍵值散列到請(qǐng)求隊(duì)列中等待同步層處理。同步任務(wù)層被劃分成多個(gè)子系統(tǒng)，每個(gè)子系統(tǒng)以同步的方式處理每個(gè)鍵值請(qǐng)求。每個(gè)子系統(tǒng)維護(hù)一個(gè)請(qǐng)求隊(duì)列。當(dāng)請(qǐng)求隊(duì)列中有待處理的鍵值請(qǐng)求的時(shí)候，子系統(tǒng)從請(qǐng)求隊(duì)列中讀出鍵值請(qǐng)求并進(jìn)行處理。每個(gè)子系統(tǒng)同時(shí)管理一部分的SCM 元數(shù)據(jù)表以及SSD 的邏輯空間中的Zone，進(jìn)行獨(dú)立的空間分配與回收。每個(gè)子系統(tǒng)有一個(gè)后臺(tái)事務(wù)線程和一個(gè)邏輯空間管理模塊。后臺(tái)事務(wù)線程在SSD 邏輯空間使用超過設(shè)定的閾值之后喚醒，開始以Zone 為單位進(jìn)行垃圾回收，邏輯空間管理模塊負(fù)責(zé)管理Block的分配與Zone的回收。

圖7 基于半異步/半同步I/O實(shí)現(xiàn)的模型實(shí)現(xiàn)的SSHKVFig.7 Implementation of SSHKV based on half-sync/half-async I/O model

在系統(tǒng)調(diào)用上，SSHKV支持基本的鍵值操作，包括Put、Get、Scan 以及Delete。所有的操作在調(diào)用SSHKV的對(duì)應(yīng)接口之后，會(huì)被包裝成一個(gè)請(qǐng)求對(duì)象并插入到隊(duì)列層中進(jìn)行處理。后臺(tái)事務(wù)線程探測到請(qǐng)求隊(duì)列中有待處理請(qǐng)求的時(shí)候被喚醒，然后開始處理請(qǐng)求。對(duì)于更新請(qǐng)求（Put 或者Delete），則首先從哈希表中分配一個(gè)合適的位置，然后插入key 以及對(duì)應(yīng)的元數(shù)據(jù)，然后將value 寫入內(nèi)存緩沖區(qū)中等待下刷，或者將對(duì)應(yīng)的value數(shù)據(jù)標(biāo)記為無效。當(dāng)內(nèi)存緩沖區(qū)中數(shù)據(jù)量超過閾值之后，在SSD 中分配一塊區(qū)域，然后將內(nèi)存緩沖區(qū)中的數(shù)據(jù)刷寫到SSD 上。對(duì)于讀請(qǐng)求（Read 或者Scan），首先從SCMHash中獲取帶查找key的元數(shù)據(jù)，然后再到內(nèi)存緩沖區(qū)或者SSD上讀取對(duì)應(yīng)的value。當(dāng)SSD空間使用量到達(dá)閾值之后，系統(tǒng)觸發(fā)后臺(tái)事物線程進(jìn)行垃圾回收，按照2.3節(jié)的方式進(jìn)行釋放無效空間。

4 性能測試與結(jié)果分析

4.1 測試環(huán)境

實(shí)驗(yàn)基本測試配置如表1所示，測試使用Intel Xeon E5-2660 處理器，為了減少操作系統(tǒng)緩存對(duì)測試結(jié)果的影響，將內(nèi)存大小限制為8 GB。存儲(chǔ)設(shè)備方面，通過修改系統(tǒng)啟動(dòng)參數(shù)分配2 GB 內(nèi)存用作模擬SCM 設(shè)備。SCM 設(shè)備通過EXT4-DAX 提供的mmap 內(nèi)存映射的方式進(jìn)行訪問。SSD 設(shè)備以塊設(shè)備文件的方式進(jìn)行直接訪問并管理其中的數(shù)據(jù)，避免了文件系統(tǒng)層的開銷。

表1 測試環(huán)境Table 1 Testing environment

測試基于microbench，microbench測試移植于LevelDB的dbbench，保證對(duì)比測試時(shí)使用的測試工具一致。進(jìn)行測試前，設(shè)置測試基本參數(shù)，key 的大小為16 Byte，value為4 KB，測試的時(shí)候首先隨機(jī)/順序?qū)懭? 500 000條KV項(xiàng)，總數(shù)據(jù)量約10 GB，默認(rèn)底層同步執(zhí)行線程數(shù)為4，邏輯空間放大5倍，即邏輯空間大小為60 GB，實(shí)際可用12 GB。具體配置參數(shù)如表2。

表2 測試參數(shù)配置Table 2 Testing parameter configuration

4.2 測試結(jié)果分析

4.2.1 基礎(chǔ)性能測試

從圖8（a）可以看到，在寫測試上，SSHKV的隨機(jī)寫IOPS 接近LevelDB 隨機(jī)寫的20 倍。同時(shí)在順序?qū)慖OPS 上也是LevelDB 的2 倍左右，并且SSHKV 的隨機(jī)寫IOPS與順序?qū)懶阅芑鞠嗟?。?duì)于隨機(jī)寫，SSHKV采用平面結(jié)構(gòu)，數(shù)據(jù)以半同步半異步IO 的方式寫入SSD，不存在后臺(tái)的重新排序過程，同時(shí)SSHKV采用邏輯空間放大的管理策略，盡可能減少了空間垃圾回收帶來的開銷，因此在隨機(jī)寫上SSHKV 具有較大的優(yōu)勢。而LevelDB 采用的日志結(jié)構(gòu)歸并樹來分層組織硬盤中的數(shù)據(jù)，數(shù)據(jù)通過compaction 操作逐層向下移動(dòng)，由于compaction操作會(huì)進(jìn)行大量數(shù)據(jù)讀寫造成讀寫放大，因此LevelDB 的隨機(jī)寫性能會(huì)受到較大的影響。順序?qū)憸y試中，LevelDB 在compaction 的時(shí)候因?yàn)镾STable 互相沒有key range 重疊，因此只需要修改內(nèi)存元數(shù)據(jù)完成對(duì)SSTable 的level 的修改，性能比隨機(jī)寫高。對(duì)于SSHKV，由于其采用半異步半同步IO的請(qǐng)求處理方式，同時(shí)使用多線程，因此能更加充分地利用SSD 的帶寬，以此達(dá)到相對(duì)于LevelDB更好的性能。

圖8 SSHKV與LevelDB基本性能對(duì)比Fig.8 Basic performance comparison of SSHKV and LevelDB

對(duì)于讀測試，如圖8（b）所示，SSHKV 隨機(jī)讀IOPS約為LevelDB 隨機(jī)讀的13 倍，但是順序讀IOPS 差于LevelDB，約為LevelDB的1/2。對(duì)于LevelDB，每次讀取的時(shí)候需要逐層查找每個(gè)key，需要出發(fā)至少兩次block讀（讀index block 以及filter block），而由于SSHKV 采用平面結(jié)構(gòu)，每次讀直接從內(nèi)存SCM中直接查找key所在數(shù)據(jù)塊的位置，因此固定只會(huì)讀一個(gè)數(shù)據(jù)塊大小，避免了LSM-Tree 結(jié)構(gòu)的讀放大，獲得了更好的性能。對(duì)于順序讀，由于LevelDB的SSTable中數(shù)據(jù)有序存儲(chǔ)，每次讀取一個(gè)key之后后續(xù)的key已經(jīng)被同時(shí)讀到內(nèi)存進(jìn)行緩存，而SSHKV每一次讀都是一次隨機(jī)讀，所以順序讀LevelDB擁有更好的性能。

4.2.2 Value大小敏感測試

對(duì)于不同value大小，選擇64 Byte到64 KB的value，保持總數(shù)據(jù)量不變，測試不同value大小下的性能變化。

從圖9（a）可以看到，對(duì)于不同value的寫性能，SSHKV的寫入速度隨value大小的增加而增加，并在4 KB左右達(dá)到最大值，同時(shí)隨機(jī)寫于順序?qū)慖OPS 始終維持接近的水平，主要是因?yàn)镾SHKV 采用LOG 方式寫數(shù)據(jù)，隨機(jī)寫也變成順序?qū)?。LevelDB對(duì)于不同value大小的寫IOPS基本保持均衡。

圖9 不同Value的基本性能對(duì)比Fig.9 Basic performance comparison of different value sizes

對(duì)于讀性能，如圖9（b）所示，SSHKV與LevelDB的讀IOPS 都隨著value 大小的增加而降低，同時(shí)保持了LevelDB順序讀優(yōu)于SSHKV的順序讀與隨機(jī)讀，LevelDB隨機(jī)讀IOPS 最低的規(guī)律。對(duì)于SSHKV，小于4 KB 的讀IOPS差距不大，而超過4 KB之后讀IOPS顯著降低，主要是因?yàn)镾SD 的訪問粒度為page（一般為4 KB），當(dāng)讀取的value 小于page 大小的時(shí)候仍然需要讀一個(gè)page，當(dāng)value大于page的時(shí)候就需要讀取多個(gè)page，因此value小于4 KB時(shí)，固定讀一個(gè)page，性能接近，value超過4 KB 時(shí)IOPS 隨著讀數(shù)據(jù)塊增加而降低。對(duì)于LevelDB 的讀性能，value 越大意味著一次block 讀能夠讀出來的key 越少，緩存效率更低，因此讀性能隨著value的增加而降低。

5 結(jié)束語

隨著存儲(chǔ)技術(shù)的不斷發(fā)展，同時(shí)擁有memory 特性以及storage 特性的SCM 技術(shù)已經(jīng)逐漸成熟并走向市場，傳統(tǒng)的針對(duì)磁盤設(shè)計(jì)的LSM-Tree 結(jié)構(gòu)不再適應(yīng)于新的存儲(chǔ)設(shè)備的特性，重新設(shè)計(jì)鍵值存儲(chǔ)的結(jié)構(gòu)已經(jīng)迫在眉睫。

本文基于SCM與SSD構(gòu)建了基于混合架構(gòu)的鍵值存儲(chǔ)系統(tǒng)SSHKV，通過使用SCM存儲(chǔ)key以及value的元數(shù)據(jù)達(dá)到快速查找value 位置的目的，同時(shí)通過半異步半同步式I/O更好地利用SSD的高并行性的特點(diǎn)，以達(dá)到最大化的I/O 性能。同時(shí)通過邏輯空間放大策略，減少了SSD中有效數(shù)據(jù)的遷移，進(jìn)一步加快了數(shù)據(jù)寫入SSD，提升了SSHKV的性能。