[paper note]Consensus on Transaction Commit

这篇论文的作者实在太吓人了,Jim Gray和Leslie Lamport,两个领域的扛把子。论文介绍的内容叫Paxos Commit,是用分布式共识算法解决分布式事务的原子提交问题,不愧是这两位大佬写出来的文章哈哈。

PS:这篇文章是我的paper note,主要是帮助自己理解和记忆,与其说是文章,其实更像是简单的笔记。

解决了什么问题


事务的属性是ACID,A代表原子性,事务要么全部提交,要么全部失败,不能出现提交了一半的情况。单机事务的原子性通过日志系统来保证,而在分布式事务里,通常的做法是两阶段提交(Tow Phase Commit,2PC)。

两阶段提交的一个重要问题是协调者宕机问题,参与者执行完Prepare状态后,参与者处于“未决”状态,意味着参与者自己无法决定事务状态,而如果此时协调者宕机,事务的状态将无法推进下去。

Paxos Commit希望解决这个问题,即在事务提交过程中,能够容忍F个副本失败而不会导致事务无法推进。

另外,论文中还提到了其他尝试解决此问题的方法(三阶段提交),并表示不屑一顾……….(三阶段提交实际上并没有改善提交过程的容灾)

继续阅读:

Paxos revisit

前一段时间借着组里的实习生学习交流的机会,又重新讨论了一次Paxos算法,颇有收获。本文整理记录几个我个人觉得比较有意义的问题,希望通过思考这几个问题,能够加深你对Paxos算法的理解。

本文假定读者已经对Paxos算法有一定了解(包括原理、正确性证明、执行流程),如果你还不了解Paxos,请移步这里

Paxos算法流程


在思考问题之前,首先重温一下Paxos算法的流程,同时统一变量名称,方便后文讨论。

Prepare阶段:

  1. Proposer选择proposal number n,并向acceptors发送Prepare(n)消息
  2. Acceptor收到Prepare(n):if n > minProposal then minProposal = n; return (acceptedProposal, acceptedValue)

Accept阶段:

  1. 如果Proposer收到了超过多数派acceptors对于Prepare(n)的回复,如果回复中有包含acceptedValue,则选择acceptedProposal值最大的作为value,否则Proposer可以自行选择value
  2. Proposer向所有acceptors发出Accept(n, value)消息
  3. Acceptor收到Accept(n, value):if n >= minProposal then acceptedProposal = n; acceptedValue = value,并回复AcceptAck(n)
  4. Proposer收到来自多数派acceptors的AcceptAck消息,value已达成决议(chosen)

问题


在上述Paxos算法流程的基础上,仔细思考下面几个问题:

  1. 为了保证算法在容灾(节点故障重启)场景下的正确性,Acceptor上需要持久化哪些信息?
  2. 如果Acceptor不持久化acceptedProposal,在Prepare阶段的第2步中minProposal代替,有没有问题?

  3. Accept阶段,Proposer不用n覆盖acceptedProposal,仍将其发送给Acceptor,Acceptor收到Accept(n, acceptedProposal, value)之后使用消息中的acceptedProposal而不是n来作为acceptedProposal,有没有问题?

  4. 在5个节点的情况下,如果修改流程为Proposer要收到4个acceptor对Prepare(n)的回应才可以发送Accept消息,要收到2个acceptor对Accept(n, value)的回应才能确认决议,有没有问题?

  5. 论文中提到Proposer选择proposal number要递增且不重复,这个要求是不是必要的?如果把Prepare阶段第2步中的>改为>=呢?

WARNING: 强烈建议花一些来仔细思考上面的问题,在得出自己的答案之后再继续往下看

继续阅读: