Paxos

概念

1.  作用：解决在分布式情况下，如何就某个值达成一致的问题。

2. 包含 Basic Paxos 和 Multi-Paxos

2. 基于两阶段提交: 准备阶段 prepare，接受阶段 accept

3. 角色： 提议者（proposer）、接受者（accepter）、学习者（learner）

4. 动作：发送准备（prepare）请求（携带提案编号）、返回准备响应（promise 应答）；发送接受（propose）请求，接受（accept);学习（learner）

过程

Paxos 算法流程中的每条消息描述如下：

1.    Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。

2.    Promise: Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”。

两个承诺：

    a.    不再接受 Proposal ID 小于等于（注意：这里是<= ）当前请求的 Prepare 请求。

    b.    不再接受 Proposal ID 小于（注意：这里是< ）当前请求的 Propose 请求。

一个应答：

    c.    不违背以前做出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。

3.    Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。

4.    Accept: Acceptor 收到 Propose 请求后，在不违背自己之前做出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。

5.    Learn: Proposer 收到多数 Acceptors 的 Accept 后，决议形成，将形成的决议发送给所有 Learners。

问题

1. 在网络复杂的情况下，一个应用 Paxos 算法的分布式系统，可能很久无法收敛，甚至陷入活锁的情况（如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到 大多数准备响应，协商失败，需要重新协商）

2. 两轮 RPC 通讯(准备阶段和接受阶段)往返消息多、耗性能、延迟大。

Multi-Paxos

兰伯特提到的 Multi-Paxos 是一种思想，不是算法 - 通过引入领导者解决上述两个问题

Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)

1. 领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况

2. 采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机 制，优化 Basic Paxos 执行

准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。

Ratf

Raft 协议是分布式里面最常用的共识算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致性。协议主要包含三个部分：领导者选举、日志复制、成员变更

Leader election

• 节点间通讯

• 请求投票(RequestVote)RPC，是由候选人在选举期间发起，通知各节点进行投票;

• 日志复制(AppendEntries)RPC，是由领导者发起，用来复制日志和提供心跳消息。

• 任期

• 选举规则多数选票规则一个节点同一任期只会投一票当任期编号相同时，日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值 更大，索引号更大)，拒绝投票给日志完整性低的候选人

• 选举失败-随机超时时间

Raft 算法和兰伯特的 Multi-Paxos 不同之处，主要有 2 点。首先，在 Raft 中，不是所 有节点都能当选领导者，只有日志最完整的节点，才能当选领导者;其次，在 Raft 中， 日志必须是连续的。

Log Replication

• 格式：指令、索引值、任期编号

• 优化的两阶段提交：第一阶段领导者通过日志复制 RPC 消息将日志项复制到集群其它节点领导者收到大多数“复制成功”的响应，将日志项提交到他的状态机，并返回成功给客户端。如果没有收到大多数“复制成功”响应，则返回失败。

• 优化：领导者的心跳或者日志复制消息包含了当前最大的会被提交的日志索引值，其它节点根据这个值提交日志

日志一致性：倒排检查注意：在 Raft 中日志必须是连续的

成员变更

TODO：进一步理解可能导致多主的情况，解决方式一次变更一个节点。

拓展

在实际场景中，我们一般需要根据场景特点，在一致性强度和实现复杂度之 间进行权衡。比如 Consul 实现了三种一致性模型。

• default:客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时(在 leader leasing 时间内)，返回本地数据给客户端，否则返回错误给客户端。在这种情 况下，客户端是可能读到旧数据的，比如此时发生了网络分区错误，新领导者已经更新 过数据，但因为网络故障，旧领导者未更新数据也未退位，仍处于稳定状态。

• consistent:客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是 领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读 到的都是最新数据。

• stale:从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据。

参考

https://blog.csdn.net/mydriverc2/article/details/108165552

https://zhuanlan.zhihu.com/p/27207160