孫家博 蔡鵬

摘要：針對基于日志結(jié)構(gòu)合并樹（Log Structured Merge Tree， LSM-tree）的數(shù)據(jù)庫查詢性能較差的問題， 目前的研究工作主要集中在利用索引和緩存技術(shù)提升LSM-tree的查詢性能.本文主要從以下幾個方面對 LSM-tree的查詢優(yōu)化技術(shù)進(jìn)行了綜述.第一，介紹了 LSM-tree的基礎(chǔ)架構(gòu)，分析了影響查詢的因素.第二， 分析了當(dāng)前的LSM-tree查詢優(yōu)化技術(shù)，包括索引優(yōu)化技術(shù)和緩存優(yōu)化技術(shù).第三，分析了索引和緩存技術(shù) 是如何提升基于LSM-tree的數(shù)據(jù)庫查詢性能的，并總結(jié)了一些現(xiàn)有的研究工作.最后，總結(jié)并給出了未來 可能的研究方法.

關(guān)鍵詞：日志結(jié)構(gòu)合并樹;索引;緩存

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

Query optimization technology based on an LSM-tree

SUN Jiabo， CAI Peng

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

Abstract： Given challenges with poor query performance for databases using LSM-trees， the present research explores the use of index and cache technologies to improve the query performance of LSM-trees. First， the paper introduces the basic structure of an LSM-tree and analyzes the factors that affect query performance. Second， we analyze current query optimization technologies for LSM-trees， including index optimization technology and cache optimization technology. Third， we analyze how index and cache， in particular， can improve the query performance of databases using LSM-trees and summarize existing research in this area. Finally， we present possible avenues for further research.

Keywords： LSM-tree; index; cache

0引 言

隨著金融領(lǐng)域數(shù)字化和信息化程度的不斷發(fā)展，交易量不斷增長，同時交易場景也越來越復(fù)雜， 并且數(shù)據(jù)也迎來了爆發(fā)式的增長，而數(shù)據(jù)庫作為基礎(chǔ)數(shù)據(jù)存儲的基礎(chǔ)設(shè)施，對其產(chǎn)生了新的挑戰(zhàn).傳 統(tǒng)數(shù)據(jù)庫已經(jīng)無法很好地滿足數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)存儲需求，而KV存儲由于其簡單性、高吞吐量 和可伸縮性，已經(jīng)成為數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)存儲設(shè)施的重要組成部分，并且作為存儲引擎應(yīng)用許多 領(lǐng)域中.例如，文獻(xiàn)[1-4]中已經(jīng)成功應(yīng)用在媒體領(lǐng)域，還有應(yīng)用于電子商務(wù)領(lǐng)域的亞馬遜Dynamo151、 虛擬貨幣領(lǐng)域[6]、數(shù)據(jù)流和日志處理領(lǐng)域[7-10]、圖數(shù)據(jù)庫[11-12]、地理空間數(shù)據(jù)庫[13]、文件系統(tǒng)[14-15]以及硬 件存儲系統(tǒng)116-171等領(lǐng)域.

KV存儲主要的底層設(shè)計(jì)有哈希存儲、B樹（B+樹）[18]和LSM-tree[19]等.LSM-tree作為KV存儲結(jié)構(gòu)最流行的底層設(shè)計(jì)之一，已經(jīng)應(yīng)用在 BigTable[2Q]、LevelDB[21]、RocksDB[22]、Cassandra[23]、HBase[24]、 AsterixDB[25]和Dynamo[5]等KV數(shù)據(jù)庫中.通過利用LSM-tree將數(shù)據(jù)先寫入內(nèi)存，然后順序?qū)懭氪?盤的特性，這些系統(tǒng)獲得了非常優(yōu)秀的寫性能.然而由于LSM-tree的特殊結(jié)構(gòu)，這些基于LSM-tree 的KV數(shù)據(jù)庫的數(shù)據(jù)查詢性能往往不是很理想.LSM-tree是由多層結(jié)構(gòu)組成的，在執(zhí)行查詢操作時， 為了找到目標(biāo)數(shù)據(jù)，需要逐層遍歷進(jìn)行檢查，會產(chǎn)生較大的查詢開銷，并且這個過程會產(chǎn)生嚴(yán)重的讀 放大問題.因此，在盡可能保證寫性能的情況下優(yōu)化LSM-tree查詢性能是非常必要的.

目前，索引和緩存技術(shù)是數(shù)據(jù)庫系統(tǒng)中最常見的查詢優(yōu)化技術(shù).索引能夠快速定位到需要查找的 數(shù)據(jù)所在的位置，通過這種方式可以有效地減少磁盤I/O，以此來提升數(shù)據(jù)庫的查詢性能.除了利用 索引快速確定數(shù)據(jù)的位置，還可以利用緩存技術(shù)將磁盤中的經(jīng)常被訪問到的數(shù)據(jù)緩存到內(nèi)存中.查詢 這部分?jǐn)?shù)據(jù)時可以直接從內(nèi)存中讀取，而不需要訪問磁盤，能夠有效地提升數(shù)據(jù)庫的查詢性能.

本文將從以下幾個部分展開：第1章介紹LSM-tree的基礎(chǔ)結(jié)構(gòu)，分析其插入、合并、查詢過程以 及查詢過程所存在的問題;第2章介紹基于索引技術(shù)對LSM-tree的查詢優(yōu)化，以及總結(jié)現(xiàn)在已有的索 引優(yōu)化方案;第3章介紹LSM-tree基于緩存技術(shù)的查詢優(yōu)化，并總結(jié)目前已有的優(yōu)化方案及其優(yōu)缺點(diǎn); 第4章總結(jié)全文并給出LSM-tree查詢優(yōu)化未來可能的研究方向.

1LSM-tree基礎(chǔ)結(jié)構(gòu)與分析

