分布式系统和集群的区别

• 集群：由多台提供相同的服务的服务器组成。

• 分布式系统：把整个系统做服务拆分，拆分成多个子服务，由多台提供不同子服务的服务器组成。

三种限流算法

令牌桶（Token Bucket）

• 系统按固定速率往桶中放入token，如果桶中的token满了就不再添加。当有请求来的时候会拿走一个token，只有拿到token才能被后续服务，没有token就会拒绝服务。

• 如果一段时间比较空闲，桶中就会有堆积的token，一旦突然有突发流量，就可以比较好地处理这些突发的大流量。所有它可以允许突发流量。

漏桶

流量可以任意速率地打来，超过漏桶容量就会拒绝请求。漏桶以固定的速率漏水。不能应对突发流量。

计数器

核心思想就是限制总并发数。具体的实现方式有：

• AtomicInteger统计当前并发数，超过阈值就拒绝请求。
• Semaphore信号量，配合阻塞队列使用，超过阈值就加入到阻塞队列中等待处理。
• 线程池

服务容错模式

• 主动超时：Http请求主动设置一个超时时间，超时就直接返回，不会造成服务堆积

• 限流：限制最大并发数

• 隔离：把每个依赖或调用的服务都隔离开来，防止级联失败引起整体服务不可用

• 熔断：当下游服务因访问压力过大而响应变慢或失败，上游服务为了保护系统整体的可用性，可以暂时切断对下游服务的调用。

• 降级：由于爆炸性的流量冲击，对一些服务进行有策略的放弃，以此缓解系统压力，保证目前主要业务的正常运行。它主要是针对非正常情况下的应急服务措施：当此时一些业务服务无法执行时，给出一个统一的返回结果。

熔断和降级的区别：https://developer.aliyun.com/article/269141

负载均衡

负载均衡常见算法有哪些？

• 轮询法(Round Robin)

• 加权轮询法(Weight Round Robin)

• 平滑加权轮询法(Smooth Weight Round Robin)

• 随机法(Random)

• 加权随机法(Weight Random)

• 源ip地址哈希法(Hash)

• 最小连接数法(Least Connections)

Nginx的5种负载均衡算法？

• 轮询（默认）
• 加权轮询
• 源ip地址哈希（ip_hash）
• url_hash
• fair：响应时间短的优先分配

常见的SLB（服务器负载均衡）

四层SLB

• 工作在OSI模型的第四层，即传输层，基于ip和端口来实现路由转发。

• 客户端向负载均衡服务器发送 SYN 请求建立第一次连接，负载均衡服务器通过配置好的负载均衡算法选择一台后端服务器，并且将报文中的 IP 地址信息修改为后台服务器的 IP 地址信息，因此 TCP 连接是直接与后端服务器直接建立起来的。

• 优点：性能好。

• 缺点：不灵活，难做大规模的功能改造。

常见的服务器有：F5、LVS(Linux Virtual Server 虚拟服务器， Linux 内核的 4 层负载均衡)

七层SLB

• 工作在应用层，需要基于URL等信息实现代理转发，主要实现方案有DNS负载均衡和反向代理。
• 需要先于负载均衡服务器建立TCP，代理完后再与后端服务器建立TCP连接，网络损耗更多一些。
• 优点：灵活，可改造，功能丰富。
• 缺点：性能差一点。

常见的服务器有：Nginx

DNS负载均衡：

一致性Hash算法

背景

在分布式集群中需要增删服务器。如果采用常用的hash(object)%N的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，除非转移数据做rehash，但这是非常麻烦的。

实现

• 将key值哈希到 [0, 2^32) 的一个环形的hash空间，各台服务器也可以将其ip地址hash到这个环上。
• key值hash后顺时针找到最近的服务器，就访问这台服务器。
• 增加服务器节点时能分担流量压力。
• 删除节点时只影响到了原先存储在该节点上的key值，其他都没有受到影响，解决了hash取模可能带来的雪崩问题。
• 一个实际节点对应若干个虚拟节点，使用虚拟节点让流量能较均匀地分散到各个节点上，即使是某节点宕机的时候。

CAP理论

• 一致性（Consistency）：所有节点访问同一份最新的数据副本。

• 可用性（Availability）：请求能够被整个系统及时正确处理，即使出现节点失效，不会一直等待。

• 分区容错性（Partition Tolerance）：在网络断开的情况下，被分隔的节点仍能正常对外提供服务。

  • 分布式系统中，多个节点之前的网络本来是连通的，但是因为某些故障（比如部分节点网络出了问题）某些节点之间不连通了，整个网络就分成了几块区域，这就叫 网络分区。

• 三者不能同时满足

不是所谓的“3 选 2”

大部分人解释这一定律时，常常简单的表述为：“一致性、可用性、分区容忍性三者你只能同时达到其中两个，不可能同时达到”。实际上这是一个非常具有误导性质的说法，而且在 CAP 理论诞生 12 年之后，CAP 之父也在 2012 年重写了之前的论文。

当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提，决定了 P 之后才有 C 和 A 的选择。对于一个分布式系统来说，分区容错性（Partition tolerance）我们是必须要实现的。

简而言之就是：CAP 理论中分区容错性 P 是一定要满足的，在此基础上，只能满足可用性 A 或者一致性 C。

因此，分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。 比如 ZooKeeper、HBase 就是 CP 架构，Cassandra、Eureka 就是 AP 架构，Nacos 既支持 CP 架构也支持 AP 架构。

• ZooKeeper 保证的是 CP。 任何时刻对 ZooKeeper 的读请求都能得到一致性的结果，但是， ZooKeeper 不保证每次请求的可用性比如在 Leader 选举过程中或者半数以上的机器不可用的时候服务就是不可用的。

• Eureka 保证的则是 AP。 Eureka 在设计的时候就是优先保证 A （可用性）。在 Eureka 中不存在什么 Leader 节点，每个节点都是一样的、平等的。因此 Eureka 不会像 ZooKeeper 那样出现选举过程中或者半数以上的机器不可用的时候服务就是不可用的情况。 Eureka 保证即使大部分节点挂掉也不会影响正常提供服务，只要有一个节点是可用的就行了。只不过这个节点上的数据可能并不是最新的。

为啥不可能选择 CA 架构呢？ 举个例子：若系统出现“分区”，系统中的某个节点在进行写操作。为了保证 C， 必须要禁止其他节点的读写操作，这就和 A 发生冲突了。如果为了保证 A，其他节点的读写操作正常的话，那就和 C 发生冲突了。

选择 CP 还是 AP 的关键在于当前的业务场景，没有定论，比如对于需要确保强一致性的场景如银行一般会选择保证 CP 。

另外，需要补充说明的一点是： 如果网络分区正常的话（系统在绝大部分时候所处的状态），也就说不需要保证 P 的时候，C 和 A 能够同时保证。

BASE 理论

• 基本可用（Basically Available）：分布式系统在出现不可预知故障的时候，允许损失部分可用性。

• 软状态（Soft state）：软状态和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

• 最终一致性（Eventually consistent）：最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

• BASE 是对 CAP 的 AP 方案的延伸，其基本思路就是：通过业务，牺牲强一致性而获得可用性，并允许数据在一段时间内是不一致的，但是最终达到一致性状态。

分布式一致性的 3 种级别：

1. 强一致性 ：系统写入了什么，读出来的就是什么。
2. 弱一致性 ：不一定可以读取到最新写入的值，也不保证多少时间之后读取到的数据是最新的，只是会尽量保证某个时刻达到数据一致的状态。
3. 最终一致性 ：弱一致性的升级版，系统会保证在一定时间内达到数据一致的状态。

业界比较推崇是最终一致性级别，但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。

实现最终一致性的具体方式：

• 读时修复 : 在读取数据时，检测数据的不一致，进行修复。比如 Cassandra 的 Read Repair 实现，具体来说，在向 Cassandra 系统查询数据的时候，如果检测到不同节点的副本数据不一致，系统就自动修复数据。

• 写时修复 : 在写入数据，检测数据的不一致时，进行修复。比如 Cassandra 的 Hinted Handoff 实现。具体来说，Cassandra 集群的节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，修复数据的不一致性。

• 异步修复 : 这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复。

比较推荐 写时修复，这种方式对性能消耗比较低。

分布式事务

刚性事务与柔性事务

• 刚性事务：遵循分布式理论的CP ，对数据要求强一致性

• 柔性事务：遵循分布式理论的AP+BASE ，允许一定时间内不同节点的数据不一致，但要求最终一致。

刚性事务

XA协议与XA接口

• XA协议是一个基于数据库的分布式事务协议，其分为两部分：事务管理器（Transaction Manager）和局部资源管理器（Resource Manager）。

• 事务管理器：是全局的调度者，管理各个局部资源管理器的提交或者回滚。二阶提交协议（2PC）和三阶提交协议（3PC）就是根据此协议衍生出来而来。主流的数据库如Oracle、MySQL等均已实现了XA接口。

• XA接口是双向的系统接口，在事务管理器与一个或多个资源管理器之间建立通信，在基于XA的一个事务中，我们可以对多个资源进行事务管理，例如我们可以实现多个数据库和多个消息中间件全部提交或全部取消的事务。

• XA规范不是java的规范，而是一种通用的规范; Java 中的规范是JTA和JTS：Java事务API（Java Transaction API）是一个Java企业版的应用程序接口，在Java环境中，允许完成跨越多个XA资源的分布式事务；Java事务服务（Java Transaction Service）是J2EE平台提供了分布式事务服务的具体实现规范，j2ee服务器提供商根据JTS规范实现事务并提供JTA接口。

2PC 2阶段提交

• 角色：协调者和参与者
• 两个阶段：
  • Prepare请求阶段：协调者向参与者发送 prepare 请求，参与者收到请求后，执行本地分支事务操作，并记录redo和undo日志信息，同时锁定当前事务相关的资源，如果参与者执行成功，回复 yes，否则回复 no。
    • 若参与者回复协调者的yes/no消息超时了，协调者可以安全地发送abort指令让所有参与者rollback。
  • Commit提交阶段：若所有参与者都回复了 yes，协调者向所有参与者发送 commit 请求让其提交分支事务，否则发送 rollback 请求让其回滚分支事务。
    • 若参与者等待协调者的commit/rollback请求超时了，如果B之前回复的是NO，此时无需等待协调者回复就可以直接回滚；如果B之前回复的是YES，此时B就不能单方面的执行abort操作或commit操作，因为如果A接收到协调者发送的commit操作但是B超时没有收到，B进行abort后就会出现数据不一致；如果B执行commit但是A返回给协调者的是NO，也会数据不一致。这是2PC的缺点。
• 缺点：
  • 同步阻塞：分支事务在 prepare 阶段锁定资源，所有与该事务相关的逻辑都处于阻塞状态，无法进行其他任何操作。
  • 协调者单点问题：如果 prepare 阶段成功了，但在commit阶段协调者发出 commit 指令之前宕机了，相关资源处于锁定状态，事务将无限期地等待。
  • 数据不一致：如果 prepare 阶段成功了，但在commit阶段协调者向某个节点发送 commit 命令因网络造成超时，各个参与者不知是该提交还是回滚事务，就会导致数据不一致。
  • 极端情况：协调者在发出DoCommit 消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
  • 2PC除本身的算法局限外，还有一个使用上的限制，就是它只适用于两个数据库之间（数据库实现了XA协议）。两个系统之间是无法使用2PC的，因为不会直接在底层的两个业务数据库之间做一致性，而是在两个服务上面实现一致性。

3PC 3阶段提交

• 为了解决2PC的问题，3PC做了如下改进：

  • prepare 阶段分成了两步：canCommi 阶段询问和 preCommit阶段锁定资源。保证了在最后提交阶段之前，各参与者节点的状态都一致。
  • 协调者和参与者都引入超时机制。当参与者因各种原因未收到协调者的commit请求后，会对commit分支事务，不会一直阻塞等待，也解决了单点问题。

• 缺点：还是不能解决数据不一致的问题。如第三阶段发出 rollback 请求，此时如果出现网络分区，协调者与部分参与者之间无法进行正常网络通信，一部分参与者在超时之后还是会进行事务提交，一部分参与者执行回滚，出现数据不一致。

• 三个阶段：

  • CanCommit阶段：协调者向所有参与者发送 CanCommit 请求，询问参与者是否能执行事务，如果全部响应YES则进入下一个阶段，否则中断事务。
  • PreCommit阶段：协调者将向所有参与者发送 PreCommit 预提交请求，参与者收到预提交请求后，执行本地分支事务操作，将 Undo 和 Redo 信息写入事务日志中，锁定资源 ，最后如果参与者顺利执行了事务则返回yes响应。一旦有任何一个 NO 响应，或因网络造成协调者等待超时，就会中断事务，向所有参与者发送中断请求（abort）。或者参与者等待preCommit指令超时，参与者自己也会中断分支事务。
  • DoCommit阶段：与2PC的第二阶段一样。但有一点改进的是：参与者等待DoCommit指令超时，参与者会自己提交事务，因为这时我们已经在第一阶段确定了所有的参与者都可以执行事务，这个时候我们有理由相信其他参与者都能进行事务的执行和提交。

柔性事务

TCC 补偿事务

TCC（Try-Confirm-Cancel）与2PC的思想很相似，事务处理流程也很相似，但2PC是应用于在DB层面，TCC则可以理解为在应用层面的2PC，是需要我们编写业务逻辑来实现。TCC的核心思想是：针对每个操作都要注册一个与其对应的确认（Try）和补偿（Cancel）。以下单业务为例：

• Try阶段：下单时通过Try操作去扣除库存预留资源。
• Confirm阶段：确认执行业务操作，只在预留的资源基础上，发起购买请求。
• Cancel阶段：涉及到的相关业务中，只要有一个业务方预留资源未成功，则取消所有业务资源的预留请求。

缺点（准确点说应该是业务逻辑考虑得是否周到）：

• 空回滚：当一个分支事务因服务器宕机或网络异常导致未执行try方法，恢复后事务回滚执行cancel方法。

  • 解决方法：需要判断是否执行了try，如果执行了就没有空回滚。当主业务发起事务时，生成一个唯一的全局事务ID，贯穿整个事务，再创建一张分支事务记录表，用于记录分支事务，try执行时将全局事务ID和分支事务ID存入分支事务表中，表示执行了try，当cancel时，先判断表中是否有该全局事务ID的数据，如果有则回滚，否则不做任何操作。比如seata的AT模式中就有分支事务表。

• 幂等问题：重试机制需要保证confirm和cancel操作的幂等性。

  • 解决方法：在分支事务记录表中增加事务执行状态，每次执行confirm和cancel时都查询该事务执行状态，判断事务的幂等性。

• 资源悬挂问题：在调用try之前会先注册分支事务，注册分支事务之后，try调用超时，此时try请求还未到达对应的服务，但因调用超时，所以会执行cancel，cancel执行完后，try请求到达，但因cancel已执行，所以执行try之后就没后续操作了，导致资源挂起，无法释放。

  • 解决方法：同样借助分支事务表中的事务执行状态，如果已经执行了confirm或者cancel那么try就不执行。

Saga事务

Saga由多个的分支事务构成。每一个分支事务在更新完数据库之后，会发布一条消息或者一个事件来触发Saga中的下一个分支事务的执行。如果某个分支事务执行失败，Saga会执行这个失败的分支事务之前成功提交的所有分支事务的补偿操作。

实现方法

• 事件模式/编排模式：没有事务协调者，各个事务会产生某类事件，或监听其它服务产生的事件并决定是否需要针对监听到的事件做出响应。

  • 优：

    • 简单且容易理解。
    • 各参与方相互之间无直接沟通，松耦合。
    • 比较适合整个分布式事务只有2-4个步骤的情形。

  • 劣：

    • 如果涉及比较多的业务参与方，会很容易失控。
    • 各业务参与方可随意监听对方的消息，整个系统逻辑混乱，代码维护很困难。
    • 可能产生环形监听，两个业务方相互监听对方所产生的事件。

  

• 控制模式：有事务协调者，通过它告诉各事务参与者该执行哪一个分支事务。

  • 优：

    • 避免环形监听。

    • 由协调中心管理，整个系统逻辑非常清楚。

    • 减少了业务参与方的复杂度。这些业务参与方不再需要监听不同的消息，只是需要响应命令并回复消息。

    • 测试更容易（分布式事务逻辑存在于协调中心，而不是分散在各业务方）。

    • 回滚也更容易。

  • 劣：

    • 需要单独维护协调中心，而这个协调中心并不属于任何业务方。（相对的缺点而已）

  

使用建议

• 每一个分支事务创建唯一的Tx id，用来精确定位某分支事务。

• 控制模式时，在命令中携带回复地址，可以让服务同时响应多个协调中心请求。

• 让各个业务参与方服务提供幂等性操作，能够在遇到异常情况下进行重试。

• 尽量在命令或者消息中携带上下文数据，避免下游处理时需要调用消息产生方接口获取更多数据，减少系统之间的相互依赖。

Seata

角色

• TC (Transaction Coordinator) 事务协调者：维护全局和分支事务的状态，**协调（指挥）**全局事务提交或回滚。
• TM (Transaction Manager) 事务管理器：定义全局事务的范围，开始全局事务、提交或回滚全局事务。
• RM (Resource Manager) 资源管理器：管理分支事务处理的资源，与TC交谈以注册分支事务和报告分支事务的状态，并驱动分支事务提交或回滚。

XA模式

前提

• 支持 XA协议的关系型数据库。
• Java 应用，通过 JDBC 访问数据库。

整体机制

Seata XA模式利用事务资源（数据库、消息服务等）对 XA 协议的支持，以 XA 协议的机制来管理分支事务。

• 执行阶段（Execute）： XA start/XA end/XA prepare + SQL + 注册分支

• 完成阶段（Finish）：XA commit/XA rollback

数据源代理

XA 模式需要 XAConnection类

获取 XAConnection 两种方式：

• 方式一：自己配置 XADataSource。

  • 给开发者增加负担，需要专门学习使用 XA 数据源，与透明化 XA 编程模型的设计目标相违背。

  • 类比 AT 模式的数据源代理机制，如下：

    

• 方式二：根据普通 DataSource 来创建。

  • 对开发者较友好，完全不必关心 XA 层面的任何问题，保持本地编程模型即可。开发中优先使用这种方式，数据源代理根据普通数据源中获取的普通 JDBC 连接创建出相应的 XAConnection。
  • 有局限：可能会不兼容。不同厂商、不同版本的数据库驱动实现机制都是不同的，所以XA模式需要同时支持第一种方式预防不兼容。
  • 类比AT的数据源代理机制：

注册分支事务

• XA start 需要 Xid 参数，这个 Xid 需要和 Seata 全局事务的 XID 和 BranchId 关联起来，以便由 TC 驱动 XA 分支的提交或回滚。目前 Seata 的 BranchId 是在分支注册时由TC统一生成的，所以在XA start之前就要注册分支事务。

• 将来一个可能的优化方向：把分支事务注册尽量延后。类似 AT 模式在本地事务提交之前才注册分支，避免分支执行失败情况下，没有意义的分支注册。这个优化方向需要 BranchId 生成机制的变化来配合。BranchId 不通过分支注册过程生成，而是生成后再带着 BranchId 去注册分支。

优劣

优：

• 事务的强一致性，满足ACID原则。
• 实现简单，无代码侵入

劣：

• 一阶段锁定的数据库资源要等到二阶段结束才释放，性能较差。（AT和TCC在一阶段结束就释放资源，性能有了优化）
• 依赖关系型数据库

AT模式

前提

• 支持本地 ACID 事务的关系型数据库。
• Java 应用，通过 JDBC 访问数据库。

整体机制

是2PC的演变：

• 一阶段：业务数据和undo-log（是DB的快照）都记录在同一个本地事务中本地提交。
  • 本地提交前先获取全局锁。
  • 本地提交后释放本地锁（本地的DB锁）和连接资源。
• 二阶段：
  • 全局提交：异步批量删除undo-log即可，能非常快地完成，然后释放全局锁。
  • 回滚：通过undo-log进行反向补偿。

写隔离

引入了全局锁，就能实现写隔离，不会出现脏写。

• 一阶段本地事务提交前，需要确保先拿到全局锁，拿不到就不能提交本地事务。
• 获取全局锁可重试，若超时则放弃，并回滚本地事务，释放本地锁。

整个过程全局锁在 tx1 结束前一直是被 tx1 持有的，所以不会脏写。

读隔离

在数据库本地事务隔离级别为读已提交 或以上时，Seata AT 模式的默认全局隔离级别是 读未提交（所以AT模式的数据一致性是弱一致的，属于最终一致，两阶段间数据属于软状态） 。若某些场景必须要求全局的读已提交 ，目前 Seata 的方式是通过 SELECT FOR UPDATE 语句的代理。

SELECT FOR UPDATE 的执行会申请全局锁 ，如果获取失败，则释放本地锁并重试。该过程的查询是阻塞的，直到拿到全局锁，即读取的相关数据是已提交的，才返回。

出于总体性能上的考虑，Seata 目前的方案并没有对所有 SELECT 语句都进行代理，仅针对 FOR UPDATE 的 SELECT 语句。

优劣

优：

• 一阶段直接提交本地事务，释放数据库资源，性能比较好
• 利用全局锁实现读写隔离（默认做不到读隔离，要实现就需要特地设置）
• 无代码侵入，框架自动完成，所以AT就是Automatic (Branch) Transaction Mode

劣：

• 两阶段之间属于软状态，属于最终一致
• 快照功能会影响性能，但比XA模式要好很多

TCC模式

Seata TCC 对原生TCC做了简单的封装和改造，所以原理与原生TCC一样。

Seata 的TCC 与AT非常类似，AT是底层DB层面做的封装，能自动完成，TCC则是把**自定义(自己写业务逻辑)**的分支事务纳入到全局事务的管理中，不依赖于底层DB资源的事务支持：

1. 一阶段 prepare 行为：调用自定义的 prepare 逻辑。
2. 二阶段 commit 行为：调用自定义的 commit 逻辑。
3. 二阶段 rollback 行为：调用自定义的 rollback 逻辑。

优劣

优：

• 一阶段直接提交事务，释放数据库资源，性能好
• 相比AT，无需生成快照，无需使用全局锁，性能最强
• 不依赖数据库事务，而是依赖补偿操作，可以用于非事务型数据库

劣：

• 有代码侵入，人工写逻辑，非常麻烦。原生TCC需要考虑周到的东西都需要解决。
• 软状态，数据是最终一致

Saga模式

原理与原生saga一样。

Saga的实现

目前seata Saga模式基于状态机引擎来实现：

• 通过状态图来定义服务调用的流程并生成 json 状态语言定义文件

• 状态图中一个节点可以是调用一个服务，节点可以配置它的补偿节点

• 状态图 json文件由状态机引擎驱动执行，出现异常时状态机引擎反向执行已成功节点对应的补偿节点将事务回滚（用户可自定义决定是否执行补偿事务）

• 可以实现服务编排需求，支持单项选择、并发、子流程、参数转换、参数映射、服务执行状态判断、异常捕获等功能

优劣

优：

• 事务参与者可以基于事件驱动实现异步调用，吞吐高
• 一阶段直接提交事务，无锁，性能好

劣：

• 软状态持续时间不确定，时效性差
• 没有锁，没有事务隔离，会有脏写

Seata XA、AT、TCC、Saga对比

分布式一致性算法

解决的问题是在分布式系统中如何就某个值（决议）达成一致，保证各节点中的数据一致。

一般通过使用复制日志来实现多副本状态机。每个Server存储着一份包括命令序列的日志文件，状态机会按顺序执行这些命令。因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态（日志），得到相同的输出。

Paxos（Basic-Paxos）算法

Paxos运行在允许节点故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用多数派 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos只需多数派同时认可该提案，就可在所有进程中达成一致。最多只针对一个确定的提案达成一致。

角色

• Proposer 提议者：提出提案 (Proposal)。Proposal信息包括提案编号 Proposal ID和提议值 Value。
• Acceptor 决策者：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数派Acceptor的accept，则称该Proposal被批准。
• Learner 学习者：不参与决策，从Proposer/Acceptor学习最新达成一致的提议值 Value。

在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。

3个阶段

• Prepare阶段：Proposer向Acceptor发出Prepare请求，Acceptor针对收到的Prepare请求进行Promise承诺。
  • Prepare: Proposer生成全局唯一且递增的Proposal ID，向所有Acceptor发送Prepare请求，这里无需携带提议值，只携带Proposal ID即可。
  • Promise: Acceptor收到Prepare请求后，做出“两个承诺，一个应答”。
    • 承诺1：只 accept Proposal ID大于决策者本地最大Proposal ID的Prepare请求；
    • 承诺2：只accept Proposal ID大于等于决策者本地最大Proposal ID的Propose请求;
    • 承诺2: 不再接受Proposal ID小于(注意是**<** )当前请求的Propose请求;
    • 应答: 不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个Proposal ID 和提议值，没有则返回空值。
• Accept阶段：Proposer收到多数Acceptor承诺的Promise后，向Acceptor发出Propose请求，Acceptor针对收到的Propose请求进行Accept处理。
  • Propose: Proposer 收到多数Acceptor的Promise应答后，从应答中选择Proposal ID最大的提议值，作为本次要发起的提案。如果所有应答的提议值均为空值，则可以自己随意决定提议值。然后连同当前Proposal ID，向所有Acceptor发送Propose请求。
  • Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提议值。
• Learn阶段：Proposer在收到多数Acceptor的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learner。

Multi-Paxos算法

Basic Paxos只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁（两个Proposer交替Prepare成功，而Accept失败）。

Multi-Paxos基于Basic Paxos做了两点改进：

• 针对每一个要确定的值，运行一次Paxos实例(Instance)，形成决议。每一个Paxos实例使用唯一的Instance ID标识。

• 在所有Proposer中选举一个Leader，由Leader唯一地提交Proposal给Acceptor进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将三阶段变为两阶段，提高效率。

Zab协议

这里讲的是zab在zookeeper中具体的实现，与论文的会有一些不同

基于ZAB协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。所有客户端写入数据都是写入到 **主进程（Leader）**中，**由 Leader 复制到备份进程（ Follower）**中，从而保证数据一致性。复制过程类似 2PC，ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交，大大减小了同步阻塞，也提高了可用性。

角色

• leader：

  • 整个集群只能有一个。负责所有写请求，当然也能提供读服务。为了保证写请求的顺序性。
  • 发起并维护与各Follwer及Observer间的心跳。
  • 所有的写操作必须要通过Leader完成再由Leader将写操作广播给其它服务器。

• follower:

  • 整个集群可以有多个，只能提供读服务。
  • 如果是写请求则转发给 Leader。
  • 参与leader选举，有选举权和被选举权和提案投票权。

• observer:

  • 不参与leader选举，也不参与“过半写成功”策略（无对proposal的投票权），仅提供读服务。
  • 在不影响写性能的情况下提高读性能。避免太多从节点参与过半写的过程，影响写性能，这样 Zookeeper 只要使用较少服务器的小集群就可以实现高性能了，如果要横向扩展的话，只需要增加 Observer 节点即可。
  • 虽然无投票权，但仍须同步Leader的数据从而在处理读请求时可以返回尽可能新的数据。

读写过程

写Leader

主要分为五步：

1. client向Leader发起写请求
2. Leader将写请求以Proposal的形式发给所有Follower（Leader并不需要得到Observer的ACK，即Observer无投票权）并等待ACK
3. Follower收到Leader的Proposal后返回ACK
4. Leader得到过半数的ACK（不是半数follower的ack，Leader对自己默认有一个ACK）后向所有的Follower和Observer发送Commmit
5. Leader将处理结果返回给client

写Follower/Observer

Follower/Observer均可接受写请求，但不能直接处理，需要转发给Leader处理，其它流程与直接写Leader无任何区别。

读操作

Leader/Follower/Observer都可直接处理读请求，从本地内存中读取数据并返回给client即可。

消息广播模式

整个 Zookeeper 就是在消息广播 和 崩溃恢复这两个模式之间切换。 当 Leader 可用时，进入消息广播模式，当 Leader 不可用时，进入崩溃恢复模式。

整个广播流程就是简化版的2PC，大体分为 3 步骤：

• 将数据都复制到 Follwer 中
• 等待 Follwer 回应 Ack，超过半数即成功
• 当超过半数成功回应，则执行 commit ，同时提交自己

一些细节：

• 实际上，在 Leader 和 Follwer 之间有一个消息队列，避免同步阻塞，实现异步解耦。
• Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一的 ID，称为ZXID，ZAB 协议按照 ZXID 顺序处理事务。
• zookeeper集群中为保证所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。
• 这是一种简化版的 2PC，不能解决单点问题。

崩溃恢复模式

一旦 Leader 宕机、服务刚启动或由于网络原因导致 Leader 与过半 Follower 失去联系，就会进入崩溃恢复模式，进行leader选举和数据同步。

ZAB 定义了 2 个原则：

1. ZAB 确保那些已在 Leader 提交的事务最终会被所有服务器提交。
2. ZAB 确保丢弃那些 Leader 已经复制数据给follower，但没有提交的事务。

为了满足上面2个原则，Leader 选举算法保证新选举出来的 Leader 拥有集群中所有机器编号（即该leader的ZXID是最大的）的事务，能保证新选举出来的 Leader 一定具有所有已经提交的提案。而且这么做的好处是：可省去 Leader 检查事务的提交和丢弃的操作。

数据同步

leader选举完之后，Leader 需要首先确认事务是否都已经被过半的 Follwer 提交了（是否完成了数据同步），才能进入消息广播模式，正式接收客户端请求。Leader 会将同步好的follower加入到可用列表，该follower的服务才可用，剩下未同步的会继续同步。

消息广播时，新加入的服务器会找到leader，并进行数据同步，然后就可提供服务了。

leader选举的4个阶段（粗略流程）

1. **Leader election 选举：**主要是节点之间进行信息同步，选择出一个leader。leader选举过程，electionEpoch自增，在选举的时候选票越大，越有可能成为leader
2. **Discovery 发现：**leader获取最新的消息。leader收集follower的选票，这个主要用来通过和leader的选票对比来确认follower需要同步的数据范围。选举出一个新的peerEpoch，主要用于防止旧的leader来进行提交操作
3. **Synchronization 同步：**leader将获取到的最新的数据同步到其他的从节点，并补全老数据，删除新数据。follower中的事务日志和leader保持一致的过程，就是依据follower和leader之间的选票进行，follower多的话则删除掉多余部分，follower少的话则补充，一旦对应不上则follower删除掉对不上的zxid及其之后的部分然后再从leader同步该部分之后的数据
4. **Broadcast 广播：**整个集群就可以对外提供读写服务，且zookeeper集群正常状态下处于该阶段。leader针对客户端的事务请求，然后提出一个议案，发给所有的follower，一旦过半的follower回复OK的话，leader就可以将该议案进行提交了，向所有follower发送提交该议案的请求，leader同时返回OK响应给客户端。

leader选举算法（源码详细流程）

到3.4.10版本为止，可选项有：

• 0 基于UDP的LeaderElection
• 1 基于UDP的FastLeaderElection
• 2 基于UDP和认证的FastLeaderElection
• 3 基于TCP的FastLeaderElection

在3.4.10版本中，默认值为3，也即基于TCP的FastLeaderElection。另外三种算法已经被弃用，并且有计划在之后的版本中将它们彻底删除而不再支持。

服务器状态

• LOOKING ：正在寻找 Leader。
• LEADING ：该节点已被选举为 Leader。
• FOLLOWING ：该节点为 Follower。
• OBSERVING ：该节点为 Observer，该节点不参与 Leader 选举。

myid

唯一标识每一台zk服务器

每个ZooKeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个ZooKeeper集群唯一的ID（整数）。例如，某ZooKeeper集群包含三台服务器，hostname分别为zoo1、zoo2和zoo3，其myid分别为1、2和3，则在配置文件中其ID与hostname必须一一对应。在该配置文件中，server.后面的数据即为myid。

server.1=zoo1:2888:3888
server.2=zoo2:2888:3888
server.3=zoo3:2888:3888

zxid

事务请求的唯一ID，Leader 处理或丢弃事务都是依赖着 zxid的，所以zxid的设计是有门道的。zxid是一个 64 位的整数。

• 低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。
• 高 32 位则代表了 Leader 上取出本地日志中最大事务 Proposal 的zxid，并从该zxid中解析出对应的 epoch 值，然后再对这个值加一。每次epoch变化，都将低32位的序号重置。
• 高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。也能让 Follwer 通过高 32 位识别不同的 Leader，简化了数据恢复流程。基于这样的策略：当 Follower 链接上 Leader 之后，Leader 会根据本地最后被提交的zxid和 Follower 上的zxid进行比对，比对结果要么回滚，要么和 Leader 同步。

选票数据结构

每个服务器在进行leader选举时，通用的选票数据封装成Notification对象，主要字段为：

• leader：要推举为leader的服务器的myid。

• zxid：要推举为leader的服务器的最大的zxid

• state：投票服务器的状态

• electionEpoch：代表第几届选举。每次leader选举（选举不一定能成功，还要再进行几轮）时，electionEpoch会+1，统计选票信息时，首先保证electionEpoch相同。

• sid（self_id）：投票服务器的myid

• peerEpoch：代表属于第几任leader的领导。每次leader选举成功之后，peerEpoch会+1，用来标记事务请求所属的轮次（很像zxid的高32位）。

除了上述对象，选举时还需要每个服务器保存它之前投票时的数据：

• logicalClock：
  • 每个服务器会维护一个自增的整数，表示这是该服务器发起的第几届投票。
  • 与electionEpoch是相同的东西，只不过名字不同，选举时会比较它俩的大小来确保选票必须是同一届的选举。
• proposedLeader：当前服务器最近一次投票时推举为leader的服务器myid
• proposedZxid：当前服务器最近一次投票时推举为leader的服务器zxid
• proposedEpoch：当前服务器最近一次投票时选票中的peerEpoch

投票流程

• 自增logicalClock选举轮次：zk规定所有有效的投票都必须在同一轮次中。每个服务器在开始新一轮投票时，自增自己的logicalClock。

• 发送选票：每个服务器最开始都是通过广播把票投给自己。

• 接收来自各个服务器的选票：

  • 服务器会从自己的recvqueue接收队列看自己是否获得外部选票。
  • 如果没有获得选票，则会判断自己是否发送完了选票（sendqueue是否为空），如果没发完就异步发送选票；如果发完，说明可能是与其他服务器断联了，需要重新连接。
  • 如果获得了选票，就往下走。

• 判断选举轮次：比较electionEpoch，统一当前是第几届选举，因为选举肯定要要求是同一届。(n=外部选票，this=自己服务器)

  • n.electionEpoch大于this.logicalClock：说明该服务器的选举轮次落后于其它服务器的选举轮次，将this.logicalClock更新为n.electionEpoch并清空自己收到的所有选票，然后再对比自己之前的选票与收到的选票进行**“选票pk”来确定是否需要变更自己的选票**，最终重新发送更新后的选票。

  • n.electionEpoch小于this.logicalClock：直接忽略该选票，继续处理下一个选票。

  • n.electionEpoch==this.logicalClock。认为是合法的选票，进行选票PK。

• “选票PK”：当且仅当以下三个条件满足其一时，将接受选票的提议，更新自己的选票，然后重新发送更新后的选票。简而言之：peerEpoch、zxid、leader越大，优先被选举为Leader。

  • n.peerEpoch > this.proposedEpoch
  • n.peerEpoch == this.proposedEpoch && n.zxid > this.proposedZxid
  • n.peerEpoch == this.proposedEpoch && n.zxid == this.proposedZxid && n.leader > this.proposedLeader

• 统计选票，检验leader是否有效：

  • 如果某个server得到半数以上的选票，就检验leader是否有效，检验通过则leader选出，选举结束。如果没过半或检验不通过，则继续接收其他选票。
  • 循环从recvqueue中取选票，满足以下条件之一时退出循环，说明没有服务器的选票能够推翻之前的结论，所以此时可以认为Leader是有效的。：
    • recvqueue 200ms内一直没有收到选票；
    • 收到一个更（第四声）新的选票（满足“选票pk”的条件，则说明提议更新）。

• 更新服务器状态：选举终止后。将服务器状态更新为LEADING或FOLLOWING。

集群启动时的leader选举过程

每个节点启动的时候状态都是LOOKING，要参与选主。在最开始，只有一台服务器Server1启动了，但其无法进行Leader选举，当第二台服务器Server2启动时，两台机器都试图找到Leader，于是进入Leader选举过程。

1. 自增logicalClock。
2. 每个Server发出一个投票。最开始Server1和Server2都会投自己作为Leader，选票用(leader，zxid，electionEpoch)来简单表示， 此时Server1的投票为(1，0，0)，Server2的投票为(2，0，0)，然后各自将这个选票广播给其他机器。
3. 接受来自各个服务器的选票。收到选票后先判断该选票的有效性：检查选票是否同届(electionEpoch)、是否来自LOOKING状态的服务器。
4. 选票pk。根据规则，server1要更新自己的选票为(2, 0, 0)，然后重新广播。 Server2则无须更新自己的选票，再次广播选票即可。
5. 统计选票、检验leader。判断是否已经有过半机器接受到相同的选票， Server1、Server2两台机器都接受了(2, 0, 0)的选票，因为200ms内都没有选票到达，leader检验通过，此时已经选出了Leader为Server2，选举结束。
6. 改变服务器状态。server1变为FOLLOWING，server2变为LEADING。

集群运行中出现服务不可用时leader选举过程

当leader宕机或leader不可用或超半数服务器与leader不同步等情况，整个集群无法提供服务，将触发选主流程，和启动时选主流程几乎一致。

1. 变更状态。Leader挂后，非Observer都变为LOOKING，然后开始进入Leader选举过程。
2. 自增logicalClock。
3. 每个Server会发出一个投票。在运行期间，每个服务器上的ZXID和electionEpoch可能不同，在第一轮投票中，Server1和Server2都会投自己，假设产生投票(1, 900, 50)， (2, 500, 100)，然后各自将投票发送给集群中所有机器。
4. 接收来自各个服务器的选票。与启动时过程相同。
5. 选票PK。与启动时过程相同，根据规则，server2的选票要变更（如果是多台服务器，可能需要多次变更选票）。
6. 统计选票、检验leader。与启动时过程相同，最终Server1成为Leader。
7. 改变服务器状态。与启动时过程相同。

新选举 leader 后怎么进行数据同步？

写数据是由 leader 负责的，leader 会将每个请求分配一个 ZXID，按顺序放入一个fifo队列中，依次执行，每次 leader 执行完一个请求后，会记录下执行的这个 ZXID。这个队列中最大的 ZXID 记为 maxZXID，最小的 ZXID 记为minZXID。

将 Observer 和 follower 中最新的 ZXID 记为lastSyncZXID（每个服务器都有）。每个请求都会封装到proposal对象中。

数据同步有4种情况：

• 差异化同步

• • 触发条件：minZXID < lastSyncZXID < maxZXID

  • 同步过程：

  • • leader 向 Observer 和 follower 发送 DIFF 指令，开始差异化同步。
    • 把差异数据封装成若干个 proposal 发送给 Observer 和 follower，针对每个Proposal，Leader都会发送PROPOSAL内容数据包和COMMIT指令数据包两个包 , 全部发送完后leader发送NEWLEADER指令。
    • Observer和follower收到newleader指令后返回ACK表示同步完成
    • 只要leader收到过半的ACK就发送UPTODATE 命令通知Observer和follower该集群已完成数据同步，可以对外提供服务。返回ack的服务器就加入可用列表，其余的继续进行数据同步。

• 回滚同步

• • 触发条件：maxZXID < lastSyncZXID
  • 例子： a，b，c中a是leader，此时队列maxZXID=100，a 收到请求，该 ZXID=101，但还没来得及同步数据 a 就挂了（zxid=101），b 变为leader（zxid=100），然后 a 恢复了，此时就需要 a 回滚超出的这部分数据，因为这些数据还没过半写，不被认可，没被commit。
  • 同步过程：leader发送 TRUNC 命令让其直接回滚到 maxZXID。

• 回滚+差异化同步

• • 触发条件：如果Leader刚生成一个 proposal，还没有来得及同步就宕机，重新选举之后作为Follower，但是新Leader没有这个没被commit的proposal数据
  • 例子： a，b，c三台服务服务器 a是leader，此时队列maxZXID=100，a 收到请求，该 ZXID 为101，还没来得及发送同步数据 a 就挂了，b 变为leader，b 又处理了3个请求（maxZXID=103），然后 a 恢复了，此时就需要 a 先将之前 ZXID 为101的数据回滚，再进行差异化同步
  • 同步过程：Observer 和 follower 先进行回滚同步，再进行差异化同步

• 全量同步

• • 触发条件：

  • • lastSyncZXID < minZXID
    • Leader上没有缓存队列，并且lastSyncZXID!=maxZXID
• • 同步过程：leader 向 Observer 和 follower 发送SNAP命令，使用快照进行数据全量同步

paxos和zab的关系？

paxos更通用，zab是paxos的具体实现。

zab怎么解决脑裂问题？

ZooKeeper 在leader选举时使用的是过半机制，少于等于一半是不会触发选主流程的、选举时也不能推举出leader，所以有过半机制就不可能出现脑裂。脑裂（软状态）时产生的一些数据因为未能过半写成功是不会被commit的，网络恢复后这部分数据会被丢弃，最终也就不会脑裂（最终一致）。

Raft算法

不同于Paxos直接从分布式一致性问题出发推导出来，Raft则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。

Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题: **Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)**等。

同时，Raft使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。

角色

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。任意时刻最多只有一个Leader。
• Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。Follower 是被动的，不会发送任何请求，只是响应来自 Leader 和 Candidate 的请求。
• Candidate：Leader选举过程中的临时角色。正常工作期间只有Leader和Followers。

Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息，它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

任期

Raft算法将时间划分为任意长度的任期(term)，每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号。如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值。如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower。如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求。

日志

• entry：每一个事件封装为 entry，只有 Leader 可以创建 entry。entry 的内容为<term,index,cmd>，其中 cmd 是可以应用到状态机的操作。
• log：由 entry 构成的数组，每一个 entry 中的 index代表其在log中的索引。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。

Leader选举

可视化网站：https://raft.github.io/

• 通过心跳机制来触发 Leader 的选举。Leader 会向所有的 Follower 发送心跳来声明自己的 Leader 身份。

  • 如果一个 Follower 在计时内没有收到心跳信息，它就认为此时没有可用的 Leader，并且开始进行一次选举以选出一个新的 Leader。

  • 如果follower能收到来自 Leader 或者 Candidate 的有效信息，那么它会一直保持为 Follower ，并且刷新自己的 electionElapsed，重新计时。

• 新一轮选举开始，Follower 会自增自己的 term 号并转换状态为 Candidate，向所有节点发起 RequestVote RPC 请求， Candidate 的状态会持续到以下情况发生：

  • 收到了来自集群内的多数选票（N/2+1），赢得选举，自己成为 Leader。

  • 其他节点赢得选举。

  • 一轮选举结束，无人胜出，继续选举。raft 使用了随机的选举超时时间来避免无限选举下去情况。每一个 Candidate 在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个节点发起选举能分散开来，在绝大多数情况下只有一个服务器会率先超时，在其他服务器超时之前赢得选举。

• 在 Candidate 等待选票的时候，它可能收到其他节点声明自己是 Leader 的心跳，此时有两种情况：

  • 该 Leader 的 term 号大于等于自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower。

  • 该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term。

日志同步

• 一旦选出了 Leader，它就开始接受客户端的请求。Leader 收到客户端请求后，会生成一个 entry，将这个 entry 添加到自己的日志末尾，然后向所有follower广播该 entry。

  • 如果 Follower 接受该 entry，则会将 entry 添加到自己的日志末尾，返回ack。某些Follower可能没有成功的复制日志，Leader会无限地重试 AppendEntries RPC直到所有的Followers最终存储了所有的entry。
  • 如果 Leader 收到了多数的成功响应，Leader 可将这个 entry 应用到自己的状态机中，可认为这该 entry 是 committed 的，并向客户端返回执行结果。

  

• Raft日志同步拥有2个特性：

  • 若不同日志中的两个entry有着相同的index和term，则它们所存储的cmd是相同的。因为entry只能由leader创建，且Leader在一个term内在给定的一个log index最多创建一条entry，同时该entry在日志中的位置不会改变。
  • 若不同日志中的两个entry有着相同的index和term，则它们之前的所有entry都是完全一样的。因为 AppendEntries 会做一致性检查：Leader会把新entry紧接着之前的entry的index和term都包含在里面。如果Follower没有在它的日志中找到index和term都相同的日志，它就会拒绝新的entry。

• 一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。Leader通过强制Follower复制leader的日志来处理日志的不一致，Follower上的不一致的日志会被Leader的日志覆盖。Leader会从后往前逐个entry尝试，每次AppendEntries失败后尝试前一个entry，直到成功找到每个Follower的日志都一致的index，就可向后逐条覆盖Follower在该位置之后的条目。

  

安全性

• 选举限制：

  • Leader 需要保证自己存储全部已经提交的entry。这样才可以使entry只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的entry。

  • 拥有最新的已提交的entry的candidate才能获得投票。每个 Candidate 发送 RequestVoteRPC 时，都会带上自己的最后一个 entry 的信息。所有节点收到投票信息时，会与该 entry 进行比较，如果发现自己的entry还要新，则拒绝投票给该 Candidate。

• 节点崩溃：

  • 如果 Leader 崩溃（或集群中没有leader），在新leader选举出来之前整个集群对外不可用。
  • 如果 Follower 和 Candidate 崩溃，leader就无限重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。

• 时间与可用性：

  raft 的要求之一就是安全性不依赖于时间，系统不能仅仅因为一些事件发生得比预想的快一些或者慢一些就产生错误。为保证此要求，最好能满足以下的时间条件：

  broadcastTime << electionTimeout << MTBF

  • broadcastTime：leader 广播消息的平均响应时间；
  • electionTimeout：选举超时时间；
  • MTBF(mean time between failures)：单台机器的平均健康时间；

  一般来说，broadcastTime 一般为 0.5～20ms，electionTimeout 可以设置为 10～500ms，MTBF 一般为一两个月。

日志压缩

• 在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行redo，影响可用性。Raft采用对整个系统进行snapshot来解决。

• 每个副本只能对自己已经提交的日志记录进行snapshot。

• 当Follower的日志落后太多或新加一台机器时，Leader会使用InstalledSnapshot RPC将snapshot发给Follower。

• 做snapshot既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要redo大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。（redis就是用了raft算法，redis的主从同步该就是这些流程）

raft如何解决脑裂问题？

paxos（包括zab）和raft解决脑裂都是使用了过半机制/多数派机制。

脑裂导致两个leader A和D，因为分区2无法得到多数派的ACK，数据同步失败，而分区1会成功。当网络恢复，集群不再分区时，raft会有如下操作：

• leaderD发现自己的Term号小于LeaderA，会自动下台(step down)成为follower。

• 前分区2中的所有节点会回滚roll back自己的数据日志，并同步新leader的log日志。

• 集群最终达到整体一致，集群存在唯一leader（节点A）。

Zookeeper

Zookeeper可以实现**「数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列」等功能。最常用的一个使用场景就是作为「注册中心」，生产者将自己提供的服务注册到 Zookeeper，然后消费者从 Zookeeper 中「拿到生产者的服务列表信息」，然后再去「调用生产者」**的内容数据，比如 Dubbo，Kafka 都是使用 Zookeeper 作为注册中心的。

ZK的数据结构模型

• data model 数据模型：

  • 层次化的多叉树结构，每个节点都可存储数据（数字、字符串或二级制序列），每个节点还可以拥有多个子节点。
  • 名称空间与unix文件系统的名称空间非常相似。根节点用 “ / ” 表示，如果节点有子节点，则无法删除它。

  

znode

是 ZooKeeper 中数据的最小单元。每个 znode 都唯一的路径标识。

ZooKeeper 主要是用来协调服务的，不是用来存储业务数据的，所以不要放比较大的数据在 znode 上，ZooKeeper 给出的上限是每个结点的数据大小最大是 1M。

• znode的4种类型：

  • 持久节点（PERSISTENT） ：一旦创建就一直存在即使 ZooKeeper 集群宕机，直到将其删除。

  • 临时节点（EPHEMERAL） ：生命周期与 客户端会话（session） 绑定，会话消失则节点消失 。只能做叶子节点 ，不能创建子节点。

  • 持久顺序节点（PERSISTENT_SEQUENTIAL） ：除具有持久节点的特性外， 子节点的名称还具有顺序性。创建子节点时会自动在节点名称后添加一个由10位数字组成的数字串，从1开始计数。如 /node1/a0000000001 、/node1/a0000000002 。

  • 临时顺序节点（EPHEMERAL_SEQUENTIAL） ：除具备临时节点的特性外，子节点的名称还具有顺序性。

• znode数据结构与内容：2部分组成

  • data ： 节点存放的数据的具体内容
  • stat ：状态信息
    • cZxid ：create ZXID，该数据节点被创建时的事务id
    • idctim：ecreate time，该节点的创建时间
    • mZxid： modified ZXID，该节点最终一次更新时的事务 id
    • mtime：modified time，该节点最后一次的更新时间
    • pZxid：该节点的子节点列表最后一次修改时的事务 id，只有子节点列表变更才会更新pZxid，子节点内容变更不会更新
    • cversion：子节点版本号，当前节点的子节点每次变化时值增加 1
    • dataVersion：数据节点内容版本号，节点创建时为 0，每更新一次节点内容(不管内容有无变化)该版本号的值增加 1
    • aclVersion：节点的 ACL 版本号，表示该节点 ACL 信息变更次数
    • ephemeralOwner：创建该临时节点的会话的 sessionId；如果当前节点为持久节点，则 ephemeralOwner=0
    • dataLength：数据节点内容长度
    • numChildren：当前节点的子节点个数

  [zk: 127.0.0.1:2181(CONNECTED) 6] get /dubbo
  # 该数据节点关联的数据内容为abc
  abc
  # 下面是该数据节点的一些状态信息，其实就是 Stat 对象的格式化输出
  cZxid = 0x2
  ctime = Tue Nov 27 11:05:34 CST 2018
  mZxid = 0x2
  mtime = Tue Nov 27 11:05:34 CST 2018
  pZxid = 0x3
  cversion = 1
  dataVersion = 0
  aclVersion = 0
  ephemeralOwner = 0x0
  dataLength = 0
  numChildren = 1
  

  ACL 权限控制

  采用 ACL（AccessControlLists）策略来对znode进行权限控制，类似于 UNIX 文件系统的权限控制，有 5 种：

  • CREATE : 能创建子节点（不是对该节点）
  • READ ：能读取节点数据和其子节点
  • WRITE : 能写入/更新节点数据
  • DELETE : 能删除子节点
  • ADMIN : 能设置节点 ACL 的权限

  对于身份认证，提供了以下几种方式：

  • world： 默认，所有用户都可无条件访问。
  • auth：不使用任何 id，代表任何已认证的用户。
  • digest： username:password的认证方式： 。
  • ip: 对指定 ip 进行限制。

Watcher 事件监听机制

允许用户在指定节点上注册 Watcher，当一些特定事件触发时，ZooKeeper 服务端会将事件通知到注册了watcher的客户端，该机制是 ZooKeeper 实现分布式协调服务的重要特性。

四个特性：

• 一次性：某个Wather一旦触发，Zookeeper就会将它移除，如果还要继续监听这个节点，就需要我们在客户端的监听回调中再次对该节点设置监听（设置为True），否则客户端只能接收到一次该节点的变更通知。
• 客户端串行：客户端的Wather回调处理是串行处理的，所以不要因为一个Wather而将整个客户端阻塞了。
• 轻量：Wather通知的单位是WathedEvent，只包含通知状态、事件类型和节点路径，不包含具体的事件内容，具体的事件内容需要客户端主动去重新获取数据。
• 异步： Zookeeper服务端发送watcher的通知事件到客户端是异步的，不能期望能够监控到节点每次的变化，Zookeeper只能保证最终一致性，而无法保证强一致性。

session 会话

zk客户端和服务端是通过 TCP 长连接 维持会话机制，只要在sessionTimeout内能够重新连接上集群中任意一台服务器，那么之前创建的会话仍然有效。会话还有对应的事件，比如 CONNECTION_LOSS 连接丢失事件 、SESSION_MOVED 会话转移事件 、SESSION_EXPIRED 会话超时失效事件 ，这些都是能被监听的。

集群架构

• 主要采用主从模式架构，核心就是ZAB协议。

• 只要过半的机器可用，整个集群都是可用的。

• 建议集群节点个数为奇数。

• client与server建立TCP连接来通信。

ZooKeeper 集群为啥最好奇数台？

其实是一个简单的数学问题。如果剩下的可用的服务器个数大于宕掉的个数的话整个 ZooKeeper 依然可用的。假如集群中有 n 台服务器，所以剩下的个数必须要大于等于n/2+1。总数2n和2n-1可容忍宕掉的数量是一样的，都是 n-1，所以没必要多加一台。