共识算法【Paxos】

Preliminary

系统包括:

  • Acceptor
  • Proposer
  • Learner

Proposer生成一项提议,发送给AcceptorAcceptor如果接受该提议,那么系统所有成员达成共识(即:该提议生效),通过Learner获取共识的内容。

可能存在的问题:

  • 如果有多个Acceptor,会出现多个Acceptor同时接受多个不同的提议的情况;
  • 如果只有一个Acceptor,一旦Acceptor出现故障,那么系统将无法运作;

PS: 下文中的接收是指收到一个请求,接受是指 accept 一项提议。

算法流程:

第一阶段

  1. Proposer 生成一个系统下唯一的ID:n;
  2. Proposer 向大多数 Acceptor 发送prepare请求(附带 n),目的是需要得到 Acceptor 的如下承诺:
    • Acceptor 需要忽略掉 ID 小于n 的请求
  3. Acceptor 如果接收到上述请求,如果 Acceptor 接收过其他 Proposer 发送的prepare请求且对应的ID如果大于 n,那么忽略该请求(不给出承诺),否则回复上述请求。回复的内容包括:
    • Acceptor 接受过的 ID 小于 n且最接近 n 的 某一项提议(抽象为一个值 v
    • 如果没有,则返回空

第二阶段

  1. Proposer 如果接收到大多数 Acceptor 的回复,Proposer 向大多数 Acceptor 发起 accept请求。请求的内容包括:
    • 这些回复的提议中 ID 最大的那项提议的值,如果没有则自拟一项提议
    • prepare请求中发送的 n
  2. Acceptor 接收到 accept 请求时,假设对应的提议ID为n。如果该 Acceptor 做过不接受ID小于m的提议的承诺,那么就忽略掉该请求,否则则接受这项提议。

第三阶段Learner 收集所有 Acceptor 接受的提议,完成共识算法。

分析

  1. 一旦系统达成共识,那么该共识就不会改变,比如:

    • Proposer 1 发送一项提议给大多数的 AcceptorProposer 1获得大多数 Acceptor 的回复后,拟定一项提议Proposal 1发送给 Acceptor达成共识;
    • Proposer 2 如果要发送另外一项提议给大多数 Acceptor,这些 Acceptor 中的部分已经接受了 Proposal 1,根据上述算法,Proposer 2 只能提出提议 Proposal 1Acceptor
  2. 存在不同的 Acceptor 接受不同的 Proposal,比如:

    • Proposer 1 发送一项提议Proposal 1给大多数的 Acceptor ,在一部分 Acceptor未接受这项提议时,另外一个 Proposer 2 发起了另一项提议Proposal 2 给这些 Acceptor
    • 因为 Proposal 2 的ID要比 Proposal 1 的ID要大,因此这部分既收到了 Proposer 1 发送的 prepare 请求又收到了Proposer 2发送的prepare请求的 Acceptor 肯定只会接受 Proposal 2
    • 这种情况只有在 Proposer 2 发送 prepare请求的 Acceptor都没有接受 Proposal 1时才成立 ;
  3. 少数 Acceptor 出现故障,不会影响系统的正常运行;

  4. 存在一个Acceptor接受多个提议的情况,此时这多个提议的值是一样的;

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,816评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,729评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,300评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,780评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,890评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,084评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,151评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,912评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,355评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,666评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,809评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,504评论 4 334
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,150评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,882评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,121评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,628评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,724评论 2 351

推荐阅读更多精彩内容

  • 0.前言 本文记录笔者学习和理解区块链共识算法Paxos的点滴,文章比较长,需要耐心来细细琢磨,笔者也是苦战了一个...
    WallisW阅读 3,230评论 2 14
  • paxos 声明: 本文思路完成模仿 朱一聪 老师的的 如何浅显易懂地解说 Paxos 而得,版权属于 朱一聪 ...
    姚钢强阅读 800评论 0 1
  • 今天整理了一下之前写过的一个下拉刷新的小控件demo,已上传到github. 效果图如下 :(目前水平较水,录制的...
    AnnieAri阅读 128评论 0 0
  • 风静树静心不静 愁来眉锁三分 小窗独坐诉黄昏 十年期一梦,一梦化烟尘。 莫道苍天怜我少 只缘因果缠人 南陈言说未成...
    词韵清心阅读 261评论 0 0
  • 蓝天白云水溪溪 青山怀抱张山寨 山水魂牵古方塘 依韵雅致梦故里 胡源风光甲天下 滋润百花兆丰泽 旧辞新貌腾蛟龙 携...