关于分布式:共识算法Paxos-算法

34次阅读

共计 3083 个字符,预计需要花费 8 分钟才能阅读完成。

1. 目录

[TOC]

2. 共识问题 1

  • 什么是共识问题?
    粗略地说,该问题是在一个或多个过程提议了一个值该当是什么后,使过程对这个值达成统一协定。
  • 解决什么问题?

    • 在一个计算机提议一个动作后,管制引擎的所有计算机要决定“持续”还是“放弃”。
    • 在互斥中,过程对哪个过程能够进入临界区达成协定。
    • 在选举中,过程对入选过程达成协定。
    • 在全排序组播中,过程对消息传递程序达成协定。

2.1 一个例子:问题形容 2

假如有两支(或多支)军队,他们必须做到同时防御或同时防守,否则就会失败。所有军队组成一个零碎,他们必须独特动作。问题是,如何让他们各自为政?

当初无妨把军队看做”过程“,把防御或防守看做一个变量”口头“。

  • 单机零碎 中,这个问题很容易解决。用一个互斥量就搞定了,相似于多线程。
  • 分布式系统 中,这个问题就麻烦啦。假如每个过程都在不同的服务器上,他们就无奈通过共享内存达到同步。如果过程是军队的话,军队之间只能通过通信兵来进行通信(消息传递)。基于消息传递的分布式军队零碎会有这些问题:

    1. 如何确定另一支军队是否被干掉?(服务器解体)
    2. 如何晓得通信兵是否被杀死(音讯失落)或久久未达到其余军队(提早不可预知)?
    3. 如果马路等通信信道被切断怎么办?(网络宰割)

2.2 另一个例子

在一个分布式数据库系统中,如果各节点(server,或过程)的初始状态统一,每个节点都执行雷同的操作序列,那么他们最初能失去一个统一的状态。为保障每个节点执行雷同的命令序列,须要在每一条指令上执行一个“一致性算法”以保障每个节点看到的指令统一,是分布式计算中的重要问题。

3. Paxos 的一致性准则 3

  • Safety(坏的事件肯定不会产生)

    1. 只有被提议的值才会被抉择;
    2. 只能有一个值被批准,不能呈现第二个值把第一个笼罩的状况;
    3. 每个节点只能学习到曾经被批准的值,不能学习没有被批准的值。
  • Liveness(好的事件最终肯定会产生)

    1. 最终会批准某个被提议的值;
    2. 一个值被批准了,其余过程最终会学习到这个值。

Paxos 只保障 Safety,而不能保障 Liveness。

4. Paxos 算法形容

4.1 假如 3

每个 server 都能够负责三种角色:提案者 (Proposer)、 接受者 (Acceptor)、 学习者(Learner)。提案者负责提出提案(proposal),接受者负责通过提案,而学习者负责更新提案。

每个 提案 都会被调配一个自然数 $n$ 作为 ID,以及一个须要提出的值 $v$。

4.2 抉择一个值(Choosing a Value) 3

阶段一
a. 提案者 抉择一个提案 (proposal) 编号 $n$,向 接受者多数派 组播一个 prepare 申请。
b. 如果一个 接受者 收到一个 prepare 申请,并且编号 $n$ 是所有他曾经通过的 prepare 申请中最大的,那么他会批准这个新的 prepare 申请,并承诺不会再批准任何比 $n$ 小的 prepare 申请和 accept 申请。

阶段二
a. 如果 提案者 收到一个 接受者多数派 的回应 prepare_ok(n,na, va),那么他就选出最大的 $n_a$ 所对应的 $v_a$。或者,若所有回应中 $v_a$ 都为空,也就是还没有批准过任何提案,那么就抉择本人的 $v$。而后发送accept(n,v) 申请。
b. 如果一个 接受者 收到一个 accept(n,v) 申请,并且 $n$ 大于所有它 prepare 过的 $n_p$,那么他就承受这个 $v$,而后回复 accept_ok(n)

4.3 学习一个值(Learning a Chosen Value)

当一个提案被多数派通过,这提案者就向所有人(servers)发送decided(v),贯彻与落实这个 $v$。

4.4 Paxos 伪代码4

# Proposer
proposer(v):
    while not decided:
        n = heigher(N[:])  # 尝试调配一个以后最大的 n 值给这个 proposal
        send prepare(n)     # 向所有 acceptor 发送 prepare request
        # 若大部分返回 ok:if prepare_ok(n, na, va) from majority:
            # 从 {na...} 中选出最大的那个和对应的 va,令 v =va;否则,就选本人的 v
            v = va with heighest na; otherwise choose its own v
         
            send accept(n, v) to all  # 向所有 acceptor 发送 accept request
            if accept_ok(n) from majority:
                send decided(v) to all  # 决定 v 并告诉所有成员

# Acceptor
acceptor state on each node (persistent):
    np      # 最大的 promise 值
    na, va  # 最大的 accepted 值
    
    prepare(n) handler:
        if n > np:
            n = np
            send prepare_ok(n)  # 承诺不再承受任何比 n 小的 proposal
        else:
            send prepare_reject
    
    accept(n, v) handler:
        if n >= np:
            na = n
            va = v
            send accept_ok(n)
        else:
            send accept_reject

直观了解


容错性剖析(Fault tolerant) 5

到底 Paxos 是如何保障一致性的呢?例子如下。

3.1 服务器解体(crash)

若有 $2f+1$ 台服务器,则最多能够容忍 $f$ 台服务器解体。上面举一个简略的例子,假如一个分布式系统由 5 个 servers 组成,其中 2 个在任意时刻解体。存在两种状况:1.AcceptorLearner 解体了;2.Leader解体了。

3.1.1. Acceptor 解体

如下图所示,S1Leader,当其收回 Accept 申请时,S4S5解体了。然而 S1S2S3 依然形成多数派,所以 $v$ 依然能够被决定下来。

3.1.2. Leader 解体

Learder解体要略微麻烦一点。首先要有谬误检测,发现 leader S1挂了。而后,因为没有 leader 了,所以要从新选举。如图,S1S5挂了,然而 S2S2S3 依然形成多数派。S2收回 prepare 申请,S3S4返回最近承受的 $v_1$,$v_1$ 再次被 S2 申请承受。于是 $v_1$ 还是胜利被决定下来了。

3.2 网络宰割(network partitioning)

另一种常见谬误是网络宰割。如下图所示,S1S2S3S4S5 之间的通信被断开,分成了两个子网络。在这种悲催的状况下,零碎依然能够达成共识。
一旦产生宰割,通过谬误检测是能够发现的,例如超时。而后多数派一方就会进行从新选举,如图,S3成为新 leader。零碎又能够失常运作了。
不过,问题还没完。如果网络通信在某一时刻又恢复正常,分布式系统中就会同时存在两个 leader!Paxos 还能够保障共识吗?是能够的。因为 $n_2>n_1$,S3~S4 曾经承诺不再承受比 $n_2$ 小的提案了。所以老 leader S1的提案 $(n_1,v_1)$ 会被回绝,而 S3 的提案 $(n_2,v’)$ 会取得通过。

3.3 音讯失落(message lost)

因为网络层是不牢靠的,音讯失落和延时是无奈防止的。应答这类谬误的次要办法还是重传。

参考文献


  1. 分布式系统:概念与设计,共识和相干问题 零碎模型和问题定义 ↩
  2. 分布式系统:概念与设计,共识和相干问题 同步零碎中的共识问题 ↩
  3. Lamport,L: Paxos Made Simple. ACM Trans. on Comp. Syst. ↩
  4. MIT 6.824 Lab 3: Paxos-based Key/Value Service ↩
  5. Tutorial Summary: Paxos Explained from Scratch ↩

正文完
 0