1、引言

對于一個數(shù)據(jù)庫的性能來說，其數(shù)據(jù)的組織方式至關重要怪嫌。眾所周知，數(shù)據(jù)庫的數(shù)據(jù)大多存儲在磁盤上胃榕，而磁盤的訪問相對內存的訪問來說是一項很耗時的操作，對比如下瞄摊。因此勤晚，提高數(shù)據(jù)庫數(shù)據(jù)的查找速度的關鍵點之一便是盡量減少磁盤的訪問次數(shù)枉层。

為了加速數(shù)據(jù)庫數(shù)據(jù)的訪問，大多傳統(tǒng)的關系型數(shù)據(jù)庫都會使用特殊的數(shù)據(jù)結構來幫助查找數(shù)據(jù)赐写，這種數(shù)據(jù)結構叫作索引( Index)鸟蜡。對于傳統(tǒng)的關系型數(shù)據(jù)庫，考慮到經(jīng)常需要范圍查找某一批數(shù)據(jù)挺邀，因此其索引一般不使用 Hash算法揉忘，而使用樹( Tree)結構。

1.1 B+樹

在傳統(tǒng)的關系型數(shù)據(jù)庫里端铛， B+樹及其衍生樹是被用得比較多的索引樹泣矛。

1.jpeg

B+樹的非葉子節(jié)點只存放鍵值，不存放數(shù)值禾蚕，而由葉子節(jié)點存放數(shù)值您朽。這樣會使樹節(jié)點的度比較大，而樹的高度就比較低换淆，從而有利于提高查詢效率哗总。葉子節(jié)點存放數(shù)值，并按照值大小順序排序倍试，且?guī)е赶蛳噜徆?jié)點的指針讯屈，以便高效地進行區(qū)間數(shù)據(jù)查詢；并且所有葉子節(jié)點與根節(jié)點的距離相同县习，因此任何查詢的效率都很相似涮母。

與二叉樹不同， B+樹的數(shù)據(jù)更新操作不從根節(jié)點開始躁愿，而從葉子節(jié)點開始叛本，并且在更新過程中樹能以比較小的代價實現(xiàn)自平衡。

正是由于 B+樹的上述優(yōu)點彤钟，它成了傳統(tǒng)關系型數(shù)據(jù)庫的寵兒来候。當然，它也并非無懈可擊样勃，它的主要缺點在于隨著數(shù)據(jù)插入的不斷發(fā)生，葉子節(jié)點會慢慢分裂——這可能會導致邏輯上原本連續(xù)的數(shù)據(jù)實際上存放在不同的物理磁盤塊位置上性芬，在做范圍查詢的時候會導致較高的磁盤 IO峡眶，以致嚴重影響到性能。

1.2 LSM樹

眾所周知植锉，數(shù)據(jù)庫的數(shù)據(jù)大多存儲在磁盤上辫樱，而無論是傳統(tǒng)的機械硬盤( HardDiskDrive, HDD)還是固態(tài)硬盤( Solid State Drive, SSD)，對磁盤數(shù)據(jù)的順序讀寫速度都遠高于隨機讀寫俊庇。

然而狮暑，基于 B+樹的索引結構是違背上述磁盤基本特點的——它會需要較多的磁盤隨機讀寫鸡挠。于是， 1992年搬男，名為日志結構( Log-Structured)的新型索引結構方法便應運而生拣展。日志結構方法的主要思想是將磁盤看作一個大的日志，每次都將新的數(shù)據(jù)及其索引結構添加到日志的最末端缔逛，以實現(xiàn)對磁盤的順序操作备埃，從而提高索引性能。不過褐奴，日志結構方法也有明顯的缺點按脚，隨機讀取數(shù)據(jù)時效率很低。

1996年敦冬，一篇名為 The Log-Structured Merge-tree(LSM-tree)的論文創(chuàng)造性地提出了日志結構合并樹( Log-Structured Merge-Tree)的概念辅搬，該方法既吸收了日志結構方法的優(yōu)點，又通過將數(shù)據(jù)文件預排序克服了日志結構方法隨機讀性能較差的問題脖旱。盡管當時 LSM-tree新穎且優(yōu)勢鮮明堪遂，但它真正聲名鵲起卻是在 10年之后的 2006年，那年谷歌的一篇使用了 LSM-tree技術的論文 Bigtable: A Distributed Storage System for Structured Data橫空出世夯缺，在分布式數(shù)據(jù)處理領域掀起了一陣旋風蚤氏，隨后兩個聲名赫赫的大數(shù)據(jù)開源組件( 2007年的 HBase與 2008年的 Cassandra，目前兩者同為 Apache頂級項目)直接在其思想基礎上破繭而出踊兜，徹底改變了大數(shù)據(jù)基礎組件的格局竿滨，同時也極大地推廣了 LSM-tree技術。

