游理通 王振杰 黃林鵬

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

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

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

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

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

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

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

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

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

本文的主要貢獻總結(jié)有3個方面：

1) 存儲系統(tǒng)功能分區(qū)與索引結(jié)構(gòu)的設計.通過對非易失性內(nèi)存的抽象，只需要用戶重新定義并實現(xiàn)與設備有關(guān)的數(shù)據(jù)結(jié)構(gòu)，就可使用存儲系統(tǒng)，從而實現(xiàn)存儲系統(tǒng)與設備模型的解耦.通過針對鍵值數(shù)據(jù)特性的分析，設計與實現(xiàn)Hash表的結(jié)構(gòu)，使用地址連續(xù)的數(shù)據(jù)結(jié)構(gòu)高效充分利用緩存，使用Hash表對所有的數(shù)據(jù)對象進行索引.對整個設備空間進行功能分區(qū)，確定并記錄各區(qū)域的范圍功能.

2) 非易失性內(nèi)存分配器的實現(xiàn).結(jié)合非易失性內(nèi)存的功能分區(qū)，設計多層次的非易失性內(nèi)存分配器，通過不同層次的功能分離，在不同層次使用不同的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)一個能夠充分結(jié)合非易失性內(nèi)存和DRAM優(yōu)勢的內(nèi)存分配器.

3) 存儲系統(tǒng)垃圾回收算法的設計與實現(xiàn).存儲系統(tǒng)垃圾回收算法以塊為單位對日志中的剩余空間進行回收.通過存儲功能區(qū)的塊狀態(tài)能夠生成垃圾回收算法所需數(shù)據(jù)結(jié)構(gòu)，把這個數(shù)據(jù)結(jié)構(gòu)存放到DRAM中，以提高系統(tǒng)運行效率并減少對NVM的占用.

1 相關(guān)工作

鍵值存儲系統(tǒng)是傳統(tǒng)的關(guān)系型數(shù)據(jù)庫的簡化形式，通過去除不必要的特性，鍵值存儲系統(tǒng)可提升自身性能，降低數(shù)據(jù)間的耦合度.

1.1 傳統(tǒng)鍵值存儲系統(tǒng)

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

1.2 基于非易失性內(nèi)存的鍵值存儲系統(tǒng)

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

1.3 基于非易失性內(nèi)存的文件系統(tǒng)

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

2 TinyKV系統(tǒng)架構(gòu)

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

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

Fig.2 TinyKV memory layout圖2 TinyKV非易失性內(nèi)存功能分區(qū)

Fig.1 Architecture of TinyKV圖1 TinyKV架構(gòu)圖

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

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

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

3 TinyKV設計與實現(xiàn)

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

3.1 存儲區(qū)功能布局

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

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

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

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

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

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

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

3.2 靜態(tài)并發(fā)、緩存友好的Hash表

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

Fig.3 TinyKV Hash table structure圖3 TinyKV Hash表結(jié)構(gòu)圖

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

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

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

Fig.5 Layout of a chain element圖5 數(shù)組鏈數(shù)據(jù)結(jié)構(gòu)圖

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

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

3.3 內(nèi)存分配器

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

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

Fig.6 NVM memory allocators圖6 NVM內(nèi)存分配器

TinyKV內(nèi)存分配器的3層結(jié)構(gòu)詳細描述如下：

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

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

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

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

3.4 多線程應用

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

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

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

3.5 垃圾回收算法

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

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

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

3.6 數(shù)據(jù)持久化

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

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

4 實驗與結(jié)果

4.1 實驗環(huán)境

實驗設備如表1所示，本次實驗中，實驗所用的計算機是Dell-R730，操作系統(tǒng)內(nèi)核版本是Linux 2.6.32.機器裝備了2個10核的CPU，其型號參數(shù)是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 實驗環(huán)境配置

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

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

Table 2 Workload Figures表2 測試數(shù)據(jù)集特征

4.2 讀寫性能

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

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

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

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

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

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

4.3 并發(fā)性能

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

圖9展示了不同系統(tǒng)在小對象均勻分布的數(shù)據(jù)集上的多線程寫性能.可以看出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 多線程性能測試

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

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

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

5 總 結(jié)

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