林清音，陳志廣

中山大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510006

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)規(guī)模與日俱增，大數(shù)據(jù)時(shí)代已經(jīng)來(lái)臨。在大數(shù)據(jù)時(shí)代背景下，有海量數(shù)據(jù)需要存儲(chǔ)，如在電子商務(wù)、社交網(wǎng)絡(luò)、網(wǎng)頁(yè)搜索等場(chǎng)景，每天都需要存儲(chǔ)和讀取大量的數(shù)據(jù)。這就要求用一種高性能的數(shù)據(jù)索引結(jié)構(gòu)來(lái)組織海量數(shù)據(jù)，以便快速存儲(chǔ)和讀取。日志結(jié)構(gòu)合并樹(shù)（log-structured merge tree，LSM-Tree）[1]是一種被廣泛使用的索引結(jié)構(gòu)，它是一種分層、有序、面向持久化存儲(chǔ)的數(shù)據(jù)索引結(jié)構(gòu)，其核心思想是將數(shù)據(jù)緩存在內(nèi)存中再批量寫(xiě)入磁盤(pán)。現(xiàn)已有許多成熟的鍵值存儲(chǔ)系統(tǒng)基于LSMTree實(shí)現(xiàn)，如Google開(kāi)發(fā)的LevelDB[2]、Facebook開(kāi)發(fā)的RocksDB，以及eBay開(kāi)發(fā)的Cassandra[3]等。

LSM-Tree具有高寫(xiě)入性能，但其層次化的數(shù)據(jù)組織結(jié)構(gòu)使其讀性能較差。在各種應(yīng)用場(chǎng)景下，在關(guān)注數(shù)據(jù)的寫(xiě)入速度時(shí)也應(yīng)該關(guān)注數(shù)據(jù)的讀取速度。LSMTree的層次結(jié)構(gòu)一方面導(dǎo)致查詢(xún)過(guò)程產(chǎn)生讀放大，另一方面也帶來(lái)非常嚴(yán)重的寫(xiě)放大。由于查詢(xún)時(shí)需要逐層查找，在此過(guò)程中需要經(jīng)過(guò)多次磁盤(pán)訪問(wèn)才能最終查找到目標(biāo)數(shù)據(jù)，因此存在讀放大。LSMTree通過(guò)壓縮（compaction）操作來(lái)維護(hù)其層次結(jié)構(gòu)，需要不斷地讀出數(shù)據(jù)進(jìn)行重新排序和合并，之后再次寫(xiě)入磁盤(pán)，因此導(dǎo)致了寫(xiě)放大。寫(xiě)放大不僅占用了存儲(chǔ)介質(zhì)的寫(xiě)帶寬，影響了寫(xiě)性能，而且對(duì)寫(xiě)放大較為敏感的介質(zhì)，例如固態(tài)硬盤(pán)（solid state disk，SSD），使用壽命將被大大縮短。LSM-Tree采用異地更新的模式，即通過(guò)追加新版本數(shù)據(jù)來(lái)完成對(duì)數(shù)據(jù)的更新而不是直接修改數(shù)據(jù)，因此LSM-Tree中包含了較多的舊數(shù)據(jù)，這些舊數(shù)據(jù)不會(huì)產(chǎn)生讀命中，但加重了LSM-Tree的讀放大和寫(xiě)放大。因此，關(guān)注更新操作對(duì)LSM-Tree產(chǎn)生的影響對(duì)于提升讀性能和減小寫(xiě)放大具有重要意義。

現(xiàn)已有很多針對(duì)LSM-Tree的寫(xiě)放大問(wèn)題的研究。Yao T等人[4]提出了MatrixKV，通過(guò)減少LSM-Tree的總層次來(lái)減小寫(xiě)放大；Lu L Y等人[5]提出了WiscKey，采用鍵值分離的方法，使得每次壓縮時(shí)只需要對(duì)鍵進(jìn)行維護(hù)，從而減小了寫(xiě)放大；Raju P等人[6]提出了PebblesDB，設(shè)計(jì)了“守衛(wèi)”來(lái)維護(hù)每一層的部分有序，降低壓縮次數(shù)，從而減小寫(xiě)放大；Yao T等人[7]提出了LWC-Tree，通過(guò)對(duì)有序字符串表（sorted string table，SSTable）追加數(shù)據(jù)，只對(duì)其元數(shù)據(jù)進(jìn)行壓縮，大大減小了寫(xiě)放大。這些工作為了減小寫(xiě)放大在一定程度上犧牲了讀性能，鍵值分離使得需要二次查找才能讀取值，而破壞LSM-Tree原本的完全有序性，不利于數(shù)據(jù)的查找。另外，雖然針對(duì)LSM-Tree的讀性能展開(kāi)優(yōu)化的相關(guān)工作很多[8-10]，但是針對(duì)頻繁更新場(chǎng)景下的讀性能優(yōu)化的工作卻較少。Shin J等人[11]提出了LSMRUM-Tree，通過(guò)在內(nèi)存中添加更新備忘錄來(lái)加速R-Tree[12]的查詢(xún)，進(jìn)而加速整個(gè)LSM-Tree的查詢(xún)；Chandramouli B等人[13]提出了Faster，設(shè)計(jì)了一種跨內(nèi)存和存儲(chǔ)介質(zhì)的混合日志，能夠?qū)崿F(xiàn)高并發(fā)的數(shù)據(jù)讀取和數(shù)據(jù)就地更新。但LSM RUM-Tree沒(méi)有解決更新帶來(lái)的舊數(shù)據(jù)導(dǎo)致的寫(xiě)放大問(wèn)題，且該工作是針對(duì)LSM R-Tree[14]進(jìn)行優(yōu)化的；Faster為了實(shí)現(xiàn)數(shù)據(jù)在內(nèi)存中的就地更新，引入了過(guò)多的內(nèi)存開(kāi)銷(xiāo)。

