深入分布式缓存-Paxos-阿里云开发者社区

开发者社区> 数据库> 正文

深入分布式缓存-Paxos

简介: 世界上只有一种一致性算法,就是 Paxos

前言

分布式系统中,根据CAP理论中的C 一致性要求,多个节点间,需要有达成一致的协议。

Paxos 算法是由图灵奖获得者 Leslie Lamport 于 1990 年提出的一种基于消息传递且具有高度容错的特性的一致性算法。算法比较难理解,大神于第一次发表八年之后,再次发表,仍然没有得到重视,直到2006年,才被Google慧眼识珠。

该算法在很多大厂都得到了工程实践,比如阿里的 OceanBase 的分布式数据库,底层就是使用的 paxos 算法。再比如 Google 的 chubby 分布式锁也是用的这个算法。

”世界上只有一种一致性算法,就是 Paxos。“,这句话被一度传扬。

Paxos协议简介

Paxos协议是一个两阶段协议,分为Prepare(准备)阶段和Accept(接收)阶段。

简单理解就是,第一轮发送消息,告知所有集群中的节点,要发生更改,第二阶段,来根据大家接受到的消息,判断多数服从少数,选择一个当做最终决定。

首先,系统根据所有想修改数据的节点,提出请求,前后顺序,生成全局唯一且递增的ID。然后开启流程。

Prepare阶段

所有要想修改数据的节点,发起请求到所有集群节点,此时,发送各自的获得的ID,以及内容

接收方节点,接收到收到的ID之后,与本地存在ID对比,如果接受到的,大于存在的ID,就把本地的ID替换为最大的那个。同时,做出约定,不再接收小于等于当前收到的ID的请求了,同时,也就不会再去处理小于当前收到的ID的请求。简单说明,就是,有了最大的,一切以最大的为中心,其余的都不在重要。另外,接收方节点,如果替换ID动作完成,就把当前存储的ID最大的告诉所有发送给自己的节点。

Accept阶段

最终所有的接收方节点,心中,都有了自己要保留的ID,大家多数服从少数,最终统一成一样的。

理解整个Paxos协议,最重要的是理解,多数服从少数,时间优先。

场景举例

有小明 小红 小李 小王 四个同学要选班长,那么只要是想选的,就要发起游说,告诉所有其他同学要选他自己。

现在,小明,小王想要竞选。

假设都通知到位(出点节点故障,同理)
image.png
此时,以一个场景为例说明(上述ID此处代表高大):

小明先对小李发起友好游说,然后小李才收到小王的消息

此时,小李告诉小明,好,我记着了,然后小王来了之后,

小李就在想,哎呀小王那么高大,当班长正好,就告诉小王,之前小明也报名了,但是我记得了,我到时候选你。

小明对小王发起游说,然后,被小王说,我也选。小明尴尬的离开。

小明又对小红发起消息,但是晚了一步,小王先对小红游说完毕了。

小红,直接把小明拉黑了。小王也去给小明发了个消息,小明此时,就说好,我知道了,我会选你的。自己背叛了自己。

最终,小李、小红、小王、小明选小王,小明 选小明,小王当选。

总结

Paxos 协议/算法 就是少数服从多数,标准的 鸽笼原理/抽屉原理,同时,还会根据相关约定的权重来判断是否需要应答,权重其实就是ID,是为了防止出现活性导致死循环。

注意:这一切都是在没有 拜占庭将军 问题的基础上建立的,即消息不会被篡改(因为分布式大多在局域网中)。

Paxos 的目标:保证最终有一个提案会被选定,当提案被选定后,其他人员最终也能获取到被选定的提案。

Paxos 协议用来解决的问题可以用一句话来简化:将所有节点都写入同一个值,且被写入后不再更改。

                                                    《end》

欢迎大家的关注,进阶架构师,需要持续不断的能量,在这里,只需跟着走,能量自然有。
image.png

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章