Skip to content

paxos

一致性

  1. master节点选举
  2. 多机数据同步
  3. 事务

拜占庭将军问题

http://baike.baidu.com/item/拜占庭将军问题

由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的,或不存在本问题。

假设:n: 总的将军数,t: 叛徒数。则n ≥ 3t+1下有解。

Paxos

如何在一个可能发生任何异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致。

算法推导:http://blog.jobbole.com/110389/?utm_source=blog.jobbole.com&utm_medium=relatedPosts

算法原理:http://codemacro.com/2014/10/15/explain-poxos/

描述

阶段一:(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。
       (b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二:(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意:V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。  
       (b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。

paxos-flow

notes

所有的值都是proposer提出、acceptor只能接受或者拒绝、无权提出不同的值。
proposer
    K:发起propose的序列号
    V:发起accept时携带的值
acceptor
    maxN:迄今为止收到propose的最大的序列号
    acceptN:迄今为止已accept的最大的序列号
    acceptV:迄今为止已accept的最大的序列号携带的值

paxos-messages