余陽 胡卉芪 周煊

摘要：隨著大數(shù)據(jù)時(shí)代的到來，金融行業(yè)產(chǎn)生的數(shù)據(jù)越來越多，對數(shù)據(jù)庫的壓力也越來越大.LevelDB是 谷歌開發(fā)的一款基于LSM-tree架構(gòu)的鍵值對數(shù)據(jù)庫，有寫入快和占用空間小的優(yōu)點(diǎn)，被金融行業(yè)廣泛應(yīng) 用.針對LSM-tree架構(gòu)的寫停頓、寫放大、對讀不友好等缺點(diǎn)，提出了一種基于非易失性內(nèi)存和機(jī)器學(xué)習(xí) 的L0層的設(shè)計(jì)方法，能夠減緩甚至解決上述問題.實(shí)驗(yàn)結(jié)果表明，該設(shè)計(jì)能夠?qū)崿F(xiàn)較好的讀寫性能.

關(guān)鍵詞：非易失性內(nèi)存;機(jī)器學(xué)習(xí);LSM-tree架構(gòu)

中圖分類號：TP392?????? 文獻(xiàn)標(biāo)志碼：A DOI： 10.3969/j.issn.1000-5641.2021.05.004

Optimization of LSM-tree storage systems based on non-volatile memory

YU Yang， HU Huiqi， ZHOU Xuan

（School of Data Science and Engineering， East China Normal University， Shanghai 200062， China）

Abstract： With the advent of the big data era， the financial industry has been generating increasing volumn of data， exerting pressure on database systems. LevelDB is a key-value database， developed by Google， based on the LSM-tree architecture. It offers fast writing and a small footprint， and is widely used in the financial industry. In this paper， we propose a design method for the L0 layer， based on non-volatile memory and machine learning， with the aim of addressing the shortcomings of the LSM-tree architecture， including write pause， write amplification， and unfriendly reading. The proposed solution can slow down or even solve the aforementioned problems; the experimental results demonstrate that the design can achieve better read and write performance.

Keywords： NVM; machine learning; LSM-tree architecture

0引 言

近年來，以LevelDB和RocksDB為代表的LSM-tree （log-structured merge tree）存儲(chǔ)引擎憑借其 良好的寫性能被應(yīng)用于多種數(shù)據(jù)庫設(shè)計(jì)中.隨著金融、互聯(lián)網(wǎng)等行業(yè)的不斷發(fā)展和成熟，在人工智 能、大數(shù)據(jù)、云計(jì)算等新技術(shù)的帶動(dòng)下，數(shù)據(jù)源不斷增加，導(dǎo)致數(shù)據(jù)的絕對數(shù)量和產(chǎn)生速率都在以驚 人的速度膨脹.根據(jù)微軟[1]和戴爾易安信主導(dǎo)的研究表明，2020年全球共產(chǎn)生了 40 ZB以上的數(shù)據(jù). 因?yàn)長SM-tree架構(gòu)具有寫放大和對讀不友好的缺點(diǎn)，巨量的數(shù)據(jù)也給這個(gè)技術(shù)帶來了不小的挑戰(zhàn).

最近幾年出現(xiàn)的非易失性內(nèi)存（Non-Volatile Memory，簡稱NVM，也被稱為Persistent Memory， 即PMEM，目前落地的產(chǎn)品是Intel的AEP）被認(rèn)為是一種繼Solid State Disk （簡稱SSD）之后的新 一代存儲(chǔ)設(shè)備，是具有“革命性”的存儲(chǔ)產(chǎn)品，會(huì)大幅提升數(shù)據(jù)存儲(chǔ)的性能.與計(jì)算、網(wǎng)絡(luò)產(chǎn)生的延遲相比，存儲(chǔ)的延遲往往是非常高的.然而由于存儲(chǔ)單元數(shù)量有限，可供能源有限，插槽數(shù)量有限，使得 繼續(xù)提高Dynamic Random Access Memory （簡稱DRAM）的大小不太可能.所以探索NVM在低時(shí) 延和高吞吐的系統(tǒng)中的應(yīng)用變得非常重要.

LSM-tree架構(gòu)使用數(shù)據(jù)量指數(shù)遞增的不同層來維護(hù)層內(nèi)有序的數(shù)據(jù).為了更好地理解基于 LSM-tree的鍵值對存儲(chǔ)，我們通過實(shí)驗(yàn)評估了 Google開發(fā)的基于DRAM-SSD的主流鍵值對存儲(chǔ) LevelDB[3]，發(fā)現(xiàn)其在大量數(shù)據(jù)并發(fā)寫入的情況下出現(xiàn)了以下缺點(diǎn)：一是寫停頓，即磁盤中的數(shù)據(jù)合并 速度慢，導(dǎo)致內(nèi)存中的數(shù)據(jù)無法寫入磁盤，使得用戶的寫入指令無法執(zhí)行，產(chǎn)生寫停頓，這違背了運(yùn)營 數(shù)據(jù)庫的可預(yù)測和穩(wěn)定性能的設(shè)計(jì)目標(biāo).二是寫放大，即已經(jīng)寫入磁盤的數(shù)據(jù)在合并時(shí)會(huì)被讀出來并 重新排序?qū)懭氪疟P，這樣的排序和讀寫磁盤會(huì)消耗大量CPU時(shí)間和SSD帶寬，大大增加前臺的查詢 時(shí)延.三是由于L。層的數(shù)據(jù)并沒有維護(hù)一個(gè)全局的范圍，所以隨著L。層的數(shù)據(jù)增加，查詢消耗在 L0層上的時(shí)間會(huì)隨著數(shù)據(jù)量線性增加.

傳統(tǒng)的DRAM-SSD的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)是為了利用DRAM的高性能和SSD的持久化能力以盡量低 的成本提供相對高效的數(shù)據(jù)庫服務(wù)，其中的高性能部分主要是由DRAM的低時(shí)延和高吞吐所保證的， 由于LSM-tree的架構(gòu)特性在Minor Compaction的時(shí)候存在DRAM到SSD的突發(fā)性高負(fù)載，這個(gè)時(shí) 候能夠快速完成Compaction釋放內(nèi)存以處理新的請求對數(shù)據(jù)庫整體的性能至關(guān)重要，而這個(gè)過程主 要受制于L。層的寫性能，所以用有高寫入性能的NVM做L。層對數(shù)據(jù)庫的整體性能理論上會(huì)有比較 大的提升，由于Major Compaction不涉及DRAM到可持久化設(shè)備的這個(gè)過程，所以影響相對較小， 考慮到經(jīng)濟(jì)因素，除了 L。層外的持久化層還是用SSD.

本文以LSM-tree架構(gòu)的上述缺點(diǎn)為出發(fā)點(diǎn)，引入NVM組成DRAM-NVM-SSD的混合存儲(chǔ)減緩 甚至解決了上述問題.

本文的主要貢獻(xiàn)如下：

（1）在DRAM和SSD的LSM-tree存儲(chǔ)架構(gòu)中，增加了 NVM層，并且設(shè)計(jì)了相對離散的結(jié)構(gòu)，使 用類似內(nèi)存池的技術(shù)給其分配空間;

（2）在NVM層上使用Learned Index技術(shù)，用學(xué)習(xí)到的索引模型預(yù)測數(shù)據(jù)的位置，加快數(shù)據(jù)在 NVM上的查找;

⑶棄用LSM-tree架構(gòu)中傳統(tǒng)的Major/Minor Compaction模式，采用漸進(jìn)式的Compaction.

1 研究背景

本章介紹有關(guān)NVM和LSM-tree架構(gòu)的背景，闡述目前LSM-tree架構(gòu)和NVM的相關(guān)研究工作.

1.1非易失性內(nèi)存

服務(wù)提供商一直都在追求更快的數(shù)據(jù)庫訪問.他們旨在不提高總擁有成本（TCO）的同時(shí)，提供給 用戶更好的服務(wù)和體驗(yàn).隨著新型存儲(chǔ)介質(zhì)的開發(fā)和出現(xiàn)，例如相變內(nèi)存[4]、憶阻器3D XPoint[6]和 STT-MRAM['使用NVM增強(qiáng)存儲(chǔ)系統(tǒng)成為一個(gè)比較經(jīng)濟(jì)的選擇.NVM是一種可字節(jié)尋址的、可持 久化的、低時(shí)延的存儲(chǔ)介質(zhì).它被認(rèn)為有望提供類似DRAM的讀寫性能，類似磁盤的持久化能力，并 以更低的價(jià)格提供比DRAM更大的空間.與SSD相比，NVM有望提供百分之一的讀寫延遲和10倍 以上的帶寬[8].

NVM可以用作通過PCIe接口訪問的可持久化存儲(chǔ)設(shè)備，也可以用作通過內(nèi)存總線訪問的主內(nèi) 存[9].現(xiàn)有研究[10]表明前者只能實(shí)現(xiàn)邊際性能的改善，浪費(fèi)了 NVM作為存儲(chǔ)介質(zhì)的高性能.對于后者， NVM可以取代或者補(bǔ)充DRAM作為單極存儲(chǔ)器系統(tǒng)[10]、NVM-SSD系統(tǒng)[11]或DRAM-NVM-SSD混 合系統(tǒng)[101.特別地，由于以下3個(gè)原因，使用DRAM-NVM-SSD混合存儲(chǔ)被認(rèn)為是一種使用NVM比 較有前景的方法.首先，NVM有望在接下來的數(shù)年中與大容量SSD共存.其次，DRAM依然有比NVM 低3倍的讀寫延遲和高5倍的帶寬.最后，混合系統(tǒng)平衡了總擁有成本和系統(tǒng)性能.所以我們的系統(tǒng) 將專注于把NVM作為可持久化內(nèi)存，高效地運(yùn)用在DRAM、NVM和SSD組成的混合系統(tǒng)中.

1.2 LSM-tree 架構(gòu)

LSM-tree[12]架構(gòu)通過分層設(shè)計(jì)充分利用存儲(chǔ)設(shè)備的高順序?qū)憥?圖1是LevelDB的架構(gòu)圖，是 一種基于DRAM-SSD的LSM-tree架構(gòu)的鍵值數(shù)據(jù)庫.它擁有防止DRAM中數(shù)據(jù)丟失的redo日志， 防止數(shù)據(jù)受系統(tǒng)崩潰的影響.

寫操作.數(shù)據(jù)首先寫入磁盤，作為數(shù)據(jù)庫恢復(fù)的Redo-Log;然后寫入內(nèi)存中的MemTable， MemTable由跳表實(shí)現(xiàn)，維護(hù)數(shù)據(jù)的有序性.數(shù)據(jù)的寫入到此結(jié)束.當(dāng)MemTable寫滿后，轉(zhuǎn)變成不可 寫入只可讀取的 MemTable （Immutable MemTable）;再將 Immutable MemTable 寫入磁盤中的 L0 層，格式變?yōu)镾STable，這一過程稱為Minor Compaction;當(dāng)L0層數(shù)據(jù)達(dá)到閾值時(shí)，與L：層進(jìn)行合并， 這一過程稱為Major Compaction;磁盤中的每一層數(shù)據(jù)到達(dá)閾值后均向下進(jìn)行Major Compaction.