本文通過(guò)實(shí)驗(yàn)證明更新操作會(huì)顯著降低LSM-Tree的讀性能，并進(jìn)一步證明了減少LSM-Tree中因?yàn)楦露氲呐f數(shù)據(jù)對(duì)于提升讀性能非常重要。因此，本文針對(duì)此問(wèn)題展開(kāi)優(yōu)化，提出了一種積極的壓縮方法，該方法有3個(gè)優(yōu)點(diǎn)：①能夠在壓縮過(guò)程中徹底清除舊數(shù)據(jù)，減小壓縮帶來(lái)的寫(xiě)放大；②能夠檢測(cè)存儲(chǔ)了大量舊數(shù)據(jù)的SSTable，并提前對(duì)其進(jìn)行舊數(shù)據(jù)清除；③加速查詢(xún)過(guò)程。

本文首先介紹LSM-Tree的基本結(jié)構(gòu)及其寫(xiě)入和查詢(xún)的執(zhí)行過(guò)程，并詳細(xì)闡述更新操作對(duì)其產(chǎn)生的影響；之后對(duì)本文為解決舊數(shù)據(jù)帶來(lái)的負(fù)面影響問(wèn)題而提出的積極的壓縮方法的設(shè)計(jì)進(jìn)行詳細(xì)介紹；最后介紹使用本文方法對(duì)鍵值存儲(chǔ)系統(tǒng)進(jìn)行改進(jìn)后的優(yōu)化效果。

1 日志結(jié)構(gòu)合并樹(shù)

LSM-Tree的主要特點(diǎn)是具有良好的寫(xiě)性能，但其讀性能較差?；镜腖SMTree由兩部分組成：一部分是內(nèi)存中的有序表（memory table，MemTable），另一部分是磁盤(pán)中的SSTable。LSM-Tree的核心思想是將寫(xiě)入的數(shù)據(jù)緩存在內(nèi)存中，隨后批量刷入磁盤(pán)，利用磁盤(pán)的批量順序?qū)懶阅苓h(yuǎn)高于多次隨機(jī)寫(xiě)性能的特點(diǎn)，達(dá)到極高的寫(xiě)入速度。如圖1所示，在寫(xiě)入數(shù)據(jù)時(shí)，數(shù)據(jù)首先寫(xiě)入位于內(nèi)存的MemTable中，當(dāng)MemTable寫(xiě)滿時(shí)，會(huì)轉(zhuǎn)化為不可變MemTable。不可變MemTable會(huì)被寫(xiě)入磁盤(pán)的L0層生成SSTable，這個(gè)過(guò)程被稱(chēng)為刷寫(xiě)（flush）。磁盤(pán)中的SSTable以層次結(jié)構(gòu)存儲(chǔ)，每一層的容量隨著層次的加深呈指數(shù)級(jí)增長(zhǎng)。為了使刷寫(xiě)快速完成，L0層中的不同SSTable是部分有序的，即單個(gè)SSTable內(nèi)部的數(shù)據(jù)有序，但不同的SSTable之間可能存在數(shù)據(jù)范圍的重疊。除L0層之外，其余層次中的SSTable都是完全有序的。

1.1 LSM-Tree的寫(xiě)入和查詢(xún)

LSM-Tree的數(shù)據(jù)寫(xiě)入是由上到下的，即當(dāng)某一層寫(xiě)滿之后，LSM-Tree才會(huì)將該層的SSTable壓入下一層。具體地，如圖1所示，每一層的容量有限，當(dāng)Li層的數(shù)據(jù)寫(xiě)滿后，LSM-Tree會(huì)選取Li層中的SSTable（記為Si）以及Li+1層中與Si存在數(shù)據(jù)范圍重疊的SSTable，將這些SSTable中的數(shù)據(jù)讀取到內(nèi)存中，進(jìn)行排序重新合并之后寫(xiě)入新的SSTable，統(tǒng)一保存到Li+1層中，此過(guò)程被稱(chēng)為壓縮。寫(xiě)入的數(shù)據(jù)隨著時(shí)間的推移會(huì)逐漸被壓入底層，而最近寫(xiě)入的數(shù)據(jù)則保存在較淺的層次。

圖1 LSM-Tree基本結(jié)構(gòu)

LSM-Tree的數(shù)據(jù)查詢(xún)也是由上到下的。首先在內(nèi)存里的MemTable和不可變MemTable中查找，然后再查找磁盤(pán)中的SSTable。如前面所說(shuō)，磁盤(pán)中的SSTable以層次結(jié)構(gòu)存儲(chǔ)，因此需要逐層對(duì)SSTable進(jìn)行查找。L0層中的SSTable是部分有序的，因此需要遍歷該層所有的SSTable，而這種查找邏輯也導(dǎo)致了L0層不能存放過(guò)多的SSTable，否則會(huì)大大降低查找速度。若在L0層的SSTable中沒(méi)有查找成功，則需要從上到下逐層查找其他層次的SSTable。其他層次的SSTable是完全有序的，因此只需要進(jìn)行二分查找即可。總體來(lái)說(shuō)，越底層的數(shù)據(jù)，其查詢(xún)速度越慢。

1.2 更新對(duì)LSM-Tree的影響

