新版etcd中，raft包就是对Raft一致性算法的具体实现。关于Raft算法的讲解，网上已经有很多文章，有兴趣的读者可以去阅读一下Raft算法论文非常精彩。本文则不再对Raft算法进行详细描述，而是结合etcd，针对算法中一些关键内容以问答的形式进行讲解。有关Raft算法的术语如果不理解，可以参见概念词汇表一节。
7.1 Raft常见问答一览Raft中一个Term（任期）是什么意思？ Raft算法中，从时间上，一个任期讲即从一次竞选开始到下一次竞选开始。从功能上讲，如果Follower接收不到Leader节点的心跳信息，就会结 束当前任期，变为Candidate发起竞选，有助于Leader节点故障时集群的恢复。发起竞选投票时，任期值小的节点不会竞选成功。如果集群不出现故 障，那么一个任期将无限延续下去。而投票出现冲突也有可能直接进入下一任再次竞选。
图12 Term示意图
Raft状态机是怎样切换的？ Raft刚开始运行时，节点默认进入Follower状态，等待Leader发来心跳信息。若等待超时，则状态由Follower切换到 Candidate进入下一轮term发起竞选，等到收到集群多数节点的投票时，该节点转变为Leader。Leader节点有可能出现网络等故障，导致 别的节点发起投票成为新term的Leader，此时原先的老Leader节点会切换为Follower。Candidate在等待其它节点投票的过程中 如果发现别的节点已经竞选成功成为Leader了，也会切换为Follower节点。
图13 Raft状态机
如何保证最短时间内竞选出Leader，防止竞选冲突？ 在Raft状态机一图中可以看到，在Candidate状态下， 有一个times out，这里的times out时间是个随机值，也就是说，每个机器成为Candidate以后，超时发起新一轮竞选的时间是各不相同的，这就会出现一个时间差。在时间差内，如果 Candidate1收到的竞选信息比自己发起的竞选信息term值大（即对方为新一轮term），并且新一轮想要成为Leader的 Candidate2包含了所有提交的数据，那么Candidate1就会投票给Candidate2。这样就保证了只有很小的概率会出现竞选冲突。
如何防止别的Candidate在遗漏部分数据的情况下发起投票成为Leader？ Raft竞选的机制中，使用随机值决定超时时间，第一个超时的节点就会提升term编号发起新一轮投票，一般情况下别的节点收到竞选通知就会投票。但是， 如果发起竞选的节点在上一个term中保存的已提交数据不完整，节点就会拒绝投票给它。通过这种机制就可以防止遗漏数据的节点成为Leader。
Raft某个节点宕机后会如何？ 通常情况下，如果是Follower节点宕机，如果剩余可用节点数量超过半数，集群可以几乎没有影响的正常工作。如果是Leader节点宕机，那么Follower就收不到心跳而超时，发起竞选获得投票，成为新一轮term的Leader，继续为集群提供服务。需要注意的是；etcd目前没有任何机制会自动去变化整个集群总共的节点数量，即如果没有人为的调用API，etcd宕机后的节点仍然被计算为总节点数中，任何请求被确认需要获得的投票数都是这个总数的半数以上。
图14 节点宕机
为什么Raft算法在确定可用节点数量时不需要考虑拜占庭将军问题？ 拜占庭问题中提出，允许n个节点宕机还能提供正常服务的分布式架构，需要的总节点数量为3n+1，而Raft只需要2n+1就可以了。其主要原因在于，拜 占庭将军问题中存在数据欺骗的现象，而etcd中假设所有的节点都是诚实的。etcd在竞选前需要告诉别的节点自身的term编号以及前一轮term最终 结束时的index值，这些数据都是准确的，其他节点可以根据这些值决定是否投票。另外，etcd严格限制Leader到Follower这样的数据流向 保证数据一致不会出错。
用户从集群中哪个节点读写数据？ Raft为了保证数据的强一致性，所有的数据流向都是一个方向，从Leader流向Follower，也就是所有Follower的数据必须与 Leader保持一致，如果不一致会被覆盖。即所有用户更新数据的请求都最先由Leader获得，然后存下来通知其他节点也存下来，等到大多数节点反馈时 再把数据提交。一个已提交的数据项才是Raft真正稳定存储下来的数据项，不再被修改，最后再把提交的数据同步给其他Follower。因为每个节点都有 Raft已提交数据准确的备份（最坏的情况也只是已提交数据还未完全同步），所以读的请求任意一个节点都可以处理。
etcd实现的Raft算法性能如何？ 单实例节点支持每秒1000次数据写入。节点越多，由于数据同步涉及到网络延迟，会根据实际情况越来越慢，而读性能会随之变强，因为每个节点都能处理用户请求。
7.2 关键部分源码解析在etcd代码中，Node作为Raft状态机的具体实现，是整个算法的关键，也是了解算法的入口。
在etcd中，对Raft算法的调用如下，你可以在etcdserver/raft.go中的startNode找到：
storage := raft.NewMemoryStorage() n := raft.StartNode(0x01, []int64{0x02, 0x03}, 3, 1, storage)通过这段代码可以了解到，Raft在运行过程记录数据和状态都是保存在内存中，而代码中raft.StartNode启动的Node就是Raft状态机Node。启动了一个Node节点后，Raft会做如下事项。
首先，你需要把从集群的其他机器上收到的信息推送到Node节点，你可以在etcdserver/server.go中的Process函数看到。
func (s *EtcdServer) Process(ctx context.Context, m raftpb.Message) error { if m.Type == raftpb.MsgApp { s.stats.RecvAppendReq(types.ID(m.From).String(), m.Size()) } return s.node.Step(ctx, m) }在检测发来请求的机器是否是集群中的节点，自身节点是否是Follower，把发来请求的机器作为Leader，具体对Node节点信息的推送和处理则通过node.Step()函数实现。
其次，你需要把日志项存储起来，在你的应用中执行提交的日志项，然后把完成信号发送给集群中的其它节点，再通过node.Ready()监听等待下一次任务执行。有一点非常重要，你必须确保在你发送完成消息给其他节点之前，你的日志项内容已经确切稳定的存储下来了。
最后，你需要保持一个心跳信号Tick()。Raft有两个很重要的地方用到超时机制：心跳保持和Leader竞选。需要用户在其raft的Node节点上周期性的调用Tick()函数，以便为超时机制服务。
综上所述，整个raft节点的状态机循环类似如下所示：
for { select { case <-s.Ticker: n.Tick() case rd := <-s.Node.Ready(): saveToStorage(rd.State, rd.Entries) send(rd.Messages) process(rd.CommittedEntries) s.Node.Advance() case <-s.done: return } }而这个状态机真实存在的代码位置为etcdserver/server.go中的run函数。
对状态机进行状态变更（如用户数据更新等）则是调用n.Propose(ctx, data)函数，在存储数据时，会先进行序列化操作。获得大多数其他节点的确认后，数据会被提交，存为已提交状态。
之前提到etcd集群的启动需要借助别的etcd集群或者DNS，而启动完毕后这些外力就不需要了，etcd会把自身集群的信息作为状态存储起来。所以要变更自身集群节点数量实际上也需要像用户数据变更那样添加数据条目到Raft状态机中。这一切由n.ProposeConfChange(ctx, cc)实现。当集群配置信息变更的请求同样得到大多数节点的确认反馈后，再进行配置变更的正式操作，代码如下。
var cc raftpb.ConfChange cc.Unmarshal(data) n.ApplyConfChange(cc)注意：一个ID唯一性的表示了一个集群，所以为了避免不同etcd集群消息混乱，ID需要确保唯一性，不能重复使用旧的token数据作为ID。
8 StoreStore这个模块顾名思义，就像一个商店把etcd已经准备好的各项底层支持加工起来，为用户提供五花八门的API支持，处理用户的各项请求。要理解Store，只需要从etcd的API入手即可。打开etcd的API列表，我们可以看到有如下API是对etcd存储的键值进行的操作，亦即Store提供的内容。API中提到的目录（Directory）和键（Key），上文中也可能称为etcd节点（Node）。
为etcd存储的键赋值 curl :2379/v2/keys/message -XPUT -d value="Hello world" { "action": "set", "node": { "createdIndex": 2, "key": "/message", "modifiedIndex": 2, "value": "Hello world" } }
反馈的内容含义如下：
action: 刚刚进行的动作名称。
node.key: 请求的HTTP路径。etcd使用一个类似文件系统的方式来反映键值存储的内容。
node.value: 刚刚请求的键所存储的内容。
node.createdIndex: etcd节点每次有变化时都会自增的一个值，除了用户请求外，etcd内部运行（如启动、集群信息变化等）也会对节点有变动而引起这个值的变化。
node.modifiedIndex: 类似node.createdIndex，能引起modifiedIndex变化的操作包括set, delete, update, create, compareAndSwap and compareAndDelete。
查询etcd某个键存储的值 curl :2379/v2/keys/message
修改键值：与创建新值几乎相同，但是反馈时会有一个prevNode值反应了修改前存储的内容。 curl :2379/v2/keys/message -XPUT -d value="Hello etcd"
删除一个值 curl :2379/v2/keys/message -XDELETE
对一个键进行定时删除：etcd中对键进行定时删除，设定一个TTL值，当这个值到期时键就会被删除。反馈的内容会给出expiration项告知超时时间，ttl项告知设定的时长。 curl :2379/v2/keys/foo -XPUT -d value=bar -d ttl=5
取消定时删除任务 curl :2379/v2/keys/foo -XPUT -d value=bar -d ttl= -d prevExist=true
对键值修改进行监控：etcd提供的这个API让用户可以监控一个值或者递归式的监控一个目录及其子目录的值，当目录或值发生变化时，etcd会主动通知。 curl :2379/v2/keys/foo?wait=true
对过去的键值操作进行查询：类似上面提到的监控，只不过监控时加上了过去某次修改的索引编号，就可以查询历史操作。默认可查询的历史记录为1000条。 curl 'http://127.0.0.1:2379/v2/keys/foo?wait=true&waitIndex=7'
自动在目录下创建有序键。在对创建的目录使用POST参数，会自动在该目录下创建一个以createdIndex值为键的值，这样就相当于以创建时间先后严格排序了。这个API对分布式队列这类场景非常有用。 curl :2379/v2/keys/queue -XPOST -d value=Job1 { "action": "create", "node": { "createdIndex": 6, "key": "/queue/6", "modifiedIndex": 6, "value": "Job1" } }
按顺序列出所有创建的有序键。 curl -s 'http://127.0.0.1:2379/v2/keys/queue?recursive=true&sorted=true'
创建定时删除的目录：就跟定时删除某个键类似。如果目录因为超时被删除了，其下的所有内容也自动超时删除。 curl :2379/v2/keys/dir -XPUT -d ttl=30 -d dir=true
刷新超时时间。
curl :2379/v2/keys/dir -XPUT -d ttl=30 -d dir=true -d prevExist=true自动化CAS（Compare-and-Swap）操作：etcd强一致性最直观的表现就是这个API，通过设定条件，阻止节点二次创建或修改。即用户的指令被执行当且仅当CAS的条件成立。条件有以下几个。
prevValue 先前节点的值，如果值与提供的值相同才允许操作。
prevIndex 先前节点的编号，编号与提供的校验编号相同才允许操作。
prevExist 先前节点是否存在。如果存在则不允许操作。这个常常被用于分布式锁的唯一获取。
假设先进行了如下操作：设定了foo的值。
curl :2379/v2/keys/foo -XPUT -d value=one然后再进行操作：
curl :2379/v2/keys/foo?prevExist=false -XPUT -d value=three就会返回创建失败的错误。
条件删除（Compare-and-Delete）：与CAS类似，条件成立后才能删除。
创建目录 curl :2379/v2/keys/dir -XPUT -d dir=true
列出目录下所有的节点信息，最后以/结尾。还可以通过recursive参数递归列出所有子目录信息。 curl :2379/v2/keys/
删除目录：默认情况下只允许删除空目录，如果要删除有内容的目录需要加上recursive=true参数。 curl 'http://127.0.0.1:2379/v2/keys/foo_dir?dir=true' -XDELETE
创建一个隐藏节点：命名时名字以下划线_开头默认就是隐藏键。 curl :2379/v2/keys/_message -XPUT -d value="Hello hidden world"
相信看完这么多API，读者已经对Store的工作内容基本了解了。它对etcd下存储的数据进行加工，创建出如文件系统般的树状结构供用户快速查询。它有一个Watcher用于节点变更的实时反馈，还需要维护一个WatcherHub对所有Watcher订阅者进行通知的推送。同时，它还维护了一个由定时键构成的小顶堆，快速返回下一个要超时的键。最后，所有这些API的请求都以事件的形式存储在事件队列中等待处理。
9 总结通过从应用场景到源码分析的一系列回顾，我们了解到etcd并不是一个简单的分布式键值存储系统。它解决了分布式场景中最为常见的一致性问题，为服 务发现提供了一个稳定高可用的消息注册仓库，为以微服务协同工作的架构提供了无限的可能。相信在不久的将来，通过etcd构建起来的大型系统会越来越多。
10 作者简介孙健波，浙江大学SEL实验室硕士研究生，目前在云平台团队从事科研和开发工作。浙大团队对PaaS、Docker、大数据和主流开源云计算技术有深入的研究和二次开发经验，团队现将部分技术文章贡献出来，希望能对读者有所帮助。
参考文献