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算法”

Paxos协议(Paxos Protocol)

即使无法解决分布式系统异步通信中的共识问题,放弃Termination属性后我们仍可以找到实用的解决方案(Practical Solution),Paxos就是其中之一。

系统模型

  • 进程间通过消息通信
  • 消息是异步的:不限制传输延迟,但是在正确的进程间消息最终总能送达
  • 进程可以重启并恢复状态(restart and remember)

角色

Paxos协议中进程有三种基本的角色:

  1. Proposers 提议者
    提出一个想要达成共识的数值
  2. Acceptors 接收者
    选择达成共识的数值
  3. Learners 学习者
    学习Proposers与Acceptors已达成共识的数值

一个进程可以承担多个角色。

继续阅读“Paxos协议(Paxos Protocol)”

Consensus Problem 共识问题

系统工程课上教授讲解了Consensus问题,以及两种解决方法。本文主要介绍什么是Consensus,以及在分布式系统异步通信中的问题。

共识问题

Consensus Problem翻译为共识问题,指多个实体在某事上达成一致的过程,具体表现为所有进程决定同一个值。
Consensus is to have several different entities to agree on something.
All processes agree on a common value.

共识的应用诸如:

  • What transactions to commit to a database in which order
  • State machine replication (每个副本执行相同的客户请求集合,并且以等价的顺序处理请求,以保证副本产生相同的输出)
  • Atomic broadcast
  • Leader election
  • Mutual exclusion

与Consistency一致性的区别在于:一致性强调同一个数据的多个副本保持对外呈现状态的一致性。如当修改一个副本的数据时,其他副本如何获取到该修改。包括严格一致性、强一致性(顺序一致性、线性一致性)、弱一致性(最终一致性)等。共识问题强调达成一致性的过程

“一致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致性(这里的一致性指强一致性)。只能说共识机制,能够实现某种程度上的一致性。”分布式系统的一致性与共识性

继续阅读“Consensus Problem 共识问题”