傳統(tǒng)的同步更新存儲結(jié)構(gòu)，例如B+樹，在新的數(shù)據(jù)更新到來時會直接覆蓋舊值.這種結(jié)構(gòu)中存儲 的數(shù)據(jù)是最新版本的值，并且作為多路查找樹，在執(zhí)行查詢操作時能夠快速確定目標(biāo)數(shù)據(jù)的位置，有 利于查詢操作的執(zhí)行.然而，由于在插入和更新數(shù)據(jù)時會產(chǎn)生隨機(jī)讀寫操作，并且可能會造成B+樹結(jié) 構(gòu)的改變，這些原因?qū)е峦礁滤饕Y(jié)構(gòu)并不適合大規(guī)模數(shù)據(jù)寫入的場景.與之相對應(yīng)的是異步更 新存儲結(jié)構(gòu)，這種結(jié)構(gòu)中比較具有代表性的是LSM-tree.在更新數(shù)據(jù)時，不會直接覆蓋舊值，而是選 擇直接插入一條新數(shù)據(jù)，這種設(shè)計(jì)可以利用順序I/O來提升數(shù)據(jù)庫的寫性能.但是在這種情況下，同 一個數(shù)據(jù)可能存在多個版本，給數(shù)據(jù)庫的查詢性能帶來了不利影響.

隨著金融領(lǐng)域數(shù)字化和信息化程度的不斷發(fā)展，數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)產(chǎn)生的速度也越來越快， 對數(shù)據(jù)庫的數(shù)據(jù)寫入速度要求也越來越高.而傳統(tǒng)的同步更新存儲結(jié)構(gòu)針對大規(guī)模數(shù)據(jù)寫入場景的 性能表現(xiàn)并不理想，ONeil等[19]在1996年提出了 LSM-tree結(jié)構(gòu)作為數(shù)據(jù)庫的底層存儲結(jié)構(gòu)，這種存 儲結(jié)構(gòu)為數(shù)據(jù)庫帶來了非常優(yōu)秀的寫性能.LSM-tree作為異步更新存儲結(jié)構(gòu)的代表，主要包含內(nèi)存組 件和磁盤存儲組件兩個部分，如圖1所示.內(nèi)存組件在實(shí)現(xiàn)時被分為兩個部分：活躍的內(nèi)存表和不可 更改的內(nèi)存表，主要用來存儲新插入的數(shù)據(jù).磁盤存儲組件是多層存儲結(jié)構(gòu)，并且每層的數(shù)據(jù)文件都 是有序存儲.在目前比較流行的LSM-tree存儲引擎中，例如LeveDB和RocksDB，均采用了有序的文 件表（SSTs），將每層的文件分成許多有序的小文件.

LSM-tree是以插入一條新數(shù)據(jù)的方式來實(shí)現(xiàn)插入和更新操作.新插入的數(shù)據(jù)首先寫入活躍的內(nèi) 存表中，當(dāng)活躍內(nèi)存表的大小達(dá)到設(shè)定閾值時，會轉(zhuǎn)換為不可變的內(nèi)存表，并通過刷盤操作將數(shù)據(jù)順 序地寫入磁盤上的L。層.當(dāng)L。層的大小到達(dá)設(shè)定的閾值或滿足其他條件時，將會觸發(fā)合并操作，將 LO層的部分文件合并到Li層，同樣Li層也會在一定條件下合并到L2層，以此類推，直到數(shù)據(jù)合并到 最后一層.每層能夠容納的文件大小一般是以固定的倍數(shù)增長，默認(rèn)情況下，相鄰層之間大小比值是 10.在合并過程中，將會對數(shù)據(jù)進(jìn)行排序.由于LSM-tree采用的是數(shù)據(jù)追加的方式更新和刪除數(shù)據(jù)， 因此，在這個過程中還會刪除不需要的舊版本數(shù)據(jù)或者被標(biāo)記為刪除的數(shù)據(jù).

通過以上過程，LSM-tree能夠?qū)崿F(xiàn)非常優(yōu)秀的寫性能.由于LSM-tree采用異步更新的方式，相同 主鍵的數(shù)據(jù)也許會在不同層的文件中存在多個版本.為了保證能夠有效地查詢到最新數(shù)據(jù)，LSM-tree 一般采取以下措施：①當(dāng)數(shù)據(jù)寫入內(nèi)存中時，如果內(nèi)存中存在主鍵相同的數(shù)據(jù)，會覆蓋掉內(nèi)存中舊版 本的數(shù)據(jù)，只保留最新的數(shù)據(jù);②當(dāng)數(shù)據(jù)發(fā)生合并時，如果參與合并的文件中存在相同主鍵的數(shù)據(jù)，合 并過程中會清除舊版本的數(shù)據(jù)，只保留新版本的數(shù)據(jù).通過以上方式能夠?qū)崿F(xiàn)在逐層查詢數(shù)據(jù)時，查 找到的第一個目標(biāo)數(shù)據(jù)就是當(dāng)前最新版本的數(shù)據(jù).

數(shù)據(jù)查詢操作主要分為點(diǎn)查詢和范圍查詢兩種類型.在LSM-tree中，對于點(diǎn)查詢，首先會從內(nèi)存 中查找，如果內(nèi)存中存在目標(biāo)數(shù)據(jù)，則直接返回;如果內(nèi)存中不存在目標(biāo)數(shù)據(jù)，則在磁盤中逐層查找， 直到找到目標(biāo)數(shù)據(jù)或者判斷數(shù)據(jù)不存在.范圍查詢的目的是找到目標(biāo)范圍內(nèi)所有的最新數(shù)據(jù)，這個過 程會遍歷LSM-tree每層的文件，最后合并每層的查詢結(jié)果并返回目標(biāo)數(shù)據(jù).

