分布式一致性与共识算法

发表于 | 更新于 | 分类于 | 阅读次数：

概要

在分布式系统中采用多副本存储数据，要保证各个数据副本的一致性，就要保证多个副本的更新操作序列{Op1,Op2,…,Opn}是相同的。而共识算法正是为解决分布式系统的一致性问题提出的，即保证集群中所有节点中的数据及更新操作序列完全相同。

共识算法又分为非拜占庭容错（eg. Paxos, Raft）和拜占庭容错（eg. POW, POS, DPOS），本文主要介绍非拜占庭容错的共识算法。

分布式基础知识

  1. CAP理论是分布式系统著名的定理，即“在异步的网络模型中，所有的节点由于没有时钟仅仅能根据接收到的消息做出判断，这时不能同时保证一致性、 可用性和分区容错性，三者不可兼得”。由于网络一定会存在延时，因此强一致性的系统会导致系统的可用性降低，因此在实际情况中，我们往往通过降低对一致性的要求，实现一致性和可用性的权衡，所以在目前主流的分布式系统中都选最终一致性。最终一致性允许多个节点的状态出现冲突，但是所有能够沟通的节点都能够在有限的时间内解决冲突。
  2. 拜占庭将军问题是分布式系统中著名的容错问题，指出”存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或不存在本问题“，而Lamport证明了”在将军总数大于3m ，背叛者为m 或者更少时，忠诚的将军可以达成命令上的一致“。
  3. FLP不可能定理是分布式系统领域重要定理之一，指出了”在网络可靠并且存在节点失效的异步模型系统中，不存在一个可以解决一致性问题的确定性算法“。

Paxos

场景

  1. 设计一个系统，存储名称为var的变量（var是任意二进制数据，由Proposer提交，Acceptor存储和管理）；
  2. 系统需要保证var取值满足一致性；
  3. 满足容错性（可容忍任意Proposer故障及半数以下Acceptor故障）。

历史方案

  1. 单个Acceptor，Proposer通过互斥锁申请访问权，提交取值；

    -> 不能容忍Proposer的故障，会导致系统陷入死锁。

  2. 抢占式访问权，Proposer向Acceptor申请访问权时指定编号epoch（越打越新），Acceptor采用喜新厌旧的原则，给新epoch发放访问权。新epoch可以抢占旧epoch使之失效，为了保持一致性，不同epoch的proposer之间采用“后者认同前者”的原则，只有在肯定旧epoch无法生成确定性取值时才会提交自己的value，否则承认旧epoch的值。

    -> 仍需要引入多Acceptor。

Paxos方案

Proposer：

  1. 获取半数以上Acceptor的访问权和对应的一组var的取值，获得访问权；
  2. 后者认同前者的原则执行value的提交：如果var的取值都为空，则努力使自己提交的var成为确定性取值；如果不为空，认同对应var的取值，并努力使之成为确定性取值。

实战

  1. 微信生产级paxos类库PhxPaxos

    引入了learner，Leader和状态机

  2. Paxos在Google的Chubby, Megastore和Spanner中的应用

  3. 利用Paxos实现一个分布式存储系统

参考文章

https://www.bilibili.com/video/av36134550/

微信生产级paxos类库PhxPaxos：https://mp.weixin.qq.com/s/6VWUA5EDV2UIq4NqmQYWUA

分布式一致性与共识算法：https://draveness.me/consensus