分区容忍系统

动机

应用需要存储持久的信息,可用性取决于数据的可用性

共识的复杂度

需要共识来保证数据的一致性

冗余的代价随着节点数的增加而增加:

  • 当所有节点都参与时,共识算法的消息数量与节点数呈线性增加
  • 平方的复杂度\rArr可扩展性差

因此只使用一部分节点参与共识,例如每个集群5台机器(Chubby)。

故障恢复也需要使用共识来决定哪些机器在运行或宕机,每个故障都需要运行共识算法,因此也与节点数成比例增加(线性)。当故障频率不高的时候开销不大。

故障

  • 硬件、软件
  • 机架、网络交换机、电源
  • 运行较慢的计算机和网络
  • 数据中心

大型系统中总会有一部分磁盘、计算机或交换器出现故障,因此需要考虑故障的发生。

可扩展性(Scalability)

通常意义上,可扩展性指通过增加资源来提高性能(吞吐量、延迟或两者同时):

  • 更多的工作单元(水平扩展):关注每秒处理的请求数量
  • 更大的工作单元(垂直扩展):关注解决更大的问题(高性能计算)

但是有时可扩展性也指,通过增加资源来提高冗余度,同时不降低性能

  • 提高持久性(durability)
  • 提高可用性(availability)

异构系统(heterogenous systems)中,新增加的机器能力比初始的机器更强,可扩展性需要解决这个问题。

系统规模越大,每台机器需要的运行系统的人员就越少(economy of scale)。

继续阅读“分区容忍系统”

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 共识问题”