GentleRain tutorial 首先要知道最简单的causal consistency是怎么实现的 在论文Session Guarantees For Weak Consistent Replicated Data中有详细的说明 每一个更新都附带一个version vector，当远端数据中心的version vector大于这个更新的version vector的时候，这个更新才能被安装到远端数据库中。从而保证因果一致性。 下一个问题，当数据中心内进行数据分区的时候，我们要怎么处理？ 每个分区内部都维护一…
GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks Abstract GentleRain是geo-replicated data store，提供因果一致性 GentleRain用periodic aggregation protocol来决定更新是否能被其他人看到 GentleRain通过一个标量的时间戳来实现因果一致性。时间戳是从loosely synchronized physical clocks导出的，时钟漂移不会…
Percolator Tutorial Percolator是google推出的用来做增量计算的系统，主要用来替换MapReduce在Google Indexing System中的作用 这里我们只关注Percolator中的事务模型 前置知识: * 2PC - 保证跨分区事务的原子提交 * Bigtable - 底层存储，可以看作是分布式KVS * MVOCC - 并发控制算法 Bigtable Bigtable是Google基于GFS的一个存储系统 不看容错的话，就是一个LSM-Tree 和现代KVS不同的是，…
Don't Hold My Data Hostage - A Case For Client Protocol Redesign Abstract 我感觉之后我还是把摘要整个写一下 从数据库传输大量的数据到客户端是一个相当昂贵的操作。这个传输时间可以很容易就占有整个语句执行时间的主导部分。这对于一些外部数据分析的工具来说是一个很大的影响。在这篇论文中，我们将分析并探索将结果集序列化的设计空间。通过实现表明现有的方法都会有性能不足的情况。然后我们提出了一种列式的序列化方法。 （我猜测是不是通过列式存储提高压缩率，从而…
Constant Time Recovery in Azure SQL Database Abstract 这个恢复机制结合了ARIES和MVCC，从而实现了常数时间的恢复。 允许连续的log trucation，从而减少了日志空间的使用量，即使是有长事务的存在（对比Innodb，如果Undo table用完了就不能开新的事务了） 对于云数据库（Cloud database，应该是DBaaS）来说，这个能力是相当重要的，因为： 1. 数据库大小是不断增加的 2. 对于commodity hardware来说，fai…
Integrating Compress and Execution in Column-Oriented Database Systems Abstract 列存储的数据库可以提高相邻数据项之间的相似度，从而带来更好的压缩效果。 压缩的最好方式不仅取决于数据的属性，还取决于查询的workload（sql workload） Introduction 列存压缩的一个优势就是我们可以在压缩的数据上直接应用算子，从而提高CPU的性能。对于RLE（游程编码）来说，比如他把数据压缩成（42,1000），表示有1000个值为…
Optimal Column Layout for Hybrid Workloads Abstract 现代的analytical system是基于列存储。然后通过delta store来进行插入和更新 我们通过确定分区的数量，他们的大小和范围，以及缓冲区大小以及他们是如何分配的来组织数据的分布。 给出workload knowledge以及performance requirements，给出一个优化的物理布局 Introduction 目前的系统对于数据的布局都是固定的，这意味着他们会被局限在某个地方，而不能…
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…