闫鹏 blog

今天早茶的topic。介绍了paxos算法与zookeeper相关的内容，可以解决单点问题觉得还挺实用的。这个算法由三个不同类型的实体，通过投票的方式决策出一个值传播到网络中，实现分布式数据的统一，使各个节点不会各自为政。

paxos是一种比较主流的算法，google与微软的集群都用这个，具体参与进来的有三个实体：

1.提议者：提议者发起新的提议，比如设置某个值。每个提议都有个编号。提议者根据参与者的反馈，多数参与者赞同的提议就获得通过。

2.参与者：参与者对提议者的提议进行投票，将投票结果反馈给提议者。当有多个提议时，参与者倾向于接受编号大的提议。例如已经接受编号n的，此时收到了编号为n-1的提议，就会拒绝

3.接受者：接受提议者与参与者的决策（获得投票通过的提议）。

一个典型的也是最简单的流程：

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

如图，为了简单理解，可以认为proposer与acceptor是相同功能server构成的一个集群，client可以认为是一个外部的用户，发送一个请求到集群后，集群中的一个server扮演提议者角色发起一个提议，后面的三个accepto进行投票，投票反馈给提议者后发现获得通过，acceptor将信息扩散给接受者。这样整个集群中就针对这个提议达成了一致。

根据这个算法，接受者收到的信息是顺序的，不会产生乱序的问题。所以对于需要序列化的服务，就可以使用这种方式将单点整成多点，避免运维风险。

还有一些更复杂情况以及一个极端情况请见参考资料吧，另外：

1.集群中有多少个节点，首先就是各个节点就是要知道的。集群中要想增加一个新的节点比较麻烦

2.当集群中有效的节点数是少数时，算法会失效

zookeeper是用来协调分布式应用的，用于维护资源信息，它的关键算法就是用的paxos来做的。当然，在其上也有一些更复杂的内容。提供服务的节点作为client链接到zookeeper上面，与zookeeper保持心跳。当client宕机，zookeeper中的一个服务节点发现后就会通过投票流程来判定这个client挂掉了，其它依赖于这个client的服务作为算法中的接受者，收到挂掉的信息后，将依赖改到其它的client上面去。当然，也存在client断开zookeeper中的一个节点后连到zookeeper的另外一个节点，但因为算法保证了发送给client断开与联通消息的顺序，也是可以满足需求的。

在我看来，zookeeper的最大作用是使资源配置服务器本身从单点变为多点，避免了单点运维的问题。对于paxos算法还是很不错的，对于需要将系统中需要将命令序列化，而又希望避免服务单点是一个非常有效的方法。

参考资料：
1.Paxos algorithm
2.zookeeper

---------------------------------------------------------------
本站作品根据创作共同协议进行授权, 转载时请务必以超链接形式标明文章原始出处
原文地址：http://www.mirecle.com/2010/04/29/paxos-algorithm-to-solve-the-problem-and-the-resources-to-locate-a-single-point.html
---------------------------------------------------------------