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
评论0