LevelDB
LevelDB
LevelDB
LevelDB ,LevelDB 是对 Bigtable 论文中描述的键值存储系统的单机版的实现,它提供了一个极其高速的键值存储系统,并且由 Bigtable 的作者 Jeff Dean 和 Sanjay Ghemawat 共同完成,可以说高度复刻了 Bigtable 论文中对于其实现的描述。
概述
LevelDB 作为一个键值存储的『仓库』,它提供了一组非常简单的增删改查接口:
class DB {
public:
virtual Status Put(const WriteOptions& options, const Slice& key, const Slice& value) = 0;
virtual Status Delete(const WriteOptions& options, const Slice& key) = 0;
virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;
virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;
}
C++
Put
方法在内部最终会调用Write
方法,只是在上层为调用者提供了两个不同的选择。
Get
和 Put
是 LevelDB 为上层提供的用于读写的接口。
LevelDB是一个写性能十分优秀的存储引擎,LSM树(Log Structured-Merge Tree)实现。LSM树的核心思想就是放弃部分读的性能,换取最大的写入能力。写性能高的原理,参考BigTable,尽量减少随机写的次数。对于每次写入操作,并不是直接将最新的数据驻留在磁盘中,而是将其拆分成(1)一次日志文件的顺序写(2)一次内存中的数据插入。
架构

-
MemTable
MemTable就是一个在内存中进行数据组织与维护的结构,通过
跳表
实现。MemTable 中,所有的数据按用户定义的排序方法排序之后按序存储
,等到其存储内容的容量达到阈值时(默认为4MB
),便将其转换成一个不可修改的MemTable,与此同时创建一个新的MemTable,供用户继续进行读写操作。 -
Immutable MemTable
只读的MemTable,后台压缩线程会将它持久到磁盘SST文件。
-
Log
数据写入内存前,先将写操作写入日志(WAL),异常发生时可通过日志恢复(redo)。
顺序写入日志,替代了直接写入磁盘(随机写入),因此写入性能更高。- 写log期间进程异常 ---> 写入失败
- 写log完成,写内存未完成 ---> redo恢复
- write动作完成(即log、内存写入都完成)后,进程异常 ---> redo恢复
- Immutable memtable持久化过程中进程异常 ---> redo恢复
- 其他压缩异常 ---> redo恢复
-
SSTable
内存中,所有的数据都是按序排列的,但是当多个MemTable数据持久化到磁盘后,对应的不同的sstable之间是存在交集的(不同批次写入的数据的顺序有交集),在读操作时,需要对所有的sstable文件进行遍历,严重影响了读取效率。因此后台会“定期“整合这些sstable文件,该过程也称为
compaction
。随着compaction的进行,sstable文件在逻辑上被分成若干层,由内存数据直接dump出来的文件称为level 0层文件,后期整合而成的文件为level i 层文件,这也是leveldb这个名字的由来。所有的sstable文件本身的内容是不可修改的,这种设计哲学为leveldb带来了许多优势,简化了很多设计。
-
Manifest
Manifest文件保存了整个LevelDB示例的全部元数据,记录不同Level分布了哪些SST文件,单个SST文件的最大最小key,以及其他一些LevelDB需要的元信息。
本质上是一个Log文件,每一个log record的内容就是
VersionEdit
。-
VersionEdit
表示一次元数据变更,内容如下:
std::string comparator_; // 比较器的名称,创建 LevelDB 的时候就确定了,以后都不能修改 uint64_t log_number_; // 最小的有效 log number。小于 log_numbers_ 的 log 文件都可以删除 uint64_t prev_log_number_; // 兼容旧版本 uint64_t next_file_number_; // 下一个文件的编号 SequenceNumber last_sequence_; // SSTable 中的最大的 sequence number std::vector<std::pair<int, InternalKey> > compact_pointers_; // 每层进行下次compaction的起始 key DeletedFileSet deleted_files_; // 可以删除的 SSTable(level-no -> file-no) std::vector<std::pair<int, FileMetaData> > new_files_; // 新增的 SSTable
通过EncodeTo序列化后,内容大致如下:
kComparator comparator_ kLogNumber log_number_ kPrevLogNumber prev_log_number_ kNextFileNumber next_file_number_ kLastSequence last_sequence_ kCompactPointer level internal_key kCompactPointer level internal_key ... kDeletedFile level fileno kDeletedFile level fileno ... kNewFile level fileno file-size smallest largest kNewFile level fileno file-size smallest largest ...
-
Version
Version 是 VersionEdit 进行 apply 之后得到的数据库状态——当前版本包含哪些 SSTable,并通过引用计数保证多线程并发访问的安全性。读操作要读取 SSTable 之前需要调用 Version::Ref 增加引用计数,不使用时需要调用 Version::UnRef 减少引用计数。
 -
VersionSet
VersionSet 是一个 Version 的集合,用链表维护,每生成一个Version在尾部插入一个节点(AppendVersion)。随着数据库状态的变化,LevelDB 内部会不停地生成 VersionEdit——进而产生新的 Version。此时,旧的 Version 可能还在被正在执行的请求使用。所以,同一时刻可能存在多个 Version。
-
-
Current
记录当前Manifest文件的名字。