LSM-tree由于其非常優(yōu)秀的寫性能已經(jīng)獲得了廣泛的實(shí)際應(yīng)用，如Amazon^ Chrome[21]、 Facebook126-271、LinkedIn和阿里巴巴|28-29].但是，由于在LSM-tree數(shù)據(jù)庫中同一·個數(shù)據(jù)可能存在多個 版本，并且由于分層結(jié)構(gòu)，在執(zhí)行查詢時需要逐層遍歷，特別是范圍查詢需要合并不同版本的記錄來 返回正確的查詢結(jié)果，這個過程極大地影響了 LSM-tree的查詢性能.針對LSM-tree查詢性能較差的 問題，許多研究人員提出了多種方法來優(yōu)化和提升LSM-tree的查詢性能.目前主流的LSM-tree查詢 優(yōu)化技術(shù)可以分為兩種：一種是基于索引的查詢優(yōu)化技術(shù)，另一種是基于緩存的查詢優(yōu)化技術(shù).

2基于LSM-tree的索引查詢優(yōu)化技術(shù)

數(shù)據(jù)庫執(zhí)行查詢操作時確定目標(biāo)數(shù)據(jù)的位置是非常重要的一步，同樣也會產(chǎn)生較大的性能開銷. 因此，快速地確定目標(biāo)數(shù)據(jù)所在的位置，可以減少查詢過程中對磁盤中數(shù)據(jù)的讀寫開銷，將能夠有效 地提升數(shù)據(jù)庫的查詢性能.通過對數(shù)據(jù)庫中的數(shù)據(jù)建立索引，能夠?qū)崿F(xiàn)不用掃描整個數(shù)據(jù)表就能快速 確定目標(biāo)數(shù)據(jù)的位置，因此，通過使用索引能夠有效地提升數(shù)據(jù)庫的查詢性能.目前，在LSM-tree中 具有代表性的查詢優(yōu)化索引是布隆過濾器（Bloom Filter）.

2.1布隆過濾器

布隆過濾器[301是Burton H. Bloom在1970年提出的一種概率數(shù)據(jù)結(jié)構(gòu)，其通過利用位數(shù)組表示 一個集合，能夠快速地判斷一個元素是否屬于這個集合.如圖2所示，布隆過濾器對插入的數(shù)據(jù)主鍵 使用多個哈希函數(shù)映射到位數(shù)組的多個位置，并將對應(yīng)位置的值置為1.在查詢數(shù)據(jù)時，布隆過濾器使 用哈希函數(shù)檢查位數(shù)組中對應(yīng)位置的值.如果值為1，則可能存在;如果不為1，則一定不存在.這種情 況下，可能會出現(xiàn)將不屬于該集合的元素誤認(rèn)為屬于該集合.例如圖2（c）， z雖然不存在，但布隆過濾 器會判斷z在集合中，即出現(xiàn)誤判.但是布隆過濾器不會把屬于該集合的元素誤認(rèn)為不屬于該集合.

布隆過濾器的誤判率是P=（l-e-表示哈希函數(shù)的數(shù)量，m表示位數(shù)組的大小，n表示集 合中元素的個數(shù)[31].利用布隆過濾器能夠快速判斷目標(biāo)數(shù)據(jù)是否在當(dāng)前文件中，但出現(xiàn)誤判時，會對 磁盤產(chǎn)生額外的訪問開銷，影響查詢性能.因此，降低誤判率是針對布隆過濾器優(yōu)化的一個重要方向.

當(dāng)= fln2時，布隆過濾器的誤判率最低，并且當(dāng)集合中元素個數(shù)n—定時，位數(shù)組的大小m越大，布 隆過濾器的誤判率P越低.但是位數(shù)組越大，占用的內(nèi)存空間越多，因此，如何在誤判率和存儲空間占 用之間取得平衡也是一個重要的優(yōu)化方向.

2.2索引優(yōu)化技術(shù)

為了提升LSM-tree的點(diǎn)查詢性能，許多基于LSM-tree的數(shù)據(jù)庫引擎[21-22]在內(nèi)存中使用布隆過濾 器對磁盤中的數(shù)據(jù)建立索引.當(dāng)查詢數(shù)據(jù)時，會在訪問某個數(shù)據(jù)文件之前，先通過布隆過濾器檢查目 標(biāo)數(shù)據(jù)是否存在對應(yīng)的數(shù)據(jù)文件中.如果布隆過濾器檢查不存在，則跳過這個數(shù)據(jù)文件，以此減少對 磁盤數(shù)據(jù)的訪問開銷;否則，訪問磁盤并讀取相應(yīng)的數(shù)據(jù)文件，然后通過查找算法在該數(shù)據(jù)文件中查 找目標(biāo)數(shù)據(jù)，如果找到目標(biāo)數(shù)據(jù)則返回，若沒找到，即出現(xiàn)誤判，則繼續(xù)查找其他數(shù)據(jù)文件.

在使用布隆過濾器查詢過程中出現(xiàn)誤判會增加額外的數(shù)據(jù)訪問開銷.文獻(xiàn)[32]中提到LSM- tree 最壞情況下 （即目標(biāo)數(shù)據(jù)在數(shù)據(jù)庫中不存在的情況） 的查詢開銷與 LSM-tree 所有層上的布隆過濾 器的誤判率之和成正比.目前，大多數(shù)基于LSM-tree的數(shù)據(jù)庫存儲引擎[21-23]中實(shí)現(xiàn)的布隆過濾器，其 磁盤中每個文件對應(yīng)的布隆過濾器的誤判率都是相同的.通過2.1節(jié)中的分析能夠知道，在數(shù)據(jù)數(shù)目 一定的情況下，想要降低布隆過濾器的誤判率，就需要分配更多的內(nèi)存空間給位數(shù)組.LSM-tree中的 層數(shù)越高，存儲的數(shù)據(jù)越多，特別是最后一層，存儲著大部分的數(shù)據(jù)，因此，對應(yīng)的布隆過濾器占用的 內(nèi)存空間也較大.如果同時降低每層對應(yīng)的布隆過濾器的誤判率，將會占用大量的內(nèi)存空間.

Monkey[32-33]是一個基于LSM-tree的KV存儲引擎，在給定內(nèi)存資源的條件下，能夠?qū)崿F(xiàn)更新 和查詢開銷的最佳平衡.為了減小LSM-tree所有層上的布隆過濾器誤判率之和，Monkey不再保持 LSM-tree中每層對應(yīng)的布隆過濾器誤判率都相同，而是設(shè)置每層的誤判率與其數(shù)據(jù)量成正比，并且一 般情況下上層的數(shù)據(jù)訪問頻率更高，通過給最上層的布隆過濾器分配更多的內(nèi)存空間降低對應(yīng)的誤 判率，在總內(nèi)存資源一定的情況下實(shí)現(xiàn)所有層的布隆過濾器誤判率之和最小.

一般情況下，查詢操作會頻繁訪問某些數(shù)據(jù)，或者隨著時間的改變，不同數(shù)據(jù)被訪問的頻次也會 發(fā)生改變.針對這個問題，Elasticbf[34]設(shè)計(jì)了一種可根據(jù)數(shù)據(jù)冷熱程度動態(tài)調(diào)整的布隆過濾器管理方 案.與傳統(tǒng)方案中每個文件構(gòu)造一個布隆過濾器并分配^個哈希函數(shù)不同，Elasticbf為磁盤上的每個 文件構(gòu)造了 ^個布隆過濾器，并為每個布隆過濾器分配fc/r個哈希函數(shù).同時，為了減少對內(nèi)存資源的 占用，Elasticbf將部分布隆過濾器存儲在磁盤上，并根據(jù)數(shù)據(jù)的冷熱程度動態(tài)調(diào)整磁盤和內(nèi)存中的布 隆過濾器.實(shí)驗(yàn)表明，在使用相同內(nèi)存的情況下，針對不同工作負(fù)載，Elasticbf能夠有效地減少布隆過 濾器誤判帶來的讀寫開銷.

布隆過濾器主要針對點(diǎn)查詢進(jìn)行優(yōu)化，對于范圍查詢優(yōu)化效果并不理想.LevelDB[21]和RocksDB[22] 使用前綴布隆過濾器優(yōu)化范圍查詢，但是只能處理有共同前綴主鍵的范圍查詢，范圍查詢性能并不理想.

文獻(xiàn)[35]提出了一*種新的數(shù)據(jù)結(jié)構(gòu) SuRF （Succinct Range Fliter），是基于 FST （Fast SuccinctTries）構(gòu)建的一種能夠支持點(diǎn)查詢和范圍查詢的數(shù)據(jù)結(jié)構(gòu).FST采用LOUDS-DS編碼字典樹，該字典 樹上層節(jié)點(diǎn)較少，由訪問頻繁的熱數(shù)據(jù)組成;下層包含大部分的節(jié)點(diǎn)，由冷數(shù)據(jù)組成.LOUDS-DS采 用層內(nèi)有序的布局，利用這個特點(diǎn)，LOUDS-DS能夠有效地支持范圍查詢.如圖3所示，F(xiàn)ull Tire能夠 準(zhǔn)確查找每一條數(shù)據(jù)，但是會占用大量的內(nèi)存資源.為了平衡過濾器的誤判率和所需的內(nèi)存資源， SuRF采用了剪枝字典樹，并提出了不同的優(yōu)化方案.SuRF-Base只存儲能夠識別每個主鍵的最小長 度的主鍵前綴，但是這種方法對于主鍵前綴相似度較高的場景會帶來較大的誤判率.例如，實(shí)驗(yàn)表明， 對于郵件地址作為主鍵的數(shù)據(jù)會帶來將近25%的誤判率.為了降低SuRF-Base的誤判率，SuRF-Hash 為每個主鍵增加了一些散列位，查詢時通過哈希函數(shù)映射到對應(yīng)位檢查目標(biāo)數(shù)據(jù)是否存在.實(shí)驗(yàn)表明， SuRF-Hash只需2?4個散列位就可將誤判率降低至1%.雖然SuRF-Hash能夠有效地減低誤判率， 但是并不能提高范圍查詢的性能.與SuRF-Hash不同的是，SuRF-Real在每個主鍵前綴的后面存儲 n個主鍵位增加主鍵的區(qū)分度，在降低誤判率的同時提升了點(diǎn)查詢和范圍查詢的性能，但是由于有些 主鍵的前綴區(qū)別較小，SuRF-Real的誤判率不如SuRF-Hash低.SuRF-Mixed結(jié)合了 SuRF-Hash和 SuRF-Real的優(yōu)點(diǎn)，能夠有效地支持點(diǎn)查詢和范圍查詢.

Rosetta[36]使用一組分層排列的布隆過濾器對每個主鍵的二進(jìn)制前綴建立索引，然后將每個范圍 查詢轉(zhuǎn)換為多次布隆過濾操作.這種方式能夠通過主鍵的二進(jìn)制前綴快速判斷目標(biāo)范圍是否存在，并 且可以降低LSM-tree中每層的布隆過濾器誤判率，能夠有效地減少查詢時對磁盤的訪問次數(shù).

為了提升LSM-tree的范圍查詢性能，與使用過濾器方法不同的是，REMIX[37]對全局?jǐn)?shù)據(jù)建立有 序的索引.在執(zhí)行范圍查詢操作時，REMIX主要有以下優(yōu)化：①通過二分查找快速定位目標(biāo)數(shù)據(jù); ②查詢數(shù)據(jù)時避免主鍵的比較;③跳過不在查詢路徑上的文件.通過這些優(yōu)化，REMIX能夠有效地提 升系統(tǒng)查詢性能.

2.3總結(jié)

布隆過濾器能夠有效地提升LSM-tree的查詢性能，但是查詢過程中產(chǎn)生的誤判會帶來額外的磁 盤讀寫開銷.Monkey通過給不同層的布隆過濾器分配不同的內(nèi)存資源，減小了布隆過濾器的誤判率 總和.但是Monkey針對每一層的布隆過濾器分配的資源是固定的，無法根據(jù)工作負(fù)載自動調(diào)整布隆 過濾器的布局.而Elasticbf能夠根據(jù)數(shù)據(jù)的冷熱程度來動態(tài)調(diào)整布隆過濾器的內(nèi)存資源分配，針對熱 點(diǎn)數(shù)據(jù)較集中的情況，Elasticbf能夠有效地提升查詢性能，但是對于熱點(diǎn)數(shù)據(jù)較分散的情況，Elasticbf 帶來的性能提升并不明顯.

Monkey和Elasticbf能夠有效地提升LSM-tree的點(diǎn)查詢性能，然而對于范圍查詢表現(xiàn)并不是十 分理想.SuRF能夠支持點(diǎn)查詢和范圍查詢，但是在插入新數(shù)據(jù)時需要重建整個數(shù)據(jù)結(jié)構(gòu)，會帶來較大 的性能開銷.Rosetta使用多個布隆過濾器，支持范圍查詢的同時也降低了誤判率，但是Rosetta不能 有效地支持長范圍查詢，并且多次過濾操作增加了查詢開銷.使用過濾器方法提升查詢性能時，降低 誤判率會帶來較大的資源占用和性能開銷.使用過濾器方法進(jìn)行范圍查詢時，需要探查每層的數(shù)據(jù)， 并且由于LSM-tree的多層結(jié)構(gòu)，數(shù)據(jù)可能存在多個版本，還需要對每層的查詢結(jié)果進(jìn)行合并，因此， 這些開銷是無法避免的.REMIX通過對全局?jǐn)?shù)據(jù)建立有序的索引，避免了過濾操作，能夠有效地減少 探查和合并查詢結(jié)果的開銷.但是在插入新數(shù)據(jù)時，與SuRF類似，REMIX也需要重建其索引結(jié)構(gòu)， 這同樣會帶來較大的性能開銷.

3基于LSM-tree的緩存查詢優(yōu)化技術(shù)

3.1緩存及其管理策略

在計(jì)算機(jī)系統(tǒng)中，由于CPU、內(nèi)存和磁盤之間存在著巨大的性能差異，當(dāng)CPU處理數(shù)據(jù)時需要 從內(nèi)存中加載數(shù)據(jù)，如果每次處理時都需要從內(nèi)存中加載數(shù)據(jù)，那么將造成CPU資源的浪費(fèi)，并會對 系統(tǒng)性能產(chǎn)生嚴(yán)重的影響.因此，在計(jì)算機(jī)系統(tǒng)中引入了數(shù)據(jù)緩存機(jī)制，通過將部分?jǐn)?shù)據(jù)緩存到 CPU的cache中，能夠有效地減少CPU從內(nèi)存中加載數(shù)據(jù)的等待時間.同理，在數(shù)據(jù)庫系統(tǒng)中，當(dāng)查 詢到來時需要從磁盤讀取相關(guān)的數(shù)據(jù)，由于磁盤I/O速度較慢，這個過程會消耗較多的時間，影響數(shù) 據(jù)庫的查詢性能.而通過緩存將磁盤上的部分?jǐn)?shù)據(jù)緩存到內(nèi)存中，在內(nèi)存中直接訪問這些數(shù)據(jù)將會有 效地提升數(shù)據(jù)訪問速度.

應(yīng)該將哪些數(shù)據(jù)緩存到內(nèi)存中并如何管理這些數(shù)據(jù)對數(shù)據(jù)庫系統(tǒng)來說也是非常重要的.目前數(shù) 據(jù)庫中常見的緩存管理策略有：最近最久未使用算法（Least Recently Used， LRU）[38]和最少使用算法 （Least Frequently Used， LFU）|39].

在實(shí)際的查詢過程中，最近被訪問過的數(shù)據(jù)，接下來被訪問的可能性也很高.因此，將最近被訪問 過的數(shù)據(jù)緩存到內(nèi)存中能夠有效地提升查詢性能.最近最久未使用算法（LRU）就是基于這種思想設(shè) 計(jì)的一種緩存替換策略，其主要過程是：

（1）訪問新數(shù)據(jù)時，將新數(shù)據(jù)插入到鏈表頭部;

（2）當(dāng)緩存中的數(shù)據(jù)被訪問時，將數(shù)據(jù)移到鏈表頭部位置;

（3）插入新數(shù)據(jù)時，如果緩存空間已占滿，將清除鏈表尾部的數(shù)據(jù).

最近最久未使用算法（LRU）只考慮最近被訪問的數(shù)據(jù)最有可能在將來被繼續(xù)訪問，但是最近訪 問的在將來不一定仍被繼續(xù)訪問.而一般情況下，被訪問最頻繁的數(shù)據(jù)在將來最可能被訪問，這也是 最少使用算法（LFU）的基本思想.最少使用算法的主要策略是：

（1）訪問新數(shù)據(jù)時，此時該數(shù)據(jù)被訪問1次，將該數(shù)據(jù)插入鏈表尾部;

（2）鏈表中的數(shù)據(jù)被訪問時，該數(shù)據(jù)訪問次數(shù)加1，并對鏈表重新排序;

（3）插入新數(shù)據(jù)時，如果緩存空間已占滿，清除鏈表尾部訪問頻率最低的數(shù)據(jù).

3.2緩存優(yōu)化技術(shù)

目前，在LSM-tree中為了減少查詢過程中對磁盤數(shù)據(jù)的讀取，大都使用了緩存技術(shù).表緩存中緩 存了磁盤文件的索引信息，加快了對磁盤上表的查找速度.塊緩存和鍵值對緩存通過在內(nèi)存中緩存磁 盤上的部分?jǐn)?shù)據(jù)，查詢時可以直接從內(nèi)存中讀取這些數(shù)據(jù)，能夠有效地提升數(shù)據(jù)庫的查詢性能.

