概论

分布式共识算法(consensus algorithm)通常的做法就是在多个节点上复制状态机。分布在不同服务器上的状态机执行着相同的状态变化，即使其中几台机器挂掉，整个集群还能继续运作。
复制状态机正确运行的核心的同步日志，日志是保证各节点状态同步的关键，日志中保存了一系列状态机命令，共识算法的核心是保证这些不同节点上的日志以相同的顺序保存相同的命令，由于状态机是确定的，所以相同的命令以相同的顺序执行，会得到相同的结果。
raft协议保证系统在任何时刻都保持一下特性：
1. 选举安全：每次给定的Term，整个集群只能选上一个leader。
2. leader只追加日志： leader永远不会改写或者删除日志中的条目，它只会追加日志。
3. 日志匹配： 如果两个节点的日志包含了相同的index和term的条目，则这两个节点的日志中，该条目及以后的条目都一样。
4. leader日志完整性： 在一个term中如果1条日志已经commit，那么后续的term中选举出来的leader一定存有这条日志。
5. 状态机安全性：如果一个server已经apply了一条日志条目到状态机中，则其他的server不会apply一调相同index但是不同的日志。

其中1、4、5中我们在心跳和选举一章已经有所阐述，我们将在这一章中详细阐述etcd是如何保证所有这5条特性成立的。

日志的基本形式和存储方式

日志的是以条目(Entry)的方式顺序组织在一起的，日志中包含index、term、type和data等字段。index随日志条目的递增而递增，term是生成该条目的leader当时处于的term。type是etcd定义的字段，目前有两个类型，一个是EntryNormal正常的日志，EntryConfChange是etcd本身配置变化的日志。data是日志的内容。

内存中的日志操作，主要是由一个raftLog类型的对象完成的，以下是raftLog的源码。可以看到，里面有两个存储位置，一个是storage是保存已经持久化过的日志条目。unstable是保存的尚未持久化的日志条目。

持久化日志： WAL和snapshot。下图显示持久化的Storage接口定义和storage结构中字段的定义。它实际上就是包含一个WAL来保存日志条目，一个Snapshotter负责保存日志快照的。

WAL是一种追加的方式将日志条目一条一条顺序存放在文件中。存放在WAL的记录都是walpb.Record形式的结构。Type代表数据的类型，Crc是生成的Crc校验字段。Data是真正的数据。v3版本中，有下图显示的几种Type：
- metadataType：元数据类型，元数据会保存当前的node id和cluster id。
- entryType：日志条目
- stateType：存放的是集群当前的状态HardState，如果集群的状态有变化，就会在WAL中存放一个新集群状态数据。里面包括当前Term，当前竞选者、当前已经commit的日志。
- crcType：存放crc校验字段。读取数据是，会根据这个记录里的crc字段对前面已经读出来的数据进行校验。
- snapshotType：存放snapshot的日志点。包括日志的Index和Term。
WAL有read模式和write模式，区别是write模式会使用文件锁开启独占文件模式。read模式不会独占文件。

Snapshotter 提供保存快照的SaveSnap方法。在v2中，快照实际就是storage中存的那个node组成的树结构。它是将整个树给序列化成了json。在v3中，快照是boltdb数据库的数据文件，通常就是一个叫db的文件。v3的处理实际代码比较混乱，并没有真正走snapshotter。

etcd日志的保存总体流程如下：
1. 集群某个节点收到client的put请求要求修改数据。节点会生成一个Type为MsgProp的Message，发送给leader。

2. leader收到Message以后，会处理Message中的日志条目，将其append到raftLog的unstable的日志中，并且调用bcastAppend()广播append日志的消息。
3. leader中有协程处理unstable日志和刚刚准备发送的消息，newReady方法会把这些都封装到Ready结构中。
4. leader的另一个协程处理这个Ready，先发送消息，然后调用WAL将日志持久化到本地磁盘。

5. follower收到append日志的消息，会调用它自己的raftLog，将消息中的日志append到本地缓存中。随后follower也像leader一样，有协程将缓存中的日志条目持久化到磁盘中并将当前已经持久化的最新日志index返回给leader。

6. 所有节点，包括follower 和leader都会将已经认定为commit的日志apply到kv存储中。对于v2就是更新store中的树节点。对于v3就是调用boltdb的接口更新数据。

7. 日志条目到一定数目以后，会触发snapshot，leader会持久化保存第6步所说的kv存储的数据。然后删除内存中过期的日志条目。
8. WAL中保存的持久化的日志条目会有一个定时任务定时删除。
以下将以v3代码为例，详细分析以上过程

日志的生成

1. v3操作etcd一般是直接使用etcd提供的client库，因为v3的client和server也采用grpc通信，直接用httpclient会非常复杂。Client结构中包含了一个叫KV的接口，里面定义了Put、Get、Delete等方法。Put方法的实现实际就是向其中一个server发送一条grpc请求，请求体正是PutRequest结构的对象。

