LSM樹原理及應用到HBase的索引

@Author  : Spinach | GHB
@Link    : http://blog.csdn.net/bocai8058
           

文章目錄

• • • 概念
    • B+樹
    • LSM樹
    • • 主要原理
    • LSM樹的讀寫
    • • LSM樹的讀寫
      • LSM樹的優化方式
      • 關于LSM最本質原理的3個問題
    • B樹與LSM樹的适應場景

概念

LSM樹全稱是基于日志結構的合并樹（Log-Structured Merge-Tree）。

No-SQL資料庫一般采用LSM樹作為資料結構，HBase也不例外。衆所周知，RDBMS一般采用B+樹作為索引的資料結構，如圖1。RDBMS中的B+樹一般是3層n路的平衡樹。B+樹的節點對應于磁盤資料塊。是以對于RDBMS，資料更新操作需要5次磁盤操作（從B+樹3次找到記錄所在資料塊，再加上一次讀和一次寫）。

B+樹

在RDBMS中，資料随機無序寫在磁盤塊中，如果沒有B+樹，讀性能會很低。B+樹對于資料讀操作能很好地提高性能，但對于資料寫，效率不高。對于大型分布式資料系統，B+樹還無法與LSM樹相抗衡。

LSM樹

随着NoSQL系統尤其是類BigTable系統的流行，LSM的檔案系統越來越讓人熟知。

• LSM主要用于為那些長期具有很高記錄更新（插入和删除）頻率的檔案提供低成本的索引機制。
• LSM樹實作了所有的索引值對于所有的查詢來說都可以通過記憶體元件或某個磁盤元件進行通路。
• LSM減少了磁盤磁壁的移動次數降低了進行資料插入時磁盤磁壁的開銷。
• LSM在進行需要即時響應的操作時會損失I/O效率，最适用于索引插入比查詢操作多的情況。

核心思想的核心就是放棄部分讀能力，換取寫入的最大化能力。LSM樹主題思想是劃分兩個部分：一部分在磁盤，一部分在記憶體。

主要原理

1. 輸入的資料首先會插入到記憶體中的樹；
2. 同時為了防止資料丢失，寫記憶體的同時需要暫時持久化到磁盤（即輸入資料時資料會以完全有序的形式先存儲在日志檔案中（對應HBase的MemStore和HLog））；
3. 當日志檔案被修改時，對應的更新會被先儲存在記憶體中來加速查詢。
4. 當記憶體空間逐漸被占滿之後，LSM會把這些有序的鍵重新整理到磁盤，同時和磁盤中的LSM樹合并成一個檔案。
   • 合并操作會從左至右周遊記憶體中的葉子節點與磁盤中樹的葉子節點進行合并；
   • 當合并的資料量達到磁盤的存儲頁的大小時，會将合并的資料持久化到磁盤；
   • 同時更新父親節點對葉子節點的指針。

     

LSM樹的讀寫

LSM樹的讀寫

資料寫

• 資料首先順序寫如HLog (WAL), 然後同步寫到MemStore；
• 在MemStore中，資料是一個2層B+樹（下圖中的C0樹）。MemStore上的樹達到一定大小之後，需要flush到HRegion磁盤中（一般是Hadoop DataNode），這樣MemStore就變成了DataNode上的磁盤檔案StoreFile，定期HRegionServer對DataNode的資料做merge操作，徹底删除無效空間，多棵小樹在這個時機合并成大樹，來增強讀性能。
• 在storefile中，資料是3層B+樹（下圖中的C1樹），并針對順序磁盤操作進行優化。

  

資料讀

• 首先搜尋MemStore，如果不在MemStore中，則到storefile中尋找。

資料删除

• 不會去磁盤上删除資料，而是為資料添加一個删除标記。在随後的major compaction中，被删除的資料和删除标記才會真的被删除。

補充：hbase在實作中，是把整個記憶體在一定門檻值後，flush到disk中，形成一個file，這個file的存儲也就是一個小的B+樹，因為hbase一般是部署在hdfs上，hdfs不支援對檔案的update操作，是以hbase這麼整體記憶體flush，而不是和磁盤中的小樹merge update，這個設計也就能講通了。記憶體flush到磁盤上的小樹，定期也會合并成一個大樹。整體上hbase就是用了lsm tree的思路。

LSM樹的優化方式

Bloom filter

就是個帶随即機率的bitmap,可以快速的告訴你，某一個小的有序結構裡有沒有指定的那個資料的。于是就可以不用二分查找，而隻需簡單的計算幾次就能知道資料是否在某個小集合裡啦。效率得到了提升，但付出的是空間代價。

compact

小樹合并為大樹:因為小樹他性能有問題，是以要有個程序不斷地将小樹合并到大樹上，這樣大部分的老資料查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了.

關于LSM最本質原理的3個問題

1. 首先說說為什麼要有WAL（Write Ahead Log）？

因為資料是先寫到記憶體中，如果斷電，記憶體中的資料會丢失，是以為了保護記憶體中的資料，需要在磁盤上先記錄logfile，
當記憶體中的資料flush到磁盤上時，就可以抛棄相應的Logfile。
           

1. 什麼是memstore,storefile？

LSM樹就是一堆小樹，在記憶體中的小樹即memstore，每次flush，記憶體中的memstore變成磁盤上一個新的storefile。
           

1. 為什麼會有compact？

随着小樹越來越多，讀的性能會越來越差，是以需要在适當的時候，對磁盤中的小樹進行merge，多棵小樹變成一顆大樹。
           

B樹與LSM樹的适應場景

LSM-Tree比較适合的應用場景是：insert資料量大，讀資料量和update資料量不高且讀一般，針對最新資料。

B-Tree比較适合的應用場景：insert資料量小，讀資料量比較高。