思想：數(shù)據(jù)修改增量保持在內(nèi)存中，達(dá)到限制后將修改操作批量寫入到磁盤中，相比較于寫入操作的高性能，讀取需要合并內(nèi)存中最近修改的操作和磁盤中歷史的數(shù)據(jù)，即需要先看是否在內(nèi)存中，若沒有命中，還要訪問磁盤文件。
原理：大樹拆分成N棵小樹，先寫入內(nèi)存中，小樹越來越大，內(nèi)存的小樹會flush到磁盤中。磁盤中的樹定期做合并操作，合并一棵大樹，優(yōu)化讀性能。
對應(yīng)于使用LSM的Leveldb來說，對于一個寫操作，先寫入到memtable中，當(dāng)memtable達(dá)到一定的限制后，這部分轉(zhuǎn)成immutable memtable（不可寫），當(dāng)immutable memtable達(dá)到一定限制，將flush到磁盤中，即sstable.，sstable再進(jìn)行compaction操作。
鏈接：https://www.zhihu.com/question/19887265/answer/365078623
LSM-Tree的價值已經(jīng)越來越低
過去LSM-Tree相比B-Tree有兩個優(yōu)點(diǎn)：
1. 可以使用無鎖的跳表來管理還處在內(nèi)存中未刷到硬盤的那部分熱數(shù)據(jù)，提高寫并發(fā)；
2. 寫入內(nèi)存前不用從硬盤讀出舊數(shù)據(jù)，而是采用定期合并新老數(shù)據(jù)的方式。
缺點(diǎn)也很明顯，影響讀性能，還得處理刺手的數(shù)據(jù)緊縮問題，還有寫放大問題。
出現(xiàn)無鎖B-Tree，第一個優(yōu)點(diǎn)已經(jīng)不是優(yōu)點(diǎn)了。
第二點(diǎn)，隨機(jī)寫場景，如果B-Tree的page緩存命中率很高就不是大問題。LSM-Tree用到了關(guān)系數(shù)據(jù)庫的場景，第二點(diǎn)就雞肋，因?yàn)閷?shí)際場景中的關(guān)系表通常都有主鍵、唯一約束、引用完整性約束以及觸發(fā)器，要實(shí)現(xiàn)這些功能每次寫常常伴隨著讀操作。
過去刷B-Tree的臟頁到硬盤會產(chǎn)生緩慢的隨機(jī)寫，現(xiàn)在無論是寫redo log還是刷臟頁都可以變成順序?qū)懥?/b>。
將整個磁盤就看做是一個日志，在日志中存放永久性數(shù)據(jù)及其索引，每次都添加到日志的末尾；通過將很多小文件的存取轉(zhuǎn)換為連續(xù)的大批量傳輸，使得對于文件系統(tǒng)的大多數(shù)存取都是順序性的，從而提高磁盤帶寬利用率，故障恢復(fù)速度快。適用于會產(chǎn)生大量插入操作的應(yīng)用環(huán)境。
LSM-tree
LSM-tree是由兩個或兩個以上存儲數(shù)據(jù)的結(jié)構(gòu)組成的。最簡單的LSM-tree由兩個部件構(gòu)成。
C0樹：常駐內(nèi)存，為任何方便鍵值查找的數(shù)據(jù)結(jié)構(gòu)，
C1樹：常駐硬盤，數(shù)據(jù)結(jié)構(gòu)與B-tree類似。經(jīng)常被訪問的結(jié)點(diǎn)也將會被緩存在內(nèi)存中。如下圖：
insert時，先寫入日志文件（恢復(fù)做準(zhǔn)備）。再插入到C0（根據(jù)索引值），不需要硬盤的I/O操作，C0的大小達(dá)到某一閾值時，內(nèi)存存儲的代價會比硬盤的I/O操作和存儲代價還高。所以將有一部分從C0滾動合并到硬盤中的C1，以減少C0的大小，C1的結(jié)構(gòu)與B-tree相似，結(jié)點(diǎn)中的條目是滿的，大小為一頁，樹根之下的所有單頁結(jié)點(diǎn)合并到地址連續(xù)的多頁塊中。
除了在多頁塊中不必從左至右填充結(jié)點(diǎn)外，C1與SB-tree幾乎相同。
如圖所示。J-1層結(jié)點(diǎn)包含連續(xù)的指向J層結(jié)點(diǎn)（node1，node2，...nodeK）的指針（P1，P2，...，PK）和分割指針的鍵（S1，S2，...，SK-1）。J層結(jié)點(diǎn)連續(xù)存放在多頁塊的K頁中，并且不必按照鍵的大小排列。如果J層的兩個結(jié)點(diǎn)存放于同一個多頁塊中，那這兩個結(jié)點(diǎn)的鍵值之間的所有結(jié)點(diǎn)也存放在多頁塊中。M是多頁塊分割的標(biāo)記，表示直到下一個M標(biāo)記或空結(jié)點(diǎn)之內(nèi)的所有后續(xù)結(jié)點(diǎn)都存放在同一個多頁塊中。M中包含了多頁塊開始的硬盤頁號和多頁塊中結(jié)點(diǎn)的數(shù)量。樹根始終是以一個單頁存儲的?？梢钥闯龆囗搲K可用于范圍檢索，而多頁塊中結(jié)點(diǎn)可用于精確的鍵值匹配的檢索。假設(shè)C0也是一種B-tree，設(shè)想在滾動合并時，C0和C1都有一個指向相等鍵值的游標(biāo)，游標(biāo)指向下一個將要合并的葉子結(jié)點(diǎn)中的條目。從根結(jié)點(diǎn)到達(dá)這個位置的路徑將C1上所有正在進(jìn)行滾動合并的多頁塊分成兩部分。一部分是游標(biāo)還未到達(dá)的結(jié)點(diǎn)，合并時讀入清空塊（emptying block），另一部分是游標(biāo)已經(jīng)過的結(jié)點(diǎn)，即滾動合并的結(jié)果，合并時寫入填充塊（filling block）。這樣的過程如下：
1.從C1中讀入未合并的葉子結(jié)點(diǎn)，存儲于內(nèi)存的清空塊中；
2.從C0中讀取葉子結(jié)點(diǎn)，并與清空塊中的葉子結(jié)點(diǎn)進(jìn)行合并排序；
3. 將合并排序的結(jié)果寫入填充塊中，并從C0中刪除用于合并排序的舊葉子結(jié)點(diǎn)；
4. 不斷地重復(fù)步驟2和3，當(dāng)填充塊被合并排序的結(jié)果填滿時，將填充塊追加到硬盤的新位置，并從C1中刪除用于合并排序的舊葉子結(jié)點(diǎn)，當(dāng)清空塊被全部讀取完時，再從C1中讀入未合并的葉子結(jié)點(diǎn)；
5.當(dāng)C0和C1的所有葉子節(jié)點(diǎn)都被讀入內(nèi)存進(jìn)行合并，并產(chǎn)生新的葉子結(jié)點(diǎn)之后，C0和C1的一次滾動合并就結(jié)束了。
C0并不將所有的條目都拿來滾動合并。由于C0存儲在內(nèi)存之中，所以C0可以保留最近插入或最常訪問的那些數(shù)據(jù)，以提高訪問速率并降低I/O操作的次數(shù)。C1的舊多頁塊可用于崩潰恢復(fù)，所以為了不覆蓋舊多頁塊，滾動合并產(chǎn)生的新多頁塊將被寫入硬盤的新空間。一般來說，每次合并之后，會剩下一些不滿的沒有寫入硬盤的填充塊，沒有填入填充塊的葉子結(jié)點(diǎn)，這些結(jié)點(diǎn)會和它們的目錄結(jié)點(diǎn)一樣暫時緩存在內(nèi)存中，等待下次滾動合并時，再寫入相應(yīng)的填充塊或者填滿并寫入硬盤。另外當(dāng)設(shè)置檢查點(diǎn)時，這些緩存的信息會被強(qiáng)制寫入硬盤。葉子結(jié)點(diǎn)載入內(nèi)存后，其父結(jié)點(diǎn)（目錄結(jié)點(diǎn)）也會被緩存至內(nèi)存中以減小滾動合并時所需的I/O操作。當(dāng)滾動合并產(chǎn)生新的葉子結(jié)點(diǎn)產(chǎn)生后，會導(dǎo)致父結(jié)點(diǎn)（或者目錄結(jié)點(diǎn)）發(fā)生相應(yīng)的變化。當(dāng)C1的父結(jié)點(diǎn)所屬的多頁塊不滿時，通常會停留在內(nèi)存中一段時間，但其所指的葉子結(jié)點(diǎn)可以先寫入硬盤之中。當(dāng)發(fā)生下列情況時，目錄結(jié)點(diǎn)及其多頁塊將被強(qiáng)制寫入硬盤：
1.? ?一個包含目錄結(jié)點(diǎn)的多頁塊已滿；只將滿的多頁塊寫入硬盤。
2.? ?根結(jié)點(diǎn)分裂，C1樹的深度增加；所有的多頁塊緩存都將被寫入硬盤。
3.? ?設(shè)置檢查點(diǎn)。所有的多頁塊都將被寫入硬盤。
兩部件LSM-tree的代價估計(jì)
為了對LSM-tree的代價進(jìn)行簡單地估計(jì)。首先定義硬盤和內(nèi)存的代價符號如下：COSTd=1M字節(jié)的硬盤存儲的代價COSTm=1M字節(jié)的內(nèi)存存儲的代價COSTP=隨機(jī)訪問時，每秒讀寫一頁的I/O操作所需硬盤臂移動的代價COSTπ=多頁塊讀寫時，每秒讀寫一頁的I/O操作所需硬盤臂移動的代價這里需要注意的是，就目前而言，硬盤存儲的代價要低于內(nèi)存存儲的代價，即COSTd
LSM-tree與B-tree的插入代價比較
執(zhí)行B-tree的插入操作需要首先找到條目要插入的位置，即要進(jìn)行一次B-tree查找。假設(shè)插入的位置是隨機(jī)的，那么之前插入所緩存的結(jié)點(diǎn)頁面可能就無法重復(fù)使用了。由此定義：De=使用B-tree進(jìn)行隨機(jī)訪問時，在內(nèi)存緩存中未找到的頁數(shù)為了執(zhí)行一個插入操作，需要進(jìn)行De次I/O操作以在B-tree葉結(jié)點(diǎn)中找到插入的位置，插入數(shù)據(jù)之后，再進(jìn)行1次I/O操作將新數(shù)據(jù)寫回。由于相關(guān)結(jié)點(diǎn)的分裂對開銷作用不大，這里我們就不考慮結(jié)點(diǎn)的分裂問題了。那么B-tree的插入代價就是
OSTB?ins=COSTP(De+1)
LSM-tree的插入操作首先是直接作用在常駐內(nèi)存的C0上的，然后是批量地從C0將條目滾動合并到C1中。滾動合并是以多頁塊作為單元進(jìn)行合并的，合并時讀取一頁所需的I/O代價為COSTπ。為了評價滾動合并的延遲插入的效果，定義M=從C0合并到C1的平均條目數(shù)Se=條目的字節(jié)大小Sp=硬盤頁的字節(jié)大小S0=C0的葉子層的大?。ㄒ哉鬃止?jié)為單位）S1=C1的葉子層的大?。ㄒ哉鬃止?jié)為單位）一個硬盤頁（通常就是一個結(jié)點(diǎn)的大?。┲兴臈l目的數(shù)目約為Sp/Se，那么滾動合并時一頁中來自于C0的條目約為S0/(S0+S1)。那么M就可以估計(jì)為：
COSTB?ins=COSTP(De+1)C?M=SpSe?S0S0+S1M=SpSe?S0S0+S1
當(dāng)C0相對于C1的大小越大時，參數(shù)M也就越大。對于一次插入來說，LSM-tree在插入C0之后，滾動合并時需要讀進(jìn)C1的葉子結(jié)點(diǎn)，再寫回C1。由于滾動合并是批量插入C0的條目的，所以一次插入的代價是滾動合并代價的1/M。
所以LSM-tree的插入代價：COSTLSM?ins=2?COSTπ/MCOSTLSM?ins=2?COSTπ/M
將B-tree與LSM-tree的插入代價相比，即可得到：COSTLSM?insCOSTB?ins=2M(De+1)?COSTπCOSTP=K1M?COSTπ
COSTLSM?insCOSTB?ins=2M(De+1)?COSTπCOSTP=K1M?COSTπOSTLSM?insCOSTB?ins=2M(De+1)?COSTπCOSTP=K1M?COSTπCOSTP
1=2De+1
在實(shí)際應(yīng)用中說，K1接近于一個常數(shù)。所以LSM-tree與B-tree之比取決于M和COSTπ/COSTP。由于C1的多頁塊在硬盤中是連續(xù)存儲的，COSTπ一般會比COSTP來得小，故公式的大小其實(shí)取決于M。當(dāng)一頁中包含的條目數(shù)較多，C0的規(guī)模與C1差距不大時，LSM-tree在數(shù)據(jù)插入上是優(yōu)于B-tree的。
代價與數(shù)據(jù)溫度
從另一個角度看，B-tree往往限制在硬盤或內(nèi)存中，而LSM-tree則是跨越硬盤和內(nèi)存實(shí)現(xiàn)數(shù)據(jù)存取的優(yōu)化。假設(shè)有一個應(yīng)用程序使用B-tree有S兆字節(jié)數(shù)據(jù)存儲（假設(shè)不變），并需要每秒隨機(jī)訪問硬盤中的數(shù)據(jù)H次。那么應(yīng)用程序使用硬盤臂的代價就是H?COSTB-ins，使用硬盤進(jìn)行存儲的代價就是S?COSTd。在應(yīng)用程序剛開始運(yùn)行的時候，主要是加載應(yīng)用程序的數(shù)據(jù)等初始化動作，這時隨機(jī)訪問硬盤的次數(shù)較少，H相當(dāng)小，這時應(yīng)用程序的開銷主要是硬盤存儲數(shù)據(jù)的開銷，即是S?COSTd。隨著程序的不斷運(yùn)行，應(yīng)用程序內(nèi)的業(yè)務(wù)邏輯會需要訪問之前存儲的數(shù)據(jù)，隨機(jī)訪問硬盤的次數(shù)就會越來越大，H也就越來越大，隨機(jī)訪問的代價就無法忽略了。具體來說，就是S?COSTd>H?COSTB-ins。應(yīng)用程序的開銷代價就變?yōu)镠?COSTP。隨機(jī)訪問的不斷增加會使得硬盤磁盤臂的功率逐漸達(dá)到最大，但在訪問硬盤的代價小于使用內(nèi)存緩存（即H?COSTB-insS?COSTm時，將應(yīng)用程序存儲數(shù)據(jù)的B-tree全部緩存到內(nèi)存中，可以使得應(yīng)用程序的開銷代價減小，這樣應(yīng)用程序的開銷代價就是S?COSTm。綜上所述，可以看出應(yīng)用程序在兩個地方發(fā)生的轉(zhuǎn)折，一個是在隨機(jī)訪問的代價與存儲的代價相等時，即
d=H?COSTB?insHS=COSTdCOSTB?ins=COSTdCOSTp(De+1)
另一個是在隨機(jī)訪問的代價與緩存的代價相等時，即
STp(De+1)
由此，將H/S定義為數(shù)據(jù)的溫度，將兩個轉(zhuǎn)折點(diǎn)之間的區(qū)域稱溫?cái)?shù)據(jù)，兩端的區(qū)域分別稱為冷數(shù)據(jù)和熱數(shù)據(jù)，同理可得使用LSM-tree存儲S兆字節(jié)時，代價也會在兩個地方發(fā)生轉(zhuǎn)折。
通常來說，De+1通常大于2，M大于1，并且隨著H的增加，De+1和M都會不斷變大。所以LSM-tree的兩個轉(zhuǎn)折點(diǎn)均要后于B-tree的轉(zhuǎn)折點(diǎn)，而且LSM-tree的第二個轉(zhuǎn)折點(diǎn)要遠(yuǎn)遠(yuǎn)在B-tree第二個轉(zhuǎn)折點(diǎn)之后。應(yīng)用程序的總體代價COSTTOT隨H/S變化如下圖所示：
冷數(shù)據(jù)區(qū)域的代價由硬盤的存儲代價決定，不大能反映數(shù)據(jù)結(jié)構(gòu)和算法的好壞。但越遲走出冷數(shù)據(jù)就越能反映對硬盤的利用率。熱數(shù)據(jù)區(qū)域的代價主要集中在內(nèi)存存儲的代價上，同樣也不大能反映數(shù)據(jù)結(jié)構(gòu)和算法的好壞。但越遲進(jìn)入就越能反映對內(nèi)存的利用率。綜合來看，LSM-tree的代價曲線在B-tree之下，可見LSM-tree對硬盤和內(nèi)存的利用率都比B-tree要高。這主要是因?yàn)閮牲c(diǎn)：
1. 滾動合并時批量寫入新插入的數(shù)據(jù)，平攤單個條目插入的開銷；
2. C1的各層結(jié)點(diǎn)存儲在多頁塊中，合并時順序讀寫多頁塊，減小磁盤臂的移動。
在熱數(shù)據(jù)區(qū)域，無論是B-tree還是LSM-tree都將數(shù)據(jù)全部讀到內(nèi)存中，LSM-tree主要是增大C0的規(guī)模，使之與C1相當(dāng)。此時的問題內(nèi)存的開銷就越來越大。由于內(nèi)存的空間畢竟是有限的，一味地增加C0是不可取的。若減少C0的規(guī)模，由M的估計(jì)公式，M可能會下降。其實(shí)當(dāng)某些比較大的條目需要不只一頁來存放的時侯，M也可能會下降。這種情況下，從C0到C1的每次滾動合并需要從C1讀入和寫出多個頁或多頁塊。特別地，當(dāng)M<K1COSTπCOSTP時，多頁塊的讀寫優(yōu)勢將蕩然無存，B樹的插入性能將優(yōu)于LSM-tree。為了避免M小于1，就又不得不增加C0的規(guī)模。一個解決方法就是在日益增大的C1和有空間上限的C0之間加入一個C做為C0和C1的緩沖。這時LSM-tree就由三個部分（C1、C和C0）組成。這種LSM-tree稱為多部件的LSM-tree。
多部件的LSM-tree
在數(shù)據(jù)不斷增加的情況下，即使在C1和C0之間增加上一個C，C的規(guī)模也會不斷增長。當(dāng)C像過去C1那么大時，就需要在C和C0之間再增加一個C。以此類推，硬盤中的C樹將會越來越多。如下圖所示：
通常，一個多部件的LSM-tree由大小依次遞增的C0，C1，C2，...，CK-1和CK組成，C0常駐內(nèi)存之中，可以是鍵值索引的數(shù)據(jù)結(jié)構(gòu)。而C1~CK則存儲于硬盤之中，但其經(jīng)常訪問的頁會被緩存于內(nèi)存之中，它們的結(jié)構(gòu)都是索引樹。在數(shù)據(jù)不斷插入的過程中，當(dāng)較小的Ci-1的規(guī)模超過某一閾值時，相鄰的兩個部件Ci-1和Ci會進(jìn)行滾動合并，從較小的Ci-1轉(zhuǎn)移條目至較大的Ci中。各個相鄰部件Ci-1和Ci的滾動合并是異步的。也就是說，一個條目會插入到C0中，之后經(jīng)過不斷的異步滾動合并過程，最終合并至CK中。由于各個相鄰部件Ci-1和Ci的滾動合并是異步的，但當(dāng)對其中的數(shù)據(jù)進(jìn)行訪問時，常常發(fā)生一些并發(fā)性問題。例如當(dāng)進(jìn)行精確檢索或者加載多頁塊至內(nèi)存時，Ci里的一個節(jié)點(diǎn)會被讀入內(nèi)存；當(dāng)進(jìn)行范圍檢索或滾動合并時，Ci里的多頁塊會被讀入內(nèi)存中。這些情況下，查找數(shù)據(jù)時Ci里的所有未被鎖住的結(jié)點(diǎn)都可以被訪問，并會定位被讀入內(nèi)存的結(jié)點(diǎn)。即使結(jié)點(diǎn)正在進(jìn)行滾動合并，結(jié)點(diǎn)也可以被訪問。顯然，這時結(jié)點(diǎn)上的數(shù)據(jù)可能是不完整的?；谶@些考慮，訪問LSM-tree必須遵循下列規(guī)則：
1.? ?當(dāng)硬盤中的相鄰部件進(jìn)行滾動合并的時候，當(dāng)前參與合并的結(jié)點(diǎn)不能被查找；
2.? ?當(dāng)C0和C1進(jìn)行滾動合并的時候，當(dāng)前參與合并的C0的結(jié)點(diǎn)周邊不能被查找和插入；
3.? ?在Ci-1和Ci與Ci和Ci+1同時進(jìn)行滾動合并時，Ci-1與Ci滾動合并的游標(biāo)有時會超過Ci和Ci+1滾動合并的游標(biāo)。
為了避免對硬盤里的部件進(jìn)行存取時產(chǎn)生的物理沖突，LSM-tree設(shè)置了以結(jié)點(diǎn)為單位的鎖。在進(jìn)行滾動合并時，正在合并的結(jié)點(diǎn)會在寫模式下被鎖住，直到有來自較大部件的結(jié)點(diǎn)被合并才被釋放。在進(jìn)行查找時，正在被讀取的結(jié)點(diǎn)會在讀模式下被鎖住，讀取完畢后，鎖即被釋放。與C0和C1的滾動合并相比，硬盤內(nèi)的相鄰部件Ci-1和Ci之間的滾動合并多了一個清空塊和填充塊。這是因?yàn)镃i-1和Ci都存儲在硬盤之中，合并時需要先將Ci-1和Ci的清空塊和填充塊存入內(nèi)存，合并的過程與C0和C1的相同，但Ci-1不會將所有的條目都拿去合并，而是會保留一部分條目（例如新插入的那部分條目）到Ci-1的填充塊。如下圖所示：
當(dāng)前正在進(jìn)行滾動合并的結(jié)點(diǎn)被加鎖（紅圈圈住的點(diǎn)），寫保護(hù)。藍(lán)色的點(diǎn)表示游標(biāo)，綠色的點(diǎn)表示游標(biāo)未到達(dá)的結(jié)點(diǎn)，樹上折線表示從樹根到游標(biāo)的路徑
查找、刪除和修改
在LSM-tree樹進(jìn)行查找時，為了保證LSM-tree上的所有條目都被檢查。首先要搜索C0，再搜索C1，進(jìn)而搜索C2，...，CK-1和CK。即使硬盤中的部件C1，C2，...，CK-1和CK的結(jié)構(gòu)都是B-tree，這也將耗費(fèi)一些時間。但在實(shí)際的應(yīng)用中，總可以將搜索限制在前幾個的部件的搜索上。試想新條目插入時首先插入至C0中，然后通過各相鄰部件Ci，和Ci+1之間的滾動合并，逐步轉(zhuǎn)移到更大的部件中。在滾動合并時，如果將最近τ時間內(nèi)被訪問的條目保留下來，而將其它條目用于合并，那么經(jīng)常被訪問的那些數(shù)據(jù)就會被依次保存在C0，C1，...，CK-1和CK中。也就是說，我們可以簡單的認(rèn)為，C0保存的是最近τ時間內(nèi)被訪問的條目，C1保存的是除了C0保存的數(shù)據(jù)外，最近2τ時間內(nèi)被訪問的條目，C2保存的是除了C0和C1保存的數(shù)據(jù)外，最近3τ時間內(nèi)被訪問的條目。依此可推廣到CK-1。而最后的部件CK保存的是最近Kτ之前的條目。這樣凡是在最近τ時間內(nèi)被執(zhí)行的事務(wù)都不需要與硬盤進(jìn)行I/O交換，可以直接在內(nèi)存中找到數(shù)據(jù)。
LSM-tree的優(yōu)勢在于其能推遲寫回硬盤的時間，進(jìn)而達(dá)到批量地插入數(shù)據(jù)的目的。為了更高效地利用LSM-tree的插入優(yōu)勢，刪除操作被設(shè)計(jì)為通過插入操作來執(zhí)行。當(dāng)C0所索引的一個條目被刪除時，首先在C0上查找該條目所對應(yīng)的索引是否存在，若不存在，就建立一個索引。然后在該索引鍵值的位置上設(shè)置刪除條目（delete node entry）。刪除條目的意義僅在于通知所有訪問該索引的操作，“此索引鍵值所索引的條目已經(jīng)被刪除了”。在后續(xù)的滾動合并中，凡是在較大的部件中碰到的與該索引鍵值相同的條目都將被刪除。此外，當(dāng)在LSM-tree中查找刪除的條目時，如果碰到這種刪除條目，就會直接返回未找到。對于條目的修改，依仗LSM-tree的插入優(yōu)勢，可以先插入一個對應(yīng)的刪除條目，待刪除條目經(jīng)滾動合并離開C0后，再在上插入該條目的新值。崩潰恢復(fù)在新條目插入到C0后，當(dāng)C0與C1進(jìn)行滾動合并時，某些條目將從C0轉(zhuǎn)移到更大的部件中。由于滾動合并發(fā)生在內(nèi)存緩存的多頁塊中，所以只有當(dāng)條目真正寫入硬盤時，滾動合并的成果才會真正生效。然而滾動合并時可能就會發(fā)生系統(tǒng)故障，進(jìn)而使得內(nèi)存數(shù)據(jù)丟失。為了能有效地進(jìn)行系統(tǒng)恢復(fù)，在LSM-tree的日常使用中，需要記錄一些用以恢復(fù)數(shù)據(jù)的日志。然而與以往數(shù)據(jù)庫中的日志不同的是，日志中只需要要記錄數(shù)據(jù)插入的事務(wù)。簡單地說，這些日志只包含了被插入數(shù)據(jù)的行的號碼及插入的域和值。LSM-tree在記日志時設(shè)置檢查點(diǎn)（checkpoint）以恢復(fù)某一時刻的LSM-tree。當(dāng)需要在時刻T0設(shè)置檢查點(diǎn)時：
1.? 完成所有部件的當(dāng)前合并，這樣結(jié)點(diǎn)上的鎖就會被釋放；
2.???[endif]將所有新條目的插入操作以及滾動合并推遲至檢查點(diǎn)設(shè)置完成之后；
3.???[endif]將C0寫入硬盤中的一個已知的位置；此后對C0的插入操作可以開始，但是合并操作還要繼續(xù)等待；
4.???[endif]將硬盤中的所有部件（C1~CK）在內(nèi)存中緩存的結(jié)點(diǎn)寫入硬盤；
5.???[endif]向日志中寫入一條特殊的檢查點(diǎn)日志。
檢查點(diǎn)日志的內(nèi)容包括：
1.???[endif]T0時刻最后一個插入的已索引的行的日志序列號（Log Sequence Number，LSN0）；
2.???[endif]硬盤中的所有部件的根在硬盤中的地址；
[if !supportLists]3.???[endif]各個部件的合并游標(biāo)；
[if !supportLists]4.???[endif]新多頁塊動態(tài)分配的當(dāng)前信息。在以后的恢復(fù)中，硬盤存儲的動態(tài)分配算法將使用此信息判別哪些多頁塊是可用的。
一旦檢查點(diǎn)的信息設(shè)置完畢，就可以開始執(zhí)行被推遲的新條目的插入操作了。由于后續(xù)合并操作中向硬盤寫入多頁塊時，會將信息寫入硬盤中的新位置，所以檢查點(diǎn)的信息不會被消除。只有當(dāng)后續(xù)檢查點(diǎn)使得過期的多頁塊作廢時，檢查點(diǎn)的信息才會被廢棄。
恢復(fù)
當(dāng)系統(tǒng)崩潰后重啟進(jìn)行恢復(fù)時，需要進(jìn)行如下操作：
1.? 在日志中定位一個檢查點(diǎn)；
2.? 將之前寫入硬盤的C0和其它部件在內(nèi)存中緩存的多頁塊加載到內(nèi)存中；
3.? 將日志中在LSN0之后的部分讀入內(nèi)存，執(zhí)行其中索引條目的插入操作；
4.? 讀取檢查點(diǎn)日志中硬盤部件（C1~CK）的根的位置和合并游標(biāo)，啟動滾動合并，覆蓋檢查點(diǎn)之后的多頁塊；
5. 當(dāng)檢查點(diǎn)之后的所有新索引條目都已插入至LSM-tree且被索引后，恢復(fù)即完成。
缺點(diǎn)：時間可能會比較長。內(nèi)存中數(shù)據(jù)很快寫入硬盤。相鄰的部件滾動合并，新產(chǎn)生的結(jié)點(diǎn)將會寫入到硬盤中的新位置。這樣在將合并產(chǎn)生的結(jié)點(diǎn)寫入硬盤時，上層結(jié)點(diǎn)中指向該結(jié)點(diǎn)的指針需要更新為結(jié)點(diǎn)的新位置。當(dāng)正在進(jìn)行滾動合并，卻臨時需要設(shè)置檢查點(diǎn)時，加載進(jìn)內(nèi)存的多頁塊和目錄結(jié)點(diǎn)都會寫入到硬盤中新的位置。這樣，在高層的目錄結(jié)點(diǎn)中指向這些結(jié)點(diǎn)的指針同樣需要立即更新為硬盤中的新地址。在恢復(fù)的過程中需要注意的是目錄結(jié)點(diǎn)的更新。
更進(jìn)一步，當(dāng)使用檢查點(diǎn)進(jìn)行恢復(fù)時，滾動合并所需的所有的多頁塊都會從硬盤重新讀回內(nèi)存，由于所有的多頁塊的新位置較之設(shè)置檢查點(diǎn)時的舊位置都發(fā)生了改變，這樣所有目錄結(jié)點(diǎn)的指針都需要更新。這聽起來似乎是一大筆性能開銷，但這些多頁塊其實(shí)都已加載到內(nèi)存里了，所以沒有I/O開銷。若要使得恢復(fù)的時間不超過幾分鐘，那么可以每隔幾分鐘的I/O操作就設(shè)置一次檢查點(diǎn)。
小結(jié)
日志結(jié)構(gòu)的合并樹（LSM-tree）是一種基于硬盤的數(shù)據(jù)結(jié)構(gòu)，與B-tree相比，減少硬盤開銷，寫快，查慢。
Bigtable在提供Tablet服務(wù)時，使用GFS來存儲日志和SSTable，GFS的設(shè)計(jì)初衷就是希望通過添加新數(shù)據(jù)的方式而不是通過重寫舊數(shù)據(jù)的方式來修改文件。而LSM-tree通過滾動合并和多頁塊的方法推遲和批量進(jìn)行索引更新，內(nèi)存存儲常用，硬盤存儲不常用數(shù)據(jù)減少查找、存儲代價。
