High-Performance Concurrency Control Mechanisms for Main-Memory Databases 这次换一个记录的方式。点出思考和关键点，而不是类似翻译似的看文章 single version locking works well when transaction are short and contention is low The multiversion schemes have higher overhead but are much less sensit…
Opportunities for Optimism in Contended Main-Memory Multicore Transactions 看这篇文章主要是看看各种并发控制的protocol Abstract 他提到那些与concurrency control无关的implementation choices是导致性能下降原因。 Intrudoction partially-pessimistic concurrency control, dynamic transaction reordering以及M…
Serializable Snapshot Isolation in PostgreSQL Abstract 就是SSI在Postgres中的实现 Overview Postgres之前只有snapshot isolation。9.1版本提供了SSI的实现。 Postgres的SSI实现必须要和现有的特性结合，而不能像research prototype一样忽略很多细节。比如要支持replication，two phase commit，subtransaction。还有控制memory useage。 和之前的系…
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就可以被删除。因为他对…