以RocksDB为存储引擎的MyRocks是近几年流行起来的MySQL分支，在Facebook等公司广泛使用，网易杭研的数据库内核团队从2018年初开始系统研究MyRocks，目前已在内部进行小范围推广使用，效果比较理想。

在调研、测试和试用期间，积累了一些经验，包括技术实现等。本系列想跟大家分享我们组内小伙伴做的LevelDB调研输出，这是第二篇，详细介绍LevelDB读写流程。

第一篇基础篇链接：

温正湖：LevelDB设计与实现 - 基础篇​zhuanlan.zhihu.com

写操作

在讲LevelDB写操作之前，先讲讲B+树型存储引擎存在的不足，这有利于理解LevelDB底层存储思想。

我们知道磁盘IO是主要影响数据库性能的因素，在没有随机写的情况下，B+树的性能还是可以的，当有大量的随机写发生时，B树叶节点会分裂，如图4所示key值跨度很大，新插入的数据在磁盘上距离很远，会产生大量的随机写IO，非常影响性能。LevelDB底层存储采用了LSM树的思想，下图演示LSM树是如何工作的。

图5是LSM Tree工作的过程，插入的数据是追加写的方式产生新的数据文件(SST),后台的compaction线程会合并有重叠key的SST文件。N行的随机写会产生很少的磁盘IO。LSM Tree不会像B+Tree那样原地更新数据，磁盘上的SST文件只读不能修改，对写多读少的场景很友好。

LevelDB写的逻辑如下：

1. 将key-value封装成WriteBatch；
2. 循环检查当前DB的状态，确定策略(DBImpl::MakeRoomForWrite()):
3. 如果当前L0层的文件数目达到了kL0_SlowdownWritesTrigger(8)阈值，则会延迟1s写入，该延迟只发生一次；
4. 如果当前memtable的size未达到阈值write_buffer_size(默认4MB)，则允许写入；
5. 如果memtable的size已经达到阈值，但immutable memtable仍然存在，则等待compaction将其dump完成；
6. 如果L0文件数目达到了kL0_StopWritesTrigger(12)，则等待compaction memtable完成；
7. 上述条件都不满足，则memtable已经写满，并且immutable memtable不存在，则将当前memetable置成immutable memtable，产生新的memtable和log file，主动触发compaction，允许该次写。
8. 设置WriteBatch的SequenceNumber;
9. 先将WriteBatch中的数据写入log(Log::AddRecord());
10. 然后将WriteBatch的数据写入memetable，即遍历WriteBatch解析出key/value/valuetype，Delete操作只写入删除的key，ValueType是KTypeDeletion，表示key以及被删除，后续compaction会删除此key-value。
11. 更新SequenceNumber（last_sequence + WriteBatch::count()）。

为了提高写入效率，LevelDB会把多个写线程提交的key-value封装成一个WriteBatch一次性写入。WriteBatch的结构如图3中WriteBatch所示。log操作在第2节WAL中已经介绍了，这里重点介绍写入memtable的操作。

用户的数据写入到log日志后，还要写入一个memtable的结构中，LevelDB利用skiplist实现了memtable，在memtable内key是有序的。immutable memtable与memtable结构是一样的，只提供读不允许写入。用户的数据已经封装在WriteBatch中，在插入memtable时，需要遍历WriteBatch,decode每个key-value。在memtable中，key-value的格式如下：

插入读取都涉及到key的比较，LevelDB提供了默认的实现Comparator,Comparator是一个接口，用户也可以自定义比较函数。LevelDB实现了两个Comparator: BytewiseComparatorImpl和InternalKeyComparator。BytewiseComparatorImpl实现了字节序比较，InternalKeyComparator封装了一层Comparator，当key相等时，还会比较SequenceNumber。

读操作

读操作基于user_key可以找到当前最大SequenceNumber的数据，也支持获取指定快照的数据。读操作逻辑如下：

1. 如果ReadOption指定了snapshot，则将snapshot的Sequence Number作为最大的Sequence Number，否则，将当前最大的Sequence Number(VersionSet::last_sequence_number)作为最大的Sequence Number。
2. 在memtable中查找(Memtable::Get())。
3. 如果在memtable中未找到，并且存在immutable memtable，就在immutable memtable中查找(Memtable::Get())。
4. 如果(3)仍未找到，在sstable中查找(VersionSet::Get())，从L0开始，每个level上依次查找，一旦找到，即返回。
5. 首先找出level上可能包含key的sstable，FileMetaData结构体内包含每个sstable的key范围。
6. L0的查找只能顺序遍历每个file_[0](FileMetaData的成员),因为L0层的sstable文件之间可能存在重叠的key。在L0层可能找到多个sstable。
7. 非L0层的查找，对file_[i]基于FileMetaData::largest做二分查找即可定位到level中可能包含key的sstable。非L0上sstable之间key不会重叠，所以最多找到一个sstable。
8. 如果该level上没有找到可能的sstable,跳过，否则，对要进行查找的sstable获得其Iterator，做seek()操作。
9. seek()成功检查有效性，依据ValueType判断是否是有效的数据：
10. kTypeValue: 返回对应的value数据。
11. kTypeDeletion: 返回data not exist。

以上就是根据指定key查找sstable的过程。下面用一张图概括Get操作。

在讲解具体的读取sstable文件前，有必要介绍一下sstable文件的格式。

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

1. data block: key-value存储部分，按key有序排列,data block内部的格式如图7左侧。LevelDB采用了前缀压缩，每16个key-value记录一次重启点restart。data block默认大小4KB。
2. meta block：存储key-value的filter,默认是bloom filter。
3. metaindex blokc: 指向meta block的索引。
4. index block:指向data block的索引。
5. footer: 索引metaindex block 和 index block。

如果数据不在内存中的组件中，那就需要在磁盘的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) { }
};

这个数据结构保存了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里面，图9的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。

未完待续...