关于算法:Paxos算法协议基本原理

Paxos

指标：复制日志

• 复制日志 => 复制状态机

  • 所有服务器依照雷同的程序执行雷同的命令
• 一致性模型确保正确的日志复制
• 只有大部分服务器是运行的零碎就能工作
• 失败的模型：失败 - 进行(非拜占庭)，提早 / 失落信息

Basic Paxos

• Proposers：

  • 流动的：提出特定的值被选中
  • 解决客户申请

• Acceptors：

  • 被动的：响应音讯给 proposers
  • 回应达成共识的投票
  • 保留选中的值
  • 想晓得哪个值被选中
  • 每个服务器都蕴含 proposer 和 acceptor

一个 Acceptor

Q：如果 acceptor 挂掉了怎么办？
A：多个 acceptors，选中被大多数 acceptors 的值

问题：平分投票

Q：Acceptor 只承受第一个达到的值？
A：如果同时提出提案，不会选中任何值，所以 Acceptors 必须能够抉择多个不同的值

问题：抉择抵触

Q：Acceptor 承受所有达到的值？
A：可能会导致抉择多个值(如下图中的 S3)，所以一旦一个值被选中，当前的提案必须提出 / 抉择一样的值(两阶段提交)

依然有抉择抵触
下图的流程：

1. s1 看到此时其余服务器没有承受某个值，之后提出 red 值
2. s5 过后也看到此时没有其余服务器没有承受某个值，就提出 blue 值
3. blue 很快就被 s3、s4、s5 承受，而 s3 之后也会承受 red 值
   
4. s1 的提案必须被终止(s3 必须回绝它)
5. 因而提案必须有序，回绝旧的提案

提案值

• 每个提案有一个惟一的值

  • 大的优先级高
  • 提案者必须抉择一个比之前见过的还大的提案值

• 一个简略的办法：

  • 一个提案值包含 轮值 + 服务器 ID
  • 每个服务器保留 maxRound

  • 为产生一个新的提案值：

    • 递增 maxRound
    • 与服务器 ID 关联
  • 提案者必须将 maxRound 长久化到磁盘，避免提案值在机器宕机重启后重用

两阶段办法

• 阶段一：Prepare RPCs

  • 找到曾经被选中的值
  • 阻止旧的提案

• 阶段二：Accept RPCs

  • 申请 acceptors 承受值

流程

例子
在之后提出一个提案有三种可能：

• 1、之前的值曾经被选中了

  • 1、新的 Proposer 会发现它并应用它
  • 2、先阐明一下方框内写的是什么意思，P 示意 Prepare，A 示意 Accept，1 中的 3 示意 Round Number，1 示意由 s1 提出，X 为 acceptedValue
  • 3、能够看到之后的提案理解到 X 曾经被选中，s3、s4、s5 也会选中同样的值

• 2、之前没有值被选中，但曾经被承受

  • 1、新的 Proposer 会发现它并应用它
  • 2、与前一种状况相似

• 3、之前没有值被选中，也没看到值被承受

  • 1、起初的 Proposer 会应用本人的值
  • 2、旧的值会被回绝

活锁

其它

• 只有 proposer 晓得哪个值被选中了，acceptor 是不晓得的
• 如果其它服务器想晓得，就必须运行 paxos

Multi-Paxos

• 用日志项将 Basic Paxos 分成每一轮
• 增加 index 参数到 Prepare 和 Accept

概述

• 怎么抉择哪个日志项来寄存给定的客户申请？

• 性能优化：

  • 应用 leader 缩小 proposer 抵触
  • 打消大部分 Prepare 申请
• 复制的完整型
• 客户协定
• 配置变更

抉择日志项

• 当客户传来申请：

  • 找到第一个没有被选中的日志项
  • 运行 Basic Paxos，在这个 index，propose 客户命令

  • Prepare 返回 acceptedValue？

    • Yes，完结选中 acceptedValue
    • No，选中客户命令

• 当接管到申请时，服务器 S1 上的记录可能处于不同的状态，服务器晓得有些记录曾经被选定（1-mov，2-add，6-ret），在前面我会介绍服务器是如何晓得这些记录曾经被选定的。服务器上也有一些其余的记录（3-cmp），但此时它还不晓得这条记录曾经被选定。在这个例子中，咱们能够看到，实际上记录（3-cmp）曾经被选定了，因为在服务器 S3 上也有雷同的记录，只是 S1 和 S3 还不晓得。还有空白记录（4-，5-）没有承受任何值，不过其余服务器上相应的记录可能曾经有值了。
• 当 jmp 申请达到 S1 后，它会找到第一个没有被选定的记录（3-cmp），而后它会试图让 jmp 作为该记录的选定值。为了让这个例子更具体一些，咱们假如服务器 S3 曾经下线。所以 Paxos 协定在服务器 S1 和 S2 上运行，服务器 S1 会尝试让记录 3 承受 jmp 值，它正好发现记录 3 内曾经有值（3-cmp），这时它会完结抉择并进行比拟，S1 会向 S2 发送承受（3-cmp）的申请，S2 会承受 S1 上曾经承受的 3-cmp 并实现选定。这时（3-cmp）变成粗体，不过还没能实现客户端的申请，所以咱们返回到第一步，从新进行抉择。找到以后还没有被选定的记录（这次是记录 4-），这时 S1 会发现 S2 相应记录上曾经存在承受值（4-sub），所以它会再次放弃 jmp，并将 sub 值作为它 4- 记录的选定值。所以此时 S1 会再次返回到第一步，从新进行抉择，以后未被选定的记录是 5-，这次它会胜利的选定 5-jmp，因为 S1 没有发现其余服务器上有承受值。

注意事项：

• 在这种形式下，单个服务器能够同时解决多个客户端申请，也就是说前一个客户端申请会找到记录 3-，下一个客户端申请就会找到记录 4-，只有咱们为不同的申请应用不同的记录，它们都能以并行的形式独立运行。
• 不过，当进入到状态机后，就必须以肯定的程序来执行命令，命令必须与它们在日志内的程序统一，也就是说只有当记录 3- 实现执行后，能力执行记录 4-。

提高效率

• Basic Paxos 是低效的

  • 多个 proposers 抵触问题
  • 对于选中一个值须要两轮 RPCs(Prepare、Accept)

• 解决：

  • 选一个 leader

    • 在一个时刻，只有一个 Proposer

  • 打消大部分 Prepare RPCs

    • 一轮 Prepare 残缺的日志，而不是单条记录。
    • 一旦实现了 Prepare，它就能够通过 Accept 申请，同时创立多条记录。这样就不须要屡次应用 Prepare 阶段。这样就能缩小一半的 RPCs。

领导选举

选举领导者的形式有很多，这里只介绍一种由 Leslie Lamport 倡议的简略形式。

• 让有 最高 ID 的服务器作为领导者
• 能够通过每个服务器定期（每 T ms）向其余服务器 发送心跳音讯 的形式来实现。这些音讯蕴含发送服务器的 ID
• 如果它们没有能收到某一具备高 ID 的服务器的心跳音讯，这个距离（通常是 2T ms）须要设置的足够长，让音讯有足够的通信传递工夫。所以，如果这些服务器没有能接管到高 ID 的服务器音讯，而后它们会本人选举成为领导者。
• 也就是说，首先它会从客户端承受到申请，其次在 Paxos 协定中，它会 同时表演 proposer 和 acceptor
• 如果机器可能接管到来自高 ID 的服务器的心跳音讯，它就不会作为 leader，如果它接管到客户端的申请，那么它会 回绝 这个申请，并告知客户端与 leader 进行通信。
• 非 leader 服务器不会作为 proposer，只会作为 acceptor
• 这个机制的劣势在于，它不太可能呈现两个 leader 同时工作的状况，即便这样，如果呈现了两个 leader，Paxos 协定还是能失常工作，只是不是那么高效而已。
• 应该留神的是，实际上大多数零碎都不会采纳这种选举形式，它们会采纳基于 租约 的形式（lease based approach），这比上述介绍的机制要简单的多，不过也有其劣势。

缩小 Prepare 的 RPC 申请

• 为什么须要 Prepare？

  • 须要应用提议序号来 阻止 旧的提议
  • 应用 Prepare 阶段来查看曾经被承受的值，这样就能够应用这些值来代替本来本人心愿承受的值。

1. 第一个问题是阻止所有的提议，咱们能够通过扭转提议序号的含意来解决这个问题，将提议序号全局化，代表残缺的日志，而不是为每个日志记录都保留独立的提议序号。这么做要求咱们在实现一轮筹备申请后，当然咱们晓得这样做会锁住整个日志，所以后续的日志记录不须要其余的筹备申请。
2. 第二个问题有点讨巧。因为在不同接受者的不同日志记录里有很多承受值，为了解决这些值，咱们扩大了筹备申请的返回信息。和之前一样，筹备申请依然返回 acceptor 所承受的最高 ID 的提议，它只对以后记录这么做，不过除了这个，acceptor 会查看以后申请的后续日志记录，如果后续的日志里没有承受值，它还会返回这些记录的标记位 noMoreAccepted。
3. 应用了这种领导者选举的机制，领导者会达到一个状态，每个 acceptor 都返回 noMoreAccepted，领导者晓得所有它已承受的记录。所以一旦达到这个状态，对于单个 acceptor 咱们不须要再向这些 acceptor 发送筹备申请，因为它们曾经晓得了日志的状态。
4. 不仅如此，一旦从集群 大多数 acceptor 那取得 noMoreAccepted 返回值，咱们就 不须要发送筹备的 RPC 申请。也就是说，leader 能够简略地发送 Accept 申请，只须要一轮的 RPC 申请。这个过程会始终执行上来，惟一能扭转的就是有其余的服务器被选举成了 leader，以后 leader 的 Accept 申请会被回绝，整个过程会从新开始。

复制的完整性

• 之前的复制是不残缺的

  • 日志项只须要复制到大多数，咱们须要复制到 全副
  • 只有 proposer 晓得某个日志项被选中了，咱们须要所有服务器都晓得哪些日志项被选中了

解决办法：

1. 在后盾继续尝试 Accept RPCs 直到所有 acceptors 返回

2. 追踪被选中的日志项

   1. 让 acceptedProposal[i] = 无穷大，这样这个日志项就不能够被笼罩，也就是说被选中了
   2. 每个服务器还会放弃一个 firstUnchosenIndex：示意未被标识选定的最小下标值

3. proposer 通知 acceptors 曾经被选中的日志项

   1. Proposer 在 Accept RPCs 中蕴含它的 firstUnchosenIndex

   2. Acceptor 将选中第 i 个日志项，如果：

      1. i < request.firstUnchosenIndex
      2. acceptedProposal[i] == request.proposal
   3. 后果：acceptors 晓得大多数被选中的日志项

该 acceptor 在 accept 之前的第 6 个日志项的提议序号为 3.4，
这时它收到一个提议序号也为 3.4 的 accepte 申请，并且 申请的 firstUnchosenIndex = 7，大于之前 3.4 所在的 6，所以将选中第 6 个日志项，同时该申请的 index = 8，将 3.4 的申请放到第 8 个日志项

这个机制无奈解决所有的问题。问题在于 acceptor 可能会接管到来自于不同 proposer 的某些日志记录，这里记录 4 可能来自于之前轮次的服务器 S5，可怜的是这种状况下，acceptor 是无奈晓得该记录是否已被选定。它也可能是一个已生效过期的值。

咱们晓得它曾经被 proposer 选定，然而它可能应该被另外一个值所取代。所以还须要多做一步。

1. 旧 leader 的日志项

   1. Acceptor 返回它的 fristUnchosenIndex 在 Accept 答复中
   2. 如果 proposer 的 firstUnchosenIndex > acceptor 答复的 firstUnchosenIndex(阐明 acceptor 中的某些状态不确定)，proposer 就会在后盾发送 Success RPC

   3. Success(index, v): 告诉 acceptor 该日志项被选中了

      1. acceptedValue[index] = v
      2. acceptedProposal[index] = 无穷大
      3. return firstUnchosenIndex
      4. 如果须要(可能存在多个不确定的状态)，Proposer 发送额定的 Success RPC

客户端协定

• 发送命令给 leader

  • 如果不晓得哪个是 leader，轻易抉择一个服务器
  • 如果该服务不是 leader，重定向 给 leader
• leader 直到日志项被选中并且被 leader 的状态机执行才回应客户

• 如果申请超时(leader 挂了)

  • 客户从新发送命令给其余服务器
  • 最终重定向给新 leader
  • 给新 leader 重试申请

问题

• 如果 laeder 在执行完命令但在回应之前挂掉

  • 该命令不能执行两次

• 解决：客户端须要为每条命令提供一个 惟一的 id

  • 服务器会将该 id 存入日志项中
  • 状态机会记录每个客户最近执行的命令，即 最高 id 序号

  • 在执行命令之前，状态机会查看该命令如否被执行过，如果执行过：

    • 疏忽
    • 返回之前执行的后果
  • 后果：只有客户端不解体，就能取得 exactly once 的保障，每个客户端命令仅被集群执行一次。如果客户端呈现解体，就处于 at most once 的状况，也就是说客户端的命令可能执行，也可能没有执行。然而如果客户端是活着的，这些命令只会执行一次

配置变更
同一时刻不能够呈现两个不重叠的多数派

解决办法：

• Leslie Lamport 倡议的 Paxos 配置变更计划是用 日志 来治理这些变更，以后的配置作为日志的一条记录存储，并与其余的日志记录一起被复制同步。
• 所以下图中 1-C1、3-C2 示意两个配置信息，其余的用来存储一般的命令。这里乏味的是，配置所应用每条记录是由它的更早的记录所决定的。
• 这里有一个零碎参数 å 来决定这个更早是多早，假如 å 为 3，咱们这里有两个配置相干的记录，C1 存于记录 1 中，C2 存于记录 3 中，这也意味着 C1 在 3 条记录内不会失效，也就是说，C1 从记录 4 开始才会失效。C2 从记录 6 开始才会失效。所以当咱们抉择记录 1、2、3 时，失效的配置会是 C1 之前的那条配置，这里咱们将其标记为 C0。
• 这里的 å 是在系统启动时配置好的参数，这个参数能够用来限度同时应用的配置信息，也就是说，咱们是无奈在 i+å 之前抉择应用记录 i 中的配置的。因为咱们无奈晓得哪些服务器应用哪些配置，也无奈晓得大多数所代表的服务器数量。所以如果 å 的值很小时，整个过程是序列化的，每条记录抉择的配置都是不同的，如果 å 为 3，也就意味着同时有三条记录能够应用雷同的配置，如果 å 大很多时，事件会变得更简单，咱们须要长时间的期待，让新的配置失效。也就是说如果 å 的值是 1000 时，咱们须要在 1000 个记录之后能力等到这个配置失效。
  

总结

• Basic Paxos：
• Prepare 阶段
• Acceptor 阶段
• Multi-Paxos：
• Choosing log entries
• Leader election
• Eliminting most Prepare requests
• Full infomation propagation
• 客户协定
• 配置变更