算法 分布式共识算法 Paxos -- 如何让所有程序员认可 PHP 才是最好的语言

yfractal · 2019年07月12日 · 最后由 eaysun 回复于 2019年09月12日 · 4425 次阅读
本帖已被设为精华帖!

为什么需要分布式

使用分布式的原因大体有两个,一个是性能,一个是高可用。

提升性能的话,可以用更好的机器,或者用更多的机器。

一般科学研究的更倾向于用更好的机器,因为这样的架构更简单。

但工程中,多数的时候需要考虑成本(穷),一般会通过使用更多的机器提升性能。

在高可用方面,因为服务器有一定的概率会挂掉,如果只有一体服务器,一旦挂掉,服务就不可用了。

为了提高可用性,会使用多台服务器,这样有服务器挂掉的话,其他服务器还可以继续提供服务。

分布式及 Paxos 所解决的问题

分布式和常见的编程所需要考虑的问题有很大的不同。

比如我们设置一个变量,a = 1,一般可以认为,这个语句在执行完之后,内存中 a 存的就是 1(并发的时候,有 cache 的存在,需要加 memory_barrier)。

但在分布式中,有多个节点存在,之间的通信只能依赖网络。但网络是不稳定的。

所以消息发出去后,在没有响应的时候,我们不知道这个节点,是否还活着,是否收到了消息,是否有处理消息。

Paxos 所做的事,就是在这杨的情况下,让多个节点达成对于某件事,达成一致。比如在多个节点中选出唯一的 master 节点。

Paxos 在真实世界中的模拟

所谓共识,就是所有人对某件事情达成一致。比如所有人都认为 PHP 是世界上最好的语言,那么这个就是一个共识。

但每个人都有不同的想法,Paxos 要做的是让这些不同的想法最终变成一个。

为了达成一致,我们首先规定,多数人所认可的事情,就是事实。就好比投票,多数人同意的,就是大家必须接受的事实。

这个过程,有两个行为,提议和接受提议。为了方便讨论,我们把人按照功能分为两类,提议者和接受者。

我们所要做的事情就变成了让多数提议者接收某个事情,最终让这件事成为所有人都接受的事情。

提议者会通过对话(message passing)的方式,把提议告诉接受者。

这里的对话,和现实中的对话一样,比如 A 问 B:你吃了吗。

B 可能没听到,可能听到不回,可能答非所问,可能突然间挂掉。也有可能 A 先问 C,然后 B 也问 C。但 C 先回答了 B,之后再回答 A。

为了方便讨论,我们现在假设,有三个提议者和三个接受者。这三个提议者,最开始,分别认为,Ruby、Python、PHP 是最好。

提议者,为了让更多的接受者接受自己的想法,就会跟所有的接受者说,xxx 是最好的。

如果接受者不接受提议,那么肯定无法达成共识。所以接受者必须要能接受提议,我们先假设只接受一条。也就是,接受了 Ruby 是最好的,就不能接收其他的了。

这个时候会出现,Ruby、Phthon、PHP 各有一个接受者。这样显然无法达成共识。那么可以推导出,接受者,必须可以更改自己所接受的东西。

所以,接受者需要可以接受新提议。既,假设某个接受者,先听到 Ruby 是最好的,后来又听到 PHP 是最好的,这个时刻,就需要认为 PHP 是最好的。

在这种条件下,如果提议者,每次都坚持自己第一次的提议,依旧可能无法达成共识。

为了达成一致,我们规定,提议者只能在已经接受的提议中选,如果没有被接受的提议,才能自己提出一个。

那么,现在流程就变成了,准备提议(获取当前情况)和提出提议。

因为只能在接受了的提议中选,多次准备、提议之后,可被接受的提议会越来越少,最终会变成一个,既达成共识。

我们在这个基础上进行进一步优化。

在准备这个过程中,我们向所有接受者询问,因为我们只需要争取大多数人的意见,所以我们不需要等所有接受者的返回,只要等到大部接受者的返回即可。

当获取到多数接受者的返回时,为了更快收敛,我们选取最新的那个提议(最后获得的)。

这个流程会不会出现没有进展的情况?会。

假设提议者 P1 从多数接受者获得的最新提议是 p1,P2 从多数接受者获得的最新提议是 p2。之后 P1、P2 将提议发给接受者。

两个人,都需多数接受者接受提议,两组接受者为 S1、S2,因为 S1、S2 都是大多数,所以有一个人都在这两个集合里。假设这个人为 A0。

我们再来看时序,P1 向所有人提议 p1,P2 向所有人提议 p2。A0 这个时候接受 p1 或者 p2。

之后 P1、P2 进行询问。依旧假设是 S1、S2 返回了结果。我们假设 P1 和 P2 最后接收到消息的接受者,不是 A0。则 P1 依旧会提议 p1,

P2 依旧会提议 p2,既没有进展。

但我们知道,这种情况,只有在符合一定条件的情况下,才会出现。所以从概率的角度来讲,多次进行准备、提议后,最终会收敛到唯一结果。

从模拟到算法

在模拟情景中,接受者和提议者,都是根据自己接受到的消息新旧程度进行更新,也就是新信息会替换掉旧信息。

但在分布式的场景里,主机会被部署在不同的地点。节点和节点间的延迟不一样。会出现 A 先发,B 后发,但 B 先到的情况。

如果按照接收到的时间,显然是不公平的。

也不能用发消息的时间戳,因为多个机器的时间可能是不一样的(开 NTP 也会有问题)。

所以在发消息的时候,附带一个数字,当接收消息的人,收到消息的时候。按照这个数字的大小顺序来判断新旧。而每个节点,递增生成这个数据。

算法描述

定义

最新提议:提议者,每次发提议的时候,会带上生成的数字,提议对应对应数字最大的,就是最新的提议。

两个阶段

准备阶段

提议者,生成数字 n,并将这个数字发送给多数接受者。

接受者,接受到这个数字 n,如果该接受者,之前收到比 n 大的数字,则忽略这条消息。

如果这个数字是接收到的消息中最大的,则回复提议者,自己最新接受的提议。

提议阶段

提议者,从多数接受者那,接收到之前准备消息的返回。

如果接受者没有返回任何提议,则提议者可以随意提提议。

如果有提议返回,则需要用最新的提议进行提议。

提议者需要将选择的提议和之前数字 n 发送给接受者。

接受者,接收到提议者发来的提议请求,如果之前没有收到过比 n 大的请求,则接受提议。

最后

经过多次讨论和交流意见,大家愉快的一致同意 PHP 才是世界上最好的语言。

参考

共收到 11 条回复
jasl 将本帖设为了精华贴 07月16日 03:22

大家愉快的一致同意 PHP 才是世界上最好的语言

这是重点,会考,先赶紧拿个小本本抄下来。

raft 才是目前 最好的分布式共识算法。

martin91 回复

大佬说的对

good call, but。。。有点晕,可以来个图么

ForrestDouble 回复

对比一下?

zzz6519003 回复

最近事情太多 😂 ,有时间的时候会考虑搞。

yfractal A Basic Paxos Algorithm Demo Using Erlang 中提及了此贴 08月05日 10:13

@zzz6519003 加了 erlang 的实现 https://ruby-china.org/topics/38909。之后会考虑加图片的 😄

第一次了解Paxos,读了一遍只看懂了大致的流程和意义,《从模拟到算法》中举的例子看完了不太明白,建议再写的详细些。我想问下,提议者A和B各向接受者C发送消息,A的n和B的n是如何被计算出来的?C是如何判断出A的n和B的n的谁大谁小呢?

SaberMyKing 回复

之后会考虑再整理下。

  1. A的n和B的n是如何被计算出来的?

A 和 B 的 n 是自己算的。保证两点就可以,递增并全局唯一。

一个简单的算法,就是在创建提议者的时候给他们一个 id 号,比如 1、2、3。然后 n 从 1 开始并把 id 当做小数部分。

比如 1.001,下一个 n 就是 2.001,以此类推。

代码实现 https://github.com/yfractal/concurrency-lab/blob/master/paxos/src/paxos_proposer.erl#L154

  1. C是如何判断出A的n和B的n的谁大谁小呢?

假设 A 给的是 1.001,B 给的是 1.002 ,那么认为 B 的大。

https://github.com/yfractal/concurrency-lab/blob/master/paxos/src/paxos_acceptor.erl#L70

代码说明 https://ruby-china.org/topics/38909

只会写 Raft 的辣鸡路过。。

大家让一让,我有阿里云华为云腾讯云的服务器,目前可以送华为云一个月的使用,有需要V我aliyun-cz

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册