美文网首页
Paxo算法学习(一)

Paxo算法学习(一)

作者: fertilizer | 来源:发表于2017-11-20 21:58 被阅读0次

个人理解,如果有不对之处,请指出。
Paxo算法用于分布式算法,为的是保证CAP中的consistency。
算法的目的是加速整个cluster的replication数据一致。
然后就需要明确几个概念:
算法中的主要成员:

  • Proposer:负责提交提案,为了简单表示可以用[V, N], value代表提案中的数据,N其实就是代表优先级N,简单点地说,小于N的一般提案都不起作用。
  • Learner:Acceptor告知learner哪些value被选定了
  • Acceptor : 只要Acceptor接受某个提案,Acceptor就认为该提案的value就被选定了。

最终要达到的效果就是Proposer,Acceptor和Learner都认为同一个value被选定了。也就是保证最终有一个value被选定了,当value被选定后,进程最终也能获取到被选定的value。

叙述Paxos算法的流程:
总共分为两个阶段:
Phase 1

  1. Proposer选择了一个提案编号N,向半数以上的Acceptor发送编号为N的Prepare请求。
  2. 如果Acceptor已经接受过提案,那么就向Proposer响应已经接受过的编号小于N的最大编号的提案。

Phase 2

  1. 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它会发送一个针对[N, V],V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。
  2. 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求作出过响应,它就接手该提案。

Learner学习被选定的value有三种方案:solution 1:Acceptor接受一个提案,然后发送给所有learner,solution 2: Acceptor接受一个提案,就将该提案发送给主learner,然后分发。 3. 接受一个提案,然后发送到一个集合里,然后再分发。

具体推导待有时间再学习,整个算法流程还是很清楚的。

Reference:

http://blog.jobbole.com/110389/
https://bitbucket.org/sciascid/libpaxos.git

相关文章

  • Paxo算法学习(一)

    个人理解,如果有不对之处,请指出。Paxo算法用于分布式算法,为的是保证CAP中的consistency。算法的目...

  • zookeeper原理

    理解zookeeper需要了解paxos算法,zookeeper是paxos算法的工业级实现。 #### Paxo...

  • Zookeeper小芝士(二)

    ZooKeeper使用的ZAB协议与Paxo算法的异同?Paxos算法是分布式选举算法,Zookeeper使用的 ...

  • Raft 算法(详细版)

    1. Raft 算法简介 1.1 Raft 背景 在分布式系统中,一致性算法至关重要。在所有一致性算法中,Paxo...

  • Paxos算法

    Paxos算法解决的问题正是分布式一致性问题,即一个分布式系统中的各个进程如何就某个值(决议)达成一致。 Paxo...

  • 死磕Zookeeper系列-3-Paxos算法

    大纲 https://www.zybuluo.com/yulongsun/note/1012707 1. Paxo...

  • 机器学习(1)——几个基本要素

    学习算法 什么是学习算法,学习当然不是一个动词,学习算法最简单的理解便是能够从数据中学习的算法,学习的解释根据 M...

  • StanFord 机器学习公开课笔记(4):生成学习算法

    本讲视频及讲义链接 生成学习算法 生成学习算法和判别学习算法的区别 判别学习算法(Discriminative) ...

  • 谁能看懂这个

    机器学习算法盘点:人工神经网络、深度学习 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法...

  • 朴素贝叶斯(Naive Bayes)

    一. 生成式(generative)学习算法 如果算法直接学习,或者尝试学习从输入空间到类别的映射关系的算法,称为...

网友评论

      本文标题:Paxo算法学习(一)

      本文链接:https://www.haomeiwen.com/subject/rvybvxtx.html