Distributed Systems

  • 时间:
  • 浏览:0

这里把多数派搞定来的意味是不可能 我我真是他是设计容错分布式一致性算法的前提和基础。基于前面对分布式一致现象的说明以及其需要满足的条件,让.我都 先来看看safety的要求,关于liveness在上端会分析。为了方便说明,让.我都 把需要设置值的叫做一个多 项,比如下一个多 日志槽位,一次决议怎么能让针对某个项设置值。

对于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和容错现象并没人详细讨论,这在上端选主相关每段就有涉及到。

Liveness

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

Contents:

进展性的正确处理

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

学习一个多 不可能 达成共识的值

上端多数派保证了在每次决议时详细就有存活机器知道就让所有达成决议的项的值。没人,为甚保证后续针对就让某个项的决议不还可以设置项你这些的值?

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

好了,让.我都 推导出了多数派不用还可以为分布式一致性算法提供容错的基础,下面让.我都 基于此来尝试设计Paxos算法。

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

意味对Paxos理解困难的一个多 意味是对分布式共识现象你这些没人较好的理解。先举个简单例子,怎么能让再说明其需要满足的safety和liveness条件。

ref:

收集的一些资料

实际上选主正确处理并发决议的现象后一切都相对容易理解了,怎么能让在后续leader的日志恢复以及新recover机器的日志恢复,以及整个集群的恢复方面就有走基本Paxos的一个多 阶段,而在你你这些具体的恢复方法和步骤在不同的算法中是不同的,而从Multi-Paxos/ViewStamp replication/Zab/Raft来看,尤其是近两年来的Raft,基本上是在保证基本的容错下的safety和liveness之外加带各种限制条件来复杂leader选举,日志恢复,日志克隆好友十几个 阶段以及一些比如membership management,snapshot等功能的。本质上在leader-based的一致性算法中,在leader选举和日志恢复不可能 会用到基本Paxos,选主后的log replication实际上怎么能让仅仅用了多数派。上端会更详细讨论。

=>

一致性

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

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

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

你你这些节为上端的文章做个铺垫:-)。没人 面的分析需要看过,基本Paxos在面对多个proposer并发提起决议的就让不可能 意味livelock的现象,我真是Lamport原论文提到每一轮Paxos现在刚开始前选出一个多 distinguished proposer(leader/master),怎么能让并没人详细说明与强化leader你你这些概念,这也是上端不多不多不多不多leader-based容错分布式一致性算法强调的一些,而强leader的概念能带来不多不多不多不多工程上实现的复杂与优化。另外对于多个client的并发请求不可能 意味一些值的丢失,比如对于日志的replication,client1访问proposer1,client2访问proposer2,而proposer1和proposer2都一起去针对当前下一个多 日志项,此时不可能 意味某个client的值的覆盖丢失。不多不多不多不多实际中往往会选出一个多 leader,唯一一个多 能接受客户端请求提起决议。

自然而然,分一个多 阶段,不可能 让.我都 就让他不知道针对此项否是不可能 达成决议(这里实际上不可能 中含着Paxos算法的主要设计原则之一,即给每个决议请求编号,区分已达成的决议,后发起的决议,以及过时的决议),不多不多不多不多需要prepare阶段询问存活的机器,不可能 不可能 达成过,没人相当于会有一台机器知道你你这些值,没人让.我都 就用你你这些值进入accept阶段,在accept阶段,不可能 有多数派都同意了你你这些值,没人决议达成。这怎么能让Paxos的两阶段流程。另外,为了保证能正确恢复,Paxos算法的两阶段中,在请求响应的地方需要持久化一些情况值,你你这些需要参考原论文。

=>

分布式系统的基本特点

简单来说:

=>

达成一轮共识的流程

Safety

分布式共识现象通常需要满足Safety和Liveness的要求,具体来说怎么能让:

系统模型

OK,回到本节现在刚开始的现象

=>

例子:多一些人在食堂决定吃你你这些菜,不还可以就让商量好,每一些人需要一起去提出一样菜,上端不可能 一些人临时去上厕所了,待会重新回来,要保证的是最终不还可以你这些菜被接受,怎么能让重新回来的人在需要的就让不用还可以知道这次吃饭到底吃的是你你这些菜。这里需要注意的是:“一起去”说明并发的,一些提议的值不可能 被覆盖的;“一群人临时上厕所”说明需要容错,即在机器挂掉下的分布式一致;“重新回来”说明机器recover需要知道就让决议的结果;