leveldb之读过程

发表于 2021-09-29 更新于 2020-12-21 分类于 leveldb 阅读次数：

LevelDB 首先会去查看内存中的 Memtable，如果 Memtable 中包含 key 及其对应的value，则返回 value 值即可；

如果在 Memtable 没有读到key，则接下来到同样处于内存中的 Immutable Memtable 中去读取，类似地，如果读到就返回，若是没有读到,那么只能万般无奈下从磁盘中的大量SSTable文件中查找。

sstable文件由data block、meta block、metaindex block、index blcok和footer组成。默认大小2MB。

如果数据不在内存中的组件中，那就需要在磁盘的sstable文件中查找了，基于B+树思想的存储引擎，利用索引可以直接定位到具体的哪个磁盘块，而LSM树的存储引擎需要遍历多个sstable文件才能确定数据在哪个磁盘块，读性能自然就不如B+树了。在介绍如何在磁盘上查找含有指定Key的sstable之前先介绍一个重要的数据结构：

struct FileMetaData {
  int refs;
  int allowed_seeks;          // Seeks allowed until compaction
  uint64_t number;
  uint64_t file_size;         // File size in bytes
  InternalKey smallest;       // Smallest internal key served by table
  InternalKey largest;        // Largest internal key served by table
  FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }
};

FileMetaData数据结构保存了sstable文件的元数据，包括文件的名字number、key的范围、引用次数。每个sstable文件对应一个FileMetaData，每一层的sstable对应的FileMetaData用std::vecotr保存，定位key在磁盘的哪个sstable文件中需要逐层遍历(level-by-level)，另外L0层因为sstable文件之间可能存在key重叠，所以L0层处理方式与其它层不同，下面介绍具体的查找过程：

1、先定位key可能在哪些sstable文件中。这里的定位利用了上面的FileMetaData结构体里的smallest、largest字段，如果在这个范围里，该文件的FileMetaData加入一个vcetor tmp保存，每一层有很多的sstable文件，而且key可能存在多个版本，所以tmp里面可能存在很多sstable文件，如何确定最新的版本在哪个文件里呢？查找的原则应该是先从最新的sstable文件中查找，对于L0层，LevelDB做了优化，这里要说明一下，sstable文件是用uint64_t number命名的，而且越新的数据number越大，所以vector tmp按照FileNumber排序。非L0层的sstable文件之间key不会重叠，所以可以利用二分查找定位sstable。

2、在第一步定位了key可能存在的sstable之后，第二步需要定位key在sstable文件的哪个data block里面，图中sstable格式里有一个重要的模块：index block。

逻辑布局

index block存储了data block的索引，为了加速读性能，leveldb也做了优化，把经常访问的sstable的index block缓存在cache中，关于cache的知识点后续会介绍。利用index block可以快速定位key可能存在哪个data block中。如何确定key到底在不在data block呢，LevelDB利用bloom filter，如果通过bloom filter得出key不在此data block中，那么该key 肯定不在此data block中，则data not found；如果通过bloom filter得出key在此data block中，还不能完全肯定在此data block中，还需要去遍历该data block。

如果在immutable memtable flush to磁盘之前，new创建的mutable memtable已经被填满，insert操作将会被暂停，stall

当前的LSM设计要承受高昂的压缩成本，因为压缩涉及迭代不可变的内存表跳过列表，将数据序列化为磁盘兼容（SSTable）格式。

序列化：将对象转化为字节序列的过程，数据持久化为sstable格式。为什么要进行序列化？为了数据持久化。

磁盘的sstable包含多个level，最坏情况下有可能触发链式compaction操作，使前台更新stall