Hycz's Blog
Life is a game. Why so serious?
Paxos学习笔记——overall
Posted by on August 16, 2011
一、一些废话
第一次听说Paxos算法，是在2011年的春节期间，与刘君吃饭时听到他提起的。后来，我渐渐了解到，Paxos乃是Google产品的重要基础，最初的使用是在Chubby中，后来似乎在Megastore中再次使用。
6月之后，既然GRE败了，那么还是先把开题的任务搞定。我觉得我开题其实是个巨大的坑，同组的其他人要么开了可以忽悠的题目，要么是别人已经做好了，但是boss不知道的题目。我开的题则是在我某天包夜，喝咖啡喝的恍惚的时候想到的，但是现在想一想，也不是怎么靠谱，甚至有可能毫无意义。无论如何，都要从Paxos算法的实现做起，刘君说，这个算法很难实现，确实如此。可笑的是，算法的实现已经很困难了，而且别人早已有了很多成功的Paxos实现，但是我却妄图在这些成功的方法上加上一些愚蠢的改动，完全是自虐。整个毕业设计的工作计划争取在放假结束前写完，这是后话
Paxos的文章很多，最为重要的自然是Lamport所写的那些文章（http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html），所以一开始我打算先把他的论文看完，但是，看了几天，我就发现这是一个极为困难的任务，首先，他的文章很多，其次，他的文章确实不太好懂。所以我退而求其次，转向了Paxos的wiki（http://en.wikipedia.org/wiki/Paxos_(computer_science)），wiki比较浅显易懂，而且涵盖了更多的内容，当我完成了这部分的工作之后，再去相应的论文中寻找更多的细节与证明。所以下面的内容大量参考wiki上的内容，许多渣翻译。
二、名字的由来与故事
来自Lamport虚构的希腊的Paxos岛群中所使用的立法一致系统（legislative consensus system）。
具体的故事是这样的（摘自中文Paxos wiki（http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95））：
为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的。
三、Safety and liveness properties，安全性和活性？好吧，我也不知道怎么翻
Paxos中定义了三条安全性质，并且保证在没出错时一直保证之：
- 非平凡性——Non-triviality
只有提议（propose）的值（value，下同，具体含义的理解在本节最后）才能被获知（learn）。 - 一致性——Consistency
只有一个值能被获知。这意味着两个不同的获知者不会得到不同的值。我的理解是一次Paxos执行中 - 活性——Liveness(C,L)
如果值C被提议了，那么最终获知者L将会得到某些值（如果足够多的处理者保持没有出错的话）。
看到这里，恐怕还是云里雾里，不知道这三条性质具体是指什么。这里先讲讲关于value的我的理解，value在这里是一个很抽象的概念，既可以是一个数字，也可以是一套方案，一系列操作，所以value的具体含义在于开发者针对什么问题使用了Paxos算法，此时，value的含义就是这个问题中需要保持一致的对象。
这三条性质保证了一致性的需要，所以Paxos算法其实就是围绕这如何保持这三条性质展开的。关于为何满足这三条性质就能保证一致状态，Lamport也给出了证明。
四、假设与定义
1、假设
Paxos的假设分为两方面，一方面是关于处理者的，一方面是关于网络的。我认为，这是由于假设中的限制非常少，才使得满足了这些假设的算法意义非凡。
关于处理者，processors，是指故事中的议员，或是真正的实现中的处理程序，节点。相关的假设如下：
- 处理者以任意速度进行处理
- 处理者会失效，无法工作
- 拥有稳定存储的处理者可以在失效之后再次加入Paxos
- 处理者不会勾结欺骗，即无拜占庭错误
关于网络，networks，是指故事中的消息传递机制，或是真正的实现中的网络系统，事实上，也就是互联网。相关假设如下：
- 处理者可以发送消息给其他的处理者
- 消息被异步地发送，并且花费任意长的时间才能收到
- 消息会丢失，顺序错误，重复
- 消息不会出现欺骗，即无拜占庭错误
2、处理者数量
一般来说，一个一致性算法的运行使用2F+1个处理者，并且可以容忍同时F个处理者的失效，即容忍少于一半的失效。然而，经过配置的话，这个协议也可以容忍更多的失效，只要失效不会产生地过快。
所谓不会失效地过快，是指不会同时一起失效，而是一个接一个地失效。这里提到的方法是使用备用处理者代替失效处理者。举例来说，5台服务器，原本可以容忍2台失效，现在使用如下，将3台作为活跃机使用，2台作为备用机使用，当活跃机失效时，就重新配置，让备用机代替活跃机工作，当然，前提是失效只会在重新配置完成后才发生，这样最终可以容忍3台失效。我认为，这样的方法实际上降低了服务器的可用性，意义不太大。
3、角色
终于到了一个很关键的地方，上面提到的处理者有不同的角色，不同角色的处理者作不同的处理动作，他们是：client, acceptor, proposer, learner, and leader。在实现时，往往一个处理者要同时扮演几个角色，这并不会影响协议的正确性，而且这也很平常，因为合并角色可以减少延迟，或者减少消息数量。
- 客户，Client
客户会向分布式系统发送请求，然后等待回应。例如，发往分布式文件服务器的写请求。 - 决议者，Acceptor
决议者是协议中的容错记忆体。一定数量的决议者被归为一组，称为额定数（Quorum）。任何发往决议者的消息都必须发往额定数量的决议者，任何来自决议者的消息都应该 由额定数量的决议者分别发出同个消息的拷贝，否则将会被忽略。简单来说，消息必须有Quorum份。 - 提议者，Proposer
提议者提议各异客户请求，尝试让决议者同意它，并且在发生冲突时作为协调者（Coordinator）推动协议继续进行。 - 获知者，Learner
获知者作为协议的副本因子，一旦一个客户请求被决议者所同意，那么获知者将会采取相应的行动，例如，执行请求并回应给客户。额外的获知者可以提供更高的可用性。 - 领导者，Leader
Paxos需要一个高阶的提议者（成为领导者）来推动协议的进行。有可能很多处理者都会认为自己是领导者，但是协议保证最终仅有一个会被选为领导者。如果两个处理者认为他们都是领导者，将会不停地提出冲突的更新请求，那么会拖延整个协议。安全性无论如何将会被保证。
4、额定数（Quorum）
额定数表示了Paxos的安全性，说明至少有一些存活的处理者知道结果。
额定数被定义为决议者集合中的一系列子集，并且这一系列子集中的任意两个子集的交集都不为空。典型的额定数是决议者的多数。比如，有决议者集合{A,B,C,D}，一个多数额定可以是其中任意的三个决议者：: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}。更一般化的情况是，可以给决议者赋予任意的正权值，此时，额定数就被定义为了子集总权值大于全集总权值的一半的那些子集。
5、提议编号与同意值（Proposal Number & Agreed Value）
每次尝试定义一个大家都同意的值，都是通过提议的形式来完成的。一个指定的提议者的每个提议都有一个唯一的提议编号。
五、典型实现方案
在大多数的Paxos实现方案中，只有三种角色：Proposer, Acceptor and Learner。这能显著降低消息复杂度，在不牺牲正确性的前提下。
通过合并角色，整个协议缩减成了一个有效的客户-主人-副本（client-master-replica）风格的部署，这是数据库社区的典型部署。使用Paxos系列方法的好处是安全性的保证。
一个典型实现的数据流将在Typical Multi-Paxos deployment中提到。
六、Paxos的系列算法
1990，Paxos算法就已经被Lamport所创立，但是直到1998年关于Paxos的论文才发表。之后有许多的工作围绕着Paxos展开，但是这都是围绕着Paxos的核心而做的修修补补，或者结合不同的情景与需求所做的改动，最为核心的仍然是Lamport最开始描述的Paxos，因为这个核心才是保证一致性的关键。
1、Basic Paxos
这个协议是Paxos系列中最基础的一个。每个Basic Paxos协议的实例都会决定一个输出值。协议可以进行很多轮（round），每轮有2个阶段（Phase）。当提议者无法与额定数量的决议者通讯时，提议者不应该启动Paxos。
描述如下（名称不翻了，不然感觉怪怪的）：
Phase 1a: Prepare
一个提议者（即领导者）创建一个提议，这个提议用一个数字N进行标识。这个数字必须比这个提议者曾使用过的提议编号都大。然后，它发送一个准备（prepare）消息（消息中包括了这个提议）给额定数量的决议者。
Phase 1b: Promise
如果决议者收到的提议编号N比任何之前收到的（来自任何提议者的）提议编号都大的话，那么决议者必须返回一个保证（promise），保证忽略之后收到的任何提议编号小于N的提议。如果一个决议者在之前已经同意了某个值，那么它在回应提议者的时候，必须附加上最新同意的提议编号以及相应的值。
否则，决议者可以忽略收到的提议。甚至可以不用回应它。然后，为了优化的目的，发送回一个拒绝（Nack）回应可以告诉提议者可以停止尝试在提议N上达到一致。
Phase 2a: Accept Request
如果一个提议者从决议者处收到了足够多的保证（额定数个），那么这个提议者需要给它的提议设定一个值（value）。如果某个决议者之前已经同意了某个提议的话，那么它已经将它同意的值发送给了提议者，这时，提议者必须将值设为已经收到的值中（在promise中一起返回的，都是各决议者已经同意的值）编号最大的提议的值。否则，它可以直接设定自己的独立的值。
然后，提议者发送一个请求接受（Accept Request）消息给额定数量的决议者，这个消息中，包含了提议中选择的值。
Phase 2b: Accepted
如果一个决议者（Acceptor）收到了提议N的接受请求消息，它必须接受它，当且仅当它还没有向一个编号大于N的提议进行保证时。这种情况下，它应该注册这个相应的值v，然后发送一个已接受（Accepted）消息给提议者和每个获知者。否则，它可以忽略这个接受请求。
每轮过程会在下面两种情况下失败：多个提议者发送了冲突的准备消息；或者是提议者没有收到额定数目的回应（保证或已接受）。在这些情况下，需要开始新的一轮，并使用新的更高的提议编号。
注意到当决议者接受一个请求时，他们也会告知提议者的领导。因此，Paxos也可以用于在一个集群的节点中选择一个领导者（Leader）。
下面是 Basic Paxos协议 的图示。注意在保证消息(Va,Vb,Vc)中返回的值在第一轮实例中通常是null，下面写出来是为了完整性。
Message flow: Basic Paxos
(one instance, one successful round)
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| |<---------X--X--X | | Promise(N,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(N,Vn)
| |<---------X--X--X------>|->| Accepted(N,Vn)
|<---------------------------------X--X Response
| | | | | | |
Basic Paxos中的出错情况
最简单的出错情况是冗余获知者的失效，或者一个决议者的失效，但此时仍有额定数量的决议者存活。这种情况下，不需要恢复操作，也不需要额外的几轮过程或几轮消息。如下所示:
Message flow: Basic Paxos, failure of Acceptor
(Quorum size = 2 Acceptors)
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| | | | ! | | !! FAIL !!
| |<---------X--X | | Promise(N,{Va,Vb})
| X--------->|->| | | Accept!(N,Vn)
| |<---------X--X--------->|->| Accepted(N,Vn)
|<---------------------------------X--X Response
| | | | | |
Message flow: Basic Paxos, failure of redundant Learner
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| |<---------X--X--X | | Promise(N,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(N,Vn)
| |<---------X--X--X------>|->| Accepted(N,Vn)
| | | | | | ! !! FAIL !!
|<---------------------------------X Response
| | | | | |
下一个出错情况是当提议者在提议了一个值之后，但是在达到共识前的时候失效了。忽略选择领导者的问题，例子如下：
Message flow: Basic Paxos, failure of Proposer
(re-election not shown, one instance, two rounds)
Client Leader Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(N)
| |<------------X--X--X | | Promise(N,{Va,Vb,Vc})
| | | | | | |
| | | | | | | !! Leader fails during broadcast !!
| X------------>| | | | | Accept!(N,Vn)
| ! | | | | |
| | | | | | | !! NEW LEADER !!
| X--------->|->|->| | | Prepare(N+1)
| |<---------X--X--X | | Promise(N+1,{Vn})
| X--------->|->|->| | | Accept!(N+1,Vn)
| |<---------X--X--X------>|->| Accepted(N+1,Vn)
|<---------------------------------X--X Response
| | | | | | |
最为复杂的情况是多个提议者相信自己是领导者。举例来说，当前的领导者失效了，并且在之后恢复了，但是其他的提议者已经重新选举了一个新的领导者。这个恢复了的领导者并不知道这件事，然后尝试开始新的一轮过程，但是这与当前的领导者冲突了。
Message flow: Basic Paxos, dueling Proposers
(one instance, four unsuccessful rounds)
Client Proposer Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(N)
| |<------------X--X--X | | Promise(N,{Va,Vb,Vc})
| ! | | | | | !! LEADER FAILS
| | | | | | | !! NEW LEADER (knows N)
| X--------->|->|->| | | Prepare(N+1)
| |<---------X--X--X | | Promise(N+1,{Va,Vb,Vc})
| | | | | | | | !! OLD LEADER recovers
| | | | | | | | !! OLD LEADER tries N+1, denied
| X------------>|->|->| | | Prepare(N+1)
| |<------------X--X--X | | Nack(N+1)
| | | | | | | | !! OLD LEADER tries N+2
| X------------>|->|->| | | Prepare(N+2)
| |<------------X--X--X | | Promise(N+2,{Va,Vb,Vc})
| | | | | | | | !! NEW LEADER proposes, denied
| | X--------->|->|->| | | Accept!(N+1,Vn)
| | |<---------X--X--X | | Nack(N+2)
| | | | | | | | !! NEW LEADER tries N+3
| | X--------->|->|->| | | Prepare(N+3)
| | |<---------X--X--X | | Promise(N+3,{Va,Vb,Vc})
| | | | | | | | !! OLD LEADER proposes, denied
| X------------>|->|->| | | Accept!(N+2,Vn)
| |<------------X--X--X | | Nack(N+3)
| | | | | | | | ... and so on ...
2、Multi-Paxos
典型的Paxos实现需要一个关于同意值（agreed value）的持续流（continuous stream），这些同意值用作分布式状态机的命令。如果每个命令都是一个Basic Paxos的实例的结果，那么这将意味着很大量的开销。
如果领导者相对稳定的话，phase 1就变得不再必要。因此，如果之后的实例都使用相同的领导者，那么phase 1就可以跳过。
为了达到这种方式，实例编号I要被包含在每个值（value）中。Multi-Paxos在保证容错的同时，将消息延迟（从提议到被他人得知）从4步延迟降到了2步延迟。
Message flow: Multi-Paxos, start
(first instance with new leader)
Client Proposer Acceptor Learner
| | | | | | | --- First Request ---
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(N,I,Vn)
| |<---------X--X--X------>|->| Accepted(N,I,Vn)
|<---------------------------------X--X Response
| | | | | | |
Message flow: Multi-Paxos, steady-state
(subsequent instances with same leader)
Client Proposer Acceptor Learner | | | | | | | --- Following Requests --- X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N+1,I,W) | |<---------X--X--X------>|->| Accepted(N+1,I,W) |<---------------------------------X--X Response | | | | | | |
典型Multi-Paxos实现
Paxos系列最常见的实现就是Multi-Paxos，特别是参加Paxos的处理者分别是提议者（Proposers），决议者（Acceptors）和获知者（Learners）。于是消息流可以被优化如下：
Message flow: Collapsed Multi-Paxos, start
(first instance with new leader)
Client Servers
| | | | --- First Request ---
X-------->| | | Request
| X->|->| Prepare(N)
| |<-X--X Promise(N,I,{Va,Vb,Vc})
| X->|->| Accept!(N,I,Vn)
| |<-X--X Accepted(N,I)
|<--------X | | Response
| | | |
Message flow: Collapsed Multi-Paxos, steady state
(subsequent instances with same leader)
Client Servers X-------->| | | Request | X->|->| Accept!(N+1,I,W) | |<-X--X Accepted(N+1,I) |<--------X | | Response | | | |
3、优化
很多的优化降低了消息的复杂度和大小。这些优化总结如下：
“可以以 额外的一个消息延迟 的代价获得消息数量的减少，方式是使用一个特别的获知者，当它发现一个值被选择之后，由它来通知其他的获知者。然后决议者只发送已接受（Accepted）消息给这个特别的获知者。在大多数的应用中，领导者和特别的获知者的角色通常是由相同的处理者所担当的。
“领导者可以只发送准备（Prepare）消息和请求接受（Accept!）消息给额定数量的决议者（而不是全部）。只要额定数中的所有决议者都能正常工作，并且可以和领导者和获知者通信，那么就没有必要让额定数之外的决议者做任何事。
“决议者不在乎被选择的是哪个值。他们仅仅对准备（Prepare）消息和请求接受（Accept!）消息做出回应，并在没有发生失效时保证只有一个值会被选择。然而，如果一个决议者确实获知了是哪个值被选择了之后，那么它可以把值储存在可靠稳定的存储器上，然后擦除它保存在那的任何其他信息。在这之后如果决议者又接到了准备消息或者请求接受消息，就可以略过Phase 1b和Phase 2b，而直接通知领导者它选择的值。
“领导者可以在其请求接受消息中发送值v的哈希（hash of v）给一些决议者，而不是发送整个值v。获知者将会或者哪个值被选择了，如果它从额定数量的决议者处收到了关于值v或者它的哈希的已接受（Accepted）消息，并且这些消息中至少有一条包含了v，而不是它的hash。然而，领导者可能会只接受了包含v的hash的保证（Promise）消息，而不是v的确切值，但是在它的Phase 2a中必须要使用v值。如果这种情况发生的话，领导者就不能执行Phase 2a，直到它与一些知道v的处理者通信并取得v值。
“提议者只可以发送提议给领导者，而不是所有的协调者（Coordinator）。然而，这需要把领导者选择算法的结果广播给所有的提议者，这是昂贵的开销。因此，更好的方案是发送提议给所有的协调者，在这种情况下，只有协调者内部需要知道领导者是谁。
“取代每个决议者发送已接受（Accepted）消息给每个获知者的方案，决议者可以发送已接受消息给领导者，然后领导者可以在一个值被选择时通知获知者。然而，这会增加一个额外的消息延迟。
“最后，观察到Phase 1对于第一轮（Round 1）是不必要的，第一轮的领导者可以从发送请求接受（Accept!）消息开始，请求接受消息中包含提议值（proposed value）。”
4、Cheap Paxos
Cheap Paxos继承了Basic Paxos，使用F+1个主处理者和F个辅处理者，能在每次失效发生后动态重新配置，能够容忍F个失效。
需要的处理者数量的减少，是以活力的损失为代价的；如果太多主处理者在短时间内失效，整个系统就需要暂停，直到辅处理者重新配置系统。在稳定的期间，辅处理者不参加协议的执行。
“只有两个处理者p和q，那么一个处理者不能辨别另一个处理者的失效是真的失效还是由于通信介质的失效。于是需要第三个处理者。然而，第三个处理者并不必加入到选择命令序列的任务中。它需要做的，是当p或者q失效时，它能够启动，当p或者q能够继续操作系统时，它又可以休息了。因此第三个处理者可以是小的/慢的/便宜的（small/slow/cheap）那个处理者，或者是一个主要投入到其他工作中去的处理者。”
Message flow: Cheap Multi-Paxos
3 main Acceptors, 1 Auxiliary Acceptor, Quorum size = 3, showing failure of one main processor and subsequent reconfiguration
{ Acceptors }
Proposer Main Aux Learner
| | | | | | -- Phase 2 --
X----------->|->|->| | | Accept!(N,I,V)
| | | ! | | --- FAIL! ---
|<-----------X--X--------------->| Accepted(N,I,V)
| | | | | -- Failure detected (only 2 accepted) --
X----------->|->|------->| | Accept!(N,I,V) (re-transmit, include Aux)
|<-----------X--X--------X------>| Accepted(N,I,V)
| | | | | -- Reconfigure : Quorum = 2 --
X----------->|->| | | Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->| Accepted(N,I+1,W)
| | | | |
5、Fast Paxos
Fast Paxos推广了Basic Paxos，降低了端到端消息延迟。在Basic Paxos中，从客户端请求到获知结果的消息延迟是3个消息延迟。Fast Paxos只要2个消息延迟，但是需要客户端发送请求到多个目标处。
直觉地，如果领导者没有用来提交的值，那么客户端可以直接发送一个请求接受（Accepted!）消息给决议者。决议者如同在Basic Paxos中一样进行回应，发送已接受（Accepted）消息给领导者，这里从客户端到获知者只要2个消息延迟。
如果领导者检测到了一个冲突，它会用以下的方法来解决冲突，它在新的一轮中发送请求接受（Accepted!）消息，在新的一轮中，可以正常接受（Accepted）。这个协调恢复方法（coordinated recovery technique）从客户端到获知者需要4个消息延迟。
当领导者发现恢复方法正在启动时，可以进行最后的优化，允许决议者自身进行冲突恢复。因此，非协调冲突恢复需要3个消息延迟（如果所有的获知者都是决议者的话，只需要2个消息延迟）。
Message flow: Fast Paxos, non-conflicting
Client Leader Acceptor Learner | | | | | | | | | X--------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | X------------------->|->|->|->| | | Accept!(N,I,W) | |<---------X--X--X--X------>|->| Accepted(N,I,W) |<------------------------------------X--X Response(W) | | | | | | | |
Message flow: Fast Paxos, conflicting proposals
Conflicting proposals with uncoordinated recovery. Note: the protocol does not specify how to handle the dropped client request.
Client Leader Acceptor Learner | | | | | | | | | | | X------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | | | | | | | | | | | !! Concurrent conflicting proposals | | | | | | | | | !! received in different order | | | | | | | | | !! by the Acceptors | X--------------?|-?|-?|-?| | | Accept!(N,I,V) X-----------------?|-?|-?|-?| | | Accept!(N,I,W) | | | | | | | | | | | | | | | | | | !! Acceptors disagree on value | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | | !! Detect collision & recover | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |
Message flow: Fast Paxos, collapsed roles
(merged Acceptor/Learner roles)
Client Servers | | | | | | | | X->|->|->| Any(N,I,Recovery) | | | | | | | | | | | | !! Concurrent conflicting proposals | | | | | | !! received in different order | | | | | | !! by the Servers | X--------?|-?|-?|-?| Accept!(N,I,V) X-----------?|-?|-?|-?| Accept!(N,I,W) | | | | | | | | | | | | !! Servers disagree on value | | X--X->|->| Accepted(N,I,V) | | |<-|<-X--X Accepted(N,I,W) | | | | | | | | | | | | !! Detect collision & recover |<-----------X--X--X--X Response(W) | | | | | |
6、Generalized Paxos
推广的一致性（generalized consensus）探讨了分布式状态机（distributed state machine）的操作和用来处理状态机一致性的一致性协议（consensus protocol）之间的关系。主要的研究当冲突的提议可以以任意顺序被状态机接受时，是一致性协议的优化。例如，由冲突的提议所提议的操作是状态机中的可交换操作。
在这种情况下，冲突的操作可以都被接受，并且避免了解决冲突和重新提议被拒绝的操作所花费的延迟。
这个概念被进一步推广到可交换操作的持续增长集 上，某些这样的持续增长集被认为是稳定的（stable）（因此可以被执行这个协议）。协议追踪这些操作集，确保在允许任何不可交换操作变稳定（stable）前，一个集合中的所有提交的可交换操作都是稳定的。（这段没太懂。。。原文如下：This concept is further generalized into ever-growing sets of commutative operations, some of which are known to be stable (and thus may be executed). The protocol tracks these sets of operations, ensuring that all proposed commutative operations of one set are stabilized before allowing any non-commuting operation to become stable. 关键在于这个stable的理解上，关于stable的词出现了2个，一个是形容词stable，一个是动词stabilize，那么stabilize这个词的意思是将所谓的operation执行，然后把执行的结果输出到稳定的存储中去么，然后stable就是指执行结果已被输出到稳定存储的状态。）
举例
- 为了阐明Generalized Paxos，这个例子由以下部分进行表示：两个并行执行的客户端间的消息流，以及一个在2个相互独立的注册地址（A和B）处执行read/write注册操作的状态机。
- 可交换性表（Commutativity Table）；做标记的地方表示有干扰：
Read(A) Write(A) Read(B) Write(B)
Read(A) | | X | | |
Write(A)| X | X | | |
Read(B) | | | | X |
Write(B)| | | X | X |
- 操作的提交序列（全局顺序）：
1:Read(A)
2:Read(B)
3:Write(B)
4:Read(B)
5:Read(A)
6:Write(A)
7:Read(A)
- 通过交换之后，一个可能的排列：
{ 1:Read(A), 2:Read(B), 5:Read(A) }
{ 3:Write(B), 6:Write(A) }
{ 4:Read(B), 7:Read(A) }
- 观察结果：
- 5:Read(A) 可以交换到3:Write(B)/4:Read(B) pair之前.
- 4:Read(B) 可以交换到 the 3:Write(B)/6:Write(A) pair之后.
- 实际上，交换只会发生在操作是同时提交的情况下.
Message flow: Generalized Paxos (example)
Responses not shown. Note: message abbreviations differ from previous message flows due to specifics of the protocol, see（Generalized Consensus and Paxos）for a full discussion.
{ Acceptors }
Client Leader Acceptor Learner
| | | | | | | | !! New Leader Begins Round
| | X----->|->|->| | | Prepare(N)
| | |<-----X--X--X | | Promise(N,null)
| | X----->|->|->| | | Phase2Start(N,null)
| | | | | | | |
| | | | | | | | !! Concurrent commuting proposals
| X--------?|-----?|-?|-?| | | Propose(ReadA)
X-----------?|-----?|-?|-?| | | Propose(ReadB)
| | X------X-------------->|->| Accepted(N,<ReadA,ReadB>)
| | |<--------X--X-------->|->| Accepted(N,<ReadB,ReadA>)
| | | | | | | |
| | | | | | | | !! No Conflict, both accepted
| | | | | | | | Stable = <ReadA, ReadB>
| | | | | | | |
| | | | | | | | !! Concurrent conflicting proposals
X-----------?|-----?|-?|-?| | | Propose(<WriteB,ReadA>)
| X--------?|-----?|-?|-?| | | Propose(ReadB)
| | | | | | | |
| | X------X-------------->|->| Accepted(N,<WriteB,ReadA> . <ReadB>)
| | |<--------X--X-------->|->| Accepted(N,<ReadB> . <WriteB,ReadA>)
| | | | | | | |
| | | | | | | | !! Conflict detected, leader chooses
| | | | | | | | commutative order:
| | | | | | | | V = <ReadA, WriteB, ReadB>
| | | | | | | |
| | X----->|->|->| | | Phase2Start(N+1,V)
| | |<-----X--X--X-------->|->| Accepted(N+1,V)
| | | | | | | | Stable = <ReadA, ReadB> .
| | | | | | | | <ReadA, WriteB, ReadB>
| | | | | | | |
| | | | | | | | !! More conflicting proposals
X-----------?|-----?|-?|-?| | | Propose(WriteA)
| X--------?|-----?|-?|-?| | | Propose(ReadA)
| | | | | | | |
| | X------X-------------->|->| Accepted(N+2,<WriteA> . <ReadA>)
| | |<--------X--X-------->|->| Accepted(N+2,<ReadA> . <WriteA>)
| | | | | | | |
| | | | | | | | !! Leader chooses order W
| | X----->|->|->| | | Phase2Start(N+2,W)
| | |<-----X--X--X-------->|->| Accepted(N+2,W)
| | | | | | | | Stable = <ReadA, ReadB> .
| | | | | | | | <ReadA, WriteB, ReadB> .
| | | | | | | | <WriteA, ReadA>
| | | | | | | |
Generalized Paxos vs. Fast Multi-Paxos
上面的数据流显示了Generalized Paxos在10个消息延迟中执行了关于7个值的协议。对相同的提议值序列，Fast Multi-Paxos则需要15-17个延迟（3个需要不协调恢复的并发提议，每个需要3个延迟，加上至少2个延迟给最终需要重新提交的3个被拒绝的提议，并发的重提议可能还要加上2个额外的延迟）。
7、Byzantine Paxos
Paxos可以被扩充以支持参加者会发生的任意错误，包括撒谎（lying），消息伪造（fabrication of messages），与其他参加者同谋（collusion with other participants），选择性不参与（selective non-participation），等等。这些类型的错误被称为拜占庭错误（Byzantine failures），Lamport给出了结局方案。
Byzantine Paxos增加了额外的一个消息（verify），用来分发已知信息，以及核实其他处理者的动作。
Message flow: Byzantine Multi-Paxos, steady state
Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I,V) | | X<>X<>X | | Verify(N,I,V) - BROADCAST | |<---------X--X--X------>|->| Accepted(N,V) |<---------------------------------X--X Response(V) | | | | | | |
Fast Byzantine Paxos溢出了这个额外的延迟，因为客户端可以直接发送命令给决议者。
注意到在Fast Byzantine Paxos中的已接受（Accepted）消息被发送给所有的决议者和获知者，而Fast Paxos仅将此消息发送给获知者。
Message flow: Fast Byzantine Multi-Paxos, steady state
Client Acceptor Learner | | | | | | X----->|->|->| | | Accept!(N,I,V) | X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST |<-------------------X--X Response(V) | | | | | |
这个失效场景与两个与两个协议相同；每个获知者等待F+1个从不同决议者处发出的同样的消息。如果这没有发生，那么决议者本身也会知道（因为他们在广播轮（broadcast round）中交换各自的消息），并且正常的决议者会再次广播这个同意值：
Message flow: Fast Byzantine Multi-Paxos, failure
Client Acceptor Learner
| | | ! | | !! One Acceptor is faulty
X----->|->|->! | | Accept!(N,I,V)
| X<>X<>X------>|->| Accepted(N,I,{V,W}) - BROADCAST
| | | ! | | !! Learners receive 2 different commands
| | | ! | | !! Correct Acceptors notice error and choose
| X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST
|<-------------------X--X Response(V)
| | | ! | |
Virtually Synchronous Paxos（虚拟同步Paxos）
虽然虚拟同步模型与Paxos对于创建状态机副本服务和简单应用来说，有时看起来是相反方向的选择，但是近来的工作（“Virtually Synchronous Methodology for Dynamic Service Replication”）证明了合并两种模型到一个统一方案的可能性。这个方法使用虚拟同步来支持执行时期（execution epochs），在执行时期内，成员（membership）被一致性协议决定并被是稳定的（stable）。于是，容错协议就被定义在了每个时期的基础上。这个方法相比于其他方法，加强了虚拟同步模型，使其在动态Paxos服务成员（making the membership of a Paxos service dynamic）的方面，提供了更好的性能。
七、最后的吐槽
首先是我的效率太低了！这篇日志从7月底一直写到了8月中旬，虽然中间经过了开年会，放假等等，前前后后有20多天，但是，主要还是我磨磨蹭蹭的原因，如果拼命写，估计7月底就写完了。。。
嘛，也不能说是写完了，应该是翻译完了，开头还想写点自己的话，后来写到具体的算法介绍时就开始照着wiki翻译了，然后强迫症让我硬生生翻译完了。。。
最后，英转中总是这么蛋疼，讲话思维是反的，于是我的渣翻译就跟机翻一样，感觉还是完全不能看啊！
Hycz's Blog 
it is really a great blog!!! thanks
I’ve benefited a lot. Thank you very much.