LSM Tree（Log-structured merge-tree）廣泛應用在HBase，TiDB等諸多數(shù)據(jù)庫和存儲引擎上，我們先來看一下它的一些應用：
這么牛X的名單，你不想了解下LSM Tree嗎？裝X之前，我們先來了解一些基本概念。 設計數(shù)據(jù)存儲系統(tǒng)可能需要考慮的一些問題有：ACID，RUM（Read,Write,Memory）。
ACID
ACID 相信小伙伴都被面試官問過，我想簡單討論的一點是：如何 持久化數(shù)據(jù) 才能保證數(shù)據(jù)寫入的 事務性 和 讀寫性能？事務性可簡單理解為：1.數(shù)據(jù)必須持久化。2.一次數(shù)據(jù)的寫入返回給用戶 寫入成功就一定成功，失敗就一定失敗。 讀寫性能可簡單理解為：一次讀 或 一次寫 需要的IO次數(shù)，因為訪問速率：CPU>>內(nèi)存>>SSD/磁盤。 對于單機存儲，最簡單的方式當然是：寫一條就持久化一條，讀一條就遍歷一遍所有數(shù)據(jù)，然后返回。當然沒人這么干，在內(nèi)存中我們都還知道用個HashMap呢。 讀性能體現(xiàn)在數(shù)據(jù)的索引在磁盤上主要用B+樹來保證。 寫性能體現(xiàn)在運用 WAL機制 來避免每次寫都去更新B+樹上的全量索引和數(shù)據(jù)內(nèi)容，而是通過redo log記錄下來每次寫的增量內(nèi)容，順序?qū)edo log寫入磁盤。同時在內(nèi)存中記錄下來本次寫入應該在B+樹上更新的臟頁數(shù)據(jù)，然后在一定條件下觸發(fā)臟頁的刷盤。 redo log是數(shù)據(jù)增刪改的實時增量數(shù)據(jù)，順序?qū)懭氡ＷC了寫性能和事務性。磁盤上的B+樹是數(shù)據(jù)增刪改的全量數(shù)據(jù)，通過定時臟頁刷盤保證這份數(shù)據(jù)的完整性。 這里的問題是：雖然通過WAL機制，提高了寫入性能，但是仍然避免不了臟頁數(shù)據(jù)定時刷盤的隨機IO寫入。 因為數(shù)據(jù)在磁盤上是以block為單位存儲的（比如4K，16K）,假如你更新了Order表一條數(shù)據(jù)，又更新了Product表一條數(shù)據(jù)，臟頁刷盤時，這兩條數(shù)據(jù)在磁盤上的block位置可能差了十萬八千里，就變成了隨機IO的寫入。 參考資料【3】
RUM
RUM（Read,Write,Memory）類似分布式領(lǐng)域的CAP定理。如果想得到三者中的兩者性能，必須以犧牲第三者的性能為代價。衡量這三者的性能指標有：讀放大、寫放大、空間放大。 讀放大 ：是指每次查詢讀取磁盤的次數(shù)。如果每次查詢需要查詢5個page (或block)，則讀放大是5.寫放大 ：是指數(shù)據(jù)寫入存儲設備的量和數(shù)據(jù)寫入數(shù)據(jù)庫的量之比。如果用戶寫入數(shù)據(jù)庫的大小是10MB，而實際寫入磁盤的大小是30MB，則寫放大是3.另外SSD的寫入次數(shù)是有限的，寫放大會減少SSD的壽命。空間放大 ：是指數(shù)據(jù)在存儲設備的總量和數(shù)據(jù)在數(shù)據(jù)庫的總量之比。如果用戶往數(shù)據(jù)庫上存10MB，而數(shù)據(jù)庫實際在磁盤上用了100MB去存，則空間放大就是10.通常，數(shù)據(jù)結(jié)構(gòu)可以最多優(yōu)化這其中的兩者，如B+樹有更少的讀放大，LSM Tree有更少的寫放大。 下面我們將介紹LSM Tree的結(jié)構(gòu)，它是如何解決 B+樹中“全量數(shù)據(jù)的隨機寫入” 問題的；在RUM問題上，又該如何優(yōu)化LSM Tree。
為什么要有LSM Tree
LSM Tree（Log-structured merge-tree）起源于1996年的一篇論文：The log-structured merge-tree (LSM-tree)。 當時的背景是：為一張數(shù)據(jù)增長很快的歷史數(shù)據(jù)表設計一種存儲結(jié)構(gòu)，使得它能夠解決：在內(nèi)存不足，磁盤隨機IO太慢下的嚴重寫入性能問題。 如果我們先后修改兩條數(shù)據(jù)，那么在臟數(shù)據(jù)塊落盤時，不是一條條隨機寫入，而是以一個臟塊批量落盤時，就能解決 B+樹中“全量數(shù)據(jù)的隨機寫入” 問題了。
Ck tree是一個有序的樹狀結(jié)構(gòu)，數(shù)據(jù)的寫入流轉(zhuǎn)從C0 tree 內(nèi)存開始，不斷被合并到磁盤上的更大容量的Ck tree上。這種方式寫入是順序?qū)懙模鰟h改操作都是append。這樣一次I/O可以進行多條數(shù)據(jù)的寫入，從而充分利用每一次寫I/O。 merge所做的事情有：當上一棵樹容量不足時，1.將上棵樹中要刪除的數(shù)據(jù)刪除掉，進行GC回收。2.合并數(shù)據(jù)的最新版本，使得Ck tree不會過度膨脹。 這種初始結(jié)構(gòu)存在的問題有：隨著數(shù)據(jù)量的增大，merge費勁，沒有好的索引結(jié)構(gòu)，讀放大嚴重?，F(xiàn)代的LSM Tree結(jié)構(gòu)如下：
MemTable ：是LSM Tree在內(nèi)存中還未刷盤的寫入數(shù)據(jù)，這里面的數(shù)據(jù)可以修改。是一個有序的樹狀結(jié)構(gòu)，如RocksDB中的跳表。SSTable（Sorted String Table） ：是一個鍵是有序的，存儲字符串形式鍵值對的磁盤文件。當SSTable太大時，可以將其劃分為多個block；我們需要通過 下圖中的Index 記錄下來每個block的起始位置，那么就可以構(gòu)建每個SSTable的稀疏索引。這樣在讀SSTable前，通過Index結(jié)構(gòu)就知道要讀取的數(shù)據(jù)塊磁盤位置了。
LSM Tree讀數(shù)據(jù)
讀數(shù)據(jù) 包括點讀和范圍讀，我們分開討論。假設LSM Tree中的key為[0-99]， 點讀 ：是指準確地取出一條數(shù)據(jù)，如get(23),則其示意圖為：
按照圖中標示的順序，會先讀取內(nèi)存，在從Level0依次往高層讀取，直到找到key=23的數(shù)據(jù)。 范圍讀 ：是指讀取一個范圍內(nèi)的數(shù)據(jù)，如讀取[23-40]內(nèi)的所有數(shù)據(jù)（ select * from t where key >= 23 && key <=40),則需要做的是在每一層SSTable找到這個范圍內(nèi)的第一個block,然后遍歷block塊的數(shù)據(jù)，直到不符合范圍條件。 參考資料【4】
“ ReadOnly MemTable ：如RocksDB，在MemTable 和 Level0數(shù)據(jù)之間還有一個內(nèi)存的ReadOnly MemTable結(jié)構(gòu)。它是LSM Tree在內(nèi)存中還未刷盤的寫入數(shù)據(jù)，這里面的數(shù)據(jù)不可以修改。是當MemTable到達一定量需要刷到SSTable時，由MemTable完整copy下來的。這樣可避免從MemTable直接刷到SSTable時的并發(fā)競爭問題。
LSM Tree寫數(shù)據(jù)
在LSM Tree寫入數(shù)據(jù)時，我們把ReadOnly MemTable畫上，示意圖如下：
當有寫請求時，數(shù)據(jù)會先寫入MemTable,同時寫入 WAL Log；當MemTable空間不足時，觸發(fā)ReadOnly MemTable copy,同時寫入WAL Log；然后刷新到磁盤Level0的SSTable中。當?shù)蛯覵STable空間不足時，不斷通過Compaction和高層SSTable進行Merge。 LSM Tree合并策略
LSM Tree有兩種合并策略，Tiering 和 Leveling。我們看圖說話：
Tiering 的特點是：每層可能有N個重疊的sorted runs，當上一層的sorted runs 要merge下來時，不會和當前層重疊的sorted runs馬上合并，而是等到當前層空間不足時，才會合并，然后再merge到下一層。Tiering這種策略可以減小寫放大，但是以讀放大和空間放大為代價。 Leveling 的特點是：每層只有一個sorted run，當上一層的sorted run 要merge下來時，會馬上和當前層的sorted run合并。Leveling這種策略可以減小讀放大和空間放大，但以寫放大為代價。
LSM Tree的優(yōu)化
參考資料[2-4]中的大佬們提到了不少優(yōu)化方式，我這里從讀，合并方面簡要總結(jié)下LSM Tree的優(yōu)化。
點讀的優(yōu)化
盡管我們可以通過SSTable的內(nèi)存block稀疏索引結(jié)構(gòu)簡單判斷key是否可能存在于block中，但如上get(23)，如果level1讀不到，仍需要往下讀level2,level3。（因為數(shù)據(jù)是按照增刪改的時間順序一層層往下落盤的，如果一個key不存在低level中，可能存在于更早的高level中）。這樣的點讀IO次數(shù)較多，讀放大嚴重。 對于精確查詢，hash的時間復雜度為 O(1)，那么可以通過布隆過濾器來優(yōu)化。我們只需要查詢時先過一遍布隆過濾器，就能排除掉一定不存在的key了，避免不必要的IO查詢。 “ 布隆過濾器：是通過hash算法來判斷一個key是否存在于某個集合中，布隆過濾器通常是一個bit數(shù)組，用針對一個key多次hash算法確定的多個bit值來表示key是否存在。多個bit值全為1，則表示key可能存在，否則不存在。好處是多個bit值通常比直接存儲一個存在的key占用空間小，省內(nèi)存。上述布隆過濾器是假設每層數(shù)據(jù)都使用相同的布隆過濾器來進行過濾，而數(shù)據(jù)隨著層數(shù)的增加通常是指數(shù)級增長的，如果使低層的數(shù)據(jù)使用更精確的布隆過濾器（所需bit數(shù)更多，但是精確度更高）,高層的數(shù)據(jù)使用稍微不那么精確的布隆過濾器，則整體點查的效率將提高。 參考資料【3】中Monkey做了上述優(yōu)化，即使隨著數(shù)據(jù)量和層數(shù)的增大，點查仍能保持在一個穩(wěn)定的時間內(nèi)。
范圍讀的優(yōu)化
Hash的不足就是無法支持范圍查詢索引，優(yōu)化方式有： 因為讀數(shù)據(jù)不存在競爭問題，可以并行讀每層的數(shù)據(jù)，縮短整體查詢時間，但是這種方式實際并沒有縮短IO次數(shù)。 前綴布隆過濾器是以key的前綴來Hash構(gòu)建布隆過濾器，而不是key本身的值。這樣可以起到過濾 like Monica* 這樣的查詢條件作用。RocksDB有做此優(yōu)化。
合并的優(yōu)化
上面提到了兩種合并策略Tiering 和 Leveling。Tiering可以減小寫放大，Leveling可以減小讀放大和空間放大。參考資料【3】中提到了數(shù)據(jù)庫所采用的合并策略走勢如下：
隨著數(shù)據(jù)量的增大，整條曲線會上移。優(yōu)化的重點在于：如何結(jié)合兩種合并策略，使曲線整體下移。 參考資料【3】中Dostoevsky采用了一種Lazy Leveling的策略：它是對低層數(shù)據(jù)采用Tiering合并策略，對高層數(shù)據(jù)采用Leveling合并策略。從而權(quán)衡了讀寫性能。
RUM的取舍
RUM的取舍和權(quán)衡類似于分布式領(lǐng)域的CAP，在特定的場景采用適合的優(yōu)化手段才能使整體性能最優(yōu)。參考資料【3】中的大佬還提到了Fluid Merge策略。233醬表示雖過了眼癮，但仍是個CRUD渣渣。 關(guān)于RUM的優(yōu)化，233醬最后放一張圖，希望對你我有所啟發(fā)。
后記
LSM Tree是這兩年一直聽到的名詞，但是一直沒有花時間了解它。233醬趁這次機會現(xiàn)學現(xiàn)賣，對其有了更深一步的了解。 對本文內(nèi)容感興趣的小伙伴可進一步閱讀參考資料，如果文中有錯誤或者不理解的地方也歡迎小伙伴們和我交流指正。
