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）的存储结构，如下图所示。

数据写入的过程：

• 数据在写入时，会先写入内存中的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:ut方法和DBImpl:elete方法最终都调用了DBImpl::Write方法，因此我们主要来看一下DBImpl:ut和DBImpl::Write
读链路——DBImpl:ut

下面代码只保存了DBImpl::Get方法的主干逻辑。和LSM Tree的原理划一，

• 首先通过调用MemTable::Get到memtable里查找key是否存在
  
• 然后到immutable memtable中查找
  
• 如果内存中找不到，末了通过调用Version::Get到SSTable中查找。如果每次查找SSTable都必要读盘服从会很低，因此LevelDB设计了缓存的机制，Version::Get最终会调用TableCache::Get
  

Mark一下读链路中的焦点类：MemTable、TableCache

1. Status DBImpl::Get(const ReadOptions& options, const Slice& key,
2.                    std::string* value) {
3.   ...
4.   MemTable* mem = mem_;
5.   MemTable* imm = imm_;
6.   Version* current = versions_->current();
9.   // First look in the memtable, then in the immutable memtable (if any).
10.   LookupKey lkey(key, snapshot);
11.   if (mem->Get(lkey, value, &s)) {
12.     // Done
13.   } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
14.     // Done
15.   } else {
16.     s = current->Get(options, lkey, value, &stats);
17.   }
18.   ...
19. }

复制代码

写链路——DBImpl::Write

DBImpl::Write的过程大抵如下：

• 首先构造本次写入的WriteBatch。
  
• 调用log::Writer::AddRecord将待写入的内容写入日志。为什么要先写入日志呢？因为我们知道MemTable是一个内存里的数据结构，一旦宕机，还未落盘的数据就会发生丢失。因此LevelDB采用了写前日志（WAL）的方式，先将数据写入恒久化日志，然后再写入MemTable。如许一旦发生宕机，可以从写前日志中规复MemTable
  
• 调用WriteBatchInternal::InsertInto将WriteBatch写入MemTable。这个函数末了实在会调用到MemTable::Add
  

Mark一下写链路中的焦点类：WriteBatch、log::Writer、MemTable

1. Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
2.   Writer w(&mutex_);
3.   w.batch = updates;
4.   w.sync = options.sync;
5.   w.done = false;
8.   MutexLock l(&mutex_);
9.   writers_.push_back(&w);
10.   while (!w.done && &w != writers_.front()) {
11.     w.cv.Wait();
12.   }
13.   if (w.done) {
14.     return w.status;
15.   }
18.   // May temporarily unlock and wait.
19.   Status status = MakeRoomForWrite(updates == nullptr);
20.   uint64_t last_sequence = versions_->LastSequence();
21.   Writer* last_writer = &w;
22.   if (status.ok() && updates != nullptr) {  // nullptr batch is for compactions
23.     WriteBatch* write_batch = BuildBatchGroup(&last_writer);
24.    
25.     status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
26.     status = WriteBatchInternal::InsertInto(write_batch, mem_);
31.     if (write_batch == tmp_batch_) tmp_batch_->Clear();
34.     versions_->SetLastSequence(last_sequence);
35.   }
38.   while (true) {
39.     Writer* ready = writers_.front();
40.     writers_.pop_front();
41.     if (ready != &w) {
42.       ready->status = status;
43.       ready->done = true;
44.       ready->cv.Signal();
45.     }
46.     if (ready == last_writer) break;
47.   }
50.   // Notify new head of write queue
51.   if (!writers_.empty()) {
52.     writers_.front()->cv.Signal();
53.   }
56.   return status;
57. }

复制代码

焦点类

由此可以看出，要理解LevelDB的代码，主要必要关注以下这些焦点类的设计和实现：

• MemTable：内存中的数据存储结构，通常使用跳表（SkipList）实现。
  
• Version：版本管理
  
• TableCache：缓存机制
  
• Writer&WriteBacth：批量写操作，答应将多个写操作打包成一个事务举行提交。
  
• log::Writer：日志
  

除此之外，还有Compaction机制。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。