雖然緩存優(yōu)化技術(shù)有效地提升了 LSM-tree的查詢性能，但是由于LSM-tree的多層結(jié)構(gòu)以及不同 層間的合并操作，當(dāng)內(nèi)存表中的數(shù)據(jù)寫入磁盤中或者磁盤中不同層間的文件產(chǎn)生合并操作時，會導(dǎo)致 內(nèi)存中緩存的數(shù)據(jù)無法使用，出現(xiàn)緩存失效問題.如圖4所示，由于L0層和L1層合并后產(chǎn)生了新的 數(shù)據(jù)塊，原來緩存中的數(shù)據(jù)將會失效.當(dāng)出現(xiàn)緩存失效時，只能去磁盤上查詢和讀取目標(biāo)數(shù)據(jù).這種情 況顯然會降低LSM-tree的查詢性能，甚至出現(xiàn)數(shù)據(jù)庫性能的劇烈抖動.因此，盡可能減小緩存失效問 題的影響對于優(yōu)化LSM-tree的查詢性能非常重要.

目前，很多研究人員針對利用緩存優(yōu)化技術(shù)提升LSM-tree的查詢性能提出了不同的方案.這些方 案根據(jù)其技術(shù)特點(diǎn)可以分為3種類型：優(yōu)化合并策略、利用機(jī)器學(xué)習(xí)方法預(yù)取數(shù)據(jù)和采用多種緩存 形式.

3.2.1優(yōu)化合并策略

LSM-tree緩存失效問題主要是由內(nèi)存中的數(shù)據(jù)刷到磁盤中和磁盤中不同層間的合并操作引起的， 因此，針對LSM-tree的合并策略進(jìn)行優(yōu)化來減小緩存失效是非常重要的一個研究方向.

文獻(xiàn)[40]提出了使用專門的合并服務(wù)器來處理數(shù)據(jù)合并操作.數(shù)據(jù)存儲服務(wù)器能夠更充分地利用 資源處理當(dāng)前的工作負(fù)載，并通過預(yù)熱算法替換數(shù)據(jù)存儲服務(wù)器緩存中的數(shù)據(jù)來減小緩存失效問題. 這種方法將合并后與緩存中數(shù)據(jù)塊有重疊的數(shù)據(jù)加載到緩存中，在新合并的數(shù)據(jù)塊中的數(shù)據(jù)仍會被 頻繁訪問的情況下，將會實(shí)現(xiàn)較好的查詢性能.

SM-tree[41]是LSM-tree的一種變體，與LSM-tree不同的是，SM-tree磁盤上的每層數(shù)據(jù)不再是有 序排列的.SM-tree通過降低磁盤上數(shù)據(jù)合并的頻率來減小緩存中的數(shù)據(jù)失效問題，但是這種方法存 在兩個問題：一是由于每層數(shù)據(jù)不是有序排列的，降低了范圍查詢的性能;二是對于頻繁更新的負(fù)載， 由于數(shù)據(jù)無序并且合并頻率低，會存在大量重復(fù)的數(shù)據(jù)，占用大量的存儲空間.

3.2.2機(jī)器學(xué)習(xí)預(yù)取數(shù)據(jù)

Leaper[42]利用機(jī)器學(xué)習(xí)方法預(yù)測未來可能被訪問到的數(shù)據(jù)并將其預(yù)取到緩存中.Leaper主要由 學(xué)習(xí)器、收集器和預(yù)取器組成.當(dāng)存儲引擎開始運(yùn)行后，Leaper中的收集器會不斷地更新統(tǒng)計(jì)信息; 學(xué)習(xí)器根據(jù)工作負(fù)載的變化周期性地訓(xùn)練預(yù)測模型，并將訓(xùn)練結(jié)果輸出給預(yù)取器;預(yù)取器根據(jù)學(xué)習(xí)器 和收集器生成的結(jié)果以及刷盤和合并操作等特征將未來可能繼續(xù)訪問的熱數(shù)據(jù)預(yù)取到緩存中.實(shí)驗(yàn) 表明，Leaper能夠有效地降低合并操作造成的緩存失效問題，并提高數(shù)據(jù)查詢性能.

3.2.3多種緩存形式

LSbM-tree[43]通過在磁盤的每一層建立合并緩存區(qū)存儲經(jīng)常被訪問的數(shù)據(jù)來避免合并時帶來的緩 存失效問題.在具體實(shí)現(xiàn)中，LSbM-tree將磁盤上合并緩存區(qū)的數(shù)據(jù)直接映射到位于內(nèi)存的緩存中，對 于頻繁訪問的數(shù)據(jù)可以直接在合并緩存區(qū)中查找，并且通過降低合并緩存區(qū)中數(shù)據(jù)的合并速率來降 低緩存中的數(shù)據(jù)失效問題.由于LSbM-tree的合并緩存中只存儲了部分頻繁訪問的數(shù)據(jù)，因此，不能 有效地提升長范圍查詢性能，并且磁盤中的合并緩存會增加額外的存儲空間開銷.

AC-Key[44]使用了 key-value、key-pointer 和 block 這 3 種緩存形式.key-value 緩存鍵值數(shù)據(jù)對， key-pointer緩存主鍵值和指向數(shù)據(jù)的指針，block緩存文件中的塊數(shù)據(jù).AC-key通過key-value和key- pointer 緩存加速點(diǎn)查詢， block 緩存加速范圍查詢， 并通過自適應(yīng)算法根據(jù)工作負(fù)載調(diào)整不同緩存的 大小和比例，在給定內(nèi)存大小的情況下，能夠有效地提升緩存命中率，并提升LSM-tree的查詢性能.

文獻(xiàn)[45]提出了使用不同粒度的緩存提升LSM-tree查詢性能的方法.在LSM-tree中，不同層的 數(shù)據(jù)合并頻率是不同的，一般情況下，層數(shù)越低數(shù)據(jù)合并頻率越低.為了降低緩存失效問題，粗粒度緩 存選擇緩存低層中頻繁訪問的數(shù)據(jù)來加快查詢速度;細(xì)粒度緩存通過緩存最近經(jīng)常被訪問的鍵值對， 并采用同步更新的方式降低緩存失效問題，能夠減少查詢時對磁盤的訪問，以此提高查詢速度.

3.3總結(jié)

