一文掌握Rocksdb的基本用法

1. Rockdb 簡介

• 一個帶版本的Key-Value存儲引擎，Key/Value采用字元串編碼，Key和Value最大長度為4GB，主要針對高性能的SSD場景，也支援不同媒體的存儲模型
• 它是一個C++庫，支援點查和範圍查詢，提供不同類型的ACID保障
• 将随機性轉換為順序寫，帶來讀寫放大的問題
• Key有序，支援Get(key)/Put(Key)/Delete(Key)/Merge(Key) and NewIterator()方法
• 它引入了leveldb project(version 1.5)的部分源碼，同時吸收了Apache Hbase的一些優秀的設計理念，LevelDB 的選擇是：犧牲部分 Get 性能，換取強悍 Put 性能，再極力優化 Get

2. Rocksdb Feature Timeline

rocksdb 功能疊代

3. RocksDB的存儲結構

3.1. MemoryTable

開發庫提供了三個 memtable：

• skiplist memtable
• vector memtable
• 字首散列（prefix-hash） memtable

Vector memtable 适用于将資料批量加載到資料庫中。每個寫入在向量的末尾插入一個新元素; 當它是重新整理 memtable 到存儲的時候，向量中的元素被排序并寫出到 L0 中的檔案。

字首散列 memtable 允許對 gets，puts 和 scans-within-a-key-prefix 進行有效的處理。

SkipList：跳表由 William Pugh 在 1990 年提出，相關論文為：Skip Lists: A Probabilistic Alternative to Balanced Trees。跳表是一種可以取代平衡樹的資料結構。跳表使用機率均衡而非嚴格均衡政策，進而相對于平衡樹，大大簡化和加速了元素的插入和删除。

3.2. SSTable

SSTable 的格式為檔案本身就是一個排序的、不可變的、持久的Key/Value對Map。其中Key和value都可以是任意的byte字元串。 KeyValue 對根據固定比較規則有序地寫入到檔案中，檔案内部分成一系列的Blocks(Block 不會太大，可自定義，預設4KB，常見的是 64KB，RocksDB對應配置項：table_options.block_size)，同時具有必要的索引資訊。這樣 就既可以順序地讀取内部 KeyValue 記錄，也能夠根據某個Key值進行快速定位。

如圖所示，SST 檔案從頭到尾分成5個部分。

名稱	占用空間	說明
Footer	固定48位元組	指出 IndexBlock 和 MetaIndexBlock 在檔案中的偏移量資訊，它是元資訊的元資訊，它位于 sstable 檔案的尾部
IndexBlock	占用一個 block 空間	記錄了 DataBlock 相關的元資訊
MetaIndexBlock	占用一個 block 空間	各個元資訊的Block，包括Filter、Properties(整個table的屬性資訊)、Compression dictionary、Range deletion tombstone
MetaBlock	可能占用多個 block空間	存儲布隆過濾器的二進制資料 及其他元資訊資料
DataBlock	可能占用多個 block空間	存儲實際的資料即鍵值對内容

3.3. Block

從上面的表格可以看出RocksDB的SSTable除了Footer外其餘都是使用Block進行存儲的，Block在硬碟上存儲的時候，會在實際資料之後加上5個位元組的額外内容：compression type、crc，如下圖所示：

3.4. Bloom Filter

這裡再說一下MetaBlock中的Bloom Filter，Bloom Filter的作用是對于任意集合的key，基于BitMap可以用來建構一個bit數組的算法。給出任意key，這個bit數組可以用于決定這個key是不是可能存在或者絕對不存在于這個key集合，用來減少無用的查詢次數，進而加快查詢的速度。

3.5. Footer

以上各部分都是 Block 的結構，隻有 Footer 不同，是一個定長的格式。

序列化後，Footer的長度固定，為48個位元組（舊）或53位元組（新），格式如下：

// legacy footer format:
//    metaindex handle (varint64 offset, varint64 size)
//    index handle     (varint64 offset, varint64 size)
//    <padding> to make the total size 2 * BlockHandle::kMaxEncodedLength
//    table_magic_number (8 bytes)
// new footer format:
//    checksum type (char, 1 byte)
//    metaindex handle (varint64 offset, varint64 size)
//    index handle     (varint64 offset, varint64 size)
//    <padding> to make the total size 2 * BlockHandle::kMaxEncodedLength + 1
//    footer version (4 bytes)
//    table_magic_number (8 bytes)
           

Footer 中的資訊，指明了 MetaIndexBlock 和 IndexBlock的位置，進而找到 MetaBlock 和 DataBlock。

讀取 SST檔案的時候，就是從檔案末尾，固定讀取這48或53位元組，進而得到了 Footer 資訊。

3.6. 磁盤檔案

• *.log: 事務日志用于儲存資料記錄檔，可用于資料恢複
• *.sst: 資料持久換檔案（此處的例子沒有生成sst檔案是因為第一次寫資料，資料量小沒觸發flush操作，資料都在記憶體的MemoryTable中）
• MANIFEST：資料庫中的 MANIFEST 檔案記錄資料庫狀态。Compaction過程會添加新檔案并從資料庫中删除舊檔案，并通過将它們記錄在 MANIFEST 檔案中使這些操作持久化。
• CURRENT：記錄目前正在使用的MANIFEST檔案
• LOCK：rocksdb自帶的檔案鎖，防止兩個程序來打開資料庫。
• IDENTITY：id
• LOG：統計日志
• OPTIONS：配置資訊

3.7. 記憶體

RocksDB的記憶體大緻有如下四個區：

• Block Cache
• Indexes and bloom filters
• Memtables
• Blocked pinned by iterators

Block Cache

RocksDB 的資料的緩存，這個緩存可以在多個 RocksDB 的執行個體下緩存。一般預設的Block Cache 中存儲的值是未壓縮的，而使用者可以再指定一個 Block Cache，裡面的資料可以是壓縮的。使用者通路資料先通路預設的 Block Cache，待無法擷取後再通路使用者 Cache，使用者 Cache 的資料可以直接存入 page cache 中。

Cache 有兩種：LRUCache 和 BlockCache。Block 分為很多 Shard，以減小競争，是以 shard 大小均勻一緻相等，預設 Cache 最多有 64 個 shards，每個 shard 的 最小 size 為 512k，總大小是 8M，類别是 LRU。

std::shared_ptr<Cache> cache = NewLRUCache(capacity);
    BlockedBasedTableOptions table_options;
    table_options.block_cache = cache;
    Options options;
    options.table_factory.reset(new BlockedBasedTableFactory(table_options));             

這個 Cache 是不壓縮資料的，使用者可以設定壓縮資料 BlockCache，方法如下：

table_options.block_cache_compressed = cache;           

如果 Cache 為 nullptr，則RocksDB會建立一個，如果想禁用 Cache，可以設定如下 Option：

table_options.no_block_cache = true;           

預設情況下RocksDB用的是 LRUCache，大小是 8MB， 每個 shard 單獨維護自己的 LRU list 和獨立的 hash table，以及自己的 Mutex。

RocksDB還提供了一個 ClockCache，每個 shard 有自己的一個 circular list，有一個 clock handle 會輪詢這個 circular list，尋找過時的 kv，如果 entry 中的 kv 已經被通路過則可以繼續存留，相對于 LRU 好處是無 mutex lock，circular list 本質是 tbb::concurrentmap，從 benchmark 來看，二者命中率相似，但吞吐率 Clock 比 LRU 稍高。

Block Cache初始化之時相關參數：

• capacity 總的記憶體使用量
• num_shards_bits 把 key 的前 n bits 作為 shard id，則總 shard 的數目為 2 ^ num_shards_bits；
• strict_capacity_limit 在一些極端情況下 block cache 的總體使用量可能超過 capacity，如在對 block 進行讀或者疊代讀取的時候可能有插入資料的操作，此時可能因為加鎖導緻有些資料無法及時淘汰，使得總體capacity超标。如果這個選項設定為 true，則此時插入操作是被允許的，但有可能導緻程序 OOM。如果設定為 false，則插入操作會被 refuse，同時讀取以及周遊操作有可能失敗。這個選項對每個 shard 都有效，這就意味着有的 shard 可能記憶體已滿， 别的 shard 卻有很多空閑。
• high_pri_pool_ratio block中為高優先級的 block 保留多少比例的空間，這個選項隻有 LRU Cache 有。

預設情況下 index 和filter block 與 block cache 是獨立的，使用者不能設定二者的記憶體空間使用量，但為了控制 RocksDB 的記憶體空間使用量，可以用如下代碼把 index 和 filter 也放在 block cache 中：

BlockBasedTableOptions table_options;
table_options.cache_index_and_filter_blocks = true;           

Indexes and bloom filters

Index 由 key、offset 和 size 三部分構成，當 Block Cache 增大 Block Size 時，block 個數必會減小，index 個數也會随之降低，如果減小 key size，index 占用記憶體空間的量也會随之降低。

filter是 bloom filter 的實作，如果假陽率是 1%，每個key占用 10 bits，則總占用空間就是 num_of_keys * 10 bits，如果縮小 bloom 占用的空間，可以設定 options.optimize_filters_for_hits = true，則最後一個 level 的 filter 會被關閉，bloom 占用率隻會用到原來的 10% 。

結合 block cache 所述，index & filter 有如下優化選項：

• cache_index_and_filter_blocks 這個 option 如果為 true，則 index & filter 會被存入 block cache，而 block cache 中的内容會随着 page cache 被交換到磁盤上，這就會大大降低 RocksDB的性能，把這個 option 設為 true 的同時也把 pin_l0_filter_and_index_blocks_in_cache 設為 true，以減小對性能的影響。

如果 cache_index_and_filter_blocks 被設定為 false （其值預設就是 false），index/filter 個數就會受 max_open_files 影響，官方建議把這個選項設定為 -1，以友善 RocksDB 加載所有的 index 和 filter 檔案，最大化程式性能。

可以通過如下代碼擷取 index & filter 記憶體量大小：

std::string out;

db->GetProperty(“rocksdb.estimate-table-readers-mem”, &out);

Memtable

memtable 則是寫 buffer，所有 kv 首先都會被寫進 memtable，其 size 是 write_buffer_size。 memtable 占用的空間越大，則寫放大效應越小，因為資料在記憶體被整理好，磁盤上就越少的内容會被 compaction。如果 memtable 磁盤空間增大，則 L1 size 也就随之增大，L1 空間大小受 max_bytes_for_level_base option 控制。

可以通過如下代碼擷取 memtable 記憶體量大小：

std::string out;
    db->GetProperty(“rocksdb.cur-size-all-mem-tables”, &out);           

Blocks pinned by iterators

這部分記憶體空間一般占用總量不多，但是如果有 100k 之多的transactions 發生，每個 iterator 與一個 data block 外加一個 L1 的 data block，是以記憶體使用量大約為 num_iterators * block_size * ((num_levels-1) + num_l0_files)。

可以通過如下代碼擷取 Pin Blocks 記憶體量大小：

table_options.block_cache->GetPinnedUsage();

4. I/O流

4.1. 寫流程

rocksdb寫入時，直接以append方式寫到WAL檔案以及memtable，随即傳回，是以非常快速。memtable達到一定門檻值後切換為Immutable Memtable，隻能讀不能寫。

Immutable memtable觸發門檻值後，背景Flush線程負責按照時間順序将Immutable Memtable刷盤 生成Level 0 SST，Level 0 SST觸發門檻值後，經合并操作(compaction)生成level 1 SST，level 1 SST 合并操作生成level 2 SST，以此類推，生成level n SST。流程如下：

同步寫 與 異步寫

預設情況下，RocksDB 的寫是異步的：僅僅把資料寫進了作業系統的緩存區就傳回了，而這些資料被寫進磁盤是一個異步的過程。如果為了資料安全，可以用如下代碼把寫過程改為同步寫：

rocksdb::WriteOptions write_options;
    write_options.sync = true;
    db->Put(write_options, …);           

這個選項會啟用 Posix 系統的 fsync(...) or fdatasync(...) or msync(..., MS_SYNC) 等函數。

異步寫的吞吐率是同步寫的一千多倍。異步寫的缺點是機器或者作業系統崩潰時可能丢掉最近一批寫請求發出的由作業系統緩存的資料，但是 RocksDB 自身崩潰并不會導緻資料丢失。而機器或者作業系統崩潰的機率比較低，是以大部分情況下可以認為異步寫是安全的。

RocksDB 由于有 WAL 機制保證，是以即使崩潰，其重新開機後會進行寫重放保證資料一緻性。如果不在乎資料安全性，可以把 write_option.disableWAL 設定為 true，加快寫吞吐率。

RocksDB 調用 Posix API fdatasync() 對資料進行異步寫。如果想用 fsync() 進行同步寫，可以設定 Options::use_fsync 為 true。

4.2. 讀流程：

按照 memtable --> Level 0 SST–> Level 1 SST --> … -> Level n SST的

順序讀取資料。這和記錄的新舊順序是一的。是以隻要在目前級别找到記錄，就可以傳回。流程如下：

4.3. Flush流程

簡單來說在RocksDB中，每一個ColumnFamily都有自己的Memtable,當Memtable超過固定大小之後(或者WAL檔案超過限制)，它将會被設定為Immutable Memtable,然後會有背景的線程啟動來重新整理這個Immutable Memtable到磁盤(SST)。

在下面這幾種條件下RocksDB會flush Memtable到磁盤：

• 當某一個Memtable的大小超過write_buffer_size
• 當所有的Memtable的大小超過db_write_buffer_size
• 當WAL檔案的大小超過max_total_wal_size，我們需要清理WAL,是以此時我們需要将此WAL對應的資料都重新整理到磁盤，也是重新整理Memtable

4.4. Compaction操作

Compaction操作的具體作用：

• 資料合并遷移：首先當上層level的sst檔案數量或者大小達到門檻值時，就會觸發指定的sst檔案的合并并遷移到下一層。每一層都會檢查是否需要進行compaction，直到資料遷移到最下層
• 資料真删：LSM樹的特點決定資料的修改和删除都不是即時的真删，而是寫入一條新的資料進行沖抵。這些資料隻會在compaction時才會真正删除（HBase是在major compaction中才會删除，minor compaction不會進行真删），是以compaction能釋放空間，減少LSM樹的空間放大，但是代價就是寫放大，需要根據業務場景要求通過參數來調整兩者之間的關系，平衡業務與性能。
• 冷熱資料管理：RocksDB的資料流向是從Memtable到level 0 最後到 level N，是以資料查詢時也是通過這個路徑進行的。由于業務上查詢大多是熱資料的查詢，是以資料的冷熱管理就顯得很必要，能很大程度上提高查詢效率；而且由于各個level的sst檔案可以使用不同的壓縮算法，是以可以根據自己的業務需求進行壓縮算法的配置，達到最佳性能。

LSM tree相關的經典壓縮算法有下面幾種：經典Leveled，Tiered，Tiered+Leveled，Leveled-N,FIFO。除了這些，RocksDB還額外實作了Tiered+Leveled和termed Level，Tiered termed Universal，FIFO。這些算法各有各的特點，适用于不同的場景，不同的 compaction 算法，可以在空間放大、讀放大和寫放大之間這三個LSM tree的"副作用"中進行取舍，以适應特定的業務場景。大家可以按需選擇，如果沒有特殊需求，開箱即用即可。至于每一種壓縮算法的具體方式以及實作将會在進階特性篇進行講解。

Compaction算法

主要兩個類型的LSM樹合并算法：

Leveled

leveled 合并，這個是RocksDB的預設政策

leveled 算法的特點是以讀放大和寫放大為代價最小化空間放大。

LSM-tree 可以看作是包含若幹 level 的序列，每個 level 是僅包括1個 sorted run。相鄰 level 的大小之比通常被我們稱為 fanout（扇出），當不同 level 之間的 fanout 相同時，LSM-tree 的寫放大最小。compaction 選擇 L(n) 的資料，與原有 L(n+1) 的資料進行合并，得到新的 L(n+1) 資料。每次 compaction 的最大寫放大系數等同于 fanout。

Tiered

一種替代合并政策，有時候被叫做“size tiered”或者“tiered”

Tiered合并通過增加讀放大和空間放大，來最小化寫放大 。

LSM-tree 依然可以看作是包含若幹 level 的序列，每個 level 包括 N 個 sorted run。L(n) 的 sorted run 大小是 L(n-1) 的 N 倍。compaction 通常選擇 L(n) 的資料合并得到新的 sorted run 輸出到 L(n+1)，但并不與 L(n+1) 的已有資料進行合并。每次 compaction 的最大寫放大系數是 1。

兩種算法的主要差别在于，leveled合并傾向于更加頻繁的把小的排序結果合并到大的裡面，而“tiered”等待多個大小接近的排序結果，然後把它們合并到一起。

Tiered+Leveled

Tiered+Leveled會有比leveled更小的寫放大，以及比teired更小的空間放大。

Tiered+Leveled實作方式是一種混合實作，在小的層使用tiered，在大的層使用leveld。具體哪一層切換tiered和leveled可以非常靈活。

RocksDB中的Leveled合并也是Tiered+Leveled。一個memtable落盤過程類似于tiered合并——memtable的輸出在L0建構一個新的排序結果并且不需要讀/重寫L0上已經存在的排序結果。根據level0_file_num_compaction_trigger的配置，L0可以有多個sort run，是以L0是Teired的。 其它層為Leveled。

FIFO Compaction

FIFO Style Compaction 是最簡單的合并政策。很适合用于儲存低開銷的事件日志資料（例如查詢日志）。當檔案總大小超過配置值 CompactionOptionsFIFO::max_table_files_size （預設值為 1GB) 時，最早的 SST 檔案将會被删除。

使用FIFO時，所有的檔案都位于 L0，是以SST檔案過多，導緻查詢性能急劇下降。

開啟 CompactionOptionsFIFO.allow_compaction 參數，可以觸發 L0 IntraCompaction，每次至少選取 level0_file_num_compaction_trigger 個 SST 檔案進行合并，進而減少檔案數量。

FIFO Compaction with TTL

FIFO Compaction with TTL 在 FIFO compaction 的基礎之上，提供 SST 檔案級别的過期删除功能。當 SST 的最新的 key 存在時間超過 mutable_cf_options.ttl，則該 SST 檔案将會在 TTL compaction 中被删除。

Write Stall

Too many memtables

• 寫限速: 如果max_write_buffer_number大于3，将要flush的memtables大于等于max_write_buffer_number - 1，write會被限速。
• 禁寫: memtable個數大于等于max_write_buffer_number，觸發禁寫，等到flush完成後允許寫入

Too many level-0 SST files

• 寫限速: L0檔案數量達到level0_slowdown_writes_trigger，觸發寫限速。
• 禁寫: L0檔案數量達到level0_stop_writes_trigger，禁寫。

Too many pending compaction bytes

• 寫限速: 等待compaction的資料量達到soft_pending_compaction_bytes，觸發寫限速。
• 禁寫: 等待compaction的資料量達到hard_pending_compaction_bytes，觸發禁寫。

4.5. Compression操作

使用options.compression來指定使用的壓縮方法。預設是Snappy。但是大多數情況下LZ4總是比Snappy好。之是以把Snappy作為預設的壓縮方法，是為了與舊版本保持相容。LZ4/Snappy是輕量壓縮，是以在CPU使用率和存儲空間之間能取得一個較好的平衡。

如果你想要進一步減少存儲的使用并且你有一些空閑的CPU，你可以嘗試設定options.bottommost_compression來使用一個更加重量級的壓縮。最底層會使用這個方式進行壓縮。通常最底層會儲存大部分的資料，是以使用者通常會選擇偏向空間的設定，而不是花費cpu在各個層壓縮所有資料。我們推薦使用ZSTD。如果沒有，Zlib是第二選擇。

如果你有大量空閑CPU并且希望同時減少空間和寫放大，把options.compression設定為重量級的壓縮方法，所有層級都生效。推薦使用ZSTD，如果沒有就用Zlib

當然也可以通過一個已經過期的遺留選項options.compression_per_level，你可以有更好的控制每一層的壓縮方式。當這個選項被使用的時候，options.compression不會再生效，但是正常情況下這個是不必要的，除非你有極特殊的需求或者性能優化要求。

最後可以通過把BlockBasedTableOptions.enable_index_compression設定為false來關閉索引的壓縮。

4.5. 離線Ingest

Ingest實作上主要是兩部分：建立SST檔案和導入SST檔案：

4.5.1. 建立SST檔案

建立SST檔案的過程比較簡單，建立了一個SstFileWriter對象之後，就可以打開一個檔案，插入對應的資料，然後關閉檔案即可。 寫檔案的過程比較簡單，但是要注意下面三點：

• 傳給SstFileWriter的Options會被用于指定表類型，壓縮選項等，用于建立sst檔案。
• 傳入SstFileWriter的Comparator必須與之後導入這個SST檔案的DB的Comparator絕對一緻。
• 行必須嚴格按照增序插入

4.5.2. 導入SST檔案

導入SST檔案也非常簡單，需要做的隻是調用IngestExternalFile()然後把檔案位址封裝成vector以及相關的options傳入參數即可。下面是IngestExternalFile()的實作邏輯：

• 把檔案拷貝，或者連結到DB的目錄。
• 阻塞DB的寫入（而不是跳過），因為我們必須保證db狀态的一緻性，是以我們必須確定，我們能給即将導入的檔案裡的所有key都安全地配置設定正确的序列号。
• 如果檔案的key覆寫了memtable的鍵範圍，把memtable進行flush操作。
• 把檔案安排到LSM樹的最合适的層級。
• 給檔案指派一個全局序列号。
• 重新啟動DB的寫操作。

為了減少compaction的壓力，我們總是想将目标的sst檔案寫入最合适的層級，即合适寫入的最低層級，下面三個條件作為限制可以選出合适的層級：

• 檔案可以安排在這個層
• 這個檔案的key的範圍不會覆寫上面任何一層的資料
• 這個檔案的key的範圍不會覆寫目前層正在進行壓縮

另外，5.5以後的新版本的RocksDB的IngestExternalFile加載一個外部SST檔案清單的時候，支援下層導入，意思是如果ingest_behind為true，那麼重複的key會被跳過。在這種模式下，我們總是導入到最底層。檔案中重複的key會被跳過，而不是覆寫已經存在的key。