RocksDB的高级架构

川长思鸟来 2022-05-31 07:17 310阅读 0赞

RocksDB是一个嵌入式的键值存储，其中键和值是任意的字节流。

RocksDB组织所有数据的排序顺序和常用操作Get(key)，Put(key)，Delete(key)和NewIterator()。

RocksDB的三个基本结构是memtable，sstfile和logfile。

memTable是一个存储器内数据结构-新的写入被插入的memTable和任选地写入到日志文件。该日志文件是存储顺序排列的文件。当memtable填满时，它被刷新到存储上的sstfile，相应的日志文件可以被安全的删除。

ssfile的默认格式：

BlockBasedTable是RocksDB中默认的SST表格式。

### BlockBasedTable文件格式 ###

<beginning\_of\_file>  
\[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\] (fixed size; starts at file\_size - sizeof(Footer))  
<end\_of\_file>  
该文件包含调用的内部指针BlockHandles，其中包含以下信息：  
offset: varint64  
size: varint64

varint64的可以参考http://blog.csdn.net/YANG\_Gang2017/article/details/79309581

（1）文件中键/值对的顺序按排序顺序存储，并划分为一系列数据块。这些块在文件的开始处接连出现。每个数据块根据其中的代码进行格式化block\_builder.cc（请参阅文件中的代码注释），然后可以选择压缩。  
（2）在数据块之后，我们存储了一堆元块。下面介绍支持的元块类型。未来可能会添加更多元块类型。每个元块再次格式化block\_builder.cc，然后可选地压缩。  
（3）一个metaindex块为每个其他元块包含一个入口，其中关键是元块的名称，并且该值是BlockHandle指向该元块的值。  
（4）一个index块每个数据块包含一个条目，其中该键是该数据块中的一个字符串>=最后一个键，并且在连续数据块中的第一个键之前。该值是BlockHandle数据块的值。如果使用kTwoLevelIndexSearch作为IndexType，则该index块是索引分区上的第二级索引，即每个条目指向另一个index包含每个数据块一个条目的块。在这种情况下，格式将会是  
\[index block - 1st level\]  
\[index block - 1st level\]  
...  
\[index block - 1st level\]  
\[index block - 2nd level\]  
（5）在该文件的最末端是包含固定长度页脚BlockHandle的的metaindex和索引块以及一个幻数。  
metaindex\_handle: char\[p\]; // Block handle for metaindex  
index\_handle: char\[q\]; // Block handle for index  
padding: char\[40-p-q\]; // zeroed bytes to make fixed length  
// (40==2\*BlockHandle::kMaxEncodedLength)

magic: fixed64; // 0x88e241b785f4cff7 (little-endian)

### Filter 元块 ###

##### 完整过滤器 #####

在这个过滤器中，整个SST文件都有一个过滤块。

##### 分区过滤器 #####

完整的过滤器被分成多个块。将顶级索引块添加到将键映射到相应的筛选器分区。在这里阅读更多。

##### 基于块的过滤器 #####

注意：下面解释了基于块的过滤器，这已被弃用。  
如果在打开数据库时指定了“FilterPolicy”，则每个表中都会存储一个过滤器块。“metaindex”块包含一个从“过滤器”映射的条目。到过滤块的BlockHandle，其中“”是过滤策略Name()方法返回的字符串。  
过滤器块存储一系列过滤器，其中过滤器i包含所有存储在文件偏移量落入范围内的块上的FilterPolicy :: CreateFilter（）输出  
\[ i\*base ... (i+1)\*base-1 \]  
目前“base”是2KB。因此，例如，如果块X和Y在\[0KB .. 2KB-1\]范围内开始，则通过调用FilterPolicy :: CreateFilter（）将X和Y中的所有键转换为过滤器，并且生成的过滤器将作为过滤器块中的第一个过滤器存储。  
过滤器块的格式如下：  
\[filter 0\]  
\[filter 1\]  
\[filter 2\]  
...

\[filter N-1\]

\[offset of filter 0\] : 4 bytes  
\[offset of filter 1\] : 4 bytes  
\[offset of filter 2\] : 4 bytes  
...

\[offset of filter N-1\] : 4 bytes

\[offset of beginning of offset array\] : 4 bytes  
lg(base) : 1 byte

过滤器块末尾的偏移量数组允许从数据块偏移量高效地映射到相应的滤波器。

### Properties 元块 ###

这个元块包含一堆属性。key是属性名，value是属性值。

统计块格式如下：  
\[prop1\] (Each property is a key/value pair)  
\[prop2\]  
...  
\[propN\]  
属性保证排序，不重复。  
默认情况下，每个表提供以下属性。  
data size // the total size of all data blocks.  
index size // the size of the index block.  
filter size // the size of the filter block.  
raw key size // the size of all keys before any processing.  
raw value size // the size of all value before any processing.  
number of entries  
number of data blocks  
RocksDB还为用户提供了“回调”来收集他们关于这个表的感兴趣的属性。

### Compression Dictionary 元块 ###

此元区块包含用于在压缩/解压每个块之前填充压缩库的字典。它的目的是解决小数据块上的动态字典压缩算法的一个基本问题：字典是在块上单次传递时建立的，因此小数据块总是有小而无效的字典。  
我们的解决方案是使用从先前看到的块中采集的数据构建的字典来初始化压缩库。然后将该字典存储在文件级元块中供在解压缩期间使用。这个字典的大小的上限是可以通过配置的CompressionOptions::max\_dict\_bytes。默认情况下它是零，即块不会被生成或存储。目前支持此功能有kZlibCompression，kLZ4Compression，kLZ4HCCompression，和kZSTDNotFinalCompression。  
更具体地说，压缩字典仅在压缩到最低级别时建立，其中数据是最大且最稳定的。为避免多次迭代输入数据，字典仅包含来自子压缩的第一个输出文件的样本。然后，字典被应用并存储在所有后续输出文件的元块中。请注意，字典不会应用于或存储在第一个文件中，因为其文件内容尚未完成，直到文件完全处理完毕。  
目前，采样是一致随机的，每个采样是64个字节。在选择样本偏移量时，我们并不知道输出文件的大小，所以我们假定它会达到最大值，这通常是真实的，因为它是压缩比中的第一个文件。在文件较小的情况下，一些采样间隔将指EOF以外的偏移量，这就意味着字典会比较小CompressionOptions::max\_dict\_bytes。 sstfile中的数据被分类以便于查找keys。