LevelDB原理解析：数据的读写与合并是怎样发生的？

您所在的位置：网站首页 › 图解数据读写与Cache操作 › LevelDB原理解析：数据的读写与合并是怎样发生的？

LevelDB原理解析：数据的读写与合并是怎样发生的？

2024-05-10 09:29| 来源: 网络整理| 查看: 265

导语 | LevelDB是一款十分优秀的存储引擎，具有极高的数据读写性能，尤其是写入性能，在笔者经历的多个项目中都有用到，因此本文打算结合LevelDB的部分源码对 LevelDB进行介绍，首先会介绍LevelDB的整体架构，然后围绕数据读写流程和合并流程展开介绍，希望与大家一同交流。文章作者：唐文博，腾讯优图实验室高级研究员。

一、LevelDB总体架构

LevelDB是一款写性能极高、可靠的单机存储引擎，是LSM-Tree的典型实现，LSM-Tree最主要的思想是牺牲部分读性能，最大化提升数据写入性能，因此LevelDB很适合被应用在写多读少的场景。

同时LevelDB还有数据在磁盘上按key顺序存储，支持按snapshot快照查询等特性。如下图所示，LevelDB主要由驻于内存的缓存结构和存在于磁盘的物理文件组成。

1. 内存缓存结构

Memtable：Memtable可读可写，内部由SkipList实现，用于在内存中缓存写操作。Immutable Memtable：内部同样由SkipList实现，但是只读，当Memtable的大小达到设定的阈值时，会变成 Immutable Memtable，后续由后台线程通过compaction操作将数据顺序落盘，变成sstable文件。

2. 磁盘文件

sstable：sstable是磁盘上的存储文件，它将key有序存放，level0层的sstable由内存中的Immutable Memtable直接持久化生成，因为没有和当前层的其他文件合并过，因此level0层的sstable里的key会发生重叠，其余层的sstable文件均由当前层和前一层的sstable文件归并而来。Manifest：Manifest文件是sstable的索引信息，用来记录每个sstable对应的key range、文件size等信息。Log：Log文件主要是用于机器重启而不丢失数据，当向LevelDB写入一条数据时，它首先会向Log文件顺序写入一条操作日志，然后再向内存Memtable写入数据，这样即便机器掉电，也不会出现数据丢失的情况。Current文件：当机器重启时，LevelDB会重新生成新的Manifest文件，所以Manifest文件可能存在多个，这里会使用Current文件记录当前使用的Manifest文件。

二、写入流程

LevelDB对外提供的写入接口有Put和Delete两种，两者本质上对应同一种操作，实际上都会向Memtable及Log文件中追加一条新纪录。

同时LevelDB支持调用端使用多线程并发写入数据，并且会使用写队列+合并写&WAL机制，将批量随机写转化成一次顺序写，从而提升写入性能。下边将结合部分源码来看看LevelDB具体是怎么实现的。

1. 具体写入流程

（1）封装WriteBatch和Writer对象

DB::Put会把key、value方法封装到WriteBatch中，DBImpl::Write方法会把WriteBatch对象封装到Writer对象中，此外Writer对象还封装了mutex_，条件变量等用来实现等待通知。

代码语言：javascript复制Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) { WriteBatch batch; batch.Put(key, value); //调用DBImpl::Write方法 return Write(opt, &batch); } struct DBImpl::Writer { Status status; WriteBatch* batch; bool sync; bool done; port::CondVar cv; explicit Writer(port::Mutex* mu) : cv(mu) { } };

（2）Writer串行化入队

多个线程并行的写入操作，会通过抢锁串行化，线程将Writer放到写队列之后，会进入等待状态，直到满足如下两个条件：

其他线程已经帮忙把Writer写入；抢到锁并且是写队列的首节点。代码语言：javascript复制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); //任务放到queue中，如果当前不是queue的头部则等待 //当某个线程将queue中自己对应的Writer写入磁盘时，可能也会将其他线程对应的Writer写入磁盘 while (!w.done && &w != writers_.front()) { w.cv.Wait(); } if (w.done) { return w.status; }

（3）确认写入空间足够

处于写队列头部的线程会调用MakeRoomForWrite方法，MakeRoomForWrite方法会检查Memtable是否有足够的空间写入，它会将内存占用过高的Memtable转换成Immutable，并构造一个新的Memtable进行写入，刚刚形成的Immutable则交由后台线程dump到level0层。

代码语言：javascript复制代码语言：javascript复制Status DBImpl::MakeRoomForWrite(bool force) { //通过改变指针指向，将Memtable转换成Immutable imm_ = mem_; has_imm_.store(true, std::memory_order_release); //生成新的Memtable mem_ = new MemTable(internal_comparator_); mem_->Ref(); //触发compaction MaybeScheduleCompaction(); }代码语言：javascript复制

（4）批量取任务，进行合并写

处于写队列头部的线程进行完MakeRoomForWrite检查之后，便会从writers_写队列里取出头部任务，同时会遍历队列中后面的Writer合并到自身，进行批量写，从而提高写入效率，最终多个Writer任务会先被写入Log文件，然后被写入内存的MemTable。

代码语言：javascript复制//从队列中批量取任务 WriteBatch* write_batch = BuildBatchGroup(&last_writer); //将任务写入Log文件 status = log_->AddRecord(WriteBatchInternal::Contents(write_batch)); //将任务写入Memtable status = WriteBatchInternal::InsertInto(write_batch, mem_);

（5）唤醒正在等待的线程

线程写入完成后，会对写完的Writer出队，并唤醒正在等在的线程，同时也会唤醒写队列中新的头部Writer对应的线程。

代码语言：javascript复制代码语言：javascript复制 //last_writer指向writers_里合并的最后一个Writer //逐个遍历弹出writers_里的元素，并唤醒对应的正在等待的写线程，直到遇到last_writer 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; } // 唤醒队列未写入的第一个Writer if (!writers_.empty()) { writers_.front()->cv.Signal(); }代码语言：javascript复制

最后对写入步骤进行简单总结，如下图所示，三个写线程同时调用LevelDB的Put接口并发写入，三个线程首先会通过抢锁将构造的Writer对象串行的放入writers_写队列，这时Writer1处于写队列头部，thread1会执行批量写操作，不仅会把自己构造的Writer写入，还会从队列中取出thread2、thread3对应的Writer，最后将三者一起写入Log文件及内存Memtable，thread2、thread3在push完之后则会进入等待状态。thread1写入完成之后，会唤醒处于等待状态的thread2和thread3。

三、读取流程

LevelDB的读取流程相对简单，从其中读取一个数据，会按照从上而下memtable -> immutable -> sstable的顺序读取，读不到则从下一个层级读取，因此LevelDB更适合读取最新写入的数据。流程如下图：

Level0中的文件直接由Immutable Memtable通过dump产生，文件之间key可能相互重叠，所以需要对level0的每个文件依次查找。

对于其他层次，LevelDB的归并过程保证了其中的key互相不重叠并且有序，因此可以直接使用二分方式进行数据查找。部分代码如下：

代码语言：javascript复制{ mutex_.Unlock(); // First look in the memtable, then in the immutable memtable (if any). LookupKey lkey(key, snapshot); //先查找memtable if (mem->Get(lkey, value, &s)) { //再查找immutable memtable } else if (imm != nullptr && imm->Get(lkey, value, &s)) { } else { //查找sstable s = current->Get(options, lkey, value, &stats); have_stat_update = true; } mutex_.Lock(); }

四、Compaction流程

Compaction是LevelDB中相对比较复杂的操作，这里仅对其中比较主要的点进行介绍。compactcion分为2种，一是minor compaction，另一种是major compaction。通过compaction操作可以达到以下几个效果：

将内存中的数据持久化到磁盘；清理冗余数据，因为LevelDB的更新和删除操作具有延后性，两种操作实际上都会向LevelDB写入一条新记录，所以通过重新compaction整理数据，可以清理冗余数据，节省磁盘空间；通过compaction使level 0以下的文件层中的数据保持有序，这样便可以通过二分进行数据查找，同时也可以减少待查找的文件数量，提升读效率。 1. minor compaction

minor compaction相对简单，对应Immutable持久化到level0层的过程。但是如果这一步骤的处理耗时过长，那么就会导致内存中的Memtable无法写入但又没有办法及时转化成Immutable，所以高性能持久化是对minor compaction最主要的要求。

为了提升数据持久化的速度，在对Immutable进行持久化时不会考虑不同文件间的重复和顺序问题，这样带来的问题是对读不够友好，读取数据时需要读取level0层的所有文件。

（1）触发minor compaction的时机

当内存中的memtable size 小于配置的阈值时，数据都会直接更新到memtable。超过大小后，memtable转化为Immutable，这时会由一个后台线程负责将Immutable持久化到磁盘成为level0的sstable文件。

（2）compaction具体流程

将Immutable memtable落盘成SSTable文件

DBImpl::WriteLevel0Table会将Immutable memtable落盘成SSTable文件，同时会将文件信息记录到edit(用于存储文件的摘要信息，如key range, file_size等)中。值得注意的是，新生成的SSTable文件实际上并不总是被放到Level0层，如果新生成的sstable的key与当前Level1层所有文件都没有重叠，则会直接将文件放到Level1层。

代码语言：javascript复制Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) { //生成sstable编号，用于构建文件名 FileMetaData meta; meta.number = versions_->NewFileNumber(); Status s; { mutex_.Unlock(); //更新memtable中的全部数据到xxx.ldb文件 //meta记录key range, file_size等sst信息 s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta); mutex_.Lock(); } int level = 0; if (s.ok() && meta.file_size > 0) { const Slice min_user_key = meta.smallest.user_key(); const Slice max_user_key = meta.largest.user_key(); if (base != nullptr) { //为新生成的sstable选择合适的level(不一定总是0） level = base->PickLevelForMemTableOutput(min_user_key, max_user_key); } //level及file meta记录到edit edit->AddFile(level, meta.number, meta.file_size, meta.smallest, meta.largest); } }

（2）将edit信息记录到version_

WriteLevel0Table执行完成之后，会将新生成的edit信息记录到version_（version_是整个LevelDB的元信息。每当因为 compaction生成新的sstable时，version_就会随之改动）中，当前的version_作为数据库的一个最新状态，后续的读写操作都会基于该状态。

代码语言：javascript复制代码语言：javascript复制//记录edit信息 versions_->LogAndApply(&edit, &mutex_); //释放imm_空间 imm_->Unref(); imm_ = nullptr; has_imm_.Release_Store(nullptr); //清理无用文件 DeleteObsoleteFiles();代码语言：javascript复制2. major compation

major compaction负责将磁盘上的sstable进行合并，每合并一次，sstable中的数据就落到更底一层，数据慢慢被合并到底层的level。

这种设计带来的一个明显的好处是可以清理冗余数据，节省磁盘空间，因为之前被标记删的数据可以在major compaction的过程中被清理。

level0中数据文件之间是无序的，但被归并到level1之后，数据变得有序，这使读操作需要查询的文件数就会变少，因此，major compaction带来的另一个好处是可以提升读效率。

（1）触发major compaction的时机

level 0层：sstable文件个数超过指定个数。因为level0是从Immutable直接转储而来，所以用个数限制而不是文件大小。level i层：第i层的sstable size总大小超过(10^i) MB。level越大，说明数据越冷，读取的几率越小，因此对于level更大的层，给定的size阈值更大，从而减少comaction次数。对于sstable文件还有seek次数限制，如果文件多次seek但是一直没有查找到数据，那么就应该被合并了，否则会浪费更多的seek。

（2）compaction流程

选择合适的level及sstable文件用于合并

筛选文件会根据size_compaction规则（level0层的sstable文件个数或当前level的sstable size总大小）或者seek_compaction规则（文件空seek的次数）计算应当合并的文件。

对于size_compaction，leveldb首先为每一层计算一个score，最后会选择score最大的level层的文件进行合并：

level 0层的score计算规则为：文件数 / 4；level i层的计算规则为：整个level所有的file size总和/(10^i)。代码语言：javascript复制void VersionSet::Finalize(Version* v) { // Precomputed best level for next compaction int best_level = -1; double best_score = -1 for (int level = 0; level < config::kNumLevels - 1; level++) { double score; //对于level 0使用文件数/4计算score if (level == 0) { score = v->files_[level].size() / static_cast(config::kL0_CompactionTrigger); } else { //对于非0层，使用该层文件的总大小 // Compute the ratio of current size to size limit. const uint64_t level_bytes = TotalFileSize(v->files_[level]); score = static_cast(level_bytes) / MaxBytesForLevel(options_, level); } if (score > best_score) { best_level = level; best_score = score; } } //使用compaction_level_记录需要合并的层，使用compaction_score_记录合并分数 v->compaction_level_ = best_level; v->compaction_score_ = best_score; }

对于seek_compaction，会为每一个新的sstable文件维护一个allowed_seek的初始阈值，表示最多容忍多少次seek miss，当allowed_seeks递减到小于0了，那么会将对应的文件标记为需要compact。

代码语言：javascript复制bool Version::UpdateStats(const GetStats& stats) { FileMetaData* f = stats.seek_file; if (f != nullptr) { f->allowed_seeks--; if (f->allowed_seeks level() == 0 ? c->inputs_[0].size() + 1 : 2); // list存储所有Iterator Iterator** list = new Iterator*[space]; int num = 0; for (int which = 0; which < 2; which++) { if (!c->inputs_[which].empty()) { //第0层 if (c->level() + which == 0) { const std::vector& files = c->inputs_[which]; // Iterator* Table::NewIterator for (size_t i = 0; i < files.size(); i++) { list[num++] = table_cache_->NewIterator( options, files[i]->number, files[i]->file_size); } } else { // Create concatenating iterator for the files from this level list[num++] = NewTwoLevelIterator( // 遍历文件列表的iterator new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]), &GetFileIterator, table_cache_, options); } } }代码语言：javascript复制参考链接：

[1] https://leveldb-handbook.readthedocs.io/zh/latest/basic.html

[2] https://draveness.me/bigtable-leveldb/

[3] https://izualzhy.cn/start-leveldb

文章推荐

大幅降低存储成本，Elasticsearch可搜索快照是如何办到的

【本文地址】

公司简介

联系我们