為什麼大部分NOSQL資料庫選擇使用LSM樹而非B+樹？

文章目錄

• LSM Tree
• 架構介紹
• • MemTable
  • Immutable MemTable
  • WAL
  • SSTable
• 核心流程
• • 寫入資料
  • 查詢資料
  • 段合并（Compaction）
• LSM-Tree VS B+ Teee

LSM Tree

LSM Tree（Log Structured Merge Trees）是一種分層，有序，面向磁盤的複合資料結構，其包括了WAL（Write Ahead Log）、SSTable（Sorted String Table）、MemTable、Immutable MemTable四個部分。LSM Tree是許多key-value 型或日志型資料庫所依賴的核心資料結構，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB等。

其核心架構如下：

LSM Tree核心架構

架構介紹

MemTable

MemTable是在記憶體中的資料結構，用于儲存最近更新的資料，會按照Key有序地組織這些資料，LSM對于具體如何組織有序地組織資料并沒有明确的資料結構定義（常用的結構如紅黑樹、跳表等）。

因為資料暫時儲存在記憶體中，記憶體并不是可靠存儲，如果斷電會丢失資料，是以通常會通過WAL(Write-ahead logging，預寫式日志) 的方式來保證資料的可靠性。

Immutable MemTable

當MemTable達到一定大小後，會轉化成Immutable MemTable。Immutable MemTable是将轉MemTable變為SSTable的一種中間狀态，它其實就相當于一個隻讀的MemTable，不再允許資料寫入，是以寫操作由新的MemTable處理。

Immutable MemTable不會無限占用記憶體，在背景有一個線程不斷地将Immutable MemTable複制到磁盤檔案中，然後釋放記憶體空間，而這些寫入的硬碟檔案，其實就是SSTABLE。

WAL

從前面我們看到，MemTable和Immutable MemTable都存儲在記憶體當中，那如果機器斷電或者伺服器崩潰，這時不就導緻資料永久丢失了嗎？為了解決這個問題，LSM引入了WAL（Write Ahead Log，預寫日志技術） 技術。

WAL的核心就是預先将資料寫入log檔案進行備份，同時在處理完成後生成檢查點，確定資料不會丢失。其核心流程如下：

1. 記憶體中的程式在處理資料時，會先講對資料的修改作為一條記錄，順序寫入磁盤的log檔案作為備份。
2. 系統會周期性檢查記憶體中的資料是否被處理完，并且生成對應的CheckPoint（檢查點） 記錄在磁盤中。
3. 當系統崩潰重新開機時，我們隻需要從磁盤中讀取出檢查點，就能夠知道最後一次成功處理的資料在log檔案中的位置。緊接着我們隻需要把這個位置之後的未被處理的資料從log檔案中讀取到記憶體即可。

SSTable

Immutable MemTable持久化到硬碟上之後的結構稱為Sorted Strings Table (SSTable)。顧名思義，SSTable儲存了排序後的資料（實際上是按照 key 排序的 key-value 對）。每個SSTable可以包含多個存儲資料的檔案，稱為segment，每個segment内部都是有序的，但不同segment 之間沒有順序關系。一個segment一旦生成便不再修改（immutable）。

SSTable示例

介紹完了LSM的核心組成後，下面就來看看其到底如何利用這些結構來完成高性能的寫入、查詢、合并。

核心流程

寫入資料

LSM之是以具有那麼高的寫性能，原因就是兩點：1.順序寫，2.批量寫。

由于外部的資料是無序到來，為確定順序寫入，LSM會在記憶體中利用Memtable（紅黑樹、跳表）來維護資料，確定資料的有序。同時為了減少随機寫入的次數 ，其不會每次都将資料寫入到硬碟中，而是當Memtable的資料量達到一定的門檻值之後，将其轉換為Immutable MemTable的同時會觸發其

flush

操作，将所有排好序的資料一次性批量、順序寫入硬碟中，生成一個segment。

資料寫入

查詢資料

LSM在查找資料時采用的是分層查找的邏輯

1. 首先去記憶體中查找MemTable和Immutable MemTable
2. 然後再按照順序依次在磁盤的每一層SSTable檔案中去找（從最新層開始查找，越是最近的資料越可能被使用者查詢）
3. 如果SSTable添加了布隆過濾器索引，則在布隆過濾器中查找key是否存在，由于布隆過濾器具有假陽性，隻要找不到，就說明目前SSTable中不存在該資料，僅此直接跳過，減少不必要的磁盤掃描。
4. 由于SSTable本身是有序的，為了避免全表掃描，此時通過将稀疏索引讀入記憶體中，利用二分查找來快速定位key在哪一塊資料中。最終隻需要讀取指定偏移量的資料就可以擷取最終的結果。

   

查詢資料流程

段合并（Compaction）

随着資料的不斷寫入，在SSTable中會産生越來越多的的segment，每一個segment都會消耗檔案句柄、記憶體和cpu運作周期。更重要的是，每個查詢請求都必須輪流檢查每個segment，是以段越多，查詢也就越慢。

為了解決這個問題，LSM引入了Compaction機制，其會定期執行合并邏輯，将多個segment合并為一個較大的segment，同時由于每個segment中的資料已經是有序的，是以其隻需要通過歸并排序的邏輯，就可以高效的完成合并。

段合并

在Compaction的過程中，在之前被标記為删除的資料不會被寫入新的segment中，且在合并結束後，所有舊的segment的資料将從硬碟上被徹底删除掉。

LSM-Tree VS B+ Teee

下面給出兩者的對比

差別	LSM-Tree	B+ Teee
應用場景	K-V資料庫、日志資料庫（頻繁寫）	關系型資料庫（頻繁讀）
寫入性能	批量順序寫，且采用追加寫（不需更新），寫入性能高	單條随機寫入，且索引需要更新，寫入性能低
查找性能	存在讀放大，查詢性能低O(N)，經過索引、緩存優化後可以O(LogN)	查找性能極高，O(LogN)
删除與修改	追加寫入，标記删除，在compaction階段才能真正删除	原地更新與删除
存儲方式	記憶體+硬碟	硬碟