十分钟搞定分布式一致性算法
前言
本文编写的目的：为了深入理解后期关于zookeeper的文章，本文这里对分布式一致性算法的由来以及要解决的问题做一个简述，更加深入的原理性东西后续将会以专辑的形式撰写。另该文比较长，建议收藏阅读
本文编写的顺序:从集中式演化到分布式--->分布式出现的一些问题--->如何解决这些问题(即最重要的一致性问题)---->事务(保证一致性的方法)---->从早期的ACID到CAP/BASE理论---->2pc/3pc----->Paxos算法
背景
20世纪60年代大型主机被发明出来以后，集中式的计算机系统架构成为了主流，其单机处理能力方面的优势非常明显，但从20世纪80年代之后，传统的集中式处理模式越来越不能满足人们的需求，同时集中式系统有明显的单点故障问题，从2008年开始，阿里开启了“去IOE”计划，后来逐渐的往分布式系统的方向发展。
分布式系统是一个硬件或软件组件分布在不同的网路计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。因此分布式系统具有以下几个特点：
分布性
多台计算机在空间上随意分布，同时分布情况也会随时变动
对等性
集群中的每个节点角色都是一样的，注意副本的概念
并发性
多个机器可能会同时操作一个数据库或存储系统，可能会引起数据不一致问题
缺乏全局时钟
分布式系统中的多个主机事件先后顺序很难界定
故障总发生
服务器宕机，网络拥堵和延迟
同时和分布式系统进行对比发现集中式系统具有以下几个特点:
部署结构简单
成本高
单点故障
大型主机的性能扩展受限于摩尔定律
注意：这里要区分集群和分布式的概念，集群是指大量的机器做同一件事情；分布式是指每台机器都有不同的角色，做不同的事情
分布式异常问题
分布式系统体系结构从出现到现在仍有很多的问题，这里列出一些典型的问题
通信异常
从集中式向分布式演变，必然会引入网络因素，由于网络的不可靠性，必然会在分布式节点之间出现网络 异常的情况
网络分区
网络分区也就是常说的脑裂，即出现多个局部小集群，每个局部网络可以互相通信
三态
三态指的是三种状态，即成功、失败、超时；在集中式系统中只有成功和失败，而超时是由于分布式系统中会出现网络异常才会有的状态
节点故障
分布式节点总会出现宕机或者僵死现象
数据丢失
对于有状态的节点，数据丢失意味着状态丢失，通常只能从其他节点读取，恢复存储的状态；通常针对这种问题，通过引入副本机制就可以解决
衡量分布式系统的性能
性能
即系统吞吐能力、响应延迟、QPS等
可用性
可扩展性
一致性
一致性模型
分布式环境下，一致性指的是数据在多个副本之间是否能够保持一致的特性，对于一个将数据副本分布在不同节点的系统上来说，如果对一个节点的数据进行了更新操作，却没有使得第二个节点上的数据得到响应的更新，那么此时在读取第二个节点的数据时，将会出现脏读现象(即数据不一致).那么一致性又分为以下几种：
强一致性
即写操作完成后，读操作一定能够读到最新的数据，在分布式场景下，很难实现；Paxos、Quorum机制、ZAB协议能够实现,后面会对这几种协议算法进行讲解。
弱一致性
不承诺立即可以读到写入的值，也不承诺多久后能达到数据一致，但会尽可能保证某个时间级别后，数据达到一致状态
读写一致性
用户读取自己写入结果的一致性，保证用户能够第一时间看到自己更新的内容;这种实现的解决方案有:
一种方案是对于特定的内容，我们去主库查询
设置一个更新时间窗口，在刚更新的一段时间内，默认去主库读取，过了这个窗口后，挑选最近更新的从库进行读取
直接记录用户更新的时间戳，在请求的时候把这个时间戳带上，凡是最后更新时间小于这个时间戳的从库都不响应
单调读一致性
本地读到的数据不比上次读到的旧，多次刷新返回旧数据会出现灵异事件，对于这种情况可以通过hash映射到同一台机器上
因果一致性
如果节点A在更新完某个数据后通知了节点B，那么节点B之后对该数据的访问和修改基于A更新的值。此时，和节点A无因果关系的节点C的数据访问则没有这样的限制
最终一致性
所有分布式一致性模型中最弱的。不考虑中间的任何状态，只保证经过一段时间之后，最终系统内数据正确，最大程度上保证了系统的并发能力，因此在高并发场景下，也是使用最广的一致性模型
事务
事务是可以保证一致性的方法，在集中式系统架构中可以通过ACID的方式实现，在早期分布式架构，是通过CAP/BASE理论来实现的，后来又演化出了2pc/3pc,以及Paxos、Raft等算法来保证一致性。
事务是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元。(概念性的东西直接略过～)
ACID
Atomicity原子性
简单说就是一个操作序列要么全部成功执行，要么全部不执行
Consistency一致性
也就是说数据从一个一致性状态转变到另一个一致性状态，中间不能存在不一致的状态
Isolation隔离性
在并发环境下，一个事务的执行不能被其他事务所干扰，每个事务都有各自独立完整的数据空间，也就是说一个事务内部的操作以及数据的使用对其他并发的事务都是隔离的。
根据隔离性的强度分为4个级别:
未授权读取(读未提交)
这是隔离级别最低的。比如说事务A和事务B同时进行，事务A在整个执行的过程中，会将某个数据值从1开始做加法操作直到变成10之后提交事务，而此时事务B能够看到事务A操作这个数据的所有变化(即从1到10的变化)，而这一系列中间值的读取就是未授权读取
授权读取(读已提交)
只允许读取已经被提交的数据而且不可重复读。比如说事务A和事务B同时进行，同样进行加法操作(从1到10),那么此时事务B是无法看到所有的中间值，只能看到最终的10.
可重复读取
在保证事务处理的过程中，多次读取同一个数据时候，它的值和事务开始时刻是一致的，可能会出现幻影数据（即同一个事务操作，在前后两个时间段内执行对同一个数据项进行读取，可能会得到不同的结果），还是拿上面的例子，事务B在第一次事务读取的时候，始终读到的是1，但是到第二次事务读取的时候就会变成了10（因为这个时候事务A已经完成了）
串行化
即所有的事务串行执行
Durability持久性
即一个事务一旦提交，对应数据的状态变更就是永久性的
CAP
Consistency一致性
数据在多个副本之间是否能够保持一致的特性。
Avaliabilty可用性
指系统提供的服务必须一直处于可用的状态，对于用户的操作总能给在有限的时间内返回结果，这里要注意下是在有限的时间内哦
Partition tolerance分区容错性
即分布式系统在遇到网络分区的时候，仍然能够保证对外提供满足一致性和可用性的服务，除非整个网络发生了故障
注意：分布式系统无法满足上面三个特性，但是一定要有分布容错性，即P，C和A根据需求进行衡量
BASE
Basically Avaliable 基本可用
即分布式系统中在出现故障的时候，允许损失部分可用性，比如响应时间上的损失或者功能上的损失，例如双11的时候，可以将一些无关紧要的服务进行降级
Soft state软状态
即允许系统中的数据存在中间状态，且中间状态的存在不会影响系统的整个可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程出现延时
Eventually consistent最终一致性
强调的是系统中所有的数据副本，在经过一段时间的同步后，最终达到一个一致的状态
分布式一致性协议算法
2pc
即二阶段提交，绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理。即将事务的提交过程分为了两个阶段来处理
阶段一：请求/表决阶段
1.事务询问
协调者向参与者发起事务内容，询问是否可以执行事务操作，并等待响应
2.执行事务
各参与者执行事务操作，并将undo和redo信息记录到事务日志中
3.各参与者向协调者反馈事务询问的响应
协调者根据所有的参与者是否都响应了yes或者no来进行表决事务是否执行或者不执行
阶段二：提交/执行/回滚阶段
情况1.执行事务提交
1.发起提交请求
协调者向参与者发起commit请求
2.事务提交
参与者收到commit请求后，正式执行事务提交，完成之后释放资源
3.反馈事务提交结果
参与者完成事务之后，向协调者发送ack消息
4.完成事务
协调者收到所有参与者返回的ack消息，完成事务
情况2.中断事务
1.发送回滚请求
协调者向参与者发起rollback请求
2.事务回滚
参与者收到rollback请求后，利用undo信息执行事务回滚操作,完成之后释放资源
3.反馈事务回滚结果
参与者完成事务之后，向协调者发送ack
4.中断事务
协调者接收到所有参与者反馈的ack,完成事务中断
二阶段提交的问题
1.性能问题
从流程上看，在执行过程中节点都处于阻塞状态。各个操作数据库的节点都占用数据库资源，只有当所有节点准备完毕后，事务协调者才会通知进行全局commit/rollback，参与者进行本地事务commit/rollback之后才会释放资源，对性能影响较大
2.单点故障问题
事务协调者是整个分布式事务的核心，一旦事务协调者出现故障，会导致参与者收不到commit/rollback的通知，从而导致参与者节点一直处于事务无法完成的中间状态
3.数据不一致
在第二阶段的时候，如果发生局部网络问题，一部分事务参与者收不到commit/rollback消息，就会导致节点间数据不一致
4.太多保守
必须 收到所有参与的正反馈才提交事务如果有任意一个事务参与者的响应没有收到，则整个事务失败回滚
3pc
基于2pc出现的一些问题，3pc进行了改进，也就是三阶段提交，将2pc的第二个阶段进行了一分为二，形成了CanCommit（提交询问）、Precommit（预提交）、doCommit阶段(最终提交)三个阶段；其实3pc和2pc的不同点在于3pc增加了超时机制。
阶段1:CanCommit(提交询问)
协调者向所有参与者发送一个请求，询问是否可以执行事务提交操作，然后开始等待所有响应者的响应
正常情况下，所有参与者会反馈yes，然后进入预备状态，否则反馈No
2.各参与者向协调者反馈事务询问的响应
1.事务询问
阶段2:PreCommit(预提交)
情况1:执行事务预提交(即所有参与者都响应yes)
1.发起预提交请求
协调者向所有参与者发出preCommit请求，并进入准备阶段
2.事务预提交
参与者接收到preCommit请求后，执行事务操作，然后将undo和redo信息记录到事务日志中
3.各参与者向协调者反馈事务执行的响应
情况2:中断事务(任何一个参与者反馈no或者超时就会中断事务)
1.发送中断请求
2.中断事务
阶段3:doCommit(最终提交)
情况1:执行提交
1.发送提交请求
2.事务提交
3.反馈事务提交结果
4.完成事务
情况2:中断事务
1.发送中断请求
2.事务回滚
3.反馈事务回滚结果
4.中断事务
3pc特点
1.降低了参与者阻塞范围,增加了超时自动处理的机制
2.能够在出现单点故障后继续保持一致
3.网络分区会出现不一致的问题
即参与者接收到了preCommit消息后，出现了网络分区，即协调者和参与者无法进行正常通信，这个时候该参与者依然会进行事务的提交，就会出现数据不一致的情况
Paxos
Paxos算法要解决的问题就是如何保证数据一致性，这是一种基于消息传递且具有高度容错特的一致性算法
首先要引入拜占庭问题
拜占庭问题：即不同军队的将军之间必须制定一个统一的行动计划，但是在地理上都是分隔开来的，只能依靠通讯员进行通信，但是通讯员可能会存在叛徒，对消息进行篡改，从而欺骗将军。
这种消息篡改的情况在同一个局域网内几乎不会出现，或者简单通过校验算法进行避免。但是在实际工程实践中，可以假设不存在拜占庭问题，基于这种假设如何保证一致性呢？这个时候又引入Paxos的故事
古希腊有一个Paxos小岛，岛上采用会议的形式来通过法令，议会上的议员通过信使来传递消息，注意信使和议员都是兼职的，有可能随时会离开议会，而且信使有可能会重复传递消息，也有可能一去不返。那么在这种情况下议会协议也要保证法令能够正确选举出来，而且不会产生冲突。
根据这个故事也就衍生出了Paxos算法，该算法有3个角色：
1.Proposer（提议者，用来发起提案的，相当于zk中的leader角色）
2.Acceptor(接受者，可以接受或拒绝提案，相当于zk中的follower角色)
3.Learner(学习者，学习被选定的提案，相当于zk中的observer角色)
注意这里讲解的是Basic Paxos，基于Baisc Paxos演化出了Multi Paxos,这里不做过多讲解，有兴趣的同学可自行查阅
大致流程就是首先选举出一个Leader，也就是Proposer用来发起提案，然后发送给所有的Acceptor来进行投票，当超过一半投通过票的时候，该提案也就通过了，那么这个时候Proposer会将该提案进行同步所有机器进行学习
也就是说Paxos是基于议会制，以少数服从多数的核心思想来保证一致性的
Raft
该算法不做过多讲解，想要了解，请查看http://thesecretlivesofdata.com/raft/网址
Raft算法是一个分布式共识算法，有三个角色
1.Leader
2.follower
如果follower接收不到leader的心跳时，会变为candidate(这里会有150s~300s的等待时间)，发起投票是否成为新的leader
3.candidate(候选人)
核心思想：少数服从多数！
ZAB协议
zookeeper是基于该协议(zookeeper原子广播协议)实现的。这里只做简单介绍，该协议比较重要，后面会和zookeeper相关文章结合单独进行讲解！
该协议有两种模式:
1.奔溃恢复
2.消息广播
它和Paxos的区别联系在于:
1.都存在类似于Leader角色，负责协调多个Follower进程的运行
2.Leader进程都会等待超过半数的Follower做出正确反馈后，才会将一个提案进行提交
3.zab协议中，每个proposal都包含一个epoch值,用了代表当前Leader周期；Paxos中也存在同样的标识，名字为Ballot
4.zab协议主要用于构建一个高可用的分布数数据主备系统
5.Paxos算法主要用于构建一个分布式的一致性状态机系统