总结

epaxos作为paxos族中的一员，并不是单独存在的。所以我在文中开篇给出总结，罗列与basic-paxos、mutli-paxos之间的区别。带着目的学习，可能相对容易理解一些。

回顾paxos的局限性，总结来说存在三个问题：

  1. basic-paxos，多个proposal提出时，容易形成活锁，影响整个算法的活性。
  2. mutli-paxos，通过只允许leader提出proposal，解决活锁问题，同时影响了吞吐量（性能局限于leader）、可扩展性（必须要leader发起提案）、可用性（leader宕机服务不可用）。
  3. paxos，各提案乱序提交，不能明确各提案之间的依赖关系。
  4. raft，通过实现对日志项进行编号，解决日志项之间依赖关系，但是又不支持乱序提交。
  5. paxos、raft，client跨地域请求leader，延迟增大。

paxos存在的活锁、提案依赖关系的问题。从某个角度来说：mutli-paxos、raft采用“曲线救国”的方案对问题进行规避，通过引入leader和事先对日志项编号来避免，或多或少都降低了可用性和吞吐量。而epaxos则是直面冲突，并给出了自己的解决冲突的方案。

epaxos简介

epaxos特性

在epaxos开篇介绍时，都会提到一个词“leaderless”，这确实是epaxos最值得骄傲的特性了。leaderless描述的是：没有leader，各节点对等，任何节点都可处理事务请求（写请求）。

在“leaderless”特性下，epaxos的优势很明显：

  1. epaxos省略了leader选举的开销，同时没有leader瓶颈限制的问题。
  2. 各节点都能处理事务请求（写请求），拥有更高的性能。
  3. 在跨地域场景下，不需要额外的同步（学习）的阶段。
  4. 客户端可选择最近的副本提供服务，具有更小的延迟。

epaxos的答卷

面对paxos遗留的两个问题：活锁、提案依赖关系。epaxos又是如何解决的呢？

epxos将协议拆分为两部分，一部分是commit协议，一部分是恢复阶段。前者是处理写请求，在各副本中选择（提交）command并确定command附加的属性值（当前command依赖其他command的顺序）。后者是集群中某个副本异常时，其他副本尝试恢复其数据。

在commit协议中，又具体分为三个阶段：

  • 阶段一：Establish ordering constraints，建立约束关系
  • 阶段二：Paxos-Accept，达成一致
  • 阶段三：commit阶段，一般异步提交，通常被大家一笔带过

commit协议中提出日志冲突的概念，阶段一也就是为了解决日志冲突而存在的。当多个command（写请求）对同一个值进行修改时，epaxos则认为发生冲突，需要先建立command之间的约束关系（command之间顺序）。

对于是否冲突，commit协议给出不同达成一致的方案：fast-path, slow-path，二者分别对应没有冲突和有冲突的写请求。fast-path是指在没有冲突的写请求中，执行阶段一即可进行提交。slow-path是指在发生冲突的写请求中，需要执行两个阶段才能进行提交。

fast-path, slow-path

这张经典的图，还是得看，清晰的描述了fast-path, slow-path二者的不同之处。R1, R2,…R5是五个副本。C1, C2, C3, C4是command（即更新操作），R1和R5分别记为C1和C2的command-leader。为了清晰起见，我们省略了异步提交消息。

左图中C1对obj_A修改，C2对obj_B修改，即两者不会发生冲突，因此两者都可以在fast-path上提交。

  1. R1收到update obj_A请求，将其发给多数派副本
  2. 各副本在收该请求后，由于没有其他请求发生冲突，则返回成功R1
  3. 异步提交
  4. R5同上

右图中C3和C4同时对obj_A修改，相互干扰，因此一个C3将在slow-path上执行。

  1. R1和R5分别收到update obj_A请求，将其分别封装为C3和C4发送其他多数派副本
  2. R3为多数派相交的副本，C4比C3先到到达R3
  3. R3在处理C4时，没有请求与之冲突，则提供通过fast-path提交
  4. R3在收到C3时，由于C4和C3发生冲突，则返回C3→C4，表示C3获得了对C4的依赖
  5. R1收到R3的响应，则将依赖关系整理后，发起accept给多数派
  6. 多数派没有继续发生冲突，则返回成功
  7. 异步提交

quorum特殊要求

需要注意，与paxos不同的是：paxos只需要多数派的副本正常响应后，便能正常提交。而对epaxos则略有差异：

  • 论文中指出在fast-path中，quorum数量为：$F+\lfloor(F+1)/2\rfloor$，其中F表示最大容忍的出错副本数量。即：command-leader需要收到$F+\lfloor(F+1)/2\rfloor$个副本（包含command-leader）的正常响应。在上面案例中，5副本的集群，最大容忍出错副本数量为2，则需要与2+[(2+1)/2] = 3.5，向下取整，即3个副本的正常响应。
  • 在slow-path中，quorum数量为：F+1，其中F表示最大容忍的出错副本数量。在上面案例中，5副本的集群，最大容忍出错副本数量为2，则需要收到2+1=3个副本的正常响应。

为了解释这个特殊要求，我们看下面的案列，存在7个副本，大于等于4则为多数派，3个容错数量。R1收到修改x=1，R2收到修改x=2，二者分别发起epaxos。
quorum特殊要求
R4, R5在fast-path先收到x=1再收到x=2。R6, R7在fast-path先收到x=2再收到x=1。如果R3是先收到x=1，那么R1、R3、R4、R5构成多数派，确定提交顺序为先提交x=1再提交x=2。如果R3是先收到x=2，那么R2、R3、R6、R7构成多数派，确定提交顺序为先提交x=2再提交x=1。
那么如果此时R1, R2, R3宕机，那么剩下的副本将不知道是先提交x=1还是先提交x=2。所以在epxos中fast-path需要quorum数量为$F+\lfloor(F+1)/2\rfloor$，即：$3+\lfloor(3+1)/2\rfloor=5$。

commit协议

正如上文提到，epaxos分为两部分，commit协议是指：

当副本L收到来自客户端写请求时，将其封装为command γ（念：伽玛），并称为γ的command-leader，command-leader开始γ的提交过程。进入第一阶段，command-leader定义γ的初始属性deps, seq。

  • deps：定义所有包含与γ冲突的command（不一定是已提交的command）的列表，也称为γ依赖于这些command。
  • seq：用于execute算法过程中，打破循环依赖的序列号。取值为所有冲突command的最大的seq。

command-leader将γ和γ的初始属性deps, seq至少发送给fast-path所要求的quorum数量（$F+\lfloor(F+1)/2\rfloor$），论文中称之为PreAccept-Message。各副本收到PreAccept-Message后，再根据自己本地的cmds-log更新γ的deps, seq值，并在自己的cmds-log中新增一条用来记录γ。将更新的γ返回给command-leader。

如果command-leader收到足够多的响应，并且所有响应中的γ的属性都相同，即构成fast-path，便发送Commit-Message进行异步提交。
如果command-leader没有收到足够多的响应，或者所有响应中的γ的属性存在不一致，即构成slow-path，command-leader需要基于所有响应更新γ的值（合并所有的deps作为新的deps，取最大的seq作为新的seq）。进入第二阶段，将新的γ至少发送给$\lfloor N/2 \rfloor$个副本，这个过程类似经典的paxos，在本轮结束之后，如果收到大多数$\lfloor N/2 \rfloor$响应（包含command-leader）即可给客户端返回成功，并发送Commit-Message进行异步提交。

commit伪代码

commit伪代码
论文中提供了伪代码，我们简单来看看，副本L收到来自客户端的请求γ，成为γ的commandleader

  1. 自增L的instance id $i_L$ ← $i_L$ + 1。
  2. $seq_γ$表示γ的seq，取值为：副本L已记录的command中最大的seq的值+1，与{0}取并集，是在没有command情况下，取0+1作为seq的值。
  3. $deps_γ$表示γ的deps，取值为：副本L中与γ冲突的command集合。
  4. 副本L将 $ (γ,seq_γ,deps_γ,pre-accepted) $ 记录到自己 $cmds_L$ ，pre-accepted表示γ的状态。
  5. 发送$ PreAccept(γ,seq_γ,deps_γ,L.i_L) $给所有副本，$L.i_L$即第一步自增的instance id。

副本R收到PreAccept请求后
6. 更新γ的seq值，取值为：副本R中已记录的command中最大的$seq+1$后与原来seq值，取最大。
7. 更新γ的deps值，取值为：取副本R中与γ冲突集合和原本deps的并集。
8. 副本R将$ (γ,seq_γ,deps_γ,pre-accepted) $记录到自己$cmds_R$，pre-accepted表示γ的状态。
9. 回复PreAcceptOK给副本L。

副本L收到最少$\lfloor N/2 \rfloor$个PreAcceptOK的响应后。（这里的$\lfloor N/2 \rfloor$感觉有问题）
10. 如果所有副本响应中$seq_γ$, $deps_γ$都相同
11. 副本L执行commit阶段，跳转至21步
12. 如果存在不相同的 $seq_γ$, $deps_γ$
13. 更新$deps_γ$，取值为：整合所有响应中的deps
14. 更新$seq_γ$，取值为：所有响应中最大seq
15. 副本L执行paxos-accept阶段

副本L开始paxos-accept阶段
16. 副本L将$(γ,seq_γ,deps_γ,accepted)$记录到自己$cmds_L$，accepted表示γ的状态。
17. 发送$Accept(γ,seq_γ,deps_γ,L.i)$给至少$\lfloor N/2 \rfloor$个副本

副本R收到Accept请求后
18. 副本R将$(γ,seq_γ,deps_γ,accepted)$记录到自己$cmds_R$，accepted表示γ的状态。
19. 回复AcceptOK给副本L。

副本L收到至少$\lfloor N/2 \rfloor$个AcceptOK响应后
20. 开始commit阶段，跳转至21步

副本L开始commit阶段
21. 副本L将$(γ,seq_γ,deps_γ,commited)$记录到自己$cmds_L$，commited表示γ的状态。
22. 回复客户端已提交的响应
23. 发送$Commit(γ,seq_γ,deps_γ,L.i)$给其他的副本

副本R收到commit请求
24. 副本R将$(γ,seq_γ,deps_γ,commited)$记录到自己$cmds_R$，commited表示γ的状态。

Explicit Prepare

这一部分，论文描述的篇幅相对较少，因此也没有被大家重视，epaxos称之为Explicit Prepare，用于恢复异常副本所处理的command。这一部分在论文中也用于执行command。如要要在一个副本上执行command γ，需要经过以下几个步骤：

  1. 等待副本提交，或者显示调用Explicit Prepare
  2. 构建γ所依赖的command的依赖图，对所有依赖command都进行Explicit Prepare
  3. 找到紧密连接的组件（command），对它们进行拓扑排序
  4. 以逆拓扑顺序，对于每个强烈连接的组件（command），执行:
    1. 按顺序将强连接组件中的所有命令排序；
    2. 以递增的编号顺序执行每个未执行的命令，将其标记为已执行

Explicit Prepare伪代码

在看伪代码之前，需要先描述一个概念。在经典的paxos中，每个proposal都有一个ballot，用于标示proposal唯一性，也用于表示proposal的先后顺序，epaxos当然也需要。为了保证ballot唯一性，所以ballot需要包含副本ID。同时新的周期要优先于旧的周期，所有还需要epoch值。最后ballot的格式为：epoch.b.R。

Explicit Prepare

副本Q怀疑L失效，尝试去恢复L.i这个instance。
25. 自增ballot，取值为epoch.(b+1).Q。（epoch.b.Q为副本Q最大的投票编号）
26. 发送$Prepare(epoch.(b+1).Q,L.i)$ 给所有副本，并等待$\lfloor N/2 \rfloor+1$个回复。
27. 假设所有回应中最大ballot的是$ballot_max$，定义R是所有回应中ballot等于$ballot_max$的响应的集合。
28,29. 如果R包含$(γ,seq_γ,deps_γ,commited)$，执行commit阶段
30,31. 如果R包含$(γ,seq_γ,deps_γ,acceprted)$，执行paxos-accept阶段
32,33. 如果R包含至少$\lfloor N/2 \rfloor$一致的回复$(γ,seq_γ,deps_γ,pre-accepted)$，且这些回复都不是来自L，执行paxos-accept阶段
34,35. 如果R至少包含一个$(γ,seq_γ,deps_γ,pre-accepted)$，执行第一阶段
36,37. 如果R没有关于这个instance id的任何信息，那么推出退出恢复阶段，副本Q对L.i实例尝试去commit no-op

副本R收到来自副本Q的Prepare(epoch.b.Q,L.i)请求
38,39. R已接收来自L.i的最大的ballot为epoch.x.Y，如果epoch.b.Q大于epoch.x.Y，回复$PrepareOK(cmds_R,epoch.x.Y,L.i)$
40,41.否则回复NACK

存在的问题

  1. 论文中强调的Executing和Commiting是两个不同的action，但是几乎没有提交关于Execution Algorithm的内容。