概要
本文是對 ben stopford 個(gè)人網(wǎng)站上對于 LSM tree 的博客的翻譯，用于自己加強(qiáng)學(xué)習(xí)印象和理解深度托启，這里是原版博客。
注：里面有一些鏈接已經(jīng)失效攘宙，我自己有更改過屯耸。
Log Structured Merge Trees
自 Google 推出 “Bigtable” 已經(jīng)接近10年的時(shí)間了(文章于2015年2月14號所寫)，它所特別的地方是采用了一種文件組織方法蹭劈。這種方法被稱之為日志結(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 版本在收購 Wired Tiger 引擎之后都是由 LSM 算法驅(qū)動的前酿。
LSM trees 的有趣之處就在于它背離了二進(jìn)制風(fēng)格的文件組織方式。當(dāng)你第一次接觸 LSM trees 的時(shí)候鹏溯，它多少會看起來有點(diǎn)違背你的直覺罢维，但當(dāng)你更加深入的去思考它是怎么在模型和存儲系統(tǒng)中工作的，你就會明白它為什么要這么設(shè)計(jì)丙挽。
一些背景
總的來說 LSM trees 被設(shè)計(jì)用來提供比傳統(tǒng)的 B+tree 或 ISAM 方法更加良好的寫的效率肺孵，這是通過移除更新分散數(shù)據(jù)的需求實(shí)現(xiàn)的。
所以這為什是一個(gè)好的方法颜阐？這歸結(jié)于一個(gè)古老的問題：磁盤在處理順序訪問的速率往往要比處理隨機(jī)訪問的速率快很多平窘。不管磁盤是固態(tài)硬盤還是機(jī)械磁盤，不管對于多小的主存凳怨，這兩個(gè)速率的差距還是很大的瑰艘。
在ACM的這個(gè)報(bào)告中的數(shù)據(jù)就證明了這一點(diǎn)是鬼。他們有點(diǎn)與直覺相背離地展示出磁盤的順序訪問比主存的隨機(jī)訪問還要快。同時(shí)還證明了對于機(jī)械磁盤或者固態(tài)硬盤紫新，順序訪問比隨機(jī)的IO至少快三個(gè)數(shù)量級均蜜。這意味著需要避免隨機(jī)操作，而順序的訪問更值得被設(shè)計(jì)芒率。
因此囤耳，基于這一點(diǎn)，我們考慮以下的思考實(shí)驗(yàn)：如果我們注重寫的吞吐量敲董，那么什么方法是最好的呢紫皇？一個(gè)很好的出發(fā)點(diǎn)是簡單的對于文件延展數(shù)據(jù)。這種方法（通常被稱作日志或者堆文件）是完全順序的腋寨，所以它提供了非炒掀蹋快的寫性能，這大概和理論的磁盤速率相等（通常為200-300M／s）萄窜。
由于既簡單又高效铃剔，因此基于日志的方法理所當(dāng)然的在很多的大數(shù)據(jù)工具中流行開來。但他們有明顯的缺點(diǎn)查刻。在日志中讀取隨機(jī)的數(shù)據(jù)比寫入更加費(fèi)時(shí)键兜，這需要反時(shí)間順序掃描，直到需要的 key 被找到穗泵。
這意味著日志只是適合于簡單的工作普气，如數(shù)據(jù)已經(jīng)完全可以訪問的時(shí)候，如先寫日志的數(shù)據(jù)庫或者有已知偏移量佃延，像簡單的信息產(chǎn)品 Kafka 一樣现诀。
所以我們除了日志以外，我們需要一些別的方法去提高在如基于鍵的訪問或者范圍查找這樣更加復(fù)雜的讀取工作中的性能履肃∽醒兀總的來說這里有4種方法能幫助我們：二分查找、哈希尺棋、B+ 或者外部的文件封锉。
1.搜索排序文件：存儲數(shù)據(jù)到一個(gè)文件，并通過key來排序膘螟。數(shù)據(jù)被定義了寬度的時(shí)候使用二分查找成福，沒有定義寬度的時(shí)候使用頁索引+掃描。
2.Hash：通過哈希函數(shù)將數(shù)據(jù)拆分荆残，之后能通過這個(gè)哈希函數(shù)直指向數(shù)據(jù)闷叉。
3.B+：使用可以導(dǎo)航的文件組織方式，如 B+tree 或者 ISAM 等脊阴。
4.外部文件：將數(shù)據(jù)存儲成日志／堆握侧，并創(chuàng)建一個(gè)單獨(dú)的 hash 或者樹索引用于找到數(shù)據(jù)蚯瞧。
所有的這些方法都能顯著的提高讀的性能（大多情況下 n->O(log(n)）。顯然這些結(jié)構(gòu)增加了順序品擎，然而順序又阻礙了寫的性能埋合，所以我們的高速的日志處理方法似乎行不通。我猜你達(dá)不到你想要的效果萄传。
很容易發(fā)現(xiàn)上面這四種方法都對數(shù)據(jù)的整體結(jié)構(gòu)強(qiáng)加了約束甚颂。
數(shù)據(jù)被有意地儲存在文件系統(tǒng)中特別的地方以方便我們使用索引快速找到它們。正是這些結(jié)構(gòu)使得導(dǎo)航得以快速進(jìn)行秀菱。也正是這些我們在寫入時(shí)候需要遵循的結(jié)構(gòu)振诬，才會增加磁盤的隨機(jī)訪問所以降低了寫的性能。
這里有幾個(gè)具體問題衍菱，每次寫都需要兩次IO赶么，一個(gè)去讀取頁一個(gè)寫入數(shù)據(jù)。但是使用日志的時(shí)候不會這樣脊串，它只需要一次IO就能完成辫呻。
更糟的是，現(xiàn)在我們還需要去更新哈锨矸妫或者B+的結(jié)構(gòu)放闺。這就是我們要對文件系統(tǒng)的特殊部分進(jìn)行更新。而大家也知道這樣的更新需要速率很慢的隨機(jī)IO。這里有一點(diǎn)很重要：像這種很分散的更新方法是很局限的。
一種常用的解決方式是將索引也存儲在日志中墓捻，讓后將日志保存在內(nèi)存中。例如匾寝，一個(gè)哈希表能夠用來映射 key 到在日志中最新value 的位置（偏移量）。這種方法在處理相對較小的數(shù)據(jù)的IO下非常有效叉谜，比如儲存在內(nèi)存中，用來映射偏移量的key踩萎。這樣我們查找一個(gè)值的時(shí)候就只需要一次IO停局。
但另一方面這會帶來一些擴(kuò)展性的限制，特別是當(dāng)你有很多小的value香府，并且這些value只是一些簡單的數(shù)字的時(shí)候董栽，那么索引將會大于數(shù)據(jù)文件本身。盡管很多產(chǎn)品企孩，如 Riak锭碳、Oracle Coherence 已經(jīng)明智的接受了這些限制。
所以這就引出了Log Structured Merge Trees勿璃。LSMs 定義了一種與上面四個(gè)方法不一樣的方法擒抛。它可以完全以磁盤為中心推汽，只需要一點(diǎn)點(diǎn)的內(nèi)存來提高效率，同時(shí)使用一個(gè)簡單的日志文件來提高寫的性能歧沪。
本質(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)都會被遺棄邪码。通過這種方法裕菠，這就避免了更新操作因?yàn)榻?jīng)過時(shí)間的推移，樹會重新定義自己霞扬。然而這種方法是有代價(jià)的：每次寫入的時(shí)候都要重寫數(shù)據(jù)結(jié)構(gòu)是很冗余的操作糕韧，會產(chǎn)生很多的寫入放大，這也是它的一個(gè)缺點(diǎn)喻圃。
基本 LSM 算法
從概念上講萤彩，基本 LSM 算法很簡單。批量寫入被順序地保存到一組較小的索引文件而不是一個(gè)很大的索引結(jié)構(gòu)（將會使文件系統(tǒng)內(nèi)部分散或者增加寫入放大）斧拍。所以每一個(gè)文件都包含一小段時(shí)間的變化雀扶。在寫入后每一個(gè)文件都被排序，所以在之后查找的時(shí)候會快很多肆汹。文件是不可變的愚墓，它們也從不更新。新的更新將會被寫入新的文件昂勉。讀取檢查所有的文件浪册，并定期將文件合并從而減少文件的數(shù)量。
讓我們更加深入的去看看這一個(gè)過程岗照。當(dāng)更新到來時(shí)候村象，將更新儲存在內(nèi)存緩沖區(qū)，為了保持 key 的順序通常采用樹的結(jié)構(gòu)儲存（如紅-黑樹等）攒至。在大多數(shù)實(shí)現(xiàn)中厚者，這個(gè)“memtable”在磁盤上作為預(yù)寫日志被復(fù)制，僅用于恢復(fù)迫吐。當(dāng) memtable 裝滿了之后排序的數(shù)據(jù)會被刷新到磁盤上库菲。這個(gè)過程在越來越多的寫入操作到來時(shí)反復(fù)執(zhí)行。重要的是志膀，當(dāng)文件不被編輯的情況下系統(tǒng)只執(zhí)行順序的 IO熙宇。新的寫入或者編輯只是簡單的創(chuàng)建新的連續(xù)的文件（見上圖）鳖擒。
所以當(dāng)越來越多的數(shù)據(jù)進(jìn)入系統(tǒng)的時(shí)候，越來越多的不可變的奇颠、排序的文件將會被創(chuàng)建败去。它們每一個(gè)都相當(dāng)于一個(gè)小的、按時(shí)間排序的變化子集烈拒，并且是有序的圆裕。
因?yàn)榕f的文件沒有更新，所以需要創(chuàng)建一些重復(fù)的條目來取代先前的記錄（或者刪除標(biāo)記）荆几。這在最初會產(chǎn)生一些冗余吓妆。
系統(tǒng)定期執(zhí)行壓縮。這個(gè)壓縮過程會選擇一些文件進(jìn)行合并吨铸，并刪除所有重復(fù)的更新操作或者刪除操作（至于具體是怎么工作的我們下面再說）行拢。這不僅對減少冗余有重要的意義，更重要的是诞吱，當(dāng)文件數(shù)量越來越多的時(shí)候這對寫入性能是有幫助的舟奠。并且，由于文件是有序的房维，所以在執(zhí)行合并文件的過程是非常高效的沼瘫。
當(dāng)請求讀的操作時(shí)候，系統(tǒng)首先檢查內(nèi)存緩沖區(qū)咙俩，如果找不到 key那么將會按照時(shí)間順序逐個(gè)檢查文件耿戚，直到 key 被找到。每一個(gè)文件都按照順序以便于導(dǎo)航阿趁。但是由于每個(gè)文件都要檢查膜蛔，所以讀的速率會隨著文件數(shù)量的增加變得越來越慢。這就是問題所在脖阵。
所以在 LSM trees 中讀的速率是比其他多路查找樹要慢的皂股。幸運(yùn)的是，這里有一些小技巧能提高性能命黔。最常用的方式是在內(nèi)存緩沖區(qū)中存入一個(gè)頁索引呜呐。這就相當(dāng)于提供了一個(gè)方便你查找到你的目標(biāo) key 的參照表。你在掃描的時(shí)候就像數(shù)據(jù)是排序的一樣纷铣。 LevelDB , RocksDB 和 BigTable 通過在每個(gè)文件的末尾加入一個(gè)塊索引來實(shí)現(xiàn)這個(gè)方法卵史。因?yàn)樵试S使用可變長字段战转，同時(shí)又適合于數(shù)據(jù)壓縮搜立，所以這通常比直接二進(jìn)制搜索要好。
即使使用每個(gè)文件的索引槐秧，讀取速度依然會隨著文件的增加而變慢啄踊。所以周期性的文件合并檢查是很重要的忧设，這可以使文件數(shù)量不會太多，同時(shí)讀取將會更加高效并維持在可接受的范圍內(nèi)颠通。
即使經(jīng)過了壓縮址晕，讀取的時(shí)候仍然要訪問許多文件。大多數(shù)實(shí)現(xiàn)中通過 Bloom filter / Bloom filter - 簡書 來解決這個(gè)問題顿锰。Bloom filter 是一種高效判斷 key 是否在一個(gè)文件中的內(nèi)存方法谨垃。
所以從寫的角度來看，所有的寫入操作只能以連續(xù)的形式批量寫入硼控。反復(fù)的文件合并會帶來額外的周期性的IO開銷刘陶。然而在尋找單一行的時(shí)候讀取操作還是有可能需要訪問大量的文件（讀取的時(shí)候是分散的）。這只是算法的工作方式牢撼，我們在隨機(jī)IO上進(jìn)行隨機(jī)IO寫操作匙隔。如果我們使用像 bloom filter 這樣的軟件技巧或者大量文件緩存這樣的硬件技巧來優(yōu)化讀取性能，那么這樣的做法是很明智可行的熏版。
基本壓縮
想要保證 LSM 的讀取相對較快纷责，文件的數(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行的文件胜榔。
最終將會產(chǎn)生5個(gè)50行的文件胳喷，它們將被合并成一個(gè)250行的文件。這個(gè)過程會不斷創(chuàng)建更大的文件夭织。見圖吭露。
使用上述這種通用方法的問題是創(chuàng)建大量的文件：這些文件都必須單獨(dú)讀取，以便搜索結(jié)果尊惰。（至少在最糟的情況下是這樣）
分級壓縮
這里有一種新的實(shí)現(xiàn)方法讲竿，像 LevelDB, RocksDB 和 Cassandra 這些產(chǎn)品通過基于文件級別而不是通過基于文件大小的壓縮方法解決這個(gè)問題。這減少了最糟情況發(fā)生時(shí)候需要查詢文件的數(shù)量弄屡，同時(shí)減小了單個(gè)壓縮的相對影響题禀。
這種基于級別的方法與基于大小的方法有兩個(gè)關(guān)鍵的不同：
1.每一個(gè)級別都包含許多文件，并且總體上保證里面不存在重復(fù)的關(guān)鍵字（key）膀捷。也就是說 key 在可用的文件中進(jìn)行分區(qū)迈嘹，因此在一個(gè)確定的級別（層）去尋找一個(gè) key 的時(shí)候只用考慮一個(gè)文件。
第一級（層）是上述區(qū)別不成立的一個(gè)特例，key 可以跨越多個(gè)文件秀仲。
2.文件將被一次性合并到上一級中融痛。當(dāng)某一級滿了的時(shí)候，將會從中抽取一個(gè)文件和上級的文件合并神僵，為數(shù)據(jù)的添加騰出空間雁刷。這里與基于文件大小的方法（將幾個(gè)差不多大小的文件合并成更大的一個(gè)文件）略有不同。
這些改變意味著基于等級的方法隨著時(shí)間的推移會增加壓縮的影響保礼，并且會更加減少空間的占用沛励。它同樣有更良好的讀性能。但是大多數(shù)工作負(fù)載下的總 IO 量都較高炮障，這就意味著一些簡單的面向?qū)懙墓ぷ髫?fù)載將不會受益侯勉。
總結(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ū)⒁ㄎ淮罅康奈募皇呛唵蔚囊粋€(gè)文件螟凭。這還有額外的壓縮 IO 產(chǎn)生。
關(guān)于 LSM trees 的思考
所以 LSM 方法是否真的比傳統(tǒng)的基于單一樹的方法好呢螺男？
我們已經(jīng)知道 LSM 有更良好的寫的性能盡管這要付出一些讀的性能代價(jià)。LSM還有一些其他的好處纵穿。LSM 樹創(chuàng)建的 SSTable（排序文件）是不變的下隧。這就使鎖的定義變得更加簡單，唯一會爭用資源的地方是內(nèi)存中的 memtable谓媒，這與需要復(fù)雜的鎖定機(jī)制來管理不同級別變化的單樹形成鮮明的對比淆院。
所以最終的問題是關(guān)于如何面向預(yù)期的工作負(fù)載來寫。如果你關(guān)心寫的性能那么 LSM 所能節(jié)省的成本是很可觀的句惯。大型互聯(lián)網(wǎng)公司似乎在這個(gè)問題上毫不動搖土辩。例如，雅虎公司報(bào)告稱由于事件日志和移動數(shù)據(jù)的增加抢野，系統(tǒng)工作負(fù)載從以前的主要是重視讀穩(wěn)步轉(zhuǎn)變成為讀寫一致拷淘。許多傳統(tǒng)的數(shù)據(jù)庫產(chǎn)品看起來似乎依然更加適用于增強(qiáng)讀取能力的結(jié)構(gòu)。
和日志結(jié)構(gòu)化系統(tǒng)一樣[見腳注]指孤，關(guān)鍵的爭論源于越來越多的可用內(nèi)存启涯。隨著更多的可用內(nèi)存，讀取性能自然而然通過操作系統(tǒng)提供的大文件緩存得以提升。寫性能（不會隨著內(nèi)存的增加而提高）成為主要的關(guān)注點(diǎn)逝嚎。所以換句話說，硬件的優(yōu)化對于讀取性能的優(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ù)庫使用了許多不同的選擇膛薛。越來越多的數(shù)據(jù)庫為不同的工作負(fù)載提供了可以更換的數(shù)據(jù)引擎。 Parquet 是 HDFS 的一種流行的替代品补鼻，并且將其推向相反的發(fā)展方向（通過列格式的聚合性能）哄啄。MySQL有一個(gè)存儲抽象，可以插入一些不同的引擎风范，如 Toku 的基于分形樹的索引咨跌。這同樣適用于 MongoDB。MongoDB 3.0 提供了支持 B+ 和 LSM 方法的 Wired Tiger 引擎硼婿。許多關(guān)系數(shù)據(jù)庫都有可以配置的索引結(jié)構(gòu)虑润，他們利用不同的文件組織起來。
硬件的使用也是值得考慮的一件事加酵，昂貴的固態(tài)磁盤拳喻，如 FusionIO，具有更好的隨機(jī)寫入性能猪腕，它就適合于原位置更新方法冗澈。相對便宜的 SSD 和機(jī)械磁盤更適用于 LSM 方法。LSM 避免了能消耗大量固態(tài)硬盤性能的小型隨機(jī)訪問陋葡。
盡管如此亚亲，LSM 方法依然是充滿爭議的。如垃 GC（圾回收機(jī)制），最大的問題是回收階段對 IO 的影響捌归。在這個(gè)黑客新聞網(wǎng)站上有一些有趣的討論肛响。
所以如果你正在看數(shù)據(jù)庫產(chǎn)品，無論是 BDB 還是 LevelDb 惜索，Cassandra 或
MongoDb特笋，你都可以將他們相對性能的某個(gè)比例與他們使用的文件結(jié)構(gòu)關(guān)聯(lián)起來。測試似乎支持這個(gè)觀點(diǎn)巾兆。當(dāng)然猎物，值得注意的你應(yīng)該參考你所使用的系統(tǒng)來權(quán)衡性能。
在SSD中角塑，每寫入一個(gè)完整的512K塊將會清除重寫周期蔫磨。因此，小的寫入會導(dǎo)致驅(qū)動器上不合適的流失量圃伶。對塊重寫有固定的限制會顯著影響他們的壽命堤如。
擴(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ù)才會被記錄递惋。這是出于性能考慮的原因。
日志結(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)的寫入速度也會更快，但是讀取速度要遠(yuǎn)遠(yuǎn)低于基于樹的雙重寫入文件系統(tǒng)见咒。在有大量內(nèi)存可用于提供文件緩存的情況下偿衰，或者介質(zhì)不能很好地處理更新的情況下，這也是可以接受的改览，就像閃存一樣下翎。