目前，針對LSM-tree的緩存失效問題，工業(yè)界和學(xué)術(shù)界提出了很多優(yōu)化方法.表1是其中一些現(xiàn) 有的優(yōu)化方法以及對應(yīng)方法存在的不足之處.

4結(jié)論

目前，隨著數(shù)據(jù)規(guī)模的不斷增加，對數(shù)據(jù)庫寫入的速度要求越來越高，面對這些場景和需求， LSM-tree以其優(yōu)秀的寫入性能得到越來越多的應(yīng)用.但是，由于其特殊的分層結(jié)構(gòu)和內(nèi)部合并操作， 查詢性能并不理想，因此，很多研究人員針對LSM-tree的查詢提出了很多優(yōu)化方案.

本文主要介紹了 LSM-tree的基礎(chǔ)結(jié)構(gòu)和LSM-tree相關(guān)的主要查詢優(yōu)化技術(shù)：索引和緩存優(yōu)化技 術(shù)，調(diào)研總結(jié)了索引和緩存技術(shù)在LSM-tree查詢中存在的不足及目前針對這些問題的相關(guān)研究工作.

針對LSM-tree的查詢優(yōu)化，未來的研究方向可以從以下幾方面出發(fā).

（1）提高緩存命中率.緩存能夠有效提升查詢性能，但是由于在LSM-tree中數(shù)據(jù)從內(nèi)存寫入磁盤 和磁盤中不同層間的數(shù)據(jù)合并操作，造成緩存失效問題，降低了緩存命中率.可以考慮利用機(jī)器學(xué)習(xí) 方法根據(jù)工作負(fù)載和LSM-tree內(nèi)部的操作特點(diǎn)，預(yù)測未來可能訪問的數(shù)據(jù)并將其預(yù)取到緩存中，從 而降低緩存失效問題.

（2）LSM-tree范圍查詢優(yōu)化.目前，大多數(shù)查詢優(yōu)化方法主要是針對LSM-tree點(diǎn)查詢進(jìn)行優(yōu)化， 對范圍查詢的優(yōu)化較少，而LSM-tree由于多層結(jié)構(gòu)，不同層間存在重復(fù)的數(shù)據(jù)，對范圍查詢更不友好. 過濾器方法優(yōu)化范圍查詢無法避免對數(shù)據(jù)的探查與探查結(jié)果的合并開銷，并且不適合長范圍查詢場 景，REMIX對數(shù)據(jù)建立全局索引能夠避免這些開銷，但是插入新數(shù)據(jù)時索引重構(gòu)開銷較大.因此，將 兩者優(yōu)勢結(jié)合在一起是一個非常值得研究的方向.

（3）針對非主鍵查詢優(yōu)化.目前，針對非主鍵的查詢場景越來越多，而LSM-tree查詢優(yōu)化方法大 都是針對主鍵類型的查詢優(yōu)化.對非主鍵的查詢，特別是多個條件下的范圍查詢場景，如何進(jìn)行優(yōu)化 是一個重要的研究方向.

[參考文獻(xiàn)]