LSM-Tree的數(shù)據(jù)更新是異地更新。SSTable一旦寫(xiě)入磁盤(pán)后就不可更改，因此對(duì)數(shù)據(jù)的更新只能通過(guò)在新的SSTable中寫(xiě)入新版本數(shù)據(jù)來(lái)完成。而新版本的數(shù)據(jù)通常存在于較淺的層次，也會(huì)在查找過(guò)程中首先被找到，因此其正確性能夠得到保證，數(shù)據(jù)更新也與數(shù)據(jù)寫(xiě)入一樣具有極高的速度。然而，隨著數(shù)據(jù)不斷更新，保存在SSTable中的舊數(shù)據(jù)不再被訪問(wèn)，卻占用了存儲(chǔ)空間。隨著壓縮的不斷進(jìn)行，這些舊數(shù)據(jù)可能被不斷讀取和重新寫(xiě)入，帶來(lái)了額外的讀寫(xiě)放大。盡管壓縮過(guò)程可以清除一部分舊數(shù)據(jù)，但這種清除是不徹底的，因?yàn)長(zhǎng)SM-Tree不知道每個(gè)鍵的最新版本保存在哪個(gè)SSTable中，所以只能清除參與到某一次壓縮中的重復(fù)鍵，而被保留下來(lái)的鍵并不一定是最新的。

總而言之，LSM-Tree的壓縮過(guò)程帶來(lái)嚴(yán)重的寫(xiě)放大，在查詢(xún)時(shí)需要訪問(wèn)多個(gè)SSTable才能查詢(xún)成功，因此存在讀放大，而LSM-Tree中由更新帶來(lái)的舊數(shù)據(jù)加重了這些影響。

本文通過(guò)實(shí)驗(yàn)證明了更新操作確實(shí)降低了LSM-Tree的讀性能。本文選擇LevelDB進(jìn)行測(cè)試。LevelDB是非常經(jīng)典的基于LSM-Tree的鍵值存儲(chǔ)系統(tǒng)。本文對(duì)基于固態(tài)硬盤(pán)的LevelDB進(jìn)行了測(cè)試，并修改了雅虎云服務(wù)測(cè)試基準(zhǔn)（Yahoo!cloud serving benchmark，YCSB）[15]中工作負(fù)載類(lèi)型的讀寫(xiě)比，工作負(fù)載U1～U9中更新操作總數(shù)呈遞增趨勢(shì)。YCSB工作負(fù)載配置見(jiàn)表1。

表1 YCSB工作負(fù)載配置

從圖2可以看出，對(duì)于基于固態(tài)硬盤(pán)的LevelDB，當(dāng)更新操作逐漸增加時(shí)，平均讀時(shí)延和99%讀尾時(shí)延都呈現(xiàn)出了增加趨勢(shì)。在執(zhí)行工作負(fù)載U9時(shí)，LevelDB的平均讀時(shí)延和99%讀尾時(shí)延比執(zhí)行工作負(fù)載U1時(shí)分別增加了約100%和約309%。該實(shí)驗(yàn)結(jié)果證明了更新操作對(duì)LevelDB讀性能的影響，即更新操作引入大量舊數(shù)據(jù)，占用了存儲(chǔ)空間，加重了查詢(xún)操作的讀放大，最終導(dǎo)致讀性能下降。因此筆者認(rèn)為，研究如何減少讀寫(xiě)混合型負(fù)載下更新操作引入的舊數(shù)據(jù)對(duì)于提高LSM-Tree的讀性能具有重要意義。

圖2 基于固態(tài)硬盤(pán)的LevelDB讀時(shí)延變化

2 積極的壓縮

更新操作產(chǎn)生的舊數(shù)據(jù)加重了LSMTree 壓縮過(guò)程的寫(xiě)放大和查找過(guò)程的讀放大，從而降低了讀性能。針對(duì)這個(gè)問(wèn)題，筆者提出了一種積極的壓縮方法，能夠有效降低LSM-Tree的寫(xiě)放大，并有效提升LSM-Tree的讀性能。該方法的總體架構(gòu)如圖3所示，筆者為L(zhǎng)SM-Tree添加了位于內(nèi)存中的更新表和積分表，增加了壓縮的觸發(fā)條件，并優(yōu)化了壓縮過(guò)程，使其能夠徹底清除舊數(shù)據(jù)，同時(shí)優(yōu)化了LSM-Tree的查詢(xún)方法，使其能夠直接找到目標(biāo)鍵所在的SSTable。此外，筆者設(shè)計(jì)的積極的壓縮方法適用于所有非原地更新的基于LSM-Tree實(shí)現(xiàn)的數(shù)據(jù)存儲(chǔ)系統(tǒng)，因?yàn)樵摲椒ㄊ轻槍?duì)LSM-Tree的壓縮操作對(duì)清除舊數(shù)據(jù)具有延后性和不徹底性的問(wèn)題進(jìn)行優(yōu)化的。原地更新的LSM-Tree鍵值存儲(chǔ)系統(tǒng)（如Faster[13]）不適合使用該方法進(jìn)行優(yōu)化，而非原地更新且具有比較嚴(yán)重的寫(xiě)放大的鍵值存儲(chǔ)系統(tǒng)（如LevelDB、RocksDB等）則較為適用。

圖3 積極的壓縮方法總體架構(gòu)

2.1 位于內(nèi)存的更新表和積分表

LSM-Tree無(wú)法徹底清除舊數(shù)據(jù)的主要原因在于無(wú)法獲知某個(gè)鍵的最新版本所在的SSTable。因此，筆者在內(nèi)存中引入了一個(gè)更新表，用于記錄最近插入的鍵所在的SSTable。具體來(lái)說(shuō)，更新表中記錄的是一個(gè)二元組，即鍵到SSTable的映射。由此，可以快速獲得某個(gè)鍵的最新版本所在的位置。積分表則用于統(tǒng)計(jì)每個(gè)SSTable包含的舊數(shù)據(jù)數(shù)量。具體地，積分表中記錄的是一個(gè)二元組，即SSTable及其對(duì)應(yīng)的積分。SSTable中的舊數(shù)據(jù)越多，其積分也就越高。

