分布式一致性原理详解

数据一致性并不只有“存在”与“不存在”两种情况,就像可以用 0% 到 100% 之间的任意数值来代表可用性的程度一样,一致性也有一些分类。一致性模型按照强弱可以粗略地分为弱一致性模型最终一致性模型强一致性模型

  • 弱一致性模型的特点是向系统更新或者写入一个数值后,后续的读操作不一定能够读到这个最新的数值。
  • 最终一致性模型的特点是向系统更新或者写入一个数值后,后续一段时间内的读操作可能读取不到这个最新的值,但是在该时间段过后,一定能够读到这个最新的数值。
  • 强一致性模型的特点是向系统更新或者写入一个数值后,无论何时都能够读到这个最新的数值。

1 强一致性模型

将强一致性模型进一步细分,可以分为两类,分别是线性一致性 (Linearizability)顺序一致性 (Sequential Consistency)

1.1 线性一致性 (Linearizability)

线性一致性又称为原子一致性或者强一致性,这个概念是由 Maurice P. Herlihy 与 Jeannette M.Wing 在 1987 年的论文 《Linearizability: A Correctness Condition for Concurrent Objects》 中提出来的。CAP 中的 C 指的就是线性一致性。

如果要达到线性一致性,需要满足如下约束:

  1. 任何一次读操作都可以读到某个数据的最新值。
  2. 系统中所有节点内执行的事件顺序都和系统级别时钟下看到的事件顺序一致。

第一点非常容易理解,第二点则约束了两个维度下事件的执行顺序都必须是一样的。这两个维度是指单个进程内的时钟顺序和整个系统的时钟顺序,如下图所示:

线性一致性

上图有三个进程 P1、P2、P3:

  • 从 P1 进程来看,只是执行了一次写操作。
  • 从 P2 和 P3 进程来看,事件顺序都是先执行一次写操作,然后执行一次读操作。
  • 从整个系统的时钟顺序来看,先执行三次写操作,然后执行两次读操作。

所以最近一次的值是 3,读操作读到的值也必须是 3。

1.2 顺序一致性 (Sequential Consistency)

通过线性一致性的例子可以看到五个事件在时间上没有重叠,但是在实际的场景中,不同进程的事件执行的时间点很可能会有重叠,如下图所示:

线性一致性
  • 从系统级时钟的维度来看,整个事件的执行顺序应该是 write1 -> write2 -> write3 -> read2 -> read3 -> read2(其中数字代表进程标识,比如 “write1” 代表 P1 进程的写操作)。

    如果按照线性一致性的约束,则第一次 read2 读到的值应该是 a=3,因为第一次 read2 前一次的写操作是 write3。但是上图中的结果并不是 a=3,而是 a=2。这是因为 write3 操作虽然是在 read2 操作之前开始执行的,但是 write3 操作结束的时间却是在第一次 read2 操作开始之后。所以 P2 进程在执行读操作时只能读取最近一次写成功的值,也就是 a=2

  • 从 P2 进程的视角看,事件执行顺序应该是 write2 -> read2 -> write3 -> write1 -> read2(这里没有把 read3 排进去是因为 read 操作本身不会被其他进程所感知),P2 进程和系统级时钟的视角看到的事件执行顺序是完全不一样的。

这种时间点重叠,并且不满足系统级时钟的事件执行顺序的一致性称为顺序一致性

在 Maurice P.Herlihy 与 Jeannette M.Wing 提出线性一致性之前,Lamport 在 1979 年就提出了顺序一致性的概念。比如 ZooKeeper 中的 ZAB 协议就是顺序一致性的。顺序一致性的约束如下:

  1. 任何一次读操作都可以读到某个数据的最新值,这一点和线性一致性是相同的。
  2. 所有进程看到的事件顺序是合理的,达成一致即可,并不需要所有进程的事件顺序和系统级时钟下的事件顺序一致。

它放宽了对一致性的要求,并不像线性一致性一样严格。

2 最终一致性模型

将最终一致性模型进一步细分,也可以分为三类,分别是因果一致性单调一致性最终一致性

2.1 因果一致性 (Causal Consistency)

因果一致性是一种最终一致性模型,它强调在分布式系统中事件的因果关系。其约束如下:

  1. 对于具有因果关系的读/写事件,所有进程看到的事件顺序必须一致。
  2. 对于没有因果关系的读/写事件,进程可以以不同的顺序看到这些并发的事件。

这里的因果关系是指单个进程内的事件执行顺序,如下图所示:

因果一致性

在上图中,P2 进程内的两次写操作具有因果关系,必须先执行赋值 a=2,再执行 a=3。所以按照因果一致性的约束,其他几个进程也必须看到这个因果关系,也就是 P3 和 P4 进程在执行读操作时,能读到值为 2 的操作一定先于能读到值为 3 的操作。而能读到 a1 的操作无关在哪个位置,因为 P1 的写操作和 P2 的写操作没有因果关系,所以其他进程可以以不同的顺序看到这些事件的执行。

下面是一个不符合因果一致性约束的例子,如下图所示:

非因果一致性

在 P3 进程的视角中先有了 a=3,然后才有 a=2,与 P2 进程看到的因果关系不一致,所以不符合因果一致性的约束。

2.2 单调一致性 (Monotonic Consistency)

单调一致性也是一种最终一致性模型,它强调了对于特定客户端的操作,系统中的数据副本的访问顺序应该保持单调的。单调一致性可以分为单调读一致性单调写一致性

  • 单调读一致性指的是任何时刻一旦读到某个数据项在某次更新后的值,就不会再读到比这个值更旧的值。
  • 单调写一致性指的是一个进程对某一个数据项执行的写操作必须在该进程对该数据项执行任何后续写操作之前完成。

相较于因果一致性,单调一致性更聚焦于单个进程内的读/写操作顺序。

2.3 最终一致性

因果一致性和单调一致性都属于最终一致性中的一种,只是在最终一致性的基础上增加了一致性的强度,因果一致性是在最终一致性的基础上增加了因果关系的约束,单调一致性是在最终一致性的基础上增加了单进程内的约束。而没有增加其他约束的最终一致性也就是字面上的最终一致性。它只有一个约束,就是向系统写入更新或者写入一个数值,后续一段时间内的读操作可能读取不到这个最新的值,但是在该时间段过后,一定能够读到这个最新的数值

以上几个一致性模型的约束条件,由弱到强分别是:最终一致性 < 单调一致性 < 因果一致性 < 顺序一致性 < 线性一致性。

3 一致性协议与共识算法

一致性模型是理论总结,一致性协议是一致性模型的具体表现形式,而共识则是一致性协议的一种具体实现手段。

共识一致性描述的内容并不相同:

  • 共识用来描述一组进程间的协作过程,并且确定下一个操作;
  • 而一致性描述的是进程间某一时刻的状态。

共识是一致性的充分不必要条件,因为达成共识就可以达到一致性,但是达到一致性,并不一定需要达成共识。

传统分布式系统领域的 Paxos 就是一种共识算法,下面我们将以 Paxos 为切入点介绍一致性协议。

3.1 Paxos 算法

Paxos 是由 Leslie Lamport 在 1990 年发表的论文 《The Part-Time Parliament》 中提出的。在 2001 年,Leslie Lamport 又以计算机领域的描述方式重新对 Paxos 算法进行了阐述,并发表了 《Paxos Made Simple》

Paxos 是一种基于消息传递且具有高度容错性的共识算法。在分布式系统中,通信是一个非常重要的环节,因为在分布式系统中,进程的崩溃、重启、通信消息丢失和延迟等情况是不可避免的。Paxos 算法的目标是确保在出现这些异常情况时,分布式系统的决议一致性不会被破坏。各个进程可以提出各种请求,但最终只有一个请求会被选中,并且一旦某个请求被选中,其他进程就能够获得该请求所带来的变化。

在 Paxos 算法中,有三类角色:

  • Acceptor (决策者):负责决策最终采用哪个提议。
  • Proposer (提议者): 该角色负责向决策者提交提议。
  • Learner (最终决策执行者): 该角色负责执行最终选定的提议。

整个过程从提议的提出到提议的选定,再到提议的执行,可以大致分为两个阶段。第一个阶段是决策者选出最终的提议,第二个阶段是最终决策执行者如何获取并执行该提议。

  • 第一个阶段其实是 Proposer 与 Acceptor 之间的交互,过程如下:
    1. Proposer 选择一个提议,该提议编号记为 M,然后向 Acceptor 的某个超过半数的子集成员发送编号为 M 的准备请求。
    2. 如果一个 Acceptor 收到一个编号为 M 的准备请求,并且该提议的编号 M 大于 Acceptor 已经响应的所有提议的编号,那么它会把已经响应的提议的最大编号返回给这个 Proposer, 并且承诺不会再批准任何小于编号 M 的提案。如果 Proposer 没有得到半数以上 Acceptor 的响应则将编号 +1 后继续发起请求。
      • 举个例子,一个 Acceptor a 已经响应了所有提议(编号为 1247)的提案。那么该 Acceptor 收到一个编号为 8 的提议后,会将编号为 7 的提议反馈给这个提出编号为 8 的 Proposer。
    3. 如果 Proposer 收到半数以上的 Acceptor 对于 M 编号的提议的反馈,则再次发送一个 {M,V} 的提议给 Acceptor (前面都是准备阶段,只发送编号,类似于检测),这个 V 就是反馈的那个最大的提案值,例如上述例子中的 7。如果响应中不包含任意提议,那么它就是任意值。
    4. 如果 Acceptor 收到这个 {M,V} 的提案请求,只要该 Acceptor 尚未对编号大于 M 的准请求做出响应,则通过该提议。
  • 产生最终的提议后,下一阶段就是让 Learner 执行该提议,该阶段是 Acceptor 与 Learner 之间的交互。Learner 在执行提议之前先要接收最终的提议,Learner 接收最终提议也有不同的方案,大致有以下三种:
    • 方案一: Acceptor 获得一个被选定的提案的前提是该提案已经被半数以上的 Acceptor 批准。因此,最简单的做法就是一旦 Acceptor 批准了一个提议,就将该提议发送给所有的 Learner。Learner 虽然可以尽快获取被选定的提案,但是需要每个 Acceptor 和所有的 Learner 逐个进行次通信。假设有 M 个 Acceptor 和 N 个 Learner,则通信次数就是 M x N,通信次数过多。
    • 方案二:让所有的 Acceptor 将它们对提案的批准情况统一发送给一个特定的 Learner,类似于 Learner 的领导者,当这个领导者获得提案后,它会负责去通知其他 Learner。这种方案的通信次数是 M + N - 1,虽然通信次数大大减少,但主领导者可能出现单点故障。
    • 方案三: 可以将方案二中的领导者的范围扩大,Acceptor 可以将批准的提案发送给一个 Learner 领导者集合,该集合中的每一个领导者都可以在一个提案被选定后通知其他 Learner,这个领导者集合中的领导者个数越多,可靠性越好,但是通信的复杂度越高。

上述算法是最基础的 Paxos 算法,也称为 Basic Paxos,在后续又衍生出了 Multi Paxos、FastPaxos 等算法,都是基于 Basic Paxos 的变种算法。

3.2 Raft 算法

由于 Paxos 算法是一套偏向理论的算法,难以理解且难以实现,斯坦福大学的两位教授 Diego Ongaro 和 John Ousterhout 决定设计一种更加简单、容易理解的共识算法,那就是 Raft 算法。它在论文 In search of an Understandable Consensus Algorithm 中最先被提出。

Raft 是一种用来管理复制状态机的算法,复制状态机通常使用复制日志实现,Raft 也不例外。每个服务器存储一个包含一系列命令的日志,其状态机按顺序执行日志中的命令。每个日志中的命令都相同并且顺序也一样,因此只要处理相同的命令序列,就能得到相同的状态和相同的输出序列。这也是 Raft 实现一致性的核心思想。

Raft 算法有三种角色:

  • Leader (领袖): 该角色的职责是接收和处理一切请求,并把同步数据给 Follower。
  • Follower (群众):该角色的职责是转发请求给 Leader,接收 Leader 同步过来的数据,以及参与投票。
  • Candidate (候选人): 该角色的职责是竟选 Leader。

这三种角色分别代表服务节点的三种状态,这三种状态之间可以互相转化。引用论文 《In Search of an Understandable Consensus Algorithm》 的身份转换图如下:

raft

从上图中可以看到集群最初的状态:所有服务器都是 Follower,当这些服务启动完成后,由于起初没有 Leader,所以 Follower 一定不会收到 Leader 的心跳消息。经过一段时间后发生选举,此时 Follower 先增加自己的当前任期号并且转换到 Candidate 身份,然后投票给自已并且并行地向集群中的其他服务器节点发送竞选请求,即图中的 “times out, starts election”。当满足以下三个条件中的一个时,Candidate 身份会发生转变:

  • 集群内超过半数的服务节点同意该 Candidate 成为 Leader,也就是超过半数的节点响应了竞选请求,此时 Candidate 会变成 Leader。即图中的 “receives votes from majority of servers”
  • 集群内其他的某个服务器节点已经成为 Leader,此时 Candidate 会变回 Follower。因为当 Leader 产生后,它会向其他的服务器节点发送心跳消息来确定自己的地位并阻止新的选举。即图中的 “discovers current leader or new term”
  • 如果有多个 Follower 同时成为 Candidate,那么选票可能会被瓜分,以至于没有 Candidate 赢得过半的投票,也就是选举超时后还是没有选出 Leader ,会通过增加当前任期号来开始一轮新的选举,但是这种情况有可能无限重复,即图中的 “times out,new election”
    • 为了防止这种情况发生,Raft 算法使用随机选举超时时间的方法来确保很少发生选票瓜分的情况。也就是每个 Candidate 在开始一次选举的时候重置一个随机的选举超时时间,然后一直等待直到选举超时。该 Candidate 会增加当前的任期号,重新发起竞选请求,此时其他 Candidate 可能还在等待中,那么其他服务节点认为该超时的 Candidate 的任期号最大,所以它会被选为 Leader。

上图中还有一种从 Leader 直接变成 Follower 的情况,这种情况多数出现在 Leader 发生了网络分区的时候。当 Leader 发生网络分区后恢复时,新的 Leader 已经产生,它会接收新 Leader 的心跳请求,发现新的 Leader 的任期号比自己的大,它会自动变成 Follower。而旧的 Leader 如果发送心跳请求给其他服务器节点时,Candidate 和 Follower 都会比对任期号,如果任期号小于自己的任期号,则直接拒绝此次心跳请求。

分布式一致性问题一直都是分布式架构下必须考虑的问题,注册中心需要在可用性和一致性之间做权衡和选择。


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容