LSM-Tree 是一種設計思想。在此思想下，可以帶來極高的寫入速度。但是稍微犧牲了讀取的速度。另外要知道，在此設計下，無法對事務有很好的支援。
還要知道，這種方式的寫入方式，它是近實時的，在實時性上略有犧牲。 在此設計下，背後要進行merge，要花費很多的資源。
十多年前，谷歌釋出了大名鼎鼎的"三駕馬車"的論文，分别是GFS(2003年)，MapReduce（2004 年），BigTable（2006年），為開源界在大資料領域帶來了無數的靈感，其中在 “BigTable” 的論文中很多很酷的方面之一就是它所使用的檔案組織方式，這個方法更一般的名字叫 Log Structured-Merge Tree。在面對億級别之上的海量資料的存儲和檢索的場景下，我們選擇的資料庫通常都是各種強力的NoSQL，比如Hbase，Cassandra，Leveldb，RocksDB等等，這其中前兩者是Apache下面的頂級開源項目資料庫，後兩者分别是Google和Facebook開源的資料庫存儲引擎。而這些強大的NoSQL資料庫都有一個共性，就是其底層使用的資料結構，都是仿照“BigTable”中的檔案組織方式來實作的，也就是我們今天要介紹的LSM-Tree。
什麼是LSM-Tree
LSM-Tree全稱是Log Structured Merge Tree，是一種分層，有序，面向磁盤的資料結構，其核心思想是充分了利用了，磁盤批量的順序寫要遠比随機寫性能高出很多，如下圖示：
圍繞這一原理進行設計和優化，以此讓寫性能達到最優，正如我們普通的Log的寫入方式，這種結構的寫入，全部都是以Append的模式追加，不存在删除和修改。當然有得就有舍，這種結構雖然大大提升了資料的寫入能力，卻是以犧牲部分讀取性能為代價，故此這種結構通常适合于寫多讀少的場景。故LSM被設計來提供比傳統的B+樹或者ISAM更好的寫操作吞吐量，通過消去随機的本地更新操作來達到這個目标。這裡面最典型的例子就屬于Kakfa了，把磁盤順序寫發揮到了極緻，故而在大資料領域成為了網際網路公司标配的分布式消息中間件元件。
雖然這種結構的寫非常簡單高效，但其缺點是對讀取特别是随機讀很不友好，這也是為什麼日志通常用在下面的兩種簡單的場景：
（1） 資料是被整體通路的，大多數資料庫的WAL（write ahead log）也稱預寫log，包括mysql的Binlog等
（2） 資料是通過檔案的偏移量offset通路的，比如Kafka。
想要支援更複雜和高效的讀取，比如按key查詢和按range查詢，就得需要做一步的設計，這也是LSM-Tree結構，除了利用磁盤順序寫之外，還劃分了記憶體+磁盤多層的合并結構的原因，正是基于這種結構再加上不同的優化實作，才造就了在這之上的各種獨具特點的NoSQL資料庫，如Hbase，Cassandra，Leveldb，RocksDB，MongoDB，TiDB等。
LSM-Tree 合并思想
LSM 樹由兩個或以上的存儲結構組成，比如在論文中為了友善說明使用了最簡單的兩個存儲結構。一個存儲結構常駐記憶體中，稱為 C0 tree ，具體可以是任何友善健值查找的資料結構，比如紅黑樹、 map 之類，甚至可以是跳表。另外一個存儲結構常駐在硬碟中，稱為 C1 tree ，具體結構類似 B 樹。 C1 所有節點都是 100% 滿的，節點的大小為磁盤塊大小。
LSM-Tree 存儲結構 1
LSM-Tree 存儲結構 2
如上圖所示，資料庫采用了基于 LSM Tree 結構作為資料庫的存儲引擎，資料被分為基線資料（ SSTable ）和增量資料（ MemTable ）兩部分，基線資料被儲存在磁盤中，當需要讀取的時候會被加載到資料庫的緩存中，當資料被不斷插入（或者修改時）在記憶體中緩存增量資料，當增量資料達到一定閥值時，就把增量資料重新整理到磁盤上，當磁盤上的增量資料達到一定閥值時再把磁盤上的增量資料和基線資料進行合并。這個本身是 LSM 的核心設計思想，非常樸素，就是将對資料的修改增量保持在記憶體中，達到指定的大小限制後将這些修改操作批量寫入磁盤，進而大幅度提升性能。關于樹的節點資料結構，不同資料庫在基于 LSM-Tree 思想實作具體存儲引擎的時候，可以根據自己的特點去定義。
LSM-Tree WAL
談及 LSM （ Log Structured Merge Tree ）樹存儲引擎，從字面意思上，其實我們基本能看到兩層意思，第一個是 Merge ，就是我們上一節說到的合并思想；另外一個就是 Log ，就是我們接下來要說的 WAL 檔案，從下面展示的基于 LSM 存儲引擎的寫的流程當中，我們可以看到 WAL 就是資料庫的一個日志檔案。
LSM-Tree 寫資料流程圖
當插入一條資料時，資料先順序寫入磁盤儲存的 WAL 檔案中，之後插入到記憶體中的 Memtable 當中， Memtable 實際上儲存的資料結構就是我們所述的記憶體當中的小樹。這樣就保證了資料的持久化，即使因為故障當機，雖然記憶體裡面的資料已經丢失，但是依然可以通過日志資訊恢複當初記憶體裡面的資料資訊，并且都是順序寫，速度非常快。當 memtable 寫入檔案 SSTable 後，這個 log 檔案的内容就不再需要了。而新的 memtable 會有新的 log 檔案對應。
SSTable 和 LSM-Tree
提到LSM-Tree這種結構，就得提一下LevelDB這個存儲引擎，我們知道Bigtable是谷歌開源的一篇論文，很難接觸到它的源代碼實作。如果說Bigtable是分布式閉源的一個高性能的KV系統，那麼LevelDB就是這個KV系統開源的單機版實作，最為重要的是LevelDB是由Bigtable的原作者 Jeff Dean 和 Sanjay Ghemawat 共同完成，可以說高度複刻了Bigtable 論文中對于其實作的描述。
在LSM-Tree裡面，核心的資料結構就是SSTable，全稱是Sorted String Table，SSTable的概念其 實也是來自于 Google 的 Bigtable 論文，論文中對 SSTable 的描述如下：
An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Operations are provided to look up the value associated with a specified key, and to iterate over all key/value pairs in a specified key range. Internally, each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory, which allows us to perform lookups and scans without touching disk.
如上所述，SSTable是一種擁有持久化，有序且不可變的的鍵值存儲結構，它的key和value都是任意的位元組數組，并且了提供了按指定key查找和指定範圍的key區間疊代周遊的功能。SSTable内部包含了一系列可配置大小的Block塊，典型的大小是64KB，關于這些Block塊的index存儲在SSTable的尾部，用于幫助快速查找特定的Block。當一個SSTable被打開的時候，index會被加載到記憶體，然後根據key在記憶體index裡面進行一個二分查找，查到該key對應的磁盤的offset之後，然後去磁盤把響應的塊資料讀取出來。當然如果記憶體足夠大的話，可以直接把SSTable直接通過MMap的技術映射到記憶體中，進而提供更快的查找。
SSTable 在背景是要經過不斷地排序合并，檔案随着層次的加深，其大小也逐漸變大。同時它也是可以啟用壓縮功能的，并且這種壓縮不是将整個 SSTable 一起壓縮，而是根據 locality 将資料分組，每個組分别壓縮，這樣的好處當讀取資料的時候，我們不需要解壓縮整個檔案而是解壓縮部分 Group 就可以讀取。如圖下圖所示的情況， leve0 的 SSTable 達到資料量的閥值之後，會經過排序合并形成 Level1 的 SSTable ， Level1 的 SSTable 達到閥值之後，會經過排序合并成為 Level2 的 SSTable 檔案。
LSM-Tree SSTable’s merge
以上圖中所示的檔案合并過程是一個排序合并的過程，是以每一層都包含大量 SSTable 檔案，但是鍵值值範圍不重複，這樣查詢操作隻需要查詢這一層的一個 SSTable 檔案即可。
關于LSM-Tree的讀寫原理
在LSM-Tree裡，SSTable有一份在記憶體裡面，其他的多級在磁盤上，如下圖是一份完整的LSM-Tree圖示：
LSM-Tree寫資料的過程
1，當收到一個寫請求時，會先把該條資料記錄在WAL Log裡面，用作故障恢複。
2，當寫完WAL Log後，會把該條資料寫入記憶體的SSTable裡面（删除是墓碑标記，更新是新記錄一條的資料），也稱Memtable。注意為了維持有序性在記憶體裡面可以采用紅黑樹或者跳躍表相關的資料結構。
3，當Memtable超過一定的大小後，會在記憶體裡面當機，變成不可變的Memtable，同時為了不阻塞寫操作需要新生成一個Memtable繼續提供服務。
4，把記憶體裡面不可變的Memtable給dump到到硬碟上的SSTable層中，此步驟也稱為Minor Compaction，這裡需要注意在L0層的SSTable是沒有進行合并的，是以這裡的key range在多個SSTable中可能會出現重疊，在層數大于0層之後的SSTable，不存在重疊key。
5，當每層的磁盤上的SSTable的體積超過一定的大小或者個數，也會周期的進行合并。此步驟也稱為Major Compaction，這個階段會真正 的清除掉被标記删除掉的資料以及多版本資料的合并，避免浪費空間，注意由于SSTable都是有序的，我們可以直接采用merge sort進行高效合并。
LSM-Tree讀資料的過程
1，當收到一個讀請求的時候，會直接先在記憶體裡面查詢，如果查詢到就傳回。
2，如果沒有查詢到就會依次下沉，知道把所有的Level層查詢一遍得到最終結果。
思考查詢步驟，我們會發現如果SSTable的分層越多，那麼最壞的情況下要把所有的分層掃描一遍，對于這種情況肯定是需要優化的，如何優化？在 Bigtable 論文中提出了幾種方式：
1，壓縮
SSTable 是可以啟用壓縮功能的，并且這種壓縮不是将整個 SSTable 一起壓縮，而是根據 locality 将資料分組，每個組分别壓縮，這樣的好處當讀取資料的時候，我們不需要解壓縮整個檔案而是解壓縮部分 Group 就可以讀取。
2，緩存
因為SSTable在寫入磁盤後，除了Compaction之外，是不會變化的，是以我可以将Scan的Block進行緩存，進而提高檢索的效率
3，索引，Bloom filters
正常情況下，一個讀操作是需要讀取所有的 SSTable 将結果合并後傳回的，但是對于某些 key 而言，有些 SSTable 是根本不包含對應資料的，是以，我們可以對每一個 SSTable 添加 Bloom Filter，因為布隆過濾器在判斷一個SSTable不存在某個key的時候，那麼就一定不會存在，利用這個特性可以減少不必要的磁盤掃描。
4，合并
這個在前面的寫入流程中已經介紹過，通過定期合并瘦身， 可以有效的清除無效資料，縮短讀取路徑，提高磁盤利用空間。但Compaction操作是非常消耗CPU和磁盤IO的，尤其是在業務高峰期，如果發生了Major Compaction，則會降低整個系統的吞吐量，這也是一些NoSQL資料庫，比如Hbase裡面常常會禁用Major Compaction，并在淩晨業務低峰期進行合并的原因。
最後有的同學可能會問道，為什麼LSM不直接順序寫入磁盤，而是需要在記憶體中緩沖一下？ 這個問題其實很容易解答，單條寫的性能肯定沒有批量寫來的塊，這個原理其實在Kafka裡面也是一樣的，雖然kafka給我們的感覺是寫入後就落地，但其實并不是，本身是 可以根據條數或者時間比如200ms刷入磁盤一次，這樣能大大提升寫入效率。此外在LSM中，在磁盤緩沖的另一個好處是，針對新增的資料，可以直接查詢傳回，能夠避免一定的IO操作。
LSM-Tree 資料修改過程
LSM-Tree 存儲引擎的更新過程其實并不存在，它不會像 B 樹存儲引擎那樣，先經過檢索過程，然後再進行修改。它的更新操作是通過追加資料來間接實作，也就是說更新最終轉換為追加一個新的資料。隻是在讀取的時候，會從 Level0 層的 SSTable 檔案開始查找資料，資料在低層的 SSTable 檔案中必然比高層的檔案中要新，是以總能讀取到最新的那條資料。也就是說此時在整個 LSM Tree 中可能會同時存在多個 key 值相同的資料，隻有在之後合并 SSTable 檔案的時候，才會将舊的值删除。
LSM-Tree 資料删除過程
LSM-Tree 存儲引擎的對資料的删除過程與追加資料的過程基本一樣，差別在于追加資料的時候，是有具體的資料值的，而删除的時候，追加的資料值是删除标記。同樣在讀取的時候，會從 Level0 層的 SSTable 檔案開始查找資料，資料在低層的 SSTable 檔案中必然比高層的檔案中要新，是以如果有删除操作，那麼一定會最先讀到帶删除标記的那條資料。後期合并 SSTable 檔案的時候，才會把資料删除。
不過瘾，再看看
B+Tree VS LSM-Tree
傳統關系型資料采用的底層資料結構是B+樹，那麼同樣是面向磁盤存儲的資料結構LSM-Tree相比B+樹有什麼異同之處呢？
LSM-Tree的設計思路是，将資料拆分為幾百M大小的Segments，并是順序寫入。
B+Tree則是将資料拆分為固定大小的Block或Page, 一般是4KB大小，和磁盤一個扇區的大小對應，Page是讀寫的最小機關。
在資料的更新和删除方面，B+Tree可以做到原地更新和删除，這種方式對資料庫事務支援更加友好，因為一個key隻會出現一個Page頁裡面，但由于LSM-Tree隻能追加寫，并且在L0層key的rang會重疊，是以對事務支援較弱，隻能在Segment Compaction的時候進行真正地更新和删除。
是以LSM-Tree的優點是支援高吞吐的寫（可認為是O（1）），這個特點在分布式系統上更為看重，當然針對讀取普通的LSM-Tree結構，讀取是O（N）的複雜度，在使用索引或者緩存優化後的也可以達到O（logN）的複雜度。
而B+tree的優點是支援高效的讀（穩定的OlogN），但是在大規模的寫請求下（複雜度O(LogN)），效率會變得比較低，因為随着insert的操作，為了維護B+樹結構，節點會不斷的分裂和合并。操作磁盤的随機讀寫機率會變大，故導緻性能降低。
還有一點需要提到的是基于LSM-Tree分層存儲能夠做到寫的高吞吐，帶來的副作用是整個系統必須頻繁的進行compaction，寫入量越大，Compaction的過程越頻繁。而compaction是一個compare & merge的過程，非常消耗CPU和存儲IO，在高吞吐的寫入情形下，大量的compaction操作占用大量系統資源，必然帶來整個系統性能斷崖式下跌，對應用系統産生巨大影響，當然我們可以禁用自動Major Compaction，在每天系統低峰期定期觸發合并，來避免這個問題。
阿裡為了優化這個問題，在X-DB引入了異構硬體裝置FPGA來代替CPU完成compaction操作，使系統整體性能維持在高水位并避免抖動，是存儲引擎得以服務業務苛刻要求的關鍵。
LSM Tree的用武之地
elasticsearch搜尋引擎中有用到LSM-Tree
clickHouse中有用到LSM-Tree
總結
本文主要介紹了LSM-Tree的相關内容，簡單的說，其犧牲了部分讀取的性能，通過批量順序寫來換取了高吞吐的寫性能，這種特性在大資料領域得到充分了展現，最直接的例子就各種NoSQL在大資料領域的應用，學習和了解LSM-Tree的結構将有助于我們更加深入的去了解相關NoSQL資料庫的實作原理，掌握隐藏在這些架構下面的核心知識。
參考文章：DB 存儲引擎：LSM-Tree 存儲引擎詳細分解 - 趙海 - twt企業IT交流平台