HBase的LSM Tree是什么

發(fā)布時間：2021-12-09 11:48:26 來源：億速云閱讀：212 作者：iii 欄目：大數據

本篇內容介紹了“HBase的LSM Tree是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

ACID

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

事務性可簡單理解為：1.數據必須持久化。2.一次數據的寫入返回給用戶寫入成功就一定成功，失敗就一定失敗。

讀寫性能可簡單理解為：一次讀或一次寫需要的IO次數，因為訪問速率：CPU>>內存>>SSD/磁盤。

對于單機存儲，最簡單的方式當然是：寫一條就持久化一條，讀一條就遍歷一遍所有數據，然后返回。當然沒人這么干，在內存中我們都還知道用個HashMap呢。

拿Mysql InnoDB舉例子：

讀性能體現在數據的索引在磁盤上主要用B+樹來保證。

寫性能體現在運用 WAL機制 來避免每次寫都去更新B+樹上的全量索引和數據內容，而是通過redo log記錄下來每次寫的增量內容，順序將redo log寫入磁盤。同時在內存中記錄下來本次寫入應該在B+樹上更新的臟頁數據，然后在一定條件下觸發(fā)臟頁的刷盤。

redo log是數據增刪改的實時增量數據，順序寫入保證了寫性能和事務性。磁盤上的B+樹是數據增刪改的全量數據，通過定時臟頁刷盤保證這份數據的完整性。

這里的問題是：雖然通過WAL機制，提高了寫入性能，但是仍然避免不了臟頁數據定時刷盤的隨機IO寫入。

因為數據在磁盤上是以block為單位存儲的（比如4K，16K）,假如你更新了Order表一條數據，又更新了Product表一條數據，臟頁刷盤時，這兩條數據在磁盤上的block位置可能差了十萬八千里，就變成了隨機IO的寫入。

RUM

RUM（Read,Write,Memory）類似分布式領域的CAP定理。如果想得到三者中的兩者性能，必須以犧牲第三者的性能為代價。衡量這三者的性能指標有：讀放大、寫放大、空間放大。

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

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

空間放大：是指數據在存儲設備的總量和數據在數據庫的總量之比。如果用戶往數據庫上存10MB，而數據庫實際在磁盤上用了100MB去存，則空間放大就是10.

通常，數據結構可以最多優(yōu)化這其中的兩者，如B+樹有更少的讀放大，LSM Tree有更少的寫放大。

下面我們將介紹LSM Tree的結構，它是如何解決 B+樹中“全量數據的隨機寫入” 問題的；在RUM問題上，又該如何優(yōu)化LSM Tree。

為什么要有LSM Tree

LSM Tree（Log-structured merge-tree）起源于1996年的一篇論文： The log-structured merge-tree (LSM-tree) 。

當時的背景是：為一張數據增長很快的歷史數據表設計一種存儲結構，使得它能夠解決：在內存不足，磁盤隨機IO太慢下的嚴重寫入性能問題。

如果我們先后修改兩條數據，那么在臟數據塊落盤時，不是一條條隨機寫入，而是以一個臟塊批量落盤時，就能解決 B+樹中“全量數據的隨機寫入” 問題了。

HBase的LSM Tree是什么

所以大佬設計了這么一種結構：

HBase的LSM Tree是什么

Ck tree是一個有序的樹狀結構，數據的寫入流轉從C0 tree 內存開始，不斷被合并到磁盤上的更大容量的Ck tree上。這種方式寫入是順序寫的，增刪改操作都是append。這樣一次I/O可以進行多條數據的寫入，從而充分利用每一次寫I/O。

merge所做的事情有：當上一棵樹容量不足時，1.將上棵樹中要刪除的數據刪除掉，進行GC回收。2.合并數據的最新版本，使得Ck tree不會過度膨脹。

這種初始結構存在的問題有：隨著數據量的增大，merge費勁，沒有好的索引結構，讀放大嚴重。現代的LSM Tree結構如下：

HBase的LSM Tree是什么

MemTable：是LSM Tree在內存中還未刷盤的寫入數據，這里面的數據可以修改。是一個有序的樹狀結構，如RocksDB中的跳表。

SSTable（Sorted String Table）：是一個鍵是有序的，存儲字符串形式鍵值對的磁盤文件。當SSTable太大時，可以將其劃分為多個block；我們需要通過下圖中的Index 記錄下來每個block的起始位置，那么就可以構建每個SSTable的稀疏索引。這樣在讀SSTable前，通過Index結構就知道要讀取的數據塊磁盤位置了。

LSM Tree讀數據

讀數據包括點讀和范圍讀，我們分開討論。假設LSM Tree中的key為[0-99]，

點讀：是指準確地取出一條數據，如get(23),則其示意圖為：

HBase的LSM Tree是什么

按照圖中標示的順序，會先讀取內存，在從Level0依次往高層讀取，直到找到key=23的數據。

范圍讀：是指讀取一個范圍內的數據，如讀取[23-40]內的所有數據（ select * from t where key >= 23 && key <=40),

則需要做的是在每一層SSTable找到這個范圍內的第一個block,然后遍歷block塊的數據，直到不符合范圍條件。

