传奇官方网站,唐山网站建设开发设计公司,做服装外贸网站,公众号登录不上文章目录 共识算法Paxos 算法三种角色一致性提交算法prepare 阶段accept 阶段commit 阶段 CAP 定理BASE 理论Zookeeper 算法实现三类角色三个数据三种模式四种状态消息广播算法Leader选举算法 共识算法
Paxos 算法
Paxos 算法是莱斯利兰伯特(Leslie Lamport)1990 年提出的一种… 文章目录 共识算法Paxos 算法三种角色一致性提交算法prepare 阶段accept 阶段commit 阶段 CAP 定理BASE 理论Zookeeper 算法实现三类角色三个数据三种模式四种状态消息广播算法Leader选举算法 共识算法
Paxos 算法
Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高 容错性的一致性算法。Google Chubby 的作者 Mike Burrows 说过世上只有一种一致性算法 那就是 Paxos所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一种公认的晦 涩难懂的算法并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有 Google Chubby、 ZAB、微信的 PhxPaxos 等。
三种角色
在 Paxos 算法中有三种角色分别具有三种不同的行为。但很多时候一个进程可能同 时充当着多种角色。 Proposal提案
Proposer提案者Acceptor表决者Learner学习者同步者
一致性
Paxos 算法的一致性主要体现在以下几点
每个提案者在提出提案时都会首先获取到一个递增的、全局唯一的提案编号 N然后将该编号赋予其要提出的提案。 关于 N 的生成有两种方式全局性生成器、提案者自身维护 N。每个表决者在 accept 某个提案后会将该提案的编号 N 记录在本地这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。在众多提案中最终只能有一个提案被选定。一旦一个提案被选定则其它学习者会主动同步(Learn)该提案到本地。没有提案被提出则不会有提案被选定
提交算法
Paxos 对于提案的提交算法有两种方案2PC 与 3PC。
2PCTwo Phase Commit即 prepare - accept3PCThree Phase Commit即 prepare - accept - commit prepare 阶段
提案者(Proposer)准备提交一个编号为 N 的提议于是其首先向所有表决者(Acceptor)发 送 prepare(N)请求用于试探集群是否支持该编号的提议。每个表决者(Acceptor)中都保存着自己曾经 accept 过的提议中的最大编号 maxN。当一个 表决者接收到其它主机发送来的 prepare(N)请求时其会比较 N 与 maxN 的值。有以下 几种情况 若 N 小于 maxN则说明该提议已过时当前表决者采取不回应或回应 Error 的方 式来拒绝该 prepare 请求若 N 大于 maxN则说明该提议是可以接受的当前表决者会首先将该 N 记录下来 并将其曾经已经 accept 的编号最大的提案 Proposal(myid,maxN,value)反馈给提案者 以向提案者展示自己支持的提案意愿。其中第一个参数 myid 表示该提案的提案者 标识 id第二个参数表示其曾接受的提案的最大编号 maxN第三个参数表示该提 案的真正内容 value。当然若当前表决者还未曾 accept 过任何提议则会将 Proposal(null,null,null)反馈给提案者。在 prepare 阶段 N 不可能等于 maxN。这是由 N 的生成机制决定的。要获得 N 的值 其必定会在原来数值的基础上采用同步锁方式增一。
accept 阶段
当提案者(Proposer)发出 prepare(N)后若收到了超过半数的表决者(Accepter)的反馈 那么该提案者就会将其真正的提案 Proposal(myid,N,value)发送给所有的表决者。当表决者(Acceptor)接收到提案者发送的 Proposal(myid,N,value)提案后会再次拿出自己曾经 accept 过的提议中的最大编号 maxN或曾经记录下的 prepare 的最大编号让 N 与它们进行比较若 N 大于等于这两个编号则当前表决者 accept 该提案并反馈给 提案者。若 N 小于这两个编号则表决者采取不回应或回应 Error 的方式来拒绝该提议。若提案者没有接收到超过半数的表决者的 accept 反馈则有两种可能的结果产生。一 是放弃该提案不再提出二是重新进入 prepare 阶段递增提案号重新提出 prepare 请求。
commit 阶段
若提案者接收到的反馈数量超过了半数则其会向外广播两类信息
向曾 accept 其提案的表决者发送“可执行数据同步信号”即让它们执行其曾接收 到的提案向未曾向其发送 accept 反馈的表决者发送“提案 可执行数据同步信号”即让 它们接受到该提案后马上执行
CAP 定理
CAP 定理又称 CAP 原则指的是在一个分布式系统中Consistency一致性、Availability 可用性、Partition tolerance分区容错性三者不可兼得
一致性C分布式系统中多个主机之间是否能够保持数据一致的特性。即当系统数据发生更新操作后各个主机中的数据仍然处于一致的状态可用性A系统提供的服务是否一直处于可用的状态即对于用户的每一个请求系 统是否总是可以在有限的时间内对用户做出响应分区容错性P分布式系统在遇到任何网络分区故障时仍能够保证对外提供满足一 致性和可用性的服务。 分区是网络分区
对于分布式系统网络环境相对是不可控的出现网络分区是不可避免的因此系统必 须具备分区容错性。但其并不能同时保证一致性与可用性。CAP 原则对于一个分布式系统来 说只可能满足两项即要么 CP要么 AP
BASE 理论
BASE 是 Basically Available基本可用、Soft state软状态和 Eventually consistent最 终一致性三个短语的简写。
BASE 理论的核心思想是即使无法做到实时一致性但每个系统都可以根据自身的业 务特点采用适当的方式来使系统达到最终一致性
基本可用BA 基本可用是指分布式系统在出现不可预知故障的时候允许损失部分可用性软状态S 软状态是指允许系统数据存在的中间状态并认为该中间状态的存在不会影响系统的 整体可用性即允许系统主机间进行数据同步的过程存在一定延时。软状态其实就是一种 灰度状态过渡状态最终一致性E 最终一致性强调的是系统中所有的数据副本在经过一段时间的同步后最终能够达到 一个一致的状态。因此最终一致性的本质是需要系统保证最终数据能够达到一致而不需 要实时保证系统数据的一致性
从达到一致性的时间角度来划分可以分为
实时一致性单机情况下可以实现实时一致性最终一致性经过一段时间后可以达到一致性
单从客户端访问到的内容角度来划分可以分为
强一致性严格一致性要求客户端访问到的数据都是一致弱一致性允许客户端访问不到部分或全部更新过的数据
Zookeeper 算法实现
ZAB 协议是 Paxos 算法的一种工业实现算法。但两者的设计目标不太一样。ZAB 协议主 要用于构建一个高可用的分布式数据主从系统即 Follower 是 Leader 的从机Leader 挂了 马上就可以选举出一个新的 Leader但平时它们都对外提供服务。而 Fast Paxos 算法则是用 于构建一个分布式一致性状态机系统确保系统中各个节点的状态都是一致的。
三类角色
为了避免 Zookeeper 的单点问题zk 也是以集群的形式出现的。zk 集群中的角色主要有 以下三类
Leaderzk 集群中事务请求的唯一处理者其也可以处理读请求。Follower处理读请求将事务请求转发给 Leader对 Leader 发起的提案进行表决同 步 Leader 的事务处理结果在 Leader 的选举过程中具有选举权与被选举权Observer不具有表决权且在 Leader 选举过程中没有选举权与被选举权的 Follower。 Learner学习者同步者。Learner Follower Observer QuorumPeer Participant Leader Followe
三个数据
在 ZAB 中有三个很重要的数据
zxid64 位长度的 Long 类型其高 32 位为 epoch低 32 位为 xid。epoch每一个新的 Leader 都会有一个新的 epochxid其为一个流水号
三种模式
ZAB 协议中对 zkServer 的状态描述有三种模式。这三种模式并没有十分明显的界线它 们相互交织在一起。
恢复模式其包含两个重要阶段Leader 的选举与初始化同步广播模式其可以分为两类初始化广播与更新广播同步模式其可以分为两类初始化同步与更新同步
四种状态
zk 集群中的每一台主机在不同的阶段会处于不同的状态。每一台主机具有四种状态。
LOOKING选举状态FOLLOWINGFollower 的正常工作状态OBSERVINGObserver 的正常工作状态LEADINGLeader 的正常工作状态
消息广播算法 当集群中的 Learner 完成了初始化状态同步那么整个 zk 集群就进入到了正常工作模式 了。 如果集群中的 Learner 节点收到客户端的事务请求那么这些 Learner 会将请求转发给 Leader 服务器。然后再执行如下的具体过程
Leader 接收到事务请求后为事务赋予一个全局唯一的 64 位自增 id即 zxid通过 zxid 的大小比较即可实现事务的有序性管理然后将事务封装为一个 Proposal。Leader 根据 Follower 列表获取到所有 Follower然后再将 Proposal 通过这些 Follower 的 队列将提案发送给各个 Follower。当 Follower 接收到提案后会先将提案的 zxid 与本地记录的事务日志中的最大的 zxid 进行比较。若当前提案的 zxid 大于最大 zxid则将当前提案记录到本地事务日志中并 向 Leader 返回一个 ACK。提问学员当 Leader 接收到过半的 ACKs 后Leader 就会向所有 Follower 的队列发送 COMMIT 消息向所有 Observer 的队列发送 Proposal。当 Follower 收到 COMMIT 消息后就会将事务正式更新到本地。当 Observer 收到 Proposal 后会直接将事务更新到本地。无论是 Follower 还是 Observer在同步完成后都需要向 Leader 发送成功 ACK
Leader选举算法
在集群启动过程中的 Leader 选举过程算法与 Leader 断连后的 Leader 选举过程稍微 有一些区别基本相同 若进行 Leader 选举则至少需要两台主机这里以三台主机组成的集群为例 在集群初始化阶段当第一台服务器 Server1 启动时其会给自己投票然后发布自己 的投票结果。投票包含所推举的服务器的 myid 和 ZXID使用(myid, ZXID)来表示此时 Server1 的投票为(1, 0)。由于其它机器还没有启动所以它收不到反馈信息Server1 的状态一直属于 Looking即属于非服务状态。
当第二台服务器 Server2 启动时此时两台机器可以相互通信每台机器都试图找到 Leader选举过程如下
每个 Server 发出一个投票。此时 Server1 的投票为(1, 0)Server2 的投票为(2, 0)然后各自将这个投票发给集群中其他机器。接受来自各个服务器的投票。集群的每个服务器收到投票后首先判断该投票的有效性如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。处理投票。针对每一个投票服务器都需要将别人的投票和自己的投票进行 PKPK 规则如下 优先检查 ZXID。ZXID 比较大的服务器优先作为 Leader。如果 ZXID 相同那么就比较 myid。myid 较大的服务器作为 Leader 服务器。 对于 Server1 而言它的投票是(1, 0)接收 Server2 的投票为(2, 0)。其首先会比较两者 的 ZXID均为 0再比较 myid此时 Server2 的 myid 最大于是 Server1 更新自己的投票为 (2, 0)然后重新投票。对于 Server2 而言其无须更新自己的投票只是再次向集群中所有 主机发出上一次投票信息即可。统计投票。每次投票后服务器都会统计投票信息判断是否已经有过半机器接受到相同的投票信息。对于 Server1、Server2 而言都统计出集群中已经有两台主机接受了(2, 0) 的投票信息此时便认为已经选出了新的 Leader即 Server2。改变服务器状态。一旦确定了 Leader每个服务器就会更新自己的状态如果是 Follower那么就变更为 FOLLOWING如果是 Leader就变更为 LEADING。添加主机。在新的 Leader 选举出来后 Server3 启动其想发出新一轮的选举。但由于 当前集群中各个主机的状态并不是 LOOKING而是各司其职的正常服务所以其只能是以 Follower 的身份加入到集群中。