在LSM-tree架構(gòu)中，存在3種類型的寫停頓.插人停頓：如果MemTable在Immutable MemTable 刷盤完成前被填滿，所有寫入LSM-tree的操作都會(huì)停止.刷盤停頓：如果L0層有許多的SSTable并 且達(dá)到了大小限制，則會(huì)阻止刷盤.合并停頓：太多的等待執(zhí)行合并的任務(wù)阻塞了前臺的操作，導(dǎo)致寫 停頓.

L。層的每個(gè)SSTable文件內(nèi)部的鍵值對是有序的，但文件之間是無序的甚至?xí)薪患?L1層及以 上每一層的數(shù)據(jù)都是全局有序的，并且保證每一層的SSTable文件之間是沒有交集的.

執(zhí)行一次 Major Compaction，首先確定 L，層參加 Compaction 的 SSTable （被稱為 Victim SSTable） 和 Lz+1 層中與 Victim SSTable 范圍有交集的 SSTable （被稱為 Overlap SSTable）作為 Compaction 的 初始輸入.落入這個(gè)擴(kuò)大后的范圍的^層的其他SSTable被反向選擇，從而確定了全部輸入.將之前 選擇的所有SSTable使用外部歸并排序的方式寫回到Lw層.由于L0層是未排序的，并且L0層中的 每一個(gè)SSTable的key范圍都很大，所以幾乎會(huì)選擇Lq層和L1層中的所有SSTable來進(jìn)行排序，導(dǎo) 致了全量的寫放大.

讀操作.讀數(shù)據(jù)首先查詢MemTable，然后查詢Immutable MemTable，最后是L0層到Ln層中的 SSTable.由于LO層沒有維護(hù)全局有序性，在LO層可能會(huì)查詢多個(gè)文件.

1.3LSM-tree研究現(xiàn)狀

現(xiàn)有的基于LSM-tree架構(gòu)的提升包括：減少寫放大、提高內(nèi)存管理水平、支持自動(dòng)優(yōu)化、用混合 存儲(chǔ)優(yōu)化LSM-tree架構(gòu)等.在這些工作中，隨機(jī)寫性能是一個(gè)被共同關(guān)注的點(diǎn)，因?yàn)槭蹸ompaction 影響，隨機(jī)寫會(huì)導(dǎo)致寫停頓和寫放大.下面討論工作中最相關(guān)的3類：減少寫放大，處理寫停頓和使用 NVM.

減少寫放大.PebblesDB[13]受到跳表啟發(fā)，使用了 guard來維護(hù)一層的局部有序性;Lwc-tree[14]提 供了追加寫數(shù)據(jù)合并元數(shù)據(jù)的輕量級Compaction; WiscKey[15]將鍵從值中分離出來，僅在Compaction 的過程中合并鍵，因此降低了寫放大.但是其缺點(diǎn)是使垃圾回收和范圍查詢變得復(fù)雜，并且只從較大 的值中收益;LSM-trie[16]通過使用基于hash范圍的Compaction來均攤Compaction的額外開銷;VT- tree[17]以數(shù)據(jù)碎片為代價(jià)，使用額外的一層來重定向數(shù)據(jù)以避免重復(fù)處理使數(shù)據(jù)有序;TRIAD[18]通過 在內(nèi)存，磁盤和日志之間創(chuàng)建協(xié)同工作來減少寫放大;MatrixKV[19]在LO層上維護(hù)了一個(gè)邏輯上和 L）層的SSTable對應(yīng)的key范圍映射，減少了 Compaction時(shí)L0層的輸入大小.

減少寫停頓.SILK[20]引入了一個(gè)I/O調(diào)度器，它通過推遲刷盤和Compaction時(shí)間到低負(fù)載的時(shí) 候來減輕寫停頓對用戶的寫影響;bLSM[21]提出了一種新的合并調(diào)度程序，用來協(xié)調(diào)多個(gè)級別的壓縮; KVell[22]使得每一項(xiàng)鍵值在磁盤上亂序，從而減輕了基于NVMe SSD鍵值存儲(chǔ)的寫停頓，這不適用于 通用的SSD的系統(tǒng).

使用NVM優(yōu)化LSM-tree架構(gòu).SLM-DB[23]針對具有NVM-SSD存儲(chǔ)的系統(tǒng)提出了單級的LSM- tree.它使用NVM上的B+樹來索引SSD上面的單層LSM-tree以提供快速讀.這個(gè)方法引入維護(hù) B+樹和LSM-tree —致性的額外消耗;MyNVM[24]利用NVM作為塊設(shè)備來減少基于SSD的鍵值存儲(chǔ) 的DRAM使用;NoveLSM[10]和NVMRocks[9]采用了在NVM上的持久化可變內(nèi)存表.然而，可變的 NVM內(nèi)存表僅僅在某種程度上減少了訪問時(shí)延，同時(shí)產(chǎn)生了更嚴(yán)重的寫入停頓的負(fù)面影響; MatrixKV維護(hù)了 L。層上SSTable之間的偏序關(guān)系，從而減少了 L。層上整體的查找時(shí)延.

2問題分析

NVM能提供比SSD快100倍的讀寫速度和高10倍的帶寬，但是傳統(tǒng)的LSM-tree架構(gòu)中的軟件 棧能否完全利用NVM的硬件優(yōu)勢？為了理解在LSM設(shè)計(jì)中使用NVM的影響，我們使用NVM替換 SSD，來存儲(chǔ)SSTable，分析讀寫數(shù)據(jù)的性能差異.數(shù)據(jù)的總大小是16 GB，單個(gè)鍵值對的大小是4 kB， 單個(gè)SSTable的大小是8 MB.圖2比較了對SSTable進(jìn)行順序讀、隨機(jī)讀、順序?qū)懞碗S機(jī)寫的吞吐量.

如圖2所示，盡管NVM硬件提供了相對于SSD更快的讀和寫，但是順序讀和隨機(jī)讀時(shí)延相對 SSD僅僅減少了二分之一;順序?qū)憰r(shí)延僅僅減少為原來的六分之一.這個(gè)結(jié)果說明當(dāng)前的LSM- tree 架構(gòu)并沒有充分利用 NVM 硬件的優(yōu)勢， 而且花費(fèi)了大量的軟件開銷.我們之后來說明這些軟件 開銷的來源.

寫操作時(shí)延.主要有3處：一是在數(shù)據(jù)寫入內(nèi)存表之前，為了避免機(jī)器故障或者斷電引起的數(shù)據(jù)丟 失，首先會(huì)將數(shù)據(jù)及它的校驗(yàn)和寫入磁盤的時(shí)延;二是數(shù)據(jù)寫入MemTable的時(shí)延;三是合并帶來的尾 時(shí)延，LSM-tree架構(gòu)中，Minor Compaction需要將Immutable MemTable的數(shù)據(jù)寫入磁盤，并序列化為 SSTable的格式，如果Minor Compaction耗時(shí)較長，會(huì)導(dǎo)致MemTable無法寫人.Major Compaction需 要占用大量CPU資源和磁盤帶寬，會(huì)拖慢所有的前臺請求.兩種Compaction操作都會(huì)導(dǎo)致寫人時(shí)延.

圖3顯示了 4 kB，8 kB，16 kB這3種大小數(shù)據(jù)的3種寫操作時(shí)延.如圖3所示，數(shù)據(jù)合并在時(shí)延中占比 最大，達(dá)到了 79%;寫日志占了總寫入時(shí)延的21%;寫入內(nèi)存表的速度很快，幾乎不用考慮它的時(shí)延.

讀操作時(shí)延·主要分為兩處：一是讀內(nèi)存，包括讀取MemTable和Immutable MemTable.二是讀 磁盤，從低往高讀取每一層的SSTable文件.首先讀SSTable文件中的索引，找到數(shù)據(jù)在SSTable文 件中的位置，再將找到的數(shù)據(jù)塊拷貝到內(nèi)存中，反序列化為內(nèi)存格式，再在數(shù)據(jù)塊中查找具體數(shù)據(jù). 圖4分析了讀4 kB、8 kB和16 kB這3種大小的數(shù)據(jù)的讀時(shí)延占比.對于小的值，查找SSTable占據(jù) 了主要時(shí)延;隨著值大小的增加，反序列化和數(shù)據(jù)拷貝的占比逐漸增加.

總結(jié)· LSM-tree架構(gòu)的讀和寫因?yàn)闆]有充分利用NVM的可字節(jié)尋址、低時(shí)延和高帶寬的優(yōu)勢， 在軟件上的性能損失過大.寫操作的開銷主要來自Compaction和日志更新，而讀操作主要是SSTable 查找和反序列化.減少這些軟件開銷對發(fā)揮NVM的硬件優(yōu)勢非常重要.由于NVM可以隨機(jī)訪問和 高帶寬低時(shí)延的特性，因此使用NVM作為L0層可以充分利用其硬件特性.對于寫，由于不像讀寫粒 度是較大的page傳統(tǒng)的可持久化存儲(chǔ)設(shè)備，NVM是可以隨機(jī)訪問的，所以可以在Compaction的時(shí) 候邊遍歷邊寫入NVM，也不用構(gòu)造page和序列化壓縮之類的工作.對于讀，也可以跳過對index block 和data block的查找以及換入換出cache的代價(jià)，直接對數(shù)據(jù)項(xiàng)進(jìn)行二分查找，并且也沒有反序列化 的過程.

3具體實(shí)現(xiàn)

為了解決合并帶來的寫時(shí)延問題，將LO層放在NVM上，希望利用NVM高效的讀寫速率和更高 的帶寬，加速Immutable MemTable寫入磁盤的過程.為了解決LO層文件之間無序、讀時(shí)延高的問題， 我們針對LO層的文件實(shí)現(xiàn)了學(xué)習(xí)索引，能夠更快地得到數(shù)據(jù)在LO層文件中的位置.架構(gòu)如圖5 所示，L0層存儲(chǔ)在NVM上，L1層到匕。層存儲(chǔ)在SSD上，針對L0層實(shí)現(xiàn)學(xué)習(xí)索引.

3.1基于非易失性內(nèi)存的L。層實(shí)現(xiàn)

數(shù)據(jù)在NVM上的組織格式稱為NVMTable，如圖6所示，根據(jù)存儲(chǔ)內(nèi)容的不同，NVMTable 被分為3種Block： Super Block，保存文件的兀信息;Meta Block，標(biāo)記某個(gè)key或者value在Entry Block中保存的是真正的數(shù)據(jù)還是指針;Entry Block，存儲(chǔ)鍵值數(shù)據(jù)對，或者指針對.

Super Block是每個(gè)NVMTable的第一·個(gè)Block，共有5個(gè)數(shù)據(jù)：Magic Number，判斷當(dāng)前文件格 式是否為NVMTable; File Number，文件號;File Type，文件類型;NB Entry，文件中鍵值對的數(shù)量; CRC64，文件校驗(yàn)碼.

每個(gè)Entry Block存儲(chǔ)8個(gè)鍵值對，一個(gè)key后面緊跟著它的value，可能是數(shù)據(jù)也可能是指向數(shù) 據(jù)的指針.Entry Block的數(shù)量#為ceil （鍵值對總數(shù)/8）.

每個(gè)Meta Block存儲(chǔ)1024個(gè)鍵值對是否內(nèi)聯(lián)的位圖信息.例如，對于鍵值對X，如果在Entry Block中保存的是真正的數(shù)據(jù)，則KeyInlineX和ValueInlineX為True;如果保存的是指向X的指針， 則 KeyInlineX 和 ValueInlineX 為 False. Meta Block 的總數(shù) #為 ceil （鍵值對總數(shù)/1 02（4）.

將數(shù)據(jù)寫入NVMTable發(fā)生在Minor Compaction的時(shí)候，通常會(huì)創(chuàng)建一個(gè)NVMTable文件和一 個(gè)Container文件，其中Container文件是從Redo-log修改而來.對于要寫入的鍵值對，首先判斷其key 和value的長度是否小于32 B，如果小于32 B，則為內(nèi)聯(lián)數(shù)據(jù)，直接將數(shù)據(jù)寫入Entry Block中;否則 將Container文件中對應(yīng)的數(shù)據(jù)的指針寫入Entry Block中.向Entry Block寫入數(shù)據(jù)時(shí)，同時(shí)在內(nèi)存 中創(chuàng)建Meta Block， —·邊確定Meta Block的位圖信息，一·邊向Entry Block寫入數(shù)據(jù).待NVMTable不 再有數(shù)據(jù)寫入，把內(nèi)存中的Meta Block給追加到文件末尾，最后更新文件頭部的Super Block，完成寫入.

為了減少數(shù)據(jù)的存儲(chǔ)空間，還對數(shù)據(jù)進(jìn)行了前綴壓縮.Container文件并不會(huì)為每一對鍵值對 都存儲(chǔ)完整的key值，而是存儲(chǔ)與上一個(gè)key不同的部分，避免了 key存儲(chǔ)重復(fù)內(nèi)容.每次用前綴壓 縮存儲(chǔ)若干個(gè)鍵值對后，設(shè)置檢查點(diǎn)，重新記錄一條完整的key，避免了讀取某個(gè)key恢復(fù)路徑過長的 問題.

3.2學(xué)習(xí)索引的實(shí)現(xiàn)

隨著Minor Compaction次數(shù)越來越多，L0層的文件數(shù)也越來越多，由于L0層文件內(nèi)部有序，文 件之間無序，系統(tǒng)讀操作需要查找的文件數(shù)也隨Minor Compaction的次數(shù)線性增加.所以需要實(shí)現(xiàn) 一種索引，來快速定位數(shù)據(jù)所在的文件及所在文件中的具體位置.

我們采用學(xué)習(xí)索引來定位一個(gè)key在LO層中的位置.首先對每一個(gè)NVMTable獨(dú)立學(xué)習(xí)一個(gè)索 引模型，創(chuàng)建key到數(shù)據(jù)位置的近似映射，然后從近似映射的位置開始與目標(biāo)key比大小，向前或者 向后線性查找到正確的位置.假設(shè)LO層一共有#個(gè)NVMTable，學(xué)習(xí)索引的平均誤差為R 256 B中 平均有夂個(gè)元素，Seek的復(fù)雜度為而傳統(tǒng)LSM-tree中的Seek復(fù)雜度為O（W x log2（M））， 如果要讓學(xué)習(xí)索引的查找路徑快于傳統(tǒng)的路徑，那么需要U/冗小于lOg2（M），所以模型的擬合盡量符 合真實(shí)分布變得非常重要.

學(xué)習(xí)索引的模型選擇的是Piecewise Geometric Model （PGM）索引125]，它是一種多層結(jié)構(gòu)，每一層 代表有不同錯(cuò)誤率下界的分段簡單線性回歸.圖7是一個(gè)PGM索引的樣例.第一層數(shù)據(jù)被劃分為 3個(gè)分區(qū)，每個(gè)部分由一個(gè)簡單的線性模型（/i，???????? 石）代表.通過構(gòu)造，每個(gè)線性模型在其相關(guān)的部分

以提前設(shè)置好的誤差值預(yù)測key的位置.第一層的分區(qū)邊界被視為它們自己的排序數(shù)據(jù)集，并且一個(gè) 有誤差值下界的分段函數(shù)由這個(gè)數(shù)據(jù)集計(jì)算得到.重復(fù)這個(gè)過程直到頂層的PGM足夠小.

一個(gè)分段線性回歸方程使用一組點(diǎn) p0， p1 ， · · ·， pn將數(shù)據(jù)分為n + 1個(gè)段.線性回歸分段函數(shù)被表示為：

每個(gè)在PGM索引里的回歸都是使用固定誤差.這種回歸能夠簡單地被當(dāng)作一個(gè)近似索引來使 用.PGM索引遞歸實(shí)施這些技巧，首先使用底層數(shù)據(jù)構(gòu)建分段回歸模型，然后使用第一個(gè)回歸的分割 點(diǎn)來構(gòu)建另外一個(gè)固定誤差的分段回歸.key查找是執(zhí)行查找每一個(gè)回歸模型，直到找到底層數(shù)據(jù) 為止.

PGM索引是從底層往上構(gòu)建的：首先選中一個(gè)誤差邊界，然后用一個(gè)最小的線性分段模型達(dá)到 這個(gè)誤差邊界.重復(fù)這個(gè)過程直到分段模型比閾值更小.

3.3漸進(jìn)式的 Compaction

LO層和Li層的key范圍的重疊是引起寫放大的主要原因.如果這些重復(fù)的key范圍能夠累積到 一定的數(shù)量再進(jìn)行Compaction，那么多次寫放大累積到一定程度會(huì)合并為一次寫放大，從而減少了寫 放大的總大小.漸進(jìn)的Compaction方法如圖8所示，即在LO層上的全局地址空間上維護(hù)許多個(gè)定長 的地址空間，并且使用內(nèi)存池的方式維護(hù)空閑空間，根據(jù)內(nèi)存表刷盤到非易失性內(nèi)存上的地址分布， 維護(hù)不同定長的地址空間的最近使用情況.如果出現(xiàn)非易失性內(nèi)存不夠用的情況，那么觸發(fā)內(nèi)存清理 的步驟，清理步驟的主要目標(biāo)是選擇一個(gè)或者多個(gè)定長地址空間內(nèi)的數(shù)據(jù)進(jìn)行淘汰，選擇的優(yōu)先級從 高到低，首先是沒有與Li層有交集的地址空間，其次是最近沒有寫入數(shù)據(jù)的地址空間，最后是數(shù)據(jù)量 多的地址空間.

如果某個(gè)地址空間的數(shù)據(jù)越來越多，會(huì)對讀越來越不友好，同時(shí)維護(hù)一個(gè)全局的每個(gè)地址空間的 最大數(shù)據(jù)個(gè)數(shù)，如果超過這個(gè)數(shù)，就觸發(fā)強(qiáng)制回收.

4實(shí)驗(yàn)評估

在LevelDB上，驗(yàn)證修改LO層的設(shè)計(jì)后其讀寫性能是否得到提升.

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

將修改后的LevelDB部署在單機(jī)環(huán)境中，使用的Linux內(nèi)核版本為x86_64 Linux 5.11.16-arch1- 1，硬件配置為：Intel Xeon Gold 6240R @ 96x 4 GHz 型號 48 核心 96 線程的 CPU，128 GB 的 DRAM， 512 GB 的 NVM，1 TB 的 NVMe 接口的 SSD.

4.2前綴壓縮的空間利用率

實(shí)驗(yàn)?zāi)康模簻y試使用NVM前后的空間利用率.

實(shí)驗(yàn)設(shè)置：將10000000條隨機(jī)的key、大小為256 B、value為空的數(shù)據(jù)分別插入到原本的SSTable 文件和Container文件中.

實(shí)驗(yàn)結(jié)果：在關(guān)閉壓縮后檢查點(diǎn)間隔相同的SSTable上所有數(shù)據(jù)所占空間為82.3 MB，在使用前 綴壓縮后為71.5 MB，壓縮比為1.15 ： 1，除了空間上的優(yōu)勢，在NVM上的格式少了很多meta信息， 比如index block， filter block等，降低了實(shí)現(xiàn)的難度.

4.3寫性能

實(shí)驗(yàn)?zāi)康模簻y試不同數(shù)據(jù)大小下，修改后的LevelDB的寫性能.

