epaxos作为paxos族中的一员,并不是单独存在的。所以我在文中开篇给出总结,罗列与basic-paxos、mutli-paxos之间的区别。带着目的学习,可能相对容易理解一些。
回顾paxos的局限性,总结来说存在三个问题:
paxos存在的活锁、提案依赖关系的问题。从某个角度来说:mutli-paxos、raft采用“曲线救国”的方案对问题进行规避,通过引入leader和事先对日志项编号来避免,或多或少都降低了可用性和吞吐量。而epaxos则是直面冲突,并给出了自己的解决冲突的方案。
在epaxos开篇介绍时,都会提到一个词“leaderless”,这确实是epaxos最值得骄傲的特性了。leaderless描述的是:没有leader,各节点对等,任何节点都可处理事务请求(写请求)。
在“leaderless”特性下,epaxos的优势很明显:
面对paxos遗留的两个问题:活锁、提案依赖关系。epaxos又是如何解决的呢?
epxos将协议拆分为两部分,一部分是commit协议,一部分是恢复阶段。前者是处理写请求,在各副本中选择(提交)command并确定command附加的属性值(当前command依赖其他command的顺序)。后者是集群中某个副本异常时,其他副本尝试恢复其数据。
在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上提交。
右图中C3和C4同时对obj_A修改,相互干扰,因此一个C3将在slow-path上执行。
需要注意,与paxos不同的是:paxos只需要多数派的副本正常响应后,便能正常提交。而对epaxos则略有差异:
,其中F表示最大容忍的出错副本数量。即:command-leader需要收到
个副本(包含command-leader)的正常响应。在上面案例中,5副本的集群,最大容忍出错副本数量为2,则需要与2+[(2+1)/2] = 3.5,向下取整,即3个副本的正常响应。
为了解释这个特殊要求,我们看下面的案列,存在7个副本,大于等于4则为多数派,3个容错数量。R1收到修改x=1,R2收到修改x=2,二者分别发起epaxos。
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数量为
,即:
。
正如上文提到,epaxos分为两部分,commit协议是指:
当副本L收到来自客户端写请求时,将其封装为command γ(念:伽玛),并称为γ的command-leader,command-leader开始γ的提交过程。进入第一阶段,command-leader定义γ的初始属性deps, seq。
command-leader将γ和γ的初始属性deps, seq至少发送给fast-path所要求的quorum数量(
),论文中称之为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)。进入第二阶段,将新的γ至少发送给
个副本,这个过程类似经典的paxos,在本轮结束之后,如果收到大多数
响应(包含command-leader)即可给客户端返回成功,并发送Commit-Message进行异步提交。
论文中提供了伪代码,我们简单来看看,副本L收到来自客户端的请求γ,成为γ的commandleader
←
+ 1。
表示γ的seq,取值为:副本L已记录的command中最大的seq的值+1,与{0}取并集,是在没有command情况下,取0+1作为seq的值。
表示γ的deps,取值为:副本L中与γ冲突的command集合。
记录到自己
,pre-accepted表示γ的状态。
给所有副本,
即第一步自增的instance id。
副本R收到PreAccept请求后 6. 更新γ的seq值,取值为:副本R中已记录的command中最大的
后与原来seq值,取最大。7. 更新γ的deps值,取值为:取副本R中与γ冲突集合和原本deps的并集。8. 副本R将
记录到自己
,pre-accepted表示γ的状态。9. 回复PreAcceptOK给副本L。
副本L收到最少
个PreAcceptOK的响应后。(这里的
感觉有问题) 10. 如果所有副本响应中
,
都相同 11. 副本L执行commit阶段,跳转至21步 12. 如果存在不相同的
,
13. 更新
,取值为:整合所有响应中的deps 14. 更新
,取值为:所有响应中最大seq 15. 副本L执行paxos-accept阶段
副本L开始paxos-accept阶段 16. 副本L将
记录到自己
,accepted表示γ的状态。17. 发送
给至少
个副本
副本R收到Accept请求后 18. 副本R将
记录到自己
,accepted表示γ的状态。19. 回复AcceptOK给副本L。
副本L收到至少
个AcceptOK响应后 20. 开始commit阶段,跳转至21步
副本L开始commit阶段 21. 副本L将
记录到自己
,commited表示γ的状态。22. 回复客户端已提交的响应 23. 发送
给其他的副本
副本R收到commit请求 24. 副本R将
记录到自己
,commited表示γ的状态。
这一部分,论文描述的篇幅相对较少,因此也没有被大家重视,epaxos称之为Explicit Prepare,用于恢复异常副本所处理的command。这一部分在论文中也用于执行command。如要要在一个副本上执行command γ,需要经过以下几个步骤:
在看伪代码之前,需要先描述一个概念。在经典的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. 发送
给所有副本,并等待
个回复。27. 假设所有回应中最大ballot的是
,定义R是所有回应中ballot等于
的响应的集合。28,29. 如果R包含
,执行commit阶段 30,31. 如果R包含
,执行paxos-accept阶段 32,33. 如果R包含至少
一致的回复
,且这些回复都不是来自L,执行paxos-accept阶段 34,35. 如果R至少包含一个
,执行第一阶段 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,回复
40,41.否则回复NACK