distribute/distribute.md
# 分布式系统一致性
- [分布式系统一致性](#)
- [1. 一致性标准](#1)
- [2. 一致性理论](#2)
- [2.1 CAP](#21-cap)
- [2.2 BASE](#22-base)
- [3. 数据分布与负载均衡](#3)
- [3.1 哈希分布](#31)
- [3.2 顺序分布](#32)
- [3.3 数据迁移](#33)
- [4. 复制](#4)
- [4.1 强同步复制](#41)
- [4.2 异步复制](#42)
- [5. 分布式协议](#5)
- [5.1 两阶段提交协议](#51)
- [5.2 三阶段提交协议](#52)
- [5.3 Paxos协议](#53-paxos)
- [5.4 * Quorum NRW](#54-quorum-nrw)
- [5.5 ★ Raft](#55--raft)
- [5.5.1 leader election](#551-leader-election)
- [5.5.2 log replication](#552-log-replication)
- [6. 解决方案 ( ★分布式事务中保持数据一致性 )](#6)
- [MQ实现二阶段提交](#mq)
- [上游应用执行业务并发送 MQ 消息（第一阶段）](#mq)
- [下游应用监听 MQ 消息并执行业务（第二阶段）](#mq)
- [TCC](#tcc)
## 1. 一致性标准
- 强一致性：假如A先写入一个值到存储系统，存储系统能够保证后续ABC读取操作都将返回最新值。
- 弱一致性：假如A先写入一个值到存储系统，系统不能保证ABC的读取操作能否读取到最新值。
- 最终一致性：~，后续没有写操作更新同样的值，ABC的读取操作最终都会读取到A写入的最新值。从A写入，到ABC读取到最新值的这段时间，称为“不一致性窗口”。
## 2. 一致性理论
### 2.1 CAP
CAP 是指在一个分布式系统下， 包含三个要素：Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），并且 三者不可得兼。
* C：Consistency，一致性，所有数据变动都是同步的。
* A：Availability，可用性，即在可以接受的时间范围内正确地响应用户请求。
* P：Partition tolerance，分区容错性，即某节点或网络分区故障时，系统仍能够提供满足一致性和可用性的服务。
关系型数据库 单节点 保证了数据强一致性（C）和可用性（A），但是却无法保证分区容错性（P）。
然而在分布式系统下，为了保证模块的分区容错性（P），只能在数据强一致性（C）和可用性（A）之间做平衡。具体表现为**在一定时间内，可能模块之间数据是不一致的，但是通过自动或手动补偿后能够达到最终的一致**。
### 2.2 BASE
BASE 理论主要是解决 CAP 理论中分布式系统的可用性和一致性不可兼得的问题。BASE 理论包含以下三个要素：
* BA：Basically Available，基本可用。
* S：Soft State，软状态，状态可以有一段时间不同步。
* E：Eventually Consistent，最终一致，最终数据是一致的就可以了，而不是时时保持强一致。
BASE 模型与 ACID 不同，满足 CAP 理论，通过牺牲强一致性来保证系统可用性。由于牺牲了强一致性，系统在处理请求的过程中，数据可以存在短时的不一致。
系统在处理业务时，**记录每一步的临时状态**。`当出现异常时，根据状态判断是否继续处理请求或者退回原始状态，从而达到数据的最终一致。`
## 3. 数据分布与负载均衡
负载的衡量有很多因素，load值，cpu，内存，磁盘，网络等。
### 3.1 哈希分布
一致哈希的便利在于，集群数量变化时可以方便的扩容和数据迁移（只影响到相邻结点）。另一个特点是，相同id请求总是发到同一台服务器，这样同一个用户id的数据不会被散列到不同服务器，但缺点也是在用户数据量大的时候可能造成过载（还有种说法是所有数据限定在同一个存储节点，无法发挥分布式多机并行处理的能力）。对于大用户，可以将它的数据再进行拆分处理。
数据迁移过程中的负载问题，5.1节
### 3.2 顺序分布
哈希分布破坏了数据的有序性，只能支持随机读取，不能支持顺序扫描。
顺序分布就是将大表划分为连续的小表，与B+树结构类似
### 3.3 数据迁移
负载均衡做？不是吧！
假设数据分片D有两个副本D1D2分别在结点A1A2，D1为主副本，D2为从副本，迁移D1到其他结点的过程为：
1. 将数据分片D的读写服务有A1切换到A2，D2变成主副本。
2. 选择一个新的结点B，**从A2结点获取D2的数据**并与之保持同步。
3. 从A1删除D1副本。
## 4. 复制
复制协议分为两种，强同步和异步复制。**两者的区别在于，是否需要同步到备副本才可以返回成功**。当系统出现故障时，分布式系统需要将服务自动切换到备副本，实现自动容错。
强同步复制能保证一致性，但是当`备副本`出现故障时，会阻塞存储系统的正常写服务，系统的整体可用性受到影响。
异步复制可用性好，但是当`主副本`出现故障时会出现数据丢失的可能性。
### 4.1 强同步复制
客户端将**写请求**发送给主副本，主副本将写请求通过同步commit log来复制到其他副本，备副本根据日志进行操作，完成后通知主副本。然后主副本修改本机，等所有操作都完成后通知客户端些完成。
备副本的个数可能大于1个，实现强同步协议时，主复本可以将操作日志并发地发给所有副本并等待回复，只要有一个备副本返回成功就可以继续操作并恢复客户端操作成功。
主复本出现故障时，至少有一个备副本可用。
### 4.2 异步复制
异步模式下，主副本不需要等待备副本的回应，本地修改成功后就可以通知客户端操作成功。
## 5. 分布式协议
* 分布式事务
一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果，他也就不知道本次事务到底应该commit还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。
### 5.1 两阶段提交协议
二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
所谓的两个阶段是指：第一阶段：`准备阶段(投票阶段)`和第二阶段：`提交阶段（执行阶段）`
* 提交请求阶段(或者叫做投票阶段)
1.事务协调者(事务管理器)给每个参与者(cohorts, 资源管理器)发送Prepare消息，等待直到收到所有cohorts的回复。
2.cohorts在本地节点执行事务(之后协调者会要求提交这个事务)，写本地的redo和undo日志。(**会对涉及到的资源加锁，直到第二步完成才释放锁资源**)
3.每一个cohorts，如果执行成功，回复一个agreement消息(假如cohorts同意执行commit)；如果执行失败，回复一个abort消息。(两阶段提交协议)。
* 提交阶段(或者叫完成阶段)
成功
如果协调者接收到所有参与者发送回来的agreement消息：
1.协调者发送一个commit消息给所有的cohorts
2.每一个参与者完成commit操作，(两阶段提交协议)**释放所有事务处理过程中使用的锁资源**
3.每一个参与者回复一个acknowledgment给协调者
4.协调者在收到所有acknowledgment消息之后完成整个操作
失败
如果任何一个参与者在提交请求阶段回复abort消息给协调者:
1.协调者回复一个rollback消息给所有的cohorts
2.每一个参与者执行本地事务的undo操作(根据undo日志记录)，并且释放事务执行过程中使用的资源和锁
3.每一个参与者给协调者回复acknowledgement消息(两阶段提交协议)。
4.协调者在接收到所有的参与者的acknowledgement消息之后执行事务undo操作
两阶段提交协议最大的缺点是：它是一个阻塞协议。当一个节点在等待回复消息时进入阻塞状态。其他需要这些资源的处理事务需要等待。如果协调者挂掉，cohorts将永远不能结束它们的事务
### 5.2 三阶段提交协议
与两阶段提交不同的是，三阶段提交有两个改动点。
1、引入超时机制。**同时在协调者和参与者中都引入超时机制。**
2、在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。
分为 CanCommit、PreCommit、DoCommit 三个阶段
* CanCommit阶段
1.事务询问 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
2.响应反馈 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态，否则反馈No。
* PreCommit阶段
假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。
1.发送预提交请求 协调者向参与者发送PreCommit请求，并进入Prepared阶段。
2.事务预提交 参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
3.响应反馈 如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。
假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
1.发送中断请求 协调者向所有参与者发送abort请求。
2.中断事务 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。
* doCommit阶段
该阶段进行真正的事务提交，也可以分为以下两种情况。
执行提交
1.发送提交请求 协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
2.事务提交 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
3.响应反馈 事务提交完之后，向协调者发送Ack响应。
4.完成事务 协调者接收到所有参与者的ack响应之后，完成事务。
中断事务 协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。
1.发送中断请求 协调者向所有参与者发送abort请求。
2.事务回滚 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
3.反馈结果 参与者完成事务回滚之后，向协调者发送ACK消息。
4.中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断。
在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。 ）
* 2PC与3PC的区别
相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，**因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。** 但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
### 5.3 Paxos协议
Paxos协议用于在主节点发生故障时，选取新的结点。
在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。
一般的NoSQL都会通过数据复制的形式保证其可用性，但客户端对多数据进行操作时，可能会有很多对同一数据的操作发送的某一台或几台Server，有可能执行：Insert、Update A、Update B....Update N，就一次Insert连续多次Update，最终复制Server上也必须执行这一的更新操作，如果因为线程池、网络、Server资源等原因导致各复制Server接收到的更新顺序不一致，这样的复制数据就失去了意义，如果在金融领域甚至会造成严重的后果。
http://blog.csdn.net/dellme99/article/details/14162159
### 5.4 * Quorum NRW
N表示数据所具有的副本数。
R表示完成读操作所需要读取的最小副本数，即一次读操作所需参与的最小节点数目。
W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。
该策略中，只需要保证R + W>N，就可以保证强一致性。 如果R + W ≤ N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。
假设N=5， 如果R=1， 那么W必须是5. 所以就是写入所有的节点是全部节点，那么读取任何一个节点就可以最新的数据。 有点就是像读写锁了。
如果R=5， 那么W只要是1就可以了。 那么写的效率就非常高。 读取的效率比较低。
如果R=N/2+1， W=N/2， 读写之间为达到某个平衡。 是不错的策略。兼顾了性能和可用性，Dynamo系统的默认设置就是这种。
### 5.5 ★ Raft
Raft是一个用于日志复制，同步的一致性算法，是Paxos的简易版本。每个结点分为leader，follower和candidate三种状态
当集群中有leader时，后续操作类似于二阶段、三阶段提交。其他结点是follower，follower会通过心跳与leader保持联系。
#### 5.5.1 leader election
如果leader挂了，那么raft就起作用了，用来选取下一个leader，具体过程如下：
1. 剩余的follower会通过心跳发现leader挂了，但是谁先发现leader挂了，谁就先成为candidate。（**这一等待过程称为election timeout，时间随机为150ms到300ms。率先成为candidate的结点会进入下一轮term投票，`term表示leader的任期`**）
2. candidate会先投自己一票，`并把自己的term+1`，然后给其他结点发送vote request，`带有自己更新后的term`，此时cadidate也会重置election timeout（其他节点如果是follwer状态，**且request的term大于自己的term，才会返回赞成票，同时将自己的term+1，并重置election timeout**）
3. 如果cadidate在timeout之前收到的投票数超过一半时，该candidate就自动成为leader，成为leader后会给其他结点以心跳形式发送带有附加信息的消息，其他结点收到心跳后就知道新的leader产生了，自己都变成follower。**follwer每次收到心跳都会重置heartbeat timeout，并回复心跳消息**
4. 如果leader挂了，那么就会重复1的过程。
5. 如果两个follower同时发现leader挂了，都成了candidate，并发送各自的vote request，由于各节点收发速率不同，那么可能出现两个candidate同票，之后大家随机休息一阵，进行下一轮选举。谁先从休息中恢复就可以先发起投票，然后进而回到第一步开始，成为leader。
#### 5.5.2 log replication
leader收到客户端请求时，会添加到自己的log中，并向其他follower发送append entries，follower接收后判断是否满足条件，满足条件就将其添加到本地log中，并回复leader成功response。leader在收到大多数成功的response后就把log提交，表示请求被raft系统接受。
具体参考：
1. [raft动画理解](http://thesecretlivesofdata.com/raft/)
2. [raft中的一些问题](https://www.jianshu.com/p/4711c4c32aab)
## 6. 解决方案 ( ★分布式事务中保持数据一致性 )
### MQ实现二阶段提交
目前主流的一致性解决方案都是利用MQ来实现二阶段提交（事务性）。
涉及三个模块：
* 上游应用，执行业务并发送 MQ 消息。
* 可靠消息服务和 MQ 消息组件，协调上下游消息的传递，并确保上下游数据的一致性。
* 下游应用，监听 MQ 的消息并执行自身业务。
#### 上游应用执行业务并发送 MQ 消息（第一阶段）
上游应用将本地业务执行和消息发送绑定在同一个本地事务中，保证要么本地操作成功并发送 MQ 消息，要么两步操作都失败并回滚。
1. 上游应用发送待确认消息到可靠消息系统
2. 可靠消息系统保存`待确认`消息并返回
3. 上游应用执行本地业务
4. 上游应用通知可靠消息系统确认业务已执行并发送消息。
5. 可靠消息系统修改消息状态为`发送状态（已发送）`并将消息投递到 MQ 中间件。
可靠消系统一开始为`待确认`状态，当步骤1-3出错时，上游应用整个事务回退，不影响一致性。而当4、5发生错误时，会出现不一致性，需要做如下处理：
1. 可靠消息服务定时监听消息的状态，如果存在状态为`待确认并且超时`的消息，则表示上游应用和可靠消息交互中的步骤 4 或者 5 出现异常。
2. 向上游应用查询业务执行的情况
3. 业务未执行，则删除该消息，保证业务和可靠消息服务的一致性。业务已执行，则修改消息状态为已发送，并发送消息到 MQ 组件。
#### 下游应用监听 MQ 消息并执行业务（第二阶段）
下游应用监听 MQ 消息并执行业务，并且将消息的消费结果通知可靠消息服务。
可靠消息的状态需要和下游应用的业务执行保持一致，可靠消息状态不是已完成时，确保下游应用未执行，可靠消息状态是已完成时，确保下游应用已执行。
1. 下游应用监听 MQ 消息组件并获取消息
2. 下游应用根据 MQ 消息体信息处理本地业务
3. 下游应用向 MQ 组件自动发送 ACK 确认消息被消费
4. 下游应用通知可靠消息系统消息被成功消费，可靠消息将该消息状态更改为`已完成`。
步骤4发生错误时，会造成不一致性，此时可靠消息服务中存在消息状态为`已发送并且超时`的消息，执行以下操作：
1. 可靠消息服务定时查询状态为已发送并超时的消息
2. 可靠消息将消息重新投递到 MQ 组件中
3. **下游应用监听消息，在满足幂等性的条件下，重新执行业务。**
4. 下游应用通知可靠消息服务该消息已经成功消费。
此外还有 **TCC和最大努力通知方案**。[ref](https://mp.weixin.qq.com/s/i1pnrORZzec6Zp0tmljD8Q)
### TCC
tcc模式中，活动管理器就等同于对外接口，先调用主服务，主服务调用从服务的try；如果从服务都try成功，那么主服务再执行业务操作，再将从服务接口返回给活动管理器，后续由活动管理器来调用从服务的执行或回滚。
但是细究可以发现，该模式适合有主从业务等级的划分，因为从服务的接口是由主服务来获取，但实际中可能主服务的调用在从服务之后，而且不一定有主从关系。再者活动管理器可以直接就知晓各服务接口，然后顺序调用，只是每个服务 **都需要有do和cancel接口**。
---
具体实践可以参考[RAS-MSG](https://github.com/yjjnls/RAS-MSG)