Home

minor compaction主要解决内存数据持久化磁盘。major compaction 则负责将磁盘上的数据合并，每合并一次，数据就落到更底一层。 1. 作用 随着数据合并到更大的 level，一个明显的好处就是清理冗余数据。 如果不同 level 的 sst 文件里，存在相同的 key，那么更底层的数据就可以删除不再保留（不考虑 snapshot的情况下）。为了充分利用磁盘高性能的顺序写，删除数据也是顺序写入删除标记，而真正删除数据，是在 major compact 的过程中。 所以，一个作用是能够节省磁盘空间。 level 0 的数据文件之间是无序的，每次查找都需要遍历所有可能重叠的文件，而归并到 level 1 之后，数据变得有序，待查找的文件变少。 所以，另外...

Iterator 的思想在 stl 很常见，通过迭代器，可以实现算法和容器的解耦。当我们实现某个算法时，只需要关注迭代器的常见操作，例如++ --等，而不用关心作用的具体容器是 map 还是 vector. 在 leveldb 的代码里，迭代器的应用也非常普遍，接口上变成了next prev等，在我看来主要有两个好处： 通用的设计：我们已经都习惯了迭代器的使用，通过Iterator来提供遍历数据的接口，学习成本低，protobuf里也在大量使用。 2.易于实现：在不同的数据上，实现相同的Iterator接口，使得在操作这些不同数据时，可以统一使用Iterator.这个跟 stl 里的思想是一致的。 正是由于大量的使用，理解leveldb 的Iterator，对通顺的阅读源...

继续接着上一篇笔记的结尾讲，这篇笔记介绍下筛选参与 major compaction 文件的过程，算是介绍 major compaction 的一个开端。 1. 当我们谈论筛选时，在谈论什么 leveldb 最为复杂的在 compaction，compaction 最为复杂的在 major compaction.面对磁盘上的众多 sstable 文件，应该怎么开始？ 千里之行始于足下，首先需要找到最应该 compact 的一个文件。 “最应该”的判断条件，前面笔记已有介绍，有seek_compaction && size_compaction，分别从读取和文件大小两个维度来判断。 筛选出这个文件后，还需要考虑一系列问题： 如果在 level 0，由于该...

major compaction 一个首要问题，就是要 compact 哪个文件。这个计算是在version完成的，与之相关的主要是两个属性allowed_seeks compaction_score。 1. seek_compaction 一个直观的想法是如果文件多次 seek 但是没有查找到数据，那么就应该被 compact 了，否则会浪费更多的 seek。用一次 compact 来解决长久空 seek 的问题，本质上，还是如何平衡读写的思想。 具体的，当一个新文件更新进入版本管理，计算该文件允许 seek 但是没有查到数据的最大次数，当超过该次数后，就应该 compact 该文件了。 对应到代码实现，是在VersionSet::Builder::Apply阶段:https...

这篇笔记讲下minor compaction过程中version是怎么生效的，算是对 minor compaction 介绍的补充。 imm_持久化为 sstable 文件后，文件的相关信息通过meta返回 { mutex_.Unlock(); //更新memtable中全部数据到xxx.ldb文件 //meta记录key range, file_size等sst信息 s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta); mutex_.Lock(); } struct FileMetaData { int refs; int allo...

上一篇笔记开始讲 minor compaction，对于 memtable 转化为 sstable 这个过程，在之前的笔记里都做了很多的铺垫，例如 MemTable/SSTable 的数据结构，写入/读取的整个流程等，因此理解起来应该不算复杂。不过其中涉及版本的操作，例如versions_->LogAndApply(&edit, &mutex_);，如果没有抓住 leveldb 里 version 相关的关键结构，很容易被绕晕。 这篇笔记，开始讲下 version. 1. 为什么要有版本管理 compaction 简言之，是一个新增与删除文件的过程。例如对于上一篇介绍的 minor compaction，是新增一个文件。对于 major compaction...

在level笔记开篇里，提到过Compaction这个过程，这是 leveldb 中最为复杂的一部分，从这篇笔记开始，介绍下 Compaction. compaction 分为两种:minor compaction 和 major compaction. minor compaction 相对简单一些，对应了MemTable持久化为sstable的过程。 1. 简介 DBImpl定义了两个MemTable: MemTable* mem_; MemTable* imm_ GUARDED_BY(mutex_); // Memtable being compacted 当size of mem_ <= options_.write_buffer_size时，数据都...

your browser does not support the video tag 1. WHY? STL algorithms can make code more expressive Avoid common mistakes Used by lots of people 2. THE WORLD OF C++ STL ALGORITHMS 2.1. LANDS of PERMUTATIONS 2.1.1. PROVINCE OF HEAPS make_heap push_heap pop_heap 2.1.2. SHORE OF SORTING sort partial_sort nth_element /...