浅谈分布式共识算法概念与演进

分布式共识是指在分布式系统中，多个节点之间达成共识的过程。

分布式共识的意义在于确保分布式系统中各个节点之间的数据一致性。通过分布式共识算法，可以使得多个节点针对某个状态达成一致，从而保证系统中各个节点之间的数据一致性。这对于构建高可用性、高性能、可扩展性的分布式系统至关重要。

分布式系统中的一致性和共识

在分布式系统中，一致性和共识是两个重要的概念。

一致性是指分布式系统中的多个服务节点，给定一系列的操作，在约定协议的保障下，使它们对外界呈现的状态是一致的。换句话说，也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案（Proposal）达成一致 。

而共识则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。因此，一致性描述的是结果状态，共识则是一种手段 。

分布式共识的算法与思想

随着分布式系统的普及，分布式共识算法成为了分布式系统中必不可少的一部分。而经典的分布式共识算法也不断衍生出了几种不同的类型。

（1）Paxos算法

Paxos算法是一种基于消息传递且具有高度容错性的分布式共识算法。它能够确保在存在网络分区或节点失效情况下，仍能够达成正确的共识结果。Paxos算法的核心思想是通过多轮的投票来达成一致意见。每一轮投票中，节点会对一个提案进行投票，当达到法定人数时，便可以认为该提案获得了通过。

Multi-Paxos是Basic Paxos的改进版，是将Basic Paxos实例执行多次，对一系列值达成共识，同时它也是一部分分布式共识算法的统称，可以说是一种思想。

（2）ZAB算法

ZAB算法是Zookeeper Atomic Broadcast的缩写，是Zookeeper保证数据一致性的核心算法。ZAB算法是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议 。

ZAB算法的主要作用是保证分布式系统中各个节点之间的数据一致性。在ZAB算法中，有两种角色：Leader和Follower。Leader负责处理客户端请求，并将数据同步到所有Follower节点上；Follower节点则负责接收Leader节点的数据，并将其写入本地磁盘。当Leader节点发生故障时，Follower节点会根据ZAB算法选举出新的Leader节点，并重新同步数据 。

（3）Raft算法

Raft算法是Paxos算法的一种改进版，具体的说是基于Multi-Paxos，其主要思想是将多个领导者（Leader）缩减为一个主节点（Leader），同时将投票阶段拆分为多个步骤，使得系统更容易理解和维护。Raft算法通过选举产生主节点，主节点负责管理日志的复制和一致性验证等工作，而其他节点只负责接收主节点发送的消息并进行响应。

（4）Gossip协议

Gossip协议是一种基于信息传播的分布式共识算法。它通过节点之间的互相交流来达成共识，并将共识结果广播给其他节点。与Paxos和Raft等算法不同，Gossip协议不需要固定的领导节点，也没有明确的提案过程，而是通过对节点之间消息的传播来实现共识。

以上几种算法的诞生过程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vJND2ELe-1693061330974)(浅谈分布式共识算法体系与演进.assets/image-20230826192159451.png)]

不同分布式共识算法的简要分析

Paxos

Paxos算法是一种解决分布式系统一致性的经典算法。它是在1990年代由莱斯利·兰波特（Leslie Lamport）提出的一种分布式一致性协议，用于在分布式系统中实现一致性决策。

Paxos算法的核心思想是，在一个分布式系统中，通过多数派节点的共同决策，确保系统在发生故障或网络故障的情况下仍然能够达成一致的状态。主要分为以下几个步骤：

• 阶段一（Promise）：

每个节点都会接受来自其他节点的请求，并且承诺不会接受任何与之前承诺的提案具有相同编号的提案。这个阶段的目标是确保每个节点发出的提案都具有唯一的编号，从而避免系统中的矛盾决策。

• 阶段二（Accept）：

在这个阶段，提出提案的节点会选择一个编号，并向所有其他节点发送提案。只有当多数派节点接受了该提案，该提案才会被认为是一致同意的决策。

• 阶段三（Decide）：

一旦提案被多数派节点接受，这些节点就会做出最终的决定，并将该提案应用到系统中。这个阶段的目标是确保所有节点都应用相同的决策，从而保证系统的一致性。

Paxos算法的关键在于，它通过多数派节点的共同决策来确保系统的一致性。即使部分节点发生故障或网络故障，只要多数派节点正常工作，系统仍然能够达成一致的状态。

ZAB

ZAB（ZooKeeper Atomic Broadcast）算法是一种基于消息传递的分布式一致性协议，常用于实现分布式系统的数据一致性。它是ZooKeeper的核心算法，为分布式应用提供了可靠的状态同步服务。

ZAB算法的核心思想是，通过消息广播的方式在分布式系统中实现一致性决策。它遵循以下主要步骤：

• 消息广播：每个节点都会接收来自其他节点的消息，并将其广播给其他节点。消息包括提议（proposal）和确认（acknowledgement）。
• 提议：当一个节点需要将一个变化（如更新或删除操作）通知给其他节点时，它会发起一个提议，并发送给其他节点。提议包含操作（operation）和序列号（sequence number）。序列号用于保证消息的顺序性。
• 确认：当一个节点接收到一个提议时，它会执行该提议的操作，并回复一个确认消息给发送提议的节点。确认消息包含操作的结果（如成功或失败）和接收到的下一个期望的序列号。
• 投票：当一个节点收到来自其他节点的提议时，它会为该提议进行投票。投票结果取决于提议的操作是否与本地节点的状态一致。如果一致，节点就会投票同意，否则就会投票拒绝。投票结果会随着确认消息返回给发送提议的节点。
• 决策：当一个节点收集到足够多的投票时，就会做出决策。决策的结果取决于多数派节点的投票结果。如果多数派节点投票同意，那么提议就会被执行，否则提议就会被拒绝。

Raft

Raft算法是一种基于消息传递的分布式一致性协议，与Paxos和ZAB算法类似，它被设计用来在分布式系统中实现一致性的决策。Raft算法通过强化领导权（leader election）和日志复制（log replication）来解决一致性问题的同时，也提供了更为清晰和易于理解的算法实现。

Raft算法的核心思想可以被分解为三个组成部分：

1. 领导权（Leadership）：Raft算法通过强化领导权来解决一致性问题。在Raft中，一个节点可以被选举为领导者（leader），其他节点则成为追随者（follower）。领导者负责处理所有客户端的请求，并将新的日志条目附加到系统的末尾。追随者则仅在领导者出现故障时才会开始运行，以避免不必要的资源浪费。
2. 日志复制（Log Replication）：Raft算法确保领导者将每个日志条目广播给所有追随者，并且每个节点都会保存一个相同的数据副本。每当领导者收到一个新日志条目时，它会将该条目附加到自己的日志中，并等待足够多的节点确认该条目已经被接收。一旦领导者收到大多数节点的确认，它就会将该条目标记为已提交，并通知客户端。
3. 安全性和一致性（Safety and Consistency）：Raft算法确保了一致性的安全性，即任何两个有效的领导者都不会做出相互矛盾的决策。此外，Raft还确保了一旦一个日志条目被标记为已提交，那么所有节点都将具有相同的数据副本。这通过一种称为持久性存储（persistent storage）的机制实现，它记录了所有已经提交的日志条目。

Gossip

Gossip协议的实现过程如下：

1. 每个节点都有一个邻居节点列表，每个邻居节点都是与该节点直接相连的其他节点。
2. 随机选择一个节点作为源节点，该节点向其邻居节点发送一条消息。
3. 每个接收消息的节点将消息转发给其邻居节点的概率正比于节点度数（与该节点直接相连的邻居节点数）。
4. 每个节点重复执行上述过程，直到所有节点都收到消息。

Gossip协议的优势在于它可以实现负载均衡和数据复制，提高系统的可靠性和性能。它还可以用于分布式计算和分布式存储等分布式系统。

总结

分布式共识中达成共识的手段几乎都是投票机制，使用投票机制的主要原因是为了在多个节点之间达成一致的决定，可以有效帮助算法在分布式环境中解决冲突和分歧，确保所有节点都能够达成共识。

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表