一個基于日志結構的非易失性內存鍵值存儲系統

游理通 王振杰 黃林鵬

(上海交通大學計算機科學與工程系 上海 200240) (litong.you@sjtu.edu.cn)

近年來，隨著大規模數據分析處理、數據密集型計算等技術的興起和發展，內存計算也成為了更加重要的基礎技術.這些技術都依賴于快速大容量的存儲.除常見的磁盤、SSD和DRAM外，非易失存儲器(non-volatile memory，NVM)技術正在快速發展，例如相變存儲器(phase-change memory，PCM)[1]、自旋矩存儲器(spin-torque transfer ram，STT-RAM)[2]和阻變存儲器(resistive ram，ReRAM)[3]等.這類存儲介質所共有的特點包括可字節尋址能力、接近DRAM的讀寫延遲以及數據的可持久性能力.DRAM和NVM可以抽象為統一的主存儲空間，這種新的混合內存架構為建造更高速有效的大容量持久性存儲系統(如文件系統、數據庫等)帶來了新的機遇.

在軟件技術方面，以LevelDB[4]，Dynamo[5]為代表的鍵值存儲系統已經是業界使用的主流系統，這類存儲系統在非結構化數據存儲方面有很好的性能優勢.現有較為成熟的鍵值存儲系統都是針對磁盤或SSD進行優化設計實現的，它們依靠文件系統來存儲數據，并進一步支持數據持久化.此外，針對非易失內存已有一些文件系統(如HMFS[6-7]，PMFS[8]，NOVA[9]，Octopus[10])，但是依靠文件系統來存儲數據，需要執行文件系統的代碼，并且操作系統也要進行用戶態和內核態之間的切換，這些都會帶來一定的開銷.由于非易失性內存的延時接近于DRAM，這種用戶態/內核態切換開銷對存儲系統的性能的影響是不能忽略的.在基于DRAM內存存儲系統方面，鍵值存儲也是研究熱點，如在實際中被廣泛應用的Memcached[11]、性能非常好的MICA[12]，但針對DRAM設計的系統無法顧及到非易失性內存的特性，如NVM的讀寫延時的差異、DRAM與NVM訪問速度差異等.因此，綜合DRAM和NVM各自特點開發新型的系統需要新的設計思路和實踐.

在使用NVM設計存儲系統時，傳統的基于文件系統和基于磁盤、DRAM或SSD的鍵值存儲系統存在4個問題：

1) DRAM和NVM混合架構下內存分配困難.針對DRAM設計的鍵值存儲系統未考慮到非易失性內存的特性，如非易失性內存的讀寫延時的差異、DRAM與非易失性內存訪問速度差異等因素.

2) 現有鍵值存儲系統數據一致性保障機制性能開銷較大，且未充分利用NVM的非易失特性.傳統架構中，多數系統只基于DRAM設計并維護一個數據日志，所有數據都是以寫日志的方式進行組織，這樣導致的一致性維護開銷較大，NVM的特性很難被充分利用.

3) 垃圾回收復雜.NVM具有讀寫不對稱的特性，因此NVM設備使用一段時間后需要垃圾回收.在日志結構的存儲系統中，數據的更新采用寫時復制的方式進行，舊數據保留在原始位置，形成空間碎片，不能被有效地重新利用.使用NVM設備進行垃圾回收時，需要整合內存碎片，整個過程復雜耗時.

4) NVM設備的并發性能難以得到充分的利用.傳統鍵值存儲系統針對DRAM設計并發機制，這種情況下，頻繁的讀寫操作會限制NVM的性能.

基于以上4點考慮，本文提出一個基于日志結構和非易失性內存構建鍵值存儲系統的方法，并以PCM為代表的存儲類內存(storage class memory，SCM)為存儲介質實現一個鍵值存儲系統TinyKV，其充分考慮了鍵值數據工作負載等特性以及非易失性內存的特點，采用日志結構技術最大化非易失性內存的吞吐性能，并提供可擴展能力和數據一致性保證.

本文的主要貢獻總結有3個方面：

1) 存儲系統功能分區與索引結構的設計.通過對非易失性內存的抽象，只需要用戶重新定義并實現與設備有關的數據結構，就可使用存儲系統，從而實現存儲系統與設備模型的解耦.通過針對鍵值數據特性的分析，設計與實現Hash表的結構，使用地址連續的數據結構高效充分利用緩存，使用Hash表對所有的數據對象進行索引.對整個設備空間進行功能分區，確定并記錄各區域的范圍功能.

2) 非易失性內存分配器的實現.結合非易失性內存的功能分區，設計多層次的非易失性內存分配器，通過不同層次的功能分離，在不同層次使用不同的數據結構，實現一個能夠充分結合非易失性內存和DRAM優勢的內存分配器.

3) 存儲系統垃圾回收算法的設計與實現.存儲系統垃圾回收算法以塊為單位對日志中的剩余空間進行回收.通過存儲功能區的塊狀態能夠生成垃圾回收算法所需數據結構，把這個數據結構存放到DRAM中，以提高系統運行效率并減少對NVM的占用.

1 相關工作

