分布式理论和协议

1.分布式理论

1.1 分布式

1.1.1 分布式特点

  • 分布性
  • 对等性
  • 并发性
  • 缺乏全局时钟
  • 故障总是会发生

1.1.2 分布式环境的问题

  1. 通信异常
  2. 网络分区
  3. 三态 分布式系统的每一次请求与响应,存在特有的三态概念,即成功、失败与超时.

可能的超时现象:

  • 由于网络原因,该请求(消息)并没有被成功的发送到接收方,而是在发送过程就发生了消息丢失现象.
  • 该请求(消息)成功的被发送接收方接收后,并进行了处理,但是在将响应反馈给发送方的过程中,发生了消息丢失现象
  1. 节点故障: 组成分布式系统的服务器节点出现的宕机或僵死现象

1.2 CAP定理

CAP

  • Consistency(一致性): 在多个副本之间是否能够保持一致的特性
  • Availability(可用性): 对于用于的每一个操作请求总是能够在有限时间内返回结果.有限时间:对于用户的一个操作请求,系统必须能够在指定的时间内返回对应的处理结果,如果超过了这个时间范围,那么系统就被认为是不可用的.返回结果:要求系统在完成对用户请求的处理后,返回一个正常的响应结果
  • Partition tolerance(分区容忍性): 分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障.网络分区是指在分布式系统中,不同的节点分布在不同的子网络(机房或异地网络等)中,由于一些特殊的原因导致这些子网络之间出现网络不连通的状态,但各个子网络的内部网络是正常的,从而导致整个系统的网络环境被切分成了若干个孤立的区域

CAP定理中可以看出: 一个分布式系统不可能同时满足一致性、可用性、分区容错性这三个基本需求,最多只能同时满足其中的两项.需要明确的一点,对于一个分布式系统而言,分区容错性可以说是一个最基本的需求

CAP定理

1.3 BASE理论

BASE是对CAP中一致性和可用性权衡的结果,其核心思想是即使无法做到强一致性(Strong consistency),但每个应用都可以根据自身的业务特点,采用适当的方式来使系统达到最终一致性(Eventual consistency).

  • Basically Available(BA,基本可用): 响应时间上的损失；功能上的损失.支持分区失败(e.g. sharding碎片划分数据库)
  • Soft state(S,软状态): 允许系统在不同节点的数据副本之间进行数据同步的过程存在延时
  • Eventually consistent(E,最终一致): 强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能够达到一个一致的状态.本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性

实际应用中,最终一致性分为五类:

  • 因果一致性(Causal consistency):如果进程A在更新完某个数据项后,通知了进行B,那么进程B之后对该数据项的访问都应该能够获取到进程A更新后的最新值,并且如果进程B要对该数据项进行更新操作的话,务必基于进程A更新后的最新值,即不能发生丢失更新情况
  • 读已之所写(Read your writes):进程A更新一个数据项后,它自己总是能够访问到更新过的最新值,而不会看到旧值
  • 会话一致性(Session consistency):系统能够保证在同一个有效的会话中实现“读已之所写”的一致性.
  • 单调读一致性(Monotonic read consistency):如果一个进程从系统中读取出一个数据项的某个值后,那么系统对于该进程后续的任何数据访问都不应该返回更旧的值
  • 单调写一致性(Monotonic write consistency):一个系统需要能够保证来自同一个进程的写操作被顺序的执行

1.4 总结.

  • 使用向上扩展(强悍的硬件)并运行专业的关系型数据库, 能够保证强一致性,能用向上扩展解决的问题都不是问题
  • 如果向上扩展的成本很高,则可以对廉价硬件运营的开源关系型数据库进行水平伸缩和分片,将相关数据分到数据库的同一个片上,仍然能够使用关系型数据库保证事务
  • 如果业务规则限制,无法将相关数据分到同一个分片上,就需要实现最终一致性,在记录事务的软状态(中间状态、临时状态)时若出现不一致,则可以通过系统自动化或者人工干预来修复不一致的问题

2.分布式协议

分布式事务处理模型DTS包括4角色:

  • 应用程序
  • 事务管理器
  • 资源管理器
  • 通信资源管理器

2.1两阶段提交协议

2PC,即 Two-Phase Commit

2.1.1 前提条件

二阶段提交算法的成立基于以下假设:

  • 该分布式系统中,存在一个节点作为协调者(Coordinator),其他节点作为参与者(Cohorts).且节点之间可以进行网络通信.
  • 所有节点都采用预写式日志,且日志被写入后即被保持在可靠的存储设备上,即使节点损坏不会导致日志数据的消失.
  • 所有节点不会永久性损坏,即使损坏后仍然可以恢复.

2.1.2 算法实现

提交请求阶段(投票阶段)

  • 1.事务询问:协调者节点向所有参与者节点询问是否可以执行提交操作,并开始等待各参与者节点的响应.
  • 2.执行事务:参与者节点执行询问发起为止的所有事务操作,并将Undo信息和Redo信息写入日志.
  • 3.各参与者向协调者反馈事务询问的响应: 如果参与者节点的事务操作实际执行成功,则它返回一个Yes消息；如果参与者节点的事务操作实际执行失败,则它返回一个No消息.

提交执行阶段(完成阶段)

执行事务提交

当协调者节点从所有参与者节点获得的相应消息都为Yes时.

  • 1.发起提交请求:协调者节点向所有参与者节点发出 Commit 的请求.
  • 2.事务提交:参与者节点正式完成操作,并释放在整个事务期间内占用的资源.
  • 3.反馈事务提交结果:参与者节点向协调者节点发送 Ack 消息.
  • 4.完成事务: 协调者节点收到所有参与者节点反馈的 Ack 消息后,完成事务.

中断事务

如果任一参与者节点在第一阶段返回的响应消息为No,或者协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时

  • 1.发送回滚请求:协调者节点向所有参与者节点发出 Rollback 的请求.
  • 2.事务回滚:参与者节点利用之前写入的Undo信息执行回滚,并释放在整个事务期间内占用的资源.
  • 3.反馈事务回滚结果:参与者节点向协调者节点发送 Ack 消息.
  • 4.中断事务:协调者节点收到所有参与者节点反馈的 Ack 消息后,取消事务.

二阶段提交成功

二阶段提交失败

2.1.2 优缺点

优点: 原理简单,实现方便

确定:

  • 1.同步阻塞.提交执行过程中,所有参与节点都是事务阻塞型的.当参与者占有公共资源时,其他第三方节点访问公共资源不得不处于阻塞状态.
  • 2.单点故障.由于协调者的重要性,一旦协调者发生故障.参与者会一直阻塞下去.尤其在第二阶段,协调者发生故障,那么所有的参与者还都处于锁定事务资源的状态中,而无法继续完成事务操作.(如果是协调者挂掉,可以重新选举一个协调者,但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题)
  • 3.数据不一致(脑裂).在二阶段提交的阶段二中,当协调者向参与者发送commit请求之后,发生了局部网络异常或者在发送commit请求过程中协调者发生了故障,这回导致只有一部分参与者接受到了commit请求.而在这部分参与者接到commit请求之后就会执行commit操作.但是其他部分未接到commit请求的机器则无法执行事务提交.于是整个分布式系统便出现了数据部一致性的现象.
  • 4.太过保守.如果在协调者只是参与者进行事务提交询问的过程中,参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话,只是协调者只能依靠自身的超时机制来判断是否需要中断事务,这样的策略显得比较保守.二阶段提交协议没有设计较为完善的容错机制,任意一个节点的失败都会导致整个事务的失败.

2.2三阶段提交协议

3PC, 即Three-Phase Commit

2.2.1 介绍

三阶段提交是二阶段提交的改进版,其将二阶段提交协议的“提交事务请求”过程一分为二,形成了由CanCommit、PreCommit、do Commit三个阶段组成的事务处理协议.

2.2.2 算法实现

阶段一(CanCommit)

  • 1.事务询问.协调者向所有的参与者发送一个包含事务内容的CanCommit请求,询问是否可以执行事务提交操作,并开始等待各参与者的响应.
  • 2.各参与者向协调者反馈事务询问的响应.参与者在接收到来自协调者的canCommit请求后,正常情况下,如果其自身认为可以顺利执行事务,那么会反馈Yes响应,并进入预备状态,否则反馈No响应.

阶段二(PreCommit) 执行事务预提交

  • 1.发送预提交请求:协调者向所有参与者节点发出PreCommit的请求,并进入Prepared阶段.
  • 2.事务预提交:参与者接收到PreCommit请求后,会执行事务操作,并将Undo和Redo信息记录到事务日志中.
  • 3.各参与者向协调者反馈事务执行的响应.如果参与者成功执行了事务操作,那么就会返回给协调者Ack 响应,同时等待最终的指令: 提交(Commit)或终止(abort)

中断事务 假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务

  • 1.发送中断请求. 协调者向所有参与者节点发出abort请求
  • 2.中断事务.无论是收到来自协调者的abort请求,或者是在等待协调者请求过程中出现超时,参与者都会中断事务

**阶段三(doCommit) 该阶段将进行真正的事务提交.

执行提交

  • 1.发送提交请求:假设协调者处于正常工作状态,并且它接收到了来自所有参与者的Ack响应,那么它将从预提交状态转换到提交状态,并向所有的参与者发送doCommit请求.
  • 2.事务提交:参与者接收到doCommit请求后,会正式执行事务提交操作,并在完成提交后释放在整个事务执行期间占用的事务资源.
  • 3.反馈事务提交结果.参与者在完成事务提交后,向协调者发送Ack消息.
  • 4.完成事务:协调者接收到所有参与者反馈的Ack消息后,完成事务.

中断事务

  • 1.发送中断请求.协调者向所有的参与者节点发送abort请求
  • 2.事务回滚.参与者接收到abort请求后,会利用其在阶段二中记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源.
  • 3.反馈事务回滚结果. 参与者在完成事务回滚之后,向协调者发送Ack信息.

  • 4.中断事务.协调者接收到所有参与者反馈的Ack信息后,中断事务

    三阶段提交成功

2.2.3 优缺点

优点:降低参与者阻塞范围,并能够在出现单点故障后继续达成一致 缺点:引入preCommit阶段,在这个阶段如果出现网络分区,协调者无法与参与者正常通信,参与者依然会进行事务提交,造成数据不一致.

无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题.Google Chubby的作者Mike Burrows说过, there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即世上只有一种一致性算法,那就是Paxos,所有其他一致性算法都是Paxos算法的不完整版.

2.2.4 2PC和3PC区别

区别 2PC 3PC
阶段 提交事务请求 以及 执行事务提交 只有协调者有超时判断.3PC将2PC的提交事务请求分成了CanCommit以及PreCommit
超时 只有协调者有超时判断 3PC上参与者和协调者都有超时的判断

2.3 TCC协议

TCC协议,Try+Confirm+Cancel

2.3.1 介绍

Try: 尝试执行业务

  • 完成所有业务检查(一致性)
  • 预留必须业务资源(准隔离性)

Confirm:确认执行业务

  • 真正执行业务
  • 不作任何业务检查
  • 只使用Try阶段预留的业务资源
  • Confirm操作要满足幂等性

Cancel: 取消执行业务

  • 释放Try阶段预留的业务资源
  • Cancel操作要满足幂等性

2.3.2 算法实现

保证最终一致性的模式

  • 1.查询模式 (每个服务操作都要唯一流水表示,以供查询)
  • 2.补偿机制(自动恢复,通知运营手工补偿,技术运营例如修改数据库等)
  • 3.异步确保模式(将执行的任务持久入库,定时任务补偿处理)
  • 4.定时校对模式(需要全局唯一流水ID)
  • 5.可靠消息模式
  • 6.缓存一致性模式

TCC协议

2.3.3 优缺点

  • 对应用的侵入性强.业务逻辑的每个分支都需要实现try、confirm、cancel三个操作,应用侵入性较强,改造成本高
  • 实现难度较大.需要按照网络状态、系统故障等不同的失败原因实现不同的回滚策略.为了满足一致性的要求,confirm和cancel接口必须实现幂等

2.4 Paxos

是一个叫莱斯利.兰伯特的牛人提出的一种基于消息传递且具有高度容错特性的一致性算法,是目前公认的的解决分布式一致性问题最有效的算法之一.

很多人都会认为zookeeper就是paxos算法的实现,但实际上,zookeeper并没有完全采用Paxos算法,而是采用一种zab(zookeeper atomic broadcast)的协议作为其数据一致性的和核心算法

2.4.1 定义

在一个可能发生异常的分布式系统中,快速正确的在集群内部对某个数据的值达成一致,且保证无论发生任何异常,都不会破坏整个系统的一致性

  • 允许消息重复,丢失、但是不允许被修改
  • 在结点数少于半数失效的情况下仍然能正常的工作,结点失效可以在任何时候发生而不影响算法正常执行

实现的时候采用一组固定数目Server,每个Server同时担任上述三个角色,多个Client将自己的请求值Value_i随机发给一个Server处理,然后这一组Server经过协商后得出统一的一个值Chosen_Value,这个值必须被每个Server学习到,同时回复给所有发起请求的Client.

2.4.2 算法实现

Paxos算法分为4种角色:

  • Proposer: 提议者
  • Acceptor: 决策者
  • Client: 产生议题者
  • Learner: 最终决策学习者

提议者和决策者是很重要的,其他的2个角色在整个算法中应该算做打酱油的,Proposer就像Client的使者,由Proposer使者拿着Client的议题去向Acceptor提议,让Acceptor来决策.这里上面出现了个新名词:最终决策.现在来系统的介绍一下paxos算法中所有的行为:

  • Proposer提出议题
  • Acceptor初步接受 或者 Acceptor初步不接受
  • 如果上一步Acceptor初步接受则Proposer再次向Acceptor确认是否最终接受
  • Acceptor 最终接受 或者Acceptor 最终不接受

Paxos提议过程

第一阶段 1.阶段1a,prepare(准备)阶段,预定proposal(提议)序号 每个提议者(proposor)拿到某个client的请求value_i后,此阶段还不能发起proposal,只能发送一个proposal序号N,将序号发送给所有的acceptor(接受者),所有的server包括自己.整个系统中所有proposal的序号不能重复且每个proposor自己用到的序号必须递增,通常的做法是,假如k台server协同运行paxos算法,那么server_i(i=0..k-1)用到proposal虚化初始化为i,以后每次要产生新序号时递增k,这样保证所有的server的proposal序号不重复

2.阶段1b,回应承诺阶段 每个acceptor收到proposal序号后,先检查之前是否Repond序号更高的proposal,若没有,那么就给出response,这个response带有自己的已经accept的序号最高的proposal(若还没accept任何proposal,回复null),同时,promise(承诺)自己不再accept低于接收序号的proposal,否则,拒绝respond.

第二阶段 1.阶段2a---发起Proposal,请求Accept Proposal如果得到了来自果树的acceptor的response,那么久有资格向acceptor发起proposal.其中n是阶段1a中发起的序号,value是收到的response中序号最大的proposal的value,若收到的response全部是null,那么value自定义,可以直接选一个client请求的value_i

2.阶段2b--Accept Proposal 检查收到的Proposal的序号是否违反阶段1b的Promise,若不违反,则Accept收到的Proposal.

Paxos

2.4.3 追本溯源: 拜占庭将军问题

拜占庭将军问题

results matching ""

    No results matching ""