featured.png

Distributed Consensus Protocol

Table of Contents

看我看我，我宣布一件事：俺是你们的 Leader！

参考：

算法高级（5）-分布式系统选举算法及脑裂

算法高级（6）-共识（Raft）算法

分布式技术原理（三）：分布式选举

Distributed Consensus Algorithms for extreme reliability by Laura Nolan (Google)

分布式共识/选举算法

The distributed consensus problem deals with reaching agreement among a group of processes connected by an unreliable communications network.

解决了这个集群中现在的领头羊寄了之后到底是哪个（幸运的）比说了算这个问题。

没有人破坏时

Bully

MongoDB

原则

从所有节点中选举出 ID 最大的为主节点。

即：优先级。

当：

  • 主节点故障
  • 某节点正在从故障中恢复

时，触发选举。

消息类型

  • Election 消息：用于发起选举。

  • Alive(Answer) 消息：ID 更高的节点对从低节点发来的 Election 消息的应答。

  • Victory(Coordinator) 消息：竞选成功的主节点向其它节点发送的宣誓主权的消息。

过程

  1. 当选举开始的时候：每个节点根据已有的节点信息表判断自己是不是最大的节点。

    如果自己是最大的节点则向其他所有节点发送 Victory 消息，告诉大家谁才是这里的主人。

    如果自己 ID 不是最大的，则向其他所有节点发送 Election 消息，并等待其他节点的回复。

  2. 若在给定时间范围内，本节点没有收到其它节点的 Alive 回复消息，则认为自己是主节点，并向其他节点发送 Victory 消息；若接收到比自己 ID 大的 Alive 消息，则知道自己已经输了，等待其他节点发送 Victory 消息。

  3. 若本节点收到比自己小的节点发送的 Election 消息，则回复一个 Alive 消息，告知我比你大，你给我滚。

优点

  • 简单霸道，谁活着并且谁的ID最大，谁就是主节点，其他节点必须无条件服从。

  • 算法复杂度低，简单易实现。

缺点

  • 每个节点都要存储全局节点的信息，额外信息存储较多。

  • 任意一个比当前主节点大的节点加入或者主节点故障都会触发重新选举，会导致频繁切换主节点。

Raft

Redis Cluster, Elasticsearch, etcds

原则

少数服从多数，获得投票数最多的成为主节点。

即：少数服从多数。

节点角色

  • Leader：主节点。同一时间只有一个 Leader，负责协调和管理其它节点

  • Candidate：候选者，每一个节点在选举开始时都可以成为 Candidate，在该角色下才可以成为 Leader。

  • Follower：Leader 的追随者，不可以发起选举。

过程

  1. 系统初始化时所有节点角色被初始化为 Follower。

  2. 开始选举时节点角色变为 Candidate，每个节点都发送选举请求。其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主。在每一轮选举中，一个节点只能投出一张票。

  3. 选举结束，发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为 Leader，其他节点的状态则由 Candidate 降为 Follower。Leader 节点和 Follower 节点会定期发送心跳检测主节点是否还活着。

  4. 当 Leader 节点的任期到了，发现其它服务器开始新一轮选举时，自动将角色降为 Follower，进入新一轮选举。

优点

  • 选举速度快。

  • 算法复杂度低，易于实现

缺点

要求系统内每个节点都要相互通信，且需要获得过半的投票数才能选主成功，通信量大。

ZAB

是一种特别为 ZooKeeper 设计的崩溃可恢复的原子消息广播算法。ZAB（ZooKeeper Atomic Broadcast）选举算法是为 ZooKeeper 实现分布式协调功能而设计的。相较于 Raft 算法的投票机制，ZAB 算法增加了通过节点 ID 和数据 ID 作为参考进行选主，节点 ID 和数据 ID 越大，表示数据越新，优先成为主。相比较于 Raft 算法，ZAB 算法尽可能保证数据的最新性。所以，ZAB 算法可以说是对 Raft 算法的改进。

原则

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

即：少数服从多数且有优先级。

节点角色

  • Looking：选举状态。当节点处于该状态时，它认为当前集群中没有 Leader，因此自己进入选举状态。

  • Leading：领导者状态，表示已经选出主，且当前节点为 Leader。

  • Following：跟随者状态，集群中已经选出主后，其他非主节点状态更新为 Following，表示对 Leader 的追随。

  • Observing：观察者状态，表示当前节点为 Observer，持观望态度，没有投票权和选举权。

过程

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

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

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

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

Paxos

“鉴于 Paxos 算法的难于理解，Raft算法的两位研究者也提到，他们花了很长的时间来理解 Paxos，也觉得很难理解，于是研究出了 Raft 算法。”

那我先摸了应该不会有人说我吧

有坏东西搞破坏时

拜占庭 摸了

Nemo Xiong avatar
Nemo Xiong
ex-Cybersecurity Executor, now a student in Unimelb

Related

comments powered by Disqus