leveldb 笔记

leveldb实现解析那岩

一代码目录结构

1. doc/

2.include/leveldb/

3. db/

主要逻辑的实现。包括：

接口的实现（db_impl/db_iter)
内部结构的定义（dbformat/memtable/skiplist/write_batch)
db运行状态以及操作的包装
log格式相关
filename处理相关
sstable相关

4. table/

sstable相关的数据格式定义以及操作实现

5. port/

6.util/

7. helper/memenv/

实现了一个简单的完全内存的文件系统，提供操作目录文件的接口。

二基本概念

1. Slice(include/leveldb/slice.h)

为操作数据的方便，将数据和长度包装成 Slice 使用，直接操控指针避免不必要的数据拷贝。

2. Option(include/leveldb/optin.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
 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. varient(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 来标识：

enum ValueType {
  kTypeDeletion = 0x0,
  kTypeValue = 0x1
};