RocksDB
- RocksDB原理
-
- B+樹
- LSM樹（Log-Structured Merge Tree）
- LevelDB特點
- RocksDB對LevelDB的優化
- RocksDB 寫入與删除
- RocksDB 讀取記錄
RocksDB原理
RocksDB是facebook開源的NOSQL存儲系統，其設計是基于Google開源的LevelDB，優化了LevelDB中存在的一些問題，其性能要比LevelDB強，設計與LevelDB極其類似。
LevelDB的開源發起者：Jeff Dean和Sanjay Ghemawat，這兩位是Google公司重量級的工程師。
Jeff Dean是Google大規模分布式平台Bigtable和MapReduce主要設計和實作者。
Sanjay Ghemawat是Google大規模分布式平台GFS，Bigtable和MapReduce主要設計和實作工程師。
如果了解Bigtable的話，應該知道在這個影響深遠的分布式存儲系統中有兩個核心的部分：Master Server和Tablet Server。其中Master Server做一些管理資料的存儲以及分布式排程工作，實際的分布式資料存儲以及讀寫操作是由Tablet Server完成的，而LevelDB則可以了解為一個簡化版的Tablet Server。
RocksDB相對傳統的關系資料庫的一大改進是采用LSM樹存儲引擎。LSM樹是非常有創意的一種資料結構，它和傳統的B+樹不太一樣，下面先說說B+樹。
B+樹
上圖是B+樹的一個例子。 B+樹根節點和枝節點分别記錄每個葉子節點的最小值，并用一個指針指向葉子節點。葉子節點裡每個鍵值都指向真正的資料塊，每個葉子節點都有前指針和後指針，這是為了做範圍查詢時，葉子節點間可以直接跳轉，進而避免再去回溯至枝和跟節點。
B+樹最大的性能問題是會産生大量的随機IO，随着新資料的插入，葉子節點會慢慢分裂，邏輯上連續的葉子節點在實體上往往不連續，甚至分離的很遠，但做範圍查詢時，會産生大量讀随機IO。
對于大量的随機寫也一樣，舉一個插入key跨度很大的例子，如7->1000->3->2000 … 新插入的資料存儲在磁盤上相隔很遠，會産生大量的随機寫IO，低下的磁盤尋道速度嚴重影響性能。
LSM樹（Log-Structured Merge Tree）
LSM樹而且通過批量存儲技術規避磁盤随機寫入問題。 LSM樹的設計思想非常樸素, 它的原理是把一顆大樹拆分成N棵小樹， 它首先寫入到記憶體中（記憶體沒有尋道速度的問題，随機寫的性能得到大幅提升），在記憶體中建構一顆有序小樹，随着小樹越來越大，記憶體的小樹會flush到磁盤上。磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優化讀性能。
LevelDB特點
- LevelDB是一個持久化存儲的KV系統，和Redis這種記憶體型的KV系統不同，LevelDB不會像Redis一樣狂吃記憶體，而是将大部分資料存儲到磁盤上。
- LevleDb在存儲資料時，是根據記錄的key值有序存儲的，就是說相鄰的key值在存儲檔案中是依次順序存儲的，而應用可以自定義key大小比較函數。
- LevelDB支援資料快照（snapshot）功能，使得讀取操作不受寫操作影響，可以在讀操作過程中始終看到一緻的資料。
- LevelDB還支援資料壓縮等操作，這對于減小存儲空間以及增快IO效率都有直接的幫助。
RocksDB對LevelDB的優化
- 增加了column family，這樣有利于多個不相關的資料集存儲在同一個db中，因為不同column family的資料是存儲在不同的sst和memtable中，是以一定程度上起到了隔離的作用。
- 采用了多線程同時進行compaction的方法，優化了compact的速度。
- 增加了merge operator，優化了modify的效率
- 将flush和compaction分開不同的線程池，能有效的加快flush，防止stall。
-
增加了對write ahead log(WAL)的特殊管理機制，這樣就能友善管理WAL檔案，因為WAL是binlog檔案。
RocksDB的整體結構：
rocksdb從3.0開始支援ColumnFamily的概念。每個columnfamilyl的meltable與sstable都是分開的，是以每一個column family都可以單獨配置，所有column family共用同一個WA檔案，可以保證跨column family寫入時的原子性。 RocksDB原理介紹RocksDB原理
RocksDB 寫入與删除
寫操作包含兩個具體步驟：
- 首先是将這條KV記錄以順序寫的方式追加到log檔案末尾，因為盡管這是一個磁盤讀寫操作，但是檔案的順序追加寫入效率是很高的，是以并不會導緻寫入速度的降低。
-
第二個步驟是:如果寫入log檔案成功，那麼将這條KV記錄插入記憶體中的Memtable中，Memtable隻是一層封裝，其内部其實是一個Key有序的SkipList清單，插入一條新記錄的過程也很簡單，即先查找合适的插入位置，然後修改相應的連結指針将新記錄插入即可。完成這一步，寫入記錄就算完成了，是以一個插入記錄操作涉及一次磁盤檔案追加寫和記憶體SkipList插入操作，這是為何RocksDB寫入速度如此高效的根本原因。
删除操作與插入操作相同，差別是，插入操作插入的是Key:Value值，而删除操作插入的是“Key:删除标記”，并不真正去删除記錄，而是背景Compaction的時候才去做真正的删除操作。
RocksDB 讀取記錄
RocksDB首先會去檢視記憶體中的Memtable，如果Memtable中包含key及其對應的value，則傳回value值即可；如果在Memtable沒有讀到key，則接下來到同樣處于記憶體中的Immutable Memtable中去讀取，類似地，如果讀到就傳回，若是沒有讀到,那麼會從磁盤中的SSTable檔案中查找。
總的讀取原則是這樣的：首先從屬于level 0的檔案中查找，如果找到則傳回對應的value值，如果沒有找到那麼到level 1中的檔案中去找，如此循環往複，直到在某層SSTable檔案中找到這個key對應的value為止（或者查到最高level，查找失敗，說明整個系統中不存在這個Key)。
相對寫操作，讀操作處理起來要複雜很多。RocksDB為了提高讀取速遞，增加了讀cache和Bloomfilter。