LSM-Tree 與 RocksDB

（點選上方公眾號，可快速關註）

來源：MRRiddler ，

blog.mrriddler.com/2017/05/30/LSM-Tree%E4%B8%8ERocksDB/

冥冥之中，接觸到了不同於關係資料庫的NoSQL Key-Value儲存引擎RocksDB，懵懵懂懂、充滿好奇，google一點，滿眼皆是LSM-Tree，頭暈眼花、若即若離，便有了這篇文章，一起與大家分享這趟探險之旅。

LSM-Tree(Log-Structured-Merge-Tree)

LSM從命名上看，容易望文生義成一個具體的資料結構，一個tree。但LSM並不是一個具體的資料結構，也不是一個tree。LSM是一個資料結構的概念，是一個資料結構的設計思想。實際上，要是給LSM的命名斷句，Log和Structured這兩個詞是合併在一起的，LSM-Tree應該斷句成Log-Structured、Merge、Tree三個詞彙，這三個詞彙分別對應以下三點LSM的關鍵性質：

• 將資料形成Log-Structured：在將資料寫入LSM記憶體結構之前，先記錄log。這樣LSM就可以將有易失性的記憶體看做永久性儲存器。並且信任記憶體上的資料，等到記憶體容量達到threshold再集體寫入磁碟。將資料形成Log-Structured，也是將整體儲存結構轉換成了“記憶體(in-memory)”儲存結構。

• 將所有磁碟上資料不組織成一個整體索引結構，而組織成有序的檔案集：因為磁碟隨機讀寫比順序讀寫慢3個數量級，LSM儘量將磁碟讀寫轉換成順序讀寫。將磁碟上的資料組織成B樹這樣的一個整體索引結構，雖然查詢很高效，但是面對隨機讀寫，由於大量尋道導致其效能不佳。而LSM用了一種很有趣的方法，將所有資料不組織成一個整體索引結構，而組織成有序的檔案集。每次LSM面對磁碟寫，將資料寫入一個或幾個新生成的檔案，順序寫入且不能修改其他檔案，這樣就將隨機讀寫轉換成了順序讀寫。LSM將一次性集體寫入的檔案作為一個level，磁碟上劃分多level，level與level之間互相隔離。這就形成了，以寫入資料時間線形成的邏輯上、而非物理上的層級結構，這也就是為什麼LSM被命名為”tree“，但不是“tree”。

• 將資料按key排序，在合併不同file、level上的資料時類似merge-join：如果一直保持生成新的檔案，不僅寫入會造成冗餘空間，而且也會大量降低讀的效能。所以要高效的、週期性合併不同file、level。而如果資料是亂序的，根本做不到高效合併。所以LSM要將資料按key排序，在合併不同file、level上的資料時類似merge-join。

很明顯，LSM犧牲了一部分讀的效能和增加了合併的開銷，換取了高效的寫效能。那LSM為什麼要這麼做？實際上，這就關係到對於磁碟寫已經沒有什麼最佳化手段了，而對於磁碟讀，不論硬體還是軟體上都有最佳化的空間。透過多種最佳化後，讀效能雖然仍是下降，但可以控制在可接受範圍內。實際上，用於磁碟上的資料結構不同於用於記憶體上的資料結構，用於記憶體上的資料結構效能的瓶頸就在搜尋複雜度，而用於磁碟上的資料結構效能的瓶頸在磁碟IO，甚至是磁碟IO的樣式。

LSM近年來已被廣泛使用起來，還有將B家族樹和LSM結合起來使用的，像HBase、SQLite4、MongoDB、Cassandra、LevelDB，還有接下來的主角RocksDB，這些當家資料儲存花旦，都或多或少支援、使用起LSM了。

RocksDB

RocksDB是Facebook在LevelDB基礎上用C++寫的Key-Value儲存引擎。其Key和Value都是二進位制流。並對快閃記憶體(flash)有更友好的最佳化。先來聊一聊RocksDB的整體結構，然後再聊一聊RocksDB中的一些有意思的抽象，最後聊一聊RocksDB記憶體上、磁碟上的具體結構。在RocksDB中，將記憶體結構中的資料寫入磁碟結構叫做flush，而不同file、level之間merge叫做compaction。

Architecture

RocksDB如上文所說是基於LSM做儲存。RocksDB在記憶體中的結構叫做memtable，用於形成Log-Structured的file叫做logfile，磁碟上的file結構叫做sstfile，用於記錄對file更改的log叫做manifest。

Column-Family

為儲存的資料邏輯分族，將不同family互相隔離，分開配置、儲存。column family共享logfile，而不共享memtable和sstfile，這使得column family有以下兩點特點：

• 多個column family仍然能保持事務的原子性。

• 單獨增加、修改、刪除一個column family內的資料效能提升。

