前言分布式确实是个有趣的话题，只要你留心，分布式在生活中无处不在。悟空哥是从一篇写得非常用心的技术论文开始学习分布式的，这篇文章获得了论文的第一名。感谢掘金社区提供的平台。从本文开始，将解释八种分布式协议/算法。本文主要讲解Paxos共识算法。本文主要内容如下：本文主要内容Paxos算法Paxos是分布式算法的老大哥。可以说，Paxos是分布式共识的代名词。最常用的分布式共识算法都是在它的基础上改进的。比如Raft算法（后面会介绍）。所以要学习分布式算法，首先要学习Paxos算法。Paxos算法主要包括两部分：基本Paxos算法：如何在多个节点之间就某个值达成共识。（这个值称为ProposalValue）Multi-Paxos算法：执行多个BasicPaxos实例，对一系列值达成共识。BasicPaxos算法是Multi-Paxos思想的核心。Multi是多次的意思，也就是说多次执行BasicPaxos算法。所以BasicPaxos算法是重中之重。三国之战在三国的刘备集团中，有两大军师：诸葛亮和庞统，都非常的厉害。当他们对多个将军有不同的作战计划时，他们如何达成一致？Paxos中一共有三种角色：proposer、receiver、learner。让我们以更一般的方式解释Paxos算法。让我们穿越回东汉末年，看看Paxos算法是如何在刘备集团的大营中攻打曹操的。刘备阵营人物介绍：领主姓名：刘备，为委托人或委托人。两位军事顾问：诸葛亮和庞统，作为提议者。三位将军：关羽、张飞、赵云，为受赠人。两个公务员：法正和马良，作为学习者。刘备集团提案人提出投票的价值。访问和协调。收到客户端请求后，可以发起两阶段提交进行共识协商。映射到上面的故事，军师是用来部署作战计划的。接受者对每个提议的值进行投票并存储接受的值。投票协商和存储数据，对提议的值进行投票，并接受共识值，存储和保存。映射到上面的故事，将军习惯于接受军师的作战计划。事实上，集群中的所有节点都作为接收者，参与共识协商，接受和存储数据。学习者（Learner）被通知投票结果，接受共识值，存储数据，不参与投票过程，即不参与共识协商。映射到上面的故事，就是两个公务员充当备胎记录作战计划。AcceptororProposer为什么说节点可以充当acceptor或者proposer呢？上篇文章讲解BASE协议的时候，讲到了两阶段提交协议。其中有协调者的身份，协调者可以是接受者，也可以是提议者。作为接收者，接收来自客户端的消息。比如诸葛亮需要接受刘备的作战要求。作为提议者，发起两阶段提交。然后该节点与其他节点作为接收者进行共识协商。比如诸葛亮要向刘备总结最后的作战方案。如下图所示，节点1作为提议者和接受者，节点2和节点3作为接受者。节点既是提议者又是接受者诸葛亮VS庞统三国有刘备集团（占领西蜀）、曹操集团（占领北方）、孙权集团（占领江南）.诸葛亮和庞统作为提议者，向三位接受者提出了作战计划。提案中有两个属性：提案编号。每次军师提出建议，都会有一个数字，这里用n表示。建议值，即作战计划，在这里用v表示。所以建议是[n,v]。诸葛亮的作战计划是北攻曹操，庞统的作战计划是南攻曹操。关羽、张飞、赵云先后接到了作战计划。谁应该听？这是一个共识问题。Paxos算法分两个阶段达成共识。准备（Prepare）阶段和接受（Accept）阶段。在准备阶段，诸葛亮和庞统作为提议者向所有接收者（关羽、张飞、赵云）发送准备请求，包括作战计划编号（提议编号），但不包括作战计划（提议值）.发送准备请求提出者诸葛亮先发送编号为1的作战计划准备请求，庞统发送编号为2的作战计划准备请求，接收者关羽（节点X）收到作战计划准备请求8:00诸葛亮提出，10:00庞统提出作战计划要求。接收方张飞（节点Y）9:00收到诸葛亮的作战计划准备请求，11:00收到庞统的作战计划准备请求。接收方赵云（Z节点）12:00收到庞统的作战计划准备请求，13:00收到诸葛亮的作战计划准备请求。准备阶段——发送准备请求注意：准备阶段不需要携带具体的作战计划，所以作战计划可以为空，但提案号必须有。收到准备请求（第一次）按照接受请求的时间顺序，关羽和张飞收到了诸葛亮的请求[1，空]，赵云收到了庞统的请求[2，空]。准备阶段-收到准备请求（第一次）因为关羽和张飞之前没有收到过提议，所以回复没有提议。也就是告诉诸葛亮，他不再响应编号小于等于1的准备请求，也不再通过编号小于1的提案。响应的时间点是14:00和15:00。而赵云之前没有收到过求婚，所以回了一个暂时没有求婚的回应。也就是告诉庞统，他不再响应编号小于等于2的准备请求，也不会通过编号小于2的提案，响应的时间点是16点。Receivethepreparationrequest(secondtime)准备阶段——收到准备请求（secondtime），对于庞统的准备请求，关羽和张飞收到的准备请求编号为2，2号大于之前收到的3号。1、关羽和张飞没有通过任何提案，所以还是会回复庞统一个没有提案的回应。也就是说，庞统将不再响应编号小于或等于2的准备请求，也不会通过编号小于2的提案。响应时间点为14:00和15:00。赵云最终收到诸葛亮的1号准备请求后，由于1号小于之前响应的准备请求的提案2号，直接放弃了准备请求，没有响应，如图？上图。接受阶段发送接受请求诸葛亮和庞统收到准备响应后，分别发送接受请求，如下图：接受阶段-发送接受请求诸葛亮收到大部分接收者（关羽和张Fei)，根据响应中提案编号最高的提案的值，设置accept请求中的值。因为关羽和张飞返回的准备回复还没有提案，所以提案编号还是发送为1，提案值为北方的接受请求，代表从北方进攻曹操。发送时间为15:00和16:00后1分钟。为什么是15点后1分钟？因为只要满足大部分接收者的准备请求，就可以发送接收请求。关羽和张飞是14:00和15:00回复的，所以15:00以后可以发。庞统在收到大部分接收者（关羽、张飞、赵云）的准备回复后，根据回复中提案编号最大的提案的价值来设置接受请求中的值。由于关羽、张飞、赵云没有提案就回复了准备回复，所以他们还是发送了提案编号2，提案值为南征求，代表南下进攻曹操。发送时间点为18:00、19:00和20:00。关羽、张飞、赵云在接到诸葛亮、庞统的录取请求后，会进行如下处理，如下图：录取阶段——收到关羽的录取请求，张飞、赵云收到诸葛亮发来的提案[1，北]，诸葛亮的提案被否决了，因为提案编号1小于他们承诺可以通过的最低提案编号2。而当他们收到庞统送来的[2，南]的提议时，因为2号不小于之前承诺的2号，他们就通过了庞统的[2，南]提议，于是关羽、张飞、赵允之战计划是从南方进攻曹操。达成了共识。学习者上台当接受者批准提案时，所有学习者都会收到通知。当learner发现大部分acceptor都通过了某个proposal，那么learner也会通过这个proposal，接受这个proposal的值。也就是说，在关羽、张飞、赵云达成共识后，学法正、马良也采取了南下进攻的作战方案。总结BasicPaxos也是通过两阶段提交协议来达成共识的。准备阶段、验收阶段。如果你不知道两阶段提交协议，你可以阅读我之前的文章。《用太极拳讲分布式理论，舒服!》BasicPaxos不仅实现了共识，还实现了容错。当少于一半的节点发生故障时，集群可以正常运行。文章反复强调了大多数节点同意的原则，这个原则赋予了BasicPaxos容错能力。提案编号代表优先级，保证三个承诺：如果prepare请求的提案编号小于或等于acceptor已响应的prepare请求的提案编号，则acceptor承诺不响应该prepare请求的提案编号准备请求。如果接受请求中提案的提案编号小于接受者已回复的准备请求中的提案编号，则接受者承诺不采纳该提案。如果接受者之前已经通过了一个提案，则接受者承诺将已经通过的编号最高的提案包含在对准备请求的响应中。加分题如果关羽和张飞通过了提案[2，南]，但是赵云没有通过任何提案，当第三位军师简庸提出一个提案，编号8，作战计划是攻曹曹从东，也是【8、董】的作战计划，那么关羽、张飞、赵云最后的作战计划是什么？本文转载自微信公众号《悟空聊天架构》，可通过以下二维码关注。转载本文请联系悟空聊天架构公众号。