為了使更新表能夠準(zhǔn)確記錄鍵的最新版本所在的SSTable，其工作機(jī)制如下。首先，當(dāng)鍵即將被寫(xiě)入磁盤(pán)中的SSTable（SSTnew）時(shí)，更新表會(huì)進(jìn)行記錄。若 K EY0此前在更新表中沒(méi)有對(duì)應(yīng)的條目，則插入一個(gè)新的 < KEY0, S STnew>條目，若KEY0此前已有記錄 < KEY0, S STold>，說(shuō)明KEY0更新了，需要將此條記錄修改為，而 S STold中存儲(chǔ)的 K EY0已經(jīng)變?yōu)榕f數(shù)據(jù)。

積分表對(duì)每個(gè)SSTable的積分更新是通過(guò)捕捉鍵的更新來(lái)完成的，這需要依賴(lài)于更新表。當(dāng)更新表的某個(gè)條目發(fā)生修改（而不是插入）時(shí)，例如由 < KEY0, SSTold>修改為 < KEY0, SSTnew>， S STold中的舊數(shù)據(jù)就產(chǎn)生了，其對(duì)應(yīng)的積分應(yīng)該加1。

更新表的大小是一個(gè)可變的參數(shù)。記錄所有插入LSM-Tree中的鍵值對(duì)的更新情況需要非常大的內(nèi)存開(kāi)銷(xiāo)。為了節(jié)省內(nèi)存開(kāi)銷(xiāo)，更新表只記錄最近的鍵值對(duì)更新情況，因此使用最近最少使用（least recently used, LRU）緩存機(jī)制來(lái)實(shí)現(xiàn)更新表。更新表越大，能夠記錄的歷史記錄越多，對(duì)舊數(shù)據(jù)的清除越有利；更新表越小，所產(chǎn)生的內(nèi)存開(kāi)銷(xiāo)也越小。積分表采用的數(shù)據(jù)結(jié)構(gòu)是哈希表，積分表的大小不設(shè)上限，因?yàn)槠溆涗浀闹皇荢STable的ID以及其對(duì)應(yīng)的積分，且積分表中的條目會(huì)隨著SSTable的刪除而刪除，不會(huì)處于無(wú)限增長(zhǎng)狀態(tài)，因此積分表產(chǎn)生的內(nèi)存開(kāi)銷(xiāo)非常小。目前筆者采用了單線程的LRU緩存機(jī)制來(lái)實(shí)現(xiàn)更新表，在高并發(fā)情況下，筆者將考慮采用多線程LRU緩存機(jī)制來(lái)提高更新表的并發(fā)訪問(wèn)性能。

2.2 壓縮觸發(fā)條件

在保留LSM-Tree原本的壓縮觸發(fā)條件的同時(shí)，筆者為L(zhǎng)SM-Tree加入了額外的壓縮觸發(fā)條件，目的是提前讓包含大量舊數(shù)據(jù)的SSTable觸發(fā)壓縮。具體地，當(dāng)積分表中某個(gè)條目的積分超過(guò)一定閾值（old_thres）時(shí)，表明該條目對(duì)應(yīng)的SSTable中包含大量的舊數(shù)據(jù)，可以直接對(duì)其觸發(fā)壓縮。原本需要等到該SSTable所在的層次容量不足時(shí)才能觸發(fā)壓縮，這樣導(dǎo)致了舊數(shù)據(jù)可能在該層次駐留較長(zhǎng)的時(shí)間，新的觸發(fā)策略則能夠提前清除這些舊數(shù)據(jù)。

2.3 壓縮過(guò)程

依據(jù)內(nèi)存中的更新表，能夠快速獲得某個(gè)鍵的最新版本所在的SSTable，因此在壓縮過(guò)程中能夠區(qū)分某個(gè)鍵是否為最新版本，并且訪問(wèn)內(nèi)存中的更新表帶來(lái)的開(kāi)銷(xiāo)極小。在壓縮過(guò)程中只需要加入相當(dāng)簡(jiǎn)單的判斷即可達(dá)到清除舊數(shù)據(jù)的目的。具體的壓縮過(guò)程如下。

如圖4所示，在遍歷參與壓縮的每個(gè)鍵時(shí)，對(duì)于鍵，訪問(wèn)更新表是否存在KEYi對(duì)應(yīng)的條目，若更新表中沒(méi)有，則此鍵最近沒(méi)有發(fā)生更新，將其視為最新版本并保留；若更新表中存在對(duì)應(yīng)條目＜KEYi,SSTi＞，則對(duì)比SSTi與當(dāng)前參與壓縮的SSTable是否一致，若一致，則KEYi是最新版本，繼續(xù)保留；若不一致，則此SSTable中的KEYi已是舊數(shù)據(jù)，可以清除，不再寫(xiě)入新的SSTable中。

圖4 積極的Compaction判別舊數(shù)據(jù)流程

由于在壓縮過(guò)程中，參與的SSTable會(huì)被刪除，保留下來(lái)的數(shù)據(jù)會(huì)被寫(xiě)入新的SSTable并保存到磁盤(pán)中，因此需要對(duì)更新表和積分表進(jìn)行相應(yīng)的維護(hù)。對(duì)于更新表來(lái)說(shuō)，其每個(gè)條目記錄的是鍵以及其最新版本所在的SSTable，若該SSTable參與了壓縮，則表明該鍵的最新版本所在的SSTable發(fā)生了變化，因此需要更新對(duì)應(yīng)的條目。例如，更新表中記錄了＜KEYi,SSTi＞，且SSTi參與了某次壓縮，KEYi被保存到SSTj中，則更新該條目為＜KEYi,SSTj＞。同時(shí)，某個(gè)SSTable參與了壓縮，說(shuō)明其中的舊數(shù)據(jù)已經(jīng)被徹底清除，無(wú)須在積分表中繼續(xù)記錄該SSTable的積分，因此可以直接從積分表中移除該SSTable對(duì)應(yīng)的條目。

2.4 加速查詢(xún)

本文的研究目的是清除舊數(shù)據(jù)。一方面減少囤積在LSM-Tree中的舊數(shù)據(jù)以弱化在查詢(xún)過(guò)程中產(chǎn)生的讀放大效應(yīng)；另一方面優(yōu)化查詢(xún)路徑，最終達(dá)到加速查詢(xún)的目的。

LSM-Tree在磁盤(pán)中查詢(xún)數(shù)據(jù)時(shí)，首先要遍歷L0層的所有SSTable，對(duì)于L0層以外的其他層次，先比較SSTable的鍵范圍，若所查詢(xún)的鍵落在某個(gè)SSTable的鍵范圍中，就需要讀取該SSTable進(jìn)行二分查找，然后依次逐層查找。這樣的查詢(xún)效率較低，需要經(jīng)過(guò)多次磁盤(pán)訪問(wèn)之后才能找到目標(biāo)鍵，造成讀放大效應(yīng)。而舊數(shù)據(jù)對(duì)讀過(guò)程的影響則體現(xiàn)在其占用了SSTable，若將囤積在LSM-Tree中的舊數(shù)據(jù)清除，一方面可減少占用的磁盤(pán)空間，在寫(xiě)入數(shù)據(jù)量相同的情況下占用的層次數(shù)更少，有效數(shù)據(jù)位于更淺的層次，查詢(xún)速度也就越快；另一方面可減少無(wú)效數(shù)據(jù)占用的SSTable數(shù)量，減少查詢(xún)過(guò)程中對(duì)SSTable的無(wú)效訪問(wèn)。

本文設(shè)計(jì)的更新表記錄了每個(gè)鍵的最新版本所在的SSTable，而查詢(xún)請(qǐng)求的目標(biāo)是找到該鍵的最新版本，因此，若查找時(shí)在內(nèi)存中的MemTable和不可變MemTable中都不命中，說(shuō)明該鍵保存在磁盤(pán)的SSTable中，可以通過(guò)查詢(xún)更新表，獲得該鍵的最新版本所在的SSTable，直接對(duì)其進(jìn)行數(shù)據(jù)讀取，而不需要經(jīng)歷原來(lái)的遍歷L0層以及對(duì)其他層次進(jìn)行二分查找的過(guò)程。

更新表的作用與緩存不同，它記錄的是最近更新的數(shù)據(jù)，而緩存記錄的是最近讀取的數(shù)據(jù)。在實(shí)際應(yīng)用場(chǎng)景中，讀操作與更新操作常常是混合的，且最近更新的鍵也很有可能馬上被讀取，因此更新表在讀性能方面也能實(shí)現(xiàn)有效提升。此外，緩存的目標(biāo)是存儲(chǔ)頻繁訪問(wèn)的數(shù)據(jù)，但是最近讀取的數(shù)據(jù)也會(huì)被寫(xiě)入緩存中，因此緩存容易受到范圍查詢(xún)的影響，使得非頻繁訪問(wèn)的數(shù)據(jù)代替了頻繁訪問(wèn)的數(shù)據(jù)，造成緩存命中率低下。另外，緩存無(wú)法與數(shù)據(jù)同步更新，一旦SSTable進(jìn)行了壓縮，緩存的數(shù)據(jù)就會(huì)失效，需要等待下一次從SSTable中讀取后才能再次生效。而我們通過(guò)更新表加速查找可以彌補(bǔ)緩存在這兩方面存在的問(wèn)題。

3 性能優(yōu)化效果對(duì)比

本文基于LevelDB實(shí)現(xiàn)了上述積極的壓縮方法，本節(jié)將展示該方法為L(zhǎng)evelDB帶來(lái)的優(yōu)化效果，包括在讀寫(xiě)混合負(fù)載基準(zhǔn)測(cè)試和YCSB[11]基準(zhǔn)測(cè)試下的讀性能提升效果以及寫(xiě)放大優(yōu)化效果。實(shí)驗(yàn)運(yùn)行在裝有CentOS 7.6、Linux 3.10內(nèi)核、英特爾Xeon 2.3 GHz處理器、16 GB內(nèi)存的機(jī)器上，對(duì)基于固態(tài)硬盤(pán)的LevelDB進(jìn)行了測(cè)試。首先，介紹本文所提方法涉及的參數(shù)對(duì)優(yōu)化效果的影響；其次，設(shè)計(jì)自定義的讀寫(xiě)混合負(fù)載，并將本文所提方法與原來(lái)的LevelDB和PebblesDB進(jìn)行對(duì)比；最后，使用YCSB基準(zhǔn)測(cè)試，將優(yōu)化后的LevelDB與原來(lái)的LevelDB和PebblesDB進(jìn)行對(duì)比，觀察優(yōu)化效果。本文通過(guò)平均讀時(shí)延和99%讀尾時(shí)延來(lái)反映讀性能，通過(guò)平均寫(xiě)時(shí)延來(lái)反映寫(xiě)性能，時(shí)延越低，則讀、寫(xiě)性能越高；通過(guò)寫(xiě)入硬盤(pán)的總數(shù)據(jù)量來(lái)反映寫(xiě)放大，寫(xiě)入的總數(shù)據(jù)量越大，寫(xiě)放大越嚴(yán)重。本文針對(duì)4個(gè)不同的指標(biāo)——平均讀時(shí)延、99%讀尾時(shí)延、寫(xiě)入數(shù)據(jù)量、平均寫(xiě)時(shí)延，用式（1）量化所提方案的優(yōu)化效果。其中，Tactive表示優(yōu)化后的LevelDB（active）的指標(biāo)數(shù)據(jù)，Torigin表示原來(lái)的LevelDB的指標(biāo)數(shù)據(jù)，P為優(yōu)化后的LevelDB（active）相比原來(lái)的LevelDB在某個(gè)指標(biāo)上減少的百分比，P值越大，優(yōu)化效果越好。

PebblesDB通過(guò)降低LSM-Tree中每一層的有序度，減少壓縮的次數(shù)以及每次壓縮涉及的SSTable數(shù)量，從而緩解寫(xiě)放大，代價(jià)是犧牲了部分讀性能，盡管PebblesDB也對(duì)讀操作進(jìn)行了優(yōu)化，以對(duì)每個(gè)SSTable創(chuàng)建一個(gè)布隆過(guò)濾器的行為代替對(duì)每個(gè)塊創(chuàng)建布隆過(guò)濾器的行為，避免對(duì)SSTable的無(wú)效讀取，但此優(yōu)化方案仍不可避免從磁盤(pán)中讀取布隆過(guò)濾器塊的行為，且增加了對(duì)SSTable進(jìn)行二分查找的時(shí)間。此外，PebblesDB也是基于LevelDB實(shí)現(xiàn)的鍵值存儲(chǔ)系統(tǒng)，因此本文選擇將PebblesDB作為對(duì)LevelDB進(jìn)行寫(xiě)放大優(yōu)化的另一種方案，與本文所提優(yōu)化方案進(jìn)行對(duì)比，證明本文所提優(yōu)化方案在降低寫(xiě)放大和提升讀性能兩者之間取得了較好的平衡。

3.1 更新表大小與old_thres參數(shù)

本文所提方法涉及兩個(gè)參數(shù)：更新表大小與old_thres參數(shù)。為了確定合適的參數(shù)大小，首先使用不同的參數(shù)大小進(jìn)行了實(shí)驗(yàn)。圖5（a）展示了讀性能在不同更新表大小下的變化情況，采用的負(fù)載是YCSB 工作負(fù)載U9（負(fù)載配置見(jiàn)表1），總鍵值對(duì)數(shù)量為10 MB，鍵大小為8 byte，值大小為1 024 byte，橫坐標(biāo)為參數(shù)變化情況，縱坐標(biāo)為讀時(shí)延。圖5（a）對(duì)應(yīng)的old_thres參數(shù)固定為10 000，不論是平均讀時(shí)延還是99%讀尾時(shí)延，隨著更新表的增大都呈下降趨勢(shì)，隨后保持穩(wěn)定。這是由于更新表緩存了最近更新的鍵值對(duì)，其大小越大，能夠緩存的鍵值對(duì)越多，得到的性能提升也就越多，而當(dāng)更新表為16 MB時(shí)已經(jīng)能夠滿足該負(fù)載的緩存需求，因此更新表繼續(xù)增大對(duì)性能影響不大。更新表的最優(yōu)大小與負(fù)載的總鍵值對(duì)數(shù)量相關(guān)，總鍵值對(duì)數(shù)量越多，設(shè)置越大的更新表越能夠加速更多的查詢(xún)請(qǐng)求，也能記錄更多的數(shù)據(jù)更新情況。雖然在實(shí)際的場(chǎng)景中總鍵值對(duì)數(shù)量往往非常大，但為了不產(chǎn)生過(guò)多的內(nèi)存開(kāi)銷(xiāo)，更新表無(wú)須記錄所有鍵值對(duì)的更新情況。即使只設(shè)置16 MB大小的更新表也能夠加速非常多的查詢(xún)請(qǐng)求，在實(shí)際場(chǎng)景下可以權(quán)衡實(shí)際的需求和開(kāi)銷(xiāo)，對(duì)更新表大小進(jìn)行設(shè)置。圖5（b）展示了讀性能和寫(xiě)性能在不同old_thres參數(shù)下的變化情況，采用的負(fù)載是自定義的讀寫(xiě)混合負(fù)載（負(fù)載配置見(jiàn)表2，update_times=1，N=5×107）。此時(shí)的更新表大小固定為64 MB，圖5（b）中的平均寫(xiě)時(shí)延統(tǒng)計(jì)的是所有更新操作的寫(xiě)時(shí)延。當(dāng)old_thres參數(shù)較小時(shí)，額外觸發(fā)的積極的壓縮較多，因此讀時(shí)延略有降低，寫(xiě)時(shí)延則較高。當(dāng)old_thres參數(shù)為1 000時(shí)，寫(xiě)性能達(dá)到最優(yōu)，與原來(lái)的LevelDB（即original）相差較小，表明額外觸發(fā)的壓縮減少了舊數(shù)據(jù)，因此減少了由空間不足所觸發(fā)的壓縮，二者達(dá)到平衡。當(dāng)old_thres參數(shù)繼續(xù)增加時(shí)，雖然額外觸發(fā)的積極的壓縮會(huì)減少，但由于存在較多舊數(shù)據(jù)，LevelDB會(huì)因?yàn)榭臻g不足而觸發(fā)壓縮，因此寫(xiě)性能又會(huì)降低。

