浅析Aurora Quorum

浅析Aurora Quorum
  Aurora在SIGMOD18'的论文《Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes》中描述了Aurora关于共识方案的选择和Quorum方案的详细内容,本文这里做一些简单的分析。     Aurora架构背景 在描述Aurora的Quorum方案前,先介绍下Aurora的系统架构。 Aurora是share-storage、一写多读的架构,构建在MySQL(InnoDB)代码库上,当然后来增加了mult...

偏序/DAG的一个例子

偏序/DAG的一个例子
  序问题可以说是分布式系统中天字第一号问题,因为它来自分布式系统最基础的那个系统模型假设 - 异步网络,而且影响了分布式系统算法设计等等很多方面。分布式系统的序问题阐述起来非常庞大,这里只是简单描述下跟偏序/DAG的一个例子 - 区块链公链的DAG。   前面已经写过一点关于偏序的东西,读者可以参见Anna KVS中的Lattice是什么?里面介绍的一些内容。   首先从比特币网络开始,比特币...

DDIA Quick Note

DDIA Quick Note
说明 《Designing Data-Intensive Applications》从数据系统角度介绍了方方面面的技术点。 内容上,基本都是一个分布式数据库存储引擎所需要的技术能力,而且很多技术点讲的很详细,不过计算引擎基本上没涉及。 另外书里面也介绍了一些其他的数据系统,也都比较有价值。     Part 1 Foundations of Data Systems Chapter 1 Reliable, Scalable, and Maintainable Applications Thinking About D...

Jeff Dean点赞的Consensus Revised论文在说啥?

Jeff Dean点赞的Consensus Revised论文在说啥?
  《Distributed consensus revised》 Heidi Howard 整篇论文151页,粗略通读了一遍,主要是了解各个变体的基本思路和正确性直觉的理解,更形式化的证明基本上都跳过了。 这里假设读者对Basic Paxos有了一定了解,看过Lamport的那篇原始论文。另外我这里行文术语基本沿用原始论文的说法,跟这篇论文稍有差异,不过如果熟悉Basic Paxos的话,应该很容易对应起来。   导读 FLP定理已经证明了在异步...

RUM Conjecture

RUM Conjecture
《Designing Access Methods: The RUM Conjecture》 这篇论文从读、写、存储空间开销角度总结了access method设计,并提出了一个RUM猜想,认为针对其中两个开销优化,则会导致第三个优化困难。 就RUM猜想本身的可信程度而言,我个人觉得一般,不过这种三角可视化的总结非常有趣,可以一读。   What is RUM Conjecture 作者总结了Access Method的一些trade off,审视了RUM三种开销:R是read overhead,...

Raft的乱序commit和乱序apply

Raft的乱序commit和乱序apply
  不知怎么地,前一阵子知乎上对Raft的乱序的问题的讨论就变多了。我觉得其实这个问题可讨论的东西并不多。   Raft作者觉得Multi Paxos太复杂,所以搞了一个Raft。Raft加了很多约束,其中可能最重要的一条就是只能顺序commit。 所以,顺序commit的锅,Raft是得好好背着,翻不了案的。   值得谈一谈的是乱序apply。 能不能乱序apply本质上取决于你的状态机的设计。   比如,考虑rocksdb...