分布式-全序广播与共识

概述

本文将简要概括全序广播与共识，清楚的理解这两个概念，将有助于理解raft、paxos等共识算法。

全序广播的要点是：消息按照相同的顺序发送到所有节点，有且只有一次。 仔细想想，这相当于进行多轮的共识过程：在每一轮，节点提出他们接下来要发送的消息，然后决定下一个消息的全局顺序。

主从复制与共识

主从复制是single master replication，master接收信息并广播给从节点，可以对标为一种fixed-sequencer的total order broadcast的实现方式（即[1]中的section4.1 fixed sequencer）。

但当主节点出故障时，我们需要重新选主。选主就涉及到共识，通过选举的方式将某个从节点提升为新的主节点。 同时还需要考虑脑裂，我们需要共识算法来选出一位主节点。 但如果共识算法是全序广播的话，又需要主节点，陷入奇怪循环。 如何解决呢？

Epoch and Quorum

目前讨论的共识协议在内部使用了某种形式的主节点，虽然主节点不是固定的。 相反，他们都采用了一种弱化的保证：协议定义一个世代编号（epoch number，对应raft中的term、paxos中ballot number) .

  • 如果当前主节点失效，那么开始新的一轮选举， 选举赋予一个单调递增的epoch号。如果两个不同主节点对应于不同epoch号码，则具有更高epoch号码的主节点将获胜
  • 在主节点作出任何决定之前，必须首先检查是否存在比它更高的epoch号码，否则就会产生冲突的决定
    • 节点不能依靠自己所掌握的信息来决策。比如出现分区，老的主节点在分区的小集群上，新的主节点在多数集群上产生，这时候老的主节点其实已经失效。
    • 这里面实际有两轮不同的投票：首先是投票决定谁是主节点，然后是对主节点的提议进行投票。
    • 在raft的读取中，这是 read index.

投票过程与两阶段提交2PC

  • 2PC的协调者并不是依赖选举产生
  • 容错共识算法只需要收到多数节点的投票结果即可通过决议，而2PC则要求每个参与者都必须做出“是”才能最终通过。

共识算法与全序广播

全序关系广播的要点是：所有节点按照相同顺序接收消息，有且只有一次。 如果仔细想想，这其实相当于进行了多轮的共识过程。在每一轮中，节点提出他们接下来想要发送的消息，然后决定要以全序的方式接收的下一个消息。

所以，全序关系广播相当于持续的多轮共识（每一轮共识的决定对应于一条消息的接收）：

  • 由于共识的一致性属性（agreement property)，所有节点以相同顺序接收相同消息
  • 由于诚实性，消息不能重复
  • 由于合法性，消息不会被破坏，也不会凭空捏造
  • 由于可终止性，消息不会丢失。

对标到raft协议中的日志复制

raft协议中的日志复制是否可以对标全序广播

我们看一下全序广播：

  • 尽最大努力可靠的广播，通过重发丢失的消息
  • 基于可靠广播，保证接收顺序

total order broadcast protocol 要满足下面四个属性：

  • validity (正确性)：如果一个正确的进程广播了一条消息，那么其他所有正确的进程都接收到这条消息
  • uniform agreement: 如果一个进程接收到消息m，那么所有正确的进程都接收到消息m
  • uniform integrity: 一个进程最多接收一次消息m
  • uniform total order: 如果进程p和q都接收到消息m和m’，当且仅当q接收消息m早于m’时，进程p接收消息m早于m’

综上所述， raft的日志保证是满足上述属性的。

  • 尽最大努力可靠的广播：如果失败，则一直发送 附加条目rpc
  • 基于可靠广播，保证接收顺序：接收到一条信息，leader会广播，然后作出决定 是否可以提交。

raft的实现中：

  1. leader 处理不一致是 通过强制跟随者直接复制自己的日志来解决的。 leader从来不会覆盖或者删除自己的日志。
  2. 安全性保证：当出现分区（或leader崩溃）时，只有拥有最新已提交记录的候选者才能成为leader。

特别注意：

在<数据密集型应用系统设计>中 将delivery翻译为发送，这实际是错误的。 在分布式-广播中介绍了，广播协议中 broadcast/deliver 对应的是发送和接收。 全序广播实际是指接收者要保持全序，与发送者的顺序无关。

参考：