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发送心跳包,确认存在;任期结束后开始新一轮选举
日志复制
- leader收到client请求后,先写自己的log,然后发到所有服务器,确认记录复制后,回应client
- 每条日志记录会存命令以及term编号,term用于检测日志的不一致。日志记录是持久,且最终一致的。当log复制到大多数服务器被接受时,才算提交成功。
- 选主时,当投票者的log比candidate更新时,它会拒绝请求;为确保安全,candidate只有比半数以上候选者的log新时,才可以成为leader
- 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
画师:烏鴨
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 suisbuds!