事實上捏境，LSM樹并不像B+樹于游、紅黑樹一樣是一顆嚴格的樹狀數(shù)據(jù)結構，它其實是一種存儲結構垫言，目前HBase贰剥，LevelDB，RocksDB這些NoSQL存儲都是采用的LSM樹筷频。

2.png

如上圖所示蚌成，LSM樹有以下三個重要組成部分：

MemTable：MemTable是在內存中的數(shù)據(jù)結構，用于保存最近更新的數(shù)據(jù)凛捏，會按照Key有序地組織這些數(shù)據(jù)担忧。因為數(shù)據(jù)暫時保存在內存中，內存并不是可靠存儲坯癣，如果斷電會丟失數(shù)據(jù)瓶盛，因此通常會通過WAL(Write-ahead logging，預寫式日志)的方式來保證數(shù)據(jù)的可靠性。

Immutable MemTable：當 MemTable達到一定大小后惩猫，會轉化成Immutable MemTable芝硬。Immutable MemTable是將轉MemTable變?yōu)镾STable的一種中間狀態(tài)。寫操作由新的MemTable處理轧房，在轉存過程中不阻塞數(shù)據(jù)更新操作拌阴。

SSTable(Sorted String Table)：有序鍵值對集合，是LSM樹組在磁盤中的數(shù)據(jù)結構锯厢，特點是有序且不可被更改皮官。為了加快SSTable的讀取，可以通過建立key的索引以及布隆過濾器來加快key的查找实辑。

LSM-tree的這種結構非常有利于數(shù)據(jù)的快速寫入(理論上可以接近磁盤順序寫速度)捺氢，但是不利于讀——因為理論上讀的時候可能需要同時從 memtable和所有硬盤上的 sstable中查詢數(shù)據(jù)，這樣顯然會對性能造成較大的影響剪撬。為了解決這個問題摄乒， LSM-tree采取了以下主要的相關措施。

• 定期將硬盤上小的 sstable合并(通常叫作 Merge或 Compaction操作)成大的 sstable残黑，以減少 sstable的數(shù)量馍佑。而且，平時的數(shù)據(jù)更新梨水、刪除操作并不會更新原有的數(shù)據(jù)文件拭荤，只會將更新刪除操作加到當前的數(shù)據(jù)文件末端，只有在 sstable合并的時候才會真正將重復的操作或更新去重疫诽、合并舅世。

• 對每個 sstable使用布隆過濾器( Bloom Filter)，以加速對數(shù)據(jù)在該 sstable的存在性進行判定奇徒，從而減少數(shù)據(jù)的總查詢時間雏亚。

1.3 總結

LSM樹和B+樹的差異主要在于讀性能和寫性能進行權衡，在犧牲的同時尋找其余補救方案摩钙。

B+樹存儲引擎罢低，不僅支持單條記錄的增、刪胖笛、讀网持、改操作，還支持順序掃描(B+樹的葉子節(jié)點之間的指針)长踊，對應的存儲系統(tǒng)就是關系數(shù)據(jù)庫功舀。但隨著寫入操作增多，為了維護B+樹結構之斯，節(jié)點分裂日杈，讀磁盤的隨機讀寫概率會變大，性能會逐漸減弱佑刷。

LSM樹(Log-Structured MergeTree)存儲引擎和B+樹存儲引擎一樣莉擒，同樣支持增、刪瘫絮、讀涨冀、改、順序掃描操作麦萤。而且通過批量存儲技術規(guī)避磁盤隨機寫入問題鹿鳖。當然凡事有利有弊，LSM 的設計目標是提供比傳統(tǒng)的 B+ 樹更好的寫性能壮莹。LSM 通過將磁盤的隨機寫轉化為順序寫來提高寫性能翅帜，而付出的代價就是犧牲部分讀性能、寫放大（B+樹同樣有寫放大的問題）命满。

LSM 相比 B+ 樹能提高寫性能的本質原因是：外存——無論磁盤還是SSD涝滴，其隨機讀寫都要慢于順序讀寫。

2胶台、基本操作

2.1 插入操作

LSM樹的插入較簡單歼疮，數(shù)據(jù)無腦往內存中的Level 0排序樹丟即可，并不關心該數(shù)據(jù)是否已經(jīng)在內存或磁盤中存在诈唬。（已經(jīng)存在該數(shù)據(jù)的話韩脏，則場景轉換成更新操作）

