学习笔记参考：

分布式系统基础-State Machine

读书笔记——Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial

利用状态机实现容错服务的一个教程

摘要部分

状态机方法是在分布式系统中实现容错服务的一般方法。 本文回顾了该方法并描述了两种不同故障模型的协议 - 拜占庭和故障停止。 还讨论了用于移除故障组件和集成修复组件的系统重新配置技术。

Introduction

分布式软件常由客户端（clients）和服务端（services）构成。

集中式的服务端虽然是最简单的架构方式，但也导致了其容错性只能与执行该服务的处理器相同，换言之，依旧是单机的容错性能。

如果这样级别的容错不可接受，那就应该在分布系统的独立容错的不同处理器上运行原始服务的副本，协议用于这些副本的交互。分布式系统的物理电气隔离确保了故障的独立性。

The state machine approcah is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with sever replicas.

状态机方法是同过复制服务器（设置代理/备份）并协调客户端与服务器代理交互的一种实现容错服务的通用方法。

该方法还为理解和设计（服务器 replica）管理协议提供了一个框架。许多涉及数据或软件复制的协议——无论是为了掩盖故障，还是为了在没有集中控制的情况下促进交互——都可以使用状态机方法派生出来。尽管实际上很少有协议是以这种方式获得的，但是从状态机的角度观察它们有助于理解它们是如何以及为什么工作的。

本文是状态机方法的一个教程，描述了两种典型环境下的方法和实现。

State Machine

状态机由状态变量（编码描述状态），状态转移指令（描述状态变化）。每一条指令由确定性程序构成。命令的执行是原子的。一段客户端的请求可以看作是指定对应的状态机实施指定的 command（同时包含该 command 要求的全部信息）

请求的输出可以看作是一个 actuator（在程序控制系统中），或是其他的外围设备，或是等待先前请求响应的客户机（可以看作是编译原理中自动机理论的语义分析）。

请求由状态机每次执行一条，并且与潜在的因果关系一直。因此，状态机的客户端可以对要处理的请求的顺序做以下假设。

O1. 单个客户对给定的状态机 sm 发送的请求将被按照发送的顺序执行。

O2. 如果客户机 c 向状态机 sm 发出请求 r 可能导致客户机 c'向 sm 发出请求 r'，那么 sm 在 r'之前处理 r。

考虑到通信网络的延迟，尤其是在分布式网络中（可以联系上一篇论文），O1 和 O2 并不意味着状态机会根据制定/接收到的请求指令执行。

状态机的语义表征：状态机的输出完全由它处理的请求序列决定

Anything that can be structured in terms of proce- dures and procedure calls can also be structured using state machines and clients.

a state machine implements the procedure

requests implement the procedure calls.

事实上，状态机在系统结构上比过程调用通常提供的灵活性更大。使用状态机，在处理请求之前不会延迟发出请求的客户机，并且可以将请求的输出发送到发出请求的客户机之外的其他地方。我们没有理由怀疑根据状态机客户端构建的应用会更加简洁。

Fault Tolerance

两种典型的错误行为

Byzantine Failures（拜占庭故障）：

该组件可能表现出任意和恶意的行为，可能涉及与其他故障组件的勾结

Fail-stop Failures. （异常终止错误）

允许其他组件检测到错误并停止。

t fault tollerant：指系统在一定范围的活动中最多不超过 t 个组件发生故障，传统的 MTBF（平均故障间隔时间）和其他的统计的故障评定方法固然有其可取之处，但是，去测定系统的最大容载故障组建个数潜意识中要求了系统具备一定的修正能力（当出现故障组件个数超出/即将超出限额时的补救措施）。

Fault-tolerance state machine

步入正题，容错状态机。

由于备份（副本）运行在分布式系统的不同处理器上，在假定每个错误最多影响一个处理器，而在不出错的情况下，相同初始状态的状态机经相同的输入（request 序列）应该抵达相同状态并输出相同内容，那么结合该系统状态机副本的输出，得到容错状态机的输出。

若考虑满足最坏情况下，出现拜占庭故障，正常运行的组件仍占据大多数，要求一个 t fault-tollerant 状态机应之少包含 2t+1 个组件。

而如果考虑故障停止情况下，那么只要满足还有一个 non-fautlty 组件具备正常输出能力即可，所以应至少包含 t+1 个组件。

实现上述容错状态机的关键在于备份（副本）的协调（Replica Coordination）：所有备份（副本）都可以接收到且接收到顺序相同的请求序列。

拆分成两个子要求：

1. Agreement：每个非故障状态机都会接收到每个请求。
2. Order：每个非故障状态机都会以相同的顺序处理这些请求。

Order 保证的是相对顺序（局部序）。

在某些情况下条件可以放宽，比如，如果我们假设只会发生 Fail-Stop Failure,并且只会收到读请求，那么 Agreement 可以被弱化成只要一台（而非每台）正常运行的状态机收到这个读请求就好啦．很容易理解。另外对于通信请求，若处理不同的请求 r 和 r'时，r->r'和 r'->r 的终状态和输出序列相同的话。文章举了一个投票的自动机例子，如果候选者每个人投票数最大为 1，且阈值（MAJ）的两倍要大于总值（Cno），换句话说，至多只有一人会被投出，那么无论怎样交换请求（投票顺序），自动机的输出和最终输出必然是相同的。但若允许每个人投票多次，或是阈值不满足上述要求，则交换请求会影响到自动机的输出和终状态。

