第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
leveldb实现解析.pdf
leveldb 实现解析
淘宝-核心系统研发-存储
那岩
neveray@gmail.com
2011-12-13
目录
一、 代码目录结构 ....................................................................... 1
doc/ ............................................................................ 1
include/leveldb/ ................................................................. 1
db/ ............................................................................. 1
table/........................................................................... 1
port/ ........................................................................... 1
util/ ........................................................................... 1
helper/memenv/ ................................................................... 1
二、 基本概念 .......................................................................... 1
Slice (include/leveldb/slice.h) .................................................. 1
Option （include/leveldb/option.h） .............................................. 2
Env （include/leveldb/env.h util/env_posix.h） .................................... 3
varint (util/coding.h) ........................................................... 3
ValueType （db/dbformat.h） ...................................................... 3
SequnceNnumber （db/dbformat.h） ................................................. 4
user key......................................................................... 4
ParsedInternalKey （db/dbformat.h） .............................................. 4
InternalKey (db/dbformat.h) ...................................................... 4
LookupKey (db/dbformat.h) ........................................................ 4
Comparator （include/leveldb/comparator.h util/comparator.cc） .................... 4
InternalKeyComparator (db/dbformat.h) ............................................ 5
WriteBatch （db/write_batch.cc） ................................................. 5
Memtable (db/memtable.cc db/skiplist.h) .......................................... 5
Sstable (table/table.cc) ......................................................... 5
FileMetaData （db/version_edit.h） ............................................... 5
block (table/block.cc) ........................................................... 6
BlockHandle(table/format.h) ...................................................... 6
FileNumber（db/dbformat.h） ...................................................... 6
filename (db/filename.cc) ........................................................ 6
level-n (db/version_set.h) ....................................................... 7
Compact (db/db_impl.cc db/version_set.cc) ........................................ 7
Compaction(db/version_set.cc) .................................................... 7
Version (db/version_set.cc) ...................................................... 8
VersionSet （db/version_set.cc） ................................................. 9
VersionEdit(db/version_edit.cc) ................................................. 10
VersionSet::Builder (db/version_set.cc) ......................................... 11
Manifest（descriptor）（db/version_set.cc）...................................... 12
TableBuilder/BlockBuilder(table/table_builder.cc table/block_builder.cc) ......... 12
Iterator (include/leveldb/iterator.h) ........................................... 12
三、 存储结构的格式定义与操作 .......................................................... 12
memtable (db/skiplist.h db/memtable) ............................................ 12
block of sstable (table/block_builder.cc table/block.cc) ......................... 14
sstable (table/table_bulder.cc/table.cc) ........................................ 16
block of log （db/log_format.h db/log_writer.cc db/log_reader.cc） .............. 18
log （db/log_format.h db/log_writer.cc db/log_reader.cc） ........................ 18
cache（util/cache.cc） .......................................................... 19
Snapshot （include/leveldb/snapshot.h） ......................................... 19
Iterator (include/leveldb/iterator.h) ........................................... 19
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
1.
2.
3.
4.
5.
6.
7.
1.
2.
3.
4.
5.
6.
7.
8.
1.
2.
3.
4.
5.
6.
7.
四、 主要流程 ......................................................................... 24
open ........................................................................... 24
put ............................................................................ 25
get ............................................................................ 25
delete.......................................................................... 26
snapshot........................................................................ 26
NewIterator ..................................................................... 26
compact......................................................................... 26
五、 总结 ............................................................................. 30
1. 设计/实现中的优化 ............................................................... 30
2. 可以做的优化 .................................................................... 31
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 使用，直接操控指针避免不必要的数据拷贝。
1
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
2
const Snapshot* snapshot;
}
// include/leveldb/option.h
struct WriteOptions {
// write 时，记 binlog 之后，是否对 binlog 做 sync。
bool sync;
// 如果传入不为 NULL，write 完成之后同时做 SnapShot.
const Snapshot** post_write_snapshot;
}
另外还有一些编译时的常量，与 Option 一起控制。
// db/dbformat.h
namespace config {
// level 的最大值
static const int kNumLevels = 7;
// level-0 中 sstable 的数量超过这个阈值，触发 compact
static const int kL0_CompactionTrigger = 4;
// level-0 中 sstable 的数量超过这个阈值, 慢处理此次写(sleep1ms）
static const int kL0_SlowdownWritesTrigger = 8;
// level-0 中 sstable 的数量超过这个阈值, 阻塞至 compact memtable 完成。
static const int kL0_StopWritesTrigger = 12;
// memtable dump 成的 sstable，允许推向的最高 level
// （参见 Compact 流程的 VersionSet::PickLevelForMemTableOutput()）
static const int kMaxMemCompactLevel = 2;
}
// db/version_set.cc
namespace leveldb {
// compact 过程中，level-0 中的 sstable 由 memtable 直接 dump 生成，不做大小限制
// 非 level-0 中的 sstable 的大小设定为 kTargetFileSize
static const int kTargetFileSize = 2 * 1048576;
// compact level-n 时，与 level-n+2 产生 overlap 的数据 size （参见 Compaction）
static const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize;
}
3. Env （include/leveldb/env.h util/env_posix.h）
考虑到移植以及灵活性，leveldb 将系统相关的处理（文件/进程/时间之类）抽象成 Env，用户可以自
己实现相应的接口，作为 Option 传入。默认使用自带的实现。
4. varint (util/coding.h)
leveldb 采用了 protocalbuffer 里使用的变长整形编码方法，节省空间。
5. ValueType （db/dbformat.h）
leveldb 更新（put/delete）某个 key 时不会操控到 db 中的数据，每次操作都是直接新插入一份 kv 数
据，具体的数据合并和清除由后台的 compact 完成。所以，每次 put，db 中就会新加入一份 KV 数据，
即使该 key 已经存在；而 delete 等同于 put 空的 value。为了区分真实 kv 数据和删除操作的 mock 数
据，使用 ValueType 来标识：
3
enum ValueType {
kTypeDeletion = 0x0,
kTypeValue = 0x1
};
6. SequnceNnumber （db/dbformat.h）
leveldb 中的每次更新（put/delete)操作都拥有一个版本，由 SequnceNumber 来标识，整个 db 有一个
全局值保存着当前使用到的 SequnceNumber。SequnceNumber 在 leveldb 有重要的地位，key 的排序，
compact 以及 snapshot 都依赖于它。
typedef uint64_t SequenceNumber;
存储时，SequnceNumber 只占用 56 bits, ValueType 占用 8 bits，二者共同占用 64bits（uint64_t).
0
SequnceNumber
56
ValueType
7. user key
用户层面传入的 key，使用 Slice 格式。
8. ParsedInternalKey （db/dbformat.h）
db 内部操作的 key。db 内部需要将 user key 加入元信息(ValueType/SequenceNumber)一并做处理。
struct ParsedInternalKey {
Slice user_key;
SequenceNumber sequence;
ValueType type;
};
9.
InternalKey (db/dbformat.h)
db 内部，包装易用的结构，包含 userkey 与 SequnceNumber/ValueType。
10. LookupKey (db/dbformat.h)
db 内部在为查找 memtable/sstable 方便，包装使用的 key 结构，保存有 userkey 与
SequnceNumber/ValueType dump 在内存的数据。
class LookupKey {
…
private:
const char* start_;
const char* kstart_;
const char* end_;
};
LookupKey:
start
kstart
end
userkey_len
(varint32)
userkey_data
(userkey_len)
SequnceNumber/ValueType
(uint64)
对 memtable 进行 lookup 时使用 [start,end], 对 sstable lookup 时使用[kstart, end]。
11. Comparator （include/leveldb/comparator.h util/comparator.cc）
对 key 排序时使用的比较方法。leveldb 中 key 为升序。
4
用户可以自定义 user key 的 comparator（user-comparator)，作为 option 传入，默认采用 byte
compare（memcmp）。
comparator 中有 FindShortestSeparator（）/ FindShortSuccessor（）两个接口，
FindShortestSeparator（start，limit）是获得大于 start 但小于 limit 的最小值。
FindShortSuccessor（start）是获得比 start 大的最小值。比较都基于 user-commparator，二者会被
用来确定 sstable 中 block 的 end-key。
12. InternalKeyComparator (db/dbformat.h)
db 内部做 key 排序时使用的比较方法。排序时，会先使用 user-comparator 比较 user-key，如果
user-key 相同，则比较 SequnceNumber，SequnceNumber 大的为小。因为 SequnceNumber 在 db 中全局
递增，所以，对于相同的 user-key，最新的更新（SequnceNumber 更大）排在前面，在查找的时候，
会被先找到。
InternalKeyComparator 中 FindShortestSeparator（）/ FindShortSuccessor（）的实现，仅从传入
的内部 key 参数，解析出 user-key，然后再调用 user-comparator 的对应接口。
13. WriteBatch （db/write_batch.cc）
对若干数目 key 的 write 操作（put/delete）封装成 WriteBatch。它会将 userkey 连同
SequnceNumber 和 ValueType 先做 encode，然后做 decode，将数据 insert 到指定的 Handler
（memtable）上面。上层的处理逻辑简洁，但 encode/decode 略有冗余。
WriteBatch encode 之后，内部保存的数据格式：
SequnceNumber
record0 ...... recordN
count
(uint64)
(uint32)
record 组成：
ValueType
（char）
key_len
(varint32)
key_data
(key_len)
value_len
(varint32)
value_data
(value_len)
1) SequnceNumber: WriteBatch 中开始使用的 SequnceNumber。
2) count: 批量处理的 record 数量
3) record：封装在 WriteBatch 内的数据。
如果 ValueType 是 kTypeValue,则后面有 key 和 value
如果 ValueType 是 kTypeDeletion，则后面只有 key。
14. Memtable (db/memtable.cc db/skiplist.h)
db 数据在内存中的存储格式。写操作的数据都会先写到 memtable 中。memtable 的 size 有限制最大值
（write_buffer_size)。
memtable 的实现是 skiplist。
当一个 memtable size 到达阈值时，会变成只读的 memtable（immutable memtable），同时生成一个
新的 memtable 供新的写入。后台的 compact 进程会负责将 immutable memtable dump 成 sstable。所
以，同时最多会存在两个 memtable（正在写的 memtable 和 immutable memtable）。
15. Sstable (table/table.cc)
db 数据持久化的文件。文件的 size 有限制最大值（target_file_size)。文件前面为数据，后面是索
引元信息。
16. FileMetaData （db/version_edit.h）
sstable 文件的元信息封装成 FileMetaData，
struct FileMetaData {
int refs; // 引用计数
5
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
