Compartmentalization方式scale复制状态机

Compartmentalization方式scale复制状态机
  Scaling Replicated State Machines with Compartmentalization，VLDB 21'   本文是针对Multi-Paxos协议的实现方案瓶颈做的扩展性方案，主要的方法论是compartmentalization，这个词本意是分离，在这里作为一种方法论，其含义是将各个功能进行剥离分开，并分别进行扩展。 Multi-Paxos的多个模块都有一些实现方案上的瓶颈，假设读者已经熟悉Multi-Paxos协议内容，我们根据论文的思路看看各个瓶...
2022年01月19日 分布式 暂无评论 喜欢 0 阅读 155 次 阅读全文

浅析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...
2020年04月30日 分布式, 数据库 暂无评论 喜欢 2 阅读 1,148 次 阅读全文

偏序/DAG的一个例子

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

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...
2020年04月04日 分布式 暂无评论 喜欢 0 阅读 361 次 阅读全文

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

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

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，...
2019年03月17日 分布式 评论 5 条 喜欢 0 阅读 880 次 阅读全文

Raft的乱序commit和乱序apply

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

Anna KVS中的Lattice是什么？

Anna KVS中的Lattice是什么？

Anna KVS官网对Anna的特性总结得非常到位：1. Crazy Fast, 2. Super-Scalable, 3. Flexibly Consistent。这里只关注Flexibly Consistent这一项，讲讲Anna是怎么实现灵活的consistency的。这篇博客算是论文导读，详细内容读者仍要仔细阅读论文原文 Anna: A KVS For Any Scale。
Lattice是什么，基于格怎么实现灵活的多种一致性，漫谈Consistency和Isolation Level。

2018年12月22日 分布式 评论 3 条 喜欢 1 阅读 1,612 次 阅读全文

Spanner: Becoming a SQL System论文阅读笔记

Spanner: Becoming a SQL System论文阅读笔记
  继2012年在OSDI年发表了Spanner论文《Spanner: Google’s Globally-Distributed Database》之后，Google在SIGMODE'17上发表了第二篇关于Spanner的论文《Spanner: Becoming a SQL System》。从整个的数据库系统角度看，2012年那篇讲是的Spanner的下半部分Storage Engine的一些feature：数据自动分区和全球部署、多副本Paxos高可用、支持外部一致性的分布式事务。2017年这篇主要讲是讲数据库的上半部分...
2018年12月01日 分布式, 数据库 暂无评论 喜欢 0 阅读 929 次 阅读全文

Quorum System的故障概率和负载

Quorum System的故障概率和负载
最近读到一个有趣的话题：Quorum System的故障概率和负载。   首先是一些概念： 节点集合 V=\{v_1, v_2, .., v_n\} Quorum  Q\subseteq V Quorum System \mathcal{S} \subseteq 2^V，且Q_1 \cap Q2 \neq \emptyset, \forall Q1,Q2 \in\mathcal{S} 故障概率Failure Probability: 假设每个节点故障概率为p，Quorum System  \mathcal{S}的故障概率记为F_p( \mathcal{S})等于每个Quorum都至少有一个节点发...
2018年11月13日 分布式 暂无评论 喜欢 0 阅读 669 次 阅读全文