前言
大家好，我是老马。
分布式系统中，一致性算法是最重要的基石，也是最难学习的部分。
本系列根据 jraft 作为入口，学习一下 raft 的原理和实现。
raft 系列
State machine replication
在计算机科学中，状态机复制（State Machine Replication，SMR）是一种通过复制服务器并协调客户端与服务器副本的交互来实现容错服务的通用方法。
该方法还提供了理解和设计复制管理协议的框架。
问题定义
分布式服务
在客户端和服务的关系中，每个服务由一个或多个服务器组成，并提供客户端通过请求调用的操作。虽然使用单一的集中式服务器是实现服务的最简单方式，但该服务的容错能力仅限于执行该服务器的处理器。如果这种容错级别不可接受，则可以使用多个独立故障的服务器。通常，单个服务器的副本在分布式系统的不同处理器上运行，并使用协议来协调客户端与这些副本的交互。
状态机
在后续讨论中，状态机被定义为以下值的元组：
- 一组状态（States）
- 一组输入（Inputs）
- 一组输出（Outputs）
- 一个转换函数（Transition Function）：输入 × 状态 → 状态
- 一个输出函数（Output Function）：输入 × 状态 → 输出
- 一个称为“开始”（Start）的特殊状态
状态机从标记为“开始”的状态开始。每个接收到的输入都会通过转换和输出函数，产生一个新的状态和输出。在接收到新输入之前，状态保持稳定，同时输出会传递给适当的接收者。在此讨论中，要求状态机是确定性的：多个相同的状态机副本从“开始”状态开始，以相同的顺序接收相同的输入，将到达相同的状态，并产生相同的输出。
容错性
确定性是提供容错性的理想特性。直观地说，如果存在多个系统副本，其中一个发生故障，其状态或输出与其他副本不同，将很容易察觉。为了实现容错，至少需要三个副本：一个可能发生故障，另外两个用于比较状态和输出。两个副本不足以判断故障副本，因为无法确定哪个副本有问题。一个三副本系统最多支持一个故障（之后必须修复或替换故障副本）。一般而言，支持F个故障的系统必须有2F+1个副本（也称为副本）。额外的副本用于作为证据，决定哪些副本是正确的，哪些是故障的。
所有这些推导都假设副本仅经历随机独立故障，例如内存错误或硬盘故障。对于恶意或串通的故障，状态机方法也可以处理，但需要进行相应的修改。故障副本不需要停止；它们可能继续操作，包括生成虚假的或不正确的输出。
特殊情况：故障停止（Fail-Stop）
理论上，如果故障副本保证停止而不生成输出，则只需要F+1个副本，客户端可以接受系统生成的第一个输出。虽然没有现有系统实现这一极限，但在分析构建在容错层之上的系统时，通常使用这一假设（因为容错层为其上层提供了故障停止的语义）。
特殊情况：拜占庭故障（Byzantine Failure）
当副本在不同方向发送不同值时（例如，向某些副本发送正确的输出，而向其他副本发送错误的输出），称为拜占庭故障。拜占庭故障可能是随机的虚假故障，也可能是恶意的智能攻击。对于非恶意的拜占庭故障，2F+1个副本，加上非加密哈希函数，足以在高概率下存活。恶意攻击需要使用加密原语来实现2F+1（使用消息签名），或者可以应用非加密技术，但副本数量必须增加到3F+1。
状态机方法
前述讨论暗示了使用状态机实现容错服务的简单技术：
- 将状态机的副本放置在多个独立的服务器上。
- 接收客户端请求，将其解释为对状态机的输入。
- 为输入选择一个顺序。
- 按照选定的顺序在每个服务器上执行输入。
- 将状态机的输出响应返回给客户端。
- 监视副本之间的状态或输出差异。
这种方法提供了一个理解和设计复制管理协议的框架。许多涉及数据或软件复制的协议——无论是为了掩盖故障还是促进没有集中控制的协作——都可以通过状态机方法推导出来。虽然其中一些协议并非直接通过这种方法获得，但将它们视为状态机有助于理解它们的工作原理和原因。
状态机方法
前面的直观讨论暗示了一种通过状态机实现容错服务的简单技术：
- 将状态机的副本放置在多个独立的服务器上。
- 接收客户端请求，将其解释为状态机的输入。
- 选择输入的顺序。
- 按照选定的顺序在每个服务器上执行输入。
- 将状态机的输出作为响应返回给客户端。
- 监控副本之间的状态或输出差异。
本文的其余部分将详细展开此技术。
步骤1和2不在本文讨论范围内。
步骤3是关键操作，请参见“输入排序”。
步骤4由状态机定义涵盖。
步骤5，请参见“发送输出”。
步骤6，请参见“审计与故障检测”。
附录中讨论了实际系统中常见的扩展，如日志记录、检查点、重配置和状态转移。
输入排序
构建分布式状态机系统的关键步骤是选择输入的处理顺序。由于所有无故障的副本在接收到相同输入时会到达相同的状态和输出，因此必须保证每个副本按相同的顺序提交输入。文献中已经提出了许多解决方案。[2][6][7][8][9]
-
可见通道：两个活跃参与系统的实体之间的通信路径（例如客户端与服务器、服务器与服务器之间的通信）。例如：客户端到服务器、服务器到服务器。
-
隐藏通道：一个不向系统公开的通信路径。例如：客户端与客户端之间的通道通常是隐藏的，比如用户通过电话沟通，或者一个进程写入磁盘文件，另一个进程读取这些文件。
当所有通信路径都是可见通道且没有隐藏通道时，可以从通信模式中推断出部分全局顺序（因果顺序）。[8][10]
因果顺序可以由每个服务器独立推导出来。输入按照因果顺序执行，可以保证所有无故障副本具有一致的状态和输出。
在开放系统中，隐藏通道是常见的，因此必须使用较弱的排序形式。输入的顺序可以通过一个投票协议来定义，其结果仅依赖于可见通道。
由一组独立实体对单一值进行投票的问题称为共识。通过扩展，可以通过一系列共识实例选择一系列值。当参与者或其通信媒介可能发生故障时，这个问题会变得更加复杂。[3]
输入可以按共识实例中的位置进行排序（共识顺序）。[7]
共识顺序可以由每个服务器独立推导出来。输入按照共识顺序执行，可以保证所有无故障副本的状态和输出一致。
优化因果顺序与共识排序
在某些情况下，可能有额外的信息可用（例如实时时钟）。在这些情况下，可以通过减少消息数量、减少消息轮次或减小消息大小来实现更高效的因果顺序或共识排序。详细信息请参见参考文献 [1][4][6][11]。
当考虑到状态机操作的语义时（例如读操作与写操作），还可以进行进一步优化。请参见参考文献《广义Paxos》。[2][12]
发送输出
客户端请求被解释为状态机的输入，并按照适当的顺序处理为输出。每个副本将独立生成输出。无故障副本总是会生成相同的输出。在客户端响应发送之前，必须过滤掉故障输出。通常，大多数副本会返回相同的输出，并将该输出作为响应发送给客户端。
系统故障
如果没有副本的输出一致，或者少于多数副本返回输出，则发生了系统故障。客户端响应必须是唯一的输出：“FAIL”。
审计与故障检测
副本的永久性、非计划性损害称为故障。证明故障很困难，因为副本可能只是响应慢，[13]或甚至可能撒谎关于其状态。[5]
无故障副本将始终包含相同的状态并生成相同的输出。这个不变性通过比较所有副本的状态和输出来启用故障检测。通常，当一个副本的状态或输出与多数副本不同，就会被判定为故障。
一种常见的实现方法是通过服务器之间传递当前副本状态和最近输出的校验和。当检测到偏差时，审计过程会在每个服务器上重新启动本地副本。[14]校验和不需要加密安全性。
可能出现的情况是，本地服务器已被入侵，或者审计过程存在故障，副本继续错误地操作。这种情况通过之前描述的输出过滤器（请参见“发送输出”）安全地处理。
附录：扩展
输入日志
在没有故障的系统中，输入在被状态机处理后可以丢弃。然而，现实中的部署必须考虑到系统中的暂时性非故障行为，例如消息丢失、网络分区和慢处理器等。[14]
一种技术是将输入序列存储在日志中。在暂时性行为发生时，副本可以从其他副本请求日志条目的副本，以填补缺失的输入。[7]
通常情况下，日志不要求持久化（可以存储在内存中）。持久化日志可以弥补长时间的暂时性期间，或支持额外的系统功能，如检查点和重配置。
检查点
如果不加控制，日志会增长，直到耗尽所有可用的存储资源。为了继续运行，必须丢弃日志条目。一般来说，当日志条目的内容不再相关时（例如，当所有副本都已经处理了某个输入时，关于该输入的信息就不再需要），可以丢弃该条目。
控制日志大小的常用技术是存储一个重复的状态（称为检查点），然后丢弃所有贡献了该检查点的日志条目。当重复的状态比日志的大小小的时候，这样做节省空间。
检查点可以通过支持一个额外的输入命令CHECKPOINT来添加到任何状态机中。每个副本除了当前的状态值外，还会维护一个检查点。当日志变大时，副本会像处理客户端请求一样提交CHECKPOINT命令。系统会确保无故障副本以相同的顺序处理该命令，之后可以丢弃所有检查点之前的日志条目。
在具有检查点的系统中，检查点之前请求的日志条目会被忽略。无法找到所需日志条目副本的副本会被视为故障副本，必须重新加入系统（见重配置）。
重配置
重配置允许在系统继续处理客户端请求的同时添加或移除副本。计划维护和副本故障是重配置的常见示例。重配置包括退出和加入。
退出
当一个服务器检测到其状态或输出存在故障时（见审计与故障检测），它可以选择性地退出系统。同样，管理员也可以手动执行命令来移除一个副本以进行维护。
向状态机添加了一个新输入命令QUIT。[2][6]一个副本像客户端请求一样向系统提交此命令。所有无故障副本在处理该输入后都会将退出的副本从系统中移除。在此期间，副本可以忽略所有协议消息。如果仍有多数无故障副本，退出成功；否则，系统发生故障。
加入
退出后，故障的服务器可以选择性地重新启动或重新加入系统。同样，管理员也可以向系统中添加新的副本以增加容量。
向状态机添加了一个新输入命令JOIN。一个副本像客户端请求一样向系统提交此命令。所有无故障副本在处理该输入后都会将加入的节点添加到系统中。新副本在加入之前必须是系统状态的最新状态（见状态转移）。
状态转移
当新副本可用或旧副本重新启动时，在处理输入之前，必须将其带到当前的系统状态（见加入）。从逻辑上讲，这要求按适当的顺序应用系统以来的每个输入。
典型的部署通过执行最近的检查点来简化逻辑流程（见检查点）。这涉及通过带外协议直接将一个副本的状态复制到另一个副本。
检查点可能很大，要求较长的转移时间。在此期间，新的输入可能会被添加到日志中。如果发生这种情况，新副本必须接收新的输入，并在收到检查点后应用它们。典型的部署在开始状态转移之前将新副本作为观察者添加到排序协议中，从而使新副本在此期间能够收集输入。
优化状态转移
常见的部署通过只发送不同的状态组件来减少状态转移时间。这需要了解状态机的内部结构。由于状态转移通常是带外协议，这种假设并不难实现。
压缩是常见的状态转移协议中常加的一项功能，可以减少总转移的大小。
领导者选举（用于Paxos）
Paxos[7]是一种解决共识问题的协议，可以用作实现共识顺序的协议。
Paxos需要一个单一的领导者来确保系统的活跃性。[7]也就是说，必须有一个副本在足够长的时间内保持领导地位，以便就状态机的下一个操作达成共识。如果领导者在每个实例后变化，或者领导者在每个实例中变化多次，系统的行为不受影响。唯一的要求是，有一个副本保持领导地位足够长的时间，以推动系统向前发展。
冲突解决
一般来说，只有在对执行哪个操作存在分歧时才需要领导者，[11]如果这些操作以某种方式发生冲突（例如，它们不能交换顺序）。[12]
当提议发生冲突时，领导者充当唯一的权威来澄清情况，定义操作的顺序，从而使系统能够继续前进。
在Paxos中，多个副本可能同时认为自己是领导者。这一特性使得Paxos的领导者选举非常简单，任何保证“最终会有一个领导者”的算法都能正常工作。
历史背景
许多研究人员在1980年代初期发表了关于复制状态机方法的文章。
Anita Borg在她1983年的论文《A message system supporting fault tolerance》中描述了基于复制状态机的容错操作系统的实现。
Leslie Lamport也在1984年的论文《Using Time Instead of Timeout In Distributed Systems》中提出了状态机方法。Fred Schneider后来在他的论文《Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial》中详细阐述了这一方法。
Ken Birman在1985至1987年间的一系列论文中开发了虚拟同步模型。对此工作的主要参考是《Exploiting Virtual Synchrony in Distributed Systems》，该文描述了Isis工具包，这个系统被用于构建纽约和瑞士证券交易所、法国空中交通管制系统、美国海军AEGIS战舰及其他应用。
Miguel Castro和Barbara Liskov最近的研究采用了状态机方法，提出了一种他们称为“实用拜占庭容错”（Practical Byzantine Fault Tolerance, PBFT）的架构，利用Lamport的原始状态机方法的版本复制特别敏感的服务，并进行了优化，从而显著提高了性能。
最近，还有一个高性能的拜占庭容错状态机复制库——BFT-SMaRt库[15]，它是在Java中开发的。
该库实现了一个非常类似PBFT的协议，并提供了补充协议，支持状态转移和实时的主机重配置（即，JOIN和LEAVE操作）。
BFT-SMaRt是目前实现状态机复制的最新努力，仍在积极维护中。
Raft是一种基于共识的算法，开发于2013年。
受PBFT启发，Tendermint BFT[16]被引入用于部分异步网络，主要用于权益证明（Proof of Stake）区块链。
参考资料
https://en.wikipedia.org/wiki/State_machine_replication