鍵值存儲系統是傳統的關系型數據庫的簡化形式，通過去除不必要的特性，鍵值存儲系統可提升自身性能，降低數據間的耦合度.

1.1 傳統鍵值存儲系統

LevelDB是Google開發的一套針對塊設備進行優化的存儲系統，其核心使用了日志結構合并樹(log-structured merge tree，LSM-Tree)[13]的數據結構.LevelDB的優點是寫操作性能很強，缺點是讀操作性能表現不佳且容易造成嚴重的寫放大.MICA是一個具有很強擴展能力的內存鍵值存儲系統，通過Hash索引結構把所有的鍵進行分區，每個處理器核心負責一個分區的讀寫工作.MICA的內存分配器使用了非嚴格的循環日志結構的分配方式，并對垃圾回收工作進行了新的解釋.在MICA提供的存儲模式中，它使用類似于分離適配(segregated fit)的方式管理內存，具有較高的內存空間使用率.當內存碎片較多時，MICA可能滿足不了大內存的需求.PebblesDB[14]介紹了一種基于碎片化的日志結構合并樹(fragmented log-structured merge trees，FLSM)的鍵值存儲系統，其通過設計新型數據結構FLSM，降低了傳統基于LSM-Tree的鍵值存儲系統寫放大嚴重的問題，有效地提高了系統整體的讀寫性能.

1.2 基于非易失性內存的鍵值存儲系統

Echo[15]是一個針對非易失性內存設計的持久性鍵值存儲系統.它利用DRAM和非易失性內存的兩級存儲結構，把數據緩存到每個線程的DRAM中.每個工作線程可以把數據提交到主線程的隊列里，由主線程負責把DRAM中的數據存儲到非易失性內存的存儲系統中，當讀寫比較頻繁時，可能會有多個主線程同時運行.它通過快照隔離的方式保證數據一致性，并假設計算機硬件可以提供數據持久化的幫助.UDORN[16]是一個基于NVM的持久化內存鍵值存儲數據庫的新型設計框架，在UDORN中，NVM上的持久數據庫被用來完成常規內存數據庫和持久化存儲圖像的功能.在運行時期間，持久性數據庫被映射到進程地址空間，這些操作通過相應的地址空間直接在NVM上執行.與傳統基于NVM Library的Redis系統相比，應用UDORN的Redis獲得了6倍的性能提升.NVMKV[17]是一個閃存感知鍵值存儲器，它依靠閃存轉換層(flash translation layer, FTL)[18]功能在關鍵值存儲處實現最少的數據管理，還有一些針對非易失性存儲器優化的鍵值系統.NVMcached[19]是非易失性存儲器的鍵值緩存，它嘗試通過使用校驗和來剔除損壞的數據以避免大多數緩存溢出.它充當后備緩存，并且任何丟失的鍵值對象都需要被重新插入其中.HiKV[20]在NVM與DRAM的混合內存架構中構建混合索引，利用Hash索引和B+樹索引的特性，提供更有效的鍵值操作，以保持其固有的快速索引搜索能力，避免長時間NVM寫入以保持2個索引的一致性.此外，HiKV將差異并發方案應用于混合索引，并采用有序寫入一致性來確保崩潰一致性.LibreKV[21]使用靜態Hash表和動態Hash表來實現系統性能和內存利用率之間的平衡.其采用基于校驗和的一致性機制來保證數據一致性和永久存儲在NVM上.與傳統的鍵值存儲系統相比，LibreKV獨立工作，不依賴于底層文件系統，簡化了讀寫I/O操作.NVHT[22-23]是一個基于Hash表結構設計的鍵值存儲系統，它針對NVM進行了多項優化，包括非易失指針結構的設計、NVM數據一致性的undo日志解決方案以及結合磨損均衡(wear-leveling)算法的內存分配器設計.

1.3 基于非易失性內存的文件系統

目前許多文件系統的研究工作都致力于在NVM上提供不同的抽象，Mnemosyne[24]，NV-Heaps[25]和NVML[26]提供了通用編程接口和持久性內存和事務機制以實現故障恢復；PMFS，NOVA和Octopus是針對非易失性內存優化的文件系統，它們允許通過POSIX文件接口對傳統的基于文件的內存進行訪問.PMFS使用具有不同CPU指令的多粒度原子更新和用于元數據一致性的細粒度日志記錄以及用于數據一致性的寫入時復制.SIMFS[27]是一個基于NVM的可持續內存文件系統，其充分利用了文件訪問路徑上的內存映射硬件.SIMFS利用一個新型設計框架：文件虛擬地址空間(file virtual address space)，進行文件讀寫操作處理.在這個框架內，當文件被打開時，其文件虛擬地址空間會被嵌入所對應的進程虛擬地址空間，之后的文件訪問由內存映射硬件處理.

2 TinyKV系統架構

本文提出了一個基于非易失性內存的鍵值存儲系統TinyKV.其充分考慮了鍵值系統對象數據比較小并且大小分布比較集中等特性，對存儲系統進行優化設計，通過日志結構的內存管理方式對非易失性內存的磨損均衡也起到了一定的幫助作用.

