Epaxos execution

Instance

这里仅列出execution需要用到的变量

type Instance struct {
    Deps    [ReplicaCount]int32
    Index   int
    Lowlink int
    Seq     int
}

• Deps：表示当前instance所依赖的其它Replica上的instance id

  • Deps[0]表示依赖Replica 0上的的instance id

  • Deps[1]表示依赖Replica 1上的的instance id

  • Deps[2]表示依赖Replica 2上的的instance id

• Index：用于使用Tarjan算法寻找强连通分量的节点搜索次序编号，=0表示此节点没有被访问过

• Lowlink：Tarjan算法中节点或节点的子树能够追溯到的最早的栈中节点的次序号

• Seq：用于强连通分量定序

看下执行过程

例如下面是一个ins的依赖图

ins1---------->ins3---------->ins5
 ^              |              |
 |              |              |
 |              |              |
 |              |              |
 |              V              V
ins2<----------ins4---------->ins6

采用Tarjan算法搜索图中的强连通分量SCC:Strongly Connected Components，该算法有两个重要的数组

• DFN[]：全称Depth First Number，表示节点被搜索到的次序编号，对应struct Instance中Index

• LOW[]：表示节点或者节点的子树能够追溯到的最早的栈中节点的次序编号，对应struct Instance中Lowlink

下面来展示一下执行过程，这里使用DFN(struct Instance中Index)，LOW(struct Instance中Lowlink)

• 从ins1开始DFS(Depth First Search)遍历, 比如顺序是ins1->ins3->ins5->ins6，依次入栈，如下

-----------
|  ins6   |->DFN:4 LOW:4
-----------
|  ins5   |->DFN:3 LOW:3
-----------
|  ins3   |->DFN:2 LOW:2
-----------
|  ins1   |->DFN:1 LOW:1
-----------

• 搜索到ins6发现没有边可搜索，这个时候退栈发现DFN:4==LOW:4，说明ins6是一个强连通分量，这个时候去exec ins6

• 同理ins5也是一个强连通分量，exec ins5之后，这个时候栈如下

-----------
|  ins3   |->DFN:2 LOW:2
-----------
|  ins1   |->DFN:1 LOW:1
-----------

• 出栈到ins3，继续搜索ins4并加入栈

• 继续搜索ins2，由于ins2有边指向ins1，ins1还在栈里面，这个时候ins2的LOW取ins1的LOW，也就是1，栈如下

-----------
|  ins2   |->DFN:6 LOW:1
-----------
|  ins4   |->DFN:5 LOW:5
-----------
|  ins3   |->DFN:2 LOW:2
-----------
|  ins1   |->DFN:1 LOW:1
-----------

• 这个时候，所有节点已经搜索完成，开始回溯并修改LOW的值，取看到的最小值，如下

-----------
|  ins2   |->DFN:6 LOW:1
-----------
|  ins4   |->DFN:5 LOW:1
-----------
|  ins3   |->DFN:2 LOW:1
-----------
|  ins1   |->DFN:1 LOW:1
-----------

• 我们需要找到一个节点DFN=LOW，也就是这个强连通分量的根，上述例子中就是ins1，栈里面的元素集合就是一个强连通分量，这里是 ins1 ins2 ins3 ins4

强连通分量定序

• 强连通分量中节点是相互可达的，也就是相互依赖，但是我们需要保证强连通分量中的ins执行顺序在每个Replica中保持一致，采用的 方式是通过ins中Seq进行排序，排序的结果也就是ins的执行顺序

其它实现细节

• 每个Replica保存了其execution后最大的ins id，定义为ExecedUpTo

• 比如ins1(Replica1)->ins10(Replica2)，实际上Replica2需要exec的是[ExecedUpTo+1, ins10]，也可以这样理解 ins1(Replica1)依赖Replica2上ins id在[ExecedUpTo+1, ins10]中的所有ins

• execution线程会给当前Replica上最小的没有committed的active ins设置一个超时时间，到达超时时间还没有达到 committed状态，会触发ins的恢复流程