RocksDB在磁盘上的file结构sstfile由block作为基本单位组成，一个sstfile结构如下：

<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]                              
<end_of_file>

其中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