分布式学习（二）

如何让程序通过协作共同去达成一个业务目标？

答：1.使用分布式互斥 2.使用分布式选举 3.使用分布式共识 4.使用分布式事务

④ 分布式协调与同步

1.分布式互斥算法

对于同一共享资源，一个程序正在使用的时候也不希望被其他程序打扰。这就要求同一时刻只能有一个程序能够访问这种资源。

在分布式系统里，这种排他性的资源访问方式，叫作分布式互斥，而这种被互斥访问的共享资源就叫作临界资源。

分布式互斥算法一：集中式算法
- 优点：直观、简单、信息交互量少、易于实现、程序只需和协调者通信，程序之间无需通信
- 缺点：协调者可能会成为系统的性能瓶颈、单点故障(使用主备)
- 使用场景：较为广泛

引入一个协调者程序，得到一个分布式互斥算法：

每个程序在需要访问临界资源时，先给协调者发送一个请求；

如果当前没有程序使用这个资源，协调者直接授权请求程序访问，否则，按照FIFO规则进行排队等待；

如果有程序使用完资源，则通知协调者，协调者从队列里取出排在最前面的请求，并给它发送授权消息，拿到授权消息的程序，可以直接去访问临界资源

一个程序完成一次临界资源访问，需要如下几个流程和消息交互(三次)：

向协调者发送请求授权信息，1 次消息交互；

协调者向程序发放授权信息，1 次消息交互；

程序使用完临界资源后，向协调者发送释放授权，1 次消息交互。

分布式互斥算法二：分布式算法（组播和轮播算法）
- 优点：每个程序按时间顺序公平地访问资源、简单粗暴、易于实现
- 缺点：可用性比集中式算法低（1.临界资源的程序增多时，容易产生“信令风暴” 2.一旦某一程序发生故障，会导致整个系统不可用）
- 改进：如果检测到一个程序故障，则直接忽略这个程序，无需再等待它的同意消息
- 适用场景：节点数目少且变动不频繁的系统，且由于每个程序均需通信交互，因此适合P2P结构的系统。(Hadoop)

当一个程序要访问临界资源时，先向系统中的其他程序发送一条请求消息（请求的资源、请求者的 ID，以及发起请求的时间），在接收到所有程序返回的同意消息后，才可以访问临界资源；

如果当前程序正在使用资源，其他程序申请了这个资源，那么当前程序会将这个申请资源的程序放在队列（记录请求资源的时间、对应的程序、申请的资源）里，等到释放此资源，就向队列里的第一个需要此资源的程序发送”同意使用资源“的消息，并从队列移除此程序（机制：先到先得、投票需全票通过）

一个程序完成一次临界资源的访问，需要进行如下几个流程和信息交互(2*(n-1))：

向其他 n-1 个程序发送访问临界资源的请求，总共需要 n-1 次消息交互；

需要接收到其他 n-1 个程序回复的同意消息，方可访问资源，总共需要 n-1 次消息交互。

分布式互斥算法三：令牌环算法（一致性哈希）
- 优点：不需要像分布式算法那样挨个征求其他程序的意见了，所以相对而言，在令牌环算法里单个程序具有更高的通信效率；同时，在一个周期内，每个程序都能访问到临界资源，因此令牌环算法的公平性也很好，甚至更好；
- 缺点：不管环中的程序是否想要访问资源，都需要接收并传递令牌，所以也会带来一些无效通信(可以进行加权处理)；单点故障问题，可以这么改进：若某一个程序出现故障，则直接将令牌传递给故障程序的下一个程序，这样稳定性也挺好的
- 适用场景：系统规模小，系统中每个程序使用临界资源的频率高且使用时间比较短

2.分布式选举算法

分布式选举算法一：Bully算法
- 在所有活着的节点中，选取 ID 最大的节点作为主节点（比如 MongoDB 的副本集故障转移功能）
分布式选举算法二：Raft算法
- 核心思想是“少数服从多数”，获得投票最多的节点成为主。
- 多数派选主算法通常采用奇数节点，以防两个节点均获得一半投票，无法选出主节点。
- 集群中每个节点拥有 3 种角色（每一轮选举，每个节点只能投一次票）：
```
Leader：即主节点，同一时刻只有一个 Leader，负责协调和管理其他节点；

Candidate：即候选者，每一个节点都可以成为 Candidate，节点在该角色下才可以被选为新的 Leader；

Follower：Leader 的跟随者，不可以发起选举。
```
分布式选举算法三：ZAB算法
- ZAB 算法可以说是对 Raft 算法的改进，是为 ZooKeeper 实现分布式协调功能而设计的。
- 多数派选主算法通常采用奇数节点，以防两个节点均获得一半投票，无法选出主节点。
- 集群中每个节点拥有 3 种角色：
```
Leader，主节点；

Follower，跟随者节点；

Observer，观察者，无投票权。
```

3.分布式共识算法

分布式选举问题，其实就是传统的分布式共识方法，主要是基于多数投票策略实现的。

4.分布式事务算法

事务具备四大基本特征 ACID，分布式事务，就是在分布式系统中运行的事务，由多个本地事务组合而成。

但随着分布式系统规模不断扩大，复杂度急剧上升，达成强一致性所需时间周期较长，限定了复杂业务的处理；

为了适应复杂业务，出现了BASE理论，该理论的一个关键点就是采用最终一致性代替强一致性，算是ACID的弱化。

BASE理论：

由于CAP 不可能同时满足，而分区容错是对于分布式系统而言又是必须的，Base 理论是对 CAP 中一致性和可用性权衡的结果，是基于 CAP 定理逐步演化而来的，其核心思想是：既是无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

Basically Available(基本可用)
- 分布式系统在出现故障时，允许损失部分可用功能，保证核心功能可用。举个例子：电商网站交易付款出问题了，商品依然可以正常浏览。
Soft state（软状态）
- 由于不要求强一致性，所以BASE允许系统中存在中间状态（也叫软状态），这个状态不影响系统可用性，如订单的“支付中”、“数据同步中”等状态，待数据最终一致后状态改为“成功”状态。
Eventually consistent（最终一致性）
- 经过一段时间，所有节点数据都会达到一致。如订单中的“支付中”状态，最终会变成“支付成功”或者“支付失败”，使订单状态与实际交易结果达成一致，但需要一定时间的延迟和等待。

分布式事务主要是解决在分布式环境下，组合事务的一致性问题。实现分布式事务有以下 3 种基本方法：

基于 XA 协议的二阶段提交协议方法(强一致性)

XA协议可以分为两部分：事务管理器和本地资源管理器

算法详解（原理类似分布式互斥的集中式算法）

优点：
- 简单
缺点：
- 同步阻塞：二阶段提交算法在执行过程中，所有参与节点都是事务阻塞型的；也就是说，当本地资源管理器占有临界资源时，其他资源管理器如果要访问同一临界资源，会处于阻塞状态。
- 单点故障：事务管理器会有此问题
- 数据不一致：在提交阶段，当协调者向参与者发送 DoCommit 请求之后，如果发生了局部网络异常，或者在发送提交请求的过程中协调者发生了故障，就会导致只有一部分参与者接收到了提交请求并执行提交操作，但其他未接到提交请求的那部分参与者则无法执行事务提交，于是整个分布式系统便出现了数据不一致的问题。

事务管理器作为协调者，负责各个本地资源的提交和回滚；
资源管理器就是分布式事务的参与者，通常由数据库实现（实现XA接口）
二阶段提交协议（2PC）用于保证分布式系统中事务提交时的数据一致性，是 XA 在全局事务中用于协调多个资源的机制。

二阶段提交协议算法（2PC）：投票（voting）和提交（commit）
第一阶段：投票
协调者（Coordinator，即事务管理器）会向事务的参与者（Cohort，即本地资源管理器）发起执行操作的 CanCommit 请求，并等待参与者的响应；
参与者接收到请求后，会执行请求中的事务操作，记录日志信息但不提交；
待参与者执行成功，则向协调者发送“Yes”消息，表示同意操作；若不成功，则发送“No”消息，表示终止操作。

第二阶段：提交
当所有的参与者都返回了响应后（Yes 或 No 消息）后，系统进入了提交阶段；
在提交阶段，协调者会根据所有参与者返回的信息向参与者发送 DoCommit 或 DoAbort 指令：
若协调者收到的都是“Yes”消息，则向参与者发送“DoCommit”消息，参与者会完成剩余的操作并释放资源，然后向协调者返回“HaveCommitted”消息；
如果协调者收到的消息中包含“No”消息，则向所有参与者发送“DoAbort”消息，此时发送“Yes”的参与者则会根据之前执行操作时的回滚日志对操作进行回滚，然后所有参与者会向协调者发送“HaveCommitted”消息；
协调者接收到“HaveCommitted”消息，就意味着整个事务结束了。

alt

三阶段提交协议方法3PC(强一致性)

为了解决2PC的单点故障、部分数据不一致问题，引入了超时机制和准备阶段，成为3PC

算法详解

优点：
- 无单点故障问题、无同步阻塞问题、强一致性、同步执行
缺点：
- 参与者接收到doCommit消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行通信，参与者依然会进行事务的提交，会出现数据的不一致性（在 DoCommit 阶段，当参与者向协调者发送 Ack 消息后，如果长时间没有得到协调者的响应，在默认情况下，参与者会自动将超时的事务进行提交，不会像两阶段提交那样被阻塞住）
- 性能较低
- 系统吞吐量不高

协调者和参与者都引入超时机制；
如果协调者或参与者在规定的时间内没有接收到来自其他节点的响应，就会根据当前的状态选择提交或者终止整个事务。

在第一阶段和第二阶段中间引入了一个准备阶段，也就是在提交阶段之前，加入了一个预提交阶段；
在预提交阶段排除一些不一致的情况，保证在最后提交之前各参与节点的状态是一致的；
实现：把 2PC 的提交阶段一分为二，全部有CanCommit、PreCommit、DoCommit 三个阶段。

第一阶段：CanCommit，与2PC的第一阶段类似
协调者向参与者发送请求操作（CanCommit请求），询问参与者是否可以执行事务提交操作，然后等待参与者的响应；
参与者收到CanCommit 请求之后，回复 Yes，表示可以顺利执行事务，否则回复 No。

第二阶段：PreCommit
协调者根据参与者的回复情况，来决定是否可以进行 PreCommit 操作：
如果所有参与者回复的都是“Yes”，那么协调者就会执行事务的预执行：
1 发送预提交请求：协调者向参与者发送 PreCommit 请求，进入预提交阶段。
2 事务预提交：参与者接收到 PreCommit 请求后执行事务操作，并将 Undo 和 Redo信息记录到事务日志中。
3 响应反馈：如果参与者成功执行了事务操作，则返回 ACK 响应，同时开始等待最终指令。
如果任何一个参与者向协调者发送了“No”消息，或者等待超时之后，协调者都没有收到参与者的响应，就执行中断事务的操作：
1 发送中断请求：协调者向所有参与者发送“Abort”消息。
2 终断事务：参与者收到“Abort”消息之后，或超时后仍未收到协调者的消息，执行事务的终断操作。

第三阶段：DoCommit
根据 PreCommit 阶段协调者发送的消息，进入执行提交阶段或事务中断阶段：
执行提交阶段：
1 发送提交请求：协调者接收到所有参与者发送的 Ack 响应，从预提交状态进入到提交状态，并向所有参与者发送 DoCommit 消息。
2 事务提交：参与者接收到 DoCommit 消息之后，正式提交事务。完成事务提交之后，释放所有锁住的资源。
3 响应反馈：参与者提交完事务之后，向协调者发送 Ack 响应。
4 完成事务：协调者接收到所有参与者的 Ack 响应之后，完成事务。
事务中断阶段：
1 发送中断请求：协调者向所有参与者发送 Abort 请求。
2 事务回滚：参与者接收到 Abort 消息之后，利用其在 PreCommit 阶段记录的 Undo信息执行事务的回滚操作，并释放所有锁住的资源。
3 反馈结果：参与者完成事务回滚之后，向协调者发送 Ack 响应。
4 终断事务：协调者接收到参与者反馈的 Ack 消息之后，执行事务的终断，并结束事务。

alt

基于消息的最终一致性方法(最终一致性)
- 2PC和3PC有两个共同的缺点：
  - 需要锁定资源，降低系统性能
  - 没有解决数据不一致的问题
- 解决方案：引入MQ，用于在多个应用之间进行消息传递，将需要分布式处理的事务通过消息或者日志的方式异步执行，消息或日志可以存到本地文件、数据库或消息队列中，再通过业务规则进行失败重试。
总结对比2PC、3PC、MQ最终一致性