2. 服务端收到gprc请求以后，会调用EtcdServer的Put()、Range()、DeleteRange()、Txn()等方法，这些方法最终都会调用到processInternalRaftRequestOnce()，这个方法的处理是先用request的id注册一个channel，调用raftNode的Propose()方法，将request对象序列化成byte数组，作为参数传入Propose()方法，最后等待刚刚注册的channel上的数据，node会在请求已经apply到状态机以后，也就是请求处理结束以后，往这个channel推送一个ApplyResult对象，触发等待它的请求处理协程继续往下走，返回请求结果。

3、raftNode的Propose方法实现在node结构上。它会生成一条MsgProp消息，消息的Data字段是已经序列化的request。也就是说v3中，日志条目的内容就是request。最后调用step()方法，是把消息推到propc channel中。

4、propc channel由node启动时运行的一个协程处理，调用raft的Step()方法，如果当前节点是follower，实际就是调用stepFollower()。而stepFollower对MsgProp消息的处理就是：直接转发给leader。

5、实例之间消息发送的过程在本系列文章的第二篇《心跳与选举》中已经介绍，不在赘述。消息到leader以后。下图是leader的处理，leader在接收到MsgProp消息以后，会调用appendEntries()将日志append到raftLog中。这时候日志已经保存到了leader的缓存中。

leader同步日志

1. 从上图可以看到，leader在append日志以后会调用bcastAppend()广播日志给所有其他节点。raft结构中有一个Progress数组，这个数组是leader用来保存各个follower当前的同步状态的，由于不同实例运行的硬件环境、网络等条件不同，各follower同步日志的快慢不一样，因此leader会在本地记录每个follower当前同步到哪了，才能在每次同步日志的时候知道需要发送那些日志过去。Progress中有一个Match字段，代表其中一个follower当前已经同步过的最新的index。而Next字段是需要leader发送给它的下一条日志的index。
   sendAppend先根据Progress中的Next字段获取前一条日志的term，这个是为了给follower校验用的，待会我们会讲到。然后获取本地的日志条目到ents。获取的时候是从Next字段开始往后取，直到达到单条消息承载的最大日志条数(如果没有达到最大日志条数，就取到最新的日志结束，细节可以看raftLog的entries方法)。

2如果获取日志有问题，说明Next字段标示的日志可能已经过期，需要同步snapshot，这个就是上图的if语句里面的内容。这部分我们等snapshot的时候再细讲。

3正常获取到日志以后，就把日志塞到Message的Entries字段中，Message的Type为MsgApp，表示这是一条同步日志的消息。Index设置为Next-1，和LogTerm一样，都是为了给follower校验用的，下面会详细讲述。设置commit为raftLog的commited字段，这个是给follower设置它的本地缓存里面的commited用的。最后的那个”switch pr.State”是一个优化措施，它在send之前就将pr的Next值设置为准备发送的日志的最大index+1。意思是我还没有发出去，就认为它发完了，后面比如leader接收到heartbeat response以后也可以直接发送entries。

4、follower接收到MsgApp以后会调用handleAppendEntries()方法处理。处理逻辑是：如果index小于已经确认为commited的index，说明这些日志已经过期了，则直接回复commited的index。否则，调用maybeAppend()把日志append到raftLog里面。maybeAppend的处理比较重要。首先它通过判断消息中的Index和LogTerm来判断发来的这批日志的前一条日志和本地存的是不是一样，如果不一样，说明leader和follower的日志在Index这个地方就没有对上号了，直接返回不能append。如果是一样的，再进去判断发来的日志里面有没有和本地有冲突（有可能有些日志前面已经发过来同步过，所以会出现leader发来的日志已经在follower这里存了）。如果有冲突，就从第一个冲突的地方开始覆盖本地的日志。

5、follower调用完maybeAppend以后会调用send发送MsgAppResp，把当前已经append的日志最新index告诉给leader。如果是maybeAppend返回了false说明不能append，会回复Reject消息给leader。消息和日志最后都是在raftNode.start()启动的协程里面处理的。它会先持久化日志，然后发送消息。

6、leader收到follower回复的MsgAppResp以后，首先判断如果follower reject了日志，就把Progress的Next减回到Match+1，从已经确定同步的日志开始从新发送日志。如果没有reject日志，就用刚刚已经发送的日志index更新Progess的Match和Next，下一次发送日志就可以从新的Next开始了。然后调用maybeCommit把多数节点同步的日志设置为commited。

7、commited会随着MsgHeartbeat或者MsgApp同步给follower。随后leader和follower都会将commited的日志apply到状态机中，也就是会更新kv存储。

持久化

日志的持久化是调用WAL的Save完成的，同时如果有raft状态变更也会写到WAL中(作为stateType)。日志会顺序地写入文件。同时使用MustSync判断是不是要调用操作系统的系统调用fsync，fsync是一次真正的io调用。从MustSync函数可以看到，只要有log条目，或者raft状态有变更，都会调用fsync持久化。最后我们看到如果写得太多超过了一个段大小的话(一个段是64MB，就是wal一个文件的大小)。会调用cut()拆分文件。