LSM 演算法的原理是什麼？

01-05

http://www.open-open.com/lib/view/open1424916275249.html 粘貼黨

Log Structured Merge Trees(LSM) 原理

十年前，谷歌發表了「BigTable」的論文，論文中很多很酷的方面之一就是它所使用的文件組織方式，這個方法更一般的名字叫 Log Structured-Merge Tree。

LSM是當前被用在許多產品的文件結構策略：HBase, Cassandra, LevelDB, SQLite,甚至在mangodb3.0中也帶了一個可選的LSM引擎（Wired Tiger 實現的）。

LSM 有趣的地方是他拋棄了大多數資料庫所使用的傳統文件組織方法，實際上，當你第一次看它是違反直覺的。

背景知識

簡單的說，LSM被設計來提供比傳統的B+樹或者ISAM更好的寫操作吞吐量，通過消去隨機的本地更新操作來達到這個目標。

那麼為什麼這是一個好的方法呢？這個問題的本質還是磁碟隨機操作慢，順序讀寫快的老問題。這二種操作存在巨大的差距，無論是磁碟還是SSD。

上圖很好的說明了這一點，他們展現了一些反直覺的事實，順序讀寫磁碟（不管是SATA還是SSD）快於隨機讀寫主存，而且快至少三個數量級。這說明我們要避免隨機讀寫，最好設計成順序讀寫。

所以，讓我們想想，如果我們對寫操作的吞吐量敏感，我們最好怎麼做？一個好的辦法是簡單的將數據添加到文件。這個策略經常被使用在日誌或者堆文件，因為他們是完全順序的，所以可以提供非常好的寫操作性能，大約等於磁碟的理論速度，也就是200~300 MB/s。

因為簡單和高效，基於日誌的策略在大數據之間越來越流行，同時他們也有一些缺點，從日誌文件中讀一些數據將會比寫操作需要更多的時間，需要倒序掃描，直接找到所需的內容。

這說明日誌僅僅適用於一些簡單的場景：1. 數據是被整體訪問，像大部分資料庫的WAL(write-ahead log) 2. 知道明確的offset，比如在Kafka中。

所以，我們需要更多的日誌來為更複雜的讀場景（比如按key或者range）提供高效的性能，這兒有4個方法可以完成這個，它們分別是：

二分查找: 將文件數據有序保存，使用二分查找來完成特定key的查找。
哈希：用哈希將數據分割為不同的bucket
B+樹：使用B+樹或者 ISAM 等方法，可以減少外部文件的讀取
外部文件：將數據保存為日誌，並創建一個hash或者查找樹映射相應的文件。

所有的方法都可以有效的提高了讀操作的性能（最少提供了O(log(n)) )，但是，卻丟失了日誌文件超好的寫性能。上面這些方法，都強加了總體的結構信息在數據上，數據被按照特定的方式放置，所以可以很快的找到特定的數據，但是卻對寫操作不友善，讓寫操作性能下降。

更糟糕的是，當我們需要更新hash或者B+樹的結構時，需要同時更新文件系統中特定的部分，這就是上面說的比較慢的隨機讀寫操作。這種隨機的操作要盡量減少。

所以這就是 LSM 被發明的原理， LSM 使用一種不同於上述四種的方法，保持了日誌文件寫性能，以及微小的讀操作性能損失。本質上就是讓所有的操作順序化，而不是像散彈槍一樣隨機讀寫。

很多樹結構可以不用 update-in-place，最流行就是

append-only Btreehttp://www.bzero.se/ldapd/btree.html

，也稱為 Copy-On-Write Tree。他們通過順序的在文件末尾重複寫對結構來實現寫操作，之前的樹結構的相關部分，包括最頂層結點都會變成孤結點。儘管通過這種方法避免了本地更新，但是因為每個寫操作都要重寫樹結構，放大了寫操作，降低了寫性能。

The Base LSM Algorithm

從概念上說，最基本的LSM是很簡單的。將之前使用一個大的查找結構（造成隨機讀寫，影響寫性能），變換為將寫操作順序的保存到一些相似的有序文件（也就是sstable)中。所以每個文件包含短時間內的一些改動。因為文件是有序的，所以之後查找也會很快。文件是不可修改的，他們永遠不會被更新，新的更新操作只會寫到新的文件中。讀操作檢查很有的文件。通過周期性的合併這些文件來減少文件個數。

