分布式要点总结

1. 集中式和分布式的区别

集中式系统的特点是部署结构简单，无需考虑多个节点之间的协作问题。但是集中式系统：1.人才培养成本高；2.用于存储的大型主机成本高；3.有明显的单点问题，一旦出现故障，整个系统将会处于宕机状态。

分布式系统具有的特征：1.分布性，计算机在空间上随意分配；2.对等性，每个计算机节点都是对等的；3.并发性，每个节点可以同时操作共用的资源；4.缺乏全局时钟，在分布式系统中很难确定两个事件谁先谁后，即分布式系统缺乏一个全局的时钟序列控制；5.故障总会发生，由于计算机多，发生故障的概率就会变大。

2. ACID、CAP、BASE理论分别是什么

ACID（事务的四个特征）：

原子性（Atomicity），指事务必须是一个原子性的操作序列单元。一次执行过程中，只有两种结果，全部成功执行或者全部不执行。
一致性（Consistency），指事务的执行不能破坏数据库数据的一致性和完整性，事务的执行结果是使数据库从一个一致性状态到另一个一致性状态。
隔离性（Isolation），指并发的事务是相互隔离的，不同的事务操作相同的数据时，每个事务有自己完整的数据空间，并发的事物之间互不干扰。
持久性（Durability），指一个事务一旦提交后，它对数据库中的数据的影响是永久性的。

CAP定理：

一致性。指数据在多个副本之间是否能够保持一致的特性。同上。
可用性。指系统提供的服务一直处于可用的状态。
分区容错性。分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境出现故障。

CAP定理指出，一个分布式系统不可能同时满足全部的三个特性，首先分区容错性是一个最基本的要求，因此如何在其他的两个特性之间寻找平衡是一个关键。

BASE原理：

Basically Available（基本可用），指当分布式系统出现不可预知的故障时，允许损失部分可用性。
Soft State（弱状态），指允许系统中的数据存在中间状态，并认为改中间状态的存在不会影响系统的整体可用性。即允许系统在不同节点的数据副本之间进行数据同步时的过程存在延时。
Eventually Consistent（最终一致性），指系统中所有的副本在经过一段时间后，最终能达到一个一致的状态。

3. 2PC、3PC的过程以及两者之间的区别

2PC（Two-Pha***mit）二阶段提交

第一阶段提交事务请求（投票阶段）
- 协调者向所有参与者发送事务内容询问是否可以执行事务提交操作
- 各参与者执行事务操作并记录操作日志
- 若参与者成功执行事务操作，则返回Yes响应，反之则是No响应
第二阶段执行事务提交

根据第一阶段参与者的反馈结果决定是否执行事务提交操作，包含两种可能结果
- 执行事务提交（所有参与者的反馈均为Yes）
  - 发送事务请求（协调者向参与者发送允许提交事务的信号Commit）
  - 事务提交
  - 反馈事务提交结果（参与者向协调者发送完成提交事务的信号Ack）
  - 完成事务（接收到所有的Ack后）
- 中断事务（任意一个参与者的反馈为No）
  - 发送回滚请求（协调者向参与者发送允许提交事务的请求RollBack）
  - 事务回滚（根据某一阶段的记录日志进行回滚，完成回滚后释放执行时所占的资源）
  - 反馈事务回滚的结果（参与者向协调者发送完成回滚的信号Ack）
  - 中断事务（接收到所有的Ack后）

2PC的优点就是提交简单，实现方便；缺点就是会产生同步阻塞（在提交过程中所有参与事务操作的逻辑都处于阻塞状态）、单点（只有一个协调者，一旦出现问题就无法完成事务操作）、脑裂（可能由于故障原因，只有部分参与者收到Commit请求导致数据不一致）和太过保守（协调者只能依靠自己的超时机制来判断是否需要中断事务）。

3PC（Three-Pha***mit）三阶段提交

第一阶段 CanCommit
- 事务询问（协调者向所有的参与者发送一个带有事务内容的CanCommit询问请求）
- 对于询问的反应（参与者根据自身状态反馈Yes或者No响应）
第二阶段 PreCommit（执行事务的预提交）
- 发送预提交请求（协调者向所有的参与者发送一个PreCommit询问请求）
- 事务预提交
- 各参与者向协调者反馈事务执行的响应
  - 各参与者都成功执行事务操作，返回Ack响应
  - 中断事务（任意一个参与者的反馈为No）
第三阶段DoCommit

该阶段执行真正的事务提交，存在以下两种情况：
- 执行提交
  - 发送提交请求（接受所有参与者的Ack响应，从“预提交”到“提交”状态并向所有的参与者发送Docommit请求）
  - 事务提交
  - 反馈事务提交结果（参与者在完成事务提交后，向协调者发送Ack消息）
  - 完成事务（协调者接收到所有参与者反馈的消息后，完成事务）
- 中断事务（任意一个参与者的反馈为No）
  - 发送中断请求（协调者向所有的参与者节点发送abort请求）
  - 事务回滚（根据某一阶段的记录日志进行回滚，完成回滚后释放执行时所占的资源）
  - 反馈事务回滚结果（返回Ack结果）
  - 中断事务（协调者接收到所有参与者反馈的Ack消息后，中断事务）

两者之间的对比：

相对于2PC，3PC提交协议最大的优点就是降低了参与者的阻塞范围，并且能在出现单点故障后继续达成一致。但也有可能出现数据不一致性的问题。

4. Paxos、Raft算法的描述及与上一步中的区别

Paxos算法的描述：proposer、acceptor、learner

第一阶段
- Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
- 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
第二阶段
- 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
- 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

learner的学习过程

图片说明

保证Paxos算法的活性

图片说明

Raft一致性算法

Raft算法是Paxos算法的一种简化实现。

包括三种角色：leader，candidate和follower。

follow:所有节点都以follower的状态开始，如果没有收到leader消息则会变成candidate状态。
candidate：会向其他节点拉选票，如果得到大部分的票则成为leader，这个过程是Leader选举。
leader：所有对系统的修改都会先经过leader。

其有两个基本过程：

Leader选举：每个candidate随机经过一定时间都会提出选举方案，最近阶段中的票最多者被选为leader。
同步log：leader会找到系统中log（各种事件的发生记录）最新的记录，并强制所有的follow来刷新到这个记录。

Raft一致性算法是通过选出一个leader来简化日志副本的管理，例如，，日志项（log entry）只允许从leader流向follower。

Paxos、Raft算法与2PC、3PC的区别

2PC解决了提交事务中的原子性问题，保证了分布式事务的多个参与者要么都执行成功要么都执行失败，但是同时2PC会出现同步阻塞、无线等待等问题，而3PC引进了PreCommit阶段则是解决了无限等待的问题，Paxos算法的引入的“过半”概念以及各分布式角色之间的轮换特点则既解决了无限等待的问题又避免了分布式单点的出现，避免了脑裂的出现。

5. ZooKeeper的工作原理

zookeeper是一个开源的分布式数据管理与协调框架，致力于提供一个高性能、高可用并且具有严格顺序访问控制能力的分布式协调服务。核心的一致性算法是ZAB协议。

ZAB协议（ZooKeeper Atomic BroadCast 原子消息广播协议）

核心是定义了对于那些会改变ZK服务器数据状态的事务请求的处理方式，即：

所有事务请求必须有一个全局的Leader服务器进行处理，剩下的服务器均为follower。leader服务器负责将一个客户端的请求转换为proposal（提议），并将该proposal分发给集群中的所有follower服务器。之后leader等待follower服务器的反馈，一旦有超过半数的follower服务器进行了正确的反馈，那么leader就会再次向所有的follower服务器分发commit消息，要求其将上一个proposal进行提交。

消息广播

使用的是原子消息协议，类似于2PC提交过程，即将事务proposal分发给集群中的其他机器，然后搜集投票，根据投票结果进行最终的事务提交。具体的广播过程就是，leader服务器会为每一个follower服务器各自分配一个队列，然后将需要广播的事务proposal依次分配到队列中，并且根据FIFO的策略进行消息发送。每一个follower在接收到proposal后首先将其以事务日志的形式写入磁盘中，并在成功后返回一个Ack给leader服务器，leader服务器在接收到超过半数follower的Ack后，就会广播一个Commit消息给所有的follower服务器以通知其进行事务提交，同时自己也会完成事务的提交，每一个follower接收Commit后也会进行事务提交。
崩溃恢复

当leader服务器出现故障后或者无法与半数以上的follower保持正常通信后就会进入崩溃恢复的状态。主要分为选举新的leader和数据同步的两个过程。其中的两个特性：
- ZAB协议需要保证那些已经在leader服务器上提交的事务最终被所有的服务器提交
- ZAB协议需要确保丢弃那些只在leader服务器上被提出的事务
正常情况下只有当follower服务器将所有未同步的事务proposal都从leader服务器上同步过来并成功应用到本地数据库，leader才会将该follower服务器加入真正可用的follower列表中。对于被丢弃的事务proposal来说，是根据epoch编号进行区分的。在ZAB协议中，会有一个事务编号ZXID，ZXID是一个64位的数字，低32位是一个简单的递增计数器，每新产生一个事务proposal就会+1，高32位是代表了leader周期epoch的编号，没产生一个新的leader，就会从这个leader服务器中日志中取出最大事务proposal的ZXID并解析出对应的epoch值，并+1。这样的话每一个ZXID都是不同的，就可以根据这个来识别不同的proposal并进行后续的处理。

算法描述

细分为三个阶段，分别是发现（Discovery）、同步（Synchronization）和广播（Broadcast）。

阶段一发现

leader的选举过程，用于在多个分布式进程中选举出主进程。
- 首先follower将自己最后接受的事务proposal的epoch值发送给准leader服务器
- 当接收到过半的follower的消息后，准leader会将接收到的所有的follower的epoch中挑选一个最大值+1，再返回给这些过半的follower。
- 当follower接收到新的epoch值时，如果它检测到当前的自己最后接受的事务值比其小，它就会改变自己事务epoch值为接收到的新epoch值，同时给准leader返回一个Ack消息，这个消息包括了当前follower的事务epoch值和历史的事务集合。
- 当准leader收到过半的follower的确认消息Ack后，成为leader，该leader就会从这过半的follower中选取一个follower作为初始事务集合。
第二阶段同步
- leader会将自己的epoch值和初始事务集合再次发送给各follower，followe在接收完信息后比对自己的epoch值，如果不相等就直接进入下一轮的循环，因为不相等的话必然是落后于leader的。若相等，则执行相应的事务操作，最后反馈一个完成事务的信号给leader。
- leader在接收到半数以上的反馈消息后，会再次向所有的follower发送Commit消息，至此leader完成同步阶段。
- follower在收到Commit消息后，就会依次处理并提交所有在初始事务集合中未处理的事务，至此follower完成同步阶段。
第三阶段广播
- leader在接收到客户端的请求后，就可以生成相应的事务，并按照ZXID的顺序向所有的follower发送提案
- follower根据接收事务的先后顺序依次处理这些事务，并将其追加到已经处理过的事务集合中，之后反馈给leader
- 当leader接收到半数以上的follower的Ack反馈消息后，就会发送Commit消息给所有的follower，要求他们进行事务的提交
- follower接收到Commit消息后就开始进行对当前事务的提交

在正常的运行过程中，ZAB协议会一直运行于阶段三反复的进行消息广播流程，如果 leader出现问题，那么ZAB协议会再次进入阶段一，重新选举新的leader。

运行分析

进程在运行的时候也是处于以下三种状态之一

LOOKING：leader选举阶段
FOLLOWING：follower服务器和leader保持同步状态
LEADING：leader服务器作为主进程领导状态

Paxos算法与ZAB协议

Paxos算法包括一个读阶段和一个写阶段，而ZAB协议分为发现、同步和广播三个阶段，多增加了一个同步阶段，同步阶段是为了保证leader在新的周期中提出事务Proposal之前，所有的进程都已经完成了对之前所有事务proposal的提交。
本质区别在于两者的设计目标不一样，ZAB协议是为了构建一个高可用的分布式数据主备系统，而Paxos算法则是为了构建一个分布式的一致性状态机系统。