几年前之前也简单读过leveldb的源码，但是更整体性一些，不够细致。这个国庆假期刚好时间充裕，想把leveldb源码中的一些细节再过一遍。这篇文章更像是一个读码笔记，会记录一些读码过程中的小想法。
- 一个sstable的格式为n * {block} + filter data + meta data + index block，其中filter data记录了filter的数据。meta data记录了使用的fliter类型，例如bloom filter，和filter data的位置。这里的meta data是可以拓展的，只是目前只用到了filter。sstable中索引信息也是和数据一起持久化到文件里的，很以前想的不一样。以前觉得索引信息可以作为一种cache，在读取sstable的时候再构建。
- 数据key使用了前缀编码压缩，options_->block_restart_interval可以用来控制每隔多少个key，重新做一次前缀压缩。
- 索引block中的key没有做前缀压缩，看来也不太需要。
- 在构建table的时候，使用block builder去生成每一个block，然后写入文件，写入文件之前可以选择是否使用压缩，可配置。
- options.paranoid_checks 用于配置是否在加载table的时候做crc检查。
- filter是按大小构建的，每2KB构建一个filter结构，在查找的时候也是先根据offset找到要使用的filter结构才行。
- 在读取sstable时，首先加载index block，通过index block找到要查找的key所在的offset，然后通过offset找到filter，如果filter不命中就直接返回，否则读取block。
- block cache可以用来缓存table的block到内存中，这样读取block的时候可以避免磁盘io，可配置。
- block size可配置，如果range select较多，可以配大些。point select较多可以配小些。因为block是索引的最小单位。block size大还有一个好处是开启压缩的时候效果较好。
- 还有一类cache是table cache，缓存的是从file number到table的映射，这里也是LRU cache，但是其大小约等于max file size，基本能缓存住所有的文件。
- read options中可以配置fill_cache，用于从文件中读取block后，记录在block cache中。range select查询中不建议开启，担心污染LRU缓存。
- 从env中可以看出，leveldb绝大多数的写操作都是append，因此不用担心写文件的原子性问题。但是有一处例外，就是写current文件的时候，是原地覆盖写。leveldb的做法是先生成临时dbtmp文件，再用原子的rename设置为current，类似shadow page的做法。
- 在memtable中，key存储的格式是key_size|key|sequence num|value type。
- leveldb的compaction任务会注册到env中做调度执行，目前是单线程的，比较容易拓展为多线程。
- 在leveldb的log中，数据以32KB的block做切分(这里的block不同于sstable中的block)，如果block的剩余空间不足够存储一个record，这个record就有可能被切到不同的block中。这个设计如果只考虑leveldb是有点多余的，因为log在db恢复的时候是顺序读取的，而这个设计明显是为了方便能够从文件任意位置开始解析record。从leveldb官方给出的文档解释是google的内部mr系统可能会用到。实际上，在使用了leveldb的存储系统，要做一些迁移功能开发的话，这个编码还是很方便的。
- leveldb是一个多版本的存储系统，多版本的存储都会有一个问题时，旧版本数据什么时候可以回收的问题。常用的做法比如可以配置存活时间，如果超过存储数据的数据，在做compact的时候就可以回收。leveldb采用了另外的方式，首先leveldb的写入版本是递增的，读取的时候会首先获取最新的版本作为快照。但是leveldb会把分配出去的snapshot维护起来，直到读取完成后才释放掉。维护snapshot的目的是为了在compact的时候，如果key中记录的sequence已经小于最小的snapshot，说明已经不会被读取到，因此可以不用输出到新sstable中。这样可以保证读取一定能读到需要的版本数据。
- 在version set中维护了version集合，使用引用计数来维护version的生命周期。当version的引用计数归零后，就可以释放该version。version中维护了当前其认为有效的全部sstable的指针，当该version被回收时，也相当于该sstable的引用计数被减1。在回收文件时，会遍历version set，如果某个sstable不在version set记录的任一version中，即可回收。这里有一个问题，会不会被回收的sstable中，记录了当前snapshot可以读到的数据？是有可能的，但是没关系，因为在做compact的时候，该数据会被存到新的sstable中了，该sstable由新version指向。所以换一个角度说，version可以认为是sstable文件的快照。
- options_.reuse_logs用于控制leveldb在recover的过程中是否重用满足大小要求的manifest文件和log文件。在recover后，会最后把memtable compact下去，memtable不会被重新利用。这里如果在recover的过程中，把memtable和回放的log对应起来，可以做到避免不必要的最后的memtable compact。好处是像类似big table的系统中，一台机器上会维护多个leveldb，每次recover的时候都compact一次会对底层的分布式fs造成陡增的访问。
- 在recover的时候，首先恢复manifest，manifest会记录log number和prev log number，只有满足>= log number或者== prev log number的日志才会需要被回放出来。>= log number比较容易理解，因为每次完成memtable到sstable的compact后，都会更新manifest中的log number。prev log number目前已经不再使用，本意是为了记录正在做compact的memtable对应的log number，实际上只要在最后comapct memtable完成后，更新manifest中的log number即可。
- 在修改manifest的时候如果出现失败，说明新生成的sstable未被记录下来，这个时候bg_error会被标记。这个时候db就会进入只读状态。leveldb并没有自动处理这类后台错误，而是交给用户，如果使用的时候出现了bg error，是需要重新打开db进行恢复的。
- 当leveldb环境文件部分损坏的情况下，可以通过db repair来恢复数据。repair动作会将所有的log转化为sstable，然后新建manifest-1，将meta信息记录在manifest-1，sstable均放置在level 0。