ETCD原理

无论是Paxos还是Raft，它们都是致力于维护一RSM(Replicated State Machine)，如上图所示。对于RSM来说，状态存储是非常关键的

(Replicated State Machine)状态机：一致性group的节点的某个时刻的状态(比如数据库里x=1,y=1是一个状态)转移可以看成自动机里的一个状态，所以叫状态机。
Replicated Log: 包含了来自客户端的用于执行在状态机上的命令(操作)。

ETCD架构图

Etcd raft lib的snapshot处理流程
snapshot的是系统状态的完整快照，其他系统接收和回放snapshot，将自身数据恢复到一个一致性状态。本文介绍一下etcd raft lib如何支持snapshot功能，主要包括：

生成snapshot
Leader发送snapshot
Follower接收和应用snapshot
1.数据结构

type ConfState struct {
    Nodes            []uint64 `protobuf:"varint,1,rep,name=nodes" json:"nodes,omitempty"`
    XXX_unrecognized []byte   `json:"-"`
}
type SnapshotMetadata struct {
    ConfState        ConfState `protobuf:"bytes,1,opt,name=conf_state,json=confState" json:"conf_state"`
    Index            uint64    `protobuf:"varint,2,opt,name=index" json:"index"`
    Term             uint64    `protobuf:"varint,3,opt,name=term" json:"term"`
    XXX_unrecognized []byte    `json:"-"`
}

type Snapshot struct {
    Data             []byte           `protobuf:"bytes,1,opt,name=data" json:"data,omitempty"`
    Metadata         SnapshotMetadata `protobuf:"bytes,2,opt,name=metadata" json:"metadata"`
    XXX_unrecognized []byte           `json:"-"`
}

2.生成snapshot
etcd会在每次apply entry的时候，判断是否需要生成snapshot。判断的条件就是apply raft index 和上一个snapshot 中的index差距是否超过一定范围。如果超过，则触发snapshot服务。具体函数流程如下图所示：

由于etcd的snapshot生成和VDL生成snapshot不一样，这里就不做详细分析。

3.Leader发送snapshot
Leader在stepLeader函数中，会根据Follower的Next值向该Follower发送raft log。如果Leader上raft entry不存在，则会发送snapshot给follower。详细的函数调用流程如下图所示：

各个函数作用如下：

sendAppend:Leader根据Follower的进度发送raft log。
r.raftLog.snapshot:调用存储引擎，获取最新的snapshot。
pr.becomeSnapshot:将该follower状态修改为ProgressStateSnapshot，表示正在发送snapshot。
send:将snapshot类型的message发送给follower。
newReady:将snapshot类型的message封装在一个Ready结构中，最终raft状态机会将Ready结构体交给应用来处理。
raftNode.start:在应用的外围循环中，会不断处理raft状态机传递出来的Ready结构体，对于snapshot会在r.processMessages函数中做处理。
r.processMessages:将包含snapshot信息的message传递给msgSnapC。
applyAll:该函数会接收msgSnapC中的消息，并调用transport发送snapshot。
transport.SendSnapshot:调用transport层发送snapshot。
peer.sendSnap:调用对应的peer的发送snapshot函数。
snapshotSender.send:真正的snapshot发送操作。
4.Follower接收和应用snapshot
Follower上对snapshot的处理主要分为接收和应用snapshot两个部分，http包会创建一个goroutine来专门接收snapshot。接收完成后，会将消息传入raft状态机，然后通过消息类型来驱动状态机。具体的函数调用流程如下所示：

上述主要函数作用如下所示：

snapshotHandler.ServeHTTP:snapshot的handler会一直等待接收snapshot，如果收到snapshot会将其写到磁盘。
snapshotter.SaveDBFrom:将收到snapshot会写到磁盘
Process:将收到snapshot的消息发送到raft 状态机
stepFollower:Follower收到MsgSnap消息后进入该函数。
handleSnapshot:snapshot对应的消息类型是:MsgSnap，会调用handleSnapshot。
r.restore:清空unstable中的entries，并将snapshot保存到unstable中。
newReady:根据unstable中的snapshot设置Ready结构体。
raftNode.start:将snapshot发送到applyAll对应的goroutine
applyAll:调用applySnapshot
applySnapshot:etcd中应用snapshot的过程。

从etcd的架构图中可以看到，etcd主要分为四个部分：

HTTP Server： 用于处理用户发送的API请求以及其它etcd节点的同步与心跳信息请求。

Store：这个模块顾名思义，就像一个商店把etcd已经准备好的各项底层支持加工起来，为用户提供五花八门的API支持，处理用户的各项请求。

用于处理etcd支持的各类功能的事务，包括数据索引、节点状态变更、监控与反馈、事件处理与执行等，是etcd对用户提供的大多数API功能的具体实现。

Raft： raft 状态机，raft强一致性算法的具体实现，是etcd的核心。

WAL：Write Ahead Log（预写式日志），是etcd的数据存储方式。除了在内存中存有所有数据的状态以及节点的索引以外，etcd就通过WAL进行持久化存储。WAL中，所有的数据提交前都会事先记录日志。Entry表示存储的具体日志内容。

随着使用量的增加，当WAL文件中数据项内容过大达到设定值（默认为10000）时，会进行WAL的切分，同时进行snapshot操作，经过snapshot以后的WAL文件就可以删除。而通过API可以查询的历史etcd操作默认为1000条。实际上数据目录中有用的snapshot和WAL文件各只有一个，默认情况下etcd会各保留5个历史文件。

故障快速恢复/回滚（undo）/重做（redo） ：所有的修改操作都被记录在WAL，可以通过执行所有WAL中记录的修改操作，快速从最原始的数据恢复到之前的状态。

通常，一个用户的请求发送过来，会经由HTTP Server转发给Store进行具体的事务处理，如果涉及到节点的修改，则交给Raft模块进行状态的变更、日志的记录，然后再同步给别的etcd节点以确认数据提交，最后进行数据的提交，再次同步。

集群选主

Raft协议是用于维护一组服务节点数据一致性的协议。这一组服务节点构成一个集群，并且有一个主节点来对外提供服务。当集群初始化，或者主节点挂掉后，面临一个选主问题。集群中每个节点，任意时刻处于Leader（主）, Follower（从）, Candidate（候选）这三个角色之一。

选举特点如下：

•当集群初始化时候，每个节点都是Follower角色；

•集群中存在至多1个有效的主节点，通过心跳与其他节点同步数据；

•当Follower在一定时间内没有收到来自主节点的心跳，会将自己角色改变为Candidate，并发起一次选主投票；当收到包括自己在内超过半数节点赞成后，选举成功；当收到票数不足半数选举失败，或者选举超时。若本轮未选出主节点，将进行下一轮选举（出现这种情况，是由于多个节点同时选举，所有节点均为获得过半选票）。

•Candidate节点收到来自主节点的信息后，会立即终止选举过程，进入Follower角色。

为了避免陷入选主失败循环，每个节点未收到心跳发起选举的时间是一定范围内的随机值，这样能够避免2个节点同时发起选主。

集群大小与容错

集群的大小指集群节点的个数。根据 etcd 的分布式数据冗余策略，集群节点越多，容错能力(Failure Tolerance)越强，同时写性能也会越差。所以关于集群大小的优化，其实就是容错和写性能的一个平衡。

ETCD推荐使用【奇数】作为集群节点个数。原因有二：

一、奇数个节点与和其配对的偶数个节点相比(比如 3节点和4节点对比)，容错能力相同，却可以少一个节点。

二、偶数个节点集群不可用风险更高，表现在选主过程中，有较大概率等额选票，从而出发下一轮选举。

所以综合考虑性能和容错能力，etcd 官方文档推荐的 etcd 集群大小是 3, 5, 7。至于到底选择 3,5 还是 7，根据需要的容错能力而定。

关于节点数和容错能力对应关系，如下表所示：

日志复制

所谓日志复制，是指主节点将每次操作形成日志条目，并持久化到本地磁盘，然后通过网络IO发送给其他节点。其他节点根据日志的逻辑时钟(TERM)和日志编号(INDEX)来判断是否将该日志记录持久化到本地。当主节点收到包括自己在内超过半数节点成功返回，那么认为该日志是可提交的(committed），并将日志输入到状态机，将结果返回给客户端。

这里需要注意的是，每次选主都会形成一个唯一的TERM编号，相当于逻辑时钟。每一条日志都有全局唯一的编号。

主节点通过网络IO向其他节点追加日志。若某节点收到日志追加的消息，首先判断该日志的TERM是否过期，以及该日志条目的INDEX是否比当前以及提交的日志的INDEX跟早。若已过期，或者比提交的日志更早，那么就拒绝追加，并返回该节点当前的已提交的日志的编号。否则，将日志追加，并返回成功。

当主节点收到其他节点关于日志追加的回复后，若发现有拒绝，则根据该节点返回的已提交日志编号，发送其编号下一条日志。

主节点像其他节点同步日志，还作了拥塞控制。具体地说，主节点发现日志复制的目标节点拒绝了某次日志追加消息，将进入日志探测阶段，一条一条发送日志，直到目标节点接受日志，然后进入快速复制阶段，可进行批量日志追加。

按照日志复制的逻辑，我们可以看到，集群中慢节点不影响整个集群的性能。另外一个特点是，数据只从主节点复制到Follower节点。

安全性

截止此刻，选主以及日志复制并不能保证节点间数据一致。试想，当一个某个节点挂掉了，一段时间后再次重启，并当选为主节点。而在其挂掉这段时间内，集群若有超过半数节点存活，集群会正常工作，那么会有日志提交。这些提交的日志无法传递给挂掉的节点。当挂掉的节点再次当选主节点，它将缺失部分已提交的日志。在这样场景下，按Raft协议，它将自己日志复制给其他节点，会将集群已经提交的日志给覆盖掉。

这显然是不可接受的。

其他协议解决这个问题的办法是，新当选的主节点会询问其他节点，和自己数据对比，确定出集群已提交数据，然后将缺失的数据同步过来。这个方案有明显缺陷，增加了集群恢复服务的时间（集群在选举阶段不可服务），并且增加了协议的复杂度。

Raft解决的办法是，在选主逻辑中，对能够成为主的节点加以限制，确保选出的节点已定包含了集群已经提交的所有日志。如果新选出的主节点已经包含了集群所有提交的日志，那就不需要从和其他节点比对数据了。简化了流程，缩短了集群恢复服务的时间。

这里存在一个问题，加以这样限制之后，还能否选出主呢？答案是：只要仍然有超过半数节点存活，这样的主一定能够选出。因为已经提交的日志必然被集群中超过半数节点持久化，显然前一个主节点提交的最后一条日志也被集群中大部分节点持久化。当主节点挂掉后，集群中仍有大部分节点存活，那这存活的节点中一定存在一个节点包含了已经提交的日志了。