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

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

共识问题的三个需求(Requirements)

  1. Termination
    终结:所有正确的进程都会作出决定
  2. Agreement
    认同:所有作出决定的进程认同同一个值(不只是正确的进程)
  3. Validity
    有效:被决定的值是由其中一个进程提出的

其他需要达成一致的部分

  • 消息顺序
  • 集合的成员(membership protocols)
  • 状态更新(保持副本同步 State machine replication)


共识的实现

FLP不可能问题(Impossibility Result)

FLP不可能问题指在异步通信中,即使最多一个进程发生崩溃,也无法达成共识。
该问题在1985年由Fischer、Lynch、Paterson在论文Impossibility of Distributed Consensus with One Faulty Process中提出。

系统模型

N个进程的集合:
每个进程由几台计算机处理(分布式)
假设我们先验地知道所有的进程

进程可以交换信息(例如通过TCP)

进程通过广播来propose数值,系统根据某些协议来作决定。

Atomic broadcast: all or none get the message
此处广播不具有原子性,也即进程崩溃时可能只有部分节点受到影响,其他节点仍能收到数据。

错误

可能存在的错误类型包括:

  1. 遗漏错误(Omission Failures)
    数据在传输过程中丢失
  2. 崩溃错误(Crash Failures)
    进程崩溃
  3. 数据错误(Value Failures)
    数据在传输过程中发生改变(例如0->1)

简化问题:假设只发生崩溃问题
Processes could restart and recover the state, but not guaranteed.

Configuration

Configuration是被提议数据的N元组,可以理解为所有节点的状态。

Univalent Configurations:只可能有一种决定的结果
0, 0, 0 -> 0 (0-deciding)
1, 1, 1 -> 1 (1-deciding)
由Validity决定

Bivalent Configurations:可能有两种结果

不可能性

在初始状态为Bivalent Configuration的情况下,如果某个进程崩溃后重启或消息延迟,可能导致经过一系列步骤(互相传递消息)后仍得到以一个不确定的Configuration,则无法终结,不满足达成共识的要求。

FLP证明了对于所有的最多只有一个节点发生错误的异步通信中不可能达成共识。

如何规避

潜在方法:

  • 采取错误检测(failure detector)
  • 不保证终结(termination)
  • 或选择大多数(majority)

参考内容

TUD Systems Engineering 1 – Consensus and Paxos
Consensus (computer science)
Consistency Model
分布式系统的一致性与共识性
分布式系统的一致性与共识(一)
FLP不可能原理

发表评论

您的电子邮箱地址不会被公开。