云原生Etcd系列之Quorum和唱票那回事

　

关于 Quorum 的两个维度

前几回说了那么多框架，设计思想的文章今天分享一个很小的点，etcd 的 quorum 是怎么实现的

Quorum 机制本质就是一个关于多数派的事情，这个多数派应用的有两个方面:

选举过程:获得多数节点投票的节点才能获胜，成为 Leader ， 运行过程:被多数节点 commit 的日志位置，这个才是被集群可靠记录的位置。被集群 commit 的日志才能被应用 apply ，

那么这里有两个小思考问题:

既然是选举过程，那怎么选举结果唱票的。

既然是运行过程，那集群的这些节点怎么确认集群的 commit 位置。

有选举自然有唱票

唱票是在选举流程中的一个步骤还记得以前选班干部的时候，在黑板上写正字，谁得票多谁就获胜当选

etcd 里面也有选举，也就是 Leader 的选举Leader 获胜的依据是的票满足大多数，也就是满足 quorum 机制

今天我们就来看看 etcd 的唱票是怎么做的。

很简单的思路，我们给每个参与选举的朋友计数，得票超过半数的，那么就胜出。

比如说 A，B，C，D，E 五个人竞选，那么得到 3 票的就可以胜出。

来看看 etcd 的唱票

选举属于 quorum 机制，代码位于 etcd/raft/quorum/ 下。quorum 的核心实现在 MajorityConfig 的结构体，其实就是个 map 的封装:

typeMajorityConfigmapstruct

这个 map 的 key 是节点的 id，这里面包含了集群的节点，map 的 value 不重要，所用用的是 struct 类型。

思考个小问题:那既然 value 不 care ，那为什么不用 slice 结构。

其实就是为了查找的需求，map 的查找是常数级别，value 又用的 struct ，不占空间，一举两得。

//etcd/raft/quorum/majority.gofuncVoteResultbool)VoteResult//搞个长度为2的数组ny:=(2)int//遍历集群节点forid:=rangecv，ok:=votes(id)if!ok//暂时没投票的missing++continueifv//投票赞同的ny(1)++else//投票拒绝的ny(0)++q:=len(c)/2+1ifny(1)gt，=q//选举成功:得票数超过半数，，比如votes=gt，(yes，yes，yes)returnVoteWonifny(1)+missinggt，=q//未知情况:不确定成功，也不确定失败returnVotePending//选举失败returnVoteLost

唱票的实现很简单，就如下几个步骤:

遍历集群节点， 统计谁赞同了，谁拒绝了，谁还没投票， 唱票的结果有三种:成功，失败，待定， 赞同投票的超过半数/2+1 )，则胜利，

这实现可太简单了，就是一个遍历投票结果，写正字，正字超过半数则胜出。

集群的节点怎么确认集群的 commit 位置。

集群内被多数节点 commit 的位置才是集群的 commit 点也就是说这个也需要满足 quorum 这个就有意思了

关键步骤:排序，然后取中间的位置。

取的这个中间的位置就是满足 quorum 的 commit 。

//etcd/raft/quorum/majority.gofuncCommittedIndex(lAckedIndexer)Index//遍历集群节点:取出每个节点的commitforid:=rangecifidx，ok:=l.AckedIndex(id)，oksrt(i)=uint64(idx)i——//排个序insertionSort(srt)//取中间，这个位置就是大多数commit的位置，属集群共识pos:=n—(n/2+1)returnIndex(srt(pos))

这个实现就很有意思了，捞出每个节点当前的 commit 位置，组成一个数组，然后给这个数组排个序，取中间的位置这个位置就是集群的 commit 位置，也就是 apply 的位置

先把集群每个节点的 commit 位置取出来，是这样的:

后来排个序是这样的，黑色的节点 commit 位置则是集群的 commit 位置:

总结

Quorum 机制是分布式系统中很重要的理论部分，这是一个关于多数派的机制。etcd 关于多数派有两个方面:Leader 选举和 raft 日志运行，

etcd 的唱票实现非常简单，就是一个计数正字的实现，用一个 map 记录集群的节点，投票计数超过多数则胜出，

etcd 确认集群 commit 位置则是先把每个节点的 commit 位置放在数组，然后排个序，然后取中间位置，这个位置就是集群的 commit 位置，

多数节点 commit 过的日志才是集群 commit 的位置，集群 commit 的日志才能 apply ，这个要记住喽，

集群 commit 位置将由 Leader 通过心跳或者日志复制的消息告诉其他节点，

。