Open Veiasai opened 5 years ago
Paxos是经典的实现最终一致性的分布式一致性算法。 Paxos中有三种Role,Proposer,Acceptor,Learner。
Proposer has two phase: prepare and propose
Proposer sends prepare request(a distinguish epoch number) to Acceptor.
Acceptor answers prepare unless the epoch is greater and ignore others.
Proposer sends a proposal request when has get promise from majority nodes of cluster.
If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than
值得注意的是,Acceptor会先记录自己做的决定(stable storage),再回复。 实际上的commit point就是出现了一个chosen value。 chosen value就是被大多数节点accept的value。
Acceptor已经有了完整状态,Leaner获取只是早晚问题。
Leaner可以获取所有Acceptor的信息,然后就能知道谁是被大多数节点accept的value。 但是问题在于,Acceptor failure。 像五个节点中,有三个节点达成一致,但是其中一个挂了。剩下两个不构成大多数。此时就无法得知谁是chosen value。(从这个角度来看,相当于没有变成chosen value,不管Acceptor在何时fail,它只要在将accept value传递出去之前fail,从外界来看,都是一个效果)
这里我觉得唯一的问题在于,当Acceptor在回复Proposer之后挂了,Proposer会认为自己提交成功,但此时没有learner能学到这个值。
Proposer也不会重新发起proposal。
此时可以由learner发起新的proposal,(因为他发现没有值被确定),当发起新的一轮,之前Proposer提交的值,肯定会被再次提交(Proposer能够提交某个值时,意味着,这个值的epoch number 已经在大多数节点上,是一个最大值。提交成功后,大多数节点已经accept了值)。所以最终还是chosen value。
Comment: 晦涩难懂。
PS: 一个值被选为chosen value -> (value, num) 也就是有了大多数的节点accept了这个value
此时,集群中不会存在 (another value, num2), num2 > num , accepted.
之后,再怎样prepare,最终都会变成chosen value.
Abstract The Paxos algorithm, when presented in plain English, is very simple