HBase/TiDB都在用的數(shù)據(jù)結(jié)構(gòu)：LSM Tree溪王，不得了解一下莹菱？

LSM Tree（Log-structured merge-tree）廣泛應(yīng)用在HBase宾袜，TiDB等諸多數(shù)據(jù)庫和存儲引擎上互艾，我們先來看一下它的一些應(yīng)用：

參考資料【4】

這么牛X的名單纫普，你不想了解下LSM Tree嗎？裝X之前节视，我們先來了解一些基本概念假栓。

設(shè)計數(shù)據(jù)存儲系統(tǒng)可能需要考慮的一些問題有：ACID匾荆，RUM（Read,Write,Memory）拌蜘。

ACID

ACID 相信小伙伴都被面試官問過简卧，我想簡單討論的一點是：如何持久化數(shù)據(jù) 才能保證數(shù)據(jù)寫入的事務(wù)性和讀寫性能烤芦？

事務(wù)性可簡單理解為：1.數(shù)據(jù)必須持久化。2.一次數(shù)據(jù)的寫入返回給用戶寫入成功就一定成功铜涉，失敗就一定失敗遂唧。
讀寫性能可簡單理解為：一次讀或一次寫需要的IO次數(shù)盖彭，因為訪問速率：CPU>>內(nèi)存>>SSD/磁盤事甜。

對于單機存儲滔韵，最簡單的方式當(dāng)然是：寫一條就持久化一條陪蜻，讀一條就遍歷一遍所有數(shù)據(jù)贱鼻，然后返回。當(dāng)然沒人這么干症昏，在內(nèi)存中我們都還知道用個HashMap呢父丰。

拿Mysql InnoDB舉例子：讀性能體現(xiàn)在數(shù)據(jù)的索引在磁盤上主要用B+樹來保證。寫性能體現(xiàn)在運用 WAL機制 來避免每次寫都去更新B+樹上的全量索引和數(shù)據(jù)內(nèi)容攘烛，而是通過redo log記錄下來每次寫的增量內(nèi)容坟漱，順序?qū)edo log寫入磁盤更哄。同時在內(nèi)存中記錄下來本次寫入應(yīng)該在B+樹上更新的臟頁數(shù)據(jù)，然后在一定條件下觸發(fā)臟頁的刷盤觅捆。

redo log是數(shù)據(jù)增刪改的實時增量數(shù)據(jù)惠拭，順序?qū)懭氡ＷC了寫性能和事務(wù)性。磁盤上的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定理。如果想得到三者中的兩者性能豆巨，必須以犧牲第三者的性能為代價剩辟。衡量這三者的性能指標(biāo)有：讀放大、寫放大往扔、空間放大贩猎。

讀放大：是指每次查詢讀取磁盤的次數(shù)。如果每次查詢需要查詢5個page (或block)萍膛，則讀放大是5.

寫放大：是指數(shù)據(jù)寫入存儲設(shè)備的量和數(shù)據(jù)寫入數(shù)據(jù)庫的量之比吭服。如果用戶寫入數(shù)據(jù)庫的大小是10MB，而實際寫入磁盤的大小是30MB蝗罗，則寫放大是3.另外SSD的寫入次數(shù)是有限的艇棕，寫放大會減少SSD的壽命。

空間放大：是指數(shù)據(jù)在存儲設(shè)備的總量和數(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)。當(dāng)時的背景是：為一張數(shù)據(jù)增長很快的歷史數(shù)據(jù)表設(shè)計一種存儲結(jié)構(gòu)过吻，使得它能夠解決：在內(nèi)存不足进泼，磁盤隨機IO太慢下的嚴(yán)重寫入性能問題。

如果我們先后修改兩條數(shù)據(jù)纤虽，那么在臟數(shù)據(jù)塊落盤時乳绕，不是一條條隨機寫入，而是以一個臟塊批量落盤時逼纸，就能解決 B+樹中“全量數(shù)據(jù)的隨機寫入” 問題了洋措。

參考資料【3】

所以大佬設(shè)計了這么一種結(jié)構(gòu)：

An LSM-tree of K+1 components

Ck tree是一個有序的樹狀結(jié)構(gòu)，數(shù)據(jù)的寫入流轉(zhuǎn)從C0 tree 內(nèi)存開始杰刽，不斷被合并到磁盤上的更大容量的Ck tree上菠发。這種方式寫入是順序?qū)懙耐趼耍鰟h改操作都是append。
這樣一次I/O可以進(jìn)行多條數(shù)據(jù)的寫入滓鸠，從而充分利用每一次寫I/O雁乡。

merge所做的事情有：當(dāng)上一棵樹容量不足時，1.將上棵樹中要刪除的數(shù)據(jù)刪除掉糜俗，進(jìn)行GC回收蔗怠。2.合并數(shù)據(jù)的最新版本，使得Ck tree不會過度膨脹吩跋。

這種初始結(jié)構(gòu)存在的問題有：隨著數(shù)據(jù)量的增大，merge費勁渔工，沒有好的索引結(jié)構(gòu)锌钮，讀放大嚴(yán)重。現(xiàn)代的LSM Tree結(jié)構(gòu)如下：

參考資料【4】

MemTable：是LSM Tree在內(nèi)存中還未刷盤的寫入數(shù)據(jù)引矩，這里面的數(shù)據(jù)可以修改梁丘。是一個有序的樹狀結(jié)構(gòu)，如RocksDB中的跳表旺韭。

SSTable（Sorted String Table）：是一個鍵是有序的氛谜，存儲字符串形式鍵值對的磁盤文件。當(dāng)SSTable太大時区端，可以將其劃分為多個block值漫；我們需要通過下圖中的Index 記錄下來每個block的起始位置，那么就可以構(gòu)建每個SSTable的稀疏索引织盼。這樣在讀SSTable前杨何，通過Index結(jié)構(gòu)就知道要讀取的數(shù)據(jù)塊磁盤位置了。

LSM Tree讀數(shù)據(jù)

讀數(shù)據(jù) 包括點讀和范圍讀沥邻，我們分開討論危虱。假設(shè)LSM Tree中的key為[0-99]，

點讀：是指準(zhǔn)確地取出一條數(shù)據(jù)唐全，如get(23),則其示意圖為：

參考資料【4】

按照圖中標(biāo)示的順序埃跷，會先讀取內(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ù)不可以修改赦颇。是當(dāng)MemTable到達(dá)一定量需要刷到SSTable時，由MemTable完整copy下來的赴涵。這樣可避免從MemTable直接刷到SSTable時的并發(fā)競爭問題媒怯。

LSM Tree寫數(shù)據(jù)

在LSM Tree寫入數(shù)據(jù)時，我們把ReadOnly MemTable畫上髓窜，示意圖如下：

當(dāng)有寫請求時扇苞，數(shù)據(jù)會先寫入MemTable,同時寫入 WAL Log；當(dāng)MemTable空間不足時寄纵，觸發(fā)ReadOnly MemTable copy,同時寫入WAL Log鳖敷；然后刷新到磁盤Level0的SSTable中。當(dāng)?shù)蛯覵STable空間不足時程拭，不斷通過Compaction和高層SSTable進(jìn)行Merge定踱。

LSM Tree合并策略

LSM Tree有兩種合并策略，Tiering 和 Leveling恃鞋。我們看圖說話：

Tiering的特點是：每層可能有N個重疊的sorted runs崖媚，當(dāng)上一層的sorted runs 要merge下來時，不會和當(dāng)前層重疊的sorted runs馬上合并恤浪，而是等到當(dāng)前層空間不足時畅哑，才會合并，然后再merge到下一層水由。

Tiering這種策略可以減小寫放大荠呐，但是以讀放大和空間放大為代價。

Leveling的特點是：每層只有一個sorted run绷杜，當(dāng)上一層的sorted run 要merge下來時直秆，會馬上和當(dāng)前層的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ù)較多弧关，讀放大嚴(yán)重盅安。

布隆過濾器
對于精確查詢唤锉，hash的時間復(fù)雜度為 O(1)，那么可以通過布隆過濾器來優(yōu)化别瞭。我們只需要查詢時先過一遍布隆過濾器窿祥，就能排除掉一定不存在的key了，避免不必要的IO查詢蝙寨。

布隆過濾器：是通過hash算法來判斷一個key是否存在于某個集合中晒衩，布隆過濾器通常是一個bit數(shù)組，用針對一個key多次hash算法確定的多個bit值來表示key是否存在墙歪。多個bit值全為1听系，則表示key可能存在，否則不存在虹菲。好處是多個bit值通常比直接存儲一個存在的key占用空間小跛锌，省內(nèi)存。

分層布隆過濾器
上述布隆過濾器是假設(shè)每層數(shù)據(jù)都使用相同的布隆過濾器來進(jìn)行過濾届惋，而數(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é)合兩種合并策略，使曲線整體下移吁系。
Lazy Leveling
參考資料【3】中Dostoevsky采用了一種Lazy Leveling的策略：它是對低層數(shù)據(jù)采用Tiering合并策略德召，對高層數(shù)據(jù)采用Leveling合并策略白魂。從而權(quán)衡了讀寫性能。