State Machine Replication

这篇博文主要是对wiki上的复制状态机的翻译，也是为了让自己更熟悉相关概念。复制状态机在分布式领域是一个常用且重要的技术，通过复制服务副本，并和副本一起来协调客户端的交互，来实现容错服务。这个方法同样提供了一个框架，来理解和设计复制管理协议。

当然，一切的技术的源头都是业务，针对业务需求来实现相关技术是最高效、最聪明的方法。因此学习技术之前，多问问自己，这样实现的目的是什么，如果是你来实现，你会怎么做。

一些定义

Distributed services 分布式服务

分布式软件是客户端和服务器之间常用的结构。每个服务通常部署在一个或多个节点上，对客户端的调用进行相应。使用单一的、中心话的节点是一种最简单的实现服务的方式，这样的结果是这个几点成了唯一的一个容错节点。这样的容错等级是不可接受的，因此需要多个节点并且他们之间是错误隔离的。一般来说，单个机器的副本被执行在分布式系统的别的节点上。进程的物理和软件隔离能确保服务的错误是独立的，这点非常重要。

State machine 状态机

状态机是自动机的一种，状态机的定义如下：

状态集合 States
输入集合 Inputs
输出集合 Outputs
迁移函数 Input×State→State
输出函数 Input×State→Output
开始状态 Start
状态机开始于Start状态，每一个输入传入节点，通过迁移函数和输出函数得到一个新的状态和输出。节点保持稳定直到一个新的输入进来。输出会被合适的接收者接受。

状态机是确定性的：多个相同状态机的副本开始于Start状态，以相同的次序收到相同的输入会到达相同的状态，并产生相同的输出。

状态机适用于需要处理合法输入流的任何算法，包括图灵完备算法。特别地，基于复制状态机的系统一般使用有限状态机来简化错误恢复。

容错

确定性 是一个提供容错的一个理想性质。直观的来说，如果系统存在多个副本，一个错误可以被观察到，因为它们之间会产生不同的状态和输出。

一个小的推论是，最小的复制组是三个节点。一个错误，我们可以通过和另外两个进行对比获悉。而两个复本是不够的，因为没办法确定谁才是错误的那一个。

反过来说，三复制组可以支持最多一个错误节点发生。如果超过一个副本错误，三个节点状态和输出都可能不一样，因此也无法确认哪个是正确的。

一般来说，一个系统支持 FF 个容错，那么必须使用 2F+12F+1 个副本。多余的副本是用来确定哪一半是正确的，哪一半是错误的。特殊的情况下可以提高一些。

以上的推论的前提是，副本随机地、独立的错误，比如说内存错误或者硬件崩溃。副本的错误包括，欺骗、虚假、勾结都可以通过状态机的方法来隔离改变。

应该注意的是，错误的副本不要求立即停止，它们可能继续工作，包括产生虚假的、错误的输出。

Special Case： Fail-Stop 失败终止
理论上来说，如果一个错误副本保证停止且不产生输出，只需要 F+1F+1 个副本就行。而且，客户端可能接受系统产生的第一个输出。可惜的是，没有系统能够实现这一限制，但是它常常用来构建更高层的容错系统（因为容错层提供Fail-Stop语义并确保其他的层都在它之上）。

Special Case: Byzantine Failure 拜占庭错误
副本给不同的节点发送不同的值，就是一个拜占庭错误（例如，一个正确的输出给了一部分副本，而将错误的输出给了另外一部分）。拜占庭问题可以是随机的、恶意的、聪明的攻击。使用 2F+12F+1 副本，并且非加密的 hash 可以应对所有的无恶意的拜占庭问题（高概率）。但恶意攻击的话需要加密传输（使用数字签名），不然的话，非加密传输的副本数在这种情况需要 3F+13F+1 个。

状态机方法

刚才的讨论提供简单的技术以实现一个基于状态机的、容错的服务，总结一下：

将状态机的副本放在不同的、独立的节点。
客户端的请求作为状态机的输入。
选择输入的一个次序。
使用这个次序执行每个节点的状态机。
将状态机的输出作为返回。
监控状态机的状态和输出的不同。
剩余的篇幅介绍一下这项技术的详细细节。

Step1、2超出了本文的范围
Step3 请看 Order Inputs，序列化输入
Step4 在之前的定义以及说过
Step5 请看 Order Outputs，序列化输出
Step6 请看 Auditing and Failure Detection，监控和故障检测

扩展里包含了一些实际系统所用到的经典方法，例如 Logging，CheckPoint，Reconfiguration，State Transfer。

Ordering Inputs

建立基于状态机的分布式系统关键的一步就是选择输入的次序。因为有一样的输入次序，所有的非错误的副本都将达到相同的状态，产生相同的输出。所以当务之急就是确保输入以相同的次序被每个副本接收。对于这一点，有许多技术，参考[1][5][6][7][8]。

Visible Channel 是两个节点之间交互的通道。例如客户端和服务之间，服务和服务之间

Hidden Channel 是不透露给系统的交互通道。例如客户端和客户端之间，或者一个进程正在写文件到磁盘上，另一个进程往磁盘里面读这个文件。

我们说，当所有的交互通道都是可见的，不存在隐藏的通道，那么一个部分性的全局序（Causal Order）就可以获得。因果序在不同的机器独立的派生出来。状态机的输入需要按照Causal Order 执行，保证所有的非错误节点都产生一致的状态和输出。

在开放的系统中，隐藏通道是常见的，因此需要使用一个弱形式的次序。输入的次序，需要通过投票协议来决定（投票协议通过可见的通道）。

一组独立的节点通过投票产生相同的单一值是一个一致性问题。另外，一系列的值需要一系列的一致性实例来选择。当参与者或者他们之间的交互媒介可能发生错误时，这个问题就会变得很困难。

一致性次序
在一些情况下需要额外的信息（比如实时的时钟）。在这种情况下，可能产生更有效的一致性次序，次序中有一定的冗余信息。更好的优化措施是将状态机的操作抽象成读和写，详细请看 Genneralized Paxos.

Sending Outputs

客户端其请求作为输入被状态机处理，并产生输出，这里也有一个次序。每一个副本是独立的产生这些输出的。非错误的副本会一直产生相同的输出。当客户端收到返回之前，错误的输出必须被过滤掉。一般来说，大部分的副本产生相同的输出，我们就将这个大部分一致的结果给客户端。

System Failure

系统错误就是找不到这样的一致输出。或者说只有一小部分产生了输出。这时候我们认为系统发生了错误。

Auditing and Failure Detection

无意义的、意想不到的输出的副本叫错误节点。定义错误很难，因为有些副本仅仅是发送延迟或者它可能撒谎了。

没有错误节点会一直产生相同的状态和相同的输出。这个不变性可以作为分辨错误节点和非错误节点的标准。一般的，如果一个副本产生的输出和状态和别人的不一样，我们就说它是错误节点。

一般的实现方法是传递副本最近的状态和最近的输出的校验。如果检测到偏差，每个节点就会重启本地的副本。校验不需要加密机制。

有一种可能是本地节点是错误的，副本继续操作是错误的。这种情况要保证安全性就需要预先过滤输出。

扩展

Input Log

CheckPoint

Reconfiguration

Quiting

Joining

State Transfer

Leader Election