Filter

RocksDB有一些奇思妙想的filter，這些filter根據特定條件生成，透過資料的key就可以判斷資料是否確定或可能被特定條件排除掉。有些filter可以用來對讀最佳化，有些也可以用來管理資料的生命週期等。

Bloom-Filter

bloom filter就是一個能提高讀效能的filter。透過演演算法可以生成一個key set對應的bloom filter。這個bloom filter可以判斷出任意key可能存在或者肯定不存在key set中。每個sstfile在生成的時候，都會建立一個或多個對應的bloom filter，當在讀資料的時候，可以快速判斷出資料是否可能在sstfile中。在做range scan和prefix查詢的時候，bloom filter也能幫上忙。

Time-To-Live(TTL)

RocksDB還支援為存入的資料設定上最長生命週期。RocksDB會為有TTL的資料建立一個filter。這種filter叫做compaction filter，當進行compaction的時候，生命週期結束的資料將會被排除。很明顯，這個TTL不是絕對時間，RocksDB會在絕對時間過後的一段時間內刪除資料。

Memtable

RocksDB在記憶體上的結構由memtable組成，具體預設使用SkipList，當然，外部也可以指定其他資料結構。不過，SkipList做為用多個線性結構模仿出層級結構的“樹狀“資料結構，能提供常數級順序訪問和對數級隨機訪問，並且在併發環境相對於其他樹狀資料結構，減輕了鎖開銷，運用在這裡再合適不過了。

Flush

為了減小鎖開銷，將寫入memtable和flush分離，RocksDB會使用多個memtable，並且把flush這件事抽象為task-pipeline，也就是job、job queue、worker抽象。將要flush的memtable先轉換成immutable memtable，代表其不可寫了，並將immutable memtable加入flush pipeline，等待後臺執行緒去flush。而同時新的memtable生成取代immutable memtable等待資料寫入。在將immutable memtable flush的過程中，值得一提的是會做inline-compaction，這是將immutbale memtable提前進行資料合併的最佳化，如果在這個memtable建立到flush的週期中，資料被加入然後刪除，在這一步就可以compact掉，這對短生命週期的資料有很大的寫最佳化。

SSTFile(SSTTable)

RocksDB在磁碟上的file結構sstfile由block作為基本單位組成，一個sstfile結構如下：

[data block 1]

[data block 2]

…

[data block N]

[meta block 1: filter block]                 

[meta block 2: stats block]                   

[meta block 3: compression dictionary block]  

…

[meta block K: future extended block] 

[metaindex block]

[index block]

[Footer]                              

其中data block就是資料物體block，meta block為元資料block。metaindex block和index block分別是對meta block和data block的索引block。metaindex block和index block都以blockhandle結構作為指向所索引block的指標。blockhandle包含所索引block的offset和size。metaindex block將所索引的meta block的名字作為key。而index block將所索引的data block前一block的最大key值與所索引data block的最小key值的中間任意值作為key。

filter block記錄的就是針對此sstfile生效的一系列filter。stats block也就是properties block，它以key-value形式記錄了此sstfile的一些屬性。sstfile組成的block有可能被壓縮(compression)，不同level也可能使用不同的compression方式。compression dictionary block記錄了適用於compression此sstfile block的庫。footer添加了一些位元組填充，和記錄了指向metaindex block、index block的blockhandle結構指標。這說明sstfile如果要遍歷block，會逆序遍歷，從footer開始。

Compaction

RocksDB會在後臺多執行緒compact。RocksDB有兩種compact style：

• Universal Style Compaction：這種style去compact就如上文LSM所聊的，將磁碟上資料完全按照寫入時間線去組織，只將相鄰時間段內寫入磁碟上的資料compact，很像在合併互不重疊(overlapping)的時間段。這種style可以compact出新的file或者level。很明顯，不同時間段內的資料會有重疊的key，會有冗餘空間。

• Level Style Compaction：這種style去compact不會將磁碟上資料完全按照寫入時間線去組織。而為了防止同一level多個file中相同key資料的冗餘，這種style要保證同一level不存在有相同key的資料。若將Ln level中的file1 要compact到Ln+1level，要將Ln+1level中所有包含重疊file1資料key的檔案一起compact，最後將這些file compact成Ln+1level中的一個新file。這種style還會造成一種效果，就是同一level的file按key值排序。雖然Level Style Compaction減少了冗餘空間，但是，對於讀資料來說，Universal Style Compaction更加遵守區域性性，所以Level Style Compaction讀效能更差一點。

也就說，Universal Style Compaction重讀輕空間，Level Style Compaction重空間輕讀。RocksDB將後者作為default style，關於這兩種style如何選擇(pick)level、file去compact，這裡就不整體敘述了，基本是file、level的數量或大小達到一個ratio的threshold就會triger compact，關於Universal Style的選擇在這裡，關於Level Style的選擇在這裡。挑個有趣的聊下，Level Style如何pick file去compact？RocksDB還不能提供一個universal策略去pick，不過以下幾個option可以選擇：

