Paxos 讲座(Raft 用户研究)

Paxos lecture (Raft user study)

频道:Diego Ongaro · 时长:1:06:33 · 发布:2013-08-15 · 播放:114275

在 YouTube 观看

简介

John Ousterhout 关于 Paxos 的幻灯片加配音讲座,为 Raft 用户研究制作,比较学生学习 Raft 和 Paxos 的方式。这是对 Paxos 共识算法的完整介绍。

HN 为什么推荐

被推荐为学习 Paxos 和 Multi-Paxos 的清晰、易懂的方式,最好与配套的 Raft 视频一起观看。

这两个视频极好地解释了 Paxos 和 Raft 算法以及它们之间的关键区别。 — HN, 2014

分布式系统 · 大学讲座与课程

中文字幕节选

大家好,我是John Ousterhout,在这个视频中我将介绍Paxos共识协议。 Paxos由Leslie Lamport在20世纪80年代末发明,从那时起,它几乎成了共识的代名词。 当大学在课堂上教授共识时,几乎总是使用Paxos作为算法,而大多数实际 共识实现都在某种程度上基于Paxos。Paxos可能已经成为 所有分布式系统中最重要的单一算法。 我将在一个创建复制日志的背景下解释Paxos,然后 我们将使用复制日志来创建一个复制状态机。当我说状态 机时,我指的是一个接收输入并产生输出的程序或应用, 并持有一些内部状态。所以你可以把几乎任何程序或应用 看作一个状态机。这个想法是,我们希望使状态机高度 可靠,而我们希望这样做的方式是让相同的状态机 同时在几个不同的服务器上运行。如果每个状态机 接收到相同的命令集,并且顺序相同,那么它们应该都 行为一致并产生相同的结果。所以理想情况下,如果一些机器崩溃, 其他机器可以继续提供服务。现在,复制日志的目标 是确保那些状态机按相同顺序处理命令。我们首先 将命令存储在日志中,并保证所有日志都有相同的 命令,顺序相同,然后我们从日志中处理命令,这 保证了状态机都做同样的事情。所以系统是这样工作的: 如果客户端想要在状态机中执行一个命令,它首先将该 命令传递给其中一个服务器。假设命令是X,该服务器记录 命令到自己的本地日志中,然后将命令传递给其他服务器, 每个服务器都将命令记录到自己的日志中。一旦命令被安全地 复制到所有日志中,它就可以传递给状态机进行 执行。我们有时使用“应用”这个词来指代当你 实际执行命令时发生的事情。一旦其中一个状态机执行了 命令,那么它的结果可以返回给客户端。你可以看到,只要 所有机器上的日志相同,并且状态机按顺序从日志中 处理命令,那么它们的行为就会一致。这就是 复制日志和状态机的基本原理。 共识模块的任务是确保日志被正确复制, 这就是我们将使用 Paxos 的目的。现在,基于共识的方法最重要的关键特性是, 只要大多数服务器在线,系统就能提供所有服务。 所以如果我们有一个比如五台服务器的集群, 那么只要三台服务器在线,它就能提供所有服务, 因此它能容忍五台中的两台宕机。通常集群规模 会是一个小的奇数,比如三、五或七。让我简要提一下 我们将为 Paxos 假设的故障模型。这是一个故障停止模型,意味着 服务器可能崩溃,或者可能停止并重启,但当它们运行时, 它们总是行为正确。它们不会以恶意方式行事,即所谓的拜占庭 故障。我们还假设网络上的任何消息都可能丢失或 延迟,这意味着它们可能以与发送时不同的顺序到达, 或者网络可能暂时分区,通信被切断, 然后最终分区可能被修复,允许再次通信。但 再次强调,我们假设当消息通过时,它们安全通过,不会被 损坏,并且当服务器运行时,它们运行正确。 有几种方法可以分解实现复制日志的问题。

HN 上的讨论

我最近参加了一门分布式系统课程,我也觉得非常有趣和出乎意料的是,在最基本的 Paxos 形式中,没有节点角色或层次结构的概念,如领导者/跟随者、主/副本等。基本情况是所有节点都有相同的复制日志,并且都是能够发起日志更改的“写入者”。这个 YouTube 视频在学习共识算法,特别是 Paxos/MultiPaxos 方面特别有帮助:[VIDEO] John Ousterhout(Raft 的作者)按照 Leslie Lamport 概述的方式讲解了 Paxos/MultiPaxos,然后讨论了一系列优化性能的改进。一个关键优化是从对单个日志槽提案执行共识,转变为对整个日志槽一起执行共识,这减少了失败的共识轮次,也是领导者节点等概念出现的地方。如果你熟悉 Raft 和 Paxos,在听这些应用于 MultiPaxos 的优化时,你可以注意到它开始类似于 Raft。我参加的课程是通过佐治亚理工… — cljacoby, 2024-02
我见过的最清晰的Raft共识算法解释之一,是John Ousterhout和Diego Ongaro的Raft用户研究[0]中的那个。这两个视频出色地解释了Paxos和Raft算法以及它们之间的关键区别。John的讲解极其清晰,幻灯片也非常有信息量。强烈推荐!Raft是一种共识算法,设计得比Paxos更容易理解。为了衡量Raft的可理解性,我们在两所大学使用CS学生进行了一项实验研究。我们录制了Raft和Paxos的视频讲座,并创建了相应的测验。这个页面将我们的材料提供给任何感兴趣的人。我们认为这些对于任何学习共识(无论是Raft还是Paxos或两者)的人来说都是有价值的资源。[0] - [LINK] Raft视频 - [LINK] Paxos视频 - [VIDEO] — krat0sprakhar, 2014-10
Raft与Multi-Paxos非常相似。这些比较两种协议“可理解性”的Raft和Paxos用户研究可能会有所帮助:[VIDEO](Paxos),[LINK](Raft)。另请参阅各种“Paxos”实现的比较:[LINK] — ignoramous, 2021-07
在我看来,如果你对Paxos有很好的理解,然后学习TLA+,你就会知道在生产分布式系统上工作所需的一切。也学习CRDT,只是为了看看最终一致的系统是什么样子。分布式系统的真正核心不是知道特定的算法,而是知道是什么让这个领域如此困难,哪些解决方案是可能的,以及这些解决方案的局限性。对于学习Paxos,我喜欢这个视频:[VIDEO] 用你选择的语言自己实现它。对于TLA+,有《Practical TLA+》教科书或Leslie Lamport的视频讲座系列:[LINK] — ahelwer, 2020-04
第一个是发表在论文中的证明,你可以阅读。我记得这个证明是针对单法令paxos的。实际上,你需要多轮。有许多微妙的变体,我不知道有证明。实现是否正确?坦率地说,那是一篇尚未写出的博士论文。如果你想读博士并且这个主题在你内心燃烧,那就去吧。关于共识算法概述,不..不是我知道的。这里有一个关于Paxos的好视频:[VIDEO] 享受吧,我的朋友。 — brutus1213, 2017-03

相关视频