A Comparison of Adaptive Radix Trees and Hash Tables Abstract 比较ART, Judy Array, 两种基于二次探测哈希的变体，三种Cuckoo Hashing的变体 结果发现ART和Judy都不能与哈希方法相比 Introduction 这里提到了这里的比较只用于integer: We only focus on keys from an integer domain. In this regard, we would like to point ou…
Building a Bw-Tree Takes More Than Just Buzz Words 两个贡献，一个是Bw-Tree的实现教程，并且提出了新的优化策略。第二个则是发现BwTree并不如其他使用锁的并发数据结构更快 Introduction Lock-free的数据结构实现的难点： 1. 需要明白所有的race conditions 2. 并发线程的同步点通常不会放到算法中，导致人们实现出错，最后变成了busy-waiting loop 3. 需要保证所有的读者全部离开后才能回收内存（在mit os中…
introduction里就是一些对MVCC的介绍。不过最后他提了一点我觉得比较关键 Careful engineering, however, matters as the performance of version maintenance greatly affects transaction and query processing. Main Contribution: 1. 低开销的MVCC implementation 2. 基于Precision Locking的变体的一种串行化的方法 3. 一种s…
Abstract 他首先提出HTAP workload中，GC通常会成为bottleneck 现有的GC技术过于粗粒度。并且不能很好的处理sudden spike的workload Introduction MVCC的一个问题就是如果workload中有很多的long-running transactions，那么活跃的版本就会增加的非常快，并且我们不能删除掉这些版本因为他们可能要被活跃事务使用 所以这些long-running transaction就会导致一个恶性循环 因为他们持续的越久，那么活跃的版本就越多，…
这个paper提出了session guarantee从而可以避免弱一致性级别带来的问题，同时还可以保持弱隔离级别的优势 A session is an abstraction for the sequence of read and write operations performed during the execution of an application 提出session的目的不是为了和事务对应（事务是用来保证ACID的），session的目的则是为了给用户提供一个一致性的视角。 贴一下原文：Sessi…
这篇论文讲的就是lamport的logic lock The Partial Ordering 如果一个事件A发生早于B，大多数人会说A发生在B之前。因为他们会用物理时间来证明这个定义。然而，如果一个系统要满足规范，那么这个规范就必须根据系统内可观察到的事件给出。如果我们的规格是物理时间，那么系统必须包含真正的时钟，而且就算是他包含了真正的时钟，我们也会遇到时钟不准确的可能性。所以我们不通过物理时钟定义“happened before“ 我们假设一个系统由若干个进程组成，每个进程包含了具有全序关系的若干个事件。同时…
整体架构 貌似和bigtable完全相同 level由这几个组建组成 memtable 是一个主存中的跳表。按序存储。当容量到达阈值的时候就转换成一个不可修改的memtable immutable memtable 不可修改的memtable。当他被创建的时候，leveldb的后台压缩进程会利用其中的内容创建一个sstable。持久化到磁盘中 log WAL，每次写操作要先顺序写日志。从而保证我们可以从异常状态下恢复。 写操作的原子性也由日志来保证，当日志成功写入的时候，写操作成功。当写日志异常的时候，后续的恢复会…
Abstraction 论文中说这个percolator是用来进行增量处理的一个系统，用来替换MapReduce在google indexing system中的作用 但是没有提到transaction相关的东西 Introduction 考虑我们为网页构建索引的任务。索引系统首先会把每个网页都爬下来，如果有多个URL都指向了相同的内容，那么拥有最高的PageRank的URL会被保留下来放到索引中。我们还会把每一个链接对应的anchor text附在他指向的页面中。同时要保证对于链接指向的重复的内容，我们也会把它转…
Consistency level in DBMS CAP中的C和ACID中的C都代表了consistency，但是他们的含义是完全不同的。 比如ACID中，一致性是指用户定义的语义。指的是我们不会违反引用约束，外键约束，以及一些用户定义的约束。 而在CAP中的C指的是让并发执行的分布式系统表现的像是一个单线程的中心化的系统。在某一时刻的读必须只有一种可能的情况，即他们反映了最近写入的数据 在ACID中，consistency level通常是不会使用的。因为ACID中的C基本上都是application deve…
背景 隔离的定义（为了清晰我就贴原文而不是自己翻译了） Database isolation refers to the ability of a database to allow a transaction to execute as if there are no other concurrently running transactions 隔离的目的就是我们在并发执行事务的时候不希望一个事务的读写操作作用于一些临时的，错误的，或者不完整的数据 最强的隔离级别被成为可串行化（serializability）…