• 優先選擇key分佈範圍集中的file去compact：file中資料key如果分佈集中，就會有更少的重疊file在下一level，就會有更少的compact開銷。用kOldestSmallestSeqFirst設定優先compactkey分佈範圍集中的file。

• 優先選擇冷資料file去compact：經常修改的熱資料如果經常compact，只會浪費開銷。設想下，剛剛插入的一組資料，馬上又刪除，如果插入後就進行compact，本應該刪除的資料又佔了兩倍的冗餘空間。用kOldestLargestSeqFirst設定優先compact冷資料file。

• 優先選擇被刪除資料多的file去compact：被刪除的資料如果早被compact的話，可以減少冗餘空間，用kByCompensatedSize設定優先compact被刪除資料多的file。

SSTFile-Indexing

如果RocksDB使用的是Level Style Compaction，那麼還可以在查詢資料時做更多最佳化。Level Style Compaction保證同一level不存在有相同key的資料，且file按key值排序。首先，對於有序結構搜尋，可以使用二分查詢。其次，如果在某一level中都查詢不到key，那麼在下一level中查詢的時候，可以用查詢到的最後一個file的key範圍排除下一level的很多file，比如如下結構：

                                         file 1                                file 2

                                      +———-+                          +———-+

level 1:                              | 100, 200 |                          | 300, 400 |

                                      +———-+                          +———-+

           file 1     file 2      file 3      file 4       file 5       file 6       file 7      

         +——–+ +——–+ +———+ +———-+ +———-+ +———-+ +———-+

level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | 

         +——–+ +——–+ +———+ +———-+ +———-+ +———-+ +———-+

如果要查詢80，在level 1中file1沒有查詢到，那麼在level2中可以排除file3以後的file。這種排除和level結構有點像區間樹。基於此思想，在level compact的時候，可以為file新增一系列指向下一level file的指標，加快查詢速度。

Manifest

因為檔案系統的操作不能保證原子性，所以RocksDB對file的更改也會記錄log，就記錄在manifest裡。實際上，可以將manifest看做，記錄的是RocksDB的狀態。manifest記錄的內容就成了RocksDB按時間排序的一系列狀態，如果，將每個狀態看做RocksDB某個時間點的快照，manifest就是RocksDB的動圖GIF。

Cache

沒有cache的儲存引擎是不完整的，RocksDB有兩種cache，block cache和table cache。先來聊聊block cache。block cache快取的單位就是sstfile的data block，這種cache有兩種演演算法，經典的LRU和clock，任由你選擇。除了data block，用於索引和提高讀效能的index block和filter block更是重點快取物件，但RocksDB並不會把這倆放在block cache中，RocksDB會單獨照顧好這倆，基本不用外部操心。而table cache快取的是sstfile的file descriptor，實際上，作業系統透過file descriptor用取用計數的方式來管理file結構體和其背後的資源。也就是說，table cache快取的是作業系統用來操作sstfile的file結構體和其背後資源，更多關於file descriptor結構，推薦這篇文章。

http://cuckootan.me/2015/04/18/Linux/行程開啟及讀寫檔案的過程/

Tips

以下是使用RocksDB的一些建議：

• RocksDB執行緒模型是單控制代碼對多執行緒。

• Get、Put、Delete等操作不需要操心資料同步問題，而Iterator和WriteBatch需要同步控制。

• WriteBatch類似於事務，提供將一個或多個資料庫操作抽象為單位的能力，此單位是原子性的，但並不會互相隔離從而併發控制，也不會檢測出異常並恢復。

本篇聊了很多RocksDB的設計思想。然而畢竟大多數工程師都是面嚮應用，不會去搞個儲存引擎。這裡就總結幾條從LSM、RocksDB等儲存引擎中學到的有關讀寫IO的技巧，理解了大有裨益。

• 相對於計算、記憶體讀取，磁碟IO慢不知多少數量級。

• 相對於執行一次磁碟IO，磁碟IO的資料量多少不重要，也就說開始、結束一次磁碟IO更費時。儘量集中對磁碟進行IO。

• 相對於磁碟隨機讀寫，磁碟順序讀寫快上3個數量級。

• 讀寫分離，減少併發鎖的效能開銷。

取用

• LSM

  https://www.zhihu.com/question/19887265

• LSM論文

  http://www.cs.umb.edu/~poneil/lsmtree.pdf

• RocksDB Blog

  http://rocksdb.org/blog/

• RocksDB Wiki

  https://github.com/facebook/rocksdb/wiki

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，看技術乾貨