SSTable(1) data block 每次minor compaction都会生成新的sstable，major compaction会将若干个sstable合并成一个大的sstable。 这次我们看一下sstable的读写过程。参考文章在这里 一个sstable文件按照块划分，用来提高读写效率。每个块的大小为4kb，每个block中除了存储数据还有压缩类型以及校验码 sstable中不同的block有不同的功能 data block 由于leveldb是按序存储，所以我们会使用类似前缀压缩的技术。不同的是每…
Memtable 这次到了memtable中，也就是leveldb的内存中数据结构 参考文章 跳表的思路就是通过概率来进行平衡，而非平衡树那样强制平衡。从而使得我们的实现可以简化很多。 上面这个例子就是增加指针的链表。让我们可以稳定按照2的次幂的步数进行跳跃。但是缺点就是很不容易处理，因为插入的时候要去仔细计算我们跳过了多少节点，从而判断是否增加额外指针。 一个拥有k个指针的结点成为k层结点。50%的结点为1层节点，25%的结点为2层节点。如果保证每层结点的分布概率相同，则仍然可以拥有相同的查询效率。 有关更加细节…
Log 这一次来看看日志，参考文章在这里 leveldb不提供事务，所以我们不必记录undo log来保证事务原子性。但是需要提供redo log来保证数据是持久化的。 每次写入write batch到memtable之前，要先将操作写入到日志中。保证写操作在之后是可以redo的。 在将memory db冻结成为immutable memory db后，对应的日志文件也会被冻结。然后通过minor compaction将immutable memory db写入成SSTable后，冻结的log就可以被删除。因为他对…
Read 这次参考的文档还是读写操作。主要看一下读的过程 在db_impl.cc中的Get是读的核心逻辑 如果选项中确定了要读的snapshot，我们就拿到这个sequence number，否则的话就获得最新的sequence number 目前还没有仔细看version的结构，但是根据代码大概可以看出来。我们拿到当前活跃的memtable，不可变的immtable。增加他们的refcnt。这样可以防止我们在访问这个数据结构的时候他被其他线程删除掉。 先尝试从memtable中读。如果成功的话就返回了。 否则的话…
Write 还是跟着leveldb handbook去看代码。这次主要是读写操作 主要是走马观花的看一下写操作的实现。 写操作对应的接口主要是Put和Delete 他们都对应了batch中的一个数据 Put会包含Key和Value，而Delete则只含有Key 他们都会调用Write来进行写入 leveldb同一时刻只允许一个写入操作将内容写入到日志以及数据库中。为了减少日志文件的写入，同时增加整体的写入性能。leveldb会将若干个小写入合并为一个大写入。 将当前的Write追加到writers中。然后等待。这里…
Efficiently Compiling Efficient Query Plans for Modern Hardware Abstract 这个Abstract写的很清楚。现有的iterator model在执行的时候对locality，以及instruction prediction利用率很差。导致执行性能比不上hand-written的代码。即便是有vectorized tuple processing，只能缓解这个问题，但是性能还是不够。 本文提出了一种基于LLVM框架的将query翻译成机器码的方法。…
Overall 开始看leveldb的代码。leveldb整体代码量不多，所以读起来应该不会很困难。并且有比较完善的leveldb handbook。读得时候要多加考虑他的设计因素。 这次从doc中的index看一下整体的概念。文档在这里 #include <cassert> #include "leveldb/db.h" leveldb::DB* db; leveldb::Options options; options.create_if_missing = true; leveldb::Statu…
bthread_id 这里的bthread id不是标识bthread的identifier，而是用于同步的一种数据结构 我们之前在channel中看到过他，用来做同步的brpc brpc中也有相关的文档 这么看他的名字叫rpc id更合适一些 这里粘一下文档的东西 bthread_id包括两部分，一个是用户可见的64位id，另一个是对应的不可见的bthread::Id结构体。用户接口都是操作id的。从id映射到结构体的方式和brpc中的其他结构类似：32位是内存池的位移，32位是version。前者O(1)时间定…
piecewise_construct 之前就被piecewise construct折磨住过。后来重新看一下发现其实在cppreference中写的很明白了 piecewise constuct实际上就是一个empty class tag，他的作用就是为函数添加一个可重载的参数，从而避免歧义 The overloads that do not use std::piecewise_construct_t assume that each tuple argument becomes the element of …