LSM樹如何在HBase中應用

發布時間：2021-12-09 09:55:15 來源：億速云閱讀：245 作者：iii 欄目：大數據

這篇文章主要介紹“LSM樹如何在HBase中應用”，在日常操作中，相信很多人在LSM樹如何在HBase中應用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”LSM樹如何在HBase中應用”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

前言

在有代表性的關系型數據庫如MySQL、SQL Server、Oracle中，數據存儲與索引的基本結構就是我們耳熟能詳的B樹和B+樹。而在一些主流的NoSQL數據庫如HBase、Cassandra、LevelDB、RocksDB中，則是使用日志結構合并樹（Log-structured Merge Tree，LSM Tree）來組織數據。本文先由B+樹來引出對LSM樹的介紹，然后說明HBase中是如何運用LSM樹的。

回顧B+樹

為什么在RDBMS中我們需要B+樹（或者廣義地說，索引）？一句話：減少尋道時間。在存儲系統中廣泛使用的HDD是磁性介質+機械旋轉的，這就使得其順序訪問較快而隨機訪問較慢。使用B+樹組織數據可以較好地利用HDD的這種特點，其本質是多路平衡查找樹。下圖是一棵高度為3的4路B+樹示例。

與普通B樹相比，B+樹的非葉子節點只有索引，所有數據都位于葉子節點，并且葉子節點上的數據會形成有序鏈表。B+樹的主要優點如下：

結構比較扁平，高度低（一般不超過4層），隨機尋道次數少；
數據存儲密度大，且都位于葉子節點，查詢穩定，遍歷方便；
葉子節點形成有序鏈表，范圍查詢轉化為順序讀，效率高。相對而言B樹必須通過中序遍歷才能支持范圍查詢。

當然，B+樹也不是十全十美的，它的主要缺點有兩個：

如果寫入的數據比較離散，那么尋找寫入位置時，子節點有很大可能性不會在內存中，最終會產生大量的隨機寫，性能下降。下圖來自TokuDB的PPT，說明了這一點。

如果B+樹已經運行了很長時間，寫入了很多數據，隨著葉子節點分裂，其對應的塊會不再順序存儲，而變得分散。這時執行范圍查詢也會變成隨機讀，效率降低了。

可見，B+樹在多讀少寫（相對而言）的情境下比較有優勢，在多寫少讀的情境下就不是很有威力了。當然，我們可以用SSD來獲得成倍提升的讀寫速率，但成本同樣高昂，對海量存儲集群而言不太可行。日志結構合并樹（LSM Tree）就是作為B+樹的替代方案產生的。

認識LSM樹

LSM樹由Patrick O'Neil等人在論文《The Log-Structured Merge Tree》中提出，它實際上不是一棵樹，而是2個或者多個樹或類似樹的結構（注意這點）的集合。下圖示出最簡單的有2個結構的LSM樹。

在LSM樹中，最低一級也是最小的C0樹位于內存里，而更高級的C1、C2...樹都位于磁盤里。數據會先寫入內存中的C0樹，當它的大小達到一定閾值之后，C0樹中的全部或部分數據就會刷入磁盤中的C1樹，如下圖所示。

由于內存的讀寫速率都比外存要快非常多，因此數據寫入C0樹的效率很高。并且數據從內存刷入磁盤時是預排序的，也就是說，LSM樹將原本的隨機寫操作轉化成了順序寫操作，寫性能大幅提升。不過，它的tradeoff就是犧牲了一部分讀性能，因為讀取時需要將內存中的數據和磁盤中的數據合并。總體上來講這種tradeoff還是值得的，因為：

可以先讀取內存中C0樹的緩存數據。內存的效率很高，并且根據局部性原理，最近寫入的數據命中率也高。
寫入數據未刷到磁盤時不會占用磁盤的I/O，不會與讀取競爭。讀取操作就能取得更長的磁盤時間，變相地彌補了讀性能差距。

在實際應用中，為了防止內存因斷電等原因丟失數據，寫入內存的數據同時會順序在磁盤上寫日志，類似于我們常見的預寫日志（WAL），這就是LSM這個詞中Log一詞的來歷。另外，如果有多級樹的話，低級的樹在達到大小閾值后也會在磁盤中進行合并，如下圖所示。

下面以HBase為例來簡要講解LSM樹是如何發揮其作用的。

HBase中的LSM樹

我們已經了解了HBase的讀寫流程與MemStore的作用。MemStore作為列族級別的寫入和讀取緩存，它就是HBase中LSM樹的C0層。并且它確實也沒有采用樹形結構來存儲，而是采用了跳表——一種替代自平衡BST的結構。MemStore Flush的過程，也就是LSM樹中C0層刷寫到C1層的過程，而LSM中的日志對應到HBase自然就是HLog了。

為了方便理解，再次祭出之前用過的HBase讀寫流程簡圖。

HFile就是LSM樹中的高層實現。從邏輯上來講，它是一棵滿的3層B+樹，從上到下的3層索引分別是Root index block、Intermediate index block和Leaf index block，對應到下面的Data block就是HFile的KeyValue結構了。HFile V2索引結構的圖示如下：

我們已經知道，HFile過多會影響讀寫性能，因此高層LSM樹的合并即對應HFile的合并（Compaction）操作。合并操作又分別Minor和Major Compaction，由于Major Compaction涉及整個Region，對磁盤壓力很大，因此要盡量避免。

HBase為了提升LSM結構下的隨機讀性能，還引入了布隆過濾器（建表語句中可以指定），對應HFile中的Bloom index block，其結構圖如下所示。

通過布隆過濾器，HBase就能以少量的空間代價，換來在讀取數據時非常快速地確定是否存在某條數據，效率進一步提升。

到此，關于“LSM樹如何在HBase中應用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！

向AI問一下細節

中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

LSM樹如何在HBase中應用

猜你喜歡

中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

LSM樹如何在HBase中應用

猜你喜歡

最新資訊

相關推薦

相關標簽