[TOC]

參考

1. Rocksdb的SST
2. 深入 LevelDB 數(shù)據(jù)文件 SSTable 的結(jié)構(gòu)
3. Rocksdb BlockBasedTable Format
4. 淺析RocksDB的SSTable格式
 5. RocksDB. BlockBasedTable源碼分析
 6. leveldb handbook
7. RocksDB(MyRocks)源碼學習

0. 前言

本文大部分內(nèi)容直接摘抄自 LevelDB handbook，同時結(jié)合了其他大神的學習分享

1. 總體結(jié)構(gòu)

RocksDB sst 文件結(jié)構(gòu)圖

偽碼表示文件架構(gòu)組織如下：

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]                  (see section: "filter" Meta Block)
[meta block 2: stats block]                   (see section: "properties" Meta Block)
[meta block 3: compression dictionary block]  (see section: "compression dictionary" Meta Block)
[meta block 4: range deletion block]          (see section: "range deletion" Meta Block)
...
[meta block K: future extended block]  (we may add more meta blocks in the future)
[metaindex block]
[index block]
[Footer]                               (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

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

名稱	占用空間	說明
Footer	固定48字節(jié)	指出 IndexBlock 和 MetaIndexBlock 在文件中的偏移量信息，它是元信息的元信息，它位于 sstable 文件的尾部
IndexBlock	占用一個 block 空間	記錄了 DataBlock 相關的元信息
MetaIndexBlock	占用一個 block 空間	各個元信息的Block，包括Filter、Properties(整個table的屬性信息)、Compression dictionary、Range deletion tombstone
MetaBlock	可能占用多個 block空間	存儲布隆過濾器的二進制數(shù)據(jù) 及其他元信息數(shù)據(jù)
DataBlock	可能占用多個 block空間	存儲實際的數(shù)據(jù)即鍵值對內(nèi)容

一個 block默認的block大小為4k，通常設置為64k（對應配置項：table_options.block_size）。
rocksdb的 sst 文件源于leveldb，主要的區(qū)別就是在于 MetaBlock 部分，rocksdb 的內(nèi)容更多，leveldb 的 MetaBlock 當前只有 Filter 的內(nèi)容。

這里有個疑問：IndexBlock 僅一個，是否夠用呢？這個疑問放到下一篇文章進行解答

2. 數(shù)據(jù)結(jié)構(gòu)

2.1. Block 結(jié)構(gòu)

5個部分的數(shù)據(jù)結(jié)構(gòu)，除了 Footer，其他的物理結(jié)構(gòu)都是 Block 形式。
Block 在硬盤上存儲的時候，會在實際數(shù)據(jù)之后加上5個字節(jié)的額外內(nèi)容：compression type、crc

Block 結(jié)構(gòu)在磁盤的存儲格式

2.1.1. DataBlock

data block中存儲的數(shù)據(jù)是leveldb中的keyvalue鍵值對。其中一個data block中的數(shù)據(jù)部分（不包括壓縮類型、CRC校驗碼）按邏輯又以下圖進行劃分：

DataBlock 在磁盤的存儲格式

struct Entry {
  varint sharedKeyLength;
  varint unsharedKeyLength;
  varint valueLength;
  byte[] unsharedKeyContent;
  byte[] valueContent;
}

struct DataBlock {
  Entry[] entries;
  int32 [] restartPointOffsets;
  int32 restartPointCount;
}

一個 DataBlock 的默認大小只有 4K 字節(jié)，所以里面包含的鍵值對數(shù)量通常只有幾十個。如果單個鍵值對的內(nèi)容太大一個 DataBlock 裝不下咋整？
這里就必須糾正一下，DataBlock 的大小是 4K 字節(jié)，并不是說它的嚴格大小，而是在追加完最后一條記錄之后發(fā)現(xiàn)超出了 4K 字節(jié)，這時就會再開啟一個 DataBlock。這意味著一個 DataBlock 可以大于 4K 字節(jié)，如果 value 值非常大，那么相應的 DataBlock 也會非常大。DataBlock 并不會將同一個 Value 值分塊存儲。

第一部分(Entry)用來存儲key-value數(shù)據(jù)。由于sstable中所有的key-value對都是嚴格按序存儲的，用了節(jié)省存儲空間，并不會為每一對key-value對都存儲完整的key值，而是存儲與上一個key非共享的部分，避免了key重復內(nèi)容的存儲。

每間隔若干個key-value對，將為該條記錄重新存儲一個完整的key。重復該過程（默認間隔值為16），每個重新存儲完整key的點稱之為Restart point。

Restart point的目的是在讀取sstable內(nèi)容時，加速查找的過程。
由于每個Restart point存儲的都是完整的key值，因此在sstable中進行數(shù)據(jù)查找時，可以首先利用restart point點的數(shù)據(jù)進行鍵值比較，以便于快速定位目標數(shù)據(jù)所在的區(qū)域；
當確定目標數(shù)據(jù)所在區(qū)域時，再依次對區(qū)間內(nèi)所有數(shù)據(jù)項逐項比較key值，進行細粒度地查找；
該思想有點類似于跳表中利用高層數(shù)據(jù)迅速定位，底層數(shù)據(jù)詳細查找的理念，降低查找的復雜度。

每一個數(shù)據(jù)項(Entry)的格式如下:

image

一個Entry分為5部分內(nèi)容：

與前一條記錄key共享部分的長度，為0則表示該 Entry 是一個重啟點；
與前一條記錄key不共享部分的長度；
value長度；
與前一條記錄key非共享的內(nèi)容；
value內(nèi)容；

舉例如下：

restart_interval=2
entry one  : key=deck,value=v1
entry two  : key=dock,value=v2
entry three: key=duck,value=v3

重啟點存儲格式

三組entry按上圖的格式進行存儲。值得注意的是restart_interval為2，因此每隔兩個entry都會有一條數(shù)據(jù)作為restart point點的數(shù)據(jù)項，存儲完整key值。因此entry3存儲了完整的key。

此外，第一個restart point為0（偏移量），第二個restart point為16，restart point共有兩個，因此一個DataBlock數(shù)據(jù)段的末尾添加了下圖所示的數(shù)據(jù)：

DataBlock 尾部數(shù)據(jù)段格式

尾部數(shù)據(jù)記錄了每一個restart point的值（每個重啟點都是4字節(jié)），以及所有restart point的個數(shù)（4字節(jié)）。

2.1.2. MetaBlock 結(jié)構(gòu)

MetaBlock 中，LevelDB 僅有 Filter 數(shù)據(jù)，RocksDB 除了 Filter 還有其他的元信息數(shù)據(jù)。這里只分析下 Filter 數(shù)據(jù) - FilterBlock。

為了加快sstable中數(shù)據(jù)查詢的效率，在直接查詢datablock中的內(nèi)容之前，leveldb首先根據(jù)filter block中的過濾數(shù)據(jù)判斷指定的datablock中是否有需要查詢的數(shù)據(jù)，若判斷不存在，則無需對這個datablock進行數(shù)據(jù)查找。

filter block存儲的是data block數(shù)據(jù)的一些過濾信息。這些過濾數(shù)據(jù)一般指代布隆過濾器的數(shù)據(jù)，用于加快查詢的速度，關于布隆過濾器的詳細內(nèi)容，可以見《Leveldb源碼分析 - 布隆過濾器》。

struct FilterEntry {
  byte[] rawbits;
}

struct FilterBlock {
  FilterEntry[n] filterEntries;
  int32[n] filterEntryOffsets;
  int32 offsetArrayOffset;
  int8 baseLg;  // 分割系數(shù)
}

FilterBlock 數(shù)據(jù)存儲格式

filter block存儲的數(shù)據(jù)主要可以分為兩部分：（1）過濾數(shù)據(jù)（2）索引數(shù)據(jù)。

其中索引數(shù)據(jù)中，filter i offset表示第i個filter data在整個filter block中的起始偏移量，filter offset's offset表示filter block的索引數(shù)據(jù)在filter block中的偏移量。

FilterBlock 存儲舉例

FilterBlock 讀取舉例

在讀取filter block中的內(nèi)容時，可以首先讀出filter offset's offset的值，然后依次讀取filter i offset，根據(jù)這些offset分別讀出filter data。

Base Lg默認值為11，表示每2KB的數(shù)據(jù)，創(chuàng)建一個新的過濾器來存放過濾數(shù)據(jù)。這里的 2K 字節(jié)的間隔是嚴格的間隔，這樣才可以通過 DataBlock 的偏移量和大小來快速定位到相應的布隆過濾器的位置 FilterOffset，再進一步獲得相應的布隆過濾器位圖數(shù)據(jù)。

一個sstable只有一個filter block，其內(nèi)存儲了所有block的filter數(shù)據(jù). 具體來說，filter_data_k 包含了所有起始位置處于 [basek, base(k+1)]范圍內(nèi)的block的key的集合的filter數(shù)據(jù)，按數(shù)據(jù)大小而非block切分主要是為了盡量均勻，以應對存在一些block的key很多，另一些block的key很少的情況。

至于為什么 LevelDB 的布隆過濾器數(shù)據(jù)不是整個塊而是分成一段一段的，這個原因筆者也沒有完全整明白，估計是為了防止 bit 位太多之后，訪問 bit 數(shù)組的時候容易造成 cache miss。期待有讀者可以提供更多思路。

2.1.3. MetaIndexBlock 結(jié)構(gòu)

對于只有 FilterBlock 的情況下，meta index block用來存儲filter block在整個sstable中的索引信息。

meta index block只存儲一條記錄：

該記錄的key為："filter."與過濾器名字組成的常量字符串

該記錄的value為：filter block在sstable中的索引信息序列化后的內(nèi)容，索引信息包括：（1）在sstable中的偏移量（2）數(shù)據(jù)長度。

2.1.4. IndexBlock 結(jié)構(gòu)

與meta index block類似，index block用來存儲所有data block的相關索引信息。

indexblock包含若干條記錄，每一條記錄代表一個data block的索引信息。

一條索引包括以下內(nèi)容：

key，取值是大于等于其索引block的最大key，并且小于下一個block的最小key；
該data block起始地址在sstable中的偏移量；
該data block的大小；

IndexBlock和 DataBlock 一樣，采取了前綴壓縮，只不過間隔為2（DataBlock 默認為16）

這里有兩個點值得注意：
1. 為什么BlockHandle的offset和size的單位是字節(jié)數(shù)而不是block？
因為SSTable中的block大小是不固定的，雖然option中可以指定block_size參數(shù)，但SSTable中存儲數(shù)據(jù)時，并未嚴格按照block_size對齊，所以offset和size指的是偏移字節(jié)數(shù)和長度字節(jié)數(shù)；跟Innodb中的B+樹索引block偏移有區(qū)別。這樣做主要有兩個原因：

RocksDB可以存儲任意長度的key和任意長度的value（不同于Innodb，限制每行數(shù)據(jù)的大小為16384個字節(jié)），而同一個key-value是不能跨block存儲的，極端情況下，比如我們的單個 value 就很大，已經(jīng)超過了 block_size，那么對于這種情況，SSTable 就沒法進行存儲了。所以通常，實際的 Block 大小都是要略微大于 block_size 的；
從另外一個角度看，如果嚴格按照block_size對齊存儲數(shù)據(jù)，必然有很多block通過補0的方式對齊，浪費存儲空間；

2. 為什么key不是采用其索引的DataBlock的最大key？
主要目的是節(jié)省空間；假設其索引的block的最大key為"acknowledge"，下一個block最小的key為"apple"，如果DataBlockIndex的key采用其索引block的最大key，占用長度為len("acknowledge")；采用后一種方式，key值可以為"ad"（"acknowledge" < "ad" < "apple"），長度僅為2，并且檢索效果是一樣的。

2.5. Footer 結(jié)構(gòu)

以上各部分都是 Block 的結(jié)構(gòu)，只有 Footer 不同，是一個定長的格式。

//  見format.h
class Footer {
public:
  Footer() : Footer(kInvalidTableMagicNumber, 0) {}
  Footer(uint64_t table_magic_number, uint32_t version);
......
private:
  uint32_t version_;
  ChecksumType checksum_;
  BlockHandle metaindex_handle_;
  BlockHandle index_handle_;
  uint64_t table_magic_number_ = 0;
};

序列化后，F(xiàn)ooter的長度固定，為48個字節(jié)（舊）或53字節(jié)（新），格式如下：

// 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字節(jié)，進而得到了 Footer 信息。

2.6. BlockHandle 結(jié)構(gòu)

另外可以發(fā)現(xiàn)，MetaIndexBlock、IndexBlock和 Footer 中，起到指針作用的value 結(jié)構(gòu)都是offset+value，對應的就是 BlockHandle 的結(jié)構(gòu)。

//  見format.h
class BlockHandle {
public:
  BlockHandle();
  BlockHandle(uint64_t offset, uint64_t size);
......
private:
  uint64_t offset_;
  uint64_t size_;
}

為了節(jié)省空間，BlockHandle 的offset 和 size 兩個字段，都是使用 varint64編碼后，連續(xù)存放在一起，編碼后的大小<=20字節(jié)。

void BlockHandle::EncodeTo(std::string* dst) const {
  // Sanity check that all fields have been set
  assert(offset_ != ~static_cast<uint64_t>(0));
  assert(size_ != ~static_cast<uint64_t>(0));
  PutVarint64Varint64(dst, offset_, size_);
}

3. SST 讀寫流程

3.1. 寫流程

寫 SST 文件的邏輯，主要在BlockBasedTableBuilder類以下兩個函數(shù)。

Flush 接口：當一個 DataBlock 滿了之后，就需要將 DataBlock輸入到磁盤。此時會根據(jù) Block 的 offset 去觸發(fā) FilterBlock 的生成（當超過2^BaseLg，就會創(chuàng)建新的 FilterBlock）
Finish 接口：當結(jié)束的時候，會依次把IndexBlock、MetaBlock、MetaIndexBlock、Footer 寫入文件，見下圖：

MetaBlock 的寫入順序

整體流程如下：

判斷Key的類型，如果是范圍刪除類型，即kTypeRangeDeletion，寫入range_del_block
如果是值類型，即需要被寫入Data Block的Key，需要判斷被寫入的Block是否已經(jīng)達到了限定的大小，如果超過了限定的數(shù)值，需要被Flush
將Key-Value寫入Data Block:r->data_block.Add(key, value)
每次寫入需要更新SST的Version元信息，即SST的邊界的最大、最小Key：smallest_key、largest_key
完成Meta Block 和MetaIndex Block的寫入，保存的是一個handle，即一個block的指針，包括偏移量offset_和size_
更新Version的元信息

3.1. 讀流程

RocksDB 讀數(shù)據(jù)首先在Memtable中查找，之后是Immutable Memtable，最后再去SST文件中查找。只有當 Memtable 和Immutable Memtable都沒有找到時，才會進入到 SST 文件的讀流程。

通過Version中記錄的信息遍歷Level中的所有SST文件，利用SST文件記錄的邊界最大，最小key- smallest_key和largest_key來判斷查找的key是否有可能存在
如果在該Level中可能存在，調(diào)用TableReader的接口來查找SST文件
- 首先通過SST文件中的Filter來初判key是否存在（查詢方式見 FilterBlock 小節(jié)的介紹）
- 如果存在key存在，進入Data Block中查找
- 在Data Block利用Block的迭代器BlockIter利用二分查找BinarySeek或者前綴查找PrefixSeek
如果查找成功則返回，如果該Level不存在查找的Key，繼續(xù)利用Version中的信息進行下一個Level的查找，直到最大的一個Level

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

RocksDB block-based SST 文件詳解

RocksDB block-based SST 文件詳解

參考

0. 前言

1. 總體結(jié)構(gòu)

2. 數(shù)據(jù)結(jié)構(gòu)

2.1. Block 結(jié)構(gòu)

2.1.1. DataBlock

2.1.2. MetaBlock 結(jié)構(gòu)

2.1.3. MetaIndexBlock 結(jié)構(gòu)

2.1.4. IndexBlock 結(jié)構(gòu)

2.5. Footer 結(jié)構(gòu)

2.6. BlockHandle 結(jié)構(gòu)

3. SST 讀寫流程

3.1. 寫流程

3.1. 讀流程

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

RocksDB block-based SST 文件詳解

參考

0. 前言

1. 總體結(jié)構(gòu)

2. 數(shù)據(jù)結(jié)構(gòu)

2.1. Block 結(jié)構(gòu)

2.1.1. DataBlock

2.1.2. MetaBlock 結(jié)構(gòu)

2.1.3. MetaIndexBlock 結(jié)構(gòu)

2.1.4. IndexBlock 結(jié)構(gòu)

2.5. Footer 結(jié)構(gòu)

2.6. BlockHandle 結(jié)構(gòu)

3. SST 讀寫流程

3.1. 寫流程

3.1. 讀流程

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av