paxos协议_phxpaxos_一步一步理解paxos算法

在分布式中，最难解决的一个问题就是多个节点间数据同步问题。paxos协议为了解决这样的问题，涌现出了各种奇思妙想。只有在解决了如何进行信息同步的基础之上才衍生出形形的应用。这里开始介绍几种分布式通信协议。

totem协议也许你还比较陌生，但是corosync就是totem协议的一个开源实现。比较火的HA软件pacemaker就是基于corosync来提供各种服务的。说起totem协议，最简单的形象就是，他将多个节点组成一个令牌环。多个节点手拉手形成一个圈，大家依次的传递token。只有获取到token的节点才有发送消息的权利。简单有效的解决了在分布式系统中各个节点的同步问题，因为只有一个节点会在一个时刻发送消息，不会出现冲突。当然，如果有节点发生意外时，令牌环就会断掉，此时大家不能够通信，而是重新组建出一个新的令牌环。

说起paxos，需要稍微提提二段提交。简单来说，二阶段提交就是1.一个节点询问其他节点，我是不是可以进行消息提交。2.如果收到所有人的同意，则告诉大家，开始提交吧。这个协议在实际中并不能很好的解决分布式中信息同步问题。例如只要有节点失效，就会发生得不到所有人同意的结果，在超时后，这一次提交失败，等一系列问题。paxos协议但是paxos在对二段提交进行了优化后，得到了一个比较好的解决办法。

paxos协议引入了多数派，以及消息编号的概念。在1准备时，询问2/n+1的参与者，要求他们保证不会接受小于编号n的提交。

可以明显的看出，这就是对二段提交的一个优化版。就是这么一个比较巧妙的思想，解决了一些二阶段提交带来的问题。

gossip协议是一个神奇的协议。它常用于P2P的通信协议，这个协议就是模拟人类中传播谣言的行为而来。简单的描述下这个协议，首先要传播谣言就要有节点。节点每秒都会随机向其他节点发送自己所拥有的节点列表，以及需要传播的消息。任何新加入的节点，就在这种传播方式下很快地被全网所知道。这个协议的神奇就在于它从设计开始就没想到信息一定要传递给所有的节点，但是随着时间的增长，在最终的某一时刻，全网会得到相同的信息。当然这个时刻可能仅仅存在于理论，永远不可达。

第一阶段：

第二阶段：

1.通信方式。

当集群有节点要发起通信时，需要等待token。当拿到token后，先广播这次需要发送的数据，然后传递token来确认所有人都接收到消息。

如果确认成功，释放token。

2.节点的加入和退出。

当集群中有节点加入时，加入的节点广播一个加入信息，所有人都开始广播自己的信息，当所有人都获得同伴信息，开始由id最小的人提交一个token，交由所有节点确认。

如果都确认后，则节点正式加入，开始正常运行。

当集群有节点退出时，由于令牌环断链，触发token超时，则同样开始广播信息，然后由最小id提交token，经过确认后恢复正常。

gossip协议有多种实现，这里说一个例子当节点启动时，读配置文件，然后向一个seed发送信息，进行信息同步，然后开始没秒都随机选择一个seed节点来同步信息

1、随机取一个当前活着的节点，并向它发送同步请求

2、向随机一台不可达的机器发送同步请求

3、如果第一步中所选择的节点不是seed，或者当前活着的节点数少于seed数，则向随意一台seed发送同步请求

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29827-1.html