基于更新熱點(diǎn)感知的LSM-Tree查詢優(yōu)化

林清音，陳志廣

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

0 引言

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

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

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

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

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

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

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

1.1 LSM-Tree的寫入和查詢

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

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

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

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

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

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

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

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

從圖2可以看出，對(duì)于基于固態(tài)硬盤的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ǔ)空間，加重了查詢操作的讀放大，最終導(dǎo)致讀性能下降。因此筆者認(rèn)為，研究如何減少讀寫混合型負(fù)載下更新操作引入的舊數(shù)據(jù)對(duì)于提高LSM-Tree的讀性能具有重要意義。

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

2 積極的壓縮

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

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

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

LSM-Tree無法徹底清除舊數(shù)據(jù)的主要原因在于無法獲知某個(gè)鍵的最新版本所在的SSTable。因此，筆者在內(nèi)存中引入了一個(gè)更新表，用于記錄最近插入的鍵所在的SSTable。具體來說，更新表中記錄的是一個(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)鍵即將被寫入磁盤中的SSTable（SSTnew）時(shí)，更新表會(huì)進(jìn)行記錄。若 K EY0此前在更新表中沒有對(duì)應(yīng)的條目，則插入一個(gè)新的 < KEY0, S STnew>條目，若KEY0此前已有記錄 < KEY0, S STold>，說明KEY0更新了，需要將此條記錄修改為，而 S STold中存儲(chǔ)的 K EY0已經(jīng)變?yōu)榕f數(shù)據(jù)。

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

2.2 壓縮觸發(fā)條件

在保留LSM-Tree原本的壓縮觸發(fā)條件的同時(shí)，筆者為L(zhǎng)SM-Tree加入了額外的壓縮觸發(fā)條件，目的是提前讓包含大量舊數(shù)據(jù)的SSTable觸發(fā)壓縮。具體地，當(dāng)積分表中某個(gè)條目的積分超過一定閾值（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 壓縮過程

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

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

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

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

2.4 加速查詢

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

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

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

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

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

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

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

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

本文所提方法涉及兩個(gè)參數(shù)：更新表大小與old_thres參數(shù)。為了確定合適的參數(shù)大小，首先使用不同的參數(shù)大小進(jìn)行了實(shí)驗(yàn)。圖5（a）展示了讀性能在不同更新表大小下的變化情況，采用的負(fù)載是YCSB 工作負(fù)載U9（負(fù)載配置見表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è)置越大的更新表越能夠加速更多的查詢請(qǐng)求，也能記錄更多的數(shù)據(jù)更新情況。雖然在實(shí)際的場(chǎng)景中總鍵值對(duì)數(shù)量往往非常大，但為了不產(chǎn)生過多的內(nèi)存開銷，更新表無須記錄所有鍵值對(duì)的更新情況。即使只設(shè)置16 MB大小的更新表也能夠加速非常多的查詢請(qǐng)求，在實(shí)際場(chǎng)景下可以權(quán)衡實(shí)際的需求和開銷，對(duì)更新表大小進(jìn)行設(shè)置。圖5（b）展示了讀性能和寫性能在不同old_thres參數(shù)下的變化情況，采用的負(fù)載是自定義的讀寫混合負(fù)載（負(fù)載配置見表2，update_times=1，N=5×107）。此時(shí)的更新表大小固定為64 MB，圖5（b）中的平均寫時(shí)延統(tǒng)計(jì)的是所有更新操作的寫時(shí)延。當(dāng)old_thres參數(shù)較小時(shí)，額外觸發(fā)的積極的壓縮較多，因此讀時(shí)延略有降低，寫時(shí)延則較高。當(dāng)old_thres參數(shù)為1 000時(shí)，寫性能達(dá)到最優(yōu)，與原來的LevelDB（即original）相差較小，表明額外觸發(fā)的壓縮減少了舊數(shù)據(jù)，因此減少了由空間不足所觸發(fā)的壓縮，二者達(dá)到平衡。當(dāng)old_thres參數(shù)繼續(xù)增加時(shí)，雖然額外觸發(fā)的積極的壓縮會(huì)減少，但由于存在較多舊數(shù)據(jù)，LevelDB會(huì)因?yàn)榭臻g不足而觸發(fā)壓縮，因此寫性能又會(huì)降低。

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

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

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

在實(shí)際應(yīng)用場(chǎng)景下，用戶對(duì)數(shù)據(jù)的插入、更新和查詢操作常常是混合的，例如一些移動(dòng)社交應(yīng)用可能會(huì)跟蹤用戶的定位，并向用戶發(fā)送特定的廣告。在這種場(chǎng)景下，移動(dòng)的用戶會(huì)頻繁地更新定位，而發(fā)送廣告的后臺(tái)則會(huì)頻繁地查詢用戶的定位[11]。因此，為了模擬真實(shí)應(yīng)用場(chǎng)景，本文設(shè)計(jì)了插入、更新和查詢操作混合的讀寫混合負(fù)載。讀寫混合負(fù)載配置見表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 讀寫混合負(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），與原來的LevelDB相比，優(yōu)化后的LevelDB（active）降低了45.3%的平均讀時(shí)延，降低了59.7%的99%讀尾時(shí)延。在此讀寫混合負(fù)載下，隨著update_times值增加，原來的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中最近寫入的數(shù)據(jù)能夠在較淺的層次停留更長(zhǎng)的時(shí)間，在此場(chǎng)景下能夠及時(shí)與更新的數(shù)據(jù)進(jìn)行壓縮。根據(jù)此負(fù)載插入、更新、讀寫混合的特點(diǎn)，最近被更新的數(shù)據(jù)也傾向于被讀取，因此LevelDB的讀性能隨update_times參數(shù)的增加變化不大。此外，在插入、更新、讀寫混合的情況下，盡管原來的LevelDB也能夠較為及時(shí)地進(jìn)行壓縮，但優(yōu)化后的LevelDB（active）有更新表加速查詢，因此讀性能更優(yōu)。

圖6 讀寫混合負(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ù)載類型。表1和圖2展示了基于固態(tài)硬盤的LevelDB隨著更新操作的不斷增加，其讀時(shí)延也不斷增加的情況。作為對(duì)比，筆者也測(cè)試了PebblesDB和優(yōu)化后的LevelDB（active）在更新操作不斷增加時(shí)的優(yōu)化效果，即采用表1所示負(fù)載類型進(jìn)行測(cè)試，其加載和執(zhí)行階段的數(shù)據(jù)量為10 GB，其請(qǐng)求分布為均勻分布。此外，筆者也選取了YCSB提供的4種經(jīng)典負(fù)載進(jìn)行測(cè)試，見表3。YCSB負(fù)載包括加載和執(zhí)行兩個(gè)階段，加載階段只包含插入操作，執(zhí)行階段則包括多種類型的操作，表3所示是4種經(jīng)典負(fù)載類型在執(zhí)行階段包含的不同操作類型的比例，其加載和執(zhí)行兩階段的數(shù)據(jù)量均為30 GB，其請(qǐng)求分布為均勻分布。

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

如圖7所示，隨著更新操作的不斷增加，本文提出的優(yōu)化方案與原來的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ù)載類型下讀時(shí)延優(yōu)化效果

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

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

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

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

4 結(jié)束語

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