简单理解Paxos算法(译)

本文翻译自Quora上的一个回答

我认为在了解Paxos前,可以先谈谈其他解决共识问题的方法,在这个基础上再理解Paxos会简单些。

结婚誓言是一种达成共识的直观方式。

  • “你愿意(若干省略)?”“我愿意!”“我愿意!”
  • “现在我宣布你们(若干省略)”

两阶段提交

现在假设这场婚姻不是发生在两个人之间,而是一个男人和多个女人之间。这个男人要么娶所有人,要么一个也不能娶。那么,结婚誓言也要相应地改成下面的样子:

  • “你愿意(若干省略)?”“我愿意!”“我愿意!”“我愿意!”......
  • “现在我宣布你们(若干省略)”

如果其中一个女人没有回应“我愿意!”,那么婚礼将无法进行。

计算机科学家称之为两阶段提交。

两阶段提交(2PC)过程如下:

  1. 表决阶段。一个协调者向所有节点发布一个值并且收集它们的返回(接受或者不接受)。在我们的场景中,一个事务协调者询问所有的资源管理器RM(数据库服务器实例)是否可以提交一个事务,RM回答是或者不是。
  2. 提交阶段。如果所有人都同意,协调者将告诉所有节点这个值被确定下来了;如果有哪怕一个节点不同意,协调者将告诉所有节点这个值没有被确定下来。在我们的场景中,协调者要求RM提交事务或者终止事务。

注意表决仅仅针对本次提出的值,节点可以回应是或者不是,而不能提出一个替代值。如果一个节点想要提出一个值,它应该开始自己的2PC。显然,这个算法是管用的,一个节点提出的值要由所有节点同意;同时,这个算法的效率较低下,对于一个拥有N个节点的集群,完成共识需要传输3N条信息。

如果某个节点挂掉了呢?比如,在阶段1中,协调者向部分节点(不是全部节点)发送提议后挂掉。

  • 现在部分节点开始第二阶段,而其他的节点还不知道。那些开始第二阶段的节点将会阻塞。
  • 在我们的场景中,表决过的RM可能不得不锁住一些资源,并且不能启用超时机制,因为协调者可能会恢复,然后继续第二阶段。

在第二阶段,如果协调者向部分节点发送提交的消息后挂掉,类似的问题一样会存在。通过另外一个协调者在监测到timeout时接管可以解决部分问题;这个节点和其他的节点保持通信来发现其他节点的表决(需要节点持久化表决结果)从而结束事务。但是这个流程也有可能发生失败从而导致事务可能无法恢复。结语:在发生节点失败的情况下2PC并不可靠。

三阶段提交

2PC的关键问题在于,当协调者挂掉时,没有其他的角色能够完成协议。这可以通过添加一个额外的步骤来完成:

  1. 第一阶段。和2PC一样,协调者向所有节点提出一个值。
  2. 第二阶段。如果在第一阶段所有节点返回“是”,协调者发送一个“准备提交”的信息,让节点执行可以撤销但是无法回复的操作。每个节点向协调者确认已经收到“准备提交”的信息。
  3. 第三阶段。和2PC的阶段一样,如果协调者接收到所有节点的确认,那么向所有节点发送第一步协调的值,让节点提交。如果协调者没有接到所有节点的确认,那么协调者取消本次事物。

假如协调者在上面的任何一个步骤挂掉,其他的任意参与者都可以接管这个角色,查询其他节点的状态。

  • 如果有任意RM向新协调者报告没有收到“准备提交”信息,新的协调者会知道没有节点提交了该事务。新的协调者可以取消这个事物或者重新执行一遍流程。
  • 如果已经提交了事务的RM挂掉,我们会知道其他的RM都已经收到并且确认了“准备提交”信息,不然协调者不会进行到提交阶段。所以协调者可以从最后得到阶段开始。

从上面可以看出,3PC可以很好地处理节点失败的情况。代价是多了一个步骤,导致了系统更高的延迟。

在发生网络分区的情况下,3PC也处理的不够好。假设所有接收到“准备提交”的RM都在分区1,其他的RM在分区2。这个会导致每个分区都会选举出各自的恢复节点,恢复节点要么提交事务,要么取消事务。万一网络分区消失,系统就会处于不一致的状态。

