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年这篇主要讲是讲数据库的上半部分...

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都至少有一个节点发...

漫谈复制状态机的几个有趣的问题

漫谈复制状态机的几个有趣的问题
读过Paxos等论文的读者,应该对复制状态机(Replicated State Machine)的概念并不陌生。复制状态机在分布式系统中是一个很简单却很强大的模型,也是一种很有价值的思想。 模型一句话描述就是:多个节点上,从相同的初始状态开始,执行相同的一串命令,产生相同的最终状态。 这里有几个有趣的问题。   复制状态机保持一致是什么意思? 实际上,与其说是一致,其实可以泛化为分布式的两个节点状态存在某种...

Raft One-Server成员变更

Raft One-Server成员变更
前面介绍了Paxos成员组变更,现在根据Raft博士论文介绍一下Raft是怎么做成员组变更的。前者更多描述几个核心的思想,而后者更加实用,介绍了实践过程中遇到的一些实际问题。 Raft博士论文描述了两种变更方案: One-Server变更:一阶段变更,要求每次成员组从G1变成G2时,G2相比G1加一个成员或者减一个成员。 Joint Consensus:支持任意的变更,即从成员组G1变成G2,不要求G1和G2有什么关联,比如可以完全...

Reconfiguring a State Machine

Reconfiguring a State Machine
  Reconfiguring a State Machine这篇论文主要讲解成员组reconfigure,即成员变更。发表时间还是2010年,相比Paxos原始论文的发表时间已经过去20年了。本博文先解读这篇论文,Raft做成员变更的方案后面另文阐述。 Reconfiguration是指在分布式系统执行过程中,改变系统内进程(副本)集合的动作。例如,Paxos成员组从(S1,S2,S3)变为(S1,S2)。成员变更可以改变成员组大小(从五个副本改为三个副本),...