Egalitarian Paxos

epaxos的目标

• 1）优化在wide-area环境下，当有节点failover出现，仍然能保证低commit延迟；
• 2）把集群的load分散到各个node上，以此提高整体集群的吞吐；
• 3）epaxos保证：在common case下，choose一个value只需要一次roundtrip（fast path）；在有冲突的case下，最多需要2次roundtrip（slow path
  基于leader的paxos变种协议

multi-paxos优缺点

• 优点：选出一个node当leader，原本两阶段的prepare和accept只需要accept阶段就能choose出一个value。
  
• 缺点：

1. 当leader宕机，集群在选出leader之前，不可服务；
2. leader干了所有的活，和其他节点不对等，也就是说leaser节点是集群的瓶颈所在；
3. 在geo-replication环境下，client必须要proposal发送到leader上，多了一跳；
4. 当出现某个节点慢或者crash，集群的抖动比较大；

epaxos的特点

1. 没有leader，这样，所有节点都是对等的（也就是论文的标题），没有瓶颈节点，集群的load分散到各个节点上；
2. client可以把proposal就近发送到某个节点上;
3. 容错性更高，不会出现因为慢节点而影响集群的服务质量，降低长尾的latency

epaxos算法的创新

1. 分布式算法执行的过程就是对cmd进行排序的过程：multi-paxox, g-paxos完全由leader分配顺序；mencius是按照规则预先建立起来的槽位；
2. Epaxos的顺序是动态决定的，给每个cmd添加排序的约束（依赖关系），每个节点通过依赖关系最终保证commit的顺序是一样的
3. fast-path：左图C1和C2更新obj_A和obj_B，没有冲突，一个roundtrip达成commitslow 2）slow-path：右图C3和C2都更新obj_A有冲突，C4的update请求在R3上先发生；C3的update请求在R3上后发生，R3拒绝C3的update，同时返回C3->C4的依赖关系，R1只需要再进行一次accept阶段就可以达成commit）

RSM中Cmd顺序问题

• cmd之间没有依赖关系：就没有必要保证一致性的顺序
• cmd之间有依赖关系：后发生的cmd需要获取dependencies，每个cmd在发送前携带它所看到的dependencies。
• 通过解析dependencies关系，来确定execute顺序（epaxos只保证dependencies是一致的）

和其他paxos变种协议比较

• mencius paxox：

1. mencius通过预先分配instance槽位实现了多写（mysql的group replication）
2. 运行速度取决于最慢的一个；
3. avalibilty比multipaxos还差，一旦任意一个replica出现failure，其他replica都要等待，直到超时后发起一个noops；

• fast paxos：

1. client发送cmd到所有的replica，减少一跳消息；
2. 需要一个replica来充当coordinator和learner，当acceptors收到的cmd的顺序不一致时，必须有稳定的leader来仲裁；

• Generalized-Paxos:

1. 当cmd没有依赖关系，允许乱序commit
2. 同样需要leader来给有依赖关系的cmd排序

• 注意：epaxos的fast path需要3个消息，Generalized-Paxos和fast-paxos都需要2个消息（client直接广播给所有的replica），但是epxos的client是发给本地的replica(co-locate)，在同一个datacenter中，相比wide-area这个延迟可以忽略。这样的好处是：epaxos可以有一个小的fast-path quorum（没必要广播给所有的replica）
  

epaxos协议的设计

• Preliminaries ：

1. Instance的顺序不是事先分配的（比如paxos中在issue一个proposal时就要决定出一个instanceID），而是随着cmd被commit时决定出来的；
2. commit和execute顺序没有必然联系，是不同的操作（raft的commit顺序和execute是一样的，g-paxos是不一样的），两者没有必要保持一致；
3. replica告知client一个cmd被commit了，client并不能知晓这个cmd是否被execute了，只能通过发起一次read操作，replica会保证先execute；

• 定义command interfere：如果执行[a, b]的顺序和执行[b, a]产生的结果不一样，就说a,b 之间是有依赖关
  

算法流程

前面提到过，choose和execute的过程是分开了，因此算法分两个子协议commit protocol和execute protocol。

• Commit protocol分成2个阶段

• 第一阶段：fast path

• Replica L收到了client发过来的cmd a，开始a的choose过程;
• L在自己的instance sub-space里找到下一个instance槽位;
• L计算自己看到的cmd a的依赖关系deps（也就是在cmd a之前，还有哪些cmd也更新同一个值），依赖关系的计算方法：遍历其他replica 的conficts 的冲突，找到相同key对应的instance（这个instance没有必要是commit的）；
• L计算cmd的seq：用来打破循环依赖，遍历所有replica上seq最大值加1；
• 广播PreAccept消息(PreAccept=<cmd a, deps, seq>)到fast path；
• 其他replica收到PreAccept消息后更新内容的conflict map，并且持久化PreAccept（deps,seq也要持久化)；
• Replica L开始接收RepAccept的Reply消息：

1. 如果cmdleader 收到足够多的reply，并且这些reply的attribute都是一致的，意味着多数派看到的attribute是consistent，L就认为可以commit了；
2. 如果收到attr不同的reply，则更新自己attr：取所有deps的并集，并更新seq为最大值，并且进入第二阶段

• 第二阶段：slow path

• 这一阶段对应basic paxos的accept阶段，发送上一阶段merge之后的<cmd a, deps, seq>。也就是：Replica L发现了新的依赖关系，要其他的Replica也接受这个依赖关系；
• Accept消息成功的广播之后，达成了commit了，发送commit；

• execute protocol

• 每个Replica遍历自己的所有的instance space；
• 如果instance没有依赖其他的instance，直接execute；
• 如果instance有依赖关系，则进行Tarjan算法，寻找以这个点根的最大联通分量，并把这个联通分量按照seq排序，依次execute；
• 如果instance一定的超时时间之内没有达到commit，则主动发送prepare，触发prepare阶段；

Epaxos算法的正确性

• 定理1：consistency 和 stability：Replica R上在Q.i commit了cmd a，那么在其他任意Replica上，它的Q.i在相同instance上commit的cmd也是a

1. basic paxos的限制：v被commit了，更高ballot的v被commit，则两个v相等
2. cmd a在Q.i上被commit了，当且仅当Q发起过Phase1，一个instance上Q不能发起多个cmd（原因同multi-paxos）
3. 
   如果Q宕机，其他Replica通过Prepare消息运行basic paxos过程，以此来保证1中的特性（考虑Q issue了一个cmd失败了，又issue了另一个cmd）

• 定理2：<cmd a, Deps-a, Seq-a>满足一致性
  
• 定理3：execute consistency：如果两个有依赖关系的cmd a和cmd b被commit了，那么a，b的execute顺序在所有的replica上是一致的

1. cmd达成commit时，cmd之间的依赖关系至少在半数以上存在，当commit之后的proposal被issue出去后，会对attr做union操作，也就是说：一旦达成commit，依赖关系就会在后续的cmd被承认
2. 进行recovery的时候也是成立的

• 定理4：cmd1在cmd2之前被commit，保证cmd1在cmd2之前被execute

recovery协议

• 当一个replica依赖某个instancde时，需要learn，如果learn不到，发送Explicit Prepare：

1. 如果其他replica上有这个instance，则学到后进行comit；
2. 如果其他replica都没有，则commit一个noop，让它不阻塞后面instance的commit
3. 如果允许client重试，那么replica在进行cmd1的复制过程时，client认为超时，又发送给replica一次这个cmd，导致重复，解决：

1. 唯一的ID；
2. 幂等性

read leases

• Paxos协议族的读操作需要像写一下发起协议流程，否则可能会读取到老的数据
• 通过限制在一个leases内某个key只在某个replica上被提交，这个leases对这个key的读操作也发到这个replica上

和其他协议的数据对比

• 延迟对比

• 环境：5副本，在每个副本同一个机房部署10个client，异步的发射请求，一共50个client
• 结论：

1. epaxos具有最好的中位数commit letency
2. multi-paxos的leader在CA，因此CA的client延时比VA和EU都低
3. mencius-balance：各个阶段压力均衡的情况下，表现很好，仅次于epaxos（各个replica均摊了load）
4. mencius-imbalance：各个阶段压力不均衡的情况下，抖动很大（需要主动发起prepare）
5. epaxs-2%测试集：即使有2%的冲突几乎不影响延时
6. epaxos-100%测试集：即使100%的冲突，延迟也优于multi-paxos

• 吞吐对比

• 节点异常测试

• 在某个node上执行for循环，抢占cpu，模拟cpu慢：

• epaxos：基本不受影响，其他节点是对等的，可以对等承受压力
• mencius：降为50%，原因是，mencius要求是连续的，apply时需要等待慢节点
• multi：lader是瓶颈节点，一点慢了，就直接影响总体的吞吐

• epaxos通过ping探测时延，动态的屏蔽掉慢节点

• mencius：理论性能取决于最慢的一个，因为instances是预分配的，必须等待前面的被learn到了，才能进行commit