圖5 不同參數(shù)對(duì)優(yōu)化效果的影響

雖然圖5展示的是更新表大小與old_thres參數(shù)各自的變化情況，但old_thres參數(shù)的作用也與更新表大小相關(guān)。若更新表過(guò)小，則記錄的更新操作也就越少，因此SSTable對(duì)應(yīng)的積分也會(huì)減少，此時(shí)積分大于old_thres參數(shù)的SSTable過(guò)少，也就難以及時(shí)清除舊數(shù)據(jù)。因此接下去的實(shí)驗(yàn)將更新表大小設(shè)置為64 MB，綜合讀寫(xiě)性能將old_thres參數(shù)設(shè)置為1 000。

3.2 混合負(fù)載基準(zhǔn)測(cè)試

在實(shí)際應(yīng)用場(chǎng)景下，用戶對(duì)數(shù)據(jù)的插入、更新和查詢(xún)操作常常是混合的，例如一些移動(dòng)社交應(yīng)用可能會(huì)跟蹤用戶的定位，并向用戶發(fā)送特定的廣告。在這種場(chǎng)景下，移動(dòng)的用戶會(huì)頻繁地更新定位，而發(fā)送廣告的后臺(tái)則會(huì)頻繁地查詢(xún)用戶的定位[11]。因此，為了模擬真實(shí)應(yīng)用場(chǎng)景，本文設(shè)計(jì)了插入、更新和查詢(xún)操作混合的讀寫(xiě)混合負(fù)載。讀寫(xiě)混合負(fù)載配置見(jiàn)表2，本基準(zhǔn)測(cè)試中鍵平均大小為8 byte，值平均大小為1 024 byte，此時(shí)插入請(qǐng)求數(shù)N=1×107，并設(shè)置了不同數(shù)量的更新操作。表2中的update_times參數(shù)表示對(duì)每個(gè)鍵的更新次數(shù)，該參數(shù)的值越高，則更新次數(shù)越多。

表2 讀寫(xiě)混合負(fù)載配置

圖6所示為使用本文提出的積極的壓縮方法進(jìn)行優(yōu)化的LevelDB取得的良好的讀性能優(yōu)化。在update_times參數(shù)變化的情況下，優(yōu)化后的LevelDB（圖6中的active）的讀性能均為最優(yōu)。當(dāng)update_times=4時(shí)取得的優(yōu)化效果最好，根據(jù)式（1），與原來(lái)的LevelDB相比，優(yōu)化后的LevelDB（active）降低了45.3%的平均讀時(shí)延，降低了59.7%的99%讀尾時(shí)延。在此讀寫(xiě)混合負(fù)載下，隨著update_times值增加，原來(lái)的LevelDB與優(yōu)化后的LevelDB（active）的讀性能變化幅度較小，PebblesDB則出現(xiàn)較為明顯的讀性能降低。這是由于觸發(fā)的壓縮策略不同。PebblesDB對(duì)每一層內(nèi)的SSTable進(jìn)行了分組，當(dāng)某個(gè)分組內(nèi)的SSTable數(shù)量達(dá)到組容量上限后就會(huì)進(jìn)行壓縮。而LevelDB則等到每一層存儲(chǔ)的SSTable達(dá)到層容量上限后才會(huì)觸發(fā)壓縮。因此隨著update_times值增加，PebblesDB執(zhí)行的壓縮會(huì)更頻繁，將更多的數(shù)據(jù)壓入更底層，而LevelDB中最近寫(xiě)入的數(shù)據(jù)能夠在較淺的層次停留更長(zhǎng)的時(shí)間，在此場(chǎng)景下能夠及時(shí)與更新的數(shù)據(jù)進(jìn)行壓縮。根據(jù)此負(fù)載插入、更新、讀寫(xiě)混合的特點(diǎn)，最近被更新的數(shù)據(jù)也傾向于被讀取，因此LevelDB的讀性能隨update_times參數(shù)的增加變化不大。此外，在插入、更新、讀寫(xiě)混合的情況下，盡管原來(lái)的LevelDB也能夠較為及時(shí)地進(jìn)行壓縮，但優(yōu)化后的LevelDB（active）有更新表加速查詢(xún)，因此讀性能更優(yōu)。

圖6 讀寫(xiě)混合負(fù)載下的讀性能優(yōu)化效果

3.3 YCSB基準(zhǔn)測(cè)試

YCSB[15]基準(zhǔn)測(cè)試是工業(yè)界用于評(píng)測(cè)鍵值存儲(chǔ)系統(tǒng)的標(biāo)準(zhǔn)，它提供了多種負(fù)載類(lèi)型。表1和圖2展示了基于固態(tài)硬盤(pán)的LevelDB隨著更新操作的不斷增加，其讀時(shí)延也不斷增加的情況。作為對(duì)比，筆者也測(cè)試了PebblesDB和優(yōu)化后的LevelDB（active）在更新操作不斷增加時(shí)的優(yōu)化效果，即采用表1所示負(fù)載類(lèi)型進(jìn)行測(cè)試，其加載和執(zhí)行階段的數(shù)據(jù)量為10 GB，其請(qǐng)求分布為均勻分布。此外，筆者也選取了YCSB提供的4種經(jīng)典負(fù)載進(jìn)行測(cè)試，見(jiàn)表3。YCSB負(fù)載包括加載和執(zhí)行兩個(gè)階段，加載階段只包含插入操作，執(zhí)行階段則包括多種類(lèi)型的操作，表3所示是4種經(jīng)典負(fù)載類(lèi)型在執(zhí)行階段包含的不同操作類(lèi)型的比例，其加載和執(zhí)行兩階段的數(shù)據(jù)量均為30 GB，其請(qǐng)求分布為均勻分布。

