Paxos-vs-Raft

前言

There is only one consensus protocol, and that’s Paxos. ——Mike Burrows(Google Chubby)

Overview

Paxos 和 Raft 的共识方式是类似的，大多数是术语的区别，比如对于 Multi-Raft 而言，大致可以分为三个层，Client，Server，Raft。

• Client 层给请求包一个唯一 id，扔到对应 Raft Group Server 层的 Leader 节点；
• Server 层是处理请求的地方，需要和 Raft 层交互，具体而言，Server 层需要将 Client 的请求发送到 Raft 层进行共识，多数派共识之后这个 Raft Group 的不同 Server 都会执行相同的请求，但是由 Leader 返回结果；
• Raft 层通过领导人选举、心跳、日志复制进行共识，日志过多时还能进行快照压缩；其中，Raft 的 leader 对应 Paxos 的 Proposer，会分配一个 rnd 并发起一次 Paxos 共识，Paxos 还有 Acceptor 和 Learner。
• Raft 的 Term 还被 Paxos 称作 views, ballot numbers, proposal numbers, round numbers。
• Raft 的选举的过程有些类似于 Classic Paxos 的 phase-1。
• Raft Leader 的日志复制则类似于 Classic Paxos 的 phase-2。

Classic Paxos phase-1

当 Paxos 的 Proposer 向 Acceptor 发送一个共识的请求时，如果请求中的 rnd 比 Acceptor 的 last_rnd 小，则拒绝共识该请求（返回自己的 last_rnd 和 value）；反之，则将 last_rnd 设置为 rnd，从此 Acceptor 只接受 last_rnd 的 phase-2 请求。所以 rnd 大的请求会覆盖 rnd 小的请求。

当 Proposer 收到 Quorum（可以简单理解为多数派）后，如果收到了 value 和 last_rnd，并且 last_rnd 比自己的大，直接退出；如果比自己的小，说明已经有其他的 Proposer 正在运行，那么需要在 不修改已存在的值的前提下 从所有 Acceptor 中选择最大的 vrnd 对应的 value 进行 phase-2。

Classic Paxos phase-2

Acceptor 收到 Proposer 后，如果 rnd 不等于 last_rnd 则退出，否则将 value 写入本地。

Classic Paxos phase-3

Acceptor 发送 phase-3 到所有的 learner，让其知道一个请求被确定了，多数场合下 proposer 也是 learner。

Multi-Paxos

Classic Paxos 没有 leader，每个请求的共识都由 Proposer 提出，在高并发的时候可能会有活锁问题，Multi-Paxos 引入了 Leader，可以稳定地进行提案， 并且会将多个请求的 phase-1 合并成一次 rpc，并且仅通过一次 phase-2 完成最终的共识。

Fast-Paxos

直接发送 phase-2，并且 rnd 为 0，保证能够安全回退为 Classic Paxos，Acceptor 在 value 为空的时候才接受 Fast-Paxos，但是在并发写入的时候，Fast-Quorum 的节点数需要大于 3/4，原因是 Fast-Quorum 的 Acceptor 在 Classic-Quorum 中必须超过半数，才不会导致退化为 Classic-Paxos 重试的时候选择一个错误的 value。

Multi-Paxos 与 Raft 的不同