随着计算机系统的规模变大，将所有的业务部署在一台机器上已经不能满足当今计算机系统了。微型机的出现及互联网的不断发展也促使了大量灵活多变的系统架构出现，尤其是分布式处理方式越来越受到工业界的青睐，计算机系统正在从集中式走向分布式架构。
集中式到分布式
由于大型机成本较高，也存在单点问题，无法满足互联网应用爆炸式的增长需求。
集中式的特点:（1）部署简单；（2）单点故障
分布式特点:（1）分布性 （2）对等性（节点没有主/从之分）（3）并发性（多个节点并发操作共享资源）（4）缺乏全局时钟（无法确定事件先后顺序） （5）故障总会发生
分布式环境的常见问题:（1）通信异常（延迟）（2）网络分区（脑裂：只有部分节点能正常通信，这些小集群完成整个系统才能完成的任务） （3）三态（成功、失败、超时）（4）节点故障
分布式事务
ACID
事务是对系统中数据进行访问与更新操作组成的一个程序执行逻辑单元，事务具有4个特征：原子性，一致性，隔离性，持久性（ACID）。
原子性
事务必须是原子操作单元，各项操作要么全部执行成功，要么全部不执行；任何一项操作失败都会导致整个事务回滚，全部操作成功才意味着事务的成功完成。
一致性
事务的执行不能破坏系统的完整性和一致性，事务在执行前后系统都必须处于一致性状态，即事务执行使得系统从一个一致性状态转变到另一个一致性状态。若事务执行发生故障后，只有一部分操作修改写入数据库，那数据库就处于不一致性的状态。
隔离性 并发的事务是相互隔离的，一个事务不能被其他事务干扰，并发执行的事务又各自完整的数据空间，事务之间相互不干扰。SQL隔离性（未授权读、授权读、可重复读、串行化）
持久性
事务一旦提交，它的修改就应该是永久性的，即使系统崩溃后，重新修复也能恢复到事务提交成功后的状态
在单机上实现事务比较简单，但在分布式系统中，分布式事务由多个分布式操作序列组成，而实现分布式事务的ACID更为复杂（通信、多节点、宕机）。当追求分布式系统严格一致性时，系统的可用性会收到影响，即可用性和一致性永远无法存在一个两全齐美的方案，折中考虑出现了CAP和BASE分布式理论。
CAP
CAP理论：分布式系统不可能同时满足一致性，可用性和分区容错性，这三个最多只能满足其中二项
一致性：数据在多个副本之间保持一致性（强一致性）（放弃C，放弃强一致性，保留最终一致性，时间窗口，最终达到一致性状态）
可用性：分布式系统提供的服务必须一致处于可用的状态，对每一个用户的请求总是在有限的时间内返回结果（有限时间、结果）（放弃A，在故障期间无法提供服务）
分区容错性：分布式系统在遇到任何网络分区故障时仍能对外提供一致性和可用性的服务，除非整个网络环境发生了故障 （放弃P意味着单机部署）
在分布式系统中，分区容错性是必须解决的问题，所以往往需要在可用性和一致性之间寻求平衡。
BASE
BASE理论：基本可用、软状态、最终一致性。BASE是对CAP一致性和可用性权衡的结果，其核心思想是分布式系统无法做到强一致性，每个应用可以根据自身业务特点来使系统达到最终一致性
基本可用：分布式系统在出现故障时，允许损失部分可用性（并不等价于不可用，如响应时间损失、服务降级）
弱状态：系统中允许存在中间状态，该状态不会影响系统的整体可用性，即允许存在一定的延迟
最终一致性：经过一段时间的同步后，系统最终能够达到一致性的状态，不需要实时保证一致性，是一种弱一致性
最终一致性的变种：因果一致性、读己之所写、回话一致性、单调读一致性、单调写一致性
一致性协议
在分布式系统进行架构设计时，往往在可用性与一致性之间反复权衡，于是就产生了一系列的分布式一致性协议，经典的一致性协议如下。
2PC
在分布式系统时，每一个节点都知道自己的事务是否成功，但是不知道其他节点的事务执行情况，因此为了保证事务的ACID，需要引入一个协调者来统一调度所有节点。协调者调度参与者的行为，并最终决定参与者是否把事务真正提交。基于这个思想出现了2PC、3PC协议。
2PC：二阶段提交，常用于数据库领域，绝大数的关系型数据库都采用了二阶段提交协议。2PC是一种强一致性协议，被广泛应用于分布式系统中。
执行流程
提交事务请求
（1）事务询问：协调者向参与者发送事务内容，咨询是否可以执行事务，等待参与者响应
（2）执行事务：参与者执行事务操作，并将undo与redo记录事务日志
（3）参与者反馈事务响应：若参与者成功执行事务则反馈yes给协调者，若执行失败则反馈no
执行事务提交
若协调者从参与者的反馈都是yes，则执行事务提交
（1）执行事务提交：向所有参与者发出commit请求
（2）事务提交：参与者接受commit请求，提交事务并释放资源
（3）反馈事务执行结果：参与者执行事务后，返回ack给协调者
（4）完成事务：协调者收到所有参与者的ack后，完成事务
中断事务
若任何一个参与者反馈了no，或者超时无响应，那么就会中断事务
（1）发送回滚请求：协调者发出rollback请求
（2）事务回滚：参与者收到rollback后，利用日志中的undo信息来回滚，并释放资源
（3）反馈结果：参与者回滚后向协调者发出ack消息
（4）中断事务：协调者收到所有参与者的ack后完成事务中断
二阶段提交将分布式事务执行分成投票和执行两个阶段，即先尝试后提交处理方式，因此它是一个强一致性的协议。
优缺点
优点：实现简单
缺点：
（1）同步阻塞：参与事务的逻辑都处于阻塞状态，无法进行其他任何操作，影响分布式系统性能
（2）单点问题：协调者一旦出现问题，事务将会失败
（3）数据不一致：若协调者发送commit后挂掉，只有部分参与者收到了消息，则导致了数据不一致现象
（4）过于保守：任何一个节点的失败都导致了整个事务的失败
3PC
三阶段提交是对二阶段提交的改进，将二阶段的“提交事务请求”拆分成2个阶段，由CanCommit、PreCommit、DoCommit三个阶段组成的事务处理协议。
执行阶段
CanCommit
（1）事务询问：协调者向所有参与者发送CanCommit请求，询问是否可以执行事务提交操作，等待响应
（2）参与者反馈询问：参与者收到请求后，若正常情况反馈yes，进入预备状态，否则有问题返回no
PreCommit
协调者根据参与者的反馈情况来决定是否可以进行事务的PreCommit操作
（1）执行事务提交
若协调者收到的都是yes，就会执行事务预提交
发送预提交请求：协调者PreCommit请求进入Prepared阶段
事务预提交：参与者收到PreCommit后执行事务操作，记录undo、redo到事务日志
反馈：参与者反馈ack给协调者
（2）中断事务:若任何一个参与者反馈了no或超市，协调者将会中断事务
发送中断请求：发送abort请求
中断事务：无论收到了abort还是等待协调者超时，参与者都将中断事务
DoCommit
（1）执行提交
发送提交请求:协调者收到所有的ack响应后，他将从预提交转变到提交状态，并发送DoCommit请求
事务提交：参与者收到DoCommit请求后，执行事务提交操作，释放资源
反馈：参与者提交事务后，返回ack;协调者收到ack后，完成事务
（2）中断事务：协调者收到任何一个no
发送中断请求：发送abort
事务回滚：参与者收到abort后利用undo来执行回滚操作，并释放资源
反馈：事务回滚后，向协调者反馈ack
中断事务：协调者收到ack后中断事务
在进入阶段三后，若协调者挂掉或者协调者与参与者通信故障，都导致DoCommit或abort请求无发送到，在超时后参与者都会提交事务
优缺点
优点：降低了阻塞范围
缺点：第三阶段无法收到DoCommit请求后，参与者继续提交事务，引发数据不一致性
Paxos
Paxos是一种基于消息传递且具有高度容错性的一致性算法，它主要解决的问题是在发送各种异常的分布式系统中，快速正确地在集群内部达成一致。
在Paxos一致性算法中，有三种参与角色，分别为：Proposer、Acceptor、Learner；在具体的实现中，一个进程可能充当不止一种角色。参与者可以以任意的速度执行，可能会出错而停止也可能会重启，消息在传递过程中也可能会出现不可预知的延迟，也可能会重复或丢失。
Paxos被广泛应用于分布式系统中，如Google Chubby（分布式锁服务）以及Hypertable（分布式数据库）中，下面我们看看Paxos协议的工作过程。
提案生成与选定
提案的选定
一个提案必须被半数以上的Acceptor批准；
若提案[M,V]被批准，那么之后任何Proposer产生的编号比M高的提案，其Value值必须为V
Proposer提案生成算法
1.Proposer选择一个提案编号M，然后向某个Acceptor集合发出请求，并提出要求 （Prepare请求阶段）
（1）承诺不再批准编号小于M的提案
（2）若Acceptor已经批准过任何提案，那么就像Proposer反馈已经批准编号小于M的最大编号的提案的值
2.如果Proposer收到了半数以上的Acceptor响应结果，他可以产生编号为[M,V]的提案，其中V是所有响应中编号最大的提案Value值；当然若没有半数以上Acceptor批准提案，V值可以任意选取
3.确认提案后，Proposer将该提案再次发送个Acceptor集合（该集合并不一定是上次响应Prepare请求的集合，但任意两个半数以上集合肯定有公共的Acceptor），期望获得他们的批准
Acceptor批准提案
根据上述Prosposer提案生成流程，Acceptor会收到两种请求：Prepare与Accept
（1）Prepare请求：Acceptor可以响应任何一个Prepare请求
（2）Acceptor请求：在不违背现有承诺下，可以响应Acceptor请求
所以，Acceptor只要未响应过任何编号大于M的Prepare请求，他就可以接受这个编号M的提案；若已经对编号大于M的请求进行了响应，它可以忽略该编号为M的提案。因此每个Acceptor只需要记住它已经批准的最大编号以及已经做出Prepare请求响应的提案最大编号。
选取主Proposer
当然该算法还有一点问题，考虑一个特殊情况：若Proposer p1提出了编号为M1的提案，并完成了Propare阶段，此时Proposer p2提出了编号更大的M2提案，那么当p1进入阶段二时的Accept请求会被Acceptors忽略，如果p1再次生成新的更高编号M3，则p2第二阶段也失败，如此程序将陷入死循环。
为了解决该问题，Paxos通过选取主Proposer来解决死循环，只有主Proposer才能提出议案，所以只要主Proposer和过半Acceptor正常工作，主Proposer提出更高编号的议案最终会被批准。
算法陈述
阶段一
1.Proposer选择一个提案M，然后向Acceptor某个超过半数的集合发出Prepare请求
2.如果Acceptor收到编号为M的Prepare请求，且该编号大于它已经响应过的所有Prepare请求，那么它可以把已经批准过的最大编号提案反馈给Proposer，并承诺不再批转任何小于M的提案
阶段二
1.如果Proposer收到半数以上Acceptor对于发出编号为M的Prepare请求响应，它会生成一个[M,V]提案的Acceptor请求给Acceptor，V是收到的响应中编号最大的提案的值，若响应中没有提案，则V是任意值均可
2.若Acceptor收到提案为[M,V]的Accept请求，只要它会同意任何编号大于M的Prepare请求，他就可以批准该提案
Learner获取提案
在提案选定后，Learner角色需要获取提案，获取的方式主要有三种。
1.一旦Acceptor批准了一个提案，就将该提案发给Learner（通信次数太多）
2.选定一个主Learner，将提案发给主Learner，由主Learner通知其他Learner（通信次数减少，主Learner单点问题）
3.选取一个主Learner集合（方案二的改进）
ZooKeeper
ZooKeeper简介
ZooKeeper是一个开源的分布式协调服务，它将分布式中复杂容易出错的一致性协议封装起来，以简单易用的接口为用户提供服务。分布式应用程序可以基于它实现许多功能，如数据发布与订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选取、分布式锁、分布式队列等。
特点
（1）顺序一致性：统一客户端的事务请求，按照其顺序应用在ZooKeeper中
（2）原子性：所有事务请求处理结果在整个集群上是一致的，要么都成功要么都失败
（3）单一视图：客户端无论连接哪个ZooKeeper服务器，看到的数据模型都是一样的
（4）实时性：保证在一定时间段内，客户端能够读取到最新的数据状态
（5）可靠性：事务引起的状态变化会保存下来，直到下一个事务对其更改
设计目标
（1）简单数据模型：共享的、树型结构名字空间来相互协调（树型结构是ZooKeeper内存的一个数据模型，由Znode数据节点构成，类似文件系统，Znode是层级关系）
（2）构建集群：集群由一组机器构成，每台都在内存中维护服务器状态，服务器间保持通信，只要超过一半机器工作正常，整个集群就能对外提供服务。
（3）顺序访问：对于客户端的每个请求，ZooKeeper都会生成一个全剧唯一的递增编号，这个编号反应了事务的先后顺序
（4）高性能：ZooKeeper将数据保存在内存中
ZooKeeper中的基本概念
集群角色
Leader、Follower、Observer三种角色。Observer不参与Leader选举和“过半写成功”策略，但它可以提升集群读性能
会话Session
客户端通过TCP长连接来连接ZooKeeper，在第一次建立连接后，session的生命周期也开始了。客户端通过心跳检测机制来保持回话有效，也能够接受服务器的Watch事件通知。当服务器压力太大或网络故障导致连接断开时，只要在sessionTimeout时间内重新连接上任意一台服务器，那么之前创建的会话依然有效。
数据节点Znode
ZooKeeper将数据保存在内存中，数据模型是一颗树（Znode Tree），由/分割的路径就是一个Znode，Znode保存数据内容及属性信息。Znode分为持久节点和临时节点，临时节点与客户端会话绑定，一旦会话失效，则临时节点会被删除。
版本
ZooKeeper为每个Znode维护一个Stat数据结构，记录了三个版本信息，version（Znode版本），cversion（Znode子节点版本），aversion（ACL版本）。
Watcher
Watcher事件监听器，允许客户端在节点上注册Watcher，并在特定事件触发时，将事件通知给感兴趣的客户端。该机制是ZooKeeper实现分布式协调服务的重要特性。
ACL
ACL策略用来进行权限控制，ZooKeeper定义了5种权限
（1）create：创建子节点
（2）read：读取节点数据和子节点列表
（3）write：更新节点数据
（4）delete：删除子节点
（5）admin：设置节点ACL
ZAB协议介绍
ZooKeeper并没有使用Paxos协议，而是使用了ZooKeeper Atomic Broadcast（原子消息广播算法）作为一致性的核心算法。ZAB不像Paxos是一种通用的分布式一致性算法，它是专门为ZooKeeper设计的崩溃可恢复的原子消息广播算法。基于该算法，ZooKeeper使用单一的的主进程来接受处理客户端的事务请求，使用ZAB协议将数据状态变更以事务Proposal形式广播到所有副本进程。所以这种主备模型保证了集群中只有一个主进程来处理请求，也保证了请求事务的顺序。
下面我们详细分析ZAB协议的具体内容，ZAB包括两种基本模式：崩溃恢复与消息广播。在服务框架刚启动或Leader挂掉后，ZAB协议进入恢复模式选举新的Leader，当选举完成并且有过半Follwers进行状态同步后，ZAB协议退出恢复模式进入消息广播模式。当一台新的服务器加入集群后，它将进入恢复模式，找到Leader进行数据同步然后参与广播模式。Leader服务器在接收到事务请求后进行事务广播协议，若其他服务器接收到事务请求将转发给Leader。当Leader崩溃或不再与半数以上服务器正常通信时，ZAB协议将从消息广播模式进入到崩溃恢复模式，所以Leader必须要有半数以上的服务器支持。
消息广播
ZAB的消息原子广播协议类似一个二阶段提交过程，针对客户端的事务请求，Leader生成对应的事务Proposal然后发送给其余机器，在收集选票后执行事务提交。与二阶段提交不同之处在于，ZAB移除了中断模式，Followers可以反馈事务Proposal也可以抛弃，只要有过半Followers反馈后就可以提交事务，这种简化的二阶段提升了效率也带来了数据不一致问题。ZAB使用崩溃恢复模式来解决。此外，消息广播使用了FIFO的TCP协议进行通信，保证了事务的顺序性。
Leader生成的Proposal事务消息都会有一个ID（ZXID），该事务ID用于保持事务之间的顺序，具体来说，Leader为每一个Follower分配一个单独的队列，将事务放入队列按照FIFO规则进行发送，得到半数以上Follwers反馈ACK后进行提交，同时也给Followers发送Commit消息。
崩溃恢复
当Leader崩溃后，ZAB需要选举出新的Leader，需要保证（1）已经在Leader上提交的事务最终被所有服务器提交（2）丢弃那些只在Leader上提出的事务
结合上述两种极端情况，ZAB需要保证提交已经被Leader提交的事务，丢弃已经被跳过的事务。所以ZAB保证新选取的Leader拥有集群中最大的事务ID（ZXID），该机器一定具有已经提交的提案。
在选举出新Leader后，ZAB还需要保证集群中过半服务器已经提交了所有事务Proposal，即数据同步。具体来说，Leader向每一个Follower的队列中发送未完成的事务Proposal，并在每一个事务后紧接着发送Commit消息表示该事务已提交，等Follower服务器将所有事务都同步过来后，Leader将它加入真正可用的Followers列表。
在特殊情况下，ZAB需要处理需要丢弃的事务。ZAB的事务编号ZXID是一个64位数字，其中低32位是自增的数字代表了Leader处理的事务顺序，高32位代表了Leader的周期epoch。没当选举出新的Leader时，都会从最大事务ZXID中取出epoch值并加1代表新的epoch值，然后将低位置0。基于该策略，当一个上一个Leader周期尚未提交事务Proposal机器加入时，它作为Follower与Leader同步时，Leader根据自己最大事务进行对比，然后让该Follower执行回退操作，回退到已经被半数以上机器提交的最新事务，因而保证丢弃了未提交的事务。
深入理解ZAB
在大概了解ZAB协议的内容后，我们详细分析ZAB的算法流程。ZAB协议主要包含了消息广播和崩溃恢复两个过程，进一步可以细分为三个阶段：发现，同步，广播。组成ZAB协议的每一个分布式进程会循环执行这三个阶段，这一循环过程称为主进程周期。
发现
发现就是Leader选举过程，其工作流程如下：
1.Follower将自己最后接受的事务epoch发给准Leader
2.接受来自过半Follower的epoch消息后，准Leader产生新的epoch值并发给这些Follower（新的epoch值为来自Follower中最大的值，然后加1）
3.Follower接受来自准Leader的新epoch值后，若大于当前的epoch则更新epoch并发送ack给准Leader，并将自己已执行的事务Proposal集合发给准Leader
4.准Leader接受ack后，会从中选择一个Follower的其事务集合初始化自身事务集合I（该Follower选取条件：ZXID最大，即epoch最大，若有epoch相同，则事务ID最大）
同步
在同步阶段中，Leader和Follower进行事务消息同步，具体流程如下：
1.Leader将epoch和事务集合I发送给过半集合Follower
2.Follower接受消息后，对比epoch若不相同（还在上一轮），直接进入下一轮，不参与本轮的同步；若相同则执行I中事务并反馈给Leader
3.当Leader收到过半Follower反馈后，发送Commit消息，然后Follower提交事务
广播
在数据同步后，Leader可以接受客户端的事务请求，并进行消息广播，具体流程如下：
1.Leader接受客户端事务请求，生成事务CXID，按顺序发送给Follower
2.Follower根据接受事务顺序，添加到事务集合，并反馈给Leader
3.收到过半Follower针对事务的ack消息后，Leader发送Commit消息，要求它们提交事务
4.Follower收到Commit消息后提交事务，此时上一个事务肯定已经提交了
下图展示了ZAB协议的工作过程的三个阶段：
运行分析
ZAB协议中，每一个进程处于以下三种状态之一：
-Looking：Leader选举
-Following：Follower与Leader同步
-Leading：Leader领导状态
进程刚启动时，都处于Looking状态，选举出Leader后，Follower切换到Following状态，Leader处于Leading状态。
ZAB与Paxos联系与区别
联系
1.两者都存在Leader与Follower角色
2.Leader都会等待超过半数Follower反馈后在提交事务
3.两者协议都存在主进程周期说法，ZAB的epoch，Paxos的Ballot
区别
Paxos在产生Leader后，进行两个阶段，分别为读阶段，写阶段。读阶段，主进程会和Follower通信，收集上一个主进程的提出议案，并把它提交；写阶段主进程提出自己的议案。
ZAB增加一个同步阶段，同步前ZAB也有一个类似的读阶段称为发现阶段，然后同步阶段确保过半Follower提交了上一周期的所有事务Proposal，同步完成后同样执行写阶段，处理客户端请求。
