分布式系统Paxos算法

这是1个有关Paxos算法非常形象的讲授与示范。Paxos是能够基于1大堆完全不可靠的网络条件下却能可靠肯定地实现共鸣1致性的算法。也就是说：它允许1组不1定可靠的处理器（服务器）在某些条件得到满足情况下就可以达成肯定的安全的共鸣，如果条件不能满足也确保这组处理器（服务器）保持1致。

甚么是共鸣？

　　具体来讲是这样：散布式系统中由于网络之间通讯可能会中断，虽然几率很低，但是没有100%完善的网络因此，依托网络通讯的计算机之间要达成共鸣就比较困难，假定有X, Y和Z3台计算机谋划在周1攻击人类世界，它们的攻击计划是只要所有计算机可用于战役时就1起进行攻击，不落下任何1台机器，但是当他们决定具体甚么时间开始攻击时，在这个关键问题上常常会出错。

　　1个基本问题是，每台机器都有自己的攻击时间建议，计算机X可以建议在08:00时间，由于这个时间正是周1凌晨，而人们刚刚过完狂欢的周末休息天，但是计算机Z认为13:00比较好，理由固然也有1大堆，让这3台计算机基于某个时刻达成共鸣是非常困难的，因此，也给人类反击留下了机会。

　　另外1个情况是，这3台计算机是位于世界不同的位置，之间通讯也许通过电缆或其他不太可靠的网络装备通讯，如果X建议在08:00，它必须确认它的这个建议能够到达活着的Y和Z，以避免1个人战役。

问题是：我们不能准确地知道某个计算机的延迟的缘由：是由于性能慢了还是已是完全死机不能用？

　　那末，X怎样知道其他两个计算机是可用的呢？也就是说，当X和其他两个计算机通讯发现得到响应要过很长时间，它不能肯定这两台计算机到底还能不能继续活下去，或许这次通讯有延迟了，下1次它们又活过来了没有延迟了，或许下次延迟更长了1点，或许下次延迟略微短了1点，这些随机几率问题使得X不能肯定Y和Z究竟是出了甚么问题造成延迟的，是由于处理了某个特别耗费CPU的任务还是由于死锁等缘由？固然，有些天真的设计者会说，只要我们将性能监控到位，如果延迟超过1定时间，我们人工参与告知X确切情况就能够，那末这类人工参与的散布式系统不是1个天然自洽的自动化系统了，不在我们讨论范围以内，而且这样的系统会让人疲于奔命。

　　由于X不能肯定Y或Z是不是可用，所以X仅仅只能和Y与Z中1台基于攻击时间达成共鸣，就没法完全3台机器全部投入战役的计划。注意的是，X Y Z3台中任何1台都可能会出现延迟，这就造成了3台机器之间任何通讯都是没法确认可靠的，比如X发出消息给Z，Z确认后回执给X，但是这段时间X突然死机了，那末Z要等待X多长时间才能知道它收到确认呢？还是再次等待X回复确认的确认，这样无穷循环下去也不能解决它们之间通讯可能出现随机不可靠的问题。

　　所有关键问题在于：由于这3台机器之间通讯是没法保证100%可靠，它们就不能就任何事情达成共鸣。

　　下面以散布式拍卖案例说明这类情况和Paxos的基本原理？

　　在传统拍卖场景中，价高者先得，这些拍卖者都是在同1个房间，彼此能够直接看得到对方的报价，如果我们假定散布式拍卖是将这些拍卖者分离到不同的地方，这样我们可以用拍卖者之间的联系摹拟散布式计算机之间的通讯。

　　假定拍卖者各自在自己家里拍卖，通过邮局信件发出自己的拍卖信息，拍卖者之间除非等到邮局投递人告知他们彼此之间的报价，否则是没法知道对方报价的。如果邮局信件投递这个环节出了问题，投递速度慢了乃至没法投递了，那末全部拍卖程序就没法继续进行下去。

Paxos解决共鸣思路

　　Paxos是1个解决共鸣问题consensus problem的算法，现实中Paxos的实现和成为1些世界级软件的心脏，如Cassandra, Google的 Spanner数据库, 散布式锁服务Chubby. 1个被Paxos管理的系统实际上谈论的是值 状态和跟踪等问题，其目标是建造更高可用性和强1致性的散布式系统。

　　Paxos完成1次写操作需要两次来回，分别是prepare/promise, 和 propose/accept：

　　第1次由提交者Leader向所有其他服务器发出prepare消息要求准备，所有服务器中大多数如果回复诺言许诺就表示准备好了，可以接受写入；第2次提交者向所有服务器发出正式建议propose，所有服务器中大多数如果回复已接收就表示成功了。

　　为了详细描写这个两段进程，首先让我们定义1下我们将使用的1些名词术语：

• 1个进程是系统中计算机的1个. 人们使用有关复制或节点等词语表达，都差不多。
• 1个客户端是属于系统中1个成员的计算机，但是询问系统值是甚么或要求系统获得1个新的值。

　　Paxos构建散布式数据库的小片断: 它仅仅实现进程将1个新的东西精确地写入系统中，进程是由Paxos的1个实例管治，可以失败或不知道任何东西、或大多数进程都知道1个一样的值，这就是共鸣，Paxos其实不真的告知我们如何用它来构建数据库或类似的东西，它只是负责独立节点之间通讯的进程， 这些进程服务器会基于1个新值履行决定，Paxos会存储1个值数据，只是1次性的，1旦你第1次设置以后就不能再改变它。

Paxo读操作

　　其实Paxos精华是在写操作，将读操作放在写操作前面讲授，是侧重Paxos以大多数服务器达成共鸣为重要标志，通过读取判断是不是达成共鸣这1状态。

　　为了从Paxos系统中读取1个值数据，客户端会要求读取所有进程中存储确当前值，然后从大多数进程服务器中取得这个值，如果数量凑不够大多数或没有足够的客户端响应，读取操作失败，下面图示你会看到1个客户端询问其他节点他们的值是多少，这些节点返回值给客户端，当客户端取得了大多数节点的响应，返回的值都是一样的，它就算成功地读操作了，并顺便保存读结果。

　　与单节点系统(只有1台服务器)相比这有些奇怪，这两个系统中，客户端都需要视察系统已决定状态，但是在非散布式系统中像MySQL或1个memcached服务器中, 客户端只需直接向标准的状态存储的服务器地址获得状态便可，在简单的Paxos中, 客户端也是一样的方式视察状态，但是由于并没有标准的状态存储的服务器地址，它需要询问所有的成员，以便能够肯定唯一1个会报告值数据，实际上是大多数节点都持有的值数据，如果客户端询问1个节点，有可能这个节点进程已过期，得到了毛病的值数据，进程失效过期的缘由有很多：由于不可靠的网络致使本应投递到它们的消息丢失了；或他们或许当机然后使用了1个过期状态恢复；或算法还在运行计算中，进程并没有正好得到消息等等。在现实中使用Paxos实现时，其实不需要每一个节点都进行1次读取，会有更好的读取方式，但是他们都是拓展的原始 Paxos 算法。

Paxos写操作

　　当1个客户端要求写入系统1个新值时，让我们看看Paxos让我们集群的进程都做了甚么？下面的进程都是只有1个值的写入，终究我们能用这个进程作为原始数据，允许值数据在彼此之间1个个设置，但是基本的Paxos算法管治了1个新值数据的写操作流程， 然后做重复的事情。

　　首先Paxos管理的系统中1个客户端要求写入1个新值，客户端这里如图所示是红圈，其它进程是蓝圈， Paxos能保证客户端发送它们的写要求到Paxos集群中任何成员, 这里演示中客户端随机挑选进程中任意1个，这类方式是重要且奇妙的，意味著没有任何单点风险，意味着我们的Paxos管治系统能继续保持在线可用，不管任何1个节点当机或其他不可用缘由无响应。如果我们设计1个特定节点作为“推荐人proposer”或 "the master" 等, 如果这个主节点死机，那末全部系统就崩溃了。

　　当写要求被接受后，Paxos进程会接受这个写新值到系统中要求“建议”， “建议”是Paxos中1个正式概念: 向1个Paxos管治的系统建议可能会成功或失败，需要步骤来确保共鸣能够达成维系，这个建议以准备消息从那些与客户端连接的进程节点们被发往全部系统。

序列号

　　这个准备消息保存在被建议的值数据中，它们也称为序列号sequence number，序列号是由建议进程产生的，它定义了接受进程应当准备接受带有序列号的建议，这个序列号是关键: 它用于表明新旧建议之间的区分，如果两个进程试图取得需要设置1个值，Paxos认为最后1个进程应当有优先权，这样让进程分辨哪一个是最后1个，这样它就可以设置最新的值。

　　这些接受的进程能够进行在系统中关键的检查：这个在到来的准备消息中序列号是我见过的最高级别吗？如果是，那就很cool, 我能准备好接受将要到来的值数据，那就不要管之前听到的任何其他值数据了，你能看到这个进程在右侧演示中：客户端每隔1段向1个进程建议1个新值，这个进程发送准备消息给其他进程，然后那些进程注意到这是1个成功的更高的超过旧的新序列号，然后就放手那些旧建议。

　　这里有1个顺序的设计(先发送准备消息)，这是为避免单点风险，如果没有这个顺序，Paxos中成员就没法分辨哪一个建议是他们可以有信心肠准备接受的。

　　我们不能想象有另外不同的共鸣算法，不是依照以下步骤：首先发送第1个消息询问其他进程，以确保将设置的新值是最新的值，虽然方式可以再简单些，但是可能就不能满足共鸣算法安全的需求了，如果两个进程正好同时建议不同的值，以下所示：

　　大自然常常会这样欺骗我们，每一个包都能另外1半的进程相信它们接受的或许是正确或许是毛病的值，系统将进入1个僵局，存在两个相同数量的组却有不同的值，那末就没法肯定大多数这个概念了，这个僵局能够被第1个Paxos消息避免，由于Paxos的序列号，那些有问题的建议将有被其他更低的序列号，这样序列号更高的建议就会绝不含糊地被大多数进程接收，它们也首先取得了更高的序列号，然后如果接遭到更低的序列号就会谢绝，Paxos 就是这样通过用序列号控制全部系统的时间节奏。

　　注意：保证没有两个建议使用相同的序列号是很重要的，这是确保他们的顺序，这样每一个序列号只有1个建议，这样才能比较两个建议，实现Paxos时，全局唯1有序的序列号实际是精确系统时间和集群中节点数量的拷贝，随着时间不断增加，历来不会重复。

Paxos第1阶段：准备Perpare/诺言Promises

　　Paxos的第1阶段是prepare/promise，准备阶段就是将建议值发送到各个目标节点。

　　当建议被发到目标节点后，进程会会检查建议中的序列号，是不是是它们见到过的最高级，如果是最高级，它们会发出1个promise不再接受比这个新序列号更旧的建议了，这个诺言promise作为消息从许下诺言的进程发到提交建议新值的进程服务器，这个诺言消息给提交建议的进程后，提交建议的进程需要自己统计1下有多少其他进程已发回它们的诺言promise了，如果判断数量上是不是到达大多数？如果大多数进程已同意接受这个建议或更高级序列号的建议，这个提交建议的进程就可以知道它取得了发言权(由于有大多数支持)，这样就开始讲话，算法中的下1步处理将可能进行；如果回复诺言的节点数量没有到达大多数，也就是共鸣没有达成，这样这个节点提交的建议将退出，客户端要求的写操作失败。

　　为了决定1个建议是不是已有足够的回复诺言promises, 提交建议者只是统计1下它接遭到的promise消息数量，然后和全部系统中节点服务器数量比较1下，“足够”意味着大多数(N/2 + 1)个进程服务器在某段时间内都回复了诺言promises。如果超过1半的进程服务器没有返回诺言，这意味着这个建议没有被大多数通过，那末在前面描写的读算法中就不能满足大多数的要求，也就不能达成共鸣，这个建议就退出。其他包括网络分区毛病也可能会禁止大多数达成共鸣，

第2阶段：Paoxs接纳Acceptance