TinyKV的整體架構如圖1所示.為了支持高并發的數據服務, TinyKV允許多個線程同時訪問鍵值對象.為減少線程間的資源干擾，TinyKV為每個工作線程設置一個單獨的分配器及數據日志.這些分配器被放在DRAM上以支持快速分配.所有線程共享一個全局Hash表來索引鍵值對象.Hash表使用動態分配的數組來解決Hash沖突.使用數組而不是列表可以通過CPU的硬件預取來加速針對鍵值對象的訪問.TinyKV通過全局靜態Hash表來索引數據，并提供插入、讀取和刪除3個應用接口來管理數據.

Fig.2 TinyKV memory layout圖2 TinyKV非易失性內存功能分區

Fig.1 Architecture of TinyKV圖1 TinyKV架構圖

在內存分配器設計中，TinyKV中的每個線程都有自己的內存分配器，這可以減少同步原語引起的開銷.TinyKV使用多級內存分配模型來有效地管理內存，并使用原子寫操作保證每一個數據元素的寫操作是一次獨立的事務，從而保證操作的原子性[8,28]，整個存儲空間首先采取分塊的方式進行管理，然后把分配的塊按功能進行劃分.

TinyKV日志和Hash表都存儲在NVM中.日志是用來保障系統的數據一致性.它首先將鍵值對象添加到日志記錄中;然后才將它們插入到Hash表中，以完成真正的持久化過程.TinyKV可以在故障恢復時掃描日志元數據信息來了解日志空間的使用情況.

此外，TinyKV在NVM中存儲系統全局靜態Hash表和動態鏈.傳統的動態Hash表的大小根據記錄的數量適度增長和收縮，當Hash表需要擴容時，這個過程會導致一定的時間與空間開銷.根據對Facebook負載數據特點的分析[29]，可以得知鍵值數據的大小分布比較集中并且比較小，例如存儲SYS(系統數據)的鍵(key)的大小有90%小于40 B，值(value)的大小有80%在500 B左右.TinyKV根據設備空間的大小，估算預測出整個設備能夠容納多少鍵值對象.根據對象數目計算Hash表的初始大小，通過大Hash表減小了載荷因子，使Hash表產生沖突的可能性減少，減少Hash表擴容的次數，以規劃合適大小的Hash表空間給數據對象.憑借這一手段，TinyKV可以使用靜態Hash表作為存儲數據的索引.為了減少靜態分配的Hash表的大小，系統設定Hash表存儲區的基本組成單位是大小為64 b的字.每個字包含一個指向鍵值對象或Hash表鏈的指針.TinyKV所維護的全局Hash表，在沒有Hash沖突發生時直接訪問鍵值對象，而當沖突發生時，它則將動態數組分配為數組鏈.

3 TinyKV設計與實現

本節主要介紹TinyKV的設計考慮和具體的實現技術.首先，我們介紹TinyKV的存儲區功能布局；接下來介紹一種支持并發并且緩存友好的Hash表,是TinyKV設計的重點；然后介紹內存分配器的詳細設計與TinyKV多線程中的應用；最后，給出TinyKV的垃圾回收算法.

3.1 存儲區功能布局

圖2是TinyKV對非易失性內存的功能分區.類似于操作系統，所有的內存空間以塊為基本管理單位，然后把這些塊根據不同功能進行劃分.每個塊的大小是2 MB，每個塊只允許存儲一種類型的信息，如Hash表的數組鏈或鍵值對象.存儲數據的塊使用順序寫的方式，存儲Hash表的塊使用隨機寫的方式.

1) 超級塊區(super block)記錄了TinyKV的參數信息和對功能區的劃分，如存儲空間的大小、塊的大小、塊的數量、各個分區的起始塊編號和塊數目.這些內容在第1次創建時確定并且不能被修改，它只會在TinyKV啟動時被讀取.

2) 系統狀態區(check point)記錄了TinyKV的運行狀態的數據結構，如上次啟動時間、上次運行時的線程個數、每個線程日志所在的塊編號、Hash表大小、空閑塊數等.每次系統啟動都會產生一個新的狀態，這些狀態保留在一個循環數組中.在系統啟動時，TinyKV會讀取最新的狀態信息，了解Hash表是否經過了擴容，掃描每個線程日志以保證數據的一致性，最后產生一條新的狀態信息，新的狀態信息可能會覆蓋最舊的狀態信息.

3) 塊狀態區(block information table)描述了非易失性內存的每一個塊的信息.塊狀態區中的元素包含與其對應塊的信息，例如鍵值對象或數組鏈的數量、是否為空閑塊以及塊修改的時間.系統將設置一個鏈表把所有的空閑塊鏈接起來，如果當前塊為空閑狀態，那么它將被鏈接至鏈表中.為了減少塊狀態區對內存的占有率，一些存儲區域將會被復用，并將塊被訪問時的狀態信息只存留在DRAM中.每個塊狀態大小為8 B，每個塊的大小為2 MB，其對存儲內存的占有率為8/221=0.000 4%.

