Flexible Paxos: Quorum Intersection Revisited
0x00 引言
再来看一篇关于Paxos变体的论文，这篇讲的是Flexible Paxos这样的一个变体。与前面的EPaxos侧重点在消除稳定/指定的Leader/Master的设计不同，Flexible Paxos(FPaxos)的问题聚焦在了Quorum这个问题上面。基本的Paxos算法总结为，
Phase 1 - Prepare & Promise
* i. A proposer selects a unique proposal number p and sends prepare(p) to the acceptors.
* ii. Each acceptor receives prepare(p). If p is the highest proposal number promised, then p is written to persistent storage and the acceptor replies with promise(p’,v’). (p’,v’) is the last accepted proposal (if present) where p’ is the proposal number and v’ is the corresponding proposed value.
* iii. Once the proposer receives promise from the majority of acceptors, it proceeds to phase two. Otherwise, it may try again with higher proposal number.
Phase 2 - Propose & Accept
* i. The proposer must now select a value v. If more than one proposal was returned in phase 1 then it must choose the value associated with the highest proposal number. If no proposals were returned, then the proposer can choose its own value for v. The proposer then sends propose(p,v) to the acceptors.
* ii. Each acceptor receives a propose(p,v). If p is equal to or greater than the highest promised proposal number, then the promised proposal number and accepted proposal is written to persistent storage and the acceptor replies with accept(p).
* iii. Once the proposer receives accept(p) from the majority of acceptors, it learns that the value v is decided. Otherwise, it may try phase 1 again with a higher proposal number.
Paxos算法的Quorum策略在上面的两个阶段都是多数(称之为Majority Quorum)，即Prepare和Propose都是得到多数的回应。而FPaxos基于一个这样的观察，这里只要保证两个阶段有交集即能保证算法的正确性(需要在加上算法其它的一些变化，Paper中只将了Quorum策略，不过这样改的话应该还是需要算法的其它操作改动)，提出了两种新的Quorum的策略。Paper中称两个阶段的Quorum分为为Q1、Q2。
0x02 两种Quorum策略
Simple Quorums
Simple Quorums的方式让人联想到Dynamo中使用的Quorum的策略。在这种方式中，FPaxos要求就是 Q1 + Q2 > N。考虑到实际的应用，这里一般是Q2 < N/2，这样就要Q2 < Q1。这几个值至少满足Q1 = N − Q2 + 1。这样是不能够容忍的副本故障的数量为Q2 − 1。而在Q2到N − Q2副本故障的时候，系统还可以进行复制的操作。
... As has been previously observed, we do not need to send prepare and propose messages to all acceptors, only to at least |Q1| or |Q2| acceptors. If any of these acceptors do not reply, then the leader can send the messages to more acceptors. This reduces the number of messages from 4 × N to (2 × |Q1|) + (2 × |Q2|).
Grid Quorums
Grid使用了一种“巧妙”的方法，可以使得Q1 + Q2 < N也可以满足Q1和Q2会有交集的。这里有N1 × N2 = N(N1、N2为行、列)。如果Q1为这个Grid的一个一行，则如果是Q2是一列的话，就可以保证两者存在交集。这样可以容忍故障的数量为MIN(N1, N2)到(N1 − 1) × (N2 − 1)。后者的情况就是下面的白色的格子都故障系统都可以运行。而且这里是N1为1 or N2为1是可以得到两种特殊的情况，
... let us consider setting N1 = N and N2 = 1 when using grid quorums or equivalently setting |Q1| = 1 and |Q2| = N with simple quorums. This would require every acceptor to participate in Q2 but only a single acceptor is needed for Q1. If any acceptors are still up, then we can complete Q1 and learn past decisions.
安全性
FPaxos的安全性基于两点，
Theorem 1. If value v is decided with proposal number p and v′ is decided with proposal number p′ then v = v′
Theorem 2. If value v is decided with proposal number p then for any message propose(p’,v’) where p′ > p then v = v′
0x03 WPaxos: Ruling the Archipelago with Fast Consensus
WPaxos的基本思路也是来自Flexible Paxos。WPaxos将FPaxos中Grid Quorum的概念拓展到跨数据中心的复制上面。在Wpaxos的Quorum中，一列可靠看着是一个分区or一个数据中心内的副本。利用这样的Qourm思路可以优化在使用Paxos跨数据中心达成一致的时候可以优化性能。相比FPaxos的另外而言，WPaxos的论文对算法有着更加详细的描述。
0x04 评估
这里的详细信息可以参看[1, 2],
Paxos Quorum Leases: Fast Reads Without Sacrificing Writes
0x10 引言
这篇Paper也是在Quorum机制上面的优化，不过这里是在不怎么损失写性能的时候明显得优化读操作。Paxos Quorum Leases的基本思路是授予所有副本中一个子集(可以是任意数量的副本，不一定要超过半数)一个租约期(Lease)，在这个时间内不会对授予部分的对象进行更新操作，在要进行更新操作的时候同步通知这些副本，而在由于某些原因不能通知 or 无法确定也没有通知成功的时候，要等到租约过期之后才能进行对象的操作操作。这样一个副本执行读取齐请求的之后就可以直接读取本地，从而提供读取操作的性能，
... Quorum leases are a compromise between the two previous schemes. Over 80% of reads at every site are performed locally. Over 70% of updates have the minimum latency achievable by a geo-distributed Multi-Paxos system, matching that provided by the single leader lease, and 2x to 3x faster (i.e. 100 to 200 milliseconds lower latency) than writes with the Megastore approach.
0x11 基本设计
Paxos Quorum Leases的设计可以应用到各种的Paxos的变体，Paper中讨论的是在Multi-Paxos中应用的情况。它在Paxos的消息之外，加入了Lease管理消息。为了优化性能，这些消息可以和Paxos通常的消息组合在一起发送。Lease管理主要包含了两种类型的消息，一种是关于租约配置的改变，即与那些副本属于一个Quorum以及那部分的对象与这个Quorum关联，另外一种就是刷新租约的操作。Lease的配置和授权的逻辑是分开的。
Lease配置
Paxos Quorum Leases中一个配置是增量地在有前面的配置变化而来。Lease配置的变化就可以通过Paxos本身来完成。如上面的图所示，一个配置必须超过半数的副本达成共识之后才算有效(这样才能保证对一个对象更新的时候能通知Lease失效or必须等到Lease过期之后才能更新)，而一个Lease的Quorum可以是任意的大小。至于具体怎么去修改这个配置，有几种不同的策略，
(a) the lease is granted to a simple majority of nodes;
(b) the number of locally-satisfied read operations is maximized;
(c) the total number of leases being managed is modest.
较好的方法需要副本对目前的一些访问特点进行统计，然后将这些消息发送给Multi-Paxos的Leader，让其决定下一次的配置怎么更新。之后这个Leader会将这一次的配置作为一个特殊的Paxos Instance来操作。至于具体怎么去做这些读操作的统计，可以存在很多种方法，一种方法是一个副本将不能本地就处理的读齐全转发给Leader，之后让Leader统计处理，
... The leader counts the number of forwarded read requests for each object-replica pair. If the number of reads from a given replica is larger than the number of reads from another replica previously included as a lease holder for the object, the leader will include the new replica as a lease holder in the next lease configuration update.
Leases 生效
在超过半数的副本对配置达成了一致的时候，接下来的问题就是如何使这个配置生效。相关的每一个副本都会发送一个Promise的消息给其它所有的副本。这个消息包含了最近Lease配置的编号，用于只接受最新的配置。这里要处理不同的时钟没有同步以及偏斜的问题。一个副本承诺在不通知其相关的副本的情况下不更新一个对象的时间区间必须是包含了相关副本能够执行本地读取的时间区间。
上面的图很好地表示了达成区间的过程，保证了R1承诺的时间包含了R2可以执行本地读取的时间。在发送一个Promise的消息之前，Grantor会发送一个Guard消息，带有一个t-guard的时间。这个Guard的消息必须被回复。之后就是发送Promise消息，这个Promise的消息必须在t-guard的过期之前接受到才会是有效的。在续签这个Lease的时候，这个Guard就不需要了，最近接受到的Promise的消息扮演了一个Guard消息的角色。逻辑还是一样的。在这个Grantor得到了一个新的配置信息的时候，Grantor可以得到目前的Promise过期之后在通知相关额度副本，也可以立即通知。在这里使用的是前一种的方法。Paxos Quorum Leases可以保证Paxos算法的强一致性，一些执行读操作的副本的一个Lease在一个相关的写操作之前还是之后的各种情况都可以保证，在Paper中有详细的讨论证明。
恢复
一个被授予Lease的副本的故障之后可能会阻塞一个更新的提交，因为它不能在回复更新通知了。这个时间与Lease有效的时间相关。探测一个副本是否正常工作主要还是使用心跳的机制，
... the grantor will contact the Multi-Paxos leader requesting a special lease configuration update that specifies that the replica suspected of failure should be excluded from all quorums it was part of. Replicas that switch to this new configuration no longer need to synchronously notify the possibly-failed replica of updates, and the system can safely resume using leases.
这里可能会有这样的一种情况比较难处理。刚好超过半数的Grantor中，有几个故障了，但是故障的数量没有超过半数。整个Paxos系统之后从这个故障中调整，之后的系统中之前的非Grantor占了多数，如果之后的共识都是在这个多数中达成，而这些操作都是在租约没有过期之前就完成了。
0x12 评估
这里的详细信息可以参看[3],
参考
- Flexible Paxos: Quorum intersection revisited, arXiv.
- WPaxos: Ruling the Archipelago with Fast Consensus, arXiv.
- Paxos Quorum Leases: Fast Reads Without Sacrificing Writes, SoCC’14.