Agreement

我们可以通过引入一个新的组件，称为 transmitter，它负责向其他的组件发送一个值，只要满足以下条件，那么就能满足 Aggrement:

IC1: All nonfaulty processors agree on the same value. 全部的正常运行的 processors 同意同一个值

IC2: If the transmitter is nonfaulty, then all nonfaulty processors use its value as the one on which they agree. 如果 transmitter 正常运行，那么其他的正常运行的 processors 均使用它的值作为它们同意的那个值

这种协议已经引起了学术界的关注．目前也已经有相应的协议产生了。我们可以将 client 作为 transmitter,也可以单独设置这样一个组件．但是如果单独设置这样一个组件的话，我们需要确保请求在发送到 trasmitter 的过程中，丢失或者被篡改．我们可以通过让 client 也接收 transmitter 发送的请求，来避免这种情况。难点是应对在执行过程中出错的处理器。

Order and Stability

顺序要求可以通过为请求赋唯一标识符值来实现，且对于稳定的请求，将最小值传递给后面的状态机副本。（个人对稳定的理解：具备相对优先顺序、不会改变、可被执行）

要点：identifiers 的指定方法和“稳定”测试。

另外需要注意的是，identifiers 的分配还需要符合 Sec.1 里 O1 和 O2，这就要求祖先请求的 identifiers 值要更小，即若\(r_j\)是由于\(r_i\)而产生的，则\(uid(r_i)< uid(r_j)\)。

文章介绍了三种方法

Using Logical Clocks

利用上一篇文章所介绍的逻辑时钟，即给偏序请求集根据两条规则。

C1. 如果 a 和 b 是同一进程的两个事件且 a 发生在 b 之前，则\(C_i \langle a \rangle < C_i \langle b \rangle\)。

C2. 如果 a 是 i 进程消息发送方，而 b 是 j 进程中该消息的接收方，则\(C_i \langle a \rangle < C_j \langle b \rangle\)。

Condition）。

设计算法来为上述构建的时钟函数赋值，为满足 C1 和 C2，分别设定两条规则：

IR1. 同一个 process 的相邻 event，其时钟值是递增的。

IR2. i 进程 a 活动发送的消息会携带一个时间戳\(T_m = C_i \langle a \rangle\)，则接收方 b 进程活动 b 设定其时钟值为\(C_j \langle b \rangle = MAX(T_m,C_j \langle b \rangle)+1\)。

C 值即我们希望得到的 identifier 值，接下来文章用来描述检查 stable 的方法，通过对处理器之间传递的消息附加序列号而已实现一些 communication channels：

FIFO Channels. 一对处理器间的消息接收顺序即发送顺序。

而对于出现故障停止的处理器，我们也可以假定下列情况的存在。

Failure Detection Assumption. 一个处理器 p 可以检测到另一个处理器 q 发生故障仅能够在其收到最后一条 q 发给 p 的消息后。

两个假设是一致的，在该假设下，可以构建如下的检测方法：

Logical Clock Stability Test Toleranting Fail-stop Failures. A request is stable at replica \(sm_i\) if a request with larger timestamp has been received by \(sm_i\) from every client running on a nonfaulty processor.当所有处理器（无论 faulty 还是 nonfaulty）都以更晚的时间戳发送给该状态机副本一条请求时，先前的请求就是稳定的。

接下来文章分类讨论解释了为什么上述成立，nonfaulty 的处理机一旦发送了更大的，由于递增性，下次发送的时间戳值会更大，而根据 FIFO 原则，receive order 和 deliver order 相同，也符合递增性。而对于认定为出错的处理机，根据 Failure Detection Assumption 原则，我们可以确定是在收到了最后一条消息后，所以之后也不会再收到故障处理器的消息，综上，测试条件成立。

Synchronized Real-Time Clocks

第二种构建满足 O1 和 O2 条件的 identifiers 值得方法是应用近似同步的实时时钟。

定义\(T_p(e)\)为事件 e 发生时 p 处理器的实时时钟值。我们通过向\(T_p(e)\)尾部后缀一端定长二进制串来唯一标定“p 处理器上的客户机进行了事件 e”这一信息。

那么为了满足 O1 和 O2 条件做以下规定。

1. Satisfied O1. 在有效的时钟精度（clock ticks/resolution）中一个处理器不会进行多于一次的请求。
2. Satisfied O2. 时钟同步应优于最小消息传递时间。

满足规定后，可以有以下的检测方法。设定\(\Delta\)为消息发出后确保每一个正常处理器收到消息时间不晚于\(uid(r) + \Delta\)的阈值，这样的\(\Delta\)是一定存在的。

Real-Time Clock Stability Test Tolerating Byzantine Failures 1. A request \(r\) is stable at a state machine replica \(sm_i\) being executed by processor \(p\) if the local clock at \(p\) reads \(\tau\) and \(uid(r) < \tau - \Delta\)