Cloud
Cloud

分布式基础理论

CAP理论

CAP理论可表述为，一个分布式系统最多只能同时满足一致性Consistency、可用性Availability和分区容错性Partition Tolerance三项中的两项；

  • 一致性：所有节点同时看到相同的数据，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致，等同于所有节点拥有数据的最新版本
  • 可用性：任何时候读写都是成功的，即服务一直可用，且是正常响应时间；
  • 分区容错性：当部分节点出现消息丢失或者分区故障时，分布式系统仍然能够继续运行，即系统容忍网络出现分区，且在遇到某节点或网络分区之间网络不可达的情况下，仍然能够对外提供满足一致性和可用性的服务；

分布式系统所关注的就是在分区容错性的前提下，如何实现更好的可用性和更稳定的一致性，业务上对一致性的要求会直接反映在系统设计中，典型的就是CP和AP架构：

  • CP 架构：放弃可用性，追求一致性和分区容错性
  • AP 架构：放弃强一致性，追求分区容错性和可用性，这是很多分布式系统设计时的选择，Base也是根据AP来扩展的

对于多数大型互联网应用的场景，结点众多、部署分散，且现在的集群规模越来越大，所以节点故障、网络故障是常态，且要保证服务可用性达到N个9，并要达到良好的响应性能来提高用户体验，因此一般都会做出如下选择：保证P和A，舍弃C强一致，保证最终一致性；

BASE理论

BASE是三个短语的简写，即基本可用Basically Available、软状态Soft State和最终一致性Eventually Consistent；BASE理论的核心思想是最终一致性，即使无法做到强一致性Strong Consistency，但每个应用都可根据自身业务特点，采用适当的方式来使系统达到最终一致性Eventual Consistency；

基本可用

基本可用即不追求CAP中的任何时候读写都是成功的，而是系统能够基本运行，一直提供服务，基本可用强调了分布式系统在出现不可预知故障的时候，允许损失部分可用性，相比正常的系统，可能是响应时间延长，或者是服务被降级；

如在双十一秒杀活动中，若抢购人数太多超过了系统的QPS峰值，可能会排队或者提示限流，这就是通过合理的手段保护系统的稳定性，保证主要的服务正常，保证基本可用；

软状态

软状态可对应ACID事务中的原子性，在ACID事务中实现的是强一致性，要么全做要么不做，所有用户看到的数据一致，原子性Atomicity要求多个节点的数据副本都是一致的，强调数据的一致性；原子性可以理解为一种硬状态，软状态则是允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时；

最终一致性

数据不可能一直是软状态，必须在一个时间期限之后达到各个节点的一致性，在期限过后，应当保证所有副本保持数据一致性，也就是达到数据的最终一致性；在系统设计中，最终一致性实现的时间取决于网络延时、系统负载、不同的存储选型、不同数据复制方案设计等因素；

CAP及BASE的关系

BASE理论是在CAP上发展的，CAP理论描述了分布式系统中数据一致性、可用性、分区容错性之间的制约关系，当选择了其中的两个时，就不得不对剩下的一个做一定程度的牺牲；

BASE理论则是对CAP理论的实际应用，也就是在分区和副本存在的前提下，通过一定的系统设计方案，放弃强一致性，实现基本可用，这是大部分分布式系统的选择，如NoSQL系统、微服务架构；

Paxos算法

在Paxos协议中有三类节点角色，分别是Proposer提案者、Acceptor批准者和Learner学习者；Proposer和Acceptor是算法核心角色，Paxos描述的就是在一个由多个Proposer和多个Acceptor构成的系统中，如何让多个Acceptor针对Proposer提出的多种提案达成一致的过程，而Learner只是学习最终被批准的提案：

  • Proposer 提案者：提出提案Proposal，Proposal信息包括提案编号 Proposal ID和提议的值Value
  • Acceptor批准者或接受者：参与决策回应Proposers的提案，在集群中Acceptor有N个，Acceptor之间完全对等独立，Proposer提出的value必须获得超过半数N/2+1的Acceptor批准后才能通过
  • Learner学习者：不参与决策从Proposers/Acceptors学习最新达成一致的提案Value；

Paxos选举过程

准备阶段

Proposer生成全局唯一且递增的ProposalID，向Paxos集群的所有机器发送Prepare请求，这里不携带value，只携带N即ProposalID；Acceptor收到Prepare请求后，判断收到的ProposalID是否比之前已响应的所有提案的N大，如果否，则不回复或者回复Error，如果是则：

  • 在本地持久化N，可记为Max_N；
  • 回复请求，并带上已经Accept的提案中N最大的value，若此时还没有已经Accept的提案，则返回value为空；
  • 做出承诺，不会Accept任何小于Max_N的提案；
选举阶段

为了方便描述，把选举阶段继续拆分为P2a、P2b和P2c

  • P2a：Proposer发送Accept：经过一段时间后，Proposer收集到一些Prepare回复，有下列几种情况：

    • 若回复数量大于一半的Acceptor数量，且所有回复的value都为空时，则Porposer发出accept请求，并带上自己指定的value；
    • 若回复数量大于一半的Acceptor数量，且有的回复value不为空时，则Porposer发出accept请求，并带上回复中ProposalID最大的value，作为自己的提案内容；
    • 若回复数量小于等于一半的Acceptor数量时，则尝试更新生成更大的ProposalID，再转到准备阶段执行；

  • P2b：Acceptor应答Accept：Accpetor收到Accpet请求后，判断：

    • 若收到的N >= Max_N一般情况下是等于，则回复提交成功，并持久化N和value；
    • 若收到的N < Max_N，则不回复或者回复提交失败；

  • P2c: Proposer统计投票：经过一段时间后，当收到一条提交失败的回复时，则尝试更新生成更大的ProposalID转到准备阶段执行，Proposer会收集到一些Accept回复提交成功的情况：

    • 当回复数量 > 一半的Acceptor数量时，则表示提交value成功，此时可发广播给所有Proposer、Learner，通知它们已commit的value；
    • 当回复数量 <= 一半的Acceptor数量时，则尝试更新生成更大的ProposalID，转到准备阶段执行；

ZAB协议

ZooKeeper是通过Zab协议来保证分布式事务的最终一致性，Zab即ZooKeeper Atomic Broadcast，ZooKeeper原子广播协议支持崩溃恢复，基于该协议ZooKeeper实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性；在ZooKeeper集群中，所有客户端请求都是写入到Leader进程中的，然后由Leader同步到其他Follower节点，在集群数据同步的过程中，若出现Follower节点崩溃或Leader进程崩溃时，都会通过Zab协议来保证数据一致性；Zab协议的具体实现可分为以下两部分：

  • 消息广播阶段：Leader节点接受事务提交，且将新的Proposal请求广播给Follower节点，收集各个节点的反馈，决定是否进行Commit，在该过程中也会使用Quorum选举机制
  • 崩溃恢复阶段：若在同步过程中出现Leader节点宕机，会进入崩溃恢复阶段，重新进行Leader选举，崩溃恢复阶段还包含数据同步操作，同步集群中最新的数据，保持集群的数据一致性

整个ZooKeeper集群的一致性保证就是在上面两个状态之前切换，当Leader服务正常时，就是正常的消息广播模式；当Leader不可用时，则进入崩溃恢复模式，崩溃恢复阶段会进行数据同步，完成以后重新进入消息广播阶段；

ZXid

Zxid是Zab协议的一个事务编号，Zxid是一个64位的数字低32位是一个简单的单调递增计数器，针对客户端每一个事务请求计数器加1；高32位则代表Leader周期年代的编号；

ZAB流程

ZAB的具体流程可以拆分为消息广播、崩溃恢复和数据同步三个过程;

消息广播

在ZooKeeper中所有事务请求都由Leader节点来处理，其他服务器为Follower，Leader将客户端的事务请求转换为事务Proposal，并将Proposal分发给集群中其他所有的Follower

完成广播之后，Leader等待Follwer反馈，当有过半数的Follower反馈信息后，Leader将再次向集群内Follower广播Commit信息，Commit信息就是确认将之前的Proposal提交

Leader节点的写入也是一个两步操作，第一步是广播事务操作，第二步是广播提交操作，其中过半数指的是反馈的节点数>=N/2+1，N是全部的Follower节点数；

  • 客户端的写请求进来之后，Leader会将写请求包装成Proposal事务，并添加一个递增事务ID，即单调递增的Zxid，以保证每个消息的先后顺序；
  • 广播这个Proposal事务，Leader节点和Follower节点是解耦的，通信都会经过一个先进先出的消息队列，Leader会为每一个Follower服务器分配一个单独的FIFO队列，然后把Proposal放到队列中；
  • Follower节点收到对应的Proposal之后会把它持久到磁盘上，当完全写入之后，发一个ACK给Leader；
  • 当Leader收到超过半数Follower机器的ack之后，会提交本地机器上的事务，同时开始广播commit，Follower收到commit之后，完成各自的事务提交；

Raft算法