3.gif

如上圖所示，我們依次插入了key=9铸磅、1赡矢、6的數(shù)據(jù)，這三個數(shù)據(jù)均按照key的大小愚屁，插入內存里的Level 0排序樹中济竹。該操作復雜度為樹高log(n)，n是Level 0樹的數(shù)據(jù)量霎槐，以很低的代價實現(xiàn)了極高的寫吞吐量送浊。

2.2 刪除操作

LSM樹的刪除操作并不是直接刪除數(shù)據(jù)，而是通過一種叫“墓碑標記”的特殊數(shù)據(jù)來標識數(shù)據(jù)的刪除丘跌。

刪除操作分為：待刪除數(shù)據(jù)在內存中袭景、待刪除數(shù)據(jù)在磁盤中和該數(shù)據(jù)根本不存在三種情況。

2.2.1 待刪除數(shù)據(jù)在內存中

如下圖所示闭树，展示了待刪除數(shù)據(jù)在內存中的刪除過程耸棒。不能簡單地將Level 0樹中的黃色節(jié)點2刪除，而是應該采用墓碑標記將其覆蓋报辱。

4.gif

2.2.2 待刪除數(shù)據(jù)在磁盤中

如下圖所示与殃，展示了待刪除數(shù)據(jù)在磁盤上時的刪除過程。我們并不去修改磁盤上的數(shù)據(jù)（理都不理它），而是直接向內存中的Level 0樹中插入墓碑標記即可幅疼。

5.gif

2.2.3 待刪除數(shù)據(jù)根本不存在

這種情況等價于在內存的Level 0樹中新增一條墓碑標記米奸，場景轉換為情況2.2.2的內存中插入墓碑標記操作。

綜合看待上述三種情況爽篷，發(fā)現(xiàn)不論數(shù)據(jù)有沒有悴晰、在哪里，刪除操作都是等價于向Level 0樹中寫入墓碑標記逐工。該操作復雜度為樹高log(n)铡溪，代價很低。

2.3 修改操作

LSM樹的修改操作和刪除操作很像泪喊，也是分為三種情況：待修改數(shù)據(jù)在內存中棕硫、在磁盤中和該數(shù)據(jù)根本不存在。

2.3.1 待修改數(shù)據(jù)在內存中

6.gif

如上圖所示袒啼，展示了待修改數(shù)據(jù)在內存中的操作過程饲帅。新的藍色的key=7的數(shù)據(jù)，直接定位到內存中Level 0樹上黃色的老的key=7的位置瘤泪，將其覆蓋即可灶泵。

2.3.2 待修改數(shù)據(jù)在磁盤中

7.gif

如上圖所示，展示了待修改數(shù)據(jù)在磁盤中的操作過程对途。LSM樹并不會去磁盤中的Level 1樹上原地更新老的key=7的數(shù)據(jù)赦邻，而是直接將新的藍色的節(jié)點7插入內存中的Level 0樹中。

2.3.3 該數(shù)據(jù)根本不存在

此場景等價于情況2.3.2实檀，直接向內存中的Level 0樹插入新的數(shù)據(jù)即可惶洲。

通過以上三種情況可以看出，修改操作都是對內存中Level 0進行覆蓋/新增操作膳犹。該操作復雜度為樹高log(n)恬吕，代價依然很低。

我們會發(fā)現(xiàn)须床，LSM樹的增加铐料、刪除、修改都是在內存中操作豺旬，完全沒涉及到磁盤操作钠惩，所以速度飛快，寫吞吐量極高族阅。

2.4 查詢操作

LSM樹的查詢操作會按順序查找Level 0篓跛、Level 1、Level 2 ... Level n 每一顆樹坦刀，一旦匹配便返回目標數(shù)據(jù)愧沟，不再繼續(xù)查詢蔬咬。該策略保證了查到的一定是目標key最新版本的數(shù)據(jù)。

我們來分場景分析：依然分為待查詢數(shù)據(jù)在內存中和待查詢數(shù)據(jù)在磁盤中的兩種情況沐寺。

2.4.1 待查詢數(shù)據(jù)在內存中

8.gif

沿著內存中已排好序的Level 0樹遞歸向下比較查詢计盒，返回目標節(jié)點即可。我們注意到磁盤上的Level 1樹中同樣包括一個key=6的較老的數(shù)據(jù)芽丹。但LSM樹查詢的時候會按照Level 0、1卜朗、2 ... n的順序查詢拔第，一旦查到第一個就返回，因此磁盤上老的key=6的數(shù)據(jù)沒人理它场钉，更不會作為結果被返回蚊俺。

