基础Paxos算法的9页笔记

       Paxos算法是Leslie Lamport发明的一种基于消息传递，用于解决分布式环境下共识的算法。所谓分布式环境下的共识，是指在分布式多节点环境下，如何让不同的节点就某个值达成一致的算法（或者策略），而达到这一点，需要能够可靠的应对分布式环境中出现的各种不确定性和故障。

       Lamport寄期望模拟一种民主议会制度来让分布式环境中的多个节点达成共识，因此假设了一个叫做Paxos的希腊城邦，而该城邦通过民主议会制度来解决问题，这个制度就是分布式共识的解法，而这个解法（或算法）就用该城邦的名字来命名，这也是Paxos的由来。

关于Paxos算法

       本文是在阅读了Lamport的《Paxos made simple》、Wiki百科对于Paxos的介绍以及一些博主分享的基础上所形成的。文中包含了笔者思考的过程，Lamport对于算法的描述是偏数学的，所以需要自己不断的做延展和梳理，否则很容易被他有些不切实际的言语带偏，比如：议员认为收到了提案，等待最终的批准，但之前有人提出了设置的值，请查看，什么是最终的批准，之前的值该怎么判定，这些内容都需要读者自己理解，所以不同人理解的Paxos在主链路上会基本一致，但到了细节，就会不一样，这也是大家认为Paxos晦涩难懂的原因之一。

       我们读懂一个算法，目的是用它解决问题，这需要工程化的思考。笔者认为Lamport的工程能力不会很强，而且他对其数学表达有一种优越感，可能因为他是数学专业的。相比较而言，他没有Doug Lea那种学术和实践两开花的水平，所以在阐述Paxos时，他没有讲明它的主要数据结构有哪些，状态有哪些，所以就会造成工程实现Paxos一定是具有二义性的，因为它会融合工程实践者自身的一些思考在其中。

Raft算法对于数据结构和算法的描述就会比较到位，不同人实现的会基本类似。Raft算法也是解决分布式共识问题的，它被开发出来的原因是为了让大家更好的理解Paxos算法。

       那为什么还需要了解和掌握Paxos算法呢？Google Chubby的作者Mike Burrows说过，这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

       可以看出该算法对于分布式环境下的共识问题，是具有里程碑意义的。这好比我们定义了食物的功能是什么？当然食物的种类千千万，谁先说出最基本的东西，没有人会不承认它的重要性，因为它解决和阐明了大家都能看到的、最基本和最核心的问题。不是说这个问题有多难，而是人家就是很早阐述清楚了，而这是你的必由之路，你就得拜师，有点这个意思。因此，对于分布式共识是我们需要理解和掌握的，而Paxos算法是无法回避的。

       Lamport认识到Basic Paxos的低效，在Basic Paxos基础上提出了Multi Paxos和Fast Paxos，这两种变体，用于减少算法中的消息传递次数，提升算法效率。本文不涉及这两种算法，只会集中在Basic Paxos。

基础Paxos算法笔记

       本文阐述的内容基本和《Paxos made simple》一致，但会增加一些笔者的思考、示例和推导，是Paxos的学习笔记。

       9页笔记，记录的比较随意，但是已经可以做到从概念到初步实践的阐述（我所理解的）Paxos算法，该算法工程化的效率不会很高，因为有太多的交互，但是容错性做到了极致。在每页笔记的介绍过程中，会深入去讨论一下，原来论文中的表述存在的一些不清楚的地方，同时会结合多方资料和自己的思考，给出一个自己的认识。

       比如：Proposer选择了一个提案编号N，一个chose是多么的简单，但是如何选择的？是否会涉及到远程通信？还是在本地有一行记录？这些问题如果不深入思考，实际对于该算法的了解也就只能停留在纸面。因此，要理解该算法，就需要思考这些细节，猜测细节实施的方案以及背后的代价。

       接下来，按照笔记的顺序，我们开始吧！很多内容我会不止讲一遍，你一定能够跟得上！