[1]ARMSTRONG T G， PONNEKANTI V， BORTHAKUR D， et al. Linkbench： A database benchmark based on the facebook social graph [C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013： 1185-1196.

[2]ATIKOGLU B， XU Y， FRACHTENBERG E， et al. Workload analysis of a large-scale key-value store [C]//Proceedings of the 12th

ACM Sigmetrics/Performance Joint International Conference on Measurement and Modeling of Computer Systems. 2012： 53-64.

[3 ] CAO Z， DONG S， VEMURI S， et al. Characterizing， modeling， and benchmarking rocksDB key-value workloads at facebook [C] //18th USENIX Conference on File and Storage Technologies （FAST 20）. 2020： 209-223.

[4 ] BU Y， BORKAR V， JIA J， et al. Pregelix： Big（ger） graph analytics on a dataflow engine [J]. Proceedings of the VLDB Endowment， 2015， 8（2）： 161-172.

[5]DECANDIA G， HASTORUN D， JAMPANI M， et al. Dynamo： Amazon's highly available key-value store [J]. ACM SIGOPS Operating Systems Review， 2007， 41（6）： 205-220.

[6]RAJU P， PONNAPALLI S， KAMINSKY E， et al. Mlsm： Making authenticated storage faster in ethereum [C]//10th USENIX Workshop on Hot Topics in Storage and File Systems （HotStorage 18）. 2018.

[7]CAO Z， CHEN S， LI F， et al. LogKV： Exploiting key-value stores for event log processing [C/OL]// 6th Biennial Conference on Innovative Data Systems Research （CIDR1（3）. 2013. http：//cidrdb.org/cidr2013/Papers/CIDR13_Paper46.pdf.

[8 ] CHEN G J， WIENER J L， IYER S， et al. Realtime data processing at facebook [C]//Proceedings of the 2016 International Conference on Management of Data. 2016： 1087-1098.

[9 ] KONDYLAKIS H， DAYAN N， ZOUMPATIANOS K， et al. Coconut palm： Static and streaming data series exploration now in your palm [C]//Proceedings of the 2019 International Conference on Management of Data. 2019： 1941-1944.

[10]KONDYLAKIS H， DAYAN N， ZOUMPATIANOS K， et al. Coconut： Sortable summarizations for scalable indexes over static and streaming data series [J]. The VLDB Journal， 2019， 28（6）： 847-869.

[11]DGRAPH. Badger Key-value DB in Go[EB/OL]. [2021-08-23]. https：//github.com/dgraphio/badger.

[12]KYROLA A， GUSSTRIN C. GraphChi-DB： Simple design for a scalable graph database system—on just a PC [EB/OL]. （2014-03-0（4） [202108-23]. https：//arxiv.org/pdf/1403.0701.pdf.

[13]ALSUBAIEE S， CAREY M J， LI C. LSM-based storage and indexing： An old idea with timely benefits [C]//Second International ACM Workshop on Managing and Mining Enriched Geo-spatial Data. 2015： 1-6.

[14]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 （FAST 1（3）. 2013： 17-30.

[15]JANNEN W， YUAN J， ZHAN Y， et al. BetrFS： A right-optimized write-optimized file system [C]//13th USENIX Conference on File and Storage Technologies （FAST 1（5）. 2015： 301-315.

[16]VINCON T， HARDOCK S， RIEGGER C， et al. Noftl-kv： Tackling write-amplification on kv-stores with native storage management [C]//Extending Database Technology. 2018： 457-460.

[17]DAYAN N， BONNET P， IDREOS S. GeckoFTL： Scalable flash translation techniques for very large flash devices [C]//Proceedings of the 2016 International Conference on Management of Data. 2016： 327-342.

[18]COMER D. Ubiquitous B-tree [J]. ACM Computing Surveys （CSUR）， 1979， 11（2）： 121-137.

[19]ONEIL P， CHENG E， GAWLICK D， et al. The log-structured merge-tree （LSM-tree） [J]. Acta Informatica， 1996， 33（4）： 351-385.

[20]CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： A distributed storage system for structured data [J]. ACM Transactions on Computer Systems， 2008， 26（2）： 1-26.

[21]Google. Leveldb[EB/OL]. [2021-08-23]. https：//leveldb.org/.

[22]Facebook. Rocksdb [EB/OL]. [2021-08-23]. https：//rocksdb.org/.

[23]Apache. Cassandra [EB/OL]. [2021-08-23]. http：//cassandra.apache.org/.

[24]HBase [EB/OL]. [2021-08-23]. https：//hbase.apache.org/

[25]ALSUBAIEE S， BEHM A， BORKAR V， et al. Storage management in AsterixDB [J]. Proceedings of the VLDB Endowment， 2014， 7（10）： 841-852.

[26]BEAVER D， KUMAR S， LI H C， et al. Finding a needle in haystack： Facebook's photo storage [J]. OSDI， 2010（10）： 1-8.

[27]MATSUNOBU Y， DONG S， LEE H. MyRocks： LSM-tree database storage engine serving Facebook's social graph [J]. Proceedings of the VLDB Endowment， 2020， 13（1（2）： 3217-3230.

[28]HUANG G， CHENG X， WANG J， et al. X-Engine： An optimized storage engine for large-scale E-commerce transaction processing [C]//Proceedings of the 2019 International Conference on Management of Data. 2019： 651-665.

[29]CAO W， LIU Z， WANG P， et al. PolarFS： An ultra-low latency and failure resilient distributed file system for shared storage cloud database [J]. Proceedings of the VLDB Endowment， 2018， 11（1（2）： 1849-1862.

[30]BLOOM B H. Space/time trade-offs in hash coding with allowable errors [J]. Communications of the ACM， 1970， 13（7）： 422-426.

[31]KIRSCH A， MITZENMACHER M. Less hashing， same performance： Building a better Bloom filter [J]. Random Structures & Algorithms， 2008， 33（2）： 187-218.

[32]DAYAN N， ATHANASSOULIS M， IDREOS S. Optimal bloom filters and adaptive merging for LSM-trees [J]. ACM Transactions on Database Systems， 2018， 43（4）： 1-48.

[33]DAYAN N， ATHANASSOULIS M， IDREOS S. Monkey： Optimal navigable key-value store[C]//Proceedings of the 2017 ACM International Conference on Management of Data. 2017： 79-94.

[34]LI Y， TIAN C， GUO F， et al. Elasticbf： Elastic bloom filter with hotness awareness for boosting read performance in large key-value stores [C]//2019 USENIX Annual Technical Conference （USENIX ATC'19）. 2019： 739-752.

[35]ZHANG H， LIM H， LEIS V， et al. Surf： Practical range query filtering with fast succinct tries [C]//Proceedings of the 2018 International Conference on Management of Data. 2018： 323-336.

[36]LUO S， CHATTERJEE S， KETSETSIDIS R， et al. Rosetta： A robust space-time optimized range filter for key-value stores [C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020： 2071-2086.

[37]ZHONG W， CHEN C， WU X， et al. {REMIX}： Efficient Range Query for LSM-trees [C]//19th USENIX Conference on File and Storage Technologies （FAST' 2（1）. 2021： 51-64.

[38]O'NEIL E J， O'NEIL P E， WEIKUM G. The LRU-K page replacement algorithm for database disk buffering [J]. Acm Sigmod Record， 1993， 22（2）： 297-306.

[39]TAILOR P， MORENA R D. A survey of database buffer cache management approaches [J] . International Journal of Advanced Research in Computer Science， 2017， 8（3）： 409-414.

[40]AHMAD M Y， KEMME B. Compaction management in distributed key-value datastores [J]. Proceedings of the VLDB Endowment， 2015， 8（8）： 850-861.

[41]JAGADISH H V， NARAYAN P P S， SESHADRI S， et al. Incremental organization for data recording and warehousing [J] . VLDB， 1997， 97： 16-25.

[42]YANG L， WU H， ZHANG T， et al. Leaper： A learned prefetcher for cache invalidation in LSM-tree based storage engines [J]. Proceedings of the VLDB Endowment， 2020， 13（1（2）： 1976-1989.

[43]TENG D， GUO L， LEE R， et al. LSbM-tree： Re-enabling buffer caching in data management for mixed reads and writes [C]//2017 IEEE 37th International Conference on Distributed Computing Systems （ICDCS）. 2017： 68-79.

[44]WU F， YANG M H， ZHANG B， et al. AC-Key： Adaptive caching for LSM-based key-value Stores [C]//2020 USENIX Annual Technical Conference （USENIX ATC' 20）. 2020： 603-615.

[45]LI X， XU G， FAN H， et al. Improving read performance of LSM-tree based KV stores via dual grained caches [C]//2019 IEEE 21st International Conference on High Performance Computing and Communications， IEEE 17th International Conference on Smart City， IEEE 5th International Conference on Data Science and Systems （HPCC/SmartCity/DSS）. 2019： 841-848.

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