热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Paxos的世界:复制日志与状态机

本文介绍了Paxos的世界中关于复制日志与状态机的概念和重要性。通过存储日志来实现数据的持久化,并通过日志流来记录数据的变化,而不是直接持久化数据本身。这样做的好处是简化了持久化存储的操作,并且方便多机之间的数据同步。

在上一篇我们谈到了复制日志的问题,每个node上面存储日志序列,node之间保证日志完全一样。

可能有人会疑问:为啥我要存储日志,直接存储最终的数据不就行了吗?

复制状态机

日志与状态机

我们可以把一个变量x,或者复杂一点,一个对象,看成是一个状态机。每1次写请求,就是一次导致这个状态机发生变化的事件,也就是日志。

以上篇最简单的一个变量x为例,只有1个node,3个客户端发送了3个修改x的指令,最终结果就是如下形式:
这里写图片描述

再复杂点,以mysql为例,客户端发送各种DML操作,这些操作落成binlog。然后binlog被应用,生成各种db表格。就是如下形式:
这里写图片描述

而在这里,就涉及到一个非常非常重要的思想:我们选择持久化导致数据(状态机)发生变化的“事件流(也就是日志流)”,而不是选择持久化“数据本身”。

为啥要这么做呢?原因有很多,我列举几个:
(1)日志只有1种操作,就是append。而数据(或者说状态),一直在变化,可以add/delete/update。把3种操作转换成了1种,这对于持久化存储来说,一下子就简单了很多!!
(2)如果我要做多机之间数据同步,如果你直接同步状态,状态本身的数据结构可能是一个很复杂的数据结构(比如关系数据库的关联表,树,图),并且状态还一直在变化,你要保证多个机器数据一致,要做数据比对,就很麻烦;而如果同步日志,日志是一个1维的线性序列,要做数据比对,非常容易!!

总之,无论从持久化,还是数据同步角度,存储状态机的输入事件流(日志流),都比存储状态机本身要更容易。

复制状态机

我们知道,状态机的原理就是:一样的初始状态 + 一样的输入事件 = 一样的最终状态。

因此,要保证多个node的状态完全一致,只要保证多个node的日志流是一样的就可以了!!即使这个node挂了,重启,重放这个日志流,就能恢复之前的状态。

也因此,我们就回到了上1篇最后的问题:复制日志!

复制日志 = 复制任何数据(复制任何状态机)。因为任何复杂的数据(状态机),都可以通过日志生成!!!

Multi Paxos与Basic Paxos

Paxos的出现,是先有Basic Paxos的形式化证明,之后再有Multi Paxos,然后是应用场景。因为最开始没有先讲应用场景,所以直接看Basic Paxos的证明,会很晦涩。

本文将反过来,就以上一篇最后提出的那个问题为例,先介绍应用场景,再一步步倒推出Paxos, Multi paxos。

一个朴素而深刻的想法

上文讲到,当3个客户端并发的发送3个请求时,下面6种可能的结果都是对的!!

这里写图片描述

因此,我们就是要找一种算法,保证虽然每个客户端是并发的发送请求,但最终3个node记录的日志,一定是同样的顺序!!(上面之1)

那如何做到呢???这里我提出一个朴素而深刻的说法:全世界对数字1,2,3,4,5,6。。。的顺序的认知,是一样的!!!所有人、所有机器,对这个的认知都是一样的!!

什么意思呢? 当我说2的时候,全世界的人,都知道2是在1的后面,3的前面!!!2代表1个位置,这个位置一定在在(1,3)之间。

我们把这个朴素的想法,应用到计算机里面,多个node直接复制日志,就变成如下这样:

当node1收到x=1的请求时,假设我要把它存放到日志中1号位置,先不要存,我先问一下另外2台机器,1号位置是不是已经存放了x=3或者x=5;如果1号位置被占了,那我就问2号位置。。。以此类推;如果1号位置没有人占,我就把x=1存放到1号位置,同时告诉另外2个node,把x=1,存放到它们各自的1号位置!!

同样, node2, node3做同样的事情。

这里的关键思想就是:虽然每个node接收到的请求的顺序不一样,但它们对于日志中1号位置、2号位置、3号位置的认知是一样的,大家一起保证,1号、2号、3号上面,存储的数据一样!

2PC

在上面的例子中,我们可以看到:每个node在存储日志之前,先要问一下其他所有人,之后再决定把这条日志写到哪个位置。

这也就是2个阶段:先问,再做决策。也就是Paxos 2PC的原型!!

Basic Paxos

把上面的问题再进一步拆解,不是3条日志,就1条。我们就先确定3个node的第1号日志,看有什么问题?

node1问了其他所有人,1号位置没有被占,因此它打算把x=1传播给node2/node3;
同样的时刻,node2问了其他所有人,1号位置也没有被占,因此它打算把x=3传播给node1/node3;
同样,node3也打算把x=5传播给node1/node2。

结果不就冲突了吗。到这里,大家就发现,不要说多条日志,就算是只确定第1号位置的日志,都是个问题!!!

而Basic Paxos就是用来解决这个问题:它怎么解决的呢?

1号位置,要么是被node1占领,大家都存放x=1;要么被node2占领,大家都存放x=3;要么是被node3占领,大家都存放x=5。

Basic paxos就搞了2条主要思路:
第1:1号位置的值一旦被大多数确定了,比如是x=5(node3占领了, node2从了node3),那我就接受这个事实。1号位置不能用了,我也得把自己的1号位置赋值成x=5。然后我就看看2号位置,看能不能把x=1存进去,同样的,如果2号也被占领了,我就只能把人家的值拿过来,填在我的2号位置。我就只能看3号位置。。。

第2:当我发现1号位置没有人占,那就告知其他人,锁定这个位置。不允许有人再占这个位置!除非这个人的权利比我大(也就是proposal id比我大)。

如果我发现1号位置为空,然后提交的时候,发现1号位置被别人占了,那就会提交失败,重试,进入第2个位置。。。

Multi Paxos

上面讨论的Basic Paxos只是保证1号位置的日志,在3个node上面1样。并且我们发现,为了让1号位置日志一样,可能要重试好多次,每个节点都会不断重试2pc。

这样一个不断重试2pc,直到最终大家达成一致的过程,就是paxos协议执行的过程,也就是一个paxos instance,最终确定一个值。

而Multi paxos,就是重复这个过程,确定一序列值,也就是日志中的每1条!!

最后

本篇从一个朴素的思想出发,最后引出paxos要做什么。下一篇,我们将详细讨论Paxos算法本身。


推荐阅读
  • 本文介绍了Java工具类库Hutool,该工具包封装了对文件、流、加密解密、转码、正则、线程、XML等JDK方法的封装,并提供了各种Util工具类。同时,还介绍了Hutool的组件,包括动态代理、布隆过滤、缓存、定时任务等功能。该工具包可以简化Java代码,提高开发效率。 ... [详细]
  • 本文介绍了高校天文共享平台的开发过程中的思考和规划。该平台旨在为高校学生提供天象预报、科普知识、观测活动、图片分享等功能。文章分析了项目的技术栈选择、网站前端布局、业务流程、数据库结构等方面,并总结了项目存在的问题,如前后端未分离、代码混乱等。作者表示希望通过记录和规划,能够理清思路,进一步完善该平台。 ... [详细]
  • mysql-cluster集群sql节点高可用keepalived的故障处理过程
    本文描述了mysql-cluster集群sql节点高可用keepalived的故障处理过程,包括故障发生时间、故障描述、故障分析等内容。根据keepalived的日志分析,发现bogus VRRP packet received on eth0 !!!等错误信息,进而导致vip地址失效,使得mysql-cluster的api无法访问。针对这个问题,本文提供了相应的解决方案。 ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 本文介绍了C#中生成随机数的三种方法,并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法,但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数,进一步突显了这个问题。文章指出,随机数生成在任何编程语言中都是必备的功能,但Random类生成的随机数并不可靠。最后,提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]
  • 本文介绍了如何使用php限制数据库插入的条数并显示每次插入数据库之间的数据数目,以及避免重复提交的方法。同时还介绍了如何限制某一个数据库用户的并发连接数,以及设置数据库的连接数和连接超时时间的方法。最后提供了一些关于浏览器在线用户数和数据库连接数量比例的参考值。 ... [详细]
  • 本文详细介绍了MysqlDump和mysqldump进行全库备份的相关知识,包括备份命令的使用方法、my.cnf配置文件的设置、binlog日志的位置指定、增量恢复的方式以及适用于innodb引擎和myisam引擎的备份方法。对于需要进行数据库备份的用户来说,本文提供了一些有价值的参考内容。 ... [详细]
  • 本文由编程笔记小编整理,介绍了PHP中的MySQL函数库及其常用函数,包括mysql_connect、mysql_error、mysql_select_db、mysql_query、mysql_affected_row、mysql_close等。希望对读者有一定的参考价值。 ... [详细]
  • 图解redis的持久化存储机制RDB和AOF的原理和优缺点
    本文通过图解的方式介绍了redis的持久化存储机制RDB和AOF的原理和优缺点。RDB是将redis内存中的数据保存为快照文件,恢复速度较快但不支持拉链式快照。AOF是将操作日志保存到磁盘,实时存储数据但恢复速度较慢。文章详细分析了两种机制的优缺点,帮助读者更好地理解redis的持久化存储策略。 ... [详细]
  • 数据库(外键及其约束理解)(https:www.cnblogs.comchenxiaoheip6909318.html)My ... [详细]
  • 解决Cydia数据库错误:could not open file /var/lib/dpkg/status 的方法
    本文介绍了解决iOS系统中Cydia数据库错误的方法。通过使用苹果电脑上的Impactor工具和NewTerm软件,以及ifunbox工具和终端命令,可以解决该问题。具体步骤包括下载所需工具、连接手机到电脑、安装NewTerm、下载ifunbox并注册Dropbox账号、下载并解压lib.zip文件、将lib文件夹拖入Books文件夹中,并将lib文件夹拷贝到/var/目录下。以上方法适用于已经越狱且出现Cydia数据库错误的iPhone手机。 ... [详细]
  • 本文介绍了在Mac上搭建php环境后无法使用localhost连接mysql的问题,并通过将localhost替换为127.0.0.1或本机IP解决了该问题。文章解释了localhost和127.0.0.1的区别,指出了使用socket方式连接导致连接失败的原因。此外,还提供了相关链接供读者深入了解。 ... [详细]
  • 本文介绍了iOS数据库Sqlite的SQL语句分类和常见约束关键字。SQL语句分为DDL、DML和DQL三种类型,其中DDL语句用于定义、删除和修改数据表,关键字包括create、drop和alter。常见约束关键字包括if not exists、if exists、primary key、autoincrement、not null和default。此外,还介绍了常见的数据库数据类型,包括integer、text和real。 ... [详细]
  • 如何在php中将mysql查询结果赋值给变量
    本文介绍了在php中将mysql查询结果赋值给变量的方法,包括从mysql表中查询count(学号)并赋值给一个变量,以及如何将sql中查询单条结果赋值给php页面的一个变量。同时还讨论了php调用mysql查询结果到变量的方法,并提供了示例代码。 ... [详细]
  • Oracle优化新常态的五大禁止及其性能隐患
    本文介绍了Oracle优化新常态中的五大禁止措施,包括禁止外键、禁止视图、禁止触发器、禁止存储过程和禁止JOB,并分析了这些禁止措施可能带来的性能隐患。文章还讨论了这些禁止措施在C/S架构和B/S架构中的不同应用情况,并提出了解决方案。 ... [详细]
author-avatar
技术交流
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有