企业架构

分布式架构的根基：深入浅出一致性算法

Posted by Coding Ideal World on January 23, 2021

分布式算法的介绍文章可谓汗牛充栋，但或是过于学术证明或是过于简单，笔者将尝试挑战用一篇文章，让近乎0基础的同学都可以理解一致性算法的原理。

分布式服务的困局

我们试想一个常见的电商场景：超时订单自动关闭，在下单后X小时内未支付的话自动关闭订单并释放库存。这时我们需要有一个定时器定时触发相关的业务操作，从高可用的角度看这个定时器需要部署多个实例，但对同一订单仅只允许触发一次。要实现这个需求有多种方案，最常见的就是集群领导者选举，可以以实例或订单组为维度选出领导者并由其负责执行特定订单的触发。领导者选举有着广泛的应用场景，我们可以尝试将之抽象成独立的服务。

2021 01 23 19 48 42

如上图，实现非常简单：

  • 创建一个领导者选举服务，使用CAS原子化地设置变量 leader 其值等于对应的实例Id， leader 的值在一定的存活周期后自动销毁以避免服务实例不可达导致没有可用的领导者

  • 多个订单服务向领导者选举服务定期提交请求，希望将自己设置成领导者

  • 领导者选举服务中 leader 的值如果存在则直接返回，反之根据先到先得原则设置 leader 的值为对应的实例Id并返回

但这个方案的问题也很明显：“领导者选举服务”单点了，一个节点挂了会导致服务不可用。那么能用多实例吗？

2021 01 23 19 51 11

如上图，这是两种多实例扩展的方案。

方案一下不同的订单实例会随机路由到不同的领导者选举服务实例，再由领导者选举服务各实例自身实现数据同步。那么怎么同步？当然可以使用数据库、Redis等中间件实现，但这导致了该服务并不纯粹，我们希望这个服务不依赖于三方服务或中间件。

方案二下要求订单服务向所有领导者选举服务实例发送请求，只要有一个领导者选举服务实例存活服务整体就还是可用的，但这一方案的问题在于请求发送与接收存在网络时延，导致不同领导者选举服务实例收到的顺序可能是不一样的，进而无法形成统一的结果。而这正是我们所面临的最棘手的一致性问题。

一致性算法

分布式架构涉及很多方面的知识，但如果要刨根问底，探寻根基的话，那么一定是一致性（共识，Censensus）算法无疑了。一致性算法是分布式架构的基础，为节点伸缩提供了核心保障。

如何在多个实例中选择领导者，如何实现数据多副本存储，如何设计分布式锁，如何确定全局ID……这一切的基石都在于一致性保障。

一致性算法很晦涩难懂，一代IT人试图用各种方式“深入浅出”地介绍一致性问题的算法实现，但真正能被大众接受的少之又少。接下来不先不介绍一致性的算法派系，也不去做严格的算法推导，我们先从问题出发，逐步深入。

我们回顾上文遇到的问题：网络的时延导致各实例接收到请求的顺序可能各不相同，那么我们是否可以从时序保证上入手呢？比如将所有请求先发到MQ，再由MQ分发请求，这的确可以解决，但是要知道的是MQ本身也需要一致性支持，这是就先有鸡还是先有蛋的问题了，所以去要求严格的消息时序以解决一致性问题是不可能的。

我们大致上总结一下分布式数据一致性要解决的问题：

在多实例中确定一个变量的值，一旦确定后只能获取不能修改。

比如上文的领导者选举就是为确定 leader 变量的值，所谓“确定”即要求领导者选举服务同一时间周期内（比如一个选举周期）对外输出的领导者是唯一的，即要求领导者选举服务的不同实例间对 leader 的取值达成共识（同一时间周期内不能订单服务inst1拿到的是 leader = inst1 ，订单服务inst2拿到的是 leader = inst2 ），并且这同一时间周期内确定的值不能被更改（同一时间周期内在确定 leader = inst1 的前提下订单服务inst3发起选举不可以更改 leader 的取值）。

我们将确定变量值的过程看做“投票”，为规范后续的用词，我们先做以下简单的定义：

  • Proposer 提案人，发起提案的请求方，比如上文的各订单服务实例

  • Acceptor 投票人，负责对提案发起投票，比如上文的各领导者选举服务实例

那么我们思考下这投票的过程中带来的实现难点：

难点一：存在多个Proposer提案人并发请求导致接收到投票的时序无法保证

要解决这个难点最直接的做法是加锁，如下图；

2021 01 23 20 01 23

我们将原本一步完成的操作分成两个步骤：

  • 准备阶段：

    • Proposer向Accepters发起加写锁的请求

    • Accepter收到请求返回成功或失败（已被加过锁）

  • 投票阶段：

    • Proposer在收到所有Accepter都加锁成功时发起投票

    • 各Accepter同意投票结果，形成确定性取值

    • 各Accepter释放锁

我们暂不考虑算法的效率问题，这样的确可解决时序问题，但这要求所有Accepter都能响应请求显然是不合理的。

难点二：部分Accepter故障时仍然可用

要解决这个问题我们只要修改加锁成功的条件为“半数以上”，如下图：

2021 01 23 20 02 28

这样服务可做到2F+1的容错能力，即在2F+1个Accepter实例的服务中最多允许F个Accepter实例同时出现故障。

既然Accepter允许故障，那么Proposer也应如此，但这述算法中如果某Proposer实例获取到锁后发生了故障即会引发死锁导致服务不可用。

诚然我们可以为锁加过期时间（由Proposer指定本次锁的到期时间以确保可以在同一时间释放），但这样做以及加锁本身对服务的可用性/性能影响都比较大。

难点三：任意Proposer故障时仍然可用

我们推演到现在，使用锁的方式遇到了严重的挑战，但我们可以按着上述两阶段投票的方式进行改进。

由于放弃加锁的方式，那么就不得不去直面并发请求带来的时序问题，首先想到的应该是为投票的提案带上时间戳以区别提案的前后时间。

我们先以只有一个Accepter的情况分析，如下图：

2021 01 23 20 04 32

对于Proposer1而言，它的流程如下：

  1. Proposer1发起了提案号为 n1 的提案请求，这里要求提案号是有序递增的，多可使用时间戳组成

  2. Acceptor收到了提案请求，将自身的 maxN （收到的最大提案号）修改成 n1 ，并承诺 不接收小于等于 maxN 提案号的请求

  3. 返回提案请求允可

  4. Proposer1正式发起提案，内容为之前的提案号及提案的值

  5. Acceptor收到了提案，将自身的 acceptN （接受的提案号） 更新为 n1 、 acceptV （接受的提案值，即确定的值） 设置成 v1 , 并承诺 不处理小于 maxN 提案号的提案

  6. 返回提案成功

对于Proposer2而言，它的流程如下：

  1. Proposer2发起了提案号为 n2 的提案请求

  2. Acceptor收到了提案请求，将自身的 maxN 修改成 n2

  3. 由于已形成了确定性值，所以直接返回已确定的值

从上面流程中可见，值的确定性是由 后者认可前者 的原则保障，只要有确定性的值，后续的提案都会认可这个值。

我们再看复杂些的情况：

2021 01 23 21 06 53

如上图，Proposer1与Proposer2交叉执行，它们的流程如下：

p1-1.2.3. 同前面流程
p2-1. 此时Proposer2发起了提案号为 n2 的提案请求
p2-2. Acceptor收到了提案请求，将自身的 maxN 修改成 n2
p2-3. 返回提案请求允可
p1-4. 此时Proposer1正式发起提案，提案号 n1 提案值 v1
p1-5. 由于已有更大的提案号 maxN = n2 ，所以返回错误
p2-4. 此时Proposer2正式发起提案，提案号 n2 提案值 v2
p2-5. Acceptor收到了提案，将自身的 acceptN 更新为 n2 、 acceptV 设置成 v2
p2-6. 返回提案成功
p1-6. 由于Proposer1的第一次提案没有通过，所以增加提案号后重新发起提案申请，提案号为 n3
p1-7. Acceptor收到了提案请求，将自身的 maxN 修改成 n3
p1-8. 由于前面已经形成了确定性值，所以直接返回之前的提案值

从上面流程中可见，Proposer2可以抢占Proposer1的提案权，即后发起的提案在未形成确定性值时可以抢占现有的提案权。

至此，我们可以容忍任意Proposer的故障，那么存在多个Acceptor时又如何呢？

实际上，Acceptor做的事与前面单一Acceptor场景一样，核心在于确保Proposer向所有的Acceptor发起请求，仅当超半数Acceptor返回成功时才算请求成功，否则重试。

2021 01 23 21 11 50

上图略显复杂，我们逐步分析：

p1-1-6. 同前面流程
p2-1-9. 抢占式提案，使当前各Acceptor的 maxN 修改成 n2
p1-7.8. Proposer1向Acceptor3（网络时延）发起了提案请求，但在提案请求阶段Acceptor不接受 ⇐ maxN 的提案号，故返回错误
p1-9-12. 由于超半数Acceptor返回成功（前一幅图），可以提交提案，但在提案提交阶段Acceptor不接受 < maxN 的提案号，故返回错误
p2-10-14. 此时Proposer2超半数Acceptor返回成功，可以提交提案，由于提案请求返回中都没有确定性值时，故使用Proposer2预设的值v2提交，超半数提案提交成功，故已形成确定性值
p1-13-21. Proposer1更新提案号重新发起提案请求，各Acceptor更新 maxN 为最新的提案号 n3 并返回各自已确定的值
p1-22-30. 提案请求返回中存在确定性值： Acceptor1的(n2, v2) 及Acceptor2的(n2, v2) 使用提案号最大的确定性值做为新提案的值，对于上例是最大提案号 n2 , 对应的值为 v2，最终Proposer1与Proposer2都得到了确定性值 v2

如果各位能理解上述流程，那么恭喜你，你已经掌握了一致性算法中最著名的 Paxos算法 核心。

Paxos:开山鼻祖

Paxos ，这是公认的最伟大的分布式一致算法，可能没有之一。Google的Chubby、Spanner都使用了Paxos以保证数据副本更新序列的一致性。

Paxos协议见于Leslie Lamport在1998年发的 《The Part-Time Parliament》 ，在此论文中他假设了一个叫Paxos的小岛，岛上的各项决定要经议会同意，议会成员都是兼职的，议员的核心角色分为提案者（Proposers）、表决/投票者（Acceptors）。Proposer 提出提案（Proposal），提案信息包括提案编号和提议的值（Value），Acceptor 收到提案后可以接受（Accept）提案，若提案获得多数 Acceptors 的接受，则称该提案被批准（Chosen）。

此论文的描述晦涩难懂，以至于很多专业人士也一头雾水，所以Lamport在2001年又发表了 《Paxos Made Simple》 以简化说明，但这还是过于晦涩。

Paxos 算法有很多变种，包含但不限于：Basic Paxos、Multi Paxos、Fast Paxos、Byzantine Paxos……

值得一提的是 Paxos 能容忍消息丢失（节点不可达）、乱序，但存储必须可靠（没有数据丢失和错误），即这是“非拜占庭算法”，而 Byzantine Paxos 则解决了拜占庭场景。关于拜占庭问题我们后文会介绍。

如果上文的图示没有看懂，那么下文我们以 Basic Paxos 这一经典算法为例写伪代码进一步阐述。

Basic Paxos

Paxos流程描述的文章太多了，但文字的描述过于苍白，上文我们用示例加示意图的形式已经描述了其核心流程，下面我们再用伪代码的形式更严格地描述Basic Paxos的核心流程：

Table 1. Basic Paxos核心流程伪代码
Phase Proposer Acceptor

1a:Prepare

 
# 当前Proposer收到（来自client）的值，可以是某一配置、记录或日志等
var value = <input value>
# 提案号，全局唯一且有序递增
var n = <auto incremental value, e.g. timestamp>
# 发起提案请求，返回各Acceptors对此提案的承诺
# rst = 结果（ok/error）
# acceptN = 被接受的提案号
# acceptV = 被接受的值
var promises:Set((rst, acceptN, acceptV)) = acceptors.foreach.prepare(n)

1b:Promise

 
# 当前Acceptor保存的最大提案号
var maxN = null
# 当前Acceptor接受的提案号及值
var (acceptN, acceptV) = null

...

# 处理提案请求
# n = 收到的提案号
def prepare(n){
    if(maxN == null){
        # 当前Acceptor最大提案号为null
        # 则将收到的提案号做为最大提案号
        maxN = n
        # 返回成功及当前Acceptor接受的提案号及值（都为null）
        return (ok, null, null)
    }else if(n <= maxN){
        # 收到的提案号小于等于当前Acceptor最大提案号
        # [核心] 承诺不接收小于等于 maxN 提案号的请求
        # 则返回错误
        return (err, null, null)
    }else{
        # 收到的提案号大于当前Acceptor最大提案号
        # 则将收到的提案号做为最大提案号
        maxN = n
        # 返回成功及当前Acceptor接受的提案号及值（可能为null也可能不为null）
        return (ok, accpetN, acceptV)
    }
}

2a:Accept

 
# 当前Proposer收到自己发起提案请求的返回
# 过滤出所以结果为ok的成功承诺
promises = promises.filter(p -> p.rst == ok)
if(promises.size <= acceptors.size/2){
    # 成功的承诺数小于等于集群acceptors数的一半
    # 则提案号自增
    n.incr
    # 重新发起提案请求
    goto <1a:Prepare>
}

if(promises.matchAll(p -> p == (ok, null, null))){
    # 所有成功的承诺都没带接受的提案号及值
    # 则什么也不做，使用当前Proposer收到（来自client）的值做为当前Proposer的提案值
}else{
    # 成功的承诺中有已接受的提案号及值
    # 则找到已接受的最大提案号对应的值做为当前Proposer的提案值
    # [核心] 后者认同前者，附议已存在的提案
    value = promises
        .orderBy(p -> p.acceptN)
        .reverse
        .get(0)
        .acceptV
}
# 发起提案，返回各Accetors对此提案的结果
# rst = 结果（ok/error）
var accepts:Set(rst) = acceptors.foreach.accept(n, value)

2b:Accepted

 
# 处理提案
# n = 收到的提案号
# value = 收到的提案值
def accept(n,value){
    if(n < maxN){
        # 收到的提案号小于当前Acceptor最大提案号
        # 返回错误
        # [核心] 不处理小于 maxN 提案号的提案
        return err
    }else{
        # 将收到的提案号及值做为当前Acceptor接受的提案号及值
        (acceptN, acceptV) = (n, value)
        # 通知learner同步信息给其它Accetpor(非关键步骤，可忽略)
        learner.accepted(n, value)
        # 返回成功
        return ok
    }
}

2b:Accepted

 
# 当前Proposer收到自己发起提案的返回
if(accepts
    .filter(a -> a.rst == ok).size <= acceptors.size/2){
    # 成功的承诺数小于等于集群acceptors数的一半
    # 则提案号自增
    n.incr
    # 重新发起提案请求
    goto <1a:Prepare>
}
# 反之，完成提案
Table 2. Basic Paxos 示例（顺序情况）
Proposer1 Proposer2 Acceptor1..3

prepare(n1)

maxN = n1
return (ok, null, null)

accept(n1, v1)

(acceptN, acceptV) = (n1, v1)
return ok

prepare(n2)

maxN = n2
return (ok, n1, v1)

accept(n2, v1)

(acceptN, acceptV) = (n2, v1)
return ok
Table 3. Basic Paxos 示例（乱序情况1）
Proposer1 Proposer2 Acceptor1..3

prepare(n1)

maxN = n1
return (ok, null, null)

prepare(n2)

maxN = n2
return (ok, null, null)

accept(n1, v1)

return err

accept(n2, v2)

(acceptN, acceptV) = (n2, v2)
return ok

# 错误重试
prepare(n3)

maxN = n3
return (ok, n2, v2)

accept(n3, v2)

(acceptN, acceptV) = (n3, v2)
return ok
Table 4. Basic Paxos 示例（乱序情况2）
Proposer1 Proposer2 Proposer3 Acceptor1..3

prepare(n1)

prepare(n2)

<from Proposer2>
maxN = n2
return (ok, null, null)

<from Proposer1>
return (err, null, null)

accept(n2, v2)

prepare(n3)

<from Proposer3>
maxN = n3
return (ok, null, null)

<from Proposer2>
return err

accept(n3, v3)

<from Proposer3>
(acceptN, acceptV) = (n3, v3)
return ok
Table 5. Basic Paxos 示例（乱序情况2）
Proposer1 Proposer2 Acceptor1 Acceptor2 Acceptor3

prepare(n1)

<from Proposer1>
maxN = n1
return (ok, null, null)

<from Proposer1>
maxN = n1
return (ok, null, null)

prepare(n2)

<from Proposer2>
maxN = n2
return (ok, null, null)

<from Proposer2>
maxN = n2
return (ok, null, null)

accept(n1, v1)

<from Proposer1>
(acceptN, acceptV) = (n1, v1)
return ok

<from Proposer1>
return err

<from Proposer2>
maxN = n2
return (ok, n1, v1)

accept(n2, v1)

<from Proposer2>
(acceptN, acceptV) = (n2, v1)
return ok

prepare(n3)

<from Proposer1>
maxN = n3
return (ok, n2, v1)

<from Proposer1>
maxN = n3
return (ok, null, null)

<from Proposer1>
maxN = n3
return (ok, null, null)

<from Proposer2>
return err

<from Proposer2>
return err

accept(n3, v1)

<from Proposer1>
(acceptN, acceptV) = (n3, v1)
return ok

<from Proposer1>
(acceptN, acceptV) = (n3, v1)
return ok

<from Proposer1>
(acceptN, acceptV) = (n3, v1)
return ok

prepare(n4)

<from Proposer2>
maxN = n4
return (ok, n3, v1)

<from Proposer2>
maxN = n4
return (ok, n3, v1)

<from Proposer2>
maxN = n4
return (ok, n3, v1)

accept(n4, v1)

<from Proposer2>
(acceptN, acceptV) = (n4, v1)
return ok

<from Proposer2>
(acceptN, acceptV) = (n4, v1)
return ok

<from Proposer2>
(acceptN, acceptV) = (n4, v1)
return ok
Multi Paxos

从上文我们可以看到Basic Paxos，算法的过程也比较复杂，确定一个值需要至少2次RPC并且可能存在活锁（即多个Proposer交替发起提案申请，见 Wikipedia Paxos 的Basic Paxos when multiple Proposers conflict章节，本文不赘述），所以一般的Paxos实现都是基于Multi Paxos，它只要约一次RPC，算法复杂度也低一些。

Basic Paxos之所以需要至少2次RPC是prepare阶段无法形成确定性取值，而其中的原因在于存在多个Proposer同时提案，所以Multi Paxos的核心思想是先为多个Proposer选举出Leader，后续所有的提案都由这个Leader发起，这样可以省略prepare阶段，直接发起accept。

Leader选举的过程类同Basic Paxos，需要至少2次RPC，Leader确定之后即只需要1次RPC。

读者可能会有疑问：为什么这叫 Multi Paxos？这是个好问题，Multi Paxos要解决的问题其实不止于减少RPC调用，Basic Paxos在多轮Prepare/Accept下只能确定一个值，而Multi Paxos则可以在降低延时的同时确定多个值并且保证其顺序，这才是Multi Paxos被广泛地工程化应用的核心原因。

关于Multi Paxos的更多介绍可参见此wiki phxpaxos 。

Tip
扩展阅读

Paxos经典论文

Wikipedia Paxos

知行学社——paxos和分布式系统

总结

本文我们通过图示及伪代码讲解了经典的 Paxos 算法实现原理，一致性算法还有很多，比如Raft、Zab，不同算法间实现的逻辑有很多的共通性，可以举一反三，如有必要笔者也会持续更新相关的内容。

FEATURED TAGS
企业架构 企业中台 云原生 领域建模 Coding 闲言碎语
FRIENDS