基于SCM與SSD的混合高效鍵值存儲系統研究

詹 玲，張藝文

1.文華學院 信息學部 計算機系，武漢 430074

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

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

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

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

基于日志結構合并樹（LSM-Tree）[12]的KV 存儲系統因為其相對良好的讀寫性能，被用于許多寫敏感負載的應用場景。KV存儲引擎諸如LevelDB和RocksDB采用了LSM-Tree 的數據結構作為KV 存儲引擎的基本數據結構。LSM-tree 通過將隨機寫合并為順序寫的方式保證了出色的寫性能，其多層結構如圖1所示，主要分為內存中的有序結構MemTable 和Immutable MemTable以及磁盤上的日志以及分層的SSTable。一個鍵值對的寫入操作過程如下：首先鍵值對會被順序寫入日志，保證寫入內存的鍵值對不會因為系統掉電而丟失；然后插入內存中基于跳表實現的有序數據結構MemTable中；當MemTable 的鍵值數達到其容量上限時，轉換為只讀的Immutable MemTable，并創建另一個MemTable來接收新寫入的鍵值對；最后將不可變MemTable 通過compact構建SSTable并寫入磁盤。

圖1 LSM-Tree結構Fig.1 Structure of LSM-Tree

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

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

1 相關研究

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

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

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

這些研究工作中，大部分[10-17]是針對傳統塊設備（HDD 和SSD）優化LSM-Tree 的數據組織，其優化策略并不能直接應用于SCM 設備上。NoveLSM[18]與SLB-DB[19]針對SCM于SSD混合架構優化LSM-Tree，但是由于LSM-Tree 本身的寫放大問題，使得它們并不能充分發揮SCM 的性能。本文針對SCM 與SSD 混合的存儲架構，考慮了SCM與SSD的性能與容量特性，設計了新的鍵值存儲結構SSHKV，充分發揮不同存儲設備的優勢，實現性能與容量的兼顧。

2 系統設計

2.1 總體結構

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

圖2 SSHKV總體結構Fig.2 Overall structure of SSHKV

對于每個到達系統的鍵值請求，key 數據直接寫入SCM，由于SCM 具有非易失的特性，所以key 數據不用擔心丟失。由于SSD 需要以塊為單位進行寫入，所以value 先寫入內存中的緩沖區，此時在SCM 中的key 中記錄Value 狀態為In-Memory，等到緩沖區的大小超過SSD 的塊大小之后再一并寫入SSD 中的log，同時修改SCM 中的value 狀態，并記錄value 在valuelog 中的偏移。

2.2 SCM元數據存儲

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

如圖3 所示，SCMHash 將SCM 空間分成大小相等的slot用于存儲元數據，每個slot對應一個key以及其相關的元數據。為了解決哈希沖突，SSHKV將SCM空間均分為兩段，前半段為正常哈希空間，后半段作為沖突空間用于容納所有發生哈希沖突的key。沖突空間基于bitmap 進行空間管理，當發生沖突的時候，選擇沖突空間中未被使用的一個slot將元數據寫入。

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

為了對沖突空間中的元數據進行尋址，SCMHash定義了沖突鏈，將與哈希空間中同一個slot中所有發生沖突的key鏈接起來。沖突鏈中前一個key結構存儲了下一個沖突key的slot地址，所有的key形成一個類似鏈表一樣的結構。同時，存儲slot地址也避免了在SCM中傳統指針因為系統重啟導致虛擬空間地址映射發生變化而無法訪問原始數據的情況。如圖3 的B 所示為一個沖突鏈的例子，key a～key b 即為一個沖突鏈，通過key a 可以獲取key b 的地址。寫入key b 時發生哈希沖突，則從沖突空間選擇一個未被使用的slot作為新的key的存儲空間，并寫入這個key以及對應的value的元數據。然后在這個key的沖突鏈上最后一個key記錄當前key的slot地址。

在SCMHash中進行查找的時候首先計算哈希值定位正常哈希空間中的起始key，然后則按照沖突鏈的順序，逐一進行查找并比較key 是否相等，直到找到對應的key或者查找失敗。

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

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

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

如圖4 是傳統日志結構空間管理的示意圖。一個Zone 中包含無效數據以及有效數據，此時邏輯空間已經寫滿，對于新的數據i 就無法寫入，此時需要觸發垃圾回收，將有效數據從old Zone 遷移到新分配的new Zone，然后在new Zone 寫入數據i，最后釋放old Zone的空間。

圖4 傳統日志結構空間管理Fig.4 Traditional log-structured space management

這種垃圾回收需要遷移有效數據，帶來一定的寫放大，而觸發垃圾回收的主要原因是沒有空閑邏輯空間。因此，本文設計了一種邏輯地址空間放大的管理策略，邏輯空間放大的策略是在保持物理地址空間不變的情況下，而將邏輯地址空間放大為物理空間的N倍的策略。該策略通過邏輯空間地址重映射，降低因為邏輯空間不夠導致的應用層GC的頻率，達到減少SSD垃圾回收開銷的目的。

邏輯空間放大策略中，邏輯地址空間的Block 被標記為無效后，系統通過TRIM指令標記物理空間對應的Block為無效數據，SSD則會在內部GC的時候直接回收這些Block。邏輯空間進行寫入的時候，由于邏輯空間大于物理空間，超出實際大小的邏輯空間直接映射到被回收的物理空間上，寫入擴展Block的數據直接被映射到被回收的物理Block 上。由于邏輯空間的大小是原來的N倍，因此垃圾回收的次數降低了N倍，以此減少了因為垃圾回收而造成的數據遷移以及邏輯空間整理開銷。

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

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

邏輯空間放大倍數N的大小可以調節，當N為1的時候退化為沒有邏輯空間放大的情況。另外，使用邏輯地址空間放大方法，實際存儲的數據必須不能夠超過物理空間的大小。

2.4 垃圾回收算法

SSHKV邏輯空間被劃分為以塊（Block）為基本單位的空間，多個Block組成一個區（Zone），邏輯空間以Block為單位進行寫入，同時以Zone為單位進行垃圾回收。

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

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

3 系統實現

如圖7 所示，SSHKV 基于半異步半同步式IO 模型進行實現。基于該模型的SSHKV 總體分為三層：異步任務層、請求隊列以及同步任務層。異步任務層以異步的方式從外部接收鍵值請求，然后根據哈希將鍵值散列到請求隊列中等待同步層處理。同步任務層被劃分成多個子系統，每個子系統以同步的方式處理每個鍵值請求。每個子系統維護一個請求隊列。當請求隊列中有待處理的鍵值請求的時候，子系統從請求隊列中讀出鍵值請求并進行處理。每個子系統同時管理一部分的SCM 元數據表以及SSD 的邏輯空間中的Zone，進行獨立的空間分配與回收。每個子系統有一個后臺事務線程和一個邏輯空間管理模塊。后臺事務線程在SSD 邏輯空間使用超過設定的閾值之后喚醒，開始以Zone 為單位進行垃圾回收，邏輯空間管理模塊負責管理Block的分配與Zone的回收。

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

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

4 性能測試與結果分析

4.1 測試環境

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

表1 測試環境Table 1 Testing environment

測試基于microbench，microbench測試移植于LevelDB的dbbench，保證對比測試時使用的測試工具一致。進行測試前，設置測試基本參數，key 的大小為16 Byte，value為4 KB，測試的時候首先隨機/順序寫入2 500 000條KV項，總數據量約10 GB，默認底層同步執行線程數為4，邏輯空間放大5倍，即邏輯空間大小為60 GB，實際可用12 GB。具體配置參數如表2。

表2 測試參數配置Table 2 Testing parameter configuration

4.2 測試結果分析

4.2.1 基礎性能測試

從圖8（a）可以看到，在寫測試上，SSHKV的隨機寫IOPS 接近LevelDB 隨機寫的20 倍。同時在順序寫IOPS 上也是LevelDB 的2 倍左右，并且SSHKV 的隨機寫IOPS與順序寫性能基本相等。對于隨機寫，SSHKV采用平面結構，數據以半同步半異步IO 的方式寫入SSD，不存在后臺的重新排序過程，同時SSHKV采用邏輯空間放大的管理策略，盡可能減少了空間垃圾回收帶來的開銷，因此在隨機寫上SSHKV 具有較大的優勢。而LevelDB 采用的日志結構歸并樹來分層組織硬盤中的數據，數據通過compaction 操作逐層向下移動，由于compaction操作會進行大量數據讀寫造成讀寫放大，因此LevelDB 的隨機寫性能會受到較大的影響。順序寫測試中，LevelDB 在compaction 的時候因為SSTable 互相沒有key range 重疊，因此只需要修改內存元數據完成對SSTable 的level 的修改，性能比隨機寫高。對于SSHKV，由于其采用半異步半同步IO的請求處理方式，同時使用多線程，因此能更加充分地利用SSD 的帶寬，以此達到相對于LevelDB更好的性能。

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

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

4.2.2 Value大小敏感測試

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

從圖9（a）可以看到，對于不同value的寫性能，SSHKV的寫入速度隨value大小的增加而增加，并在4 KB左右達到最大值，同時隨機寫于順序寫IOPS 始終維持接近的水平，主要是因為SSHKV 采用LOG 方式寫數據，隨機寫也變成順序寫。LevelDB對于不同value大小的寫IOPS基本保持均衡。

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

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

5 結束語

隨著存儲技術的不斷發展，同時擁有memory 特性以及storage 特性的SCM 技術已經逐漸成熟并走向市場，傳統的針對磁盤設計的LSM-Tree 結構不再適應于新的存儲設備的特性，重新設計鍵值存儲的結構已經迫在眉睫。

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