leveldb 实现解析
淘宝-核心系统研发-存储
那岩
neveray@gmail.com
2011-12-13
目录
一、 代码目录结构 ....................................................................... 1
1. doc/ ............................................................................ 1
2. include/leveldb/ ................................................................. 1
3. db/ ............................................................................. 1
4. table/........................................................................... 1
5. port/ ........................................................................... 1
6. util/ ........................................................................... 1
7. helper/memenv/ ................................................................... 1
二、 基本概念 .......................................................................... 1
1. Slice (include/leveldb/slice.h) .................................................. 1
2. Option （include/leveldb/option.h） .............................................. 2
3. Env （include/leveldb/env.h util/env_posix.h） .................................... 3
4. varint (util/coding.h) ........................................................... 3
5. ValueType （db/dbformat.h） ...................................................... 3
6. SequnceNnumber （db/dbformat.h） ................................................. 4
7. user key......................................................................... 4
8. ParsedInternalKey （db/dbformat.h） .............................................. 4
9. InternalKey (db/dbformat.h) ...................................................... 4
10. LookupKey (db/dbformat.h) ........................................................ 4
11. Comparator （include/leveldb/comparator.h util/comparator.cc） .................... 4
12. InternalKeyComparator (db/dbformat.h) ............................................ 5
13. WriteBatch （db/write_batch.cc） ................................................. 5
14. Memtable (db/memtable.cc db/skiplist.h) .......................................... 5
15. Sstable (table/table.cc) ......................................................... 5
16. FileMetaData （db/version_edit.h） ............................................... 5
17. block (table/block.cc) ........................................................... 6
18. BlockHandle(table/format.h) ...................................................... 6
19. FileNumber（db/dbformat.h） ...................................................... 6
20. filename (db/filename.cc) ........................................................ 6
21. level-n (db/version_set.h) ....................................................... 7
22. Compact (db/db_impl.cc db/version_set.cc) ........................................ 7
23. Compaction(db/version_set.cc) .................................................... 7
24. Version (db/version_set.cc) ...................................................... 8
25. VersionSet （db/version_set.cc） ................................................. 9
26. VersionEdit(db/version_edit.cc) ................................................. 10
27. VersionSet::Builder (db/version_set.cc) ......................................... 11
28. Manifest（descriptor）（db/version_set.cc）...................................... 12
29. TableBuilder/BlockBuilder(table/table_builder.cc table/block_builder.cc) ......... 12
30. Iterator (include/leveldb/iterator.h) ........................................... 12
三、 存储结构的格式定义与操作 .......................................................... 12
1. memtable (db/skiplist.h db/memtable) ............................................ 12
2. block of sstable (table/block_builder.cc table/block.cc) ......................... 14
3. sstable (table/table_bulder.cc/table.cc) ........................................ 16
4. block of log （db/log_format.h db/log_writer.cc db/log_reader.cc） .............. 18
5. log （db/log_format.h db/log_writer.cc db/log_reader.cc） ........................ 18
6. cache（util/cache.cc） .......................................................... 19
7. Snapshot （include/leveldb/snapshot.h） ......................................... 19
8. Iterator (include/leveldb/iterator.h) ........................................... 19
四、 主要流程 ......................................................................... 24
1. open ........................................................................... 24
2. put ............................................................................ 25
3. get ............................................................................ 25
4. delete.......................................................................... 26
5. snapshot........................................................................ 26
6. NewIterator ..................................................................... 26
7. compact......................................................................... 26
五、 总结 ............................................................................. 30
1. 设计/实现中的优化 ............................................................... 30
2. 可以做的优化 .................................................................... 31
1
leveldb 是 Google 开源的持久化 KV 单机存储引擎，开源页面 http://code.google.com/p/leveldb/。
针对存储面对的普遍随机 IO 问题，leveldb 采用了 merge-dump 的方式，将逻辑场景的写请求转换成顺序写
log 和写 memtable 操作，由后台进程将 memtable 持久化成 sstable。对于读请求，随机 IO 还是无法避免，
但它设计了一系列策略来保证读的效率。
这里对 leveldb 的实现做具体解析，但并不采用对代码注释的方式，而是意图从上层设计的角度，将内部的
实现逻辑串联起来，尽量发现策略设计背后的原因。
一、 代码目录结构
1. doc/
相关文档。有 log 和 sstable 的格式介绍（log_format/table_format）。
2. include/leveldb/
使用者需要的头文件，包含基本的接口,可以自定义的 comparator/env/cache，以及依赖的头文件。
3. db/
主要逻辑的实现。包括接口的实现（db_impl/db_iter）,内部结构的定义
（dbformat/memtable/skiplist/write_batch），db 运行状态以及操作的包装
（version_set/version_edit），log 格式相关（log/log_reader/log_writer）,filename 处理相
关（filename），sstable 相关（builder/table_cache）.
4. table/
sstable 相关的数据格式定义以及操作实现。
格式定义（format），block 相关的操作（block/block_builder）,sstable 相关的操作
（table/table_builder）,操作便利封装的复合 Iterator(two_level_iterator/ merger),优化
Iterator 的 wrapper（iterator_wrapper）。
5. port/
根据系统环境，为移植实现的锁/信号/原子操作/压缩相关。提供 posix/android。
6. util/
提供的通用功能实现。
memtable 使用的简单内存管理（arena）,LRU cache 的实现（cache）, comparator 的默认实现
（comparator），通用功能的实现（coding/crc32c/hash/random/MutexLock/logging）,leveldb
将文件/进程相关的操作封装成 Env，提供了默认的实现（env_posix）。
7. helper/memenv/
实现了一个简单的完全内存的文件系统，提供操作目录文件的接口。
二、 基本概念
1. Slice (include/leveldb/slice.h)
为操作数据的方便，将数据和长度包装成 Slice 使用，直接操控指针避免不必要的数据拷贝。
2
class Slice {
…
private:
const char* data_;
size_t size_;
};
2. Option （include/leveldb/option.h）
leveldb 中启动时的一些配置，通过 Option 传入，get/put/delete 时，也有相应的
ReadOption/WriteOption。
// include/leveldb/option.h
Options {
// 传入的 comparator
const Comparator* comparator;
// open 时，如果 db 目录不存在就创建
bool create_if_missing;
// open 时，如果 db 目录存在就报错
bool error_if_exists;
// 是否保存中间的错误状态(RecoverLog/compact),compact 时是否读到的 block 做检验。
bool paranoid_checks;
// 传入的 Env。
Env* env;
// 传入的打印日志的 Logger
Logger* info_log;
// memtable 的最大 size
size_t write_buffer_size;
// db 中打开的文件最大个数
// db 中需要打开的文件包括基本的 CURRENT/LOG/MANIFEST/LOCK, 以及打开的 sstable 文件。
// sstable 一旦打开，就会将 index 信息加入 TableCache，所以把
// (max_open_files - 10)作为 table cache 的最大数量.
int max_open_files;
// 传入的 block 数据的 cache 管理
Cache* block_cache;
// sstable 中 block 的 size
size_t block_size;
// block 中对 key 做前缀压缩的区间长度
int block_restart_interval;
// 压缩数据使用的压缩类型（默认支持 snappy，其他类型需要使用者实现）
CompressionType compression;
}
// include/leveldb/option.h
struct ReadOptions {
// 是否对读到的 block 做校验
bool verify_checksums;
// 读到的 block 是否加入 block cache
bool fill_cache;
// 指定读取的 SnapShot
