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

本文共 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微信服务号开发简记

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月15日 20时39分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql男女字段应该建立索引吗_那些字段适不适合建索引? 2019-04-21
安装mysql最后一步密码_MySQL安装最后一步无响应解决方法 2019-04-21
mysql modify语句格式_40条MySQL数据库语句格式 2019-04-21
mysql忽略大小写jpa解决_JPA 大小写敏感问题 2019-04-21
MySQL5.7 固态盘性能设置_MySQL 5.7 安装完成后,立即要调整的性能选项 2019-04-21
idea java web mysql_解决idea中javaweb的mysql8.0.15配置问题 2019-04-21
mysql.net 环境配置_windows环境下下安装配置mysql5.7.24 2019-04-21
servlet对象是在服务器端还是在客户端被创建?_Servlet编程之会话管理 2019-04-21
sqoop mysql hadoop_如何将mysql数据导入Hadoop之Sqoop安装 2019-04-21
webpack卸载_webpack的安装 2019-04-21
mysql主库线程_MySQL 主从扩展--主库的线程状态 2019-04-21
phpmyadmin管理mysql_LAMP实验二:使用phpMyAdmin管理MySQL 2019-04-21
mysql一秒最多写多少次_Mysql的两种“超过多少次”写法(力扣596) 2019-04-21
mysql el函数_MySQL中的常用函数 2019-04-21
mysql 备份 晓燕_mysql字符串函数 2019-04-21
mysql返回第n个值_获取mysql一组数据中的第N大的值 2019-04-21
java 获取请求的路径_JavaWeb-request获取请求路径的相关方法 2019-04-21
java 适应边框_带边框自适应宽度100%的解决办法 2019-04-21
router vue 页签文字_记一次基于vue的spa多页签实践经验 2019-04-21
估计的商是什么意思_商是什么意思,商的繁体字,商有几笔,商字几画 2019-04-21