Raft算法

一种更容易理解的共识算法。

使用共识的动机

容错(Fault Tolerance)

系统或系统上运行的服务可能会出现故障,为了恢复正常需要重新启动。这时既可以在同一台机器上重启(systemd),也可以在不同的机器上重启。

为了在不同机器上重启服务,需要协调服务(coordination service)的帮助。协调服务可以检测目标服务是否不可用,并在其他的机器上完成重启。协调服务本身也是容错的。

对于容错我们只需要该服务的一个副本(replica)。

协调服务:

  • Raft: Consul
  • Paxos: Chubby
  • Zab (atomic broadcast): Zookeeper

容错服务:

  • 需要在多个(协调服务所协调的)副本间复制状态(state replication)
  • 基于错误类型,可能需要F+1、2F+1、3F+1个副本来容忍F个错误

状态机复制(State Machine Replication, SMR)

状态机:从初始状态开始处理序列请求,在状态之间转换,最后产生输出

状态机的确定性(deterministic):对同一个状态机,同样的输入总是产生同样的转换和输出

状态机复制:

  • 对于容错的客户端-服务端系统,状态机复制是服务的复制(replication of services),协调副本与客户端请求。
  • 每个副本需要执行相同的客户端请求集合,以等价的顺序执行请求以保证副本能产生相同的内部状态和相同的输出。

继续阅读“Raft算法”