天天看点

分布式共识算法paxos,Raft,ZAB原理前言一、paxos二、RaftZAB

目录

  • 前言
  • 一、paxos
    • basic paxos
        • 证明
        • 角色
        • 过程
        • 缺陷
    • Multi-paxos
        • 和paxos的区别
        • 过程
  • 二、Raft
        • Raft和multi-paxos的区别
        • 问题定义
        • 角色定义
        • 选举过程
        • 日志同步过程
        • 网络故障处理
  • ZAB
        • 与raft区别

前言

对于分布式中,多个节点的数据强一致性问题,通常采用如下策略或算法为解决方案。

  • 主从同步
  • paxos
    • basic paxos
    • multi paxos
    • fast paxos
  • Raft
  • ZAB

一、paxos

basic paxos

paxos 首先假设通信是安全的

证明

角色

  • Proposer 提议发起者,处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。
  • Acceptor 提议批准者,负责处理接收到的提议,他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
  • learner 记录者,负责记录提案。

过程

缺陷

  • 效率低下
  • 难以实现
  • paxos存在活锁问题,多个proposer提出提案,且n不断增长,则任何一个提案都无法被达成。
  • 如果learner不止一个,则learner间数据同步依然是个问题

Multi-paxos

multi paxos 是paxos算法的优化,升级版。以便该算法能够被应用在现实中。

lamport 对multi-paxos 的具体实现其实是并没有细节的指定的, 只是简单提了一下. 所以有各种不同的multi-paxos 的实现

和paxos的区别

multi-paxos对角色进行了新的抽象

  • Leader/master:唯一的proposer ,
    • multi-paxos规定只能有一个提案提出者,所有请求都需要经过leader。
    • 这个策略保证了提案的有序,所以简化掉了paxos的prepare阶段。
  • node: 去掉了各种角色,统一为节点,更接近计算机实现
    • 通过一定的策略竞选出某个节点为第n任主节点,则其它节点为从节点
    • 从节点负责接收主节点的数据,也就是提案,可以理解为数据库的主从同步。

过程

  1. 发起者(leader)直接告诉其他节点,准备递交协议号为I+1的协议
  2. 收到了大部分从节点的回复后,主节点就直接回复client成功写入

二、Raft

因为paxos难以理解,难以实现,所以raft应运而生。

可以说raft是multi-paxos的优化升级版,更易理解,且补充了实现方案。

paxos 是对于一个问题达成一致的协议

而raft 本身是对一堆连续的问题达成一致的协议

raft是etcd的采用的共识算法

动画演示 http://thesecretlivesofdata.com/raft/

官网:https://raft.github.io/

Raft和multi-paxos的区别

raft 是基于对multi paxos 的两个限制形成的

  • 发送的请求的是连续的, 也就是说raft 的append 操作必须是连续的. 而paxos 可以并发的. (其实这里并发只是append log 的并发提高, 应用的state machine 还是必须是有序的)
  • 选主是有限制的, 必须有最新, 最全的日志节点才可以当选. 而multi-paxos 是随意的 所以raft 可以看成是简化版本的multi paxos(这里multi-paxos 因为允许并发的写log, 因此不存在一个最新, 最全的日志节点, 因此只能这么做. 这样带来的麻烦就是选主以后, 需要将主里面没有的log 给补全, 并执行commit 过程)

问题定义

raft将共识问题划分成三个子问题,实现了这三个子问题,则实现了共识问题。

  • 选主
  • log同步
  • safety 在所有的操作中,集群共识一直是一致。

角色定义

  • leader 接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
  • follower 接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
  • candidate follower在精选leader时,会先变成candidate

选举过程

  1. 一个follower节点总是在等待超时,在超时前接收到leader的心跳,则重置超时。如果超时,则变为candidate节点开始竞选,任期(term)+1,Vote count为1(自己投了自己)。并向其他节点发送竞选通知。
  2. 如果得到选票响应超过半数,则该节点变为leader节点。并周期向其他节点发送心跳。
  3. 如果得到选票响应不超过半数,则等待随机时间。如果期间内没有给其他节点投票,则发起第二轮选举。

日志同步过程

网络故障处理

1.网络分区

则每个分区都会产生一个leader,但只有节点较多的分区能够保存数据成功。

在分区恢复后,任期较低的leader节点变为follower,并从leader节点同步日志。

ZAB

zab 与raft基本相同,也是multi-paxos的一种实现

是zookeeper的实现算法

与raft区别

  • zab中一个leader周期叫做epoch raft中叫做term
  • zab心跳包由从节点发往主节点,raft是主节点发往从节点

继续阅读