2.4.2 待查詢數(shù)據(jù)在磁盤中

9.gif

先查詢內存中的Level 0樹，沒查到便查詢磁盤中的Level 1樹逛万，還是沒查到泳猬，于是查詢磁盤中的Level 2樹，匹配后返回key=6的數(shù)據(jù)宇植。

綜合上述兩種情況得封，我們發(fā)現(xiàn)，LSM樹的查詢操作相對來說代價比較高指郁，需要從Level 0到Level n一直順序查下去忙上。極端情況是LSM樹中不存在該數(shù)據(jù)，則需要把整個庫從Level 0到Level n給掃了一遍闲坎，然后返回查無此人（可以通過 布隆過濾器 + 建立稀疏索引 來優(yōu)化查詢操作）疫粥。代價大于以B/B+樹為基本數(shù)據(jù)結構的傳統(tǒng)RDB存儲引擎。

2.5 合并操作

合并操作是LSM樹的核心（畢竟LSM樹的名字就叫: 日志結構合并樹腰懂，直接點名了合并這一操作）梗逮。

之所以在增、刪绣溜、改慷彤、查這四個基本操作之外還需要合并操作：

• 一是因為內存不是無限大，Level 0樹達到閾值時怖喻，需要將數(shù)據(jù)從內存刷到磁盤中
• 二是需要對磁盤上達到閾值的順序文件進行歸并瞬欧，并將歸并結果寫入下一層，歸并過程中會清理重復的數(shù)據(jù)和被刪除的數(shù)據(jù)(墓碑標記)罢防。

我們分別對上述兩個場景進行分析艘虎。

2.5.1 內存數(shù)據(jù)寫入磁盤的場景

10.gif

對內存中的Level 0樹進行中序遍歷，將數(shù)據(jù)順序寫入磁盤的Level 1層即可咒吐，我們可以看到因為Level 0樹是已經(jīng)排好序的野建，所以寫入的Level 1中的新塊也是有序的（有序性保證了查詢和歸并操作的高效）属划。此時磁盤的Level 1層有兩個Block塊。

2.5.2 磁盤中多個塊的歸并

11.gif

我們注意到key=5和key=7的數(shù)據(jù)同時存在于較老的Block 1和較新的Block 2中候生。而歸并的過程是保留較新的數(shù)據(jù)同眯，于是我們看到結果中，key=5和7的數(shù)據(jù)都是紅色的（來自于較新的Block2）唯鸭。

綜上我們可以看到须蜗，由于原始數(shù)據(jù)都是有序的，歸并的過程只需要對數(shù)據(jù)集進行一次掃描即可目溉，復雜度為O(n)明肮。

2.6 總結

可以看到LSM樹將增、刪缭付、改這三種操作都轉化為內存insert + 磁盤順序寫(當Level 0滿的時候)柿估，通過這種方式得到了無與倫比的寫吞吐量。

LSM樹的查詢能力則相對被弱化陷猫，相比于B+樹的最多3~4次磁盤IO秫舌，LSM樹則要從Level 0一路查詢Level n，極端情況下等于做了全表掃描绣檬。（即便做了稀疏索引足陨，也是lg(N0)+lg(N1)+...+lg(Nn)的復雜度，大于B+樹的lg(N0+N1+...+Nn)的時間復雜度）娇未。

同時钠右，LSM樹只append追加不原地修改的特性引入了歸并操作，歸并操作涉及到大量的磁盤IO忘蟹，比較消耗性能飒房，需要合理設置觸發(fā)該操作的參數(shù)。
另外媚值，LSM還有以下局限性：

• 讀放大：讀取數(shù)據(jù)時實際讀取的數(shù)據(jù)量大于真正的數(shù)據(jù)量狠毯。例如在LSM樹中需要先在MemTable查看當前key是否存在，不存在繼續(xù)從SSTable中尋找褥芒。

• 寫放大：寫入數(shù)據(jù)時實際寫入的數(shù)據(jù)量大于真正的數(shù)據(jù)量嚼松。例如在LSM樹中寫入時可能觸發(fā)Compact操作，導致實際寫入的數(shù)據(jù)量遠大于該key的數(shù)據(jù)量锰扶。

• 空間放大：數(shù)據(jù)實際占用的磁盤空間比數(shù)據(jù)的真正大小更多献酗。上面提到的冗余存儲，對于一個key來說坷牛，只有最新的那條記錄是有效的罕偎，而之前的記錄都是可以被清理回收的。