LevelDB源码解析 | 01 总体架构
什么是leveldb？LevelDB 是一个由 Google 开发的高性能的嵌入式键值存储数据库，与传统的关系型数据库不同，LevelDB 是一个 NoSQL 类型的数据库，它采用了 键值对（Key-Value）的数据模型，因此可以高效地存储和检索大量数据。
LevelDB具有以下几个特点：
[*]嵌入式设计：LevelDB 是一个嵌入式数据库，意味着它并不作为独立的服务运行，而是直接嵌入到应用程序中，通常用于本地存储数据。
[*]高性能：LevelDB 支持高吞吐量的读写操作，尤其在写入时表现优秀。它使用了 Log-Structured Merge Tree（LSM Tree） 数据结构来优化磁盘的写入性能，得当在存储体系上实行高效的顺序写入。
[*]恒久化存储：LevelDB 将数据存储在磁盘中，并支持恒久化存储。
LevelDB的基本原理——LSM Tree
LevelDB采用了 Log-Structured Merge Tree（LSM Tree）的存储结构，如下图所示。
https://i-blog.csdnimg.cn/img_convert/b14a906319b43d8ddd932ee51b6d174b.png
数据写入的过程：
[*]数据在写入时，会先写入内存中的memtable。memtable会维护一个键有序的数据结构，当一个memtable写满后，该memtable会从可读可写的状态变成只可读不可写的immutable memtable，并随后落到磁盘上形成SST文件。同时，内存中会创建一个新的memtable继承接受写入。由于memtable中的数据是有序的，以是每个SST文件中的数据也是有序的，这也是为什么它叫sorted string table。
[*]内存中的memtable黑白恒久化的，掉电会丢失。因此每个数据在写入memtable之前会先写入WAL日志举行恒久化，如许方便故障规复。
[*]磁盘上维护多层的逻辑结构。immutable memtable最初（基本上）都会直接写入第一层，即L0层。但是由于一个键可能被写入多次、在磁盘上存在多条记载，因此这不仅影响查找性能、也浪费磁盘空间。以是会通过定期的compaction机制对数据举行去重并压入磁盘的更低层，即L1-LN层
数据读取的过程：
[*]从数据的新旧程度来看，memtable中的数据总是最新写入的、其次是immutable memtable，末了是磁盘中的SST文件。以是在读取数据时，会先查询memtable、其次查询immutable memtable、末了逐层查询磁盘上的SST文件。
LSM Tree结构的利益：
[*]写入磁盘时，一种是WAL日志的追加写、一种是SST文件的顺序写入。因此可以看出这种结构的磁盘写入均为顺序写，因此写入性能较高
[*]读取时，由于每个SST文件内部的数据都是有序的，因此可以借助索引以及二分查找的手段实现较高的读取性能
LSM Tree结构的潜在问题：
[*]空间放大：LSM Tree会保存对一个键的多次写入，以是存储中会包罗对一个键修改的全部历史记载，导致大量的磁盘空间被占用。可能的解决方案有：（1）设置TTL删除过期数据；（2）compaction
[*]读放大：对一个key的多次写入都会保存并写入L0层的SST文件，而且L0层的文件是无序的，以是查找一个键可能必要扫描多个文件。固然compaction在一定程度上可以缓解L0层的读放大，但是它会把数据推向更深的层次，还是可能造成查找文件次数的增长。可能的解决方案：（1）布隆过滤器；（2）compaction
[*]写放大。compaction在一定程度上可以缓解空间放大和读放大，但是会加剧写放大。缘故原由在于compaction过程会导致数据的重复写入，以是一次写入等价于多次磁盘写入。
[*]对范围查找的支持没有那么好。LSM-Tree 由于数据分布在多个层级，范围查找时可能必要合并多个 SSTable 的数据，导致扫描服从不如 B+Tree。
LevelDB总体代码架构
LevelDB的主要功能实在就是数据存储与读写，因此我们可以从LevelDB的主干读写链路入手，共同上刚刚介绍的LSM Tree的原理，初步了解LevelDB的总体代码架构、焦点类以及不同类之间的关系和调用逻辑。
LevelDB对外提供的接口在db.h中，而接口的相关实现代码在db_impl.cc中。LevelDB提供的几个重要接口包括：
[*]Get：读取一个键值对
[*]Put：修改/新增一个键值对
[*]Delete：删除一个键值对
[*]Write：写入键值对
从代码中可以看出DBImpl::Put方法和DBImpl::Delete方法最终都调用了DBImpl::Write方法，因此我们主要来看一下DBImpl::Put和DBImpl::Write
读链路——DBImpl::Put
下面代码只保存了DBImpl::Get方法的主干逻辑。和LSM Tree的原理划一，
[*]首先通过调用MemTable::Get到memtable里查找key是否存在
[*]然后到immutable memtable中查找
[*]如果内存中找不到，末了通过调用Version::Get到SSTable中查找。如果每次查找SSTable都必要读盘服从会很低，因此LevelDB设计了缓存的机制，Version::Get最终会调用TableCache::Get
Mark一下读链路中的焦点类：MemTable、TableCache
Status DBImpl::Get(const ReadOptions& options, const Slice& key,
std::string* value) {
...
MemTable* mem = mem_;
MemTable* imm = imm_;
Version* current = versions_->current();
// First look in the memtable, then in the immutable memtable (if any).
LookupKey lkey(key, snapshot);
if (mem->Get(lkey, value, &s)) {
// Done
} else if (imm != nullptr && imm->Get(lkey, value, &s)) {
// Done
} else {
s = current->Get(options, lkey, value, &stats);
}
...
} 写链路——DBImpl::Write
DBImpl::Write的过程大抵如下：
[*]首先构造本次写入的WriteBatch。
[*]调用log::Writer::AddRecord将待写入的内容写入日志。为什么要先写入日志呢？因为我们知道MemTable是一个内存里的数据结构，一旦宕机，还未落盘的数据就会发生丢失。因此LevelDB采用了写前日志（WAL）的方式，先将数据写入恒久化日志，然后再写入MemTable。如许一旦发生宕机，可以从写前日志中规复MemTable
[*]调用WriteBatchInternal::InsertInto将WriteBatch写入MemTable。这个函数末了实在会调用到MemTable::Add
Mark一下写链路中的焦点类：WriteBatch、log::Writer、MemTable
Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
Writer w(&mutex_);
w.batch = updates;
w.sync = options.sync;
w.done = false;
MutexLock l(&mutex_);
writers_.push_back(&w);
while (!w.done && &w != writers_.front()) {
w.cv.Wait();
}
if (w.done) {
return w.status;
}
// May temporarily unlock and wait.
Status status = MakeRoomForWrite(updates == nullptr);
uint64_t last_sequence = versions_->LastSequence();
Writer* last_writer = &w;
if (status.ok() && updates != nullptr) {// nullptr batch is for compactions
WriteBatch* write_batch = BuildBatchGroup(&last_writer);
status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
status = WriteBatchInternal::InsertInto(write_batch, mem_);
if (write_batch == tmp_batch_) tmp_batch_->Clear();
versions_->SetLastSequence(last_sequence);
}
while (true) {
Writer* ready = writers_.front();
writers_.pop_front();
if (ready != &w) {
ready->status = status;
ready->done = true;
ready->cv.Signal();
}
if (ready == last_writer) break;
}
// Notify new head of write queue
if (!writers_.empty()) {
writers_.front()->cv.Signal();
}
return status;
} 焦点类
由此可以看出，要理解LevelDB的代码，主要必要关注以下这些焦点类的设计和实现：
[*]MemTable：内存中的数据存储结构，通常使用跳表（SkipList）实现。
[*]Version：版本管理
[*]TableCache：缓存机制
[*]Writer&WriteBacth：批量写操作，答应将多个写操作打包成一个事务举行提交。
[*]log::Writer：日志
除此之外，还有Compaction机制。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]