分布式理论、协议以及算法相关(CAP、2PC、TCC、Paxos、Raft、一致性Hash等)

1. 分布性系统理论部分

1.1. 拜占庭将军问题(节点共识问题)

  1. 分布式系统中,各节点可能存在故障通信等问题,同时还可能存在恶意攻击等问题,需要在此基础上解决节点的共识问题;
  2. 共识问题解决方法:
    • 基于口信消息
    • 基于签名消息
  3. 算法类型:
    • 存在恶意节点行为(区块链),采用拜占庭容错算法,如BFT/PBFT/Pow
    • 无恶意节点,消息伪造等情况,采用非拜占庭容错(故障容错 - CFT)算法,如Paxos、Raft算法、ZAB协议

1.2. 分布式CAP理论

1.2.1. CAP的三个指标(一致性、可用性、分区容忍性)

  1. 一致性(强调分布式系统的数据一致能力):对客户端的承诺,强调各个节点之间的数据一致,即集群和单节点是一致的。
  2. 可用性(强调分布式系统的分区容错能力):客户端不论访问哪个节点,都能得到响应数据,但不保证是最新的;
  3. 分区容错性:分布式每个分区(节点)在出现故障时(比如通信问题),分布式系统应该任然能提供服务;

在P分区容错性,必然的前提下,我们的分布式系统设计在不同业务上,AP和CP有不同的侧重点,即当出现了分区错误的时候(节点网络问题),应该考虑选择CP还是AP。 - 选择了CP模型,如果在某个节点写失败下,分布式系统会整体拒绝提供服务(读的话可以支持); - 选择了AP模型,如果在某个节点写失败下,分布式系统整体还是保证可用的(可以事后补偿达到最终数据一致);客户端对节点的读取操作,节点返回当前节点提供的信息,允许返回不一致的信息(可能不是最新的信息)。

1.3. ACID - 追求一致性性,CP模型延伸

1.3.1. 二阶段提交,代表XA、TCC、Raft、Paxos

  1. 二阶段提交过程:
    • 投票阶段:Coordinator 协调者, 联系其他节点投票,进入二阶段提交请求阶段(投票阶段),收集投票结果
      • 每个节点如果确认,就需要锁定相关资源,等待协调者投票结果反馈。一旦承诺,就必须确保事务执行到位,即使节点存在故障或其他问题(代码保证)
      • 协调者搜集了全部节点的投票结果,进行评估是否需要执行分布式事务
    • 执行阶段:Coordinator 协调者,基于投票结果,按照要么全部执行,要么全部取消的原则(实现ACID中的原子性),将结果通知所有的节点
      • 每个节点基于通知的结果,确保按协调者的要求执行
  2. 二阶段提交最早用于数据库分布式事务(代表协议XA,比如MYSQL就支持XA分布式事务),XA协议也叫做Distributed Transaction Processing(DTP)模型
  3. 二阶段提交的问题:
    • 节点提交请求节点(投票阶段),需要预留资源(资源锁定)
    • 针对资源预留,数据库是独立的系统,无法弹性的调整锁的粒度,如果锁得范围过大,会影响并发度
    • 问题替代方案 - TCC 利用业务确认和取消的幂等性,确保事务执行成功
  4. Raft、Paxos这类强一致性分布式算法,也采用二阶段提交协议思想,只是需要大部分节点确认就执行事务,而ACID要求全部节点确认才执行事务。
  5. 三阶段提交,是基于考虑到协调者故障,节点参与者资源长时间锁定问题,加入节点询问和超时机制,但带来了更多的节点消息通信,使得系统更加复杂,较少使用。

1.3.2. TCC(Try-Confirm-Cancel),事务补偿

  1. TCC(预留-确认-取消)
    • 预留阶段(TRY):
      • 协调者尝试让各个节点保留资源,准备执行各自的任务
      • 协调者注册确认与取消操作
      • 协调者收集各节点,针对预留节点的回复
    • 确认阶段(Confirm):
      • 执行预留阶段资源满足情况下,协调者确认操作,协调者向各个节点发送事务确认执行的操作
      • 各节点向协调者返回各自任务执行情况
    • 取消阶段(Cancel):
      • 执行预留阶段,如果某节点不满足资源,协调者通知其他节点全部取消操作,达到一致性
  2. TCC的本质是补偿事务,也是基于二阶段提交思想,程序应用扮演了协调者的角色。可以将TCC理解为编程模型,即业务层面上的协议,即确认和取消操作都应该是幂等的,因为当确认或取消失败时候,应用程序需要满足补偿重试达到一致;
  3. 少用TCC:TCC不是依赖数据库来实现分布式事务的一致性,而是在业务层面上实现分布式事务,好处是对数据库压力减少,带来的问题就是对代码的侵入性增加,提升了代码的复杂度。因此,从代码简洁和维护性上,如果要确保分布式事务的强一致性,优先考虑支持分布式事务的数据库,比如MYSQL XA,当数据库无法满足业务要求时候(比如性能开销),再来考虑TCC。
  4. 幂等性:同一操作对同一系统,所产生的影响均与一次执行的影响一致,不会因为多次导致副作用的产生,主要是基于Token、索引这类唯一标识,标记同一操作,消除多次执行的副作用
  5. 失败重试:幂等性需要将提交相关信息保存到持久存储上,即使故障、超时,也需要在故障恢复、超时后,不断重试以实现自己的承诺。

1.3.3. ACID在CAP中的考虑

ACID是强一致性,即CP优先考虑,可用性方必然受到损失。如果一个节点出现,分布式事务是必然失败的。但绝大多数场景,对一致性要求没有那么高,

1.4. BASE - 追求可用性,AP模型的延伸

1.4.1. BASE(BasicallyAvialiable、SoftState、EventuallyConsistent) - 基本可用、软状态、最终一致

  1. BASE强调可用性,属于CAP中的AP延伸,其中最关键的是基本可用和最终一致,软状态指数据的过渡状态,不同节点之间存在短暂的不一致,最终会达成数据的一致。

1.4.2. 基本可用(BasicallyAvailable)分布式设计考虑

在系统过载情况,一方面考虑提供有损服务,弃朱保帅,另一方面积极寻求资源扩容,提升整体系统的吞吐量

  1. 流量错峰(不同地区售票时间错峰出售)
  2. 异步处理(买票排队,基于队列先收到用户买票请求,排队异步处理,延迟响应)
  3. 服务降级(看到非实时数据,采用缓存数据提供服务)
  4. 过载保护(熔断/限流,直接拒绝掉一部分请求,或者当请求队列满了,移除一部分请求,保证整体系统可用)
  5. 故障隔离(出现故障,做到故障隔离,避免影响其他服务)
  6. 弹性扩容(基于Metric和Monitor实现系统态势感知,做到弹性伸缩)

1.4.3. 最终一致性(EventuallyConsistent)

  1. 最终一致:系统所有数据经历一段时间后,最终会达到一个一致的状态;
  2. 最终一致的数据,以什么数据为准:
    • 以最新写入的数据为准(KV存储)
    • 以第一次写入的数据为准(不希望存储数据被更改)
  3. 如何实现最终一致性:
    • 读时修复,读数据的时候,检查分布式各节点数据是否一致,不一致则通知系统修复(读需要做数据比对,考虑开销,算法效率)
    • 写时修复(数据存储+失败重传),写数据的时候,检查分布式各节点数据是否一致,不一致则通知系统同步修复(不需要同其他节点做数据比对,仅在有差异时候才修复)
    • 异步修复,定期检测数据是否一致,最终达到一致(常用)
  4. 考虑设计支持一次性级别,比如All、Quorum、One、Any,让用户选择相应的一致性级别,比如ALL来支持强一致性。

To be continue