實(shí)驗(yàn)設(shè)置：key自增模擬金融業(yè)務(wù)下數(shù)據(jù)庫生產(chǎn)環(huán)境中主鍵自增的常見場景，分別測試4 kB， 8 kB， 16 kB這3種不同大小的value的寫時(shí)延，每種大小的數(shù)據(jù)分別生成10萬條測試數(shù)據(jù)，測試數(shù)據(jù)屬于 均勻分布.L0層的文件數(shù)量上限為10.

實(shí)驗(yàn)結(jié)果：如圖9所示，可以發(fā)現(xiàn)總體寫時(shí)延相對圖3沒有修改的情況都降低了 30%左右.由于 寫內(nèi)存表和寫日志的路徑基本沒有變化，但是內(nèi)存表持久化的過程由DRAM到SSD變?yōu)榱?DRAM 到NVM，所以減少的大部分時(shí)延都是來自合并.

4.4讀性能

實(shí)驗(yàn)?zāi)康模簻y試不同數(shù)據(jù)大小下，修改后的LevelDB的讀性能.

實(shí)驗(yàn)設(shè)置：key在數(shù)據(jù)范圍內(nèi)使用高斯分布，模擬金融業(yè)務(wù)下數(shù)據(jù)庫訪問中存在查詢熱點(diǎn)的情況， 分別測試4 kB， 8 kB， 16 kB這3種不同大小的value的讀時(shí)延，每種數(shù)據(jù)分別生成10萬條測試數(shù)據(jù)， 測試數(shù)據(jù)屬于均勻分布，之后生成在測試數(shù)據(jù)范圍內(nèi)均勻分布的10萬條查詢.

實(shí)驗(yàn)結(jié)果：如圖10所示，可以發(fā)現(xiàn)總體讀時(shí)延相對圖4沒有修改的情況都降低了 50%左右.將 LO層放在NVM上，縮短了 LO層的查詢路徑，由于CPU可以直接讀取NVM上的數(shù)據(jù)，所以省略了 圖4中的數(shù)據(jù)拷貝和反序列化，而圖4中的數(shù)據(jù)拷貝和反序列化流程時(shí)間占了整體查詢流程的一半， 同時(shí)查找學(xué)習(xí)索引也比傳統(tǒng)SSTable的二分查找更快.

4.5學(xué)習(xí)索引性能

實(shí)驗(yàn)?zāi)康模簻y試使用學(xué)習(xí)索引后，從單個(gè)SSTable文件中定位到某個(gè)key的時(shí)間.

實(shí)驗(yàn)設(shè)置：主鍵長度設(shè)置為16 bit，主鍵為自增，矩陣庫使用的是Eigen[26]，高精度庫使用的是 gmp[27]，精度設(shè)置為1000.主鍵的檢查點(diǎn)間隔為16，使用由檢查點(diǎn)作為訓(xùn)練集訓(xùn)練出來的模型來預(yù)測 輸入主鍵對應(yīng)的檢查點(diǎn)的位置.

實(shí)驗(yàn)結(jié)果：通過向量乘法得到預(yù)測檢查點(diǎn)編號的時(shí)間固定為5.7叫，理論上學(xué)習(xí)索引的查詢時(shí)延 不會(huì)隨著key的增加而增加，但是如表1所示，查詢的時(shí)間是增加的，可以認(rèn)為學(xué)習(xí)索引的預(yù)測隨著 精度不夠越來越不準(zhǔn)，造成在線性查找正確的檢查點(diǎn)上花費(fèi)了更多時(shí)間，在key數(shù)量較多的時(shí)候查詢 時(shí)間可能會(huì)有劣勢，所以理論上學(xué)習(xí)索引應(yīng)該是固定代價(jià)，但是實(shí)際工程上的實(shí)現(xiàn)因?yàn)槟Ｐ碗y選擇和 計(jì)算精度不夠難以在大規(guī)模數(shù)據(jù)上應(yīng)用.

5 結(jié)論

本文提出了一個(gè)針對高并發(fā)，高吞吐場景下的基于NVM的LSM-tree架構(gòu)，該結(jié)構(gòu)充分利用了 NVM可字節(jié)尋址、可持久化能力和大容量的優(yōu)點(diǎn).本文基于LevelDB實(shí)現(xiàn)了上述設(shè)計(jì)，通過實(shí)驗(yàn)證明，將NVM 引入LSM-tree架構(gòu)能有效地降低讀寫時(shí)延.目前的設(shè)計(jì)只針對離散型的SSTable進(jìn)行了測試，并未對 不同的SSTable格式做實(shí)驗(yàn).如何選擇SSTable的不同形態(tài)及其收益也是值得探討和關(guān)注的問題.

[參考文獻(xiàn)]

[1]EL-SHIMI A， KALACH R， KUMAR A， et al. Primary data deduplication—large scale study and system design [C] //2012 USENIX Annual Technical Conference. USENIX Association， 2012： 285-296.

[2]SHILANE P， HUANG M， WALLACE G， et al. WAN-optimized replication of backup datasets using stream-informed delta compression [J]. ACM Transactions on Storage， 2012， 8（4）： 1-26.

[3]GOOGLE INC. LevelDB [EB/OL]. [2019-06-20]. https：//github.com/google/leveldb.

[4]BHASKARAN M S， XU J， SWANSON S. Bankshot： Caching slow storage in fast non-volatile memory [J]. ACM SIGOPS Operating Systems Review， 2014， 48（1）： 73-81.

[5]STRUKOV D B， SNIDER G S， STEWART D R， et al. The missing memristor found [J]. Nature， 2008， 453（719（1）： 80-83.

[6]IZRAELEVITZ J， YANG J， ZHANG L， et al. Basic performance measurements of the intel optane DC persistent memory module

[EB/OL]. （2019-03-1（3） [2021-06-12]. https：//arxiv.org/pdf/190305714v1.pdf.

[7]DRISKILL-SMITH A. Latest advances and future prospects of STT-RAM [C]//Non-Volatile Memories Workshop. 2010： 11-13.

[8]CAULFIELD A M， DE A， COBURN J， et al. Moneta： A high-performance storage array architecture for next-generation， non-volatile memories [C] //2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture. IEEE， 2010： 385-395.

[9]LI J， PAVLO A， DONG S. NVMRocks： RocksDB on non-volatile memory systems [EB/OL]. [2021-06-20]. http：//istc-bigdata.org/ index.php/nvmrocks-rocksdb-on-non-volatie-memory-systems/.

[10]KANNAN S， BHAT N， GAVRILOVSKA A， et al. Redesigning LSMs for nonvolatile memory with NoveLSM [C]//2018 USENIX Annual Technical Conference. USENIX Association， 2018： 993-1005.

[11]WU M， ZWAENEPOEL W. eNVy： A non-volatile， main memory storage system [J]. ACM SIGOPS Operating Systems Review， 1994， 28（5）： 86-97.

[12]JAGADISH H V， NARAYAN P P S， SESHADRI S， et al. Incremental organization for data recording and warehousing [C]//Proceedings of the 23rd VLDB Conference. 1997： 16-25.

[13]RAJU P， KADEKODI R， CHIDAMBARAM V， et al. Pebblesdb： Building key-value stores using fragmented log-structured merge trees [C]//Proceedings of the 26th Symposium on Operating Systems Principles. 2017： 497-514.

[14]YAO T， WAN J， HUANG P， et al. A light-weight compaction tree to reduce I/O amplification toward efficient key-value stores [C]//Proceedings of the 33rd International Conference on Massive Storage System Technology （MSST）. 2017： 1-13.

[15]LU L， PILLAI T S， GOPALAKRISHNAN H， et al. Wisckey： Separating keys from values in SSD-conscious storage [J]. ACM Transactions on Storage， 2017， 13（1）： 1-28.

[16]WU X， XU Y， SHAO Z， et al. LSM-trie： An LSM-tree-based ultra-large key-value store for small data items [C]//2015 USENIX Annual Technical Conference. USENIX Association， 2015： 71-82.

[17]SHETTY P J， SPILLANE R P， MALPANI R R， et al. Building workload-independent storage with VT-trees [C]//11th USENIX Conference on File and Storage Technologies. USENIX Association， 2013： 17-30.

[18]BALMAU O， DIDONA D， GUERRAOUI R， et al. TRIAD： Creating synergies between memory， disk and log in log structured key- value stores [C]//2017 USENIX Annual Technical Conference. 2017： 363-375.

[19]YAO T， ZHANG Y， WAN J， et al. MatrixKV： Reducing write stalls and write amplification in LSM-tree based KV stores with matrix container in NVM [C]//2020 USENIX Annual Technical Conference. USENIX Association， 2020： 17-31.

[20]BALMAU O， DINU F， ZWAENEPOEL W， et al. SILK： Preventing latency spikes in log-structured merge key-value stores [C]//2019 USENIX Annual Technical Conference. USENIX Association， 2019： 753-766.

[21]SEARS R， RAMAKRISHNAN R. bLSM： A general purpose log structured merge tree [C] //Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. 2012： 217-228.

[22]LEPERS B， BALMAU O， GUPTA K， et al. KVell： The design and implementation of a fast persistent key-value store [C]//Proceedings of the 27th ACM Symposium on Operating Systems Principles. New York： Association for Computing Machery， 2019： 447-461.

[23]KAIYRAKHMET O， LEE S， NAM B， et al. SLM-DB： Single-level key-value store with persistent memory [C]//17th USENIX Conference on File and Storage Technologies. USENIX Association， 2019： 191-205.

[24]EISENMAN A， GARDNER D， ABDELRAHMAN I， et al. Reducing DRAM footprint with NVM in Facebook [C]//Proceedings of the Thirteenth EuroSys Conference. 2018： 1-13.

[25]FERRAGINA P， VINCIGUERRA G. The PGM-index： A fully-dynamic compressed learned index with provable worst-case bounds [J]. Proceedings of the VLDB Endowment， 2020， 13（10）： 1162-1175.

[26]EIGEN. [EB/OL]. [2019-06-20]. https：//eigen.tuxfamily.org/.

[27]GMP. [EB/OL]. [2019-06-20]. https：//gmplib.org/.

（責(zé)任編輯：林晶）