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

# Proposerproposer(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并告诉所有成员# Acceptoracceptor 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.Acceptor或Learner解体了；2.Leader解体了。

3.1.1. Acceptor 解体

如下图所示，S1为Leader，当其收回Accept申请时，S4和S5解体了。然而S1，S2，S3依然形成多数派，所以$v$依然能够被决定下来。

3.1.2. Leader 解体

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

3.2 网络宰割(network partitioning)

另一种常见谬误是网络宰割。如下图所示，S1，S2与S3，S4，S5之间的通信被断开，分成了两个子网络。在这种悲催的状况下，零碎依然能够达成共识。
一旦产生宰割，通过谬误检测是能够发现的，例如超时。而后多数派一方就会进行从新选举，如图，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 ↩