“ReadOnly MemTable：如RocksDB，在MemTable 和 Level0數據之間還有一個內存的ReadOnly MemTable結構。它是LSM Tree在內存中還未刷盤的寫入數據，這里面的數據不可以修改。是當MemTable到達一定量需要刷到SSTable時，由MemTable完整copy下來的。這樣可避免從MemTable直接刷到SSTable時的并發(fā)競爭問題。

LSM Tree寫數據

在LSM Tree寫入數據時，我們把ReadOnly MemTable畫上，示意圖如下：

HBase的LSM Tree是什么

當有寫請求時，數據會先寫入MemTable,同時寫入 WAL Log；當MemTable空間不足時，觸發(fā)ReadOnly MemTable copy,同時寫入WAL Log；然后刷新到磁盤Level0的SSTable中。當低層SSTable空間不足時，不斷通過Compaction和高層SSTable進行Merge。

LSM Tree合并策略

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

HBase的LSM Tree是什么

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)化方式，我這里從讀，合并方面簡要總結下LSM Tree的優(yōu)化。

點讀的優(yōu)化

盡管我們可以通過SSTable的內存block稀疏索引結構簡單判斷key是否可能存在于block中，但如上get(23)，如果level1讀不到，仍需要往下讀level2,level3。（因為數據是按照增刪改的時間順序一層層往下落盤的，如果一個key不存在低level中，可能存在于更早的高level中）。這樣的點讀IO次數較多，讀放大嚴重。

布隆過濾器

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

“布隆過濾器：是通過hash算法來判斷一個key是否存在于某個集合中，布隆過濾器通常是一個bit數組，用針對一個key多次hash算法確定的多個bit值來表示key是否存在。多個bit值全為1，則表示key可能存在，否則不存在。好處是多個bit值通常比直接存儲一個存在的key占用空間小，省內存。

分層布隆過濾器

上述布隆過濾器是假設每層數據都使用相同的布隆過濾器來進行過濾，而數據隨著層數的增加通常是指數級增長的，如果使低層的數據使用更精確的布隆過濾器（所需bit數更多，但是精確度更高）,高層的數據使用稍微不那么精確的布隆過濾器，則整體點查的效率將提高。

參考資料【3】中Monkey做了上述優(yōu)化，即使隨著數據量和層數的增大，點查仍能保持在一個穩(wěn)定的時間內。

HBase的LSM Tree是什么

范圍讀的優(yōu)化

Hash的不足就是無法支持范圍查詢索引，優(yōu)化方式有：

并行查詢

因為讀數據不存在競爭問題，可以并行讀每層的數據，縮短整體查詢時間，但是這種方式實際并沒有縮短IO次數。

前綴布隆過濾器

前綴布隆過濾器是以key的前綴來Hash構建布隆過濾器，而不是key本身的值。這樣可以起到過濾 like Monica* 這樣的查詢條件作用。RocksDB有做此優(yōu)化。

合并的優(yōu)化

上面提到了兩種合并策略Tiering 和 Leveling。Tiering可以減小寫放大，Leveling可以減小讀放大和空間放大。參考資料【3】中提到了數據庫所采用的合并策略走勢如下：

HBase的LSM Tree是什么

隨著數據量的增大，整條曲線會上移。優(yōu)化的重點在于：如何結合兩種合并策略，使曲線整體下移。

Lazy Leveling

參考資料【3】中Dostoevsky采用了一種Lazy Leveling的策略：它是對低層數據采用Tiering合并策略，對高層數據采用Leveling合并策略。從而權衡了讀寫性能。

HBase的LSM Tree是什么

RUM的取舍

RUM的取舍和權衡類似于分布式領域的CAP，在特定的場景采用適合的優(yōu)化手段才能使整體性能最優(yōu)。參考資料【3】中的大佬還提到了Fluid Merge策略。233醬表示雖過了眼癮，但仍是個CRUD渣渣。

關于RUM的優(yōu)化，233醬最后放一張圖，希望對你我有所啟發(fā)。

HBase的LSM Tree是什么

“HBase的LSM Tree是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！

向AI問一下細節(jié)

HBase的LSM Tree是什么

ACID

RUM

為什么要有LSM Tree

LSM Tree讀數據

LSM Tree寫數據

當有寫請求時，數據會先寫入MemTable,同時寫入 WAL Log；當MemTable空間不足時，觸發(fā)ReadOnly MemTable copy,同時寫入WAL Log；然后刷新到磁盤Level0的SSTable中。當低層SSTable空間不足時，不斷通過Compaction和高層SSTable進行Merge。

LSM Tree合并策略

LSM Tree的優(yōu)化

點讀的優(yōu)化

范圍讀的優(yōu)化

合并的優(yōu)化

RUM的取舍

猜你喜歡

最新資訊

相關推薦

相關標簽

當有寫請求時，數據會先寫入MemTable,同時寫入 WAL Log；當MemTable空間不足時，觸發(fā)ReadOnly MemTable copy,同時寫入WAL Log；然后刷新到磁盤Level0的SSTable中。當低層SSTable空間不足時，不斷通過Compaction和高層SSTable進行Merge。