SoCC '15 | Zorro: Zero-Cost Reactive Failure Recovery in Distributed Graph Processing

[PeterSH6]

https://assured-cloud-computing.illinois.edu/files/2014/03/Zorro-Zero-Cost-Reactive-Failure-Recovery-in-Distributed-Graph-Processing.pdf

[PeterSH6]

这篇文章提出了proactive和reactive的概念。proactive中包含checkpoint和logging等，reactive中主要包含replication。

Desirable Property for Failure Recovery

本篇论文将图系统中一个节点在一个iteration中可能的步骤抽象成三个步骤：Gather => Apply => Scatter 使用reactive方法的意思就是整个系统不做任何的checkpoint或者logging，仅仅使用replication来恢复系统。这样操作的前提是在graph processing system中有很多冗余的vertices，所以可以使用replica来恢复。对于没有冗余的节点，或者replicas全挂了的节点，挂了之后就使用初始值。因此，这篇论文并没有保证full recovery，而是保证graph processing application的结果不会因为fault而有明显的下降。这里面的ideas是重要的节点都会有冗余，不重要的节点可能没有冗余，但丢失了没关系。这种节点的分配方式（是否有冗余），和整个图的拓扑有很大关系。

Out-Neighbor: 将有出边的节点replicate到另一个机器上，因此一个vertex有一个出边则在整个系统中至少有1个replica，至多有两个replica。 All-Neighbor: 将每一条边分配到server中，该模式的冗余度比前者高。在这种模式下，一个replica会被标记为master，另外的replicas会被标记为mirrors，mirrors会将Gather阶段的结果传输到master节点中，然后master combine and synchronizes the result with the mirrors.

Recovery Flow

在恢复过程中，级联错误会被当成是一个大的Failure，且之后的Failure不会影响之前的Failure的恢复过程。健康节点将该节点发送到新加入的server中，然后新加入的server会发送ack。

之后这篇论文又通过建模估算了一下系统中可能丢失的节点数量和recovery overhead，用了Zipf分布，不太懂，先不细讲了。

[PeterSH6]

最后有一个疑问，Dataset中节点的数量非常多，但是实验的机器数量只有16台，那么这就意味着其实16台机器中保存的节点数量比这个还要多。

然后从实验的结果来看，比如pagerank算法，几乎不掉acc，top-k的节点都保存的很好，作者分析的结论是重要的节点都保存（有冗余）的很好，丢失的主要是不重要的节点。对于out-neighbor来说，出边越多的节点，拥有更多冗余的可能性更高。对于all-neighbor来说，因为是分配边到节点中，万一一个非常重要的节点所相关的边都被分配到了一台机器上，那这台机器挂了，这个重要节点也就丢失了。但是这里的效果出奇的好，可能图系统在分配的时候有什么机制有意或无意（概率问题）使得这些重要节点有冗余。