Distributed Systems

  • 时间:
  • 浏览:1
  • 来源:uu快3官方网站_uu快3苹果版_走势

系统模型

Liveness

分布式共识问題通常还要满足Safety和Liveness的要求,具体来说而是:

这里把多数派搞掂来的意味着是意味着我随便说说他是设计容错分布式一致性算法的前提和基础。基于前面对分布式一致问題的说明以及其还要满足的条件,大伙儿儿先来看看safety的要求,关于liveness在上端会分析。为了方便说明,大伙儿儿把还要设置值的叫做五个 项,比如下五个 日志槽位,一次决议而是针对某个项设置值。

好了,大伙儿儿推导出了多数派上能 为分布式一致性算法提供容错的基础,下面大伙儿儿基于此来尝试设计Paxos算法。

Safety

实际上选主除理并发决议的问題后一切都相对容易理解了,而是在后续leader的日志恢复以及新recover机器的日志恢复,以及整个集群的恢复方面上能 走基本Paxos的五个 阶段,而在哪几种具体的恢复最好的最好的办法和步骤在不同的算法中是不同的,而从Multi-Paxos/ViewStamp replication/Zab/Raft来看,尤其是近两年来的Raft,基本上是在保证基本的容错下的safety和liveness之外打上去各种限制条件来繁复leader选举,日志恢复,日志克隆好友好多个阶段以及许多比如membership management,snapshot等功能的。本质上在leader-based的一致性算法中,在leader选举和日志恢复意味着会用到基本Paxos,选主后的log replication实际上而是仅仅用了多数派。上端会更全版讨论。

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/60 829689

进展性的除理

先简要回顾下Paxos算法的核心要素:

当然,其中采用全局递增的标识给决议编号在定义五个 决议的五个 阶段的互相交错时的行为上起着决定性作用(你这人 点实际上是意味着并发提决议意味着的,对于leader-based的算法比如raft实际上在五个 term期间内没办法 五个 有效的leader,所有决议没办法 由你这人 leader发出,所以不所处你这人 问題,对于每个“”客户端请求决议”term的值不还要增加,以后 当进入选主的情况报告时,意味着会有并发的candidate发起选主决议了,此时实际上又回到了基本的Paxos,raft采用随机timeout的简单最好的最好的办法来除理基本Paxos的livelock问題)你这人 点还要较形式化地分析,不好像上述那样以逻辑推演的最好的最好的办法一步一步导出,意味着涉及的情况报告转换较多。

学习五个 意味着达成共识的值

你这人 篇文章主要简单介绍一下分布式共识和一致性协议的背景和Paxos算法,以及我所理解的它的设计逻辑,并按照你这人 逻辑尝试非形式化地重新设计Paxos算法,并与Lamport原始论文中的描述相对应。这篇文章主要指basic Paxos,而上能 许多变形比如Multi-Paxos及许多的leader-based的分布式一致算法,比如Raft/Viewstamped Replication/Zab,后续文章会着重分析leader-based的分布式一致算法。

对于Liveness的问題想多说点,在FLP定理中讨论的模型是全版异步,crash-failure fault但网络可靠你这人 假设比较严格的模型,并证明了在此系统模型下不所处全版的分布式一致性算法能除理分布式共识问題(注意是全版,意味着大伙儿儿放弃许多Safety意味着Liveness的要求,比如可证严格的Safety而使用随机化等最好的最好的办法保证一定概率的Liveness,另五个 的算法是能实现的,而这也是Paxos一类算法的确定,毕竟放弃了Safety没不需要 意义了),而通常像Paxos和类Paxos算法讨论的模型比FLP中的模型更松:全版异步,网络不可靠,crash-failure fault甚至byzantine fault,所以Paxos类算法本质上也没最好的最好的办法完美除理Liveness的问題,Lamport的原始论文中只提到选主(选出distinguished proposer)来除理你这人 问題,以后 至于选主本身生活的Liveness和容错问題并没办法 全版讨论,这在上端选主相关要素上能 涉及到。

除了除理上端的问題,选主还能为算法优化与繁复带来更大空间。比如raft对选主做限制,保证leader上的日志上能 最新且连续的,在一定程度上繁复了lamport在《paxos made simple》中简单提及的multi-Paxos在leader日志恢复的步骤,另外,batch决议请求,让leader保证最新日志优化读请求(leader lease/follower lease)等。

=>

例子:多另一方在食堂决定吃哪几种菜,没办法 以后商量好,每另一方都上能 并肩提出一样菜,上端意味着村里人 临时去上厕所了,待会重新回来,要保证的是最终只本身生活生活菜被接受,以后 重新回来的人在还要的以上能不能 知道这次吃饭到底吃的是哪几种菜。这里还要注意的是:“并肩”说明并发的,许多提议的值意味着被覆盖的;“村里人 临时上厕所”说明还要容错,即在机器挂掉下的分布式一致;“重新回来”说明机器recover上能 知道以后决议的结果;

一致性

ref:

埋点的许多资料

自然而然,分五个 阶段,意味着大伙儿儿以后我想知道针对此项是与非 意味着达成决议(这里实际上意味着包含着Paxos算法的主要设计原则之一,即给每个决议请求编号,区分已达成的决议,后发起的决议,以及过时的决议),所以还要prepare阶段询问存活的机器,意味着意味着达成过,没办法 大约会有一台机器知道你这人 值,没办法 大伙儿儿就用你这人 值进入accept阶段,在accept阶段,意味着有多数派都同意了你这人 值,没办法 决议达成。这而是Paxos的两阶段流程。另外,为了保证能正确恢复,Paxos算法的两阶段中,在请求响应的地方还要持久化许多情况报告值,你这人 上能 参考原论文。

分布式系统的基本特点

OK,回到本节开始的问題

=>

你这人 节为上端的文章做个铺垫:-)。另五个 面的分析上能 看完,基本Paxos在面对多个proposer并发提起决议的以后意味着意味着livelock的问題,随便说说Lamport原论文提到每一轮Paxos开始前选出五个 distinguished proposer(leader/master),以后 并没办法 全版说明与强化leader你这人 概念,这也是上端所以leader-based容错分布式一致性算法强调的许多,而强leader的概念能带来所以工程上实现的繁复与优化。另外对于多个client的并发请求意味着意味着许多值的丢失,比如对于日志的replication,client1访问proposer1,client2访问proposer2,而proposer1和proposer2都并肩针对当前下五个 日志项,此时意味着意味着某个client的值的覆盖丢失。所以实际中往往会选出五个 leader,唯五个 能接受客户端请求提起决议。

上端多数派保证了在每次决议时上能 存活机器知道以后所有达成决议的项的值。没办法 ,如可保证后续针对以后某个项的决议没办法 设置项本身生活的值?

Paxos算法无疑是分布式系统理论中的经典,意味着所以论文、博客都没办法 全版分析算法的背景以及实际中应用会产生的非常多的细节问題,所以意味着先要理解,意味着说先要完埋点解,实现和测试则是更繁复,不过这也是你这人 问題有意思的意味着吧:-)。读过许多论文,思考过许多问題,希望能把你这人 问題的背景,以及各种容错分布式一致性算法设计的逻辑和背景记录下来,当然,内容随便说说不需要 ,最早得追溯到迪杰斯特拉对并发与分布式问題的讨论吧,所以你这人 系列准备以Paxos算法为核心,介绍其一系列的衍生算法及其相关的问題。当然,所以东西是通过许多论文结合另一方的理解去推测作者当时如可去思考设计优化哪几种算法的,至于形式化证明的要素就弱化了。整个系列的最大目的是希望能理清分布式共识问題的背景,主要容错分布式一致性协议的设计逻辑以及它们的联系与区别,上端有意味着分析下实际工程中的实现比如ZooKeeper/Etcd/Consul等,最后意味着有意味着另一方简单实现一下:-)

简单来说:

=>

关于liveness的问題,意味着所处多个proposer交替抢占意味着的livelock问題,意味着针对某个项无法达成某个值的决议。你这人 在前面也提到FLP定理所限制的。

Contents:

意味着对Paxos理解困难的五个 意味着是对分布式共识问題本身生活没办法 较好的理解。先举个简单例子,以后 再说明其还要满足的safety和liveness条件。

=>

达成一轮共识的流程