网站建设总结体会,wordpress修改首页,新产品线上推广方案,近期十大新闻热点事件数据库浅谈之共识算法
HELLO#xff0c;各位博友好#xff0c;我是阿呆 #x1f648;#x1f648;#x1f648;
这里是数据库浅谈系列#xff0c;收录在专栏 DATABASE 中 #x1f61c;#x1f61c;#x1f61c;
本系列阿呆将记录一些数据库领域相关的知识 #x1…数据库浅谈之共识算法
HELLO各位博友好我是阿呆
这里是数据库浅谈系列收录在专栏 DATABASE 中
本系列阿呆将记录一些数据库领域相关的知识
OK兄弟们废话不多直接开冲 一 概述
CAP 理论
在一个分布式系统中 Consistency一致性、 Availability可用性、Partition tolerance分区容错性三者不可得兼 一致性C所有数据备份同一时刻是否同样所有节点访问同一份最新数据副本 可用性A保证每个请求不管成功或者失败都有响应 分区容忍性P系统中任意信息的丢失不会影响系统继续运作 共识算法背景
问题 ① 有一份随时变动的数据确保它正确存储在网络中几台不同机器上怎么处理
在分布式系统中必须考虑动态数据如何在不可靠网络通讯条件下依然能在各节点之间正确复制
数据同步 状态转移(State Transfer) 性能损耗
每当数据有变化就把变化情况在各个节点之间的复制看成是一种事务性的操作只有系统的每一台机器都反馈成功完成磁盘写入后数据变化才能宣布成功。以同步为代表的数据复制方法叫做状态转移State Transfer
这类方法属于比较直观但通常要牺牲可用性 问题 ② 有一份随时变动的数据确保它正确存储在几台不同机器上且尽可能保证数据随时可用怎么做
共识算法 这个让系统各节点不受局部网络分区、机器崩溃、执行性能或者其它因素影响能最终表现出整体一致的过程就是各个节点的协商共识Consensus 两个目标 : ① 让分布式系统内部暂时容忍存在不同状态但最终保证大多数节点状态一致 ② 分布式系统在外部看来始终表现整体一致
共识Consensus与一致性Consistency的区别 一致性指的是数据不同副本之间的差异而共识是指达成一致性的方法与过程 状态机 操作转移
系统 高可用 和 高可靠 之间的矛盾是由于增加机器数量反而降低了可用性导致的
为缓解这个矛盾在分布式系统里主流的数据复制方法是以操作转移为基础的比如 ( x x 1 )
使用确定操作使状态间产生确定转移结果的计算模型被称为状态机
状态机的特性任何初始状态一样的状态机如果执行命令序列一样那么最终达到状态也一样。多台机器的最终状态一致只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以
广播指令与指令执行期间允许系统内部状态存在不一致的情况也就是不要求所有节点的每一条指令都是同时开始、同步完成的只要求在此期间的内部状态不能被外部观察到且当操作指令序列执行完成的时候所有节点的最终的状态是一致的这种模型就是状态机复制 Quorum 机制
在分布式环境下考虑到网络分区现象不可能消除且不必追求所有节点任何情况下数据状态一致所以采用 少数服从多数 原则。即系统中超过半数节点完成状态转换就认为数据变化已被正确地存储在了系统中。
容忍少数通常是不超过半数节点失联使增加机器数量可提升系统整体可用性
分布式共识基础
分布式共识是什么
在多个节点均可独自操作或记录的情况下使得所有节点针对某个状态达成一致的过程本质是 求同存异 一致性和共识的区别是什么
一致性指的是数据不同副本之间的差异而共识是指达成一致性的方法与过程 分布式共识的两个关键点是什么
1、获得记账权 2、所有节点达成一致 二 核心
Paxos 算法
要求
① 为了有明确的多数决策节点数量应被设为奇数
② 系统初始化时网络中每个节点都知道整个网络所有决策节点的数量、地址等信息 主要概念
提案节点Proposer提出对某个值设置节点设置值这个行为就是提案 (Proposal) 值一旦设置成功不会丢失也不可改变
决策节点Acceptor应答提案节点决定该提案是否可以被投票、是否可以被接受
提案一旦得到半数决策节点接受即被批准(Accept)。该值将不能更改也不会丢失且最终所有节点都会接受它
记录节点Learner不参与提案也不参与决策单纯从提案、决策节点中学习已达成共识的提案。少数节点刚从网络分区中恢复时将会进入这种状态 分布式并发操作下的共享数据
假设有一个变量 i 当前在系统中存储的数值为 2同时有外部请求 A、B 分别对系统发送操作指令把 i 的值加 1 和 把 i 的值乘 3。没有并发控制将可能得到 (21)×39 和 2×317 这两种结果。因此对同一个变量的并发修改必须先加锁后操作不能让 A、B 的请求被交替处理
但是在分布式系统中通讯故障可能在任何时刻出现。如果一个节点在取得锁后、在释放锁前发生崩溃失联就会导致整个操作被无限期等待所阻塞 解决方案
主要包括 准备Prepare和 批准Accept两个阶段
准备Prepare阶段相当于抢锁过程。如果发起提案那必须先向所有决策节点广播一个申请 ( 称为 Prepare请求 ) 。提案节点的 Prepare 请求中会携带一个全局唯一的数字 N 作为提案 ID决策节点收到后会给出两个承诺和一个应答
两个承诺 ① 不会再接受提案 ID 小于或等于 N 的 Prepare 请求 ② 不会再接受提案 ID 小于 N 的 Accept 请求
一个应答 不违背以前承诺前提下回复已经批准过提案中 ID 最大的那个提案所设定的值和提案 ID。如果该值没有被任何提案设定过则返回空值。如果违反此前承诺即收到的提案 ID 不是最大的可直接不理会请求 批准Accept 当提案节点收到了多数派决策节点应答后开始第二阶段 批准 过程
此时有两种可能
① 如果提案节点发现所有响应的决策节点此前都没有批准过这个值即为空就说明它是第一个设置值的节点那就可以随意决定要设置的值并将自己选定的值与提案 ID。构成一个二元组ID,VALUE再次广播给全部决策节点
② 如果提案节点发现响应的决策节点中已经有至少一个节点的应答中包含有值了那就必须从应答中找到提案ID 最大的那个值并接受构成一个二元组ID,maxAcceptValue然后再次广播给全部的决策节点 每个决策节点收到 Accept 请求时都会在不违背以前承诺前提下接受并持久化当前提案 ID 和携带数值。但如果收到的提案 ID 并不是收到过的最大的那对 Accept 请求将不理会
记录节点
当提案节点收到了多数派决策节点的应答后协商结束共识决议形成将决议发送给所有记录节点进行学习
Basic Paxos 协商过程-时序图 典型场景
背景假设一个分布式系统中有五个节点S1、S2、S3、S4、S5此时有两个并发的请求希望将同一个值分别设置为 X 和 YP 表示准备阶段A 表示批准阶段
场景一 在协商过程中谁先获得了多数节点支持先在Promise中返回决议值谁就是本次决议的最终值在协商结束之前无论有多少次新的提案都不在进行处理
S1 选定的提案 ID 是 3.1全局唯一 ID 3 加上节点标号 1先取得了多数派决策节点的 Promise 和 Accept 应答此时 S5 的提案 ID 是 4.5发起 Prepare 请求收到的多数派应答中至少会包含一个此前应答过 S1 的决策接节点假设是 S3
那么 S3 提供的 Premise 中必定将 S1 已经决议好的值 XS5 就必须无条件的使用 X 而不是 Y 作为自己的提案值。即使S5的提案ID更大但是已经有了Accept 场景二X 被选定不一定是要多数派共同批准只取决于 S5 提案时 Promise 应答中是否已经包含了批准过 X 决策节点如下图S5 发起提案 Prepars 请求时X 并未获取多数派批准但由于 S3 已经批准的原因最终共识的结果依然是 X 场景三S5 在提案的时候 Promise 应答中并没有包含批准过 X 的决策节点。比如应答 S5 提案时节点 S1已经批准了 X节点 S2、S3 并未批准但是返回了 Promise 应答那此时 S5 以更大的提案 ID 获得了 S3、S4、S5 的Promise
这三个节点均为批准过任何值那么 S3 将不会再接受来自 S1 的 Accept 请求因为它的提案 ID 已经不是最大的。所以这三个节点将批准Y的取值整个系统将会对取值为Y达成一致 场景四如果两个提案节点交替使用最大的提案ID使得准备阶段成功但是批准阶段失败的话那这个过程理论上可以无限延续下去形成活锁Live Lock实际算法中会引入随机超时时间来避免活锁产生 Multi Paxos (Raft)
活锁问题 两个提案节点互不相让提出自己的提案抢占同一个值修改权限导致整个系统再持续的反复横跳从外部来看就像是被锁住了
活锁问题和许多 BasicPaxos 异常场景中 (网络不可靠、请求并发) 所遇到的麻烦源于任何一个提案节点能完全平等的与其他节点并发的提出提案而带来的问题MultiPaxos 对 BasicPaxos 核心改进是选择
选主
提案节点通过心跳确定当前网络中所有节点里是否存在一个主提案节点 一旦发现没有主节点节点就会在心跳超时后 ( 不存在主节点 ) 使用 BasicPaxos 中定义的准备、批准的两轮网络过程向所有其他节点广播自己 竞选主节点的请求希望整个分布式系统对 由我做主节点 协商达成一致共识 如果得到了决策结点中多数派的批准便宣告竞选成功 选主完成后只有主节点本身才能提出提案。此时无论是哪个提案节点接收到客户端的请求操作都会将请求转发给主节点完成提案而主节点提案无需经过准备过程因为经过选举时那次准备后后续提案都是对相同提案 ID 的一连串批准过程
可以理解为 选主后不会有其它节点与主节点竞争相当于处于无并发环境的有序操作所以此时系统中要对某个值达成一致只进行一次批准交互即可 注 主提案节点竞选类似于 BasicPaxos 过程 任期和分区
原本idvalue二元组变成了三元组idivalue给主节点增加一个 单调递增 的任期编号应对主节点陷入网络分区后重新恢复但系统已完成了重新选主过程此时必须以任期编号大的节点为准
我们假设网络恢复正常如下图
网络分区 raft 算法 对于 双主问题 解决方案 从整体来看当节点有了选主机制后可以进一步简化为 主节点Leader和从节点(Follower)不必区分提案节点、决策节点和记录节点了 结点状态与竞选 leader
每个节点有三种状态followercandidateleader状态之间是互相转换的
主节点主节点负责与客户端通讯给follower发心跳同步日志与提交命令给 从节点
从节点每一个有一个倒计时器时间随机倒计时结束后自动转换成 candidate结点初始状态都是 follower
candidate 向其它结点发送投票请求收到半数以上票时candidate 成为 leader并向其它 follower 发送心跳。如果再给其它 follower 发心跳同时收到了其它 candidate 的心跳说明同时当选 leader则本轮竞选无效再通过重置倒计时器重新竞选
倒计时器 当受到 candidate 投票请求与 leader 心跳倒计时器重新刷新倒计时 如何保证数据一致
客户端向服务端发送存储数据的请求
leader 记日志把消息分发 follower 记日志leader 提交响应客户端提交成功然后通知 follower 提交
发生网络分区时两个分区分别选举 leader出现脑裂那么超过半数结点的分区 leader 可以继续对外服务另一个分区 leader 无法提交
恢复网络正常后小于半数结点的分区 leader 重新变成 follower同时该分区的结点通过主节点日志追加丢失的数据 三 结语
身处于这个浮躁的社会却有耐心看到这里你一定是个很厉害的人吧
各位博友觉得文章有帮助的话别忘了点赞 关注哦你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容加油吧技术人