讓我們更具體的看看，當一些更新操作到達時，他們會被寫到內存緩存（也就是memtable）中，memtable使用樹結構來保持key的有序，在大部分的實現中，memtable會通過寫WAL的方式備份到磁碟，用來恢複數據，防止數據丟失。當memtable數據達到一定規模時會被刷新到磁碟上的一個新文件，重要的是系統只做了順序磁碟讀寫，因為沒有文件被編輯，新的內容或者修改只用簡單的生成新的文件。

所以越多的數據存儲到系統中，就會有越多的不可修改的，順序的sstable文件被創建，它們代表了小的，按時間順序的修改。

因為比較舊的文件不會被更新，重複的紀錄只會通過創建新的紀錄來覆蓋，這也就產生了一些冗餘的數據。

所以系統會周期的執行合併操作（compaction)。合併操作選擇一些文件，並把他們合併到一起，移除重複的更新或者刪除紀錄，同時也會刪除上述的冗餘。更重要的是，通過減少文件個數的增長，保證讀操作的性能。因為sstable文件都是有序結構的，所以合併操作也是非常高效的。

當一個讀操作請求時，系統首先檢查內存數據(memtable)，如果沒有找到這個key，就會逆序的一個一個檢查sstable文件，直到key 被找到。因為每個sstable都是有序的，所以查找比較高效(O(logN))，但是讀操作會變的越來越慢隨著sstable的個數增加，因為每一個 sstable都要被檢查。（O(K log N), K為sstable個數， N 為sstable平均大小）。

所以，讀操作比其它本地更新的結構慢，幸運的是，有一些技巧可以提高性能。最基本的的方法就是頁緩存（也就是leveldb的 TableCache，將sstable按照LRU緩存在內存中）在內存中，減少二分查找的消耗。LevelDB 和 BigTable 是將 block-index 保存在文件尾部，這樣查找就只要一次IO操作，如果block-index在內存中。一些其它的系統則實現了更複雜的索引方法。

即使有每個文件的索引，隨著文件個數增多，讀操作仍然很慢。通過周期的合併文件，來保持文件的個數，因些讀操作的性能在可接收的範圍內。即便有了合並操作，讀操作仍然會訪問大量的文件，大部分的實現通過布隆過濾器來避免大量的讀文件操作，布隆過濾器是一種高效的方法來判斷一個sstable中是否包含一個特定的key。（如果bloom說一個key不存在，就一定不存在，而當bloom說一個文件存在是，可能是不存在的，只是通過概率來保證）

所有的寫操作都被分批處理，只寫到順序塊上。另外，合併操作的周期操作會對IO有影響，讀操作有可能會訪問大量的文件（散亂的讀）。這簡化了演算法工作的方法，我們交換了讀和寫的隨機IO。這種折衷很有意義，我們可以通過軟體實現的技巧像布隆過濾器或者硬體（大文件cache）來優化讀性能。

Basic Compaction

為了保持LSM的讀操作相對較快，維護並減少sstable文件的個數是很重要的，所以讓我們更深入的看一下合併操作。這個過程有一點兒像一般垃圾回收演算法。

當一定數量的sstable文件被創建，例如有5個sstable，每一個有10行，他們被合併為一個50行的文件（或者更少的行數）。這個過程一直持續著，當更多的有10行的sstable文件被創建，當產生5個文件時，它們就被合併到50行的文件。最終會有5個50行的文件，這時會將這5個50 行的文件合併成一個250行的文件。這個過程不停的創建更大的文件。像下圖：

上述的方案有一個問題，就是大量的文件被創建，在最壞的情況下，所有的文件都要搜索。

Levelled Compaction

更新的實現，像 LevelDB 和 Cassandra解決這個問題的方法是：實現了一個分層的，而不是根據文件大小來執行合併操作。這個方法可以減少在最壞情況下需要檢索的文件個數，同時也減少了一次合併操作的影響。

按層合併的策略相對於上述的按文件大小合併的策略有二個關鍵的不同：

每一層可以維護指定的文件個數，同時保證不讓key重疊。也就是說把key分區到不同的文件。因此在一層查找一個key，只用查找一個文件。第一層是特殊情況，不滿足上述條件，key可以分布在多個文件中。
每次，文件只會被合併到上一層的一個文件。當一層的文件數滿足特定個數時，一個文件會被選出併合併到上一層。這明顯不同與另一種合併方式：一些相近大小的文件被合併為一個大文件。

這些改變表明按層合併的策略減小了合併操作的影響，同時減少了空間需求。除此之外，它也有更好的讀性能。但是對於大多數場景，總體的IO次數變的更多，一些更簡單的寫場景不適用。

總結

所以， LSM 是日誌和傳統的單文件索引（B+ tree，Hash Index）的中立，他提供一個機制來管理更小的獨立的索引文件(sstable)。

通過管理一組索引文件而不是單一的索引文件，LSM 將B+樹等結構昂貴的隨機IO變的更快，而代價就是讀操作要處理大量的索引文件(sstable)而不是一個，另外還是一些IO被合併操作消耗。

如果還有不明白的，這還有一些其它的好的介紹。

http://leveldb.googlecode.com/svn/trunk/doc/impl.html

and here

關於 LSM 的一些思考

為什麼 LSM 會比傳統單個樹結構有更好的性能？

我們看到LSM有更好的寫性能，同時LSM還有其它一些好處。 sstable文件是不可修改的，這讓對他們的鎖操作非常簡單。一般來說，唯一的競爭資源就是 memtable，相對來說需要相對複雜的鎖機制來管理在不同的級別。

所以最後的問題很可能是以寫為導向的壓力預期如何。如果你對LSM帶來的寫性能的提高很敏感，這將會很重要。大型互聯網企業似乎很看中這個問題。 Yahoo 提出因為事件日誌的增加和手機數據的增加，工作場景為從 read-heavy 到 read-write。。許多傳統資料庫產品似乎更青睞讀優化文件結構。

因為可用的內存的增加，通過操作系統提供的大文件緩存，讀操作自然會被優化。寫性能（內存不可提高）因此變成了主要的關注點，所以採取其它的方法，硬體提升為讀性能做的更多，相對於寫來說。因此選擇一個寫優化的文件結構很有意義。

理所當然的，LSM的實現，像LevelDB和Cassandra提供了更好的寫性能，相對於單樹結構的策略。

Beyond Levelled LSM

這有更多的工作在LSM上， Yahoo開發了一個系統叫作 Pnuts，組合了LSM與B樹，提供了更好的性能。我沒有看到這個演算法的開放的實現。 IBM和Google也實現了這個演算法。也有相關的策略通過相似的屬性，但是是通過維護一個拱形的結構。如 Fractal Trees， Stratified Trees.

這當然是一個選擇，資料庫利用大量的配置，越來越多的資料庫為不同的工作場景提供插件式引擎。 Parquet 是一個流行的HDFS的替代，在很多相對的文面做的好很（通過一個列格式提高性能）。MySQL有一個存儲抽象，支持大量的存儲引擎的插件，例如 Toku (使用 fractal tree based index)。

Mongo3.0 則包含了支持B+和LSM的 Wired Tiger引擎。許多關係資料庫可以配置索引結構，使用不同的文件格式。

考慮被使用的硬體，昂貴的SSD，像FusionIO有更好的隨機寫性能，這適合本地更新的策略方法。更便宜的SSD和機械盤則更適合LSM。

延伸閱讀

There is a nice introductory post
https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/.
The LSM description in this
http://www.eecs.harvard.edu/~margo/cs165/papers/gp-lsm.pdf
is great and it also discusses interesting extensions.
These three posts provide a holistic coverage of the algorithm:
http://leveldb.googlecode.com/svn/trunk/doc/impl.html, http://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra and http://www.quora.com/How-does-the-Log-Structured-Merge-Tree-work.
The original Log Structured Merge Tree pape
r http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782rep=rep1type=pdf
. It is a little hard to follow in my opinion.
The Big Table paper
http://static.googleusercontent.com/media/research.google.com/en/archive/bigtable-osdi06.pdf
is excellent.
http://highscalability.com/blog/2014/8/6/tokutek-white-paper-a-comparison-of-log-structured-merge-lsm.html
on High Scalability.
Recent work on
http://researcher.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf
which builds on the LSM concept.
http://blog.empathybox.com/post/24415262152/ssds-and-distributed-data-systems
on SSDs and the benefits of LSM

來自：

http://lcblog.sinaapp.com/?p=223

其實大家提的 LSM 最開始論文裡面都使用樹做搜索結構的, 現在在用的都不是嚴格的樹結構了。

如[這篇文章](https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/)解釋的一樣，從最樸素的角度上來講可以把`SSTable(sorted string table)`作為一個連續的kv構成的塊。

SSTable +-+---+----+---+ |k| v | k | v | ... +-+---+----+---+

對於一個大文件來說，讀取整個文件以後就能構成一個各個鍵值的索引，當然可以在文件追加一塊索引，和文件一起保存。

Index +-+-------+ |k|offset | +-+-------+ |k|offset | +-+-------+ . . .

有了索引以後用 seek 操作或者直接把文件 mmap 到內存中都可以有很好的隨機讀性能。

但是對於隨機寫來說, 會造成大量的I/O，如果我們能夠保證我們的`SSTable`是不可修改(immutable)的，只有`SSTable`在內存當中的時候(也就是`MemTable`)才可以修改，就能避免隨機寫的大負載問題。

通過下面幾條約束就能完成我們的要求：
1. 首先`SSTable`索引要放在內存中，這樣讀索引更快
2. 所有寫只能寫到`MemTable`當中, 因為`SSTable`不可修改
3. 所有讀要先查看`MemTable`如果沒有再查看內存中的索引(最後找到磁碟上的kv)
4. 定期把`MemTable`刷成`SSTable`,這段時間`MemTable`也變成了不可修改的,新的`MemTable`會頂替
5. 定期對`SSTable`進行合併

最終我們保證了隨機寫很快（因為只在`MemTable`中），隨機讀也很快（因為要麼在`MemTable`中要麼通過索引可以很快找到)。

還有一個問題是對於已有數據的刪除和修改怎麼辦？

因為`SSTable`不可修改所以只能追加寫一個新的數據覆蓋老的數據，對於刪除則是追加一個"墓碑"值覆蓋掉存在的值。把索引指向新值，這樣老值就不會被訪問了。最後在`SSTable`合併的時候這些老值會完全消失。所以還要定期合併`SSTable`

以上是對leveldb的LSM結構的樸素解釋。實際上`MemTable`和`SSTable`都沒有採用純粹的樹形結構,`MemTable`使用的是跳錶而`SSTable`使用的是層次的結構。(這也是為什麼 leveldb 叫 level db 的原因)

從這裡開始完善樸素解釋

首先對於`MemTable`來說不是持久化的如果重啟導致內存中的數據丟失怎麼辦？[WAL](https://github.com/facebook/rocksdb/wiki/Write-Ahead-Log-File-Format) 表示的是預寫日誌，這個日誌和`MemTable`是同步的，這個日誌把每次的命令追加到日誌中再更改`MemTable`，這樣如果重啟的話能夠進行"重放"把從已經持久化的狀態開始把數據填回到`MemTable`當中。

其次是對`SSTable`的合併，`SSTable`是分層存儲的，第一層也就是Level0(被稱作 young level)，是`MemTable`刷入的一層，允許這一層的`SSTable`的key有交集。對於每一層都有一個閾值(young level 是 4,其他層是按大小算的，10^L MB)，如果超過閾值自動向下一層合併，從level1開始的每一次key不允許有交集。具體的做法是從 young level 中把有交集的`SSTable`一起和下一層key有交集的`SSTable`合併成一個新的`SSTable`，然後其他層則是從自身層取出一個和下一層有交集的`SSTable`合併即可。這個屬性可以用歸納法證明，從0層向1層合併的時候，1層只有一個的情況下肯定不會相交，然後假設n個的時候也不相交，在n+1的時候有交集，那麼n+1合併時有0層的 key 和 n 當中的有交集，但是有交集的部分會被歸併掉所以矛盾，所以n+1個的時候也是沒有交集的。那1層能保證沒有交集的話取出一個向下合併也是類似的不會有交集。所以再重複一遍分層存儲的兩個屬性。

對於樸素解釋的兩個擴展使得我們對leveldb的設計更接近了。

1. young層SSTable之間可能存在交集
2. Li（i&>0）層SSTable之間不存在交集

在這個基礎上再增加幾個約束條件，一個是，對於合併過程每超過2MB就會產生一個新文件，如果文件和下一層的文件有交集的個數有10個以上的話也會產生一個新文件，這樣的目的是保證Ln和Ln+1之間不會重複太多。個人理解是覆蓋太多，會成了倒三角的"樹"情況，上一層搜索性能不好。

當然大量的隨機讀落在磁碟上還是會有性能問題，因為 seek 也可能是不連續的，這個可以用樓上提到的緩存的方式彌補。

來自從樸素解釋出發解釋leveldb的設計

http://f.dataguru.cn/thread-58476-1-1.html