paxos算法协议_分布式一致性算法_区块链技术_区块链神吐槽
区块链技术资源分享
追寻中本聪先生的脚步

paxos算法协议_分布式一致性算法

Paxos是一种流行的容错分布式共识算法,它允许将全球一致的(全部)订单分配给客户端消息(操作)。

这里概括的大部分内容都是来自Lamport的Paxos Made Simple,但我试图大幅简化它,请参阅该文件的更多细节和明确的解释。

分布式一致性算法的目标是允许一组计算机都同意系统中提出的一个节点(而不是一个随机值)的单个值。

在分布式系统中这样做的挑战是消息可能丢失或者机器cn失败。Paxos保证只要参与算法的大多数系统可用,一组机器将选择一个建议值。

该算法的设置是可以提出值的一组进程的设置。该算法必须确保选择那些提出的值中的单个值,并且所有过程都应该学习该值。

有三类代理:

  1. 提议者
  2. 受体
  3. 学习者

一台机器可以承担任何或所有这些角色。

提议者提出了建议的价值。

接受者驱动算法的目标,就单一的价值达成一致,让学习者了解结果。

接受者要么拒绝提案,要么同意接受提案,并承诺将来会接受哪些提案。

这确保只有最新的一套道具才会被接受。

一个过程可以在一个实现中充当多个代理。事实上,许多实现都具有各个进程的集合,每个进程都承担所有三个角色。

代理程序异步通信。他们也可能无法沟通,可能会重新启动。消息可以采取任意长的交付。他们可以被复制或丢失,但不会损坏。一个损坏的消息应该可以被检测到,并且可以算作一个丢失的消息(例如,这是UDP所做的)。

绝对最简单的实现包含一个接受者。提议者将提案值发送给接受者。接受者一次处理一个请求,选择接收到的第一个提议的值,并且让每个人(学习者)知道。其他提议者必须同意这个价值。

只要接受者不失败,这就行得通了。不幸的是,接受者可能会失败。为了防止接受者的失败,我们转向复制并使用多个接受者过程。提议者现在发送一个包含值的提议给一组接受者。当大多数接受者接受该提案(同意)时,选择价值。

然而,不同的提案者可以在几乎同一时间独立提出提案,这些提案可以包含不同的价值。他们每个人都会与不同的接受者子集沟通。现在不同的接受者会有不同的价值观,但没有一个会有多数。我们需要允许接受者能够接受多个提案。我们将通过为每个提案分配唯一的提案编号来跟踪提案。每个提案都将包含提案编号和值。不同的提案必须有不同的提案号码。我们的目标是就发送给不同接受者子集的提案集合中的一个提议价值达成一致。

当具有该价值的单一提案已经被大多数接受者接受时,选择价值。这意味着它已被选中。可以选择多个提案,但所有提案都具有相同的价值:如果选择具有值v的提案,那么每个选定的较高编号提案也必须具有值v

如果提案编号为n和价值为v的提案被发布,那么存在一个由多数接受者组成的集合S

  1. S中没有接受方接受任何少于n的提议
  2. v是S中被接受者接受的所有编号<n的提案中编号最高的提案的价值。

要发出编号为n的提案的提议者必须学习编号小于n的最高编号的提案,如果有的话,已经或将要被大多数接受者中的每个接受者接受。要做到这一点,提议者从承诺人那里得到承诺,将来不会接受少于n的提议。


Paxos算法

分两个阶段运行:

阶段1:准备发送提案请求
提议者:提议者选择提案编号n,并向大多数受让者 发送准备请求。数字n存储在提议者的稳定存储器中,以便提议者可以确保下一个提议使用更高的数字(即使提议者进程重新启动)。
受体:

  • 如果一个接受者过去收到一个大于n的提议 ,那么它就忽略这个准备请求。
  • 承诺人承诺不接受少于n的提案。
  • 接受者回答提议者过去的提议,它以前接受的最高数小于nreply(n',v')
如果提案人从大多数接受者那里收到了对其准备请求的请求回应,那么它可以发出一个编号为n 和值为v的提案,其中v是回答中编号最高的提案的价值或者由提议者如果答复的接受者没有提出建议。
阶段2:接受:发送提案(然后在接受之后传播给学习者)
提议者: 提议者现在可以发出提案。它会发送一个消息给一组接受者,声明它的提议应该被接受(一个accept(n,v)消息)。如果提议者接收到它的响应制备(n)的从大多数接受器的请求时,它然后发送接受(N,v)的请求到每个这些受体的一个提案编号Ñ具有值v,其中v是最高 - 在答复中提出了提案,如果答复没有提出任何提案,则是有价值的。
受体:
如果受主接收接受(N,V)为提案编号请求Ñ,它接受,除非它已经回答了该提案准备请求具有大于一个数量Ñ

接受者收到提议者的两种请求:准备接受请求。任何请求都可以被忽略。接受者只需要记住它接受过的最高编号的提案和它已经回复的最高编号的编制请求的编号。接受者必须将这些值存储在稳定的存储器中,以便在接收者失败并且必须重新启动的情况下可以保存它们。

只要遵循每个算法,提议者就可以提出多个提议。

paxos算法协议

paxos算法协议

paxos共识

既然接受者有一个提议的价值,那么我们就需要一种方法来了解一个提案已被大多数接受者所接受。该学习者负责获取这些信息。

每个接受者在接受提案后,都会将其转发给所有的学习者。这样做的问题是潜在的大量重复消息:(接受者数量)*(学习者数量)。如果需要的话,这可以被优化。

可以选出一个或多个 “杰出的学习者”。接受者将与他们交流,他们反过来会通知其他学习者。

paxos确保进展

该算法的一个问题是,对于两个提议者来说可能会继续发出数量增加的提议序列,其中没有一个被选择。

来自一个提议者的接受消息可能被接受者忽略,因为已经从另一个提议者处理了更高编号的准备消息。为了确保算法的进展,选择一个“杰出提议者”作为唯一的尝试发布提议。

在操作中,客户向领导者发送命令,这是一个当选的“杰出提议者”。这个提议者对命令进行排序(分配一个值)并运行Paxos算法,以确保选择了一致的序列号。

由于失败或其他服务器可能会有冲突,因此认为它是领导者,使用Paxos可以确保只有一个命令(提案)被赋值。

分享到:更多 ()
区块链神吐槽

来评论吐槽 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

区块链资源分享

韭菜的自我进化