张 基，谢在鹏，毛莺池，徐媛媛，朱晓瑞，李博文

（河海大学计算机与信息学院，南京 211100）

0 概述

容错技术是分布式系统的重要组成部分，确保了发生故障时的系统连续性和功能性［1］。近年来，随着分布式系统规模的不断扩大、分布式架构和计算复杂度的日益增加［2］以及廉价商业硬件的广泛使用，使得计算任务发生故障的概率持续增加，例如在Google 生产集群中平均每天会有数十个节点发生故障［3］。瞬态故障尤其是软错误［4］会导致计算机系统的异常行为，这类故障会损坏数据的完整性，引起分布式节点的计算失效［4-5］。在一些大型分布式系统中平均每天会有1%～2%的节点发生失效［6］，因此容错技术可在保证部分节点失效的情况下，使分布式系统仍能继续运行且得到正确结果［7-9］。在基于MapReduce［10］的分布式计算中，数据洗牌（shuffle）阶段较高的通信开销严重影响了分布式计算性能，例如在Facebook 的Hadoop 集群中，33%的任务执行总时间用于数据洗牌阶段［11］。针对基于MapReduce 分布式计算框架的多副本容错算法通信开销较大的问题，本文提出一种结合分布式编码计算的容错算法CTMR，使基于MapReduce 的分布式计算系统在发生瞬态故障的情况下仍能继续运行且得到正确结果，同时能有效降低容错计算过程中的通信开销。

1 相关工作

基于多副本冗余技术［12-15］的分布式容错算法于1962年由IBM提出，但在现代分布式系统中仍然被广泛采用［16-17］。这类算法的主要思想是：在含有n个节点的分布式系统中，如果每个节点要容忍f个故障，那么该节点可以使用（f+1）个独立的副本，显然存储和运行这些副本需要消耗大量的空间和其他资源。……