0%

分布式技术原理与算法解析 笔记

分布式技术原理与算法解析
作者: 聂鹏程

04 | 分布式选举:国不可一日无君

长者为大:Bully 算法

Bully 算法是一种霸道的集群选主算法,为什么说是霸道呢?因为它的选举原则是“长者”为大,即在所有活着的节点中,选取 ID 最大的节点作为主节点。

在 Bully 算法中,节点的角色有两种:普通节点和主节点。初始化时,所有节点都是平等的,都是普通节点,并且都有成为主的权利。但是,当选主成功后,有且仅有一个节点成为主节点,其他所有节点都是普通节点。当且仅当主节点故障或与其他节点失去联系后,才会重新选主。

Bully 算法在选举过程中,需要用到以下 3 种消息:

  • Election 消息,用于发起选举;
  • Alive 消息,对 Election 消息的应答;
  • Victory 消息,竞选成功的主节点向其他节点发送的宣誓主权的消息。

Bully 算法选举的原则是“长者为大”,意味着它的假设条件是,集群中每个节点均知道其他节点的 ID。在此前提下,其具体的选举过程是:

  1. 集群中每个节点判断自己的 ID 是否为当前活着的节点中 ID 最大的,如果是,则直接向其他节点发送 Victory 消息,宣誓自己的主权;
  2. 如果自己不是当前活着的节点中 ID 最大的,则向比自己 ID 大的所有节点发送Election 消息,并等待其他节点的回复;
  3. 若在给定的时间范围内,本节点没有收到其他节点回复的 Alive 消息,则认为自己成为主节点,并向其他节点发送 Victory 消息,宣誓自己成为主节点;若接收到来自比自己ID 大的节点的 Alive 消息,则等待其他节点发送 Victory 消息;
  4. 若本节点收到比自己 ID 小的节点发送的 Election 消息,则回复一个 Alive 消息,告知其他节点,我比你大,重新选举。

目前已经有很多开源软件采用了 Bully 算法进行选主,比如 MongoDB 的副本集故障转移功能。MongoDB 的分布式选举中,采用节点的最后操作时间戳来表示 ID,时间戳最新的
节点其 ID 最大,也就是说时间戳最新的、活着的节点是主节点。

小结一下。Bully 算法的选择特别霸道和简单,谁活着且谁的 ID 最大谁就是主节点,其他节点必须无条件服从。这种算法的优点是,选举速度快、算法复杂度低、简单易实现。

但这种算法的缺点在于,需要每个节点有全局的节点信息,因此额外信息存储较多;其次,任意一个比当前主节点 ID 大的新节点或节点故障后恢复加入集群的时候,都可能会触发重新选举,成为新的主节点,如果该节点频繁退出、加入集群,就会导致频繁切主。

民主投票:Raft 算法

采用 Raft 算法选举,集群节点的角色有 3 种:

  • Leader,即主节点,同一时刻只有一个 Leader,负责协调和管理其他节点;
  • Candidate,即候选者,每一个节点都可以成为 Candidate,节点在该角色下才可以被选为新的 Leader;
  • Follower,Leader 的跟随者,不可以发起选举。

Raft 选举的流程,可以分为以下几步:

  1. 初始化时,所有节点均为 Follower 状态。
  2. 开始选主时,所有节点的状态由 Follower 转化为 Candidate,并向其他节点发送选举请求。
  3. 其他节点根据接收到的选举请求的先后顺序,回复是否同意成为主。这里需要注意的是,在每一轮选举中,一个节点只能投出一张票。
  4. 若发起选举请求的节点获得超过一半的投票,则成为主节点,其状态转化为 Leader,其他节点的状态则由 Candidate 降为 Follower。Leader 节点与 Follower 节点之间会定期发送心跳包,以检测主节点是否活着。
  5. 当 Leader 节点的任期到了,即发现其他服务器开始下一轮选主周期时,Leader 节点的状态由 Leader 降级为 Follower,进入新一轮选主。

节点的状态迁移如下所示(图中的 term 指的是选举周期):

请注意,每一轮选举,每个节点只能投一次票。这种选举就类似人大代表选举,正常情况下每个人大代表都有一定的任期,任期到后会触发重新选举,且投票者只能将自己手里唯一的票投给其中一个候选者。对应到 Raft 算法中,选主是周期进行的,包括选主和任值两个时间段,选主阶段对应投票阶段,任值阶段对应节点成为主之后的任期。但也有例外的时候,如果主节点故障,会立马发起选举,重新选出一个主节点。

小结一下。Raft 算法具有选举速度快、算法复杂度低、易于实现的优点;缺点是,它要求系统内每个节点都可以相互通信,且需要获得过半的投票数才能选主成功,因此通信量大。该算法选举稳定性比 Bully 算法好,这是因为当有新节点加入或节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或故障后恢复的节点获得投票数过半,才会导致切主。

具有优先级的民主投票:ZAB 算法

ZAB(ZooKeeper Atomic Broadcast)选举算法是为 ZooKeeper 实现分布式协调功能而设计的。相较于 Raft 算法的投票机制,ZAB 算法增加了通过节点 ID 和数据 ID 作为参考进行选主,节点 ID 和数据 ID 越大,表示数据越新,优先成为主。相比较于 Raft 算法,ZAB 算法尽可能保证数据的最新性。所以,ZAB 算法可以说是对 Raft 算法的改进。

使用 ZAB 算法选举时,集群中每个节点拥有 3 种角色:

  • Leader,主节点;
  • Follower,跟随者节点;
  • Observer,观察者,无投票权。

选举过程中,集群中的节点拥有 4 个状态:

  • Looking 状态,即选举状态。当节点处于该状态时,它会认为当前集群中没有 Leader,因此自己进入选举状态。
  • Leading 状态,即领导者状态,表示已经选出主,且当前节点为 Leader。
  • Following 状态,即跟随者状态,集群中已经选出主后,其他非主节点状态更新为Following,表示对 Leader 的追随。
  • Observing 状态,即观察者状态,表示当前节点为 Observer,持观望态度,没有投票权和选举权。

投票过程中,每个节点都有一个唯一的三元组 (server_id, server_zxID, epoch),其中server_id 表示本节点的唯一 ID;server_zxID 表示本节点存放的数据 ID,数据 ID 越大表
示数据越新,选举权重越大;epoch 表示当前选取轮数,一般用逻辑时钟表示。

ZAB 选举算法的核心是“少数服从多数,ID 大的节点优先成为主”,因此选举过程中通过(vote_id, vote_zxID) 来表明投票给哪个节点,其中 vote_id 表示被投票节点的 ID,vote_zxID 表示被投票节点的服务器 zxID。ZAB 算法选主的原则是:server_zxID 最大者成为 Leader;若 server_zxID 相同,则 server_id 最大者成为 Leader。

接下来,我以 3 个 Server 的集群为例,此处每个 Server 代表一个节点,与你介绍 ZAB 选主的过程。

第一步:当系统刚启动时,3 个服务器当前投票均为第一轮投票,即 epoch=1,且 zxID 均为 0。此时每个服务器都推选自己,并将选票信息 <epoch, vote_id, vote_zxID> 广播出去。

第二步:根据判断规则,由于 3 个 Server 的 epoch、zxID 都相同,因此比较 server_id,较大者即为推选对象,因此 Server 1 和 Server 2 将 vote_id 改为 3,更新自己的投票箱并重新广播自己的投票。

第三步:此时系统内所有服务器都推选了 Server 3,因此 Server 3 当选 Leader,处于Leading 状态,向其他服务器发送心跳包并维护连接;Server1 和 Server2 处于 Following 状态。

小结一下。ZAB 算法性能高,对系统无特殊要求,采用广播方式发送信息,若节点中有 n 个节点,每个节点同时广播,则集群中信息量为 n*(n-1) 个消息,容易出现广播风暴;且除了投票,还增加了对比节点 ID 和数据 ID,这就意味着还需要知道所有节点的 ID 和数据ID,所以选举时间相对较长。但该算法选举稳定性比较好,当有新节点加入或节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或故障后恢复的节点数据 ID 和节点ID 最大,且获得投票数过半,才会导致切主。

三种选举算法的对比分析

05 | 分布式共识:存异求同

分布式共识就是在多个节点均可独自操作或记录的情况下,使得所有节点针对某个状态达成一致的过程。

分布式共识:存异求同

06 | 分布式事务:All or nothing

07 | 分布式锁:关键重地,非请勿入

特别放送

那些你不能错过的分布式系统论文

欢迎关注我的其它发布渠道