Etcd源码分析（一）Raft算法

本文是Etcd源码分析系列文章的第一篇，将重点从理论上分析Etcd的一致性算法 - Raft。

1. 分布式基础理论

当前，微服务架构日益普遍，虽然大多数微服务本身是无状态的，但是它们通常会操作一些含有数据的分布式系统，如数据库、缓存等。在本小节中，将先简单回顾一下分布式理论的一些知识点。

1.1 分布式基础

分布式系统

分布式系统由多个不同的服务节点组成，节点与节点之间通过消息进行通信和协调。根据消息机制的不同，分布式系统的运行模型可以分为异步模型系统 和同步模型系统。

分布式系统的一致性

在一个分布式系统中，保证集群中所有节点中的数据完全相同，并且能够对某个提案达成一致，是分布式系统正常工作的核心。

但由于引入了多个节点，分布式系统中常会出现各种各样非常复杂的情况，包括节点宕机、通信受到干扰/阻断、节点间运行速度存在差异等等，即当多个节点通过异步通讯方式组成网络集群时，这种异步网络默认是不可靠的，那么，如何保证这些不可靠节点的状态最终能达成相同一致的状态，此即分布式系统的一致性问题，而解决此类问题的算法即为共识算法。

1.2 分布式理论

ACID原则

• 原子性（Atomicity）：每次操作是原子的

• 一致性（Consistency）：数据库的状态是一致的

• 隔离性（Isolation）：各种操作彼此之间互相不影响

• 持久性（Durability）：状态的改变是持久的

ACID是传统数据库常用的设计理念，追求强一致性。

BASE理论

• 基本可用（Basically Available）：指分布式系统在出现故障的时候，允许损失部分可用性

• 软状态（Soft State）：允许系统存在中间状态，而该中间状态不会影响系统整体可用性

• 最终一致性（Eventual Consistency）：系统中的所有数据副本经过一定时间后，最终能够达到一致的状态

CAP理论

一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容忍性（Partition tolerance）这三项中的两项，其中：

• 一致性（Consistency）：强一致性，所有节点在同一时间的数据完全一致

• 可用性（Availability）：分布式系统可以在正常响应的时间内提供相应的服务

• 分区容忍性（Partition tolerance）：在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务

CAP原理最早是2000年由Eric Brewer在ACM组织的一个研讨会上提出猜想，后来Lynch等人进行了证明，该原理被认为是分布式系统领域的重要原理之一。

FLP不可能原理

在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

这个定理告诉我们，不要浪费时间去为异步分布式系统设计在任意场景上都能够实现共识的算法，异步系统完全没有办法保证能在有限时间内达成一致。

该原理见于由Fischer、Lynch和Patterson三位科学家于1985年发表的论文《Impossibility of Distributed Consensus with One Faulty Process》，该定理被认为是分布式系统中重要的原理之一。

1.3 共识算法

拜占庭将军问题

拜占庭将军问题是 Leslie Lamport 在《 The Byzantine Generals Problem》 论文中提出的分布式领域的容错问题，它是分布式领域中最复杂、最严格的容错模型。

在该模型下，系统不会对集群中的节点做任何的限制，它们可以向其他节点发送随机数据、错误数据，也可以选择不响应其他节点的请求，这些无法预测的行为使得容错这一问题变得非常复杂。

解决非拜占庭将军容错的一致性问题

拜占庭将军问题是对分布式系统容错的最高要求，但在日常工作中使用的大多数分布式系统中不会面对所有这些复杂的问题，我们遇到更多的还是节点故障、宕机或者不响应等情况，这就大大简化了系统对容错的要求，解决此类问题的常见算法：

• paxos

• raft

• zab

Leslie Lamport 提出的 Paxos 可以在没有恶意节点的前提下保证系统中节点的一致性，也是第一个被证明完备的共识算法

解决拜占庭将军容错的一致性问题

解决此类问题的常见算法：

• pow

• pos

• dpos

1.4 复制状态机

复制状态机（replicated state machine）通常是基于复制日志实现的，每一个节点存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。

由于每一个日志都按照相同的顺序包含相同的指令，所以每一个节点都执行相同的指令序列后，都会产生相同的状态，即，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。

而保证复制日志相同就是共识算法的工作了。

2. Raft算法

Raft ，是一种用来管理日志复制的一致性算法。

论文原文： In search of an Understandable Consensus Algorithm (Extended Version)

论文翻译：Raft 一致性算法论文译文。

Raft算法在论文中有详细的描述，建议阅读，本小节只针对算法中的关键点作部分说明。

2.1 Paxos与Raft

早在 1990 年，Leslie Lamport向 ACM Transactions on Computer Systems (TOCS) 提交了关于 Paxos 算法的论文The Part-Time Parliament。但Paxos 很难理解，而且，Paxos 需要经过复杂的修改才能应用于实际中。实际上，目前工程实践中所有声称基于Paxos实现的系统都非真正的Paxos系统。

Raft是一种在可理解性上更容易的一种一致性算法。可理解性是作者非常强调的一点，引用作者在论文中的结语：

算法的设计通常会把正确性，效率或者简洁作为主要的目标。尽管这些都是很有意义的目标，但是我们相信，可理解性也是一样的重要。在开发者把算法应用到实际的系统中之前，这些目标没有一个会被实现，这些都会必然的偏离发表时的形式。除非开发人员对这个算法有着很深的理解并且有着直观的感觉，否则将会对他们而言很难在实现的时候保持原有期望的特性。

2.2 Raft的可理解性设计

为使得大多数人能够很容易理解，Raft在设计上采用了一下两种方式：

1. 问题分解：将问题分解成为若干个可解决的、可被理解的小问题。在 Raft 中，把问题分解成为了领导选取（leader election）、日志复制（log replication）、安全（safety）和成员变化（membership changes）。

2. 状态空间简化：减少需要考虑的状态的数量。在 Raft 中，使用随机化选举超时来简化了领导选取算法，随机化方法使得不确定性增加，但是它减少了状态空间。

2.3 选举和日志复制

选举和日志复制的具体过程，参见论文描述，或动画演示。

2.3.1 Raft的一致性原则

选举安全原则（Election Safety）：

一个任期（term）内最多允许有一个领导人被选上

领导人只增加原则（Leader Append-Only）：

领导人永远不会覆盖或者删除自己的日志，它只会增加条目

日志匹配原则（Log Matching Property）:

如果在不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的

如果在不同日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。

领导人完全原则（Leader Completeness)：

如果一个日志条目在一个给定任期内被提交，那么这个条目一定会出现在所有任期号更大的领导人中

状态机安全原则（State Machine Safety）：

如果一台服务器将给定索引上的日志条目应用到了它自己的状态机上，则所有其他服务器不会在该索引位置应用不同的条目

2.3.2 Raft的安全性约束

在所有的以领导人为基础的一致性算法中，领导人最终必须要存储全部已经提交的日志条目。

Raft 算法在领导人选取部分加入了一个限制，这个限制能够保证对于固定的任期，任何的领导人都拥有之前任期提交的全部日志条目，即：

Raft 使用投票的方式来阻止没有包含全部日志条目的服务器赢得选举。RequestVote RPC 实现了这个限制：这个 RPC（远程过程调用）包括候选人的日志信息，如果它自己的日志比候选人的日志要新，那么它会拒绝候选人的投票请求。

2.4 集群成员变更

将集群成员变更纳入到算法中是Raft易于应用到实践中的关键。它支持自动化配置，即配置可以在集群运行期间进行动态变更而不影响可用性。

在Raft的论文中，简要说明了一种一次变更多个节点的方式，但是没有在安全性和可用性上给出更多的说明。而实际上，Raft的开源实现，如Etcd，都采用了更加简洁的一次只能变更一个节点的算法。

在实际工程实现过程中，Raft作者也更加推荐一次变更一个节点的方式，首先因为简单，其次所有的集群变更方式都可以通过 一次变更一个节点的方式达到任何想要的集群状态。

为了保证安全性，Raft对集群配置的调整采用了两阶段的方式。从一个配置直接切换到另一个配置是不安全的，因为不同的服务器会在不同的时间点进行切换，而在某个时间点有可能两个服务器同时被选举成为领导人。

两阶段变更的方式：

第一阶段：共同一致（过渡阶段）

• 领导者收到从旧配置到新配置的变更请求时，创建共同一致的日志并复制给其他节点

• 追随者以最新的配置做决定，领导者需要以已经提交的配置来做决定

• 新旧配置中所有机器都可能成为领导者

• 达成一致要在新旧配置上均获得大多数支持

第二阶段：切换到新配置

• 提交新配置的日志到所有节点，一旦新配置的日志被提交，即完成变更

2.5 日志压缩

在实际的系统中，Raft 产生的日志在持续的正常操作中不断增长，但不可以无限的增长下去。

快照（snapshot）是最简单的压缩方式。在快照中，全部的当前系统状态都被写入到快照中，存储到持久化的存储中，然后在那个时刻之前的全部日志都可以被丢弃。

Raft快照基本思想：

• 每个服务器独立创建快照，只包括已经被提交的日志

• 快照值存储了当前的状态、最后的索引位置和任期号

• 快照完成后，删除最后索引位置之前的所有日志和快照

• 领导人必须偶尔的发送快照给一些落后的跟随者

2.6 客户端交互

客户端和 Raft 进行交互包括两方面内容：

• 客户端是如何发现领导者的

• Raft 是如何支持线性化语义（linearizable semantics）的

线性化语义，指每一次操作立即执行，在它调用和收到回复之间只执行一次

客户端发现领导者

Raft 中的客户端将所有请求发送给领导人。

当客户端启动的时候，它会随机挑选一个服务器进行通信。

如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供它最近接收到的领导人的信息（附加条目请求包含了领导人的网络地址）。

如果领导人已经崩溃了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

支持线性化语义

客户端对于每一条指令都赋予一个唯一的序列号。

状态机跟踪每条指令最新的序列号和相应的响应。

如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

本章总结

本章回顾了分布式理论的核心知识点，并重点梳理了Raft算法的相关内容，包括设计原则、集群变更、快照思想和客户端交互。本章没有对算法过程进行详细叙述，因为关于算法在论文中有清晰而详细的描述，强烈建议阅读论文原文。

参考资料

1. Raft 一致性算法论文译文：https://www.infoq.cn/article/raft-paper

2. 共识算法：Raft：https://www.jianshu.com/p/8e4bbe7e276c

3. CoreOS 实战：剖析 etcd：https://www.infoq.cn/article/coreos-analyse-etcd/

4. 微信 PaxosStore：深入浅出 Paxos 算法协议：https://www.infoq.cn/article/wechat-paxosstore-paxos-algorithm-protocol?utm_source=related_read&utm_medium=article

5. 谈谈分布式系统中的复制：http://www.voidcn.com/article/p-sfcgwsjt-zg.html

6. Bully算法：http://www.distorage.com/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E6%8A%80%E6%9C%AF%E7%B3%BB%E5%88%97-%E9%80%89%E4%B8%BB%E7%AE%97%E6%B3%95/

7. 分布式一致性与共识算法：https://draveness.me/consensus

8. membership：https://zhuanlan.zhihu.com/p/29678067

9. 分布式系统中的FLP不可能原理、CAP理论与BASE理论：https://zhuanlan.zhihu.com/p/35608244