Raft

etcd-raft 有关 log 的实现在分布在log.go，log_unstable.go，storage.go 三个文件中。首先看一下 raftLog 结构体。 raftLog 结构体 type raftLog struct { // storage contains all stable entries since the last snapshot. storage Storage // unstable contains all unstable entries and snapshot. // they will be saved into storage. unstable unstable // committed is the highest log position that is known to be in // stable storage on a quorum of nodes. committed uint64 // applied is the highest log position that the application has // been instructed to apply to its state machine. // Invariant: applied <= committed applied uint64 } 其中 Storage 存放 stable 的 log，它是一个接口，具体实现可由应用层控制，在 raftexample 和 etcd server 中都是用了 默认的实现 MemoryStorage unstable 存放的是还未放到 stable 中的 log，可见实际上无论是 stable 还是 unstable，他们都是存在内存中的，那么不怕断点导致的丢失吗？ 其实真正生产环境中使用的 etcd server 在写入 MemoryStorage 前还要写入 WAL 和 snapshot，也就是说，etcd的稳定存储是通过快照、预写日志、MemoryStorage 三者共同实现的。具体细节本文先不讨论。 committed 表示该节点所知数量达到quorum的节点保存到了 stable 中的日志里，index最高的日志的index applied 表示该节点的应用程序已应用到其状态机的日志里，index最高的日志的index。 由此可见，committed 和 applied 都是在 stable 中，不在 unstable。 他们的关系如下所示 ...

首先看一下 raft node 之间传递的基本消息（比如 leader 选举，AppendLog）类型 Message protobuf 定义 message Message { optional MessageType type = 1 ; optional uint64 to = 2 ; optional uint64 from = 3 ; // 整个消息发出去时，所处的任期 optional uint64 term = 4 ; // logTerm is generally used for appending Raft logs to followers. For example, // (type=MsgApp,index=100,logTerm=5) means leader appends entries starting at // index=101, and the term of entry at index 100 is 5. // (type=MsgAppResp,reject=true,index=100,logTerm=5) means follower rejects some // entries from its leader as it already has an entry with term 5 at index 100. // 该消息携带的第一条Entry记录的的Term值 optional uint64 logTerm = 5 ; // 索引值，该索引值和消息的类型有关,不同的消息类型代表的含义不同 optional uint64 index = 6 ; repeated Entry entries = 7 ; // 已经提交的日志的索引值，用来向别人同步日志的提交信息。 optional uint64 commit = 8 ; // 在传输快照时，该字段保存了快照数据 optional Snapshot snapshot = 9 ; optional bool reject = 10; optional uint64 rejectHint = 11; optional bytes context = 12; } message Entry { optional uint64 Term = 2; // Index:当前这个entry在整个raft日志中的位置索引, // 有了Term和Index之后，一个`log entry`就能被唯一标识。 optional uint64 Index = 3; optional EntryType Type = 1; optional bytes Data = 4; } raftexample 目录提供了一个如何使用 raft library 的例子， 首先从 main.go 来看如何启动一个 raft node。 ...

在实现的时候发现这张状态转换图非常重要。整个 raft 的运行就是围绕着这张图发生一系列状态转换。 因此，第一步实现一个状态机就成了关键。 参考资料 Go 并发、管道

投票的过程 日志的复制 一旦选举成功，所有的 Client 请求最终都会交给 Leader 处理。 当 Client 请求到 Leader后，Leader 首先将该请求转化成 LogEntry，然后添加到自己的 log[] 中，并且把对应的 index 值存到 LogEntry 的 index 中，这样 LogEntry 中就包含了当前 Leader 的 term 信息和在 log[] 中的index信息，这两个信息在发给 Follower 以后会用到。 所以一旦一个节点成为 Leader 以后，那么它的 log[] 保存的这一组 LogEntry 就代表了整个集群中的最终一致的数据。用 raft 论文的话来说就是，节点是一个状态机，LogEntry 是指令集，任何一个节点，只要逐个执行这一串指令，最后状态机的状态都一样。 先看看与日志复制相关的几个数据结构，首先是 raft 结构，其中相关的有以下几个变量： type Raft struct { .... log []LogEntry commitIndex int // 所有机器 lastApplied int nextIndex []int // 只在 leader matchIndex []int ..... } nextIndex 和 matchIndex，这两个数组只有当这个 raft 是 Leader 的时候才有效，否则这两个数组的内容无效。 ...