理解Paxos Made Practical
发布日期:2021-08-30 19:27:52 浏览次数:3 分类:技术文章

本文共 1929 字,大约阅读时间需要 6 分钟。

Paxos Made Practical
当一个组中一台机器提出一个值时,其它成员机器通过PAXOS算法在这个值上达成一致。
Paxos分三个阶段。
第一阶段:
提出者会选出一个提议编号n(n>0,n的低位应当包括提出者的唯一标识。这样两台机器就不会产生同样的编号),然后会向组内其它成员发送信息PREPARE(n)。成员假设已经见到过PREPARE信息大于n,就会拒绝它;假设已经见到的PREPARE信息n‘ < n(这个提议n’的值假设为v‘),就会回复信息PREPARE-RESULT(n’, v’)。假设这个成员还没有见过不论什么提议。就会回复信息PREPARE-RESULT(0, nil)。假设组内大多数成员(majority)都接受了这个PREPARE(n)信息,就进入PAXOS算法的第二阶段。

第二阶段:
It sets v to the value in the highest-numbered prepare-result it received. If v is nil, it selects any value it wishes for v.(没看懂)
接下来提议者会向其它成员广播消息PROPOSE(n。v)。相同,假设成员已经见过的PREPARE(n‘’)(确定是PREPARE而不是PROPOSE)。n‘’ > n。就会拒绝这个消息;否则,就会接受这个消息,并给提议者一个回复。

假设组内多数(包含提议者自己)都接受了这个PROPOSE消息,提议者会广播消息DECIDE(n,v),这就表示这个组在提议的值v上已经达成一致了。

第三阶段哪里去了?


以下是PAXOS算法在实际中是怎样实现的。


先来了解一下什么是状态机(state machine):是一个能接收请求产生回复的可确定性服务(deterministic service),可确定性服务意思是假设两个状态机拥有同样的初始状态。那么当它们接收到同样序列的请求时会产生同样的回复。

首先。我们要清楚一个复制系统(replication system),如Columbia University的M-SMR。会提供两套库,服务器端(server-side)库和client(client-side)库。前者负责状态机的实现,后者是让client发送请求给状态机然后得到回复。


让我们详细看看服务器端(server-side)库提供的三个函数:
替代文字
这里说一下run函数的第三个參数
buf execute (buf request);
这是状态机里一个非常重要的组成函数。它负责将请求带给状态机并返回回复。
之前我们说过client库负责用户请求的提交和得到回复(这怎么和server端函数run的參数execute函数的功能一致呢?),假如这时有多个用户请求同一时候到来。client库就须要对这些请求达成一个统一的运行顺序让组内成员去运行,来保证一致性。这里就涉及与组内成员的通信问题。client库是怎样来联系组内各个成员的?也许是RPC。
不幸的是并非全部的RPCserver都是确定性的(deterministic)。举个样例,一个文件server会在一个文件发生写操作后将改动时间记录在文件的inode中。这样即使两个成员机器运行同样的文件server程序并运行同样的写请求,可是它们在运行写操作的时间却无法保证同样,比方都是2014/11/14 23:06。

这样就会在成员之间出现分歧状态。为什么你记录的改动时间比我早十分钟?解决方法是让一个机器记录下自己的改动时间,然后广播给大家。告诉大家都来记录这个时间。

事实上这里改动时间就是一个不确定性值(non-deterministic value)。还是那个问题client库是通过什么手段来联系组内各个成员的?
看来这个问题是无法解答了。解析来切入正题: Normal-case operation


Normal-case Operation
在一个组里,有一个primary。其它的称作backups,这里有一个术语:view,表示一个拥有primary机器的处于活动状态的机器集合。每个view会有一个view-id来唯一标识,并且view-id是单调递增的,随着每一次view的改变。
替代文字

上图展示了在正常情况(没有机器增加,没有机器故障)下信息的流动。

这里再引入一个术语:viewstamp,由view-id和timestamp结合而来,primary会给每个到来的请求一个timestamp。这个timestamp就指明了请求被运行的顺序。

相同加强版的viewstamp也表示请求的运行顺序。


转载地址:https://blog.csdn.net/weixin_34049948/article/details/85890391 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:解析cocos2d-lua项目中的Hello World
下一篇:JAVA微信服务号开发简记

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.172.111.71]2022年05月22日 09时26分44秒