Leader Election Algorithm

共识算法

保证数据一致性

• 主从一致性：共识算法
• NRW：满足R(读取分片数) + W(写入分片数) > N(节点总分片数)即可保证数据一致

---

集群：多台服务器组成，每个服务器是一个节点
主节点：选出主节点管理其他节点，保证数据在每个节点上的一致性
CAP理论：分布式系统不能同时满足consistency、availability、partition tolerance

Base理论：Basically Available(基本可用)，Soft state（软状态）,和 Eventually consistent（最终一致性），是CAP的弱化

分布式事务

• ACID问题：atomicity(原子性)、consistency(一致性)、isolation（隔离性）、durability（持久性）
• 2PC：阶段一：事务询问+执行事务；阶段二：执行事务提交+中断事务
• 3PC：相对2PC引入准备阶段和超时机制，canCommit->preCommit->DoCommit
  拜占庭问题：恶意节点, 采用POW（工作量证明）和POS（权益证明）共识算法 -> 区块链

Raft算法

一言以蔽之，少数服从多数，民主投票算法

• 优点
  • 选举稳定性好，新节点加入时会触发选主，由于需要获得半数投票，不一定切主
  • 选举速度快
• 缺点
  • 通信量大，每个节点都要相互通信，且获得半数投票
• 角色
  • Leader: 周期性heartBeat到follower
  • Candidate：只有candidate可以选为leader
  • Follower
• event loop: (follower, candidate)超时选举，leader发送heartbeat到follower
• 应用：k8s,etcd

选举流程

• 开始选主：follower一段时间没收到心跳包
• 选主阶段：每一轮每一节点只能投一次票
  • 使用term计数, 首先所有follower升为candidate, 给自己投票并向其他节点发投票请求
  • candidate收到自称leader的请求，若leader的term>candidate，则candidate承认并降为follower，否则拒绝
  • 两个candidate票数一样多，则超时重新选举（故采用奇节点）
• 选举结束：所有candidate降为follower, leader会与follower发送心跳包，确认存在；任期结束后开始新一轮选举

日志复制

1. leader收到client请求后，先写自己的log，然后发到所有服务器，确认记录复制后，回应client
2. 每条日志记录会存命令以及term编号，term用于检测日志的不一致。日志记录是持久，且最终一致的。当log复制到大多数服务器被接受时，才算提交成功。
3. 选主时，当投票者的log比candidate更新时，它会拒绝请求；为确保安全，candidate只有比半数以上候选者的log新时，才可以成为leader
4. leader通过强制follower复制自己的log来处理不一致

ZAB算法

具有优先级的民主投票，相较raft,增加节点ID和数据ID选主，保证数据最新性, 但是选举较慢

• 角色
  • Leader
  • Follower
  • Observer
• 节点状态
  • Looking：选举状态
  • Leading：当前节点为Leader
  • Following：追随Leader
  • Observing：没有投票权和选举权
• 选主原则
  • 少数服从多数，ID大的优先
  • 每个节点有三元组(server_ID,server_zxID,epoch)，分别表示节点ID、数据ID、选举轮数
  • server_zxID最大者成为Leader；若server_zxID相同，则server_id最大者成为Leader
• 应用：zookeeper

Paxos算法

刨去拜占庭问题的完备共识算法，包括basic paxos算法+multi paxos思想，raft是paxo算法的简化

• 角色
  • Proposer/coordinator:接受客户端请求并发起提案
  • Acceptor：投票
  • Learner：某个提案超过半数投票，则Learner将接受该提案并运算，将结果返回客户端

Bully算法

长者为大

• 选举原则
  • 每个节点均知道其他节点的ID, 活着的ID大的节点直接胜利
• 信息
  • Election：发起选举
  • Alive：应答，在活着的节点中选举
  • Victory：主节点向其他节点宣誓主权
• 优点：选举快，易实现
• 缺点：每个节点需要全局节点信息；新节点加入会导致频繁切主
• 应用：MongDB, 时间戳为ID
• 流程
  

三者对比

---

cover
id：36075756
画师：烏鴨