分布式系统选主怎么玩

孙玄：毕业于浙江大学，现任转转公司首席架构师，技术委员会主席，大中后台技术负责人（交易平台、基础服务、智能客服、基础架构、智能运维、数据库、安全、IT 等方向）；前58集团技术委员会主席，高级系统架构师；前百度资深研发工程师；

【架构之美】微信公众号作者；擅长系统架构设计，大数据，运维、机器学习等技术领域；代表公司多次在业界顶级技术大会 CIO 峰会、Artificial、Intelligence、Conference、A2M、QCon、ArchSummit、SACC、SDCC、CCTC、DTCC、Top100、Strata+、Hadoop World、WOT、GITC、GIAC、TID等发表演讲，并为《程序员》杂志撰稿 2 篇。

分布式系统为了保证其可靠性，一般都会多节点提供服务，各别节点的故障不会影响系统的可用性。对于分布式的存储系统来说，在保证可用性的同时，数据的可靠性（不丢失）也是其要解决的核心问题。目前通用的方案是使用多副本存储。这就会引入一个新的问题，分布式存储系统的又一核心问题——多个副本间的数据一致性保障。所以就有了各种数据一致性协议。例如：Zookeeper 的 Zab、Etcd 使用的 Raft 和无比复杂的 Paxos 等等。这些一致性协议都有一个共同的特点，那就是都有一个主节点（Leader）负责数据的同步。

本文不讨论这些一致性协议的工作原理，我们重点聊一聊它们的选主策略——当Leader 挂掉后，集群必须有能力选出一个新的 Leader。为什么只讨论选主呢？因为在我们的工作中几乎不太可能去设计实现一致性协议，但"选主"这个事儿还是有可能需要我们去做的。例如之前文章介绍的时间轮，我们有多个节点提供服务，但只能有一个节点去转动轮子（一秒移动一次当前指针），这个时候就需要系统中始终有一个 Leader 负责转动轮子。业务上类似的需求还有很多，这里就不举例了，接下来我们介绍下几种选主策略。

首先明确下选主的时机：一般发生在集群的 Leader 宕机或者集群刚刚启动时，集群中没有 Leader，这时就会触发选主。这里有两个技术点：

1、集群中节点需要能够感知到 Leader 的存在；

2、从剩余的活跃节点中选出一个新的 Leader；

选主常用的方式有两种：投票和竞争，下面我们分别介绍下。

1. 投票选主

在投票选主方式中，一般集群中会有两种角色：Leader 和 Follower，Leader 和各Follower 间保持心跳，Follower 通过心跳判断 Leader 是否存活，如果 Follower 感知不到 Leader，则触发选举。获得集群半数以上节点投票的 Follower 将成为集群新的 Leader。为了提高选举的效率，集群节点数一般都为奇数个。

那么 Leader 是如何选出来的呢？不同的一致性协议，有不同的玩法，下面简单了解下 Zookeeper 和 Etcd 的选主方式（为了便于理解对模型做了简化，只描述核心算法和思路）：

1.1 ZooKeeper

ZK 的节点在投票时是通过比较两个“ID”来决定把票投给谁的：

1、ZXID：ZooKeeper 事务 Id，越大表示数据越新；

2、SID：集群中每个节点的唯一编号；

投票时的比较算法为：谁的 ZXID 大谁胜出，ZXID 相同情况谁的 SID 大谁胜出（简单理解：谁的数据先胜出，数据一样谁的编号大谁胜出）。

选举算法如下：

1、集群失去 Leader 后，所有节点进入 Looking 状态，向集群中广播（第一轮投票）自身选举值（SID，ZXID），投自己一票；

2、每个节点都会将自身选举值与收到的所有其它节点的选举值作比较，选出“最大”的，如果最大的不是自己，则改投最"大“节点，广播变更(第二轮投票)；

3、集群中节点收到第二轮结果后，统计超过半数的选举值，其对应的节点将成为集群新的 Leader；选举过程如下图所示：

图1 ZooKeeper选主过程

1.2 Etcd

Etcd 使用 Raft 一致性协议，集群中每个节点都有自己的倒计时器，且时间随机。Follower 每次收到心跳后都会重置倒计时器，当某个 Follower 的倒计时结束，说明长时间没有收到心跳，就可以认为 Leader 挂了，需要选举新的 Leader 了。这个 Follower 就会触发选举，想成集群为新的 Leader。

Follower 首先会将自身状态改为 Candidate，并向所有节点发起投票，如果得到半数以上节点的同意则成为集群新的 Leader。否则，在下次倒计时结束后发起新一轮选举。

Raft 选举过程中，投票节点通过对比任期（Term，一个连续递增的整型值）和CommitId（类似 ZK 的事务 Id）来判断是否投“同意”票。选举过程如下：

1、Candidate 发起投票时将自身当前任期加 1 (NewTerm)，并向集群中所有节点发起投票请求（请求中包含新的任期值）；

2、Follower 节点将自身当前任期（CurrentTerm）和收到的 Candidate 投票请求中带来的 NewTerm 比较，如果 NewTerm 大就投“同意”票（这里忽略的 CommitId的比较是为了更好理解和强调 Term 的作用，比较方法与 ZK 类似）；

3、Candidate 得到大于半数节点的”同意“后成为 Leader，与其他节点建立心跳，并更新所有节点的当前任期为 NewTerm;

4、如果不够半数，则选举失败，等待倒计时器下次到期发起下一轮选举;

选举过程如图2、图3所示：

图2 Leader心跳中断，进入下一任期

集群正常情况下，各节点处于同一任期，Leader 节点定时发送心跳重置各Follower 倒计时器，当 Leader 心跳中断后，Follower 倒计时器不再被重置，则会必然会有节点到期，触发选举，图2中 Follower 1先到期，变为 Candidate 并发起选举，进入下一任期。

图3 完成选举

选举成功，原 Follower 成为集群新的主节点，开始向各 Follower 发送心跳，并更新其它节点的任期。

上面介绍的流程只是最简单的场景，实际情况会复杂些，例如有可能会有产生多个 Candidate，因为只要有 Follower 节点到期，就会发起投票，进入 Candidate 状态，Reft 是如何尽量避免产生多个 Candidate 的呢？

首先各节点倒计时时间随机，尽量避免同时到期。其次 Follower 收到 Candidate 的投票请求时会重置自己的倒计时器，这样就尽量保证了在选举失败后 Candidate 能够率先到期，可以下一任期继续由它发起投票。

但是肯定还存在产生多个 Candidate 的情况，所以协议规定一个 Follower 在一个任期只能投一次票，这样就够不可能有两个 Candidate 同时获得半数以上的投票（不可能选出两个 Leader 来）。如果选举失败，由于节点倒计时器时间随机，所以几乎可以肯定会有一个 Candidate 先到期，并且大概率在下一轮选举中成为 Leader。

2、竞争选主

上面介绍的投票选举方式需要集群各节点互相感知对方的存在，实现相对复杂，下面介绍一种比较简单的方案——竞争选主。

竞争选主需要借助外部存储服务来实现，各节点通过对某个约定的 Key-Value 数据的访问，来决定谁是 Leader，假设 KV 数据为 Leader：UUID（写入前生成的唯一 Id），具体”抢主“逻辑如下：

1、尝试获取 Leader：UUID 数据，判断数据是否存在；

2、如果 Leader 不存在，则将 Leader:UUID 写入到存储服务中并设置其 TTL（如果存储服务不支持 TTL，可以将 TTL 作为Value的一部分一起写入），本地保存UUID 值，当前进程为主节点；

3、如果 Leader 存在，通过 TTL 判断是否过期，如果过期，当做 Leader 不存在处理，否则对比 Leader 的 UUID 和本地存储的 UUID 是否一致；

3.1、如果一致则刷新”数据“ TTL，当前进程为 Leader；

3.2、如果不一致则不作任何操作，当前节点不是 Leader；

集群内所有的进程，都保证以小于 TTL 的周期执行上述逻辑，Leader 就会不停的“刷新” Leader:UUID 的 TTL，始终保持自己是 Leader，如果想更安全，刷新时可以使用 CAS 的方式每次更新 UUID。当 Leader 宕机不能继续刷新后，数据必然会过期，其它节点将会竞争写入，成为集群新的 Leader（和分布式锁很像，可以理解为一把长期持有的锁，新的玩法）。

图4 竞争Leader

我们分析下上述逻辑，当约定的 Key 不存在时，集群处于没有主或主挂了的状态，其他节点可以通过判断这个 Key 感知到 Leader 是否存在，从而触发选主，写入 Key 的过程相当于竞争选主的过程，谁写入成功谁就是新的 Leader。

3、总结

本文介绍了两种选主方式，竞争的方式很好理解，实现也非常简单，但为什么存储系统很少选择竞争选主方案？如果我们的业务模块要实现选举使用那种方案好一些？