sstable

• 压缩类型
• CRC校验码压缩类型说明了Block中存储的数据是否进行了数据压缩，若是，采用了哪种算法进行压缩。leveldb中默认采用Snappy算法进行压缩。

• data block : 用来存储key value数据对；
• filter block :用来存储一些过滤器相关的数据（布隆过滤器），但是若用户不指定leveldb使用过滤器，leveldb在该block中不会存储任何内容；
• meta Index block : 用来存储filterblock的索引信息（索引信息指在该sstable文件中的偏移量以及数据长度）；
• index block ：index block中用来存储每个data block的索引信息；
• footer : 用来存储meta index block及index block的索引信息；

注解

leveldb设计Restartpoint的目的是在读取sstable内容时，加速查找的过程。

由于每个Restartpoint存储的都是完整的key值，因此在sstable中进行数据查找时，可以首先利用restartpoint点的数据进行键值比较，以便于快速定位目标数据所在的区域；

当确定目标数据所在区域时，再依次对区间内所有数据项逐项比较key值，进行细粒度地查找；

该思想有点类似于跳表中利用高层数据迅速定位，底层数据详细查找的理念，降低查找的复杂度。

• 与前一条记录key共享部分的长度；
• 与前一条记录key不共享部分的长度；
• value长度；
• 与前一条记录key非共享的内容；
• value内容；例如：

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

注解

leveldb中，特殊的sstable文件格式设计简化了许多操作，例如：

索引和BloomFilter等元数据可随文件一起创建和销毁，即直接存在文件里，不用加载时动态计算，不用维护更新

• 该记录的key为："filter."与过滤器名字组成的常量字符串
• 该记录的value为：filterblock在sstable中的索引信息序列化后的内容，索引信息包括：（1）在sstable中的偏移量（2）数据长度。

• data block i 中最大的key值；
• 该data block起始地址在sstable中的偏移量；
• 该data block的大小；

注解

其中，data block i最大的key值还是index block中该条记录的key值。

如此设计的目的是，依次比较indexblock中记录信息的key值即可实现快速定位目标数据在哪个data block中。

• memory db将内容持久化到磁盘文件中时，会创建一个sstable进行写入；
• leveldb后台进行文件compaction时，会将若干个sstable文件的内容重新组织，输出到若干个新的sstable文件中；

// tWriter wraps the table writer. It keep track of file descriptor
// and added key range.
type tWriter struct {
    t *tOps
 
    fd storage.FileDesc // 文件描述符
    w  storage.Writer   // 文件系统writer
    tw *table.Writer
 
    first, last []byte
}

• 该迭代器可以是一个内存数据库的迭代器，写入情景对应着上述的第一种情况；
• 该迭代器也可以是一个sstable文件的迭代器，写入情景对应着上述的第二种情况；

注解

sstable的元数据包括：（1）文件编码（2）大小（3）最大key值（4）最小key值

故，理解tableWriter的Append函数是理解整个写入过程的关键。

// Writer is a table writer.
type Writer struct {
    writer io.Writer
    // Options
    blockSize   int // 默认是4KiB
 
    dataBlock   blockWriter // data块Writer
    indexBlock  blockWriter // indexBlock块Writer
    filterBlock filterWriter // filter块Writer
    pendingBH   blockHandle
    offset      uint64
    nEntries    int // key-value键值对个数
}

• 若本次写入为新dataBlock的第一次写入，则将上一个dataBlock的索引信息写入；
• 将keyvalue数据写入datablock;
• 将过滤信息写入filterBlock；
• 若datablock中的数据超过预定上限，则标志着本次datablock写入结束，将内容刷新到磁盘文件中；

func (w *Writer) Append(key, value []byte) error {
    w.flushPendingBH(key)
    // Append key/value pair to the data block.
    w.dataBlock.append(key, value)
    // Add key to the filter block.
    w.filterBlock.add(key)
 
    // Finish the data block if block size target reached.
    if w.dataBlock.bytesLen() >= w.blockSize {
        if err := w.finishBlock(); err != nil {
            w.err = err
            return w.err
        }
    }
    w.nEntries++
    return nil
}

• 封装dataBlock，记录restart point的个数；
• 若dataBlock的数据需要进行压缩（例如snappy压缩算法），则对dataBlock中的数据进行压缩；
• 计算checksum；
• 封装dataBlock索引信息（offset，length）；
• 将datablock的buffer中的数据写入磁盘文件；
• 利用这段时间里维护的过滤信息生成过滤数据，放入filterBlock对用的buffer中；Close

• 若buffer中仍有未写入的数据，封装成一个datablock写入；
• 将filterBlock的内容写入磁盘文件；
• 将filterBlock的索引信息写入metaIndexBlock中，写入到磁盘文件；
• 写入indexBlock的数据；
• 写入footer数据；至此为止，所有的数据已经被写入到一个sstable中了，由于一个sstable是作为一个memorydb或者Compaction的结果原子性落地的 ，因此在sstable写入完成之后，将进行更为复杂的leveldb的版本更新 ，将在接下来的文章中继续介绍。

• 首先判断“文件句柄”cache中是否有指定sstable文件的文件句柄，若存在，则直接使用cache中的句柄；否则打开该sstable文件，按规则读取该文件的元数据 ，将新打开的句柄存储至cache中；
• 利用sstable中的indexblock进行快速的数据项位置定位，得到该数据项有可能存在的两个 datablock；
• 利用index block中的索引信息，首先打开第一个可能的data block；
• 利用filter block中的过滤信息，判断指定的数据项是否存在于该datablock中，若存在，则创建一个迭代器对datablock中的数据进行迭代遍历，寻找数据项；若不存在，则结束该datablock的查找；
• 若在第一个datablock中找到了目标数据，则返回结果；若未查找成功，则打开第二个datablock，重复步骤4；
• 若在第二个datablock中找到了目标数据，则返回结果；若未查找成功，则返回Not Found错误信息；缓存

• sstable文件句柄及其元数据；
• data block中的数据；

• 读取文件的最后48字节的利用，即Footer 数据；
• 读取Footer数据中维护的(1) Meta Index Block(2) IndexBlock两个部分的索引信息并记录，以提高整体的查询效率；
• 利用meta index block的索引信息读取该部分的内容；
• 遍历meta index block，查看是否存在“有用”的filterblock的索引信息，若有，则记录该索引信息；若没有，则表示当前sstable中不存在任何过滤信息来提高查询效率；数据项的快速定位

注解

值得注意的是，与data block一样，indexblock中的索引信息同样也进行了key值截取，即第二个索引信息的key并不是存储完整的key，而是存储与前一个索引信息的key不共享的部分，区别在于datablock中这种范围的划分粒度为16，而index block中为2 。

也就是说，indexblock连续两条索引信息会被作为一个最小的“比较单元“，在查找的过程中，若第一个索引信息的key小于目标数据项的key，则紧接着会比较第三条索引信息的key。

这就导致最终目标数据项的范围区间为某”两个“data block。

• 若过滤数据显示目标数据不存在于datablock中，则目标数据一定不 存在于data block中；
• 若过滤数据显示目标数据存在于datablock中，则目标数据可能存在 于data block中；

• 索引数据
• 过滤数据