概要
本文是對(duì) ben stopford 個(gè)人網(wǎng)站上對(duì)于 LSM tree 的博客的翻譯，用于自己加強(qiáng)學(xué)習(xí)印象和理解深度，這里是原版博客。
注：里面有一些鏈接已經(jīng)失效，我自己有更改過。
Log Structured Merge Trees
自 Google 推出 “Bigtable” 已經(jīng)接近10年的時(shí)間了(文章于2015年2月14號(hào)所寫)，它所特別的地方是采用了一種文件組織方法。這種方法被稱之為日志結(jié)構(gòu)合并樹。日志結(jié)構(gòu)合并樹的文章發(fā)表于1996年，盡管它所描述的方法與現(xiàn)實(shí)中工程實(shí)現(xiàn)采用的方法有很大的不同。
LSM 作為核心的文件組織方法現(xiàn)在已經(jīng)被應(yīng)用到大量的產(chǎn)品中。HBase、Cassandra、LevelDB、SQLite，甚至 MongoDB 3.0 版本在收購(gòu) Wired Tiger 引擎之后都是由 LSM 算法驅(qū)動(dòng)的。
LSM trees 的有趣之處就在于它背離了二進(jìn)制風(fēng)格的文件組織方式。當(dāng)你第一次接觸 LSM trees 的時(shí)候，它多少會(huì)看起來有點(diǎn)違背你的直覺，但當(dāng)你更加深入的去思考它是怎么在模型和存儲(chǔ)系統(tǒng)中工作的，你就會(huì)明白它為什么要這么設(shè)計(jì)。
一些背景
總的來說 LSM trees 被設(shè)計(jì)用來提供比傳統(tǒng)的 B+tree 或 ISAM 方法更加良好的寫的效率，這是通過移除更新分散數(shù)據(jù)的需求實(shí)現(xiàn)的。
所以這為什是一個(gè)好的方法？這歸結(jié)于一個(gè)古老的問題：磁盤在處理順序訪問的速率往往要比處理隨機(jī)訪問的速率快很多。不管磁盤是固態(tài)硬盤還是機(jī)械磁盤，不管對(duì)于多小的主存，這兩個(gè)速率的差距還是很大的。
在ACM的這個(gè)報(bào)告中的數(shù)據(jù)就證明了這一點(diǎn)。他們有點(diǎn)與直覺相背離地展示出磁盤的順序訪問比主存的隨機(jī)訪問還要快。同時(shí)還證明了對(duì)于機(jī)械磁盤或者固態(tài)硬盤，順序訪問比隨機(jī)的IO至少快三個(gè)數(shù)量級(jí)。這意味著需要避免隨機(jī)操作，而順序的訪問更值得被設(shè)計(jì)。
因此，基于這一點(diǎn)，我們考慮以下的思考實(shí)驗(yàn)：如果我們注重寫的吞吐量，那么什么方法是最好的呢？一個(gè)很好的出發(fā)點(diǎn)是簡(jiǎn)單的對(duì)于文件延展數(shù)據(jù)。這種方法（通常被稱作日志或者堆文件）是完全順序的，所以它提供了非?？斓膶懶阅?，這大概和理論的磁盤速率相等（通常為200-300M／s）。
由于既簡(jiǎn)單又高效，因此基于日志的方法理所當(dāng)然的在很多的大數(shù)據(jù)工具中流行開來。但他們有明顯的缺點(diǎn)。在日志中讀取隨機(jī)的數(shù)據(jù)比寫入更加費(fèi)時(shí)，這需要反時(shí)間順序掃描，直到需要的 key 被找到。
這意味著日志只是適合于簡(jiǎn)單的工作，如數(shù)據(jù)已經(jīng)完全可以訪問的時(shí)候，如先寫日志的數(shù)據(jù)庫(kù)或者有已知偏移量，像簡(jiǎn)單的信息產(chǎn)品 Kafka 一樣。
所以我們除了日志以外，我們需要一些別的方法去提高在如基于鍵的訪問或者范圍查找這樣更加復(fù)雜的讀取工作中的性能?？偟膩碚f這里有4種方法能幫助我們：二分查找、哈希、B+ 或者外部的文件。
1.搜索排序文件：存儲(chǔ)數(shù)據(jù)到一個(gè)文件，并通過key來排序。數(shù)據(jù)被定義了寬度的時(shí)候使用二分查找，沒有定義寬度的時(shí)候使用頁(yè)索引+掃描。
2.Hash：通過哈希函數(shù)將數(shù)據(jù)拆分，之后能通過這個(gè)哈希函數(shù)直指向數(shù)據(jù)。
3.B+：使用可以導(dǎo)航的文件組織方式，如 B+tree 或者 ISAM 等。
4.外部文件：將數(shù)據(jù)存儲(chǔ)成日志／堆，并創(chuàng)建一個(gè)單獨(dú)的 hash 或者樹索引用于找到數(shù)據(jù)。
所有的這些方法都能顯著的提高讀的性能（大多情況下 n->O(log(n)）。顯然這些結(jié)構(gòu)增加了順序，然而順序又阻礙了寫的性能，所以我們的高速的日志處理方法似乎行不通。我猜你達(dá)不到你想要的效果。
很容易發(fā)現(xiàn)上面這四種方法都對(duì)數(shù)據(jù)的整體結(jié)構(gòu)強(qiáng)加了約束。
數(shù)據(jù)被有意地儲(chǔ)存在文件系統(tǒng)中特別的地方以方便我們使用索引快速找到它們。正是這些結(jié)構(gòu)使得導(dǎo)航得以快速進(jìn)行。也正是這些我們?cè)趯懭霑r(shí)候需要遵循的結(jié)構(gòu)，才會(huì)增加磁盤的隨機(jī)訪問所以降低了寫的性能。
這里有幾個(gè)具體問題，每次寫都需要兩次IO，一個(gè)去讀取頁(yè)一個(gè)寫入數(shù)據(jù)。但是使用日志的時(shí)候不會(huì)這樣，它只需要一次IO就能完成。
更糟的是，現(xiàn)在我們還需要去更新哈?；蛘連+的結(jié)構(gòu)。這就是我們要對(duì)文件系統(tǒng)的特殊部分進(jìn)行更新。而大家也知道這樣的更新需要速率很慢的隨機(jī)IO。這里有一點(diǎn)很重要：像這種很分散的更新方法是很局限的。
一種常用的解決方式是將索引也存儲(chǔ)在日志中，讓后將日志保存在內(nèi)存中。例如，一個(gè)哈希表能夠用來映射 key 到在日志中最新value 的位置（偏移量）。這種方法在處理相對(duì)較小的數(shù)據(jù)的IO下非常有效，比如儲(chǔ)存在內(nèi)存中，用來映射偏移量的key。這樣我們查找一個(gè)值的時(shí)候就只需要一次IO。
但另一方面這會(huì)帶來一些擴(kuò)展性的限制，特別是當(dāng)你有很多小的value，并且這些value只是一些簡(jiǎn)單的數(shù)字的時(shí)候，那么索引將會(huì)大于數(shù)據(jù)文件本身。盡管很多產(chǎn)品，如 Riak、Oracle Coherence 已經(jīng)明智的接受了這些限制。
所以這就引出了Log Structured Merge Trees。LSMs 定義了一種與上面四個(gè)方法不一樣的方法。它可以完全以磁盤為中心，只需要一點(diǎn)點(diǎn)的內(nèi)存來提高效率，同時(shí)使用一個(gè)簡(jiǎn)單的日志文件來提高寫的性能。
本質(zhì)上來講它使磁盤盡可能的產(chǎn)生順序訪問，而不是如上面所說的分散的隨機(jī)訪問。
存在許多不需要更新的樹的結(jié)構(gòu)，最流行的是只追加B樹（ append-only Btree），也被稱之為 copy-on-wirte 樹。他們通過覆蓋樹的結(jié)構(gòu)來工作，每次寫操作發(fā)生的時(shí)候他們就順序的在文件的最后追加覆蓋。相關(guān)部分的樹結(jié)構(gòu)，包括最頂層的節(jié)點(diǎn)都會(huì)被遺棄。通過這種方法，這就避免了更新操作因?yàn)榻?jīng)過時(shí)間的推移，樹會(huì)重新定義自己。然而這種方法是有代價(jià)的：每次寫入的時(shí)候都要重寫數(shù)據(jù)結(jié)構(gòu)是很冗余的操作，會(huì)產(chǎn)生很多的寫入放大，這也是它的一個(gè)缺點(diǎn)。
基本 LSM 算法
從概念上講，基本 LSM 算法很簡(jiǎn)單。批量寫入被順序地保存到一組較小的索引文件而不是一個(gè)很大的索引結(jié)構(gòu)（將會(huì)使文件系統(tǒng)內(nèi)部分散或者增加寫入放大）。所以每一個(gè)文件都包含一小段時(shí)間的變化。在寫入后每一個(gè)文件都被排序，所以在之后查找的時(shí)候會(huì)快很多。文件是不可變的，它們也從不更新。新的更新將會(huì)被寫入新的文件。讀取檢查所有的文件，并定期將文件合并從而減少文件的數(shù)量。
讓我們更加深入的去看看這一個(gè)過程。當(dāng)更新到來時(shí)候，將更新儲(chǔ)存在內(nèi)存緩沖區(qū)，為了保持 key 的順序通常采用樹的結(jié)構(gòu)儲(chǔ)存（如紅-黑樹等）。在大多數(shù)實(shí)現(xiàn)中，這個(gè)“memtable”在磁盤上作為預(yù)寫日志被復(fù)制，僅用于恢復(fù)。當(dāng) memtable 裝滿了之后排序的數(shù)據(jù)會(huì)被刷新到磁盤上。這個(gè)過程在越來越多的寫入操作到來時(shí)反復(fù)執(zhí)行。重要的是，當(dāng)文件不被編輯的情況下系統(tǒng)只執(zhí)行順序的 IO。新的寫入或者編輯只是簡(jiǎn)單的創(chuàng)建新的連續(xù)的文件（見上圖）。
所以當(dāng)越來越多的數(shù)據(jù)進(jìn)入系統(tǒng)的時(shí)候，越來越多的不可變的、排序的文件將會(huì)被創(chuàng)建。它們每一個(gè)都相當(dāng)于一個(gè)小的、按時(shí)間排序的變化子集，并且是有序的。
因?yàn)榕f的文件沒有更新，所以需要?jiǎng)?chuàng)建一些重復(fù)的條目來取代先前的記錄（或者刪除標(biāo)記）。這在最初會(huì)產(chǎn)生一些冗余。
系統(tǒng)定期執(zhí)行壓縮。這個(gè)壓縮過程會(huì)選擇一些文件進(jìn)行合并，并刪除所有重復(fù)的更新操作或者刪除操作（至于具體是怎么工作的我們下面再說）。這不僅對(duì)減少冗余有重要的意義，更重要的是，當(dāng)文件數(shù)量越來越多的時(shí)候這對(duì)寫入性能是有幫助的。并且，由于文件是有序的，所以在執(zhí)行合并文件的過程是非常高效的。
當(dāng)請(qǐng)求讀的操作時(shí)候，系統(tǒng)首先檢查內(nèi)存緩沖區(qū)，如果找不到 key那么將會(huì)按照時(shí)間順序逐個(gè)檢查文件，直到 key 被找到。每一個(gè)文件都按照順序以便于導(dǎo)航。但是由于每個(gè)文件都要檢查，所以讀的速率會(huì)隨著文件數(shù)量的增加變得越來越慢。這就是問題所在。
所以在 LSM trees 中讀的速率是比其他多路查找樹要慢的。幸運(yùn)的是，這里有一些小技巧能提高性能。最常用的方式是在內(nèi)存緩沖區(qū)中存入一個(gè)頁(yè)索引。這就相當(dāng)于提供了一個(gè)方便你查找到你的目標(biāo) key 的參照表。你在掃描的時(shí)候就像數(shù)據(jù)是排序的一樣。 LevelDB , RocksDB 和 BigTable 通過在每個(gè)文件的末尾加入一個(gè)塊索引來實(shí)現(xiàn)這個(gè)方法。因?yàn)樵试S使用可變長(zhǎng)字段，同時(shí)又適合于數(shù)據(jù)壓縮，所以這通常比直接二進(jìn)制搜索要好。
即使使用每個(gè)文件的索引，讀取速度依然會(huì)隨著文件的增加而變慢。所以周期性的文件合并檢查是很重要的，這可以使文件數(shù)量不會(huì)太多，同時(shí)讀取將會(huì)更加高效并維持在可接受的范圍內(nèi)。
即使經(jīng)過了壓縮，讀取的時(shí)候仍然要訪問許多文件。大多數(shù)實(shí)現(xiàn)中通過 Bloom filter / Bloom filter - 簡(jiǎn)書 來解決這個(gè)問題。Bloom filter 是一種高效判斷 key 是否在一個(gè)文件中的內(nèi)存方法。
所以從寫的角度來看，所有的寫入操作只能以連續(xù)的形式批量寫入。反復(fù)的文件合并會(huì)帶來額外的周期性的IO開銷。然而在尋找單一行的時(shí)候讀取操作還是有可能需要訪問大量的文件（讀取的時(shí)候是分散的）。這只是算法的工作方式，我們?cè)陔S機(jī)IO上進(jìn)行隨機(jī)IO寫操作。如果我們使用像 bloom filter 這樣的軟件技巧或者大量文件緩存這樣的硬件技巧來優(yōu)化讀取性能，那么這樣的做法是很明智可行的。
基本壓縮
想要保證 LSM 的讀取相對(duì)較快，文件的數(shù)量的限制管理是很重要的，所以讓我們更加深入的來看看文件合并這個(gè)過程。這個(gè)過程有點(diǎn)像垃圾回收：
當(dāng)缺點(diǎn)數(shù)量的文件產(chǎn)生之后，比如說5個(gè)文件，每個(gè)文件10行，它們將被合并成為一個(gè)50行的文件（也許更小一點(diǎn)）。
每當(dāng)10行的文件填滿之后，繼續(xù)將他們合并成50行的文件。
最終將會(huì)產(chǎn)生5個(gè)50行的文件，它們將被合并成一個(gè)250行的文件。這個(gè)過程會(huì)不斷創(chuàng)建更大的文件。見圖。
使用上述這種通用方法的問題是創(chuàng)建大量的文件：這些文件都必須單獨(dú)讀取，以便搜索結(jié)果。（至少在最糟的情況下是這樣）
分級(jí)壓縮
這里有一種新的實(shí)現(xiàn)方法，像 LevelDB, RocksDB 和 Cassandra 這些產(chǎn)品通過基于文件級(jí)別而不是通過基于文件大小的壓縮方法解決這個(gè)問題。這減少了最糟情況發(fā)生時(shí)候需要查詢文件的數(shù)量，同時(shí)減小了單個(gè)壓縮的相對(duì)影響。
這種基于級(jí)別的方法與基于大小的方法有兩個(gè)關(guān)鍵的不同：
1.每一個(gè)級(jí)別都包含許多文件，并且總體上保證里面不存在重復(fù)的關(guān)鍵字（key）。也就是說 key 在可用的文件中進(jìn)行分區(qū)，因此在一個(gè)確定的級(jí)別（層）去尋找一個(gè) key 的時(shí)候只用考慮一個(gè)文件。
第一級(jí)（層）是上述區(qū)別不成立的一個(gè)特例，key 可以跨越多個(gè)文件。
2.文件將被一次性合并到上一級(jí)中。當(dāng)某一級(jí)滿了的時(shí)候，將會(huì)從中抽取一個(gè)文件和上級(jí)的文件合并，為數(shù)據(jù)的添加騰出空間。這里與基于文件大小的方法（將幾個(gè)差不多大小的文件合并成更大的一個(gè)文件）略有不同。
這些改變意味著基于等級(jí)的方法隨著時(shí)間的推移會(huì)增加壓縮的影響，并且會(huì)更加減少空間的占用。它同樣有更良好的讀性能。但是大多數(shù)工作負(fù)載下的總 IO 量都較高，這就意味著一些簡(jiǎn)單的面向?qū)懙墓ぷ髫?fù)載將不會(huì)受益。
總結(jié)
因此，LSM trees 是日志方法和傳統(tǒng)的固定索引的方法（如B+樹 和 Hash 索引）的一個(gè)折中。它提供了管理一組較小的、單獨(dú)索引文件的機(jī)制。
通過管理一組索引而不是單獨(dú)的一個(gè)，LSM trees 將與B+ 、Hash 索引相關(guān)聯(lián)的低效的隨機(jī) IO 替換成為更快的、順序的IO。
這樣的代價(jià)是在讀取的時(shí)候?qū)⒁ㄎ淮罅康奈募皇呛?jiǎn)單的一個(gè)文件。這還有額外的壓縮 IO 產(chǎn)生。
關(guān)于 LSM trees 的思考
所以 LSM 方法是否真的比傳統(tǒng)的基于單一樹的方法好呢？
我們已經(jīng)知道 LSM 有更良好的寫的性能盡管這要付出一些讀的性能代價(jià)。LSM還有一些其他的好處。LSM 樹創(chuàng)建的 SSTable（排序文件）是不變的。這就使鎖的定義變得更加簡(jiǎn)單，唯一會(huì)爭(zhēng)用資源的地方是內(nèi)存中的 memtable，這與需要復(fù)雜的鎖定機(jī)制來管理不同級(jí)別變化的單樹形成鮮明的對(duì)比。
所以最終的問題是關(guān)于如何面向預(yù)期的工作負(fù)載來寫。如果你關(guān)心寫的性能那么 LSM 所能節(jié)省的成本是很可觀的。大型互聯(lián)網(wǎng)公司似乎在這個(gè)問題上毫不動(dòng)搖。例如，雅虎公司報(bào)告稱由于事件日志和移動(dòng)數(shù)據(jù)的增加，系統(tǒng)工作負(fù)載從以前的主要是重視讀穩(wěn)步轉(zhuǎn)變成為讀寫一致。許多傳統(tǒng)的數(shù)據(jù)庫(kù)產(chǎn)品看起來似乎依然更加適用于增強(qiáng)讀取能力的結(jié)構(gòu)。
和日志結(jié)構(gòu)化系統(tǒng)一樣[見腳注]，關(guān)鍵的爭(zhēng)論源于越來越多的可用內(nèi)存。隨著更多的可用內(nèi)存，讀取性能自然而然通過操作系統(tǒng)提供的大文件緩存得以提升。寫性能（不會(huì)隨著內(nèi)存的增加而提高）成為主要的關(guān)注點(diǎn)。所以換句話說，硬件的優(yōu)化對(duì)于讀取性能的優(yōu)化比寫性能的優(yōu)化要好，因此選擇更適用于優(yōu)化寫性能的文件結(jié)構(gòu)是很有意義的。
當(dāng)然，像 LevelDB、Cassandra 這樣的 LSM 實(shí)現(xiàn)相較于單一樹的方法提供了更加良好的寫的性能。
Levelled LSM 的拓展
這里有一些在 LSM 的基礎(chǔ)上做的一些工作。雅虎公司開發(fā)出來一個(gè)叫做 Pnuts 的系統(tǒng)，它結(jié)合了 LSM 和 B 樹，并且表現(xiàn)出更良好的性能。雖然我沒有看到這個(gè)算法公開可用的實(shí)現(xiàn)。IBM和Google也以類似的方式做了近期的工作，盡管路徑不同。也有相似的方法具有相似的性質(zhì)，但保留了總體結(jié)構(gòu)。這包括了 Fractal Trees 和 Stratified Trees 。
當(dāng)然這只是一種選擇，數(shù)據(jù)庫(kù)使用了許多不同的選擇。越來越多的數(shù)據(jù)庫(kù)為不同的工作負(fù)載提供了可以更換的數(shù)據(jù)引擎。 Parquet 是 HDFS 的一種流行的替代品，并且將其推向相反的發(fā)展方向（通過列格式的聚合性能）。MySQL有一個(gè)存儲(chǔ)抽象，可以插入一些不同的引擎，如 Toku 的基于分形樹的索引。這同樣適用于 MongoDB。MongoDB 3.0 提供了支持 B+ 和 LSM 方法的 Wired Tiger 引擎。許多關(guān)系數(shù)據(jù)庫(kù)都有可以配置的索引結(jié)構(gòu)，他們利用不同的文件組織起來。
硬件的使用也是值得考慮的一件事，昂貴的固態(tài)磁盤，如 FusionIO，具有更好的隨機(jī)寫入性能，它就適合于原位置更新方法。相對(duì)便宜的 SSD 和機(jī)械磁盤更適用于 LSM 方法。LSM 避免了能消耗大量固態(tài)硬盤性能的小型隨機(jī)訪問。
盡管如此，LSM 方法依然是充滿爭(zhēng)議的。如垃 GC（圾回收機(jī)制），最大的問題是回收階段對(duì) IO 的影響。在這個(gè)黑客新聞網(wǎng)站上有一些有趣的討論。
所以如果你正在看數(shù)據(jù)庫(kù)產(chǎn)品，無論是 BDB 還是 LevelDb ，Cassandra 或
MongoDb，你都可以將他們相對(duì)性能的某個(gè)比例與他們使用的文件結(jié)構(gòu)關(guān)聯(lián)起來。測(cè)試似乎支持這個(gè)觀點(diǎn)。當(dāng)然，值得注意的你應(yīng)該參考你所使用的系統(tǒng)來權(quán)衡性能。
在SSD中，每寫入一個(gè)完整的512K塊將會(huì)清除重寫周期。因此，小的寫入會(huì)導(dǎo)致驅(qū)動(dòng)器上不合適的流失量。對(duì)塊重寫有固定的限制會(huì)顯著影響他們的壽命。
擴(kuò)展閱讀
腳注：日志結(jié)構(gòu)化文件系統(tǒng)
除了名稱和側(cè)重于寫入吞吐量之外，就我所能看到的而言，LSM和日志結(jié)構(gòu)化文件系統(tǒng)之間沒有太多關(guān)系。
現(xiàn)在使用的常規(guī)文件系統(tǒng)往往是“日志記錄”，例如ext3，ext4，HFS等都是基于樹的方法。索引節(jié)點(diǎn)的固定高度的樹表示目錄結(jié)構(gòu)，日志用于防止故障情況。在這些實(shí)現(xiàn)中，日志是合乎邏輯的，這意味著只有內(nèi)部元數(shù)據(jù)才會(huì)被記錄。這是出于性能考慮的原因。
日志結(jié)構(gòu)化文件系統(tǒng)被廣泛的用于閃存介質(zhì)，因?yàn)樗鼈兊膶懭敕糯舐瘦^低。隨著文件緩存開始主宰更一般情況下的讀取工作負(fù)載，寫入性能變得越來越重要，他們也得到了更多的關(guān)注。
在日志結(jié)構(gòu)化的文件系統(tǒng)中，數(shù)據(jù)只寫入一次，并且被直接發(fā)送到一個(gè)被按時(shí)間順序推進(jìn)的緩沖區(qū)中。緩沖區(qū)是垃圾收集區(qū)域并定期刪除冗余的寫入。與 LSM 一樣，日志結(jié)構(gòu)化文件系統(tǒng)的寫入速度也會(huì)更快，但是讀取速度要遠(yuǎn)遠(yuǎn)低于基于樹的雙重寫入文件系統(tǒng)。在有大量?jī)?nèi)存可用于提供文件緩存的情況下，或者介質(zhì)不能很好地處理更新的情況下，這也是可以接受的，就像閃存一樣。
