MENU

一致性算法(Paxos、Raft、ZAB)

June 5, 2018 • Read: 565 • 算法

对于一个分布式系统,不能同时满足以下三点:

  • 一致性
  • 可用性
  • 分区容错性

image

什么是一致性

一致性模型

  • 弱一致性

    • 最终一致性

      • DNS
      • Gossip
  • 强一致性

    • 同步
    • Paxos
    • Raft
    • ZAB

paxos其实是一个共识算法。系统的最终一致性,不仅需要达成共识,还取决于Client的行为

强一致性算法——主从同步

主从同步复制

  1. Master接受写请求
  2. Master复制日志至slave
  3. Master等待,直到所有slave返回

问题:一个节点失败,Master阻塞,导致整个集群不可用,保证了一致性,可用性却大大降低
image

强一致性算法——多数派

每次写入都保证写入大于N/2个节点,每次读入保证从大于N/2个节点中读取

image
问题:在并发环境下,无法保证系统的正确性,顺序非常重要

强一致性算法——Basic Paxos

  • Client:系统外部角色,请求发起者。像民众
  • Propser:接收Client请求,向集群提出提议(propose)。并在冲突发生时,起到冲突调节的作用。像议员,替民众提出议案
  • Accepter:提议投票和接收者,只有在形成法定人数时,提议才被最终接受。像国会
  • Learner:提议接受者,backup,备份,对集群一致性没影响。像记录员

步骤:

  1. Prepare

    propser提出一个提案,编号为N,此N大于这个ProPser之前提出的议案编号,请求acceptor的quorum(法定人数)接受
  2. Promise

    如果N大于此acceptor之前接受的任何提案编号则接受,否则拒绝
  3. Accept

    如果达到了quorum,propser会发出accept请求,请求包含提案编号N,以及提案内容
  4. Accepted

    如果此acceptor在此期间没有收到任何编号大于N的提案,则接受此提案内容,否则忽略

基本流程

image
部分节点失败,但达到了Quorum

image
Propser失败

image
潜在问题,存在活锁

image

强一致性算法——Multi Paxos

基本流程:首先有一个Propser竞选Leader,只要在Leader不宕机,以后都由这个Leader提出提案

image
减少角色,进一步简化。首先Server中有一结点竞选Leader

image

最后编辑于: January 1, 2019
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment