async_simple Coroutine 简单看看async simple的coroutine的实现。 async_simple的coroutine是通过Lazy<T>实现的，即每一个Coroutine的返回值都是Lazy<T>，然后我们可以通过co_await Lazy来等待一个coroutine的返回值。 所以这里要关注的有两个点，一个是Lazy是怎么开始执行一个coroutine的，即关注Lazy的promise_type，另一个就是在coroutine内去co_await一个La…
async_simple Future/Promise 概览 简单看看async_simple的Future/Promise。注意这里不会关注coroutine/uthread部分 Future/Promise这块和folly，以及seastar的接口都是类似的，之后可以再写一下他们实现上的区别。 简单来说，就是Promise可以获取一个对应的Future，对应生产者和消费者。然后Future可以通过then(Func &&func)来创建一个continuation，表示在这个future获取到结…
Cache 这次看看Cache 和文档中的不同，文档中的这个是goleveldb的。而我们看的是C++的leveldb C++的leveldb就是一个简单的LRUCache 并发控制通过一个大mutex来保护。为了减少冲突分了Shard 不过leveldb中的LRU是intrusive的，他的Node内嵌了list和hashmap的变量 LRU的主体在这里，其中HandleTable是一个哈系表，由key映射到Handle上 lru和in use其实可以猜到，一个是lru的链表，一个是当前使用的，也就是pin住的链…
SSTable(3) Read & Write 参考文档在这里 还是看这个图。footer是固定的，通过footer去找到meta index block和index block meta index block指向filter block，为什么不直接让footer指向filter block呢？因为meta index block中存储了filter的名字，是变长的。而footer是定长的。所以增加了一个额外的indirection 代码中主要是在table builder做写操作 table buil…
SSTable(2) filter block 文档在这里 这次代码比较简单 StartBlock的作用就是不断构建索引到filter offsets Finish会把剩下的数据的filter构建出来。然后把每块对应的offset追加进来，最后加上总共的array length以及BaseLg。具体含义可以看文档 result就是这些data block 可以看到核心的逻辑就是这个GenerateFilter了。他会先把当前的buffer切成原本的key。然后通过CreateFilter创建filter 这里的Cr…
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中读。如果成功的话就返回了。 否则的话…