leveldb(3) 元数据

Hbase有存储在zookeeper的metadata来定位RegionServer，

而LevelDB也通过元数据管理模块去感知每一层有哪些SST文件；快速的定位某条数据所在的SST文件；以及重启后恢复到之前的状态。

作用概括如下：

LeveDB用 Version 表示一个版本的元信息，Version中主要包括一个FileMetaData指针的二维数组，分层记录了所有的SST文件信息。 FileMetaData 数据结构用来维护一个文件的元信息，包括文件大小，文件编号，最大最小值，引用计数等，其中引用计数记录了被不同的Version引用的个数，保证被引用中的文件不会被删除。

VersionSet 是一个Version构成的双向链表，这些Version按时间顺序先后产生，记录了当时的元信息，链表头指向当前最新的Version，同时维护了每个Version的引用计数，被引用中的Version不会被删除，其对应的SST文件也因此得以保留，通过这种方式，使得LevelDB可以在一个稳定的快照视图上访问文件。VersionSet中除了Version的双向链表外还会记录一些如LogNumber，Sequence，下一个SST文件编号的状态信息。

leveldb中只要文件变动应用在旧的Version上可以得到新的Version。而这个更新信息都保存在VersionEdit中。

即：

Version N + VersionEdit = Version N+1

为了避免进程崩溃或机器宕机导致的数据丢失，LevelDB需要将元信息数据持久化到磁盘，承担这个任务的就是 Manifest 文件。可以看出每当有新的Version产生都需要更新Manifest，很自然的发现这个新增数据正好对应于VersionEdit内容。

在Manifest中的一次增量内容称作一个Block，其内容如下：

记录了向leveldb中写入的记录总数，写数据时被使用

前文回顾

SSTable 全称 Sorted String Table，顾名思义，里面的 key-value 都是有序保存的。除了两个 MemTable，LevelDB 中的大部分数据是以 SSTable 的形式保存在外存上。

SSTable 由 compaction 生成：

在一个 SSTable 中，文件末尾的 Footer 是定长的，其他数据都被划分成一个个变长的 block：index block、metaindex block、meta blocks、data blocks。

Index block 、 meta index block 、 data block 都是通过 BlockBuilder 来生成，通过 Block 来读取的。最简单的方式，block 里面只需要将一个个 key-value 有序保存。但是为了节省空间，LevelDB 在 block 的内部实现了 前缀压缩 。

前缀压缩利用了 key 的有序性（前缀相同的有序 key 会聚集在一起）对 key 进行压缩，每个 key 与前一个 key 相同的前缀部分可以不用保存。读取的时候再根据规则进行解码即可。

LevelDB 将 block 的一个 key-value 称为一条 entry。每条 entry 的格式如下：

一个 block 的数据格式如下：

在 block 中查找一个 key（ Block::Iter::Seek ）：

Meta block（bloom filter）由 FilterBlockBuilder 来生成，通过 FilterBlockReader 来读取。

后面会单独写一篇介绍 filter。

这一篇我们来解析leveldb的Compaction机制，要把这个讲清楚，需要回答下面的问题：

随着Put/Delete *** 作增多，sstable文件会越来越多，占用的磁盘空间也越来越大。删除无效的key( 被标记删除的key，被新版本覆盖的老版本的key )，然后重新生成sstable文件，可以有效减少sstable文件的数量，这个过程就是Compaction。

Compaction的入口函数是MaybeScheduleCompaction()，触发的时机：

leveldb是在后台线程执行Compact，目前只允许单线程，也就是说Compact只能串行执行。

入口函数是DBImpl::BackgroundCompaction()，流程如下：

leveldb通过VersionSet::PickCompaction()来选择要压缩的Layer和Table，怎么做到的呢？

原来，在每个Version生成的时候，会计算哪个Layer需要进行Compaction，方法是计算每个layer的compaction_score，选择得分最高的layer，这是由LogAndApply()函数完成的：

调用LogAndApply()生成Version的时机：

选择Layer和Table的过程头绪比较多，具体实施Compaction的过程相对比较好理解，用下面这张图表述Compaction的整个过程:

---