第09课:分布式微服务架构体系详解——共识问题

前言

在分布式架构体系中,一致性和共识是分不开的概念,一致性也是我们解决很多分布式问题的关键,比如,通过一致性模型可以实现数据集群的数据复制;通过基于阻塞的 2PC 协议可以实现分布式的原子性提交,保证事务数据的一致。

我们在第 07 课:分布式一致性中介绍了分布式一致性的一些理论,并且引出了分布式共识(Consensus)的话题。共识就是让分布式系统中所有节点都对一些值达成共识。在分布式系统中,解决共识问题可以帮助我们处理很多分布式问题,包括第08课中介绍的原子提交协议,以及本课将介绍的全序广播。

本课主要介绍具有容错特性的共识算法——Quorum、Paxos,以及这些算法在实践应用领域中的介绍。本篇课程学完之后,相信读者们对于分布式的技术体系会有一个更加深刻和整体的认识。分布式系统的知识体系还有很多其他方面,对于需要在架构上深耕的读者可以阅读更多的论文,每篇文章下面也会有一些相关文献的链接,可以作为延伸阅读。

分布式系统的共识问题

在考虑搭建一套分布式系统的时候,在一开始我们便要开始考虑如何解决共识问题了。尽管 FLP 不可能理论告诉我们,在基于异步模型的系统中,即使有一个节点 Crash 了,也没有办法解决共识问题。但我们还是需要一个分布式的协议或者算法来处理一致性或者说是原子提交。

在第 08 课:分布式事务实践 中我们介绍了关于原子提交协议中的 2PC、3PC。除了分布式事务,这些一致性算法还可以用于第 03 课:数据复制中介绍的,集群各个节点的数据复制。不过,2PC、3PC 都是没有容错特性的,比如 2PC 存在 Commit 阶段协调者单点问题,3PC 中如果存在网络延迟高,参与者对延时进行误判时,也无法保证原子提交。

本文将介绍两个典型的一致性算法——具有容错性的共识算法,Quorum 和 Paxos(Raft 算法跟 Paxos 一样,也是可以实现线性一致性的,但 Paxos 更加难理解,Raft 相对来说更容易实现)。本文会从算法理论的证明讲起,结合基于这些算法实现的分布式技术,帮助大家理解算法的应用场景。在实践分布式系统中,我们基本不需要去实现这一套算法,但理解共识算法可以更好地对分布式技术有个体系化的认知。

共识算法

分布式的应用系统中,大多是基于异步的模型,并且在 CAP 理论介绍中讲到了,在大型分布式架构中,几乎无法忽视 P(分区容错性)。而在分布式系统中,不仅仅存在分区容错一种网络分区的错误,还有可能是节点 Crash,各种天灾人祸都可能导致网线断了,机房发生地震等。

下面就来看一些具有容错特性的共识算法。这些共识算法,有的是支持线性一致性如 Paxos、Raft;有的是支持最终一致性如 Quorum。在支持容错的一致性算法(共识算法)中,Paxos 是比较难理解和实现的,很多分布式技术实践一般都会对 Paxos 的算法进行一定的调整。但 Paxos 还是经典的传统的一致性算法。相较 Paxos、Raft 算法更容易理解和实现。Raft 算法发表于 2013 年,目前已经有很多语言的实现并广泛被应用,比如 Etcd,已经被 CoreOS、Kubernetes 和 Cloudfoundry 等知名的项目用于处理服务发现。Quorum 和 Paxos、Raft 的应用场景不同,下面会详细介绍下 Quorum 以及 Paxos 算法的实现细节。

共识的容错性

共识,从字面理解也即达成一致,这个一致也不一定是所有决策都是一样的,也可能是大多数决策是一样的,而达成了一致的决策。这个决策,在分布式领域,可以用来做领导(Leader)节点选举,也可以用来处理数据复制的数据一致性。

我们再回顾一下一致性那一课中,共识的三个衡量标准:

  • Termination(终止性):非失败进程最终需要决定一个值。
  • Agreement(一致性):所有的进程决定的值必须是同一个值。
  • Validity(有效性):这个被决定的值必须是被某些进程提出的。
    2PC 是一个一致性算法,但是不满足共识的 Termination 特性(如果协调者挂了,那么其他可以正常运行的节点也只能阻塞住)。所以,Termination 决定了共识算法必须要得出结论,即使一部分节点 Crash 了,其他节点也要能做出决定。比如第 08 课中的举例,4 个人在考虑吃什么,即使一个人说不出话来,另外 3 个也不能互相望着没有结论。当然,在分布式系统中的容错需要有个限度,如果所有节点都 Crash 了,也就不存在还能做出决定了。所以对于失败节点的数量一般是有一个界定。在有 N 个 Node 的系统,只要有 (N/2 + 1) 个节点还是可用的、且是可连接状态,就认为整个系统是可用的,也即这个系统具有容错性。共识算法,为了保证让大多数节点达成一致,一般需要奇数个节点(3,5,7...)。3 个 Node 可以容忍 1 个 Node 挂掉,5 个 Node 允许 2 个挂掉。

目前大多数共识算法都基于没有拜占庭将军问题的假设,拜占庭问题主要是考虑系统中有节点不遵循算法协议,比如会有节点发送一些扰乱秩序的消息给其他节点,将破坏共识达成。本文将不再延展拜占庭问题的思路,现在拜占庭容错(BFT-Byzantine Fault Tolerance)又因为区块链技术火了起来,感兴趣的读者可以去看一些经典的 Paper。在学习这些共识算法时,更多可以关注它们的实现思想和共同点。

Quorum

算法介绍

Quorum 是一种支持容错的共识算法。在分布式系统中,可以用来做分布式事务的原子提交协议(最终一致性)以及数据复制。下面介绍下 Quorum 在分布式数据复制中的算法实现。

在具有数据复制的数据存储集群中,一份数据会需要同步给集群中的所有节点。通过 Quorum,可以保证分布式环境下的数据副本的读写一致。在 Quorum 算法中,每一份数据副本都是一个 Vote(投票)。假设集群有 N 个节点,如果有一个写操作,在 W 个副本上写入成功,记作 Vw。对于读操作而言,读操作从 R 个节点成功读取数据副本,记作 Vr。则读的副本和写的副本数需要满足以下两个规则:

  • Vr + Vw > N 保证写操作和读操作会覆盖一部分节点,也即 Write 和 Read 有重叠部分。最少的情况,重叠一个 Node 即可,则此时: Vr + Vw = N +1。
  • Vw > N/2 保证写操作要覆盖至少一半以上的节点。
    举个直观的例子,假设我们有 5 个 Node,一个 Client 写入 3(5/2 +1) 个 Node,则写入成功了;在读取的时候,需要从至少 = 3 (3+3>5)个节点中读取数据,如下图所示:

1-36

在写入操作前,初始的所有 Node 的数据都是 a=0。写入 a=1 同步给3各节点时,则写入成功。写入后,读数据从随机的三个 Node B、C、D 读到的是 (D:0,B:1,C:1)。结果集中包含 0,也包含 1,为了确定 1 是新的副本,而 0 是旧的,我们需要一个解决数据版本冲突的机制。如,可以通过 LWW(last-write-win),或者数据版本号(Vector clock)来决定哪个是最新的数据,或者不直接解决而使用继续读取,直到读到 3 个一致的数据副本,所以最差的情况可能需要从全部 5 个节点读取数据。当然,存储服务本身也可以不解决,而将数据返回给 Client 去决定采用哪个数据。

Quorum 在 Dynamo 中的应用

通过前文的介绍,可能很多读者觉得 Quorum 存在明显的读写性能问题,如果是节点 Crash 了,还会导致数据不一致。但 Quorum 机制在处理 NoSQL 的数据复制的场景下被广泛应用的。比如 Dynamo、Cassandra 都是用 Quorum 机制来处理大数据集群,包括多数据中心的数据复制。他们在冲突检测,处理方面的实现细节略不同(Cassandra 通过 LWW "last-write-win" 机制来减少每一轮的 Read 数),本文以 Dynamo 为例介绍 Quorum 机制的应用。Cassandra 的实现细节可以阅读 Cassandra DataDistributeReplication。

Quorum 在 Dynamo 的应用主要是处理集群的数据复制,Dynamo 的 Quorum 算法不是严格的大多数投票选举达成一致的算法,所以 Dynamo 是一个提供弱一致性但是高可用的存储 Key-Value 结构数据的 NoSQL 系统。LinkedIn 的 Voldemort 以及 Facebook 的 Cassandra 也参考了 Dynamo 的分布式架构模型。在 Quorum 算法中,比较重要的一个环节就是什么时候处理以及怎样处理更新冲突,Dynamo 通过增加一个节点角色——协调者(Coordinator),以及使用向量时钟解决数据副本的写冲突。下面看下 Dynamo 的数据处理实现(以下描述的 W、R 即是上文介绍的 Quorum 算法中至少需要的 W、R 值):

  • 写入数据:使用一致性哈希算法决定 key 存储到哪个 node 节点。如果存在写入数据冲突,则使用 Vector Clock 来解决,保证写入数据的因果关系。关于 Vector Clock 的实现,忘记的同学可以复习下第 01 课:逻辑时钟的内容。
  • 数据复制:使用 Quorum 算法,将数据复制给各个节点。但是为了降低响应延迟,其 Quorum 的配置,在应用中一般配置成,W + R < N。对于写请求,写请求会先发送给一个协调者,然后协调者通过 Vector Clock 在本地解决写数据冲突,然后将最新的数据副本复制到 N 个节点。在收到至少 W-1 个节点的成功响应后便返回给 Client 写入请求成功。
  • 读取数据:读取时也是通过协调者将读请求发送给 N 个节点,然后等待 R 个节点返回数据,可能导致读取多个不同的数据副本,协调者会将这些数据进行数据版本合并,将决定的最新版本的数据,回写到返回旧版本数据的 Node。
    Dynamo 处理数据过程简单示意如下图(红色线代表写请求,蓝色线代表读请求):

2-26
示例中,一共有 6 个节点,则按照 Quorum 标准,NWR = 6,4,3。

先看一下写请求。首先根据一致性哈希算法,put(Sx)请求 hash 到了 NodeA 和 NodeF 之间的范围,然后从环中的位置顺序寻找到 NodeF,则 NodeF 作为本次 put 请求的协调者。NodeF 本地通过向量时钟解决写入数据的冲突,然后将最新版本的数据写入本地,同时将写请求发送给所有节点(本图没有全部画出来所有请求的 line)。在收到 2 个节点(NodeC,NodeE)返回 OK 后,判断本次写入请求处理成功,并返回给 Client。本次写请求结束,6 个节点中有 3 个节点保存了最新的数据副本(其他节点因为网络延迟可能本地还是旧版本的数据)。

ClientB 发出读请求 get(Sx),通过一个负载均衡器,请求落到了一个节点 NodeD 作为本次读请求的协调者。协调者将读请求发送给全部 6 个节点(也没有全部画出来),在等待有 2 个节点(NodeE,NodeB)成功返回数据后,本地进行数据版本的合并,然后决定出来 [Sx:3] value=Sv 是最新的数据副本。NodeD 将这个数据更新到本地,然后将新数据副本回写到刚才返回旧版本数据([Sx:1] v=Sz)的 NodeB。本次读请求结束,R=3。所以 Dynamo 中实际的 NWR = 6,3,3。

Dynamo 目前在亚马逊的应用场景是存储“购物车”数据,所以 Dynamo 保证了集群节点一直“可写入”,Dynamo 认为让用户一直可以加入购物车、删除购物车的操作更重要。其核心目标是高可用,也允许节点短暂的不可用 (node down),在节点恢复后,通过同步复制,保证失败的节点追赶上从复制失败以后更新的数据。所以,我们也便知道,为什么 Dynamo 不是大多数投票,因为其 W 和 R 节点不保证重叠。Dynamo 更多的是从性能的角度考虑。

正常来说,写 W 个节点,读 R 个节点,一共 N 个节点。写的多会增加写的响应时间,但是加强了数据持久化的可靠性。读更多的节点也会增加读到最新版本的数据的可靠性。以下列举一些其他使用 Quorum 来实现数据复制的系统的 NWR 值的默认配置策略:

  • Basho Riak:N = 3、R = 2、W = 2
  • Linkedin Voldemort:N = 2 or 3、R = 1、W = 1
  • Apache Cassandra:N = 3、R = 1、W = 1

Paxos

算法介绍

在第07课:分布式一致性中,我们提到了 Paxos 是一个异步模型的共识算法。Paxos 是由 Leslie Lamport 在 1990 年提出的,其算法在工程实践方面复杂度很高,很多实践方式是基于 Paxos 进行一定的调整和改进。

通过 FLP 不可能理论可以知道,异步的系统模型没法达到严格的共识,但是 Paxos 已经是尽最大可能达到共识的大部分条件。Paxos 在网络延时有限的情况可以做到共识,否则可能无法满足终止性条件(对于 Paxos 活锁问题将不在本文详细展开)。

在 Paxos 中,多个节点决定出来的值,叫做“提案(Proposal)”,最后要得出来的共识的值(Value)必须要是提案中的某个值。Paxos 算法将所有的 Node 都区分为不同的角色:

  • Proposer 提案者:提出提案(Proposal),包括提案的编号(ID,是一个 Sequence Number,ID 是唯一的,随着每一轮算法过程递增)和提议的值(Value),并且统计被大多数 Acceptor 接受的值。

  • Acceptor 决策者:收到提案后可以接受(Accept)提案,投票过程中允许少数 Acceptor 节点失败。

  • Learner 最终决策学习者:负责接受被最终批准(Chosen)出来的提案。
    Paxos 算法过程主要分为两个阶段 Prepare 和 Accept 阶段,这两个阶段需要满足如下约束:

  • Prepare 阶段:一个 Acceptor 必须接受它收到的第一个提案。

  • Accept 阶段:如果某个 value 为 v 的提案被选定了,那么每个编号更高的被 Acceptor 接受的提案的 value 必须也是 v。

  • Accept 阶段:如果某个 value 为 v 的提案被选定了,那么之后任何 Proposer 提出的编号更高的提案的 value 必须也是 v。
    对于上述约束条件,需要结合过程看。为了能更好理解晦涩的 Paxos 算法,下面以决议“今晚吃什么”为例描述下两个阶段过程。

一. Prepare 阶段(准备阶段)

Proposer 向超过半数(n/2+1)Acceptor 发起 prepare 消息,消息包含提案编号 + 提议值 [Nx,Vx]。

  • 当 Acceptor 接收到 prepare 请求时,如果这个 Acceptor 之前没有接受过任何提案,则必须接受收到的第一个提案 [Nx,Vx],回复 OK;否则对比本次收到消息的提案编号以及上一次回复过的 prepare 请求的编号(Ny)大小。如果 Ny > Nx 则拒绝本提案 Nx;
  • 如果本次提案编号 Nx > Ny,则回复给提出本提案的 Proposer,曾经接受过的最大编号的提案 [Ny,Vy]。同时该 Acceptor 承诺不再接受任何编号小于 Nx 的提案。
    Prepare 阶段的简单示意如下图。proposerA 提出的提案编号为 1 的 value=日料 的提案。因为 Acceptor 必须接受收到的第一个提案。所以 X,Y 节点必须接受收到的第一个消息,也即 [1,日料] 。而 Z 接受它收到的第一个消息 [2,烧烤],并且对接受的消息回复 OK。过了一段时间之后,X,Y 又收到了 proposerB 的提案编号为 2 的,value = 烧烤。因为 2>1 所以,X,Y 回复给 proposerB 他们之前已经接受了 [1,日料]。又过了一段时间 Z 收到了第二个消息 [1,日料],而因为已经接受并且回复过编号更大的 [2,烧烤],所以 Z 忽略了这个消息。

3-21

二.Accept 阶段(决议阶段)

Proposer 收到半数以上的 Acceptor 对其发出的 prepare[Nx,Vx] 的回复消息是“OK”,说明 Acceptor 大多接受了该 Proposer 提出的提案,则 Proposer 发送一个 accept 请求信息 [Nx,Vx] 给半数以上的 Acceptor。如果消息不是“OK”而是一个被 Acceptor 接受过的最大提案的 Value 假设是 [Nz,Vz],则 Proposer 发送 accept 请求信息 [Nx,Vz] 给所有 Acceptor。

如果回复数量不是多数,则提案 [Nx,Vx] 未被接受,Proposer 增加序列号为 Nx+1,然后再重新发送 prepare 请求,回到阶段 1 重新开始。

如果 Acceptor 收到一个针对编号为 Nx 的提案的 accept 请求,只要该 Acceptor 没有对编号大于 Nx 的 Prepare 请求做出过响应,它就接受该提案。

提案被选中(chosen)后 Learner 就可以学习该提案。

Accept 阶段的简单示意如下图。

4-14

图中没有画出来 proposerA,因为它不重要了,proposerA 确实收到了半数以上的 Acceptor 回复的 OK,因为对 X,Y 曾经来说,[1,日料] 是第一个提案,然后 proposerA 继续发送了 accept[1,日料] 的请求。在收到 proposerA 发出的 accept 请求后,X,Y 因为在 Prepare 阶段中承诺了只接受编号大于等于 2 的提案,所以 X,Y 直接忽略了这个 proposerA 发送过来的 accept[1,日料] 请求。

过了一段时间,也即图中画出来的,X,Y,Z 都分别收到了 proposerB 发送来的 accept [2,日料]。为什么是日料?因为那个约束条件,对于 proposerB 来说,它收到的 半数以上 的消息并不是 "OK"(除了 Z),而是 X,Y 回复的“之前有个人提议了 [1,日料],并且我接受日料,但是你编号大,我不拒绝你的编号”。所以 proposerB 在 Accept 阶段,发送的 accept 请求必须是 value=日料。因为收到了多数的回复,所以编号还是带上自己原来的编号,请求就变成了 accept [2,日料]。最终,被大多数 Acceptor 决议出来之后的值,[日料],被 Leaner 接受。

Paxos 对于全序广播的实践

在分布式系统中,进程的处理有快有慢,消息的传递也存在延时,因此系统中的进程没有办法根据消息的到达的顺序去确定当前的提案进展。消息传递的延迟,节点处理的快慢,没有一个全局的顺序来决定。

共识算法一般不仅可以用来对单个值达成一致,还可以对序列性的值达成共识,也即我们前面讲到过的顺序一致性。全序广播即是需要消息以同样的顺序确切传递一次给各个 Node。通过共识算法来实现的话,可以通过进行多轮的共识。每一轮共识都是由 Node propose(提议)即将需要发送的消息,然后决议出下一个需要发送的消息,以此产生一个全序(Total Order)。所以全序广播就可以通过重复的多轮共识算法实现。目前基于 Multi-Paxos 可以实现全序广播,这里不再展开实现细节。

通过 Paxos 还可以实现多副本一致性、分布式锁。目前比较受社区广泛应用的 Zookeeper 就是基于 ZAB(核心算法基于 Paxos)实现了全序广播协议,同时也可以作为分布式锁,Zookeeper 还可以作为一致性的 key-Value 存储。Zookeeper 也被用于做服务发现,比如 Dubbo、Kafka 的服务注册中心都基于 Zookeeper。

共识的限制

虽然共识算法可以解决分布式的一致性的问题,并且具有容错特性,但是也存在一些限制,比如,使用共识算法的系统需要更多的 Node,至少 3 个,才可以允许 1 个节点失败。共识算法也依赖故障检测机制,系统需要知道消息失败的原因是 timeout 或者是节点失败。在网络延迟很高的时候,可能导致认为选举出来的 leader 不可用,但实际 leader 节点本身在正常运行,这会导致其他节点进行频繁的新一轮的 leader 选举,降低集群的吞吐量,所以共识是对网络延迟敏感的。

共识算法也不是万能的,比如数据存储服务的多数据中心,(多主)模型就不需要共识算法来处理写冲突。毕竟也不是所有场景都需要共识算法来保证线性一致性。在数据复制的领域很少使用 Paxos、Raft 类似的可以提供线性一致性保证的共识算法,大多数情况更倾向于性能而使用简单的异步复制加上写入冲突解决。不过数据存储服务的集群,也需要选举 Master(Leader),选举方式可以使用共识算法来实现,以应对故障转移。如果是单主复制的集群,有些 DB 提供了自动的 leader 选举(比如 MongoDB 基于 Raft 算法实现了 Leader 选举),在主库挂了的时候,可以快速重新选出新的主库。

小结

本文介绍了分布式系统一致性解决方案的另外一个方向——具有容错的共识算法,其中详细介绍了 Quorum 以及 Paxos。Quorum 提供了弱一致性,一般用于做 NoSQL 系统的数据复制。Paxos 跟 Raft 都是提供线性一致性的共识算法,可以用来实现分布式锁、服务发现、一致性 KV 存储等。这些共识算法整体的套路都是基于多数节点进行“选举”或者“投票”,然后从若干节点的接受的“投票”中进行决议,最终选出一个可以作为共识的值。

关于共识算法,还有很多方面,从论证到延展的实现,可以值得更深入去了解。算法只是一个基础思路,在实践中会有不同的实现方式和考量。比如 Dynamo 实现的就是非大多数的 Quorum,Zookeeper 也基于 Paxos 改进出了 ZAB 算法。Raft 算法相较 Paxos 来说在实践方面会更有优势,而且更容易理解。至此,分布式的核心问题之一——一致性,已经从概况上介绍得差不多了。一般在实践中,我们是不需要来实现一套共识算法的,而是直接使用 Zookeeper、Etcd 等技术。下一课,会对于实施分布式微服务架构时,技术选型的一些思考方面以及基本元素做一些总结。Github 上的示例代码 也会再次更新。

资料
Distributed Systems、Failures and Consensus
Dynamo: A flawed architecture
Cassandra DataDistributeReplication
PBS-How eventual is eventual consistency
Distributed systems for fun and profit —— Replication
论文资料
Google BigTable
Dynamo: Amazon’s Highly Available Key-value Store
Cassandra - A Decentralized Structured Storage System
Serving Large-scale Batch Computed Data with Project Voldemort

(全文完)

(转载本站文章请注明作者和出处 第09课:分布式微服务架构体系详解——共识问题