分布式系统中有关一致性的理解

首先什么是一致性？

一致性就是分布式系统中相互独立多个节点就某个值达成一致。

具体可分为强一致性和弱一致性。

强一致性：在任意时刻，所有节点中的数据是一样的。同一时间点，你在节点A中获取到key1的值与在节点B中获取到key1的值应该都是一样的。

弱一致性：不保证任意时刻所有节点数据一样，有很多不同实现。最广泛实现的是最终一致性。所谓最终一致性，就是不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。也可以简单的理解为在一段时间后，节点间的数据会最终达到一致状态。

分布式一致性的应用场景：

多节点提供读写服务，保证高可用性，可伸缩性（ZooKeeper，DNS，redis集群）

分布式系统面临的问题：

* 消息传递异步无序(asynchronous): 现实网络不是一个可靠的信道，存在消息延时、丢失，节点间消息传递做不到同步有序(synchronous)

* 节点宕机(fail-stop): 节点持续宕机，不会恢复

* 节点宕机恢复(fail-recover): 节点宕机一段时间后恢复，在分布式系统中最常见

* 网络分化(network partition): 网络链路出现问题，将N个节点隔离成多个部分

* 拜占庭将军问题(byzantine failure)[2]: 节点或宕机或逻辑失败，甚至不按套路出牌抛出干扰决议的信息

而需要满足一致性的分布式系统设计一般前提是无拜占庭将军问题（内网可信）

此处要提到分布式系统的基础理论，FLP定理，即当只在节点宕机的模型中，不能同时满足可用性和强一致性。它的另一个角度提法是CAP理论，即强一致性、可用性和分区容错性，只能保证其中2个。

保证一致性的协议有很多，包括2PC，3PC，Paxos，raft和PacificA。

2PC：2阶段锁提交协议，保证多个数据分片上操作的原子性。（分布式事务）

节点分为协调者（coordinator）和参与者（participat），执行分为2个阶段

阶段一：coordinator发起一个提议，分别问询各participant是否接受。Participate执行事务操作，将undo和redo信息写入事务日志，向coordinator回复yes或no

阶段二：coordinator根据participant的反馈，提交或中止事务，如果participant全部yes则提交，只要有一个participant回复no就中止。Participate根据coordinator的commit/Rollback信息正式提交或终止事务，并释放占用资源，返回ack。

优点：原理简单、实现方便

缺点：同步阻塞、单点问题、数据不一致（协调者在未发送完commit请求前崩溃或网络原因部分participate没收到commit，则部分participate无法进行事务提交）、太过保守（如果参与者在与协调者通信期间出现故障，协调者只能靠超时机制来判断是否需要中断事务）

3PC：3阶段锁提交协议，保证多个数据分片上操作的原子性。（分布式事务）

相对2PC，分为询问，预提交，提交3个阶段（解决阻塞，但还是可能数据不一致）

过程：coordinator接收完participant的反馈(vote)之后，进入阶段2，给各个participant发送准备提交(prepare to commit)指令。participant接到准备提交指令后可以锁资源，但要求相关操作必须可回滚。coordinator接收完确认(ACK)后进入阶段3、进行commit/abort，3PC的阶段3与2PC的阶段2无异。协调者备份(coordinator watchdog)、状态记录(logging)同样应用在3PC。

Paxos算法（解决单点问题）

Paxos算法是当前最重要的一致性算法，所有一致性算法都是paxos或是paxos的简化版。

Paxos算法解决多份相同数据就某个值达成一致。正确性证明的理论基础：任意2个法定集合（超过半数节点组成的集合）的交集不为空。

角色：

从提案到表决流程涉及到三个角色：

* Proposer：提案者，可能有多个，它门负责提出提案。

* Acceptor：接受人，一定要有多个，它们对指定提案进行表决，同意则接受提案，不同意则拒绝。

* Learner：学习人，收集每位Acceptor接受的提案，并根据少数服从多数的原则，形成最终提案。

实际上，分布式系统中一个组件可以对应一种或多种角色。

算法描述：

* 第一阶段（Prepare阶段）

Proposer：

* 选取提案编号n，并向大多数Acceptor发送携带编号n的prepare请求。

Acceptor：

* 如果收到的提案编号n比自己已经收到的编号都要大，则向Proposer承诺不再接收编号小于n的提案，如果之前接受过提案，则同时将接受的提案中编号最大的提案及其编号发给Proposer。

* 如果收到的提案编号n小于自己已经收到提案编号的最大值，则拒绝。

* 第二阶段（Accept阶段）

Proposer：

* 首先，对接收到响应，逐条处理：

* 如果接收到拒绝，则暂不处理。

* 如果接收到同意，同时还接收到Acceptor已经接受的提案，则记下该提案及编号。

* 处理完响应后，统计拒绝和同意个数：

* 如果大多数拒绝，则准备下次提案。

* 如果大多数同意，从这些Acceptor已经接受的提案中选取提案编号最大的提案作为自己的提案，没有则使用自己的提案，逐个向Acceptor发送Accept消息。

Acceptor：

* 如果收到的提案编号n小于自己已经收到最大提案编号，则拒绝。

* 如果收到的提案编号n等于自己已经收到最大提案编号，则接受该提案。

* 如果收到的提案编号n大于自己已经收到最大提案编号，则拒绝。

* 形成共识（与Prepare&Accept阶段并行）

Acceptor：

* 每当接受一个提案，则将该提案及编号发给Learner。

Learner：

* 记录每一个Acceptor当前接受的提案，一个Acceptor先后发来多个提案，则保留编号最大的提案。

* 统计每个提案被接受的Acceptor个数，如果超过半数，则形成共识。

Raft和PacificA是基于paxos的简化实现，更容易理解更容易实现。等看了再总结下

http://www.cnblogs.com/liulaoshi/p/7821339.html

参考文章：

https://segmentfault.com/a/1190000004474543

https://www.zhihu.com/question/19787937

http://www.cnblogs.com/bangerlee/p/5268485.html

http://www.voidcn.com/article/p-xvyhhccc-dm.html