什么是Paxos算法?
Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态。但是如何保证在每个节点上执行相同的命令序列呢?这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos算法便是这样一种一致性算法,它由大牛Lamport于1990年提出,在Lamport的论文中,他虚拟了一个叫“Paxos”的城邦并以讲故事的方式阐述算法,因此叫做Paxos算法。
1.应用场景
(1)分布式中的一致性
Paxos算法主要是解决一致性问题,关于“一致性”,在不同的场景有不同的解释:
NoSQL领域:一致性更强调“能读到新写入的”,就是读写一致性
数据库领域:一致性强调“所有的数据状态一致”,经过一个事务后,如果事务成功,所有的表数据都按照事务中的SQL进行了操作,该修改的修改,该增加的增加,该删除的删除,不能该修改的修改了,该删除的没删掉;如果事务失败,所有的数据还是在初始状态;
状态机:在状态机中的一致性更强调在每个初始状态一致的状态机上执行一串命令后状态都必须相互一致,也就是顺序一致性。Paxos算法中的一致性指的就是这种情况,接下来我们会对这种场景进一步讨论。
(2)MQ
假如所有系统的Log信息都写入一个MQ Server,然后通过MQ把每条Log指令发异步送到多个Log Server写入文件(写入多个Log Server的原因是对Log文件做备份以防数据丢失),则所有Log Server上的数据肯定是一致的(Log内容及顺序完全相同),因为MQ本身就有排序功能,只要进了Q数据也就有了序,相当于编了全局唯一的号,无论把这些数据写入多少个文件,只要按编号,各文件的内容必定是一致的,但一个MQ Server显然是一个单点,如果宕机,会影响整个系统的可用性。
(3)多MQ
要解决MQ单点问题,首选方案是采用多个MQ Server,即使用一个MQ Cluster,客户端可以访问任意MQ Server,不同的客户端可能访问不同MQ Server,不同MQ Server上的数据内容、顺序可能不一致,如果不解决这个问题,每个MQ Server写入Log Server的内容就不一致,这显然不是我们期望的结果。
(4)NoSQL中的数据更新
一般的NoSQL都会通过数据复制的形式保证其可用性,但客户端对多数据进行操作时,可能会有很多对同一数据的操作发送的某一台或几台Server,有可能执行:Insert、Update A、Update B....Update N,就一次Insert连续多次Update,最终复制Server上也必须执行这一的更新操作,如果因为线程池、网络、Server资源等原因导致各复制Server接收到的更新顺序不一致,这样的复制数据就失去了意义,如果在金融领域甚至会造成严重的后果。
上面这些不一致问题性正是Paxos算法要解决的,当然这些问题也不是只有Paxos能解决,在没有Paxos之前这些问题也得到了解决,比如通过使用双Master模式的MQ解决MQ单点问题;通过使用Master Server解决NoSQL的复制问题,但这些解决方法都存在一些缺陷,要么难水平扩展,要么影响可用性。当然除了Paxos算法还有其他一些算法也试图解决这类问题,比如:Viewstamped Replication算法。
2.Paxos如何解决这类问题
Paxos对这类问题的解决就是试图对各Server上的状态进行全局编号,如果能编号成功,那么所有操作都按照编号顺序执行,一致性就不言而喻。当Cluster中的Server都接收了一些数据,如何进行编号?就是表决,让所有的Server进行表决,看哪个Server上的哪个数据应该排第一,哪个排第二...,只要多数Server同意某个数据该排第几,那就排第几。
很显然,为了给每个数据唯一编号,每次表决只能产生一个数据,否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步,我们称表决的数全可以得出最终结果。
相关推荐
Raft是分布式环境下的一致性算法,它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常类似于paxos协议(参见我...
《Paxos到Zookeeper:分布式一致性原理与实践》从分布式一致性的理论出发,向读者简要介绍几种典型的分布式一致性协议,以及解决分布式一致性问题的思路,其中重点讲解了Paxos和ZAB协议。同时,本书深入介绍了分布式...
Paxos算法是分布式技术大师Lamport提出的,主要目的是通过这个算法,让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说,就是在一个选举过程中,让不同的选民最终做出一致的决定。 Lamport为了...
fast paxos算法与zookeeper leader选举源代码分析.doc
FourInOne是高可用的,没有单点问题,可以有任意多个复本,它的复制不是定时而是基于内容变更复制,有更高的性能,FourInOne实现了领导者选举算法(但不是Paxos),在领导者服务器宕机情况下,会自动不延时的将请求...
因为分布式系统本身的复杂特性,以及对于容错性的要求,这些技术通常是重量级的,比如 Paxos 算法,欺负选举算法,ZooKeeper 等,侧重于消息的通信而不是共享内存,通常也是出了名的复杂和难以理解,当在具体的实现...
本文主要介绍了leader...业界最著名的一致性算法就是大名鼎鼎的Paxos,但Paxos是出了名的难懂,而Raft正是为了探索一种更易于理解的一致性算法而产生的,它将一致性拆分为leader选举、日志复制、安全性三个关键元素R
Fourinone是高可用的,没有单点问题,可以有任意多个复本,它的复制不是定时而是基于内容变更复制,有更高的性能,Fourinone实现了领导者选举算法(但不是Paxos),在领导者服务器宕机情况下,会自动不延时的将请求...
WPaxosWPaxos是Paxos一致性算法的生产级高性能Java实现,参考了微信团队C++语言开发的类库,支持多分组,可用于解决高并发、高可靠分布式系统中多副本数据一致性问题以及分布式共识问题。针对一些网络分区、机器宕机...
该存储库包含基于基于状态的Paxos算法之上的领导者选举抽象,组成员资格抽象和共识抽象的实现。 我们在同名论文Nicolo'Rivetti和Angelo Corsaro,基于状态的Paxos,2013年第13届ACM / IFIP / USENIX国际中间件会议...
1.说一下你了解的分布式算法有哪些? 2.说一下你对HDFS源码的理解,读源码有哪些收获? 3.MapReduce的任务如何和HDFS结合起来? 4.介绍一下2PC的协议? 5.2PC在什么时候会发生阻塞? 6.HDFS写入数据时发生故障...
Raft 是一种共识算法,用于在分布式环境中选举领导者并管理复制日志。 它产生的结果等价于(multi-)Paxos,和Paxos一样高效,但它的结构与Paxos不同; 这使得 Raft 比现有的和众所周知的 Paxos 更易于理解,也为构建...
算法基础选举和日志复制安全性节点变更这是第一篇:《解读Raft(一算法基础)》分布式系统除了提升整个体统的性能外还有一个重要特征就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台的机器故障不会使...
Paxos算法 ZAB协议 Leader选举 微内核+插件 Dubbo内核四大机制 运行时内存 不同垃圾收集器工作原理详解 GC日志分析 Spring全家桶源码分析 Tomcat架构原理 Web请求处理原理 数据访问层框架原理 架构与设计思维模式 ...
Weave是用Java实现的分布式密钥库,并使用基于RAFT的领导者选举的自定义实现来达成共识。 它被设计为快速,可访问且容错的。 Weave旨在促进原始RAFT论文的目标,包括易懂性。 这就是为什么Weave有充分的文档资料并...
raft 是一种分布式的共识算法,其目的是要实现多个节点集群的容错性,一致性从而能够构建大规模的软件系统。 在raft之前,比较有名的是Paxos。但是paxos难于理解。 raft的诞生是为了让共识算法更容易理解,在工程上更...
Zookeeper集群搭建指的是ZooKeeper分布式模式安装。通常由2n+1台servers组成。这是因为为了保证Leader选举(基于Paxos算法的实现)能够得到多数的支持,所以ZooKeeper集群的数量一般为奇数。
6.4.4. Paxos算法(扩展) 32 6.4.5. 选举机制(面试重点) 34 6.4.6. 写数据流程 35 6.5. 企业面试真题 37 6.5.1. 请简述ZooKeeper的选举机制 37 6.5.2. ZooKeeper的监听原理是什么 37 6.5.3. ZooKeeper的部署方式...