Replication-Based Fault-Tolerance for Large-Scale Graph Processing
Replication-Based Fault-Tolerance for Large-Scale Graph Processing
复制标题
DOI：
10.1109/dsn.2014.58
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Peng Wang;Kaiyuan Zhang;Rong Chen;Haibo Chen;Haibing Guan
中科院分区：
文献类型：
--
作者：
Peng Wang;Kaiyuan Zhang;Rong Chen;Haibo Chen;Haibing Guan
算法复杂度和数据集大小的增加使得许多图并行算法需要使用网络机器，这也使得容错成为必须，因为机器的规模越来越大。然而，现有的大规模图并行系统通常采用分布式检查点机制来容错，这不仅会带来显著的性能开销，而且恢复时间也很长.本文观察到，为分布式图计算创建的顶点副本可以自然地扩展，以实现图状态的快速内存恢复。本文提出了一种新的容错机制，模仿者，支持廉价的维护顶点状态复制顶点状态到他们的副本在正常的消息交换，并提供快速的内存中重建失败的顶点从副本在其他机器。Imitator是通过扩展Hama实现的，Hama是Pregel的一个流行的开源克隆。评估表明，Imitator的性能开销可以忽略不计（所有情况下都小于5%），并且可以在不到3.4秒的时间内从超过100万个顶点的故障中恢复。
The increasing algorithm complexity and dataset sizes necessitate the use of networked machines for many graph-parallel algorithms, which also makes fault tolerance a must due to the increasing scale of machines. Unfortunately, existing large-scale graph-parallel systems usually adopt a distributed checkpoint mechanism for fault tolerance, which incurs not only notable performance overhead but also lengthy recovery time. This paper observes that the vertex replicas created for distributed graph computation can be naturally extended for fast in-memory recovery of graph states. This paper proposes Imitator, a new fault tolerance mechanism, that supports cheaply maintenance of vertex states by replicating vertex states to their replicas during normal message exchanges, and provides fast in-memory reconstruction of failed vertices from replicas in other machines. Imitator has been implemented by extending Hama, a popular open-source clone of Pregel. Evaluation shows that Imitator incurs negligible performance overhead (less than 5% for all cases) and can recover from failures of more than one million of vertices with less than 3.4 seconds.