[科普中国]-状态机复制

在计算机科学领域，状态机复制或状态机方法****是实现容错服务的一种常规方法，主要通过复制服务器，并协调客户端和这些服务器镜像间的交互来达到目标。这个方法也同时提供了理解和设计复制管理协议的一套基本框架。

历史背景Leslie Lamport在1984年发表的关于“在分布式系统中使用时间而不是超时”的论文中首次提出了状态机方法。弗雷德·施耐德（Fred Schneider）后来在他的论文“使用状态机方法实现容错服务：教程”中阐述了这种方法。

Ken Birman在1985年到1987年间发表的一系列论文中发展了虚拟同步模型。这项工作的主要参考文献是“利用分布式系统中的虚拟同步”，它描述了Isis Toolkit，一个用来建立纽约瑞士股票交易所，法国空中交通管制系统，美国海军AEGIS战舰等应用。

Miguel Castro和Barbara Liskov最近的工作是使用状态机方法，他们称之为“实用的拜占庭式容错”架构，它使用Lamport的原始状态机方法版本复制特别敏感的服务，但通过优化大大提高了性能。

最近，也有创造的BFT智能库，高性能拜占庭容错状态机复制库用Java开发。这个库实现了一个非常类似于PBFT的协议，以及提供状态转移和主机重新配置（即JOIN和LEAVE操作）的互补协议。BFT-SMaRt是最近实现状态机复制的努力，仍然在积极维护。

基于共识的算法Raft于2013年开发。Raft 是一种通过日志复制来实现的一致性算法，提供了和(多重)Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 是不同的，因此Raft 算法更容易理解和应用。1

问题定义分布式服务分布式软件通常由客户端和服务器组成，每个服务包含一到多个服务器，并提供可以由客户端通过请求来调用的操作。尽管使用单个中心化服务器是实现服务的最简单方式，但这种方式使得服务的容错性最多能和运行服务器的处理器相同。假如这种程度的容错性是不可接受的，那么就必须引入多个故障无相关性的服务器。通常而言，单一服务器的多个服务镜像运行在分布式系统的分离处理器上，并通过协议来保障客户端和这些镜像间的交互。在分布式系统中，物理和电子上被隔离开的处理器保障了服务器之间故障没有相关性，彼此独立，这整合需求一致。2

状态机在后文中，状态机被定义为下面这些值元组：

一组状态

一组输入

一组输出

一个转换函数（输入 x 状态 → 状态）

一个输出函数（输入 x 状态 → 输出）

被称为“初始”的一个独特状态

一个状态机从“初始”状态开始，每一个输入都被传入转换函数和输出函数，以生成一个新的状态和输出。在新的输入被接收到前，状态保持不变，而输出同时被传输给恰当的接受者。

在本文中，状态机必须具备确定性：多个相同状态机的拷贝，从同样的“初始”状态开始，经历了相同的输入序列后，会达到同样的状态，并且输出同样的结果。

通过恰当输入流，状态机可以实现任意的算法，包括完备图灵机的各种算法。通常而言，基于状态机复制的系统都会主动把它们的实现限制在有限状态机的范畴，以简化故障恢复。2

容错决定性是提供容错支持的理想特性。直观而言，假如系统存在多分拷贝，其中一个的故障会因为与其它系统的状态或者输出有差异，而变得明显。

只要简单推理下，就可以知道实现容错性需要最少三份拷贝，在一个系统出错的情况下，其它两个系统可以供我们比较状态和输出。而两份拷贝显然不够，因为我们无从判别出错的是哪一个。

再进一步推演，就可以知道具备三份拷贝的系统最多能支持单系统故障（随后必须修复或者替换掉故障拷贝）。假如有多余一个拷贝出现故障，那么三份状态或者输出都会互不相同，导致无法判断正确的拷贝。

通常而言，一个支持F个故障的系统，必须至少包含2F+1份拷贝（也称为镜像）。多余的拷贝被用作区分正确和故障拷贝的证据。特殊的情况也可以改良这些制约

目前的推理都预设这些镜像仅仅是面临随机的独立故障，比如内存错误或者硬盘崩溃。但源自某些镜像尝试欺骗系统而带来的问题，也同样能被状态机复制通过隔离变化来处理。

值得一提的是，并不需要停掉故障镜像的运行，它们可以继续运作，即便会产出伪造或者错误的输出。2

状态机方法前面的直观讨论意味着一个简单的技术来实现一个状态机方面的容错服务：

在多个独立的服务器上放置状态机的副本。

接收客户端请求，解释为输入到状态机。

选择输入的顺序。

在每台服务器上按所选顺序执行输入。

通过状态机的输出响应客户端。

监视状态或输出差异的副本。2

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学