HBase 篇(八):LSM Tree
Google的BigTable論文提到了一個很重要的東西:它所使用的檔案組織方式(LSM-Tree),這個東東出自1996 年的一篇論文《The Log-Structured Merge-Tree (LSM-Tree)》。
對HBase有一定了解的同學對這個LSM一定不陌生。我們先來回憶下HBase的讀寫
寫流程
-
向zookeeper發起請求,從ROOT表中獲得META所在的region,再根據table,namespace,rowkey,去meta表中找到目標資料對應的region資訊以及regionserver
-
把資料分別寫到HLog和MemStore上一份,若MemStore中的資料有丟失,則可在HLog上恢復
-
當memstore資料達到閾值(預設是64M),將資料刷到硬碟,將記憶體中的資料刪除同時刪除Hlog中的歷史資料。
-
當多個StoreFile檔案達到一定的大小後,會觸發Compact合併操作,合併為一個StoreFile,這裡同時進行版本的合併和資料刪除。
-
當Compact後,逐步形成越來越大的StoreFIle後,會觸發Split操作,把當前的StoreFile分成兩個,這裡相當於把一個大的region分割成兩個region
-
當hregionser宕機後,將hregionserver上的hlog拆分,然後分配給不同的hregionserver載入,修改.META.
讀流程
-
首先用MemStoreScanner搜尋MemStore裡是否有所查的rowKey(這一步在記憶體中,很快),
-
同時也會用Bloom Block通過一定演算法過濾掉大部分一定不包含所查rowKey的HFile,
-
上面提到在RegionServer啟動的時候就會把Trailer,和Load-on-open-section裡的block先後載入到記憶體,所以接下來會查Trailer,因為它記錄了每個HFile的偏移量,可以快速排除掉剩下的部分HFile。
-
經過上面兩步,剩下的就是很少一部分的HFile了,就需要根據Index Block索引資料(這部分的Block已經在記憶體)快速查詢rowkey所在的block的位置;
-
找到block的位置後,檢查這個block是否在blockCache中,在則直接去取,如果不在的話把這個block載入到blockCache進行快取,
-
最後掃描這些讀到記憶體中的Block(可能有多個,因為有多版本),找到對應rowKey返回需要的版本。
熟悉了HBase的讀寫流程後(尤其是寫流程),瞭解lsm tree就會變得容易很多了。Log-Structured Merge-Tree中文翻譯是日誌結構合併樹。那我們就從日誌結構與合併樹這兩個方面來講。
日誌結構
我們知道磁碟隨機讀寫效能是比順序讀寫慢至少3個數量級的,日誌的特點是 它是順序追加寫 的,可以保證非常好的寫操作效能,但是從 日誌檔案中讀一些資料將會比寫操作需要更多的時間 ,需要倒序掃描,直接找到所需的內容。
因此日誌適用的場景非常有限:
為了為更復雜的讀場景(比如按key或者range)提供高效的效能,人們發明了幾種方式:
二分查詢: 將檔案資料有序儲存,使用二分查詢來完成特定key的查詢。
雜湊:用雜湊將資料分割為不同的bucket
B+樹:使用B+樹 或者 ISAM 等方法,可以減少外部檔案的讀取
外部檔案: 將資料儲存為日誌,並建立一個hash或者查詢樹對映相應的檔案。
所有的方法都可以有效的提高了讀操作的效能(最少提供了O(log(n)) ),但是,卻丟失了日誌檔案超好的寫效能。上面這些方法,都 強加了總體的結構資訊在資料上,資料被按照特定的方式放置,所以可以很快的找到特定的資料 ,但是卻對寫操作不友善,讓寫操作效能下降。更糟糕的是,當我們需要更新hash或者B+樹的結構時,需要同時更新檔案系統中特定的部分,這就是上面說的比較慢的隨機讀寫操作。這種隨機的操作要儘量減少。
此時,LSM 被髮明瞭, LSM 使用一種不同於上述四種的方法,保持了日誌檔案寫效能,以及微小的讀操作效能損失。本質上就是 通過把隨機寫的資料寫到記憶體,然後定期flush到磁碟,對於磁碟來說,讓所有的操作順序化,而不是隨機讀寫。
合併樹
LSM樹原理把一棵大樹拆分成N棵小樹, 它首先寫入記憶體中即是小樹,隨著小樹越來越大,會flush到磁碟中,磁碟中的樹定期可以做merge操作,合併成一棵大樹,以優化讀效能 。
lsm tree,理論上,可以是記憶體中樹的一部分和磁碟中第一層樹做merge,對於磁碟中的樹直接做update操作有可能會破壞物理block的連續性,但是實際應用中,一般lsm有多層,當磁碟中的小樹合併成一個大樹的時候,可以重新排好順序,使得block連續,優化讀效能。
hbase在實現中,是把整個記憶體在一定閾值後,flush到disk中,形成一個file,這個file的儲存也就是一個小的B+樹,因為hbase一般是部署在hdfs上,hdfs不支援對檔案的update操作,所以hbase這麼整體記憶體flush,而不是和磁碟中的小樹merge update,這個設計也就能講通了。記憶體flush到磁碟上的小樹,定期也會合併成一個大樹。整體上hbase就是用了lsm tree的思路。
覺得有價值請關注 ▼