游理通 王振杰 黃林鵬

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

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

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

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

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

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

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

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

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

本文的主要貢獻(xiàn)總結(jié)有3個(gè)方面：

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 TinyKV設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 內(nèi)存分配器

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

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

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

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

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

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

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

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

3.4 多線程應(yīng)用

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

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

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

3.5 垃圾回收算法

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

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)設(shè)備如表1所示，本次實(shí)驗(yàn)中，實(shí)驗(yàn)所用的計(jì)算機(jī)是Dell-R730，操作系統(tǒng)內(nèi)核版本是Linux 2.6.32.機(jī)器裝備了2個(gè)10核的CPU，其型號(hào)參數(shù)是Intel?Xeon E5-2650-V3，2.3 GHz，Ivy Bridge EP.每個(gè)CPU的L3緩存是25 MB，每個(gè)核的L2緩存是10×256 KB.機(jī)器上裝備了128 GB的DDR3 DRAM，使用DRAM模擬NVM.

Table 1 Experiment Configuration表1 實(shí)驗(yàn)環(huán)境配置

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

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

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

4.2 讀寫性能

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

Fig.7 Single thread write throughput圖7 寫性能測(cè)試

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

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

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

Fig.8 Single thread read throughput圖8 讀性能測(cè)試

4.3 并發(fā)性能

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

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

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

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

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

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

5 總 結(jié)

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