深入理解分布式（一） —— 一张图理解Paxos算法

目录

序

首先我们知道，Paxos算法，是一种基于消息传递且具有高度容错特性的共识（consensus）算法。这里我们不对它的发展和目标进行展开，如果有不清楚的可以参考wiki：https://zh.wikipedia.org/zh/Paxos%E7%AE%97%E6%B3%95

Paxos算法很强大，但同样也很难理解，那为什么我们还需要耗费时间去理解它呢，使用现成的解决方案不香吗？老实说，

  1. 为了面试！！
  2. 为了借鉴算法的思想，举一反三！！

这篇文章主要是使用流程图的方式，帮助读者抓住算法的关键点以及推导流程，使读者更容易理解并记住Paxos算法的工作原理。

概念

如果你还不太了解Paxos的这些核心概念，请参考wiki百科，

  • Acceptor、Proposer、Learner
  • 批准
  • 选定 —— 被半数以上Proposer批准
  • 提案 —— [编号，值]，例如 [M0,V0]，[Mn,Vn]

提案的选定

 
要解决：即使只有一个提案，仍然可以选定提案
要解决：由于某些Acceptor出错或其他原因
导致每个提案都无法被超出半数Acceptor批准，
即，提案无法被选定
等同于
被选定意味着至少被一个Acceptor批准，
通过满足<b>P2a</b>来满足<b>P2</b>
我们需要<b>P1</b>来保证提案被选定，但是由于通信是异步的，
如果一个提案，在某些提案被选定后，发送给为还未接受
任何提案的Acceptor，同时如果这个提案的Value与那些选定
提案的Value不同，此时，<b>P1</b>与<b>P2a</b>相矛盾。我们可以通过
满足<b>P2b</b>使得<b>P1</b>与<b>P2a</b>同时满足。
<b>Proposer生成提案</b>时，只需要通过保持<b>P2c</b>，就能满足<b>P2b</b>
从<b>P1</b>到<b>P2c</b>其实是一系列条件的逐步增强，我们要
证明这些条件可以满足一致性，就要进行反向推导：
<b>P2c => P2b => P2a => P2</b>
然后通过<b>P2</b>和<b>P1</b>来满足一致性。
通过<b>第二数学归纳法</b>来证明<b>P2c</b>可以满足<b>P2b</b>，即：<ol><li>先证明，在<b>P2c</b>的前提下，Mn=M0+1时
结论成立</li><li>再证明，在<b>P2c</b>的前提下，当假设M0+1到
Mn-1都成立时，Mn也成立。</li><li>最终可归纳出：
当每个Proposer按照这个<b>P2c</b>的条件产生提案时，
就能满足<b>P2b</b>了</li></ol>
<b>P1</b> ：一个Acceptor必须批准它收到的第一个提案
选定一个提案，需要半数以上的Acceptor批准
一个Acceptor可以批准多个提案
结论：允许多个提案被选定，但被选定的提案必须
具有相同的Value值
<b>P2</b>：如果『M0,V0』被选定, 所有比M0大的提案，
且被<b>选定</b>，其Value也必须是V0
<b>P2a</b>：如果『M0,V0』被选定, 所有比M0大的提案，
且被Acceptor<b>批准</b>，其Value也必须是V0
<b>P2b</b>：如果『M0,V0』被选定，之后Proposer产生的
编号更高的提案，其Value都为V0
<b>P2c</b>：如果『Mn,Vn』被提出, 那么肯定存在一个半数以上
Acceptor组成的集合S，满足以下条件中的任意一个：
<ul><li>S中不存在批准过编号小于Mn的提案的Acceptor。</li><li>选取S中所有Acceptor批准的编号小于Mn的提案，
其中编号最大的那个提案的Value值必须是Vn。</li></ul>
实际上<b>P2c</b>规定了Proposer产生提案的方式，
当每个Proposer按照这个规则产生提案时，就能
满足<b>P2b</b>了。
<b>P2b => P2a => P2</b>不难理解，对于<b>P2c => P2b</b>
我们可以通过<b>第二数学归纳法</b>来证明：
    首先假设提案『M0,V0』被选定了，设比该提案编号
更大的提案为『Mn,Vn』，我们需要证明在<b>P2c</b>的
前提下，对于所有『Mn,Vn』，存在<b>Vn = V0</b>

关注作者公众号，随时了解更多干货！

在这里插入图片描述

往期推荐

版权声明：本文为qq_32331073原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。