- 浏览: 627696 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (819)
- java开发 (110)
- 数据库 (56)
- javascript (30)
- 生活、哲理 (17)
- jquery (36)
- 杂谈 (15)
- linux (62)
- spring (52)
- kafka (11)
- http协议 (22)
- 架构 (18)
- ZooKeeper (18)
- eclipse (13)
- ngork (2)
- dubbo框架 (6)
- Mybatis (9)
- 缓存 (28)
- maven (20)
- MongoDB (3)
- 设计模式 (3)
- shiro (10)
- taokeeper (1)
- 锁和多线程 (3)
- Tomcat7集群 (12)
- Nginx (34)
- nodejs (1)
- MDC (1)
- Netty (7)
- solr (15)
- JSON (8)
- rabbitmq (32)
- disconf (7)
- PowerDesigne (0)
- Spring Boot (31)
- 日志系统 (6)
- erlang (2)
- Swagger (3)
- 测试工具 (3)
- docker (17)
- ELK (2)
- TCC分布式事务 (2)
- marathon (12)
- phpMyAdmin (12)
- git (3)
- Atomix (1)
- Calico (1)
- Lua (7)
- 泛解析 (2)
- OpenResty (2)
- spring mvc (19)
- 前端 (3)
- spring cloud (15)
- Netflix (1)
- zipkin (3)
- JVM 内存模型 (5)
- websocket (1)
- Eureka (4)
- apollo (2)
- idea (2)
- go (1)
- 业务 (0)
- idea开发工具 (1)
最新评论
-
sichunli_030:
对于频繁调用的话,建议采用连接池机制
配置TOMCAT及httpClient的keepalive以高效利用长连接 -
11想念99不见:
你好,我看不太懂。假如我的项目中会频繁调用rest接口,是要用 ...
配置TOMCAT及httpClient的keepalive以高效利用长连接
背景
Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视,使Lamport在八年后重新发表到TOCS上。即便如此paxos算法还是没有得到重视,2001年Lamport用可读性比较强的叙述性语言给出算法描述。可见Lamport对paxos算法情有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪,其中的chubby锁服务使用paxos作为chubby cell中的一致性算法,paxos的人气从此一路狂飙。
Paxos是什么
Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致,是分布式计算中的重要问题。
Paxos的两个原则
安全原则---保证不能做错的事
1. 只能有一个值被批准,不能出现第二个值把第一个覆盖的情况
2. 每个节点只能学习到已经被批准的值,不能学习没有被批准的值
存活原则---只要有多数服务器存活并且彼此间可以通信最终都要做到的事
1. 最终会批准某个被提议的值
2. 一个值被批准了,其他服务器最终会学习到这个值
Paxos的两个组件
Proposer
提议发起者,处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。
Acceptor
提议批准者,负责处理接收到的提议,他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
Paxos定义
接下来用举例的方式一步一步解释Paxos为了完成一致性,必须要解决的一些问题。这里为了方便解释,假设每一台服务器都是一个Proposer,也是一个Acceptor
一个Acceptor
首先从最简单的方式开始,假设只有一个Acceptor,让它做决定是否批准一个值
如上图,每一个proposer提议一个值给Acceptor来批准,然后Acceptor批准一个值作为最终的值。
但是这种简单的方式,没有办法解决Acceptor crash的问题,如果唯一的Acceptor crash了,就没有办法知道哪个值被选择了,就需要等待它重启,这一条违反了存活原则,这个时候有4台服务器存活,但已经没有办法工作了。
多个Acceptor
为了解决这个问题,就必须要用到一种多数选择的方法。使用一个Acceptor的集合。然后只有其中的多数批准了一个值,这个值才可以确实是被最终被批准的。为了达到目的也需要一些技巧。
批准第一个达到的值
首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值
但是有一个问题,比如上图,因为没有值被多数批准,无法批准一个最终的值出来。这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值
批准每个提议的值
接下来规定Acceptor批准每个提议的值,但是这也会带来一个问题,可能会批准出多个值
如图,S1发出提议,S1,S2,S3批准 red为最终批准的值。S5随后发出提议,s3,S4,S5批准,blue又为最终批准的值。此时S1,S2最终批准red,S3,S4,S5最终批准blue,这就违背了我们的一致性原则,最终只有一个值被选择。
二段提交原则
要解决这个问题,就要S5在发送自己的提议之前,优先检查有没有已经被批准的值,如果有应该提议已经被批准的值而放弃自己的值,也就是放弃自己的blue改为提议red,这样最终只有一个值被批准就是red。这个就是经典的二段提交原则。
不幸的是,二段提交还是存在另一个问题。
如图,S1在发送提议之前,检查没有值被批准,因此提议red。但同时在所有Acceptor批准之前,S5也要进行提议,这个时候也检查出没有值被批准,所以它也把自己的blue作为提议发送给acceptor。接下来S5的提议优先到达S3,S4,S5,这些Acceptor先批准了blue,达到多数所以blue最终被批准了。但是随后S1,S2,S3接收到了red进行批准。所以又出现了批准出多个值的问题。
提议排序
这个问题要解决,就需要一旦Acceptor批准了某个值,其他有冲突的值都应该被拒绝。也就是说S3随后到达的red应该被拒绝,为了做到这一点。需要对Proposer进行排序,将排序在前的赋予高优先级,Acceptor批准优先级高的值,拒绝排序在后的值。
为了将提议进行排序,可以为每个提议赋予一个唯一的ID,规定这个ID越大,优先级越高
在提议者发送提议之前,就需要生成一个唯一的ID,而且需要比之前使用的或者生成的都要大
提议ID生成算法
在Google的Chubby论文中给出了这样一种方法:假设有n个proposer,每个编号为ir(0<=ir<n),proposor编号的任何值s都应该大于它已知的最大值,并且满足:s %n = ir => s = m*n + ir
proposer已知的最大值来自两部分:proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值
以3个proposer P1、P2、P3为例,开始m=0,编号分别为0,1,2
1. P1提交的时候发现了P2已经提交,P2编号为1 > P1的0,因此P1重新计算编号:new P1 = 1*3+0 = 4
2. P3以编号2提交,发现小于P1的4,因此P3重新编号:new P3 = 1*3+2 = 5
Paxos算法
到此阶段,要保证Paxos的两个原则已经都满足了,Paxos也就顺利的实现了。
二段提交
prepare 阶段:
1. Proposer 选择一个提案编号 n 并将 prepare 请求发送给 Acceptors 中的一个多数派;
2. Acceptor 收到 prepare 消息后,如果提案的编号大于它已经回复的所有 prepare 消息,则 Acceptor 将自己上次接受的提案回复给 Proposer,并承诺不再回复小于 n 的提案;
acceptor阶段:
1. 当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后,就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求,包括编号 n 和根据 prepare阶段 决定的 value(如果根据 prepare 没有已经接受的 value,那么它可以自由决定 value)。
2. 在不违背自己向其他 Proposer 的承诺的前提下,Acceptor 收到 accept 请求后即接受这个请求。
prepare阶段有两个目的,第一检查是否有被批准的值,如果有,就改用批准的值。第二如果之前的提议还没有被批准,则阻塞掉他们以便不让他们和我们发生竞争,当然最终由提议ID的大小决定。整个过程如下图
参考:http://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D
http://oceanbase.org.cn/?p=90#rd&sukey=3997c0719f1515203122ffff0e0da7aed97903f996a2b246f96866d58b6be21d54264fe972af2fe71ac7d73b869b108d
发表评论
-
Zookeeper的四字命令
2017-05-18 20:39 549http://www.cnblogs.com/wuxl360/ ... -
Zookeeper开源客户端框架Curator简介
2016-10-25 08:43 496ZooKeeper原生的API支持通过注册Watcher来进行 ... -
Curator Framework的基本使用方法
2016-10-21 15:17 1042Curator Framework提供了简化使用zookeep ... -
ZooKeeper学习总结
2016-09-30 15:18 401参考:http://www.tuicool.com/artic ... -
推荐一个zookeeper信息查看工具
2016-08-31 16:01 1690zookeeper信息查看工具 下载地址:https://i ... -
Paxos算法细节详解(一)--通过现实世界描述算法
2016-08-24 16:29 536http://www.cnblogs.com/endsock/ ... -
ZooKeeper学习总结 第一篇:ZooKeeper快速入门
2016-08-22 16:23 422http://www.cnblogs.com/leocook/ ... -
zookeeper原理(转)
2016-08-22 14:02 382ZooKeeper是一个分布式的 ... -
zookeeper客户端curator使用手记
2016-08-09 15:10 458http://www.tuicool.com/articles ... -
Zookeeper的一致性协议:Zab
2016-08-01 09:21 647Zookeeper使用了一种称为Zab(Zookeeper A ... -
ZooKeeper源码阅读(一):ZAB协议
2016-07-29 14:29 653ZooKeeper内部有一个in-memo ... -
Zookeeper基本原理与应用场景
2016-07-28 18:51 306http://blog.csdn.net/yunpiao123 ... -
Paxos算法简述
2016-07-21 14:10 365Paxos算法是分布式中一个著名的一致性算法。它的假设前提是, ... -
Zookeeper-Zookeeper leader选举
2016-07-20 09:05 525在上一篇文章中我们大 ... -
部署与管理ZooKeeper(转)
2016-07-19 09:17 367http://www.cnblogs.com/ggjuchen ... -
ZooKeeper原理及使用
2016-08-02 08:27 403ZooKeeper是Hadoop Ecosystem中非常重要 ... -
ZooKeeper Java API
2016-05-22 10:05 879ZooKeeper提供了Java和C的binding. 本文关 ...
相关推荐
Paxos算法是一种分布式一致性算法,由Leslie Lamport提出,主要用于解决...虽然Paxos算法在理论上可能较为复杂,但其基本原理可以通过日常生活中的实例进行简化理解,帮助初学者更好地掌握这一关键的分布式系统概念。
通过分析和理解这段代码,我们可以更深入地了解CBAA的细节,例如如何处理并行通信、如何调整出价策略以适应不同的任务分配环境,以及如何判断算法是否收敛。 总的来说,CBAA是一种融合了拍卖理论和分布式一致性技术...
【标题】:“Paxos:CS...通过阅读和分析这些代码,可以深入理解Paxos算法的实现细节,以及如何在实际项目中应用分布式一致性解决方案。同时,这也是提升分布式系统设计能力、理解和应用高级并发编程技巧的良好实践。
15. **并行和分布式算法**:在多处理器和网络环境中的算法设计,如MapReduce模型和Paxos协议,它们在大数据处理和云计算中扮演重要角色。 《十五个经典算法研究与总结》的目录和索引为读者提供了方便的导航,帮助...
《算法在程序设计中的应用——以“Algorithm-snek”为例》 算法,是计算机科学的灵魂,是编程的核心。它如同一把精巧的钥匙,能够解锁...因此,对于任何想要深入学习编程的人来说,理解和掌握算法是不可或缺的一步。
总结,Zookeeper的理论原理涉及多个层面,包括ZAB协议的崩溃恢复和原子广播,客户端的交互流程,FastLeaderElection选举机制,以及Paxos算法的影响。深入理解这些原理有助于我们在实际应用中更好地利用Zookeeper,...
因此,出现了Raft协议,它简化了Paxos的算法流程,更易于理解。Raft将Paxos的复杂问题分解为领导者选举、日志复制、安全性三个相对独立的子问题,并为每个子问题提供了清晰的解决方案。Multi-Paxos是Paxos的一个扩展...
- **Zookeeper使用Paxos算法的简化版**:Zookeeper采用FastPaxos策略,简化了Paxos算法,提高了选举效率。 - **状态机模型**:每个客户端请求都被视为一个状态机的转换,确保了操作的顺序性和一致性。 6. **故障...
Zookeeper采用Paxos算法的简化版本ZAB协议进行领导者选举,当一个Zookeeper集群中的一部分节点失效或失去联系时,ZAB协议可以确保集群能够快速恢复并重新选举出新的领导者。 六、Zookeeper的监控与调优 通过JMX接口...
5. **一致性模型**:如Paxos或Raft等分布式一致性算法,保证在网络中分布式状态的一致性,适用于大型多服务器架构的游戏。 实现这些同步方法的装置可能包括硬件设备和软件组件: 1. **高性能服务器**:处理大量...
Zookeeper采用Paxos算法实现一致性,通过ZNode(类似文件系统的节点)的数据结构来存储数据,这种设计使得Zookeeper能够支持实时数据更新和读取。每个ZNode都可以包含数据和子ZNode,具有版本号,便于管理和跟踪变化...
3. **一致性算法**:如Lamport时钟、Vector Clocks或Paxos等,用于解决网络延迟造成的事件顺序冲突。 4. **数据压缩与优化**:为了减少网络传输的开销,通常会对游戏状态更新进行压缩,例如只发送变化的部分,或者...
Zookeeper采用了Paxos算法的变种ZAB(Zookeeper Atomic Broadcast)来保证数据的一致性。ZAB协议主要包含两个阶段:同步(Synchronization)和广播(Broadcast)。在同步阶段,Zookeeper确保所有服务器的状态一致,...
5. **选举算法**:Zookeeper使用Paxos或Fast-Paxos算法实现领导者选举,确保在集群中的某个节点故障后,能快速选举出新的领导者。 6. **一致性**:Zookeeper通过ZAB(Zookeeper Atomic Broadcast)协议保证数据的...
ZooKeeper采用Paxos算法实现选举,当一个Zookeeper服务器认为自己是领导者时,它会向其他服务器发送提案,获得大多数服务器的同意后,该服务器成为领导者。 5. **Zookeeper的Watcher机制** Watcher是Zookeeper中...
2. **选举算法**:Zookeeper使用Paxos或FastPaxos算法进行领导者选举。 3. **数据同步**:集群中的节点会进行数据同步,确保各节点的数据一致性。 4. **容错性**:集群中只要有半数以上的节点正常工作,Zookeeper...
Zookeeper采用Paxos算法实现分布式一致性,由一个服务器作为Leader,多个服务器作为Follower组成集群。当客户端请求时,会先发送到Leader,由Leader负责处理并同步到其他Follower,从而保证数据一致性。 四、...
以上只是分布式系统中的一部分关键知识点,实际面试可能会涵盖更多细节,例如分布式一致性算法(如Paxos、Raft)、服务注册与发现、状态管理和监控等。熟悉并理解这些概念和技术,对于Java开发者在面试中表现出色和...
再者,Zookeeper采用Paxos算法的变种来实现一致性。在分布式环境中,确保数据的一致性是非常关键的,Zookeeper通过Zab协议(ZooKeeper Atomic Broadcast)来保证数据的强一致性,即使在部分节点失效的情况下也能保持...