分布式技术原理与算法解析之分布式协同 学习笔记 （2）

• 2021 年 1 月 23 日
• AI
• 深度学习

• 背景：

集群（大于等于2个服务器组建），将服务器视为节点，对于一个集群，节点之间怎么协同呢？（如数据库集群提供读写功能、管理集群提供管理/故障恢复功能）

协同是根据不同的任务所表达的含义也不尽相同，要搞好协同，需要选一个主节点，负责对其他节点的协调和管理，保证集群有序运行和节点间数据的一致性（一致性：数据在每个集群节点中是一样的，不存在不同的情况。）

• 我们需要考虑的方面：（1）通信量（2）稳定性（3）

• 几种常见的选举算法：

  • Bully算法
    • 特点：在所有活着的节点中，选取ID最大的节点为主节点。
    • 选举时间点：
      • 某个新节点加入了集群或者某个节点从宕机中恢复
      • 集群中的某个节点检测到leader崩溃
    • 总体流程:
    • 节点node向所有比自己大的节点发送选举消息(选举为Election消息)
    • 如果节点node得不到任何回复(回复为Alive消息)，那么节点node成为主节点master，并向所有的其它节点宣布自己是master(宣布为Victory消息)
    • 如果node得到了任何回复，node节点就一定不是master，同时等待Victory消息，如果等待Victory超时那么重新发起选举。
      
    • 优点：选举速度快，算法复杂度低，简单易实现。
    • 缺点：（1）每个节点都有全局节点的信息——>额外信息存储较多
      （2）容易频繁切主，不适合大规模系统。
    • 典型应用场景：MongoDB的副本集故障转移功能

• Raft算法选举

  • 特点：投票制度选举，得票最多的节点成为主。

  • 选举时间点：

    • 集群启动初始化时
    • 集群的Master崩溃的时,长时间没有收到Leader消息。
    • 任一节点发现集群中的Master没有得到（n/2+1）节点认可时则触发选举

  • 总体流程：

  • 初始化时，所有节点均为 Follower 状态。

  • 开始选主时，所有节点的状态由 Follower 转化为 Candidate，并向其他节点发送选举请求。

  • 其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主，在每一轮选举中，一个节点只能投出一张票。

  • 若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为 Leader，其他节点的状态则由 Candidate 降为 Follower。Leader 节点与 Follower 节点之间会定期发送心跳包，以检测主节点是否活着。

  • 当 Leader 节点的任期到了，即发现其他服务器开始下一轮选主周期时，Leader 节点的状态由 Leader 降级为 Follower，进入新一轮选主。

  • 优点：（1）选举速度快，算法复杂度低，易实现。（2）稳定性好，新节点不一定导致切主。

  • 缺点：算法要求每个节点都相互通信，通信量较大。
    
    

  • 典型应用场景：Google开源的Kubernetes(需要进一步了解)

• ZAB算法（Zookeeper Atomic Broadcast（Zookeeper 原子广播协议，一致性协议）

  • 特点:增加了通过节点ID和数据ID作为参考进行选主，节点ID和数据ID越大，表示数据越新，优先成为主，相较于Raft，ZAB算法尽可能保证数据的最新性。ZAB算法选主原则：server_zxID 最大者成为 Leader；若 server_zxID 相同，则 server_id 最大者成为 Leader。

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

  • 选举时间点：同Raft一样。

  • 总体流程：少数服从多数，ID大的节点优先成为主。每一轮将选票信息 <epoch, vote_id, vote_zxID> 广播出去。
    

  • 优点：（1）稳定性较好 （2）系统性能好

  • 缺点：(1) 集群中信息量为 n*(n-1) 个消息，容易出现广播风暴。 (2)除了投票，还增加了对比节点 ID 和数据 ID，所以选举时间相对较长。

  • 说明：**ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持崩溃恢复和原子广播协议，**基于该协议，Zookeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性。如下图：（参考链接：//zhuanlan.zhihu.com/p/60352367）
    

• 三种算法比较：