副本一致性算法

副本一致性算法

Paxos

Raft

Raft 之所以会出现,主要是因为 Paxos 晦涩难懂,大家表示很难看懂。

  • Paxos 可以多点写入,无需选举 Leader,每个节点都可以接受写请求。虽然为了避免活锁问题,Multi Paxos 可以选举一个 Leader,但是也不是强制执行的,允许同一时间有多个 Leader 同时存在。多点写入,这增加了复杂度。
  • Raft 只能单点写入
  • 任意时刻只能有一个有效的 Leader,只能 Leader 接受写请求,Leader 同步给超过半数的 Follower

日志结构

  • index: 日志的顺序编号,如 1、2、3、4 …
  • term: 写入日志的 Leader 所在的任期、轮数,其他地方称之为 epoch
  • commitIndex: 这条日志被复制到了多数的机器上
  • lastApplied: 哪些日志已经回放到了状态机

term 只会单调递增,日志的顺序满足: 后一条日志的 term >= 前一条日志的 term

term 作用

(1) 防止脑裂

网络分区恢复,存在两个 Leader,旧 Leader 向 Follower 发送数据,Follower 知道它的 term = 4,就知道它是过期的 Leader,于是拒绝执行写入,同时反馈给老的 Leader,你已经过期了。

(2) term 如何一直递增?

每个节点都保存了一个 term 的值,那么 term 比较小的节点是否会被选为 Leader ? 答案是不会。因为选举的时候,是要多数同意,意味着一定有一个节点保存了最新的 term 的值,而选举的时候,是选日志最新的节点作为 Leader

ZAB

Replicated State Machine Vs. Primary-Backup System

  • Replicated State Machine: 记录的是持久化的请求序列
  • Primary-Backup System: 记录的是持久化的数据的状态变化

Paxos 和 Raft 用的是前者,ZAB 用的是后者。

三种算法对比