登录 |  注册
首页 >  云计算&大数据 >  经典算法大全 · 实例详解 >  Paxos算法原理及应用-分布式一致性算法

Paxos算法原理及应用-分布式一致性算法

Paxos、Raft分布式一致性算法应用场景一文讲述了分布式一致性问题与分布式一致性算法的典型应用场景。作为分布式一致性代名词的Paxos算法号称是最难理解的算法。本文试图用通俗易懂的语言讲述Paxos算法。

 Paxos算法简介

Paxos算法是1990年LeslieLamport 在论文《ThePart-TimeParliament》提出的,是一个基于消息传递且具有高度容错性的一致性算法。但是初期由于Paxos难于理解并没有引起多少人的重视,直到2006年Google的三大论文出现,其中ChubbyLock服务使用了Paxos作为ChubbyCell的一致性算法,这才使得Paxos算法的人气从此一路飙升,可以说Paxos是分布式协议的鼻祖,在分布式领域有着非常重要的地位。

Paxos也有其自身的缺点:一个是难于理解;另一个是论文中并没有提供工程实现方法,对工程实现支持并不好。因此在工程实践中,常常是借鉴Paxos算法的核心思想,同时结合系统特点和痛点,进行Paxos算法改造来满足系统需求,并逐渐衍生出了多个Paxos算法的变种,比如Multi-Paxos、Fast-Paxos、Cheap-Paxos、GeneralizedPaxos、Mencius等。

Paxos算法原理

Paxos要解决的问题:假设有一组可以发起提案的进程集合,一个一致性算法要保证在提出的多个Value中,只有一个Value被选中(Chosen).如果没有Value被提出,就不应该有Value被选定。当有一个Value被选定,所有进程都应该能学习到这个被选定的Value。

基本概念

三种角色:

  • Proposers,提案的发起者;

  • Acceptors,提案的接受者,即投票者;

  • Learners,最终决议的学习者和执行者。

在Paxos算法中,一个节点可以充当多种角色。Proposer可以提出提案,Acceptor可以接受提案(即为提案投票),如果某个提案被最终选定(Chosen),那么该提案里的Value就被选定了。

算法原理

Paxos算法设计了Prepare、Accept、Learn三个阶段,前两个阶段实现从多个Proposer提出的提案中选择一个提案(即选择一个Value)并达成共识,第三个阶段让Learners学习到这个最终被选定的提案。

1.选择一个Value并达成共识

这部分涉及到两个角色,即Proposer和Acceptor。如何从Proposers提出的多个Value中选定一个Value,是Paxos算法的核心内容。

【算法流程】:

Paxos.jpg

注:

提案由提案编号N和提议值Value组成,表示为[N,V]。

[ResN, [AcceptN, AcceptV]]中,ResN表示Acceptor已经响应过的Prepare请求的最大编号,[AcceptN, AcceptV]表示Acceptor已经接受过的编号最大的提案。

[算法分析]

Paxos算法中主要有四种类型消息:Prepare、Promise、Accept、Accepted。

1)Proposer先发起一个Prepare消息,来获得提议的权利,同时学习已经被选定的提案。Acceptor通过回复Promise消息,对提议权的请求进行投票。

2)当Proposer收到超过半数的Promise消息后,就获得了提议权,并把学习到的提案Value值放到自己的提案里面。然后通过Accept消息发出自己的提案。

3)Acceptor通过回复Aeccpted消息,对提案进行投票。

4)当Proposser收到超过半数的Accepted消息后,这个提案就被选定了。

5)如果一直没有提案被选出,那么Proposer就会重新获取提案编号,再进入第一阶段,重复这个Paxos算法流程,直到最后有提案被选中。

2.Learners学习被选定的Value

Paxos算法中,对Learners如何学习到选定的Value提出了3种方案,而每一种方案都有其优缺点,具体如下:

Paxos.jpg

说明:M是Acceptor的数量,N是Learner的数量

在算法的实践中,使用Proposer将通过的提案发送给Learners也是一个不错的选择,可根据具体情况选择合适的方案。

Paxos算法在MGR的应用

MGR,MySQLGroupReplication的缩写,即MySQL组复制技术。MGR是MySQL官方在5.7.17版本推出的高可用解决方案,基于原生的复制技术,以插件的方式提供。支持多节点并发地执行事务是MGR的一个重要特性,我们知道MGR采用share-nothing的复制方案,组内每个成员都有自己完整的数据副本,节点之间的数据是最终一致的。如何做到的呢?先来了解一下MGR中事务的生命周期,如下图所示。

Paxos.jpg

1.事务在各自的MySQLServer层启动、执行,这个过程无需和MGR集群内的其他节点进行协调、通信。

2.当事务需要提交时(prepare之后,写binlog之前),将事务信息(包含binlog、write_set、gtid、节点uuid)发送到MGR中的通信模块,事务消息将基于Paxos协议在全集群范围进行原子广播,每个节点都将收到整个集群发生的所有事务,且所有事务在每个节点内的排序是完全相同的。

3.通信模块将事务按照排序顺序发送到本节点的全局事务认证模块。全局事务认证模块对事务进行冲突检测,并将检测结果返回MySQLServer层。

4.根据检测结果,本地事务将更新日志写入binlog并commit,或者回滚;异地事务将更新日志写入relaylog等待应用,或者丢弃。

从MGR事务的生命周期中,可以看到基于Paxos的通信模块(即MGR中的组通信引擎XCom)对节点间数据一致性起到了至关重要的作用,也是MGR的核心。下面我们介绍一下基于Paxos的通信模块(XCom)的具体实现。为了避免单Leader写入性能瓶颈问题,MGR并没有使用传统的Multi-Paxos,而是采用了类似Mencius的算法。在XCom的算法里,每个节点都有一个唯一的编号,在全局有序的消息序列中,每个节点都有属于自己特定的slot,如下图所示,共三个节点,编号分别是0、1、2。

Paxos.jpg

节点0持有slots:0, 3, 6, ...

节点1持有slots:1, 4, 7, ...

节点2持有slots:2, 5, 8, ...

正常情况下,没有leader选举,每个节点都是它所属slots的Leader,这是协议里约定好的。在自己所属的slots里,可以直接发起事务提案(省去了Paxos算法中Prepare阶段),当有过半节点接受(Accept)提案后,就可以将事务信息发送到本节点的全局事务认证模块。

但是此算法可能导致全局slot序列中有gap产生,如下图所示,节点1和节点2已经对slot1和slot2的消息达成了共识,但是对slot0的消息还没有达成共识。

Paxos.jpg这时候,是不能对slot1和slot2的消息进行应用的,所以需要有人在slot0上提一个noop提案,令整个系统继续向前推进。当节点0正常的情况,节点0自己会适时提出noop提案的,否则需要其他节点帮助slot0提一个noop提案,这时候就需要执行Paxos的整个流程,包括prepare阶段(选择一个Leader来发起noop提案)。

总结

以上便是Paxos在MGR通信模块中的具体实现。Paxos算法在工程中的应用还有很多,例如Google提出的分布式锁服务ChubbyLock,其中ChubbyCell基于Paxos算法实现了副本间数据的一致性及集群Leader的选举;阿里自研分布式数据库OceanBase采用Paxos算法实现数据一致性;著名的Raft协议也是对Paxos算法的一个简单实现;而国产分布式数据库TiDB,其调度/元数据存储组件PD,及底层存储组件TiKV均使用Raft协议保证了数据一致性,实现了Leader的故障转移等等。可以说在分布式系统的世界中,Paxos算法的影子随处可见。
下一篇: Raft算法原理及应用-分布式一致性算法
推荐文章
  • MD5(Message-DigestAlgorithm5)是一种广泛使用的散列函数(哈希函数),由美国密码学家罗纳德·李维斯特(RonaldL.Rivest)在1991年设计。MD5的作用是对任意长度的信息生成一个固定长度(128位,即32个十六进制字符)的“指纹”或“消息摘要”,并且几乎不可能找到
  • 循环冗余校验(CyclicRedundancyCheck,CRC)是一种用于检测数据传输和存储过程中发生错误的技术,属于一种基于数学原理的错误检测编码(ErrorDetectionCoding)方法。它通过在原始数据上附加一个固定长度的校验码,使得接收端可以通过同样的计算规则对收到的数据进行校验,确
  • AES(AdvancedEncryptionStandard)是一种广泛使用的对称密钥加密算法,它是美国国家标准与技术研究院(NIST)于2001年制定的加密标准,用于替代原有的DES(DataEncryptionStandard)。AES算法以其高效性、安全性和可靠性而著称,在众多应用领域中被广泛
  • RSA(Rivest-Shamir-Adleman)是一种广泛应用的非对称加密算法,由RonRivest、AdiShamir和LenAdleman在1977年提出。其安全性基于数学上的大数因子分解难题,即对于足够大的两个素数p和q而言,已知它们的乘积很容易,但想要从这个乘积中恢复原始的素数则异常困难
  • 最小生成树(MinimumSpanningTree,MST)是一种图论算法,用于在一个带权重的无向连通图中找到一棵包括所有顶点且总权重尽可能小的树。常见的最小生成树算法有两种:Prim算法和Kruskal算法。Prim算法原理:Prim算法是一种贪心算法,它从图中的一个顶点开始,逐步增加边,每次都添
  • 关于最短路径算法的Java实现,这里简述一下几种常用的算法及其基本原理,并给出一个Dijkstra算法的基本实现框架。Dijkstra算法(适用于无负权边的图)Dijkstra算法用于寻找图中一个顶点到其他所有顶点的最短路径。它维护了一个距离表,用来存储从源点到各个顶点的已知最短距离,并且每次都会选
学习大纲