0%

分布式

Posted on Edited on

DaintreeRiver_ZH-CN2284362798_1920x1080.jpg

CAP 理论

CAP 定理的含义

分布式系统有三个指标：一致性、可用性和分区容错性，CAP 原理表示这三个指标不可能同时做到。

pic

分区容错

大多数分布式系统分布在多个子网中，每个子网叫做一个区。分区容错性的意思是，区内部可以正常通信，但区间通信可能失败。在分布式系统中，分区容错性必不可少，即 P 总是成立的，因为需要总是假设网络是不可靠的。

一致性

一致性指发生写操作后，分布式节点必须都能返回新的值。CAP 理论的一致性指的是强一致性。

可用性

可用性指在任意时刻，服务器都能处理用户发送的请求。

权衡

分布式必须保证分区容错性，但一致性和可用性存在矛盾，需要进行权衡。

为了保证一致性，当分布式系统某节点在对数据进行写操作时，必须锁定其他节点该数据的读写操作，才能满足一致性；而当锁定数据期间，分布式系统无法满足可用性。

为了保证可用性，当分布式系统某节点在对数据进行写操作时，其他节点仍然能够提供该数据相关的服务，才能满足可用性；而此时无法满足一致性。

BASE 原则

分布式系统的BASE理论

BASE 理论是对 CAP 理论一致性和可用性权衡的结果，核心思想是虽然无法达到强一致性，但是可以采用适当的方式达到最终一致性。BASE 指基本可用，软状态和最终一致性。

基本可用

基本可用指分布式系统在出现故障的时候，允许损失部分可用性，保证核心功能可用性。

软状态

允许存在中间状态，而该中间状态不会影响系统的可用性。即允许数据同步时存在延迟。

最终一致性

分布式系统的数据在经过一段时间后，能够达到一致。

FLP 不可能原理

在异步通信场景下，即使只有一个进程失败，也没有任何算法保证非失败进程达到一致性。

2PC

2PC 是两阶段提交，引入协调者来协调参与者的行为，并最终决定这些参与者是否要真正提交事务。

2PC 过程

  • 准备阶段
    • 协调者向参与者发送事务内容，询问参与者是否可以提交事务
    • 各个参与者执行事务操作，并将信息写入 undo 和 redo 日志
    • 如果参与者执行成功，返回 yes；如果执行失败，返回 no
  • 提交阶段
    • 如果所有参与者返回 yes
      • 协调者向参与者发送提交请求
      • 参与者提交事务，并返回 ACK 完成消息
      • 协调者收到所有参与者的 ACK ，即完成事务提交
    • 如果存在参与者返回 no
      • 协调者向参与者发送回滚请求
      • 参与者回滚事务，并返回 ACK 完成消息
      • 协调者收到所有参与者的 ACK ，即完成事务回滚

2PC 问题

  • 同步阻塞
  • 单点故障
  • 数据不一致
  • 没有容错性

3PC

3 PC 是三阶段提交，是 2 PC 的改进版本。3PC 引入了超时机制，并且将 2PC 的准备阶段一分为二，产生三阶段提交。

3PC 过程

  • CanCommit
    • 协调者向参与者发送 CanCommit 请求，询问是否可以执行事务提交操作
    • 参与者如果自身能够顺利执行事务，返回 yes；否则返回 no
  • PreCommit
    • 如果所有参与者返回 yes，执行 PreCommit
      • 协调者向参与者发送 PreCommit 请求
      • 参与者收到 PreCommit 请求，执行事务，将操作写入 undo 和 redo 日志
      • 参与者根据执行情况发送 ACK 响应
    • 如果至少有一个参与者返回 no 或协调者等待超时
      • 协调者向所有参与者发送中断请求
      • 参与者收到中断请求或超时，执行事务中断
  • doCommit
    • 协调者收到所有参与者的 ACK 响应
      • 协调者向参与者发送 doCommit 请求
      • 参与者收到 doCommit 请求或者超时，正式提交事务
      • 事务提交完成后，向协调者发送 ACK
      • 协调者收到所有参与者 ACK ，完成事务
    • 协调者收到 no 或等待超时
      • 执行者向所有参与者发送中断请求
      • 参与者收到中断请求，进行事务回滚并释放事务资源
      • 参与者向协调者发送 ACK
      • 协调者收到 ACK 后执行事务中断

协调者在 CanCommit 和 PreCommit 阶段，如果收到至少一个 no 或等待超时，都会中断事务；

在 PreCommit 阶段，如果参与者等待超时，会中断事务；在 doCommit 阶段，如果参与者等待超时，会自动提交事务

3PC 问题

3PC 在等待超时后协调者或参与者会中断事务，能够避免单点故障问题；在 doCommit 阶段，如果协调者单点故障，参与者会自动提交事务。

由于引入超时机制，协调者和参与者不会无限等待下去，在一定程度上减缓了同步阻塞问题。

但 3 PC 仍然存在数据不一致问题，如果参与者收到 PreCommit 请求并给予响应，等待 doCommit 请求时，协调者发生故障，那么参与者会提交事务，造成数据不一致。

Paxos 协议

Paxos 协议用于解决分布式系统一致性问题。将所有节点都写入同一个值，一旦写入不可更改。

Paxos 的两个操作：

  • Proposal Number：提议编号，可理解为提议版本号，要求不能冲突
  • Proposal Value：提议的值

Paxos 的三个角色：

  • Proposer：提议发起者，不同的发起者可以提议不同的 Value
  • Accpetor：提议接受者，接受者有 N 个且彼此独立。Proposer 提出的 Value 必须获得超过半数 $\frac{N}{2}+1$ 接受者的批准才能通过
  • Learner：提议学习者，把通过的确定性值同步给其他未确定的 Accpetor

Proposer 将发起提案 Value 给所有 Accpetor，超过半数 Accpetor 获得批准后，Proposer 将提案写入Accpetor 内，最终所有 Accpetor 获得一致性的确定性取值，且后续不允许再修改。

Paxos 过程

  • 准备阶段
    • 每个提议发起者 Proposer 选择一个提议编号 N 并向所有提议接受者 Accpetor 发送提议请求
    • 每个提议接受者 Accpetor 接受提议请求 $(n_i,v_i )$
      • 提议者之前未接受过任何提议请求，那么提议接受者发送一个 $(no \ previous)$ 提议响应，设置当前接受的提议为 $(n_1,v_1 )$ ，并保证以后不会接受序号小于 $n_1$ 的提议
      • 提议者之前接受过提议请求
        • 新的提议请求的 $n_2$ 大于等于已接受提议的 $n_1$ ，发送 $(n_1,v_1)$ 提议响应，并设置当前接受提议为 $(n_2,v_2 )$
        • 新的提议请求的 $n_2$ 小于已接受提议的 $n_1$，不响应
  • 接受阶段（此阶段也不接受小于当前 n 的提议）
    • 计算提交响应
      • 如果提交响应未超过半数 $\frac{N}{2}+1$ ，提议失败
      • 如果提交响应超过半数 $\frac{N}{2}+1$，可发送接受请求，发送它收到的最大提议编号的值
    • 提议接受者接受到接受请求
      • 如果提议版本号小于自己保存的记录版本号，不接受
      • 如果提议版本号大于等于自己保存的记录版本号，写入本地
  • 学习阶段
    • 提议接受者向提议学习者发送自己接受的提议 $(n,v)$
    • 提议学习者选择出大多数接受的提议并把值同步给其他未确定的接受者 Accpetor