表3 4種YCSB經(jīng)典負(fù)載配置

如圖7所示，隨著更新操作的不斷增加，本文提出的優(yōu)化方案與原來(lái)的LevelDB相比能夠降低65.2%的平均讀時(shí)延（工作負(fù)載U5）以及69.4%的99%讀尾時(shí)延（工作負(fù)載U5）。而PebblesDB的讀性能則比LevelDB差，且隨著更新操作的增加，其讀時(shí)延增加的趨勢(shì)較為明顯，而本文提出的優(yōu)化方案讀時(shí)延較為穩(wěn)定，證明本文提出的優(yōu)化方案受更新操作的影響較小。

圖7 表1所示負(fù)載類(lèi)型下讀時(shí)延優(yōu)化效果

如圖8（a）所示，對(duì)于表3中的YCSB經(jīng)典負(fù)載類(lèi)型，優(yōu)化后的LevelDB（active）與原來(lái)的LevelDB相比讀性能均有所提升，能夠降低33.9%的平均讀時(shí)延（工作負(fù)載a）。而隨著更新比例的減小，優(yōu)化效果逐漸減弱。與PebblesDB相比，本文提出的優(yōu)化方案在工作負(fù)載c測(cè)試下的讀性能優(yōu)化效果略顯不足，這是由于工作負(fù)載c沒(méi)有更新操作，因此本文提出的優(yōu)化方案效果微弱，而PebblesDB則依賴(lài)于SSTable級(jí)別的布隆過(guò)濾器得到較好的讀性能。如圖8（b）所示，優(yōu)化后的LevelDB（active）與原來(lái)的LevelDB相比能夠降低71.4%的寫(xiě)放大（工作負(fù)載b），而PebblesDB則在各種負(fù)載類(lèi)型下都維持了最低的寫(xiě)放大。盡管本文對(duì)寫(xiě)放大的優(yōu)化強(qiáng)度不如PebblesDB，但讀性能的提升優(yōu)于PebblesDB。工作負(fù)載b的更新操作比例非常低，但工作負(fù)載b負(fù)載測(cè)試的寫(xiě)放大優(yōu)化效果卻優(yōu)于工作負(fù)載a，這是由于LevelDB內(nèi)部設(shè)置了額外的壓縮策略，即當(dāng)對(duì)某個(gè)SSTable的無(wú)效訪問(wèn)次數(shù)超過(guò)一定閾值時(shí)會(huì)觸發(fā)壓縮，這也是LevelDB加大清除舊數(shù)據(jù)力度的方法之一。采用了積極的壓縮之后，更多舊數(shù)據(jù)會(huì)被及時(shí)清除，且更新表具有直接找到目標(biāo)SSTable的功能，因此對(duì)SSTable的無(wú)效訪問(wèn)次數(shù)會(huì)減少。

圖8 表3所示負(fù)載類(lèi)型下的平均讀時(shí)延和寫(xiě)放大優(yōu)化效果

積極的壓縮方法在壓縮過(guò)程中會(huì)額外訪問(wèn)更新表判定舊數(shù)據(jù)，且該方法還設(shè)置了主動(dòng)觸發(fā)壓縮的策略，可能會(huì)導(dǎo)致壓縮次數(shù)過(guò)多，占用過(guò)多帶寬和CPU資源。為了探究積極的壓縮所帶來(lái)的額外開(kāi)銷(xiāo)，筆者分析了表3所示負(fù)載類(lèi)型測(cè)試下執(zhí)行階段的平均寫(xiě)時(shí)延（更新或插入操作）。在工作負(fù)載a測(cè)試下，優(yōu)化后的LevelDB（active）與原來(lái)的LevelDB相比有9.3%的寫(xiě)性能下降，說(shuō)明總壓縮次數(shù)以及每次執(zhí)行壓縮的時(shí)間能夠達(dá)到較為合理的平衡。在讀密集型負(fù)載（如工作負(fù)載b和工作負(fù)載d）測(cè)試下，其平均寫(xiě)時(shí)延與LevelDB和PebblesDB相比反而有所降低，這是由于省去了由無(wú)效訪問(wèn)次數(shù)觸發(fā)的壓縮操作，由讀操作引發(fā)的壓縮減少了，進(jìn)而減少了占用的帶寬，因此提升了寫(xiě)入速度。

圖9 表3所示負(fù)載類(lèi)型下的平均寫(xiě)時(shí)延對(duì)比

4 結(jié)束語(yǔ)

LSM-Tree是一種廣泛使用的大數(shù)據(jù)索引結(jié)構(gòu)，在實(shí)現(xiàn)極高寫(xiě)入性能的同時(shí)，給數(shù)據(jù)的更新帶來(lái)了大量的舊數(shù)據(jù)，降低了其讀性能。本文提出了一種積極的壓縮方法，能夠提前觸發(fā)壓縮，并在壓縮過(guò)程中徹底清除舊數(shù)據(jù)，同時(shí)優(yōu)化了LSM-Tree的查詢(xún)邏輯，減少了舊數(shù)據(jù)帶來(lái)的負(fù)面影響，提升了讀性能。實(shí)驗(yàn)表明，本文提出的優(yōu)化方案能夠降低LevelDB 65.2%的平均讀時(shí)延、69.4%的99%讀尾時(shí)延以及71.4%的寫(xiě)放大。