4) Hash表區(Hash table)是TinyKV的索引結構，每個桶包含指向鍵值對象的指針、一個標志位記錄是否有線程在修改這個桶以及桶里對象的個數等信息.當桶中包含多個對象時，它的指針是一個數組，這個數組包含了所有屬于這個桶的鍵值對象的地址.在TinyKV中的存儲地址都是一個48 b的無符號整數，它是對象所在位置相對于內存起始地址的偏移量，運行時地址可以通過存儲地址加上內存起始地址的偏移量得到，Hash表的大小是2N，這樣可以根據位運算來計算鍵值對象將要插入的位置.

5) 保留內存區(reserved memory)緊跟在Hash表后面，通過它可以很方便地對Hash表擴容.當數據存儲區內存不足時，它還可以用來存儲數據對象.對Hash表擴容是從保留內存區的塊從前向后分配空間，當用來存儲數據對象時，保留內存區的塊從后向前開始分配.

6)數據存儲區(data area)是為了存儲鍵值對象，或者包含鍵值對象地址的數組.數據存儲區的每個塊只存儲一種類型的數據.當存儲區域的內存不足時，可以向保留內存區申請空間.

3.2 靜態并發、緩存友好的Hash表

圖3展示了TinyKV的Hash表結構.在圖的最左邊是Hash表區域的結構，可以將其看成一個數組.最右邊是TinyKV存儲的鍵值對象.中間是為了解決Hash沖突而動態分配的數組(稱為數組鏈)，這些數組里存儲的是鍵值對象的地址.TinyKV通過計算出key的Hash值找到對應的桶，然后根據桶里的內容確定鍵值對象或者數組鏈的地址.如果桶里只有一個鍵值對象，那么它包含的是鍵值對象的地址；如果桶里有多個對象，為了解決沖突，它包含的地址是數組鏈的地址，數組鏈則包含相應對象數據的地址.

Fig.3 TinyKV Hash table structure圖3 TinyKV Hash表結構圖

為了減少Hash表區域的大小，TinyKV對桶的大小做了限制，其定義如圖4所示.Hash表中每個存儲桶是大小為64 b的字.其中，has_writer表示是否有線程在修改這個桶.TinyKV允許多個線程進行讀操作的同時，最多有一個線程可以修改同一個桶，它由原子操作設置或清除.在并發訪問key-value的模式下，讀事務的順序具有一定的隨機性，如果一個線程A修改key1的同時，另一個線程B進行讀key1，它保證線程B讀到的數據是新數據或是修改前數據，但如果線程A在修改key1之后繼續讀取key1，其讀取的數據是新數據.每個寫線程在訪問任一個桶的同時，它必須檢查has_writer是否為0.如果為0，它把has_writer置1，然后再訪問該桶；如果為1，它就等待.為了保證只有一個線程可以修改同一個桶，必須對has_writer進行保護.TinyKV使用CAS原語保證互斥，它相當于一個自旋鎖的作用，讀線程是不需要讀寫這個鎖的.TinyKV還使用了事務機制，保證寫操作是原子操作，從而保證讀的數據只能是修改前或修改后的數據，從而可以保證讀操作的一致性.

Fig.4 Definition of TinyKV Hash table圖4 TinyKV Hash表的定義

第3個字段reserved表示位于存儲桶中的鍵值對象的數量.version是對桶分裂次數的統計.當Hash表進行擴容時，會有一個變量記錄它擴容的次數.每次對Hash表進行擴容，在Hash表里的桶就會產生一次分裂.當它到達最大值或者保留內存區剩余資源不足時，擴容操作會失敗.nr_objects表示桶里包含的數據對象個數，每個桶最多容納255個元素.nvm_addr是非易失內存內的一個對象的地址.當nr_objects=1時，它指向一個鍵值對象；當nr_objects>1時，它指向一個數組鏈，數組鏈包含鍵值對象的地址.

Fig.5 Layout of a chain element圖5 數組鏈數據結構圖

數組鏈是一個動態分配的數組，其大小與起始地址均為cache_line的整數倍，它的內存是從數據存儲區分配的.數組中的每個元素指向一個鍵值對象.元素的數據格式如圖5所示.每個元素大小是64 b，其中低48 b的nvm_addr存儲鍵值對象的地址，高16 b的tag是對key進行數字描述，它可以用key的Hash值高16 b來表示.在訪問鍵值進行匹配時，需要對key的內容進行逐一匹配.當TinyKV進行查找時，它會先匹配tag，然后再根據nvm_addr訪問鍵值對象.若2個鍵值對象具有相同的tag，再繼續對其nvm_addr進行對比，直至找到所需對象數據.2個不同的key具有相同tag的概率是1216=0.001 5%.故首先比較Hash值高16 b的tag，將會極大地減少了讀取匹配字符串的次數.

為了遍歷一個鏈表，CPU要先把數據從內存中加載到高速緩存中，因為鏈表是結點不連續的存儲結構，CPU訪問內存的次數是不確定的，使用地址連續的數組，可以將CPU訪問內存的次數降到最少.若硬件預取生效，會進一步降低CPU訪問內存的次數.TinyKV沒有明確對桶中的元素數量進行限制，當桶中元素數超出原始設定大小，TinyKV從數據存儲區分配一個新的數組，其大小為原始數組的大小與一個cache_line之和，分配完畢后，將原始數組的數據復制到新的數組中，并把相應的桶的nvm_addr設置為新數組的地址，雖然這可能會造成某些桶元素較多，但這個問題可以通過現有的比較成熟的Rehash機制來解決[30].

3.3 內存分配器

TinyKV對NVM進行分塊管理，其優勢是支持高并發分配.如果對整塊NVM進行統一管理，則NVM塊元數據信息只有一份，則每一次NVM分配都將會鎖定整塊NVM空間的元數據，而不能同時分配多塊NVM區域給多個用戶，因此，鍵值對象不可跨塊存儲.系統采用分塊管理后，每塊NVM空間有自己獨立的元數據信息，從而可以并發地進行修改.基于對Facebook負載數據特點的分析，可以得知，一般的鍵值對象所占用空間較小，內存分配器只需分配一個塊，即可滿足鍵值對象的存儲空間要求.由于分配內存過大或過小都會造成較大的瓶頸，分塊過大，每個塊內的數據元素較多，難以支持高并發的訪問；分塊過小，塊元數據所占的空間開銷較大.因此，TinyKV將分配的塊的大小限制在2 MB以內(塊的大小).當塊空間不足時，需要重新分配新塊，舊塊剩余空間可以繼續用于分配給之后存儲的較小數據元素，這樣雖然會造成一定程度上的內存碎片，但由于鍵值對象本身所占用空間較小，所以內存分配過程中空間浪費情況不是很嚴重.

TinyKV中的每個線程都有自己的內存分配器，這可以減少由同步原語引起的開銷.TinyKV使用多級內存分配模型來有效地管理內存.如圖6所示，TinyKV的內存分配器采用3層結構進行描述，一方面能夠獨立定義各層的功能，另一方面各個層次的結構可以根據需要放在DRAM或非易失性內存中.第1層為塊管理層，它保留一個空的內存塊池，分配和釋放塊；第2層是日志分配層，每個線程都有各自的日志分配器.分配器在分配新日志時需要底層的塊，如果塊變空，它會將塊釋放到底層；第3層是對象分配層，該層是為鏈或鍵值對象分配內存的對象分配器，這些對象分配器無法重復使用日志尾部之前的空間，只能利用來自日志尾部的內存.因此，在刪除鍵值對象時，日志中存在許多不可復用的碎片.為了復用這些內存碎片，分配器需要執行垃圾收集.垃圾收集機制將被廢棄的日志中的一些尚在使用的鍵值對象移動到新的日志中，并將廢棄日志塊釋放到塊管理層.

Fig.6 NVM memory allocators圖6 NVM內存分配器

TinyKV內存分配器的3層結構詳細描述如下：

1) 塊管理層.它負責整個非易失性內存的塊區域內存分配管理.它的主要數據結構是由塊狀態區的數組組成，所以對它的修改要保存到非易失性內存中.所有線程共享一個塊管理層，它負責記錄塊的類型、塊內有效數據的大小、自由鏈表的維護等.它提供的功能有：分配塊、釋放塊、修改塊狀態.由于塊管理層的數據結構可以由所有線程同時修改，所以需要一種同步機制保證數據的一致性，TinyKV使用CAS操作來替代互斥鎖中以提高并發的性能.

2) 日志管理層.一個日志最大的大小是一個塊的大小.每個線程都有一個獨立的日志分配器，日志分配器所維護的數據只能被所有者線程進行修改，所以不需要互斥鎖進行數據同步.由于數據存儲區存儲鍵值對象和數組鏈對象2種數據，所以日志也有2種類型，一種是鍵值數據日志，另一種是數組鏈對象日志.在系統狀態區有記錄各個線程正在使用的日志的塊編號的信息.

3) 對象管理層.它在日志尾部為鍵值對象或者數組鏈分配內存空間.這些對象分配器，無法重復使用日志尾部之前的空間，只能利用來自日志尾部的內存.因此，在刪除鍵值對象時，日志中存在許多不可復用的內存碎片.為了重用這些內存碎片，分配器需要執行垃圾回收.垃圾回收機制將被廢棄的日志中的一些尚在使用的鍵值對象移動到新的日志中，并將廢棄日志塊釋放到塊管理層.

對于每個塊，塊信息表(block information table，BIT)中都有一個記錄塊使用情況的元素.對于寫操作密集型工作負載，塊使用情況經常發生變化.為了減少對NVM的寫操作次數，日志分配器將塊區域信息復制到DRAM，因此塊使用的更新情況保存在DRAM中.當塊區域存儲達到上限時，日志分配器將塊信息轉存到NVM，并使用clwb或clflushopt指令將相關日志數據持久保存至NVM，并要求內存池中新的塊區域啟動新日志.分配內存時，TinyKV使用Lock-Free的更新操作.由于每個線程日志，沒有多個線程將鍵值對象附加到同一個日志中；但是，當2個工作線程想要刪除同一個日志中的鍵值對象時，塊使用信息會被這2個線程同時修改.所以塊信息數據的更新操作必須是原子的，以此保證一致性.

3.4 多線程應用

TinyKV可以通過多線程技術對系統處理用戶請求的能力進行擴展.在多線程編程中一個最常見的問題是數據同步，比較常用的數據同步技術有互斥鎖、條件變量以及讀寫鎖等.一般來說，當發生數據競爭時，鎖的使用會帶來較大的系統開銷.例如futex會在可能發生數據競爭時，使應用程序發生用戶態和內核態的轉換.由于TinyKV的數據更新使用的日志結構，所以數據競爭的情況是不會發生的.但由于Hash表的數據是原地更新，因此要對Hash表的結構進行數據同步操作，對Hash表的每個桶進行鎖保護.

TinyKV實現了一種允許多個讀者和一個寫者同時對一個桶的數據進行訪問的操作.它對讀者不加約束，而寫者在修改桶里的數據時，需要申請寫鎖.由于TinyKV的數組鏈存儲的是指向鍵值對象的地址，每個地址是48 b的，而CPU對數據對齊的64 b字的更新是原子的.當一個寫者與多個讀者同時對一個key進行訪問時，讀者看到的要么是寫者更新后的數據，要么是寫者更新前的數據.

由于TinyKV的日志結構，若未立即刪除舊的數據，不會出現懸垂指針.與鎖相關的信息可以放在DRAM中，也可以放在非易失性內存中.如果將它們放到DRAM中，可以提高運行效率，但是當Hash表很大時，將占用大量的DRAM.如果將它們放入到非易失內存中，加鎖信息可能會持久存儲到NVM中，下次系統啟動時，需要檢測并釋放所有存儲的加鎖信息，因為存儲加鎖信息沒有意義.

3.5 垃圾回收算法

在日志結構的存儲系統中，回收被刪除對象空間的有效方法是垃圾回收算法，垃圾回收算法的時機和策略對性能的影響同樣重要.TinyKV使用垃圾收集線程來回收鍵值對象或鏈式數組被刪除時累積在日志中的空閑內存.TinyKV啟動后，線程掃描BIT以了解塊的使用情況，然后使用與LFS[31]類似的成本收益方法來選擇廢棄的日志.根據日志中的可用空間量和日志的修改時間選擇需要廢棄的日志.對于每個所選日志，垃圾收集線程都會掃描存儲在日志中的鍵值對象，將活動對象復制到新日志并將其重新插入到TinyKV中，然后它將被廢棄的日志內存空間釋放到內存池中，使得其所占用的內存可用于新日志.

TinyKV的垃圾回收算法，包括存儲系統內垃圾的產生及特點、影響垃圾回收性能的因素、垃圾回收的時機以及垃圾回收算法.在TinyKV中，當數據更新時，新數據被追加至日志的尾部，而舊數據的引用在Hash表中被替代，使得舊數據成為失效數據，因此產生了垃圾數據.為了減少垃圾回收的代價，有效數據的占比越小越好.隨著時間的推移，舊日志中的數據被修改的可能性越大，從而有效的數據量越來越少.TinyKV觸發垃圾回收時機有2個：1)當日志內的有效數據為零時；2)當TinyKV中剩余塊不足10%時.當日志內有效數據為零時，塊在代價很小的情況下立即被回收，回收的塊被插入到剩余塊的鏈表尾部.在第2種情況下，TinyKV掃描整個塊狀態表，根據塊的有效數據量和塊上次被修改時間計算花費收益比[30]，根據收益比的數值建立一個最小堆.針對那些日志內有效數據為零的塊，TinyKV的垃圾回收機制可以對其進行異步回收，從而提升垃圾回收的效率.由于在回收的過程中，回收塊中的有效數據非常少，因此TinyKV的垃圾回收效率較高.

在掃描全局塊狀態表，建立起最小堆后，選擇堆頂的塊，把其中的有效數據移動到垃圾回收線程自己的日志中.垃圾回收算法通過掃描被選中塊的所有數據對象，計算對象的Hash值，通過Hash表進行查詢數據對象是否還被引用.如果正在被引用，說明它是有效數據；否則說明它是垃圾對象.由于日志是不允許修改的，并且數據對象不能使用反向指針指向引用它的桶或數組鏈，故在數據被修改或刪除時，TinyKV不能通過標記來記錄數據修改或刪除的信息，所以在掃描時不能單純依靠數據本身識別它是否為有效數據.最后更新Hash表中關于更新被移動數據的索引信息的操作，流程大致與插入操作相似，不同點在于要比較Hash表中的關于這個數據對象的索引信息是否相同.若不同，說明在垃圾回收的過程中，這個數據對象已經被其他線程進行了修改，那么被移動的對象即可刪除；若相同，把索引信息更新到數據對象所在的當前位置.

3.6 數據持久化

目前一種比較有效的方式是把非易失內存和DRAM一樣映射成寫回的方式(write-back)，通過特殊的CPU指令來保證修改的數據能夠最終到達非易失性內存中.clflush是比較傳統的刷新高速緩存行的方式，它把數據從高速緩存中寫回內存中并使高速緩存行失效，多個clflush的順序是固定的；clflushopt是對非易失性內存進行優化而提出的指令，會使高速緩存行失效，但這個指令是無序的.通常情況下，clflushopt的性能比clflush要好，適用于在比較大的數據中使用.clwb同樣是對非易失性內存進行優化而提出的指令，不同于clflushopt的是它不會使高速緩存行失效.不過，這些指令不能保證數據能夠到達非易失性內存上，必須使用內存屏障原語(sfence)明確地表示要等待這些指令的完成.在TinyKV中，只有當日志滿時，才會使用clflushopt或clflush對整個日志的數據持久化；當修改一個數據對象時，持久化必要的元數據信息，同時計算存儲數據的校驗碼，以便在系統恢復時能夠回退到一致狀態.

當TinyKV正常關閉時，為了快速恢復數據，TinyKV會將所有當前活動日志和一些數據結構(例如分配器)轉移至NVM.在TinyKV異常關閉的情況下(例如系統崩潰)，TinyKV必須恢復到一致狀態，并通過掃描數據日志來重建一些數據結構，這個過程較為迅速.TinyKV快速恢復的過程具體描述為：1)檢測TinyKV日志的大小，正常情況下，TinyKV日志的大小不會大于塊的大??；2)當日志已滿時，日志中的鍵值對象通過內存分配器將數據持久化保存到NVM，但可能會存在尚未來得及回收的日志；3)TinyKV為每個可能的未回收的日志啟動一個恢復線程，其會掃描其日志中的所有鍵值對象，記錄第1個損壞對象，將日志的尾部設置為該對象的地址，并將剩余對象故障前的舊地址壓入恢復堆棧；4)通過恢復線程，所有堆棧中的對象將會回滾至故障前狀態.

4 實驗與結果

4.1 實驗環境

實驗設備如表1所示，本次實驗中，實驗所用的計算機是Dell-R730，操作系統內核版本是Linux 2.6.32.機器裝備了2個10核的CPU，其型號參數是Intel?Xeon E5-2650-V3，2.3 GHz，Ivy Bridge EP.每個CPU的L3緩存是25 MB，每個核的L2緩存是10×256 KB.機器上裝備了128 GB的DDR3 DRAM，使用DRAM模擬NVM.

Table 1 Experiment Configuration表1 實驗環境配置

1) 對比系統.本次實驗對TinyKV,LevelDB和Masstree[32]的性能做了比較.LevelDB需要文件系統存儲數據，我們在內存中創建一個文件系統，并把LevelDB的數據文件存放到這個文件系統中.Masstree是一個鍵值內存存儲系統，使用B+樹作為系統的索引結構，類Trie的數據結構對B+樹進行連接.為了減少數據訪問的延遲，它大量采用了數據預取技術.

2) 測試數據集.本次數據采用的數據集是用YCSB[33]性能測試工具集生成的.數據集的類型和大小等信息如表2所示.數據集的類型根據數據的分布特征可分為2種：均勻(uniform)分布和偏斜(skewed)分布.均勻分布的數據是等概率隨機生成的；偏斜分布的數據是根據Zipfian分布生成的，其數據分布的特征是某些數據比大多數數據的出現次數要高很多.根據大小和數據分布，我們生成了4個數據集，其特點如表2所示:

Table 2 Workload Figures表2 測試數據集特征

4.2 讀寫性能

本節將對比各系統單線程的讀寫性能.對于每一類型的數據集合，在進行寫性能測試時，每一次測試，我們都重新建立一個存儲系統，通過持續不斷地插入數據，得出實驗結果.在進行讀性能測試時，所有的存儲系統都預先存儲了6 400萬個數據，通過連續地進行數據查詢，得出實驗結果.系統的單線程寫性能測試結果如圖7所示：

Fig.7 Single thread write throughput圖7 寫性能測試

在TinyKV-flush模式中，TinyKV通過clflush和內存屏障原語對元數據進行持久化.在一個日志空間寫滿時，對整個日志的數據進行持久化，針對未來得及持久化的日志內的數據，依靠系統恢復時檢錯并回滾到一致性狀態.在TinyKV-noflush模式中，不使用刷新高速緩存的指令進行數據持久化.通過對比2種模式的實驗結果揭示數據持久化對系統性能的影響.在測試LevelDB和Masstree時，我們不使用相關指令對數據進行持久化操作.在TinyKV-noflush模式下，TinyKV的寫性能優于LevelDB和Masstree.當進行數據持久化操作時，即在TinyKV-flush模式中，TinyKV的系統寫性能有很大的損失.在數據對象比較小時，吞吐量減少了40%左右;在數據對象比較大時，吞吐量減少了20%左右.

我們比較在TinyKV-flush模式下的TinyKV和LevelDB,Masstree.如圖7所示，在均勻分布的數據集上TinyKV的性能比LevelDB和Masstree要好.在小數據對象的數據集測試中，TinyKV的吞吐量是LevelDB的10倍，是Masstree的2.6倍；在大數據對象的數據集測試中，TinyKV的吞吐量是LevelDB的30倍，是Masstree的7倍.通過大小數據對象的測試性能差異，可以看出TinyKV的索引結構是比較有效率的.另一方面，如圖7所示，在偏斜分布的數據集上，當數據對象比較小時，TinyKV的寫性能要比Masstree要小，這是數據持久化帶來的負面影響.在偏斜分布的數據集中，由于某些數據出現的次數要比大部分數據要多，所以如果能對這些數據做緩存則系統的性能會有很大的提升.這是系統在偏斜分布數據集測試性能比均勻分布數據集優異的原因.但TinyKV使用刷新高速緩存的指令做數據持久化時，會與Hash表和數據鏈有關的高速緩存行失效.這樣，對TinyKV來說，偏斜分布數據集上的數據空間局域性蕩然無存.如果使用clwb替代clflush，這種情況或許能得到改善.

圖8展示了TinyKV,Masstree以及LevelDB的讀性能.讀性能測試不涉及數據的持久化過程，故TinyKV的運行模式是TinyKV-flush.如同Masstree一樣，TinyKV追加一個與key相關聯的value的指針.當存儲系統中不存在key時，返回一個空指針.在不同的數據集上，TinyKV的性能都比其他系統要好.正如系統的寫測試的實驗結果，這些系統在偏斜分布數據集的測試性能比均勻分布數據集的測試性能更加優異.

Fig.8 Single thread read throughput圖8 讀性能測試

4.3 并發性能

在TinyKV系統中，數據查詢不需要加鎖，當不對系統的數據進行修改時，CPU的高速緩存不會由于緩存一致性而失效，系統多線程查詢性能良好.

圖9展示了不同系統在小對象均勻分布的數據集上的多線程寫性能.可以看出TinyKV和Masstree的擴展性比較好.LevelDB的曲線比較平緩，其吞吐量基本維持在0.02 Mops左右；Masstree在單線程時它的吞吐量是0.11 Mops，當使用10個線程時，它的吞吐量也達到了0.21 Mops.TinyKV在單線程時的吞吐量是2.1 Mops，在4線程時它的吞吐量達到了5.4 Mops，在10線程時它的吞吐量達到了6.7 Mops.這一方面得益于TinyKV每個線程使用了專有的日志及Hash表的桶有獨立的寫鎖，另一方面隨著線程的增多，寫鎖資源的競爭會激烈.

Fig.9 Write throughput of multi-threads圖9 多線程性能測試

現有的基于NVM的鍵值存儲系統依賴于一些主流的索引數據結構，如B樹、RB樹等，并在數據更新時保證這些數據結構的一致性.NVTree，FPTree工作是針對B+樹做了并發一致性方面的工作，在范圍查詢方面，B+樹可以表現出更高的性能.TinyKV采用Hash索引方式是為了保證系統的輕量級特性：支持高吞吐率的PUT/GET操作，這在一定程度上犧牲了范圍檢索的性能.

一些鍵值存儲系統，如MICA，HiKV等，同樣采用了Hash結構的鍵值索引方式.但是它們與TinyKV的設計理念不同：MICA是一種高速內存鍵值數據庫，但沒有結合NVM去保證數據持久性.因此，若要支持持久性，現有的MICA需依賴于傳統的技術方案：寫日志到磁盤或定期做檢查點.這會導致以頁(4 KB)為單位的數據同步產生嚴重的I/O開銷.HiKV使用一種混合索引結構，既支持Hash索引也支持B+樹索引.這使得HiKV可以支持復雜的負載數據處理，例如范圍檢索+特定數據集合.然而，在簡單的負載數據處理上，TinyKV仍舊更有優勢.這得益于TinyKV全局Hash的索引結構設計，以及多線程并發機制的支持.

由于時間原因和硬件條件的限制，例如：MICA對服務器和客戶端均做了一定程度的硬件假設，如NUMA結構支持、多核支持等；HiKV暫時不開源，復現工作需要較多時間.因此，我們沒有展開實驗進行說明，敬請諒解.

5 總 結

本文設計并實現一種基于日志結構的非易失性內存鍵值存儲系統TinyKV，采用分塊技術對非易失性內存進行劃分，以塊為單位對存儲空間進行管理；使用日志結構的數據修改方式，既滿足數據一致性的存儲要求又能提高存儲空間的利用率；通過設計多日志的存儲結構，減少多線程的競爭，提高系統擴展能力；設計多級的內存分配器，在底層進行塊管理，中間層進行日志管理，上層進行DRAM數據對象空間分配；實現了一個高效的Hash表作為存儲系統的索引結構，它通過估算Hash表的大小分配比較大的初始空間，從而減少Hash表的沖突概率并減少Hash表的擴容次數；使用動態數組作為解決Hash沖突的存儲方式，對Hash表實現了允許多讀單寫的讀寫方式；在垃圾回收算法中，通過掃描塊狀態表在DRAM中構建運行時需要的數據信息，避免把垃圾回收算法產生的數據存儲到非易失性內存中.實驗測試結果證明，TinyKV具有良好的吞吐性能和擴展能力，在使用均勻分布的小對象數據集進行多線程寫性能測試時，TinyKV單線程的吞吐量為2.1 Mops，4線程的吞吐量為5.4 Mops，TinyKV的吞吐量是LevelDB的10倍，是Masstree的2.6倍；在大對象數據集測試中，TinyKV的吞吐量是LevelDB的30倍，是Masstree的7倍.