面试知识点——共识算法

Paxos

Paxos最主要的贡献是解决了在不可靠通信和可能失效的节点中达成共识的问题。

1. Paxos算法的基本概念

Paxos算法由三种角色组成：

1. 提议者（Proposer）：提出提议（Proposal）。
2. 接受者（Acceptor）：投票决定是否接受一个提议。
3. 学习者（Learner）：学习最终被选定的提议。

2. Paxos的基本流程

Paxos可以分为两个主要阶段：准备阶段（Prepare Phase）和接受阶段（Accept Phase）。

准备阶段

1. 提议者选择提议编号 n，并向一组接受者发送准备请求（Prepare Request）。
2. 接受者收到准备请求后，如果 n 大于其已经响应过的所有编号，则承诺不再接受编号小于 n 的提议，并回复其最后接受的提议（如果有）及其编号。

接受阶段

1. 提议者收到足够数量的承诺回复后，可以发出一个带有编号 n 的提议请求（Propose Request），提议内容可以是接受者回复中编号最高的已接受提议的值，或者是一个新值（如果没有已接受的提议）。
2. 接受者收到提议请求后，如果尚未对编号大于或等于 n 的准备请求作出承诺，则接受该提议。

决策达成

一旦某个提议被多数接受者接受，那么这个提议就是被选定的提议。学习者可以通过接受者的消息得知最终选定的提议。

3. Paxos的特性保证了一致性

• 安全性：即使在网络分区或节点失效的情况下，Paxos仍能确保不会出现冲突的决策，只有一个值会被选定。
• 活性：在某些条件下，Paxos可能会陷入无法达成决定的状态（如不断有新的提议者尝试提出新的提议），但在实际应用中，通常通过引入超时和领导者选举等机制来解决。故如果多数Acceptors活着，最终会选定一个值。

4. 活锁问题

Paxos可能出现活锁，即多个Proposers不断提出更高编号的提案，导致没有值被选定。解决方法包括:

• 选举一个主Proposer。
• 引入随机延迟。

Raft

Raft是一种用于管理分布式系统中一致性的共识算法。它旨在简化分布式系统的实现，使得开发者更容易理解和实现一致性。以下是Raft的几个关键特点和工作原理：

1. 主要角色

Raft算法定义了三种角色：

• Leader：负责处理所有的客户端请求，并将日志条目复制到其他节点（Followers）。
• Follower：被动响应Leader的请求，接收和应用Leader发送的日志条目。
• Candidate：在Leader失效时，节点可以转变为Candidate，发起Leader选举。

2. 工作原理

Raft的工作流程可以分为以下几个阶段：

a. 选举阶段

• 当集群启动或Leader失效时，Follower节点会在一定时间内未收到心跳信号后，转变为Candidate，发起选举。
• Candidate节点会向其他节点发送投票请求，收集票数，达到多数票则成为新的Leader。

b. 日志复制

• Leader接收客户端请求后，将其转化为日志条目，添加到本地日志中。
• Leader将该日志条目复制到所有Followers。
• Followers在成功接收并应用日志后，会向Leader发送确认。
• Leader在收到足够的确认后，将该条目标记为已提交，并通知所有Followers。

c. 状态应用

• 一旦日志条目被提交，Leader会通知Followers应用该条目到状态机中。

3. 特点

• 易于理解：Raft的设计目标之一是提供一种比Paxos更易于理解的算法。
• 强一致性：Raft确保所有节点在相同的时间内应用日志条目，保持数据一致性。
• 高可用性：通过选举机制，Raft能够快速恢复Leader，确保系统可用性。

4. 随机超时机制

随机超时：每个Follower节点在未收到Leader的心跳信号时，会设置一个随机的超时时间。这意味着不同节点的超时时间不同。
先发起投票：一旦某个节点的超时计时器到期，它会转变为Candidate并发起选举。这种机制确保了在网络通畅的情况下，只有一个节点会在特定时刻发起投票请求。

5. 应用场景

Raft广泛应用于需要强一致性和高可用性的分布式系统中，例如数据库、配置管理系统和分布式文件系统等。

ZAB

ZAB（Zookeeper Atomic Broadcast）是Apache ZooKeeper中用于实现高可用性和一致性的协议。它主要用于确保在分布式系统中，所有节点都能达成一致的状态。以下是ZAB的几个关键特点和工作原理：

1. 主要组成部分

• Leader：负责处理所有的写请求，并将更新的状态广播给Follower。
• Follower：接收Leader的更新，并将其应用于本地状态。
• Observer：一种特殊类型的节点，可以接收Leader的更新，但不参与投票。

2. 工作原理

• 选举过程：ZAB首先进行Leader选举，确保有一个节点成为Leader。
• 广播：Leader接收客户端的写请求后，将请求转化为事务，并将其广播给所有的Follower。
• 确认：Follower在处理完Leader的请求后，会向Leader发送确认消息。Leader在收到足够的确认后，才会将该事务标记为已提交。
• 数据一致性：所有Follower在接收到Leader的提交后，都会更新自己的状态，确保数据一致性。

3. 特点

• 高可用性：通过Leader和Follower的角色分配，ZAB能够在Leader故障时快速选举新的Leader，确保系统可用。
• 顺序一致性：所有节点按照相同的顺序应用更新，确保一致性。
• 容错性：只要大多数节点（超过半数）可用，ZAB就能继续操作，提供强一致性。

4. 应用场景

ZAB是ZooKeeper的核心协议，广泛用于需要协调和一致性服务的分布式应用，如配置管理、分布式锁、命名服务等。

总之，ZAB协议通过Leader-Follower模型和原子广播机制有效地解决了分布式系统中的一致性问题，确保了高可用性和数据一致性。