Paxos,Raft,EPaxos:分布式共识技术是如何发展的?

本文从技术角度讨论了分布式共识的应用,并对各个领域进行了比较分析。

分布式共识是分布式系统的基石,一直是计算系统领域的重点。近年来,随着分布式系统的扩展,对它的可用性和一致性的要求不断提高,导致分布式共识的使用增加。

从Paxos的统治到Raft的诞生,整个分布式共识在许多行业中的应用,我们已经看到了这项技术的快速发展,其中包括引起人们广泛关注的the leaderless EPaxos。

本文将从技术角度讨论分布式共识在行业中的应用,并对可理解性,可用性,效率和适用方案进行比较分析。

什么是分布式共识?

简而言之,分布式共识是在一个或多个过程提出一个值之后,使系统中的所有过程就一个值达成一致。

为了在一定价值上达成协议,每个过程都可以提出自己的建议。最后,通过使用分布式共识算法,所有正常运行的进程都将获得相同的值。

分布式共识机制的工业应用是建立多复制状态机模型,以实现高可用性和强一致性。

Paxos,Raft,EPaxos:分布式共识技术是如何发展的?-即刻学术
分布式共识允许多台计算机共享相同的状态并运行相同的确定性状态机,以便当几台计算机出现故障时,整个计算机可以继续正常工作。

Paxos

作为分布式共识中的主要算法之一,Paxos至少需要两个阶段达成协议:准备阶段(准备请求)和接受阶段(接受请求)。

Paxos,Raft,EPaxos:分布式共识技术是如何发展的?-即刻学术
准备阶段实现以下目的:

  • 赢得提案权:只有获得提案权后,才能在接受阶段启动提案。否则,需要重新获得提议权。
  • 学习已经被提出的 value。

接受阶段将提案收集为多数。一旦确定了大多数提案,就可以解决该决议并可以对其进行学习。如果拒绝接受阶段,则需要再次进行准备阶段。

Multi-Paxos

基本的Paxos算法需要至少两次网络行程才能达成决议。在并发的情况下,该算法可能需要更多轮次。在极端情况下,它甚至可能会产生活锁,效率低下。为了解决这个问题,因此提出了Multi-Paxos。
Paxos,Raft,EPaxos:分布式共识技术是如何发展的?-即刻学术
Multi-Paxos选举一位领导人(leader),proposal 将由该领导人发起。由于没有竞争,所以消除了活锁问题。如果leader 足够稳定,所有的 proposal 都由该 leader 提出,则可以跳过 prepare 阶段,将两阶段过程更改为一阶段过程,从而提高了效率。Multi-Paxos并没有唯一的领导者。相反,它允许多个领导者同时提出请求而不影响安全性。在极端情况下,它会降级为基本Paxos。

RAFT

与直接从分布式共识问题中得出的Paxos不同,Raft是从多重复制状态机中提出的。它使用更强的假设来减少要考虑的状态,从而易于理解和实施。

以下总结了Raft和Multi-Paxos之间的异同。

相似:

  • raft 的leader 是Multi-Paxos 的 proposer
  • raft 的Term 实质是Multi-Paxos 的 ProposalId
  • raft 的日志条目 logEntry 是 Multi-Paxos 的Proposal
  • raft 的日志索引 logIndex 是 Multi-Paxos 的InstanceId
  • raft 的leader election 实际是 Multi-Paxos 的prepare 阶段
  • raft 的日志复制 log replication 是 Multi-Paxos 的acception 阶段

差异:
Paxos,Raft,EPaxos:分布式共识技术是如何发展的?-即刻学术
Raft假设系统在任何时候最多只有一位领导者,并且提案只能由一位领导者(强领导者 strong leader)发送。否则会影响正确性。Multi-Paxos还会选举领导人,但这仅是为了提高效率。Multi-Paxos并不限制只有领导者(弱领导者 weaker leader)可以提出建议。

在工程中,strong leader 通常使用 "leader lease" 和 "leader stickiness" 来约束:

  • leader lease:前任领导者的租约到期后,系统会随机等待一段时间以启动领导者选举,以确保新老领导者之间的租约不会重叠。
  • leader stickness关注者(follower)如果具有未到期的领导者租约,那么会拒绝了新的领导者选举请求。

Raft有一个限制,即具有最新提交的日志的节点仅有资格成为领导者。相反,Multi-Paxos没有此限制。

Raft在确认日志之前检查日志连续性。如果检测到日志不连续性,则拒绝新日志写入以确保日志连续性。Multi-Paxos跳过此检查,并在日志中保留空白,Multi-Paxos 的日志有间隙。

Raft的AppendEntries中是带有领导者的提交索引的日志条目。确定大多数日志后,领导者将更新本地提交索引(commit index)以完成提交,然后下一个AppendEntries携带新的提交索引并通知其他节点。相比之下,Multi-Paxos不做任何日志连接性假设,并且需要额外的提交消息( commit messages)来通知其他节点。

EPaxos

Egalitarian Paxos (EPaxos)由SOSP'13提出,比Raft早出世,但直到最近才有人注意到EPaxos。

EPaxos是一种无领导者共识算法,它允许任何副本提交日志。通常,提交日志需要一次或两次网路传输。

EPaxos 没有leader 选举开销。当一个副本不可用时,可以立即访问其他副本,从而实现更高的可用性。每个副本都是负载均衡的,不会造成leader的瓶颈,并且具有更高的吞吐量。客户端可以选择最近的副本来提供服务,从而减少跨可用区和跨区域方案的延迟( cross-available-zone (AZ) and cross-region scenarios)。

EPaxos与Paxos或Raft不同,Paxos或Raft的所有的 Instance Number 都是预先排序好的。然后来对每一个实例的值达成一致。EPaxos无需预先确定实例的顺序,而是在运行时动态确定实例的顺序。EPaxos 不仅对实例的么一个值达成一致,而且也会对实例之间的相对顺序达成一致。

EPaxos将不同实例的相对顺序视为一致性问题,并在副本之间达成一致。这样,每个副本可以在其自己的实例中同时提议提议。在同意这些实例的值和相对顺序之后,将根据相对顺序对它们进行重新排序,并最终以新顺序将其应用于状态机。

从图论的角度来看,日志(log)是图的节点,而日志之间的顺序(order)是图的边缘(edge)。EPaxos分别在节点(log)和边缘(edge)上达成协议,然后使用拓扑排序(topological sorting)来确定日志的顺序。鉴于图中可能会出现循环,因此EPaxos需要处理循环依赖问题。

EPaxos引入了日志冲突的概念,该概念与并行Raft类似,但与并发冲突不同。如果日志之间不存在冲突(例如访问不同的密钥),则它们的相对顺序无关紧要。因此,EPaxos仅处理冲突日志之间的相对顺序。

如果并发提议的日志之间不存在冲突,则EPaxos仅需要经过接受前(pre-acceptance)阶段(请求接受前)即可提交(result in a fast path)。否则,它需要经过接受阶段(the acceptance phase)才能提交(resulting in a slow path)。

在pre-acceptance 阶段,EPaxos 就尝试对日志和其他日志之间的相对顺序达成协议,并维护日志和其他日志之间的冲突关系。如果在 pre-acceptance 阶段结束之后,log 和其他log之间没有发现冲突,那么就同意日志的相对顺序,并且EPaxos 可以直接发送异步提交进行提交。如果发现冲突,就不会商定日志的相对顺序。因此,EPaxos 必须经过日志接受阶段(the log acceptance phase)才能达到一个大多数冲突的一个依赖关系,然后发送提交消息进行提交。

EPaxos 的 fast-path 的quorums为2F,可以优化为 F+[(F+1)/2]。它与Paxos和Raft的三个和五个副本一致。slow path与Paxos的接受阶段有关,并且quorums值固定为 F + 1。

EPaxos还具有主动学习算法,可以用于在恢复期间追赶日志。本文不详细介绍该算法。如果您有兴趣,请阅读相关论文。

对比分析

从Paxos到Raft,再到EPaxos,可以对这些算法进行比较,以显示演变过程。以下部分主要在可理解性,效率,可用性和适用方案方面对算法进行比较和分析。

1.可理解性

众所周知,Paxos非常晦涩难懂。不仅难以理解也难以从工程上实施。另一方面,Raft旨在提高可理解性和易于实施。它大大降低了使用分布式共识的门槛,并使分布式共识更受欢迎。Raft提出后,迅速流行并极大地促进了分布式共识的工程应用。

EPaxos的提出甚至早于Raft,但长期以来却很少受到关注。原因之一是EPaxos难以理解。EPaxos基于Paxos,但比Paxos更加难以理解,这极大地阻碍了EPaxos的工程应用。但是,金总是发光。由于其独特的优势,EPaxos获得了普及,并且很有前途。

2.效率

从Paxos到Raft再到EPaxos,效率是否得到了提高?以下各节在负载平衡性能,消息复杂性,流水线和并发处理方面比较了Multi-Paxos,Raft和EPaxos。

负载均衡

Multi-Paxos和Raft leader的负载比EPaxos更高,并且副本之间的负载不平衡,因此领导者很容易成为瓶颈。但是,EPaxos不需要引导者,并且副本之间的负载是完全平衡的。

消息复杂度

在大多数情况下,由Multi-Paxos和Raft选出一位领导人后,只需进行一次网络往返就可以提交日志。但是,Multi-Paxos引入了其他异步消息提交。Raft只需要向前推送本地提交索引,而无需使用其他消息。EPaxos根据日志冲突需要进行一两次网络往返。因此,Raft的消息复杂度最低,其次是Paxos。EPaxos具有最高的。

管道

我们将管道分为顺序管道和无序管道。Multi-Paxos和EPaxos支持混乱的流水线,而Raft由于对数连续性假设仅支持顺序流水线。但是,Raft也可以实现无序的管道。它只需要为 leader 上的每个 follower 维护一个类似TCP的滑动窗口,并为每个follower 维护一个接收窗口。允许接收窗口的日志是不连续的,并且窗口外部有连续的日志。日志连续运行后,窗口将向前滑动,并且窗口中的管道可能会混乱。

并发处理

Multi-Paxos采用Paxos政策。一旦检测到并发冲突,系统将回滚并重试,直到成功为止。Raft使用强大的 leader 来避免并发冲突,因此 follower 不会与 leader 竞争,从而避免了并发冲突。EPaxos直接处理并发冲突,并将冲突的依赖项视为解决并发冲突的一致性问题。简而言之,Paxos采用冲突回退,Raft采用避免冲突,而EPaxos采用冲突解决方案。Paxos和Raft的日志是线性的。EPaxos的日志类似于图形。因此,EPaxos具有更好的并行性和更高的吞吐量。

3.可用性

EPaxos中的任何副本都可以提供服务。当副本不可用时,可以立即将服务切换到另一个副本,对可用性影响不大。但是,Multi-Paxos和Raft取决于领导者。如果领导者不可用,则需要重新选举领导者。因此,在选择新的领导者之前,该服务不可用。显然,EPaxos具有比Multi-Paxos和Raft更好的可用性。在Multi-Paxos和Raft之间,哪个比另一个具有更好的可用性?

Raft 采用了强大的 leader,但 follower 必须等待旧 leader 的租约到期才能发起选举。Multi-Paxos采用 weak leader。follower 可以随时竞选领导者。尽管Multi-Paxos可能会降低效率,但是当领导者失败时,它可以更快地恢复服务。因此,Multi-Paxos比Raft具有更好的可用性。

4.应用场景

EPaxos更适用于跨可用区和跨区域的情况。在对可用性有苛刻要求的情况下,领导者容易产生瓶颈。Multi-Paxos和Raft具有类似的应用场景,例如内部网络。对于一般的高可用性方案,leader 不太容易产生瓶颈。

给TA打赏
共{{data.count}}人
人已打赏
科学人

纪念一下博客优化

2021-1-16 20:27:00

科学人

即刻学术会员说明及本站服务

2021-2-28 22:28:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索