Paxos

首先问一个问题,有比3PC更好的算法吗?3PC面临的唯一问题是网络分区,对吧?要想回答这个问题,让我们假设网络分区是唯一的问题(实际并不是,后面会提到)。由网络分区导致的一致性问题值得解决吗?

首先,随着云计算的兴起,为了服务的可扩展性,可能会将服务部署在不同的大陆上;这种情况下,的确需要一个容忍网络分区的算法。

第二,网络分区并不是3PC面临的唯一问题。处理节点临时故障,最常见的情况是故障-恢复-继续上次执行。这种fail-recover模式也可以用来描述一个异步的网络模型,在这个模型中,无法规定节点用于响应消息的时间上限,因为永远不能假定一个节点已经挂了--它们可能会很慢,或者网络可能会很慢。不能对这个模型采用超时机制。

3PC能处理fail-stop,但不能处理fail-recover。不幸的是,现实情况需要处理fail-recover,因此,我们需要一个更通用的方案。Paxos就是这样的方案。

工作过程

Paxos的工作过程和2PC很像:

  • 选择一个节点成为leader/proposer。
  • leader选择一个值,发送到所有的节点(Paxos中称之为acceptor),这个消息被称为“接受请求”消息。acceptor可以回应接受或拒绝。
  • 一旦节点中的大多数回应接受,共识就能达成,协调者将“提交”消息发送到所有节点。

和2PC不同的关键在于,2PC需要所有节点同意,Paxos只需要大多数节点同意。这个想法很有意思,因为在两个不同的大多数节点集合中,至少会有一个节点同时在这两个集合中。这就可以保证,如果大多数节点都同意某个值,随后任何想做出提议的节点都能从其他节点发现这个值并同意。这意味着,即使一半的急诶单无法回复,Paxos算法也能进行下去。

当然,leader本身可能也会挂掉。为此,Paxos不会在给定的时间点授予当个节点leader职责。算法允许任意节点成为leader,并且协调事务。这自然意味着在给定的时间点,可能存在多个认为自己是leader的节点。在这种情况下,两个leader也许会提出不同的值。那么,如何在这种情况下达到共识呢?Paxos为此设计了两种机制:

  • 为leader分配顺序。这样每个节点就能区分现有的leader和从失败中恢复过来的leader,从而防止旧的leader阻碍共识的达成。
  • 对leader提出的值进行限制。一旦在某个值上达成了共识,Paxos强迫后面的leader也选择这个值来保证共识的延续。让acceptor发送其最近确认的值和发送该值leader的序列号,来实现这一点。新的leader可以选择一个从acceptor接收的值;如果没有值被发送,leader可以选择自己提出的值。

协议过程

准备阶段

  • 一个节点选择成为leader,选择一个序列号x和值v来创建一个提议P1(x, v)。leader将这个提议发送给acceptor,等待大多数节点的返回。
  • acceptor在收到提议P1(x, v)后,判断:
    • 比较x和之间和之前接受的最高序列号的提议,比如P2(y,v2)
    • 如果x<y,回复拒绝和y值
    • 如果x>y,回复同意和P2(y, v2)
    • 如果提议是该acceptor要接受的第一个提议,回复“同意”,承诺leader该acceptor未来不会接受小于x的请求。
    • 如果该acceptor之前有接受过提议:

接受阶段

  • 如果大多数的acceptor回复“拒绝”或者没有回复,leader取消本次提议。
  • 如果大多数的acceptor回复“同意”,leader也能知道acceptor已经接受的提议。leader从这些值中任选一个值(如果没有值被接受,选择自己的值),发送“接受请求”消息,带着提议的序列号和值(x, v)。
  • 当acceptor收到“接受请求”消息,如果满足下面的两个条件,就发送“接受”,否则返回“拒绝”。
    • v和之前接受的某个值相同
    • x是该acceptor所接受提议中序列号的最大值
  • 如果leader没有从大多数节点中收到“接受”消息,leader取消这次提议然后重新开始;如果leader从大多数节点中收到了“接受”消息,本次协商就结束了。作为优化,leader可以发送“提交”消息给其他的节点。

Paxos失败处理

在Paxos算法中,如果我们指定集群中同一时间只能有一个leader,并且要求所有节点都要投票呢?是的,我们就得到了2PC。2PC是Paxos的一个特例。

如上所述,Paxos比2PC更能容忍失败:

  • leader挂掉。其他的leader可以提出自己的提议来继续协议。
  • 挂掉的leader恢复。由于节点只会同意具有最大序列值的提议,并且只提交之前接受的值,所以两个节点能够同时共存。

Paxos也比3PC更能容忍失败,尤其是在网络分区的情况下。在3PC中,如果两个分区分别同意一个值,那么当分区消失时,系统会处于不一致的状态。在Paxos中,这个问题不会存在,因为同意一个值需要大多数的节点参与。除非一个分区里面的节点占大多数,否则共识不能达成。如果占有多数节点的分区达成共识,这个共识需要另外一个分区的节点接受。

Paxos可能出现的问题是,当两个leader由于节点不能获知彼此的存在时,不停地提出比原来提议序列号高的提议,这会导致Paxos不能终止。最终两个leader获知了彼此的存在,其中一个做出让步。

这是一个一致性和实时性之间的妥协。Paxos保证了一致性,一旦共识达成,值就不会被修改。但是,Paxos不保证可用,在某些极端情况下可能无法达成共识。事实上,一个异步算法不能保证既安全又实时。这被称之为FLP不可能结果。

延伸阅读

  • Principles of Transaction Processing,第8章提供了一个2PC的细节描述
  • Non-blocking Commit Protocols,Dale Skeen描述3PC的文章。
  • The Part-time Parliament。
  • Paxos Made Simple。
  • Paxos Made Live。

原文发布于微信公众号 - 派森公园(demon-hsy)

原文发表时间:2018-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【学习】深度解析LinkedIn大数据平台(二):数据集成

第二部分:数据集成 请让我首先解释 一下“数据集成”是什么意思,还有为什么我觉得它很重要,之后我们再来看看它和日志有什么关系。 数据集成就是将数据组织起来,使...

3317
来自专栏美团技术团队

常见性能优化策略的总结

本文要感谢我职级评定过程中的一位评委,他建议把之前所做的各种性能优化的案例和方案加以提炼、总结,以文档的形式沉淀下来,并在内部进行分享。力求达到如下效果: 1....

4075
来自专栏QQ音乐技术团队的专栏

直播礼物系统设计要点

送礼是直播业务里的核心功能,随着业务的发展,围绕着送礼功能会衍生各种周边功能,如增加几种排行榜,建立一种荣誉体系等。

7580
来自专栏文渊之博

SQL Server2012新特性概述

公司最近要升级数据库,SQL Server 2008R2-->2012。再开始升级之前先找了点资料分析一下2012的新特性和功能,提前预热一下。 2012中主要...

17310
来自专栏Java面试笔试题

什么是中间件?

计 算机技术迅速发展。从硬件技术看,CPU速度越来越高,处理能力越来越强;从软件技术看,应用程序的规模不断扩大,特别是Internet及WWW的出 现,使计算机...

682
来自专栏无题

各RDB与Nosql性能与特点总结

最近考虑到数据库包括各种缓存到底面对高并发情况性能到底是怎么样的,所以多方收集整理成此篇,以后也会持续更新。 mysql: 1.性能从10万条规模升到100万...

38510
来自专栏北京马哥教育

《大型网站技术架构》读书笔记之六:永无止境之网站的伸缩性架构

一、网站架构的伸缩性设计 01、不同功能进行物理分离实现伸缩 (1)纵向分离:将业务处理流程上得不同部分分离部署,实现系统的伸缩性; ? (2)横向分离:将不同...

3179
来自专栏Java Edge

Redis分布式

1 Redis分布式算法原理 1.1 传统分布式算法 举个例子 蓝色表与4个节点时相同槽 1.2 Consistent hashing一致性算法原理 环形 ha...

4098
来自专栏JAVA高级架构

分布式架构--基本思想汇总

541
来自专栏JAVA技术zhai

优化不易,且写且珍惜!

本文要感谢我职级评定过程中的一位评委,他建议把之前所做的各种性能优化的案例和方案加以提炼、总结,以文档的形式沉淀下来,并在内部进行分享。力求达到如下效果:

4017

扫码关注云+社区