状态机复制

在计算机科学中，状态机复制（SMR）或状态机方法是一种通过复制服务器和协调客户与服务器副本的交互来实现容错服务的一般方法。该方法还为理解和设计复制管理协议提供了一个框架。

就客户和服务而言。每个服务包括一个或多个服务器，并输出客户端通过提出请求而调用的操作。尽管使用单一的、集中的服务器是实现服务的最简单的方法，但所产生的服务只能像执行该服务器的处理器一样具有容错性。如果这种容错水平是不可接受的，那么可以使用独立故障的多个服务器。通常，单个服务器的副本在分布式系统的不同处理器上执行，并使用协议来协调客户与这些副本的交互。

在接下来的讨论中，状态机将被定义为以下数值的元组（也见Mealy机和Moore机）。

一组状态 一组输入 一组输出 一个过渡函数 (Input × State → State) 一个输出函数 (Input × State → Output) 一个称为Start的区分状态。 一个状态机从标记为Start的状态开始。每个收到的输入都会通过过渡和输出函数产生一个新的状态和一个输出。状态保持稳定，直到收到新的输入，而输出被传达给适当的接收器。

这种讨论要求状态机是确定性的：同一个状态机的多个副本从起始状态开始，以相同的顺序接收相同的输入，将在产生相同的输出后到达相同的状态。

通常情况下，基于状态机复制的系统自愿限制其实现，以使用有限状态机来简化错误恢复。

确定性是提供容错性的一个理想特性。直观地说，如果一个系统存在多个副本，其中一个的故障会被注意到，因为它的状态或输出与其他的不同。

稍微推理一下，容错所需的最小拷贝数是三个；一个有故障，另外两个我们与之比较状态和输出。两个副本是不够的，因为没有办法分辨哪个副本是有故障的。

进一步的推理表明，一个三副本系统最多可以支持一次故障（之后必须修复或替换有问题的副本）。如果不止一个副本发生故障，所有三个状态和输出都可能不同，而且没有办法选择哪个是正确的。

一般来说，一个支持F个故障的系统必须有2F+1个副本（也叫副本）。额外的副本被用作证据来决定哪些副本是正确的，哪些是有问题的。特殊情况下可以提高这些界限。

所有这些推论的前提是，副本只经历随机的独立故障，如内存错误或硬盘崩溃。由试图撒谎、欺骗或串通的复制体引起的故障也可以由状态机方法来处理，并进行单独的修改。

失败的复制体不需要停止；它们可以继续运行，包括产生虚假的或不正确的输出。

特殊情况。理论上，如果一个失败的复制体被保证停止而不产生输出，那么只需要F+1个复制体，客户可以接受系统产生的xxx个输出。现有的系统都没有达到这个限制，但在分析建立在容错层之上的系统时，经常会用到这个限制（因为容错层为其上面的所有层提供故障停止语义）。

前面的直观讨论意味着以状态机的方式实现容错服务的简单技术。

在多个独立的服务器上放置状态机的副本。 接收客户的请求，解释为对状态机的输入。 为输入选择一个顺序。 在每个服务器上按照选择的顺序执行输入。 用状态机的输出响应客户。 监控副本的状态或输出的差异。