总结

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的内容。