分布式集群系统-一致性协议、基本理论和算法

小鱼儿 2022-12-21 00:48 151阅读 0赞

### 分布式集群系统 ###

*  一、分布式系统存在的问题
 *  二、分布式理论
 *   *  1、CAP理论（一致性、可用性、分区容错性）
     *  2、BASE理论（基本可用、软状态、最终一致性）
     *  3、一致性协议2PC（投票、提交）
     *  4、一致性协议3PC（canCommit、PreCommit、DoCommit）
     *  5、一致性算法Paxos
     *  6、一致性算法Raft
     *   *  1、leader选举
         *  2、日志复制（log replicate）

# 一、分布式系统存在的问题 #

*  通信异常
 *  网络分区
 *  节点故障
 *  三态

分布式系统特有的三态概念：成功、失败、超时。

网络异常的情况下出现 ***超时***：

1、请求没有被成功发送到接收方；

2、接收方处理成功后，响应反馈给发送方过程中，发生了消息丢失现象。

> 一致性有哪几种？

弱一致性

单调读一致性

因果一致性

最终一致性

# 二、分布式理论 #

## 1、CAP理论（一致性、可用性、分区容错性） ##

*  所有副本数据一致（即强一致性）
 *  系统一直可用
 *  节点故障或网络分区故障时，仍能够满足一致性和可用性

一般情况不会考虑舍弃P，而是考虑C或A，总之，分区容错性是一定要满足的。考虑在一致性和可用性之间做个协调。

## 2、BASE理论（基本可用、软状态、最终一致性） ##

基本可用：绝不等价于系统不可用，而是以下两点：

*  牺牲响应时间（12306刷不到余票，多试几次）
 *  牺牲功能上的损失（双十一购物商品页为了保证一致性，部分请求被引导到降级页面）

软状态（支付中。。配送中。。审批中。。）

最终一致性：付款为付款中过一段时间后，支付完成

## 3、一致性协议2PC（投票、提交） ##

mysql、oracle支持2PC，数据库参与者是各个数据库

优点：简单

缺点：1）同步阻塞，影响分布式性能；

2）单点问题，如果协调者出问题，流程无法运转；

3）数据不一致

设当协调者向所有的参与者发送 commit 请求之后，发生了局部网络异常或者是协调者在尚未发送完所有 commit 请求之前自身发生了崩溃，导致最终只有部分参与者收到了 commit 请求。这将导致严重的数据不一致问题。

4）过于保守

某个参与者出现问题后，协调者只能等待其超时

## 4、一致性协议3PC（canCommit、PreCommit、DoCommit） ##

进行到阶段三可能出现的问题：

1）协调者出现问题；  
2）协调者和参与者之间的网络故障；

以上问题导致参与者无法接收到doCommit或abort请求，导致参与者在等待超时之后，直接进行事务提交。

> 对比

2PC只有协调者有超时机制；3PC参与者也有超时机制；

3PC在阶段三，参与者等待超时时，会直接进行事务提交；

3PC多了一个缓冲阶段，保证了最终提交前各参与者节点的状态是一致的。

但是，3PC并没有完全解决数据不一致的问题。

## 5、一致性算法Paxos ##

> 解决什么问题？

分布式系统一致性问题。（拜占庭将军问题）

2PC、3PC提交有个问题，每个 ***参与者*** 提交不同数据，以谁为准呢？这个问题引入了 ***协调者*** 的角色，但是协调者又有可能会故障，所以协调者也需要集群部署，这里又以哪个协调者为准呢？Paxos就是为了解决这个问题而产生的。

Paxos引入几个角色：Proposer（提案发起者）、Acceptor（决策者）、Learner(最终决策后的效仿者)

> 目的在多个Proposer和多个Accepter中选择一个唯一提案。

Paxos算法分两个阶段（即两个请求）：

Proposer两次请求：Prepare请求(携带提案,提案有自身编号)/Accept请求（先学习到已发布的提案编号）

> 如何保证Paxos算法活性？

1、通过选举主Proposer，并规定只有主Proposer才能提出议案。

2、只要主Proposer和过半的Accepter能够正常通信，一旦主Proposer提出编号更高的提案，就会被批准。

## 6、一致性算法Raft ##

[Raft动画描述][Raft]

[https://raft.github.io/][https_raft.github.io]

### 1、leader选举 ###

> 心跳机制

*  leader会向各follower发送心跳包，两次心跳之间，各Follower处于倒计时状态；
 *  如果leader挂掉，最先超时的follower先选举自己为candidate，然后向各Follower发送拉票请求；
 *  如果大多数Follower选择投票给该candidate，该节点将升级为leader；
 *  如果出现多个candidate，大家会重新等待超时，最先超时的重新晋升为candidate，然后再拉票；

### 2、日志复制（log replicate） ###

也就是数据同步。

*  如果某个Follower挂掉，过段时间后又复活，那它会从leader同步最新数据，加入Follower；
 *  如果leader挂掉，再重新选举新的leader后，该节点又复活，它将从leader同步最新数据，并加入Follower；

[Raft]: http://thesecretlivesofdata.com/raft/
[https_raft.github.io]: https://raft.github.io/