526互联

共识算法-Paxos

发布时间 2023-08-16 10:37:06作者: Angelia-Wang

共识算法引入

分布式：同一个应用的不同模块分别部署，它们之间通过约定的通信协议进行交互。

集群：将一个应用部署到多态服务器上，它们拥有相同的功能，所有成员都是平等的。

分布式和集群并不冲突，分布式架构也可用集群的方式部署。在后端部署过程中，“分布式+集群”的部署方式也很常见。

? 将订单服务拆分为 库存服务 + 支付服务，同时为提升并发处理能力，将库存服务和支付服务采用集群部署，并添加负载均衡策略。则创建一个订单时，订单服务根据负载均衡策略，将请求分发给库存服务集群和支付服务集群中的任意成员完成。

实际场景中，很多公司的集群部署只针对应用模块(库存服务, 支付服务)，而不针对背后的数据管理服务 (数据库)。因此应用模块集群中的每个节点都会访问同一个数据库服务，此时数据库服务是并不满足容错性的。

要让数据库具有容错性，在把数据库扩展到集群的同时，还需解决数据对齐的问题。—— 复制状态机

复制状态机 (Replicated state machine)：相同的初始状态 + 相同的输入 = 相同的结束状态。

多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。

要实现复制状态机，需要一个保证协议来保证一组成员以相同顺序执行一组命令，从而能从一个相同的初始状态，达到相同的结束状态。这个保证协议就是 共识算法，实现日志的同步复制（首先将命令存入日志，并保证所有的日志具有相同顺序的相同命令），来让所有成员的状态机都能以相同的顺序处理命令。

image-20230816040525205

系统这样运行：

如果一个客户端想要状态机执行一条命令，它先会将命令传给其中一个服务器。服务器会记录这条命令，并将它传递给其他的服务器。其他的服务器都会各自记录这条命令，一旦命令在所有的日志中都保存有副本，那么它就可以传递给状态机供执行。我们有时会使用词语 “应用（apply）” 代表命令真实执行的情况，一旦其中一台状态机执行了命令，那么它的结果就会被返回到客户端。

共识模块最关键的特性是：对于一个系统来说，只要有大多数的服务器是可用的，那么它就可以提供所有的服务。

  • 共识算法运行在集群之上，单个成员谈不上共识。集群在没有共识算法时，能提升的只有并发处理能力，而共识是为了所有成员都认同某一个值。
  • 共识算法都是非拜占庭算法，即在不出现拜占庭故障的环境下设计出来的。
  • 拜占庭故障：在分布式环境中，可能有恶意成员破快算法的安全性。
    • 要解决拜占庭故障，需要 3F + 1 的成员总数来保证算法的安全性，F 是能容忍的恶意成员的数目。
    • 在后端的分布式环境中这种故障不常出现，因此默认该故障不发生。

Basic Paxos

通常谈论的 Paxos 就是 Basic Paxos。

最简单的共识问题：我们有一组服务器，其中有些服务器会提议 (propose) 特定的值，要挑选这些值中唯一的一个，这个被选中的值称为 (chosen)。

Basic Paxos 的需求

  1. 安全性：(1) 一次只能选定一个值；(2) 一个值一旦被选定，就永远被选定不会再改变。
  2. 可用性：在系统中大多数 (majority) 服务器能正常工作，且消息能在合理时延内到达的前提下，要求：(1) 最终总会选定一个值，而不是一直处于没有值被选定的状态；(2) 如果一个值被选定，所有服务器最终都能知道这个值被选定。

❗️某个值被服务器接受 (accepted) 并不代表被选定 (chosen)，一个值只有被集群大多数节点接受后才认为是被选定的。

Basic Paxos 的组件

  1. 提议者 (Proposers)：接收来自客户端的请求，获得特定的选定值，然后向集群里的其他服务器传递这个值 (相当于“提案”)，试图并让其他服务器也达成一致选择这个值。
  2. 接受者 (Acceptors)：被动接收来自于提议者 (Proposers) 的请求并做出响应，可以把这种响应当成 “投票”。
  3. 学习者 (Learners)：不参与提案和投票，只被动接收提案结果。他的存在可用于扩展读性能，或者跨区域之间读操作。

一般每个服务器都同时包含以上三种角色，这意味着任何一个服务器副本都能够提出提案，接受其他副本的提案，以及学习通过的提案。
但让角色分离，让每台服务器拥有独立角色来构建 Paxos 协议也是可以的。

Basic Paxos 协议

提案选定

Paxos lecture (Raft user study) 中记录了要实现共识性需解决的问题，这里进行一个概述：

Q1：若 接受者 (Acceptors) 只有一个，该结点宕机后就不知道选择的值是什么，导致系统不可用。
A1：要有一组(通常是个奇数)，才能通过仲裁 (quorum) 保证高可用。

Q2：若 提议者 (Proposers) 各提各的，可能导致好几轮投票投不能达成一致。
A2：要有一个两阶段协议，在 提议者 (Proposers) 发出 accept 请求前，能先通过 propose 请求查看集群中是否有其他已 accept 的请求。若有，则放弃自己的值，采用已接受的值 (accepted)，让该值最终能被选定 (chosen)。

Q3：两阶段中可能有老的 accept 请求因为网络原因在新的 accept 请求后才到达，这时已经接受了新请求，就应拒绝老请求。
A3：保证请求有序 (给一个全局唯一的序号)，以消除老的请求 (序号比接受过的序号小就拒绝)。

提议序号 (proposal number) = 自增数 (Round Number) + Server Id

所有服务器保存 Round Number 的最大值 maxRound。该值值必须被持久化到磁盘或其他稳定的媒介，以确保可以在系统崩溃后能够恢复，保证提议序号全局唯一不会重复。

image-20230816002718290

第一阶段 (提议准备)：提议者 (Proposers) 广播 prepare RPC 请求。这个请求有两个目的：(1) 它会尝试找到其他可能被选定的值，这样就可以保证使用被选定的值，而不是自己的值；(2) 如果有其他存在的但未被选中的请求值，它会阻止老的请求，这样就可以避免发生竞争。

第二阶段 (提议接受)：提议者 (Proposers) 广播 accept RPC 请求 (包含一个选择好的值)。若这个阶段大多数都达成一致，就认为这个值已经被选定 (chosen)。

下面展示一个完整的请求流程：

image-20230816002901053

获取一个提议序号，进入提议准备阶段（prepare phase）：

  1. 提议者（Proposers） 向集群所有服务器广播 prepare RPC 请求 Prepare(n)；
  2. 接受者（Acceptor） 收到 Prepare(n) 请求后，会做两件事：
    1. 通过内部变量（minProposal）保证永远不会接受一个提议序号更低的请求。如果当前的提议序号 n > minProposal 就更新当前的 minProposal。
    2. 响应并返回已通过的最大提议内容（提议序号和值），如果没有就返回空。如果它之前已接受了某个提议，它会记录该请求的内容 （提议序号和值）。
  3. 提议者（Proposers） 会等待大多数 接受者（Acceptor） 的响应，一旦它接收到响应，它会检查看是否有返回，以及接受的提议值是什么。它会从所有的响应中挑选最高的提议序号，并用这个具有最高提议序号的值作为接受值，以替代它所提议的初始值继续后面的计算。如果没有 接受者（Acceptor） 返回已接受的提议值，那么它会使用自己的初始值继续后面的计算。

接下来进入提议接受阶段（accept phase）：

  1. 提议者（Proposers） 向集群所有服务器广播 accept RPC 请求 Accept(n, value)；
    • 提议序号 n 必须与准备阶段的序号值保持一致
    • 值 value 可以是 提议者（Proposers） 所提议的初始值，也可以是从 接受者（Acceptor） 返回的接受值
  2. 接受者（Acceptor） 收到 accept 请求后，会做两件事：
    1. 将该提议序号 n 与自己保存的提议序号 minProposal 作比较：若 n 更小则拒绝该 accept 请求；否则接受这个请求，并记下请求内容（提议序号以值），更新当前的 minProposal，保证它是最大的。
    2. 返回它当前的 minProposal。这样 提议者（Proposers） 就可以使用这个返回值来判断请求是否被接受。
  3. 提议者（Proposers） 会等待直到它接收到多数响应。一旦收到这些响应，它就会检查是否有请求被拒绝。比较返回值和自身提议序号，若不同证明请求被拒绝。若大多数请求被接受，表明此提议值被选定，协议结束执行；否则这次提议需要重新开始。下一轮会获得一个更高的提议序号，有更多机会在竞争中取胜。

为保证这个协议能工作正常，集群必须保证三个值的稳定，minProposal、acceptedProposal 以及 acceptedValue，它们需要保存在稳定的媒介，如磁盘或闪存中。

提案获取

在一个提案达成共识后，如何让 Learner 获取该提案也是一个值得细究的问题。一般有以下几种方案。

  • 方案一
    最简单的方法就是一旦 Acceptor 批准了一个提案，就将该提案发给所有的 Learner 。这种做法虽然可以让 Learner 尽快的获得被选中的提案，但是却需要每个 Acceptor 与所有 Learner 逐一进行通信，通信次数为二者乘积，所以效率较低。
  • 方案二
    选定一个主 Learner ，如有某一个提案批准后，由 Acceptor 通知主 Learner ，当主 Learner 被通知后，由它通知其他的 Learner 。这个方案虽然多了一个步骤，但是通信次数大大降低，通信次数为 Learner 的数量。该方案同时引出另一个问题：主 Learner 随时可能出现故障。
  • 方案三
    在基于方案二的基础上，由单个主 Learner 扩展成一个主 Learner 集合。集合中 Learner 数量越高，可靠性也越好。

Basic Paxos 缺点

1️⃣ 竞争提议可能会导致活锁：新提议的 prepare 请求阻止了旧提议的 accept 请求导致旧请求重开；旧提议重开后的 prepare 请求又阻止了新提议的 accept 请求，导致新提议重开。如此循环下去。

解决方法1：提议失败后重新开始前等待一会，让提议有机会完成。

解决方法2：通过领导者选举 (leader election) 机制，保证在同一时间下只有一个 提议者（Proposers） 在工作。

2️⃣ 每次客户端的请求都要求两轮的 RPC 远程调用。会因为往返信息多，耗性能，延迟大。

3️⃣ 一旦值被选定之后，只有一台服务器（即发起提议的那台服务器）知道它选定的值是什么。如果其他的服务器想要知道被选定的值，它就必须自己执行协议。

Multi-Paxos

对于 Multi-Paxos 官方只是给出了一个思想,并没有给出对应的实现,所以很多算法都是基于这个思想实现的,比如 Chubby 的 Multi-Paxos 算法, Raft 算法。

有了 Basic Paxos 来完成对一个值的共识后，可为一组日志记录创建一组 Basic Paxos 实例（每条 log 对应一个独立的 Paxos 实例）实现一系列值的共识，这就是 Multi-Paxos。

Multi-Paxos 要为每个 Basic Paxos 实例添加唯一的 index 标识，用来选择特定的日志记录，所有的服务器为日志里的每条记录都保有独立的状态。

Multi-Paxos 基于 Basic Paxos 做出两点改进（也就是改进了上面说的前两点缺点）：

  1. 因为多个 提议者 (proposer) 会导致活锁问题。所以引入领导者选举机制，在所有 提议者 (proposer) 中选举出一个 领导者 (Leader)，由 领导者 (Leader) 进行提议。
  2. 在系统中仅有一个 领导者 (Leader) 进行提议的情况下，可以为 领导者 (leader) 使用一轮提议准备 (Prepare)，但是准备的对象是完整的日志，而不是单条日志记录。一旦完成了准备 (Prepare)，就可以通过使用接受 (Accept) 请求创建多条日志记录，而无需多次使用准备 (Prepare) 阶段。这样就能减少一半的 RPC 请求。

领导者选举的方式有很多，可通过一次 Basic Paxos，也可采用租约的方式等。

如果出现多个 Leader，Multi-Paxos 也能正常工作，但是就会退化为 Basic Paxos，没那么高效了。

参考链接

Paxos lecture (Raft user study)

并发笔记