分布式系统的一致性算法_分布式一致性算法

一，什么是一致性

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

• 一致性（C）
• 可用性（A）
• 分区容错性（P）

一致性是指分布式系统中的多个服务节点，给定一系列操作，在特定协议的保障下，使这些节点对外呈现的状态是一致的，即保证集群中所有服务节点中的数据完全相同并且能够对某个提案达成一致

一致性分类：

为什么需要一致性

从传统的集中式单节点结构演变到分布式多节点结构，碰到的首个问题就是节点一致性的保障

共识性

共识性描述了分布式系统中多个节点之间，彼此对某个状态达成一致性结果的过程，保证系统达到某一程度的一致性往往核心就是通过共识性算法来完成

共识算法就是对某个节点提出的提案达成一致意见的过程

• 非拜占庭容错类算法
  • 容忍不超过一般的节点故障
• 拜占庭容错类算法
  • 容忍不超过三分之一的节点故障

一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性，描述了多个节点对数据状态的维护能力。

共识性则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。

二，强一致性算法

Paxos

Paxos是基于消息传递且具有高度容错特性的强一致性算法，开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失，延迟，乱序以及重复，他利用大多数机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障

Basic-Paxos

角色介绍

• proposers：向集群提出提议（提议编号+提议的value），起到冲突调节的作用
• Acceptor：参与决策，回应proposers的提议，收到提议后可以接受提议，如果提议获得多数Acceptor的接受，则称该提议被批准
• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

步骤和阶段

• prepare： proposer提出一个提案，编号为N，此N大于这个proposer之前提出的提案编号，请求acceptors的quorum接收
• promise：如果N大于此accpetor之前接收的任何提案编号则接受，否则拒绝
• accept：如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及内容
• accepted：如果此acceptor在此期间没有收到任何大于N的提案，则接受此提案内容，否则忽略

总结：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

缺陷

• 效率低，两次RPC
• 活锁问题

Raft

Raft实现了和Paxos一样的功能，将分布式一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
• Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
• Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

leader选举

follow服务器如果长时间没有接收到leader服务器的请求，他会成为一个candidate并开始一次leader选举，收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

leader选举需要某个节点发起投票，在确定哪个节点向其他节点发起投票之前，每个节点会分配一个随机的选举超时时间，在这个时间内，节点必须等待，不能成为Candidate状态，节点在成为candidate状态后会向其他节点发送投票请求，希望其他节点投票选举自己为leader，在此过程中会出现三种情况：

• 该节点得到大多数节点的投票，成为leader
• 该节点收到了leader的心跳包，表示有其它服务器已经抢先当选了Leader；
• 没有服务器赢得多数的选票，Leader选举失败，等待下一次选举。

选举出leader后，leader通过定期发送心跳包保持自己的leader状态，如果follower在一段时间内没有收到leader的心跳包则认为leader可能已经挂了，就会再次发起leader选举

日志复制

当选举出leader后，follow不在接受客户端的请求，客户端的所有请求都会由leader去处理，leader会将接收到请求写入到leader的日志中，然后向其他并行的服务器发起请求让follow对日志进行复制，当这些日志被复制到大多数服务器上后，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

Zab

Zab全称是zookeeper原子广播协议，是通过Zab协议来保证分布式事务的最终一致性，Zab协议是为分布式协调服务Zookeeper专门设计的一种 支持崩溃恢复 的 原子广播协议 ，是Zookeeper保证数据一致性的核心算法

在Zookeeper中主要依赖Zab协议来实现数据一致性，基于该协议，zk实现了一种主备模型（即Leader和Follower模型）的系统架构来保证集群中各个副本之间数据的一致性。
这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader客户端将数据同步到其他Follower节点。Zookeeper 客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。

• Zab需要确保在leader服务器上提交的事务最终会被所有服务器提交
• Zab需要确保那些只在leader服务器上被提出而没有被提交的事务被丢弃

原理

Zab协议要求每个leader都要经历三个阶段：发现，同步，广播

• 发现：zookeeper集群必须选举出一个leader进程
• 同步：leader要负责将本身的数据和follow完成同步
• 广播：所有的事务请求都必须由leader服务器来处理，leader服务器处理完成后，向所有follow发送数据同步请求，当leader收到超半数follow的正确反馈后，leader会再次向所有follow发送commit请求，要求将上一个事务进行提交

崩溃恢复

当整个集群在启动过程中，或者当leader服务器出现网络中断，崩溃退出或者异常或者重启时，Zab会进入崩溃恢复模式，重新进行选举产生新的leader

当选举产生了新的 Leader，同时集群中有过半的机器与该 Leader 服务器完成了状态同步（即数据同步）之后，Zab协议就会退出崩溃恢复模式，进入消息广播模式。

这时，如果有一台遵守Zab协议的服务器加入集群，因为此时集群中已经存在一个Leader服务器在广播消息，那么该新加入的服务器自动进入恢复模式：找到Leader服务器，并且完成数据同步。同步完成后，作为新的Follower一起参与到消息广播流程中

Zab 协议如何保证数据一致性

1、一个事务在 Leader 上提交了，并且过半的 Folower 都响应 Ack 了，但是 Leader 在 Commit 消息发出之前挂了。
2、假设一个事务在 Leader 提出之后，Leader 挂了。

Zab 协议崩溃恢复要求满足以下两个要求：
1）确保已经被 Leader 提交的 Proposal 必须最终被所有的 Follower 服务器提交。
2）确保丢弃已经被 Leader 提出的但是没有被提交的 Proposal。