分布式一致性算法（Paxos、Raft、ZAB）

仅用作自己记录

CAP理论

• 一般来说，对于一个分布式系统，不能同时满足以下三点：

  • Consistency (一致性)
  • Availability (可用性)
  • Partition Tolerance (分区容错性)

• 典型例子

  一致性	可用性	分区容错性	产品
  高	高	低	RDBMS(MySQL、PostgreSQL等)
  高	低	高	HBase、MongoDB、Redis、ZooKeeper
  低	高	高	Cassandra

• 解释

  • MySQL中，部分节点挂了，导致集群无法正常提供服务，这就是分区容错性低（不具备数据冗余性）
  • HBase存在主节点，一但主节点挂了，将无法使用，这叫可用性低（当然你可以用HA来解决，但是又会引入其他问题）
  • Cassandra的数据存储采用Gossip协议，实现的是弱一致性（最终一致性，即一条请求的发送进入数据库，到全数据库数据最终一样，需要一定时间），即一致性低

BASE理论

• BASE解释
  • Basically Available (基本可用)
  • Soft state (软状态)
  • Eventually consistent (最终一致性)
• 思想：即使分布式系统无法做到强一致性，但可以采用适当的间接性手段，实现弱一致性，最终达到全局的一致性，例如Cassandra数据库使用的Gossip协议

一致性模型

• 强一致性（原子一致性、线性一致性）

  • 在任意时刻，所有节点中的数据是一样的
  • 任何一次读都能读到某个数据的最近一次写的数据
  • 和全局时钟下的顺序一致

• 顺序一致性

  • 任何一次读都能读到某个数据的最近一次写的数据
  • 所有进程的顺序一致，不需要和全局时钟下的顺序一致

• 弱一致性

  • 最终一致性，随着时间推荐，会最终达到全局一致性

• 举例

  • DNS、Gossip都是最终一致性的
  • Paxos、Raft、ZAB是强一致性的（不一定，需看情况）

Basic-Paxos

• 角色分类
  • Proposer 提案者：可以有多个，用于发起一个议案（由client向Proposer发出），议案包括议案编号、议案内容
  • Acceptor 接收者、批准者：用于接收Proposer提出的议案，并决定采纳哪一个议案
  • Learner 学习者、记录者：在最终决定采纳某个议案后，进行记录，不做其他事
• 约束条件
  • Acceptor必须接受它收到的第一个议案
  • Acceptor只认可接收到的最新的议案（即议案编号最新）
  • 当某个议案被一半以上Acceptor认可后，那么该议案成功
• 运作流程

  Proposer 广播 ---Prepare(n)---> 所有的 Acceptor
  
  Proposer <---接受--- Acceptor 1
  Proposer <---接受--- Acceptor 2
  Proposer <---否认--- Acceptor 3
  
  // 如果有一半以上Acceptor接受，那么该议案成功
  // 否则说明还有其他Proposer的议案（编号不同），隔一个随机时间，更新自己的议案编号，重提
  Proposer 广播 ---Accpet(n, value)---> 所有的 Acceptor
  
  // 议案通过
  Proposer <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]
  

Multi-Paxos

• 说明
  • Basic-Paxos每次都要重新选举一个可信任的Proposer，但实际上Proposer不会随时都挂掉
  • 因此，应该先只选举一次可信任的Proposer，后续的议案都由它来发起
  • 当该Proposer挂了（没有心跳包），再次进行选举即可
  • 该Proposer叫做Leader，Leader只有一个
• 运作流程

  // 第一次，需要选举一个 Leader
  Leader 广播 ---Prepare(n)---> 所有的 Acceptor
  Leader <---接受--- Acceptor 1
  Leader <---接受--- Acceptor 2
  Leader <---否认--- Acceptor 3
  // 如果有一半以上Acceptor接受，那么选举成功
  
  // 后续一直重复该流程 1
  Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
  Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]
  
  // 后续一直重复该流程 2
  Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
  Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]
  
  // 后续一直重复该流程 3
  Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
  Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]
  
  ......
  
  // 后续一直重复该流程 n
  ......
  

Raft

• 代表：copycat
• 说明
  • Raft是Multi-Paxos的简化模型
  • 区别
    • Raft中追加日志的操作必须是连续的（Multi-Paxos中是并发）
    • 只有拥有最新、最全日志的节点才能够当选Leader（Multi-Paxos中任意节点都可以写日志，无限制）
• 运作流程
  • 同Multi-Paxos
  • Leader对应Leader
  • Acceptor对应Follower
• 可供参考的动态图
  • https://raft.github.io/
  • http://thesecretlivesofdata.com/raft/

ZAB

• 代表： ZooKeeper
• 基本与Raft相同
• 不同点
  • Raft每一次leader的任期叫做term，ZAB中叫做epoch
  • Raft有leader向follower发送心跳，ZAB相反
  • 选主投票方式不同
  • 事务操作方式不同

ZooKeeper-ZAB

• Leader选举：Leader挂了，其他节点将进行重新选举。各节点优先投自己一票（myId, zxid），再广播至其他节点。每个节点对比收到的票，zxid大的优先，zxid相等再按myId大的优先。选中某个投票后，会再向集群其他节点广播选中的票。当某个票被集群中超过一半的节点选中后，该票对应的Follower升为Leader（也就是说，一个节点A会查看收到的票，如果其中的某个节点的得票数超过集群节点数的一半，这个节点A就认为该票对应的Follower是Leader，其他节点依此类推）。
• 集群消息广播：当Client一次写请求发送至ZooKeeper集群时，无论连接的是什么节点，写操作都会转发至Leader，由Leader来控制写（保证一致性）。每一次写操作都会更新zxid。Leader会先向Follower发送一次请求（Propose），如果超过一半的节点回复Ack，那么Leader会认为没问题，执行commit（向所有节点发送），完成本次写操作。