概述
本文旨在整理出一条清晰的 Raft 学习路线，以及对其中的一些关键部分展开说明。
Raft 简介
如果想要了解 Raft 算法，可以阅读下面的文章：
第一篇文档必须阅读，接下来是对第二篇文章中的复制状态机部分的翻译。
复制状态机（Replicated state machines）
共识算法通常出现在复制状态机的语境中。通过这种方法，不同服务器上的状态机可以拥有相同的状态副本，并且在部分服务器宕机的情况下，集群可以继续提供服务。在分布式系统中，可以使用复制状态机解决各种各样的故障容错问题。比如，GFS、HDFS、RAMCloud 之类的、具有单个主节点的大型系统，通常使用单独的复制状态机来管理主节点选举，以及存储用于拯救主节点崩溃的配置信息。复制状态机的实现包括 Chubby 和 ZooKeeper。
如上图所示，通常使用复制日志来实现复制状态机。每台服务存储包含一系列命令的日志，服务器上的状态机按顺序执行这些命令。不同服务器上的日志包含相同顺序的相同命令，因此所有状态机处理相同的命令序列。由于状态机是确定性的，所以所有状态机拥有相同的状态和相同的输出序列。
共识算法的工作是保持复制日志一致。服务器上的共识模块接收客户端命令，然后把它们添加到日志中。它与其它服务器上的共识模块进行通信，确保所有日志最终包含相同顺序的相同请求（即使某些服务器发生故障）。正确地复制命令后，每台服务器上的状态机按照日志顺序处理它们，并将输出返回给客户端。最终，所有服务器看起来像是单独的、高可靠的状态机。
用于实际系统的共识算法通常具有如下属性：
- 在所有非拜占庭条件下保证安全（绝不会返回错误结果），这些条件包括网络延迟、分区，数据包丢失、重复和重排
- 只要大多数服务器正常运行，并且能与其它服务器和客户端进行通信，那么共识算法就可以正常工作。因此由五台服务器组成的集群能容忍其中任意两台失败。假设服务器因停止而发生失败，它们之后可以从稳定的存储中的状态进行恢复，并重新加入集群
- 不依赖时间来保证日志的一致性：在最糟糕的情况下，错误的时钟和极端的消息延迟会导致可用性问题
- 在常规情况下，一旦集群中的大多数服务器响应 PRC，命令就可以完成 。少数慢速服务器不必影响整体系统性能
Raft 的 Golang 实现
Raft 的 Golang 实现包括 Etcd 使用的 etcd-raft、Consul 使用的 hashicorp/raft 等。下面是 etcd-raft README.md 的部分翻译。
通过 Raft 协议，集群中的节点可以维护一个复制状态机，通过复制日志使状态机保持同步。查看 Diego Ongaro 和 John Ousterhout 编写的 In Search of an Understandable Consensus Algorithm 获取更多关于 Raft 的细节。
该 Raft 库是稳定的，并且实现了全部 Raft 特性。自 2016 年起，它被广泛应用在生产环境中，每天为数以万计的集群提供服务。它为 etcd、Kubernetes、Docker Swarm、Cloud Foundry Diego、CockroachDB、TiDB、Project Calico、Flannel、Hyperledger 等分布式系统提供动力。
大多数 Raft 实现具有庞大的设计，包括存储处理，消息序列化，以及网络传输。而该库遵循极简的设计哲学，只实现了核心 Raft 算法。这种极简主义提高了灵活性、确定性和性能。
为了保持基础代码简洁以及提供灵活性，该库只实现了 Raft 算法；网络和磁盘 IO 都留给用户实现。用户必须自己实现用于在 Raft 节点之间传递消息的传输层。类似地，用户必须自己实现用于持久化 Raft 日志和状态的存储层。
为了方便地测试该 Raft 库，它的行为必须是确定性的。为实现该确定性，该库将 Raft 模型化为状态机。状态机接受 Message 作为输入。Message 既可以是本地的定时更新，也可以是来自远端节点的网络消息。状态机的输出是一个三元组 {[]Messages, []LogEntries, NextState}，它包含 Message 和 log entries 的数组和 Raft 状态变更。对于具有相同状态的不同状态机而言，相同的状态机输入必须生成相同的状态机输出。
raftexample 是一个简单的示例程序，可以通过该程序学习如何使用该包：https://github.com/etcd-io/etcd/tree/main/contrib/raftexample。接下将对 raftexample 的源代码进行解析。
raftexample 源码解析
构建和运行
关于如何构建和运行 raftexample，请直接参考 README.md。
设计
raftexample 包含三个组件：raft 支持的键值存储，REST API 服务，以及基于 etcd raft 实现的 raft 共识服务。
raft 支持的键值存储持有所有已提交的键值。该存储是 raft 服务和 REST 服务之间沟通的桥梁。键值更新通过该存储被下发到 raft 服务。一旦 raft 报告该更新被提交，那么该存储会更新它的 Map。
REST 服务通过访问这个 raft 支持的键值存储，暴漏当前的 raft 共识。GET 命令用于在该存储中寻找键，并返回值（如有）。PUT 命令用于向该存储发起更新提议。
raft 服务与集群中的其它节点参与共识。当 REST 服务提交提议时，raft 服务将该提议传输给其它节点。当 raft 达成共识时，raft 服务通过 commit 管道发布所有已提交的更新命令。对于 raftexample 而言，键值存储消费该 commit 管道。
预备知识
1，预写日志（WAL）
在计算机科学中，WAL（write-ahead logging）是数据库中用于提供原子性和持久性（两个 ACID 特性）的一系列技术。使用 WAL 的好处是：
- 在大多数场景下，WAL 明显更快
- WAL 可以提高并发，因为读不会阻塞写，写不会阻塞读。读和写可以并发处理
- 使用 WAL，磁盘 IO 操作更加顺序
使用 WAL 方式时，原始内容被保存在磁盘文件，所有更新操作会被追加到单独的 WAL 文件。当然，最终会将被追加到 WAL 文件的事务转移回原始文件。把 WAL 文件事务移回原始文件被称为“检查点”。如果想要了解更多关于 WAL 的内容，可以浏览 READ MORE 中的链接。
2，快照（Snapshot）
Snapshot 是指定数据集合的一个完整可用拷贝，该拷贝包括相应数据在某个时间点的映像。
3，WAL 和 Snapshot 之间的关系
设 T1 时刻的快照是 Snapshot1，那么将 WAL 中 (T1, T2] 之间的事务日志应用到 Snapshot1，将得到 T2 时刻的快照 Snapshot2。因为 WAL 中 T2 时刻及以前的事务日志已经被应用，所以可以释放 WAL 中 T2 时刻及以前的事务日志。
点击 replay-wal.jpg 查看 raftexample 的 Replay WAL 流程。
点击 snapshot-raftexample.jpg 查看 raftexample 的快照生成（raftNode.maybeTriggerSnapshot()）流程。
比如在 HDFS 中，editlog 是 WAL；fsimage 是 snapshot；checkpoint 是生成快照的流程
架构
