Home

从输入网页到显示出网页内容，这个过程只有短短几秒的时间，作者却写成了一本书。作为一个半路出家的程序员，这本书就像一本科普读物一样，把我很多零碎的知识点串了起来。但即使作者没有展开来讲，很多地方已经看的让我云里雾里不知所云了，很佩服作者的知识面。 列下书籍大纲，权且备忘： 网络包的旅程：

本文总结下 leveldb 一些好的代码习惯。 1. 返回信息丰富 leveldb::Status除了返回码，可以提供更丰富的返回信息。 例如,leveldb::DB::Put接口的返回值： virtual Status Put(const WriteOptions& options, const Slice& key, const Slice& value) = 0; 内部使用const char*来记录全部内容： // OK status has a null state_. Otherwise, state_ is a new[] array /...

二分法是个很有意思的话题，思路很简单，也能极大的提高程序的性能，之前我们介绍过如何写出正确的二分法以及分析 。因为二分法在 leveldb 使用非常常见，这篇笔记炒个冷饭，再结合着 leveldb 源码讲下二分法最重要的一个概念：循环不变式。 1. Block 内的 Seek 当我们查找 target 是否存在于某个 data block，用的就是二分法，二分的对象是 restart points. restart points 将 entry 分为多组： 每组包含多个key:value数据，每一个 restart point 指向一组里最小的那个 entry，我们称为 min-key entry. Seek的目标是找到第一个 >= target 的 entry. ...

这篇笔记介绍下写入和读取过程，前面已经铺垫了很多基础组件，写入介绍起来相对简单一些了。 1. Put 先用一张图片介绍下： 写入的key value首先被封装到WriteBatch // Default implementations of convenience methods that subclasses of DB // can call if they wish Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) { WriteBatch batch; //key,value数据更新到batch里 batch.Put(key,...

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...