第４３ 卷 第１１期２０２０年１ １ 月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ ．４３Ｎｏ．１１Ｎｏｖ．２０２０面向Ｆｌｉｎｋ迭代计算的高效容错处理技术郭文鹏ｎ赵宇海＂王国仁２）韦刘国ｎ东北大学计算机科学与工程学院 沈阳 １１０１６９ ）２ ）（ 北京理工大学计算机学院 北京 １０００８１ ）摘 要 迭代计算是相同逻辑的重复执行， 在各种机器学习和数据挖掘方法中被广泛使用． 在大数据的处理与分析领域中， 分布式迭代计算更是当前的热点研究问题之一． 容错机制是分布式系统高可用性的必要保证． 现有分布式系统的容错机制虽然在髙可用性上表现良好， 但忽略了面向迭代计算的容错效率问题． 本文针对批流混合大数据计算系统ＡｐａｃｈｅＦｌｉ ｎｋ的迭代容错效率问题， 进行了系统的研究． 执行流处理任务时， Ｆｌｉｎｋ采用“分布式快照”的检查点机制来完成容错． 对于海量数据的迭代分析， 检查点增加了不必要的延迟． 执行批处理任务时， Ｆｌｉｎｋ采用从头执行任务的方式来实现容错， 该方式虽然实现简单， 但带来了很大的时间开销． 针对以上问题， 本文首先提出了一种基于补偿函数的乐观迭代容错机制． 该容错机制在迭代任务发生故障时采用乐观补偿的思想恢复任务， 在迭代执行过程中不采用任何额外的容错手段（不会引人额外的容错开销） ， 采用用户自定义的补偿函数收集健康节点上的迭代数据， 并结合初始的迭代数据对故障节点上丢失的分区数据进行恢复， 继续执行至迭代收敛状态，保证了迭代任务的高效顺利执行． 由于乐观迭代容错机制并不保证得到的结果与无故障执行得到的结果完全一致， 因此针对精度要求较高的迭代任务， 本文结合Ｆｌ ｉｎｋ系统的迭代数据流模型， 进一步提出一种基于头尾检査点悲观迭代容错机制． 与传统的阻塞检査点（阻塞下游操作符）的工作方式不同， 该容错机制以非阻塞的方式编写检査点， 充分结合ＦＵｎｋ迭代数据流的特点， 将可变数据集的检查点注人迭代流本身． 通过设计迭代感知， 简化了系统架构， 降低了检査点成本和故障恢复时间． 本文基于Ｆｌ ｉｎｋ系统， 在大量的真实数据集和模拟数据集上， 从增量迭代和全量迭代两方面对提出的两种容错机制进行了全面的实验研究， 验证了本文提出的迭代容错优化技术的高效性． 实验结果证实， 本文基于Ｆｌｉｎｋ系统提出的乐观容错机制和悲观容错机制在计算效率上均优于现有的分布式迭代容错机制． 前者在全量迭代计算任务中运行时间最髙可提升２２．８％， 在增量迭代计算任务中最髙可提升３３．８％； 后者在全量迭代任务中最高可节省１５．３％的时间开销， 在增量迭代任务中最高可节省１８．５％的时间开销．关键词 分布式迭代计算； ＡｐａｃｈｅＦｌｉｎｋ； 乐观容错； 悲观容错； 检查点中图法分类号ＴＰ１８ＤＯＩ号１０． １ １８９７／ＳＰ． Ｊ．１０１６．２０２０．０２１０１ＥｆｆｉｃｉｅｎｔＦａｕｌｔ－ＴｏｌｅｒａｎｔＰｒｏｃｅｓｓｉｎｇＴｅｃｈｎｏｌｏｇｙｆｏｒＦｌｉｎｋＩｔｅｒａｔｉｖｅＣｏｍｐｕｔｉｎｇＧＵＯＷｅｎ－ＰｅｎｇｎＺＨＡＯＹｕ－Ｈａｉ１）ＷＡＮＧＧｕｏ－Ｒｅｎ２）ＷＥＩＬｉ ｕ－Ｇｕｏｎｌ）（．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔ ｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉ ｎｅｅｒｉｎｇ＾ＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ＊Ｓｈｅｎｙａｎｇ１１０１６ ９）２ ＞（ ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ？ＢｅｉｊｉｎｇＩｎｓｔ ｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉ ｎｇ１０００８１）ＡｂｓｔｒａｃｔＩｔｅｒａｔｉ ｖｅｃａｌｃｕｌａｔｉｏｎｉｓｔｈｅｒｅｐｅａｔｅｄｅｘｅｃｕｔｉｏｎｏｆｔｈｅｓａｍｅｌｏｇｉ ｃａｎｄｉ ｓｗｉ ｄｅｌｙｕｓｅｄｉ ｎｖａｒｉｏｕｓｍａｃｈｉ ｎｅｌｅａｒｎｉｎｇａｎｄｄａｔａｍｉ ｎｉ ｎｇｍｅｔｈｏｄｓ．Ｉｎｔｈｅｆｉｅｌｄｏｆｂｉｇｄａｔａｐｒｏｃｅｓｓｉｎｇａｎｄａｎａｌｙｓｉｓ，ｄｉｓｔｒｉｂｕｔｅｄｉｔｅｒａｔｉ ｖｅｃｏｍｐｕｔｉ ｎｇｉｓｏｎｅｏｆｔｈｅｃｕｒｒｅｎｔｈｏｔｒｅｓｅａｒｃｈｉｓｓｕｅｓ．Ｆａｕｌ ｔｔｏｌｅｒａｎｃｅｉｓａｎｅｃｅｓｓａｒｙｇｕａｒａｎｔｅｅｆｏｒｈｉｇｈａｖａｉｌａｂｉｌｉｔｙｏｆｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍｓ．Ａｌｔｈｏｕｇｈｔｈｅｆａｕｌｔｔｏｌｅｒａｎｃｅｍｅｃｈａｎｉｓｍｏｆｅｘｉｓｔｉ ｎｇｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍｓｐｅｒｆｏｒｍｓｗｅｌｌｉ ｎｈｉｇｈａｖａｉｌａｂｉｌｉｔｙ，ｉｔｉｇｎｏｒｅｓｔｈｅｐｒｏｂｌｅｍｏｆｆａｕｌ ｔｔｏｌｅｒａｎｃｅｅｆｆｉ ｃｉｅｎｃｙｆｏｒｉ ｔｅｒａｔｉ ｖｅｃｏｍｐｕｔｉ ｎｇ．Ｔｈｉ ｓｐａｐｅｒｓｙｓｔｅｍａｔｉｃａｌ ｌｙｓｔｕｄｉｅｓｔｈｅｉ ｔｅｒａｔｉ ｖｅ收稿日期： ２０１９－０９－０２； 在线发布日期： ２０２０－０２－１３． 本课题得到科技部重点研发项目“云计算和大数据”重点专项项目（ ２０１８ＹＦＢ１００４４０２ ）和国家自然科学基金（ ６１７７２１２４） 资助． 郭文鹏， 硕士研究生， 主要研究方向为大数据． Ｅ－ｍａｉｌ ：１７６２８８２２３２４＠ｑｑ．ｃｏｍ． 赵宇海（ 通信作者） ， 博士， 教授， 中国计算机学会（ 〇＾） 高级会员， 主要研究领域为数据挖掘． ￡－１１＾丨： ２１１３〇７１１１＾＠１１＾１．１１扣． ６（１１１． 〇１ ． 王国仁， 博士， 教授，中国计算机学会（ ＣＣＦ） 高级会员， 主要研究领域为数据库． 韦刘国， 硕士研究生， 主要研究方向为大数据．２１０２ 计 算机 学 报 ２０２０年ｆａｕｌ ｔ－ｔｏｌｅｒａｎｔｅｆｆｉｃｉｅｎｃｙｏｆｂａｔｃｈ－ｆｌｏｗｈｙｂｒｉｄｂｉｇｄａｔａｃｏｍｐｕｔｉ ｎｇｓｙｓｔｅｍＡｐａｃｈｅＦｌｉ ｎｋ．Ｗｈｅｎｐｅｒｆｏｒｍｉ ｎｇｓｔｒｅａｍｐｒｏｃｅｓｓｉ ｎｇｔａｓｋｓ， Ｆｌｉｎｋｕｓｅｓａ“ｄｉｓｔｒｉ ｂｕｔｅｄｓｎａｐｓｈｏｔ”ｃｈｅｃｋｐｏｉｎｔｍｅｃｈａｎｉｓｍｔｏｃｏｍｐｌ ｅｔｅｆａｕｌ ｔｔｏｌｅｒａｎｃｅ．Ｆｏｒｉｔｅｒａｔｉｖｅａｎａｌｙｓｉｓｏｆｍａｓｓｉ ｖｅｄａｔａ，ｃｈｅｃｋｐｏｉｎｔｓａｄｄｕｎｎｅｃｅｓｓａｒｙｄｅｌａｙ．Ｗｈｅｎｐｅｒｆｏｒｍｉｎｇｂａｔｃｈｐｒｏｃｅｓｓｉｎｇｔａｓｋｓ，Ｆｌｉｎｋｕｓｅｓｔｈｅｔａｓｋｅｘｅｃｕｔｉｏｎｍｅｔｈｏｄｆｒｏｍｔｈｅｂｅｇｉ ｎｎｉ ｎｇｔｏａｃｈｉｅｖｅｆａｕｌ ｔｔｏｌｅｒａｎｃｅ．Ａｌ ｔｈｏｕｇｈｔｈｉｓｍｅｔｈｏｄｉｓｓｉｍｐｌ ｅｔｏｉ ｍｐｌｅｍｅｎｔ ，ｉｔｂｒｉ ｎｇｓａｌｏｔｏｆｔｉ ｍｅｏｖｅｒｈｅａｄ．Ｉｎｖｉｅｗｏｆｔｈｅａｂｏｖｅｐｒｏｂｌｅｍｓ？ｔｈｉｓｐａｐｅｒｆｉｒｓｔｐｒｏｐｏｓｅｓａｎｏｐｔｉ ｍｉ ｓｔｉ ｃｉｔｅｒａｔｉ ｖｅｆａｕｌ ｔｔｏｌ ｅｒａｎｃｅｍｅｃｈａｎｉ ｓｍｂａｓｅｄｏｎｃｏｍｐｅｎｓａｔｉ ｏｎｆｕｎｃｔｉｏｎｓ．Ｔｈｉｓｆａｕｌ ｔ－ｔｏｌｅｒａｎｔｍｅｃｈａｎｉ ｓｍｕｓｅｓｏｐｔｉ ｍｉｓｔｉｃｃｏｍｐｅｎｓａｔｉ ｏｎｔｏｒｅｃｏｖｅｒｔａｓｋｓｗｈｅｎｉｔｅｒａｔｉ ｖｅｔａｓｋｓｆａｉｌ ．Ｉｔｄｏｅｓｎｏｔｕｓｅａｎｙａｄｄｉｔｉｏｎａｌｆａｕｌｔ－ｔｏｌｅｒａｎｔｍｅｔｈｏｄｓ（ｉｔｄｏｅｓｎｏｔｉ ｎｔｒｏｄｕｃｅａｄｄｉｔｉ ｏｎａｌｆａｕｌｔ－ｔｏｌｅｒａｎｔｏｖｅｒｈｅａｄ）ｄｕｒｉｎｇｉｔｅｒａｔｉ ｖｅｅｘｅｃｕｔｉ ｏｎ，ａｎｄｕｓｅｓｕｓｅｒ－ｄｅｆｉ ｎｅｄｃｏｍｐｅｎｓａｔｉ ｏｎｆｕｎｃｔｉｏｎｓｔｏｃｏｌ ｌｅｃｔｈｅａｌ ｔｈｙｎｏｄｅｓ．Ｉｔｅｒａｔｉ ｖｅｄａｔａ＊ｃｏｍｂｉ ｎｅｄｗｉ ｔｈｔｈｅｉ ｎｉ ｔｉ ａｌｉｔｅｒａｔｉｖｅｄａｔａ ，ｒｅｃｏｖｅｒｓｔｈｅｌ ｏｓｔｐａｒｔｉ ｔｉｏｎｄａｔａｏｎｔｈｅｆａｉｌ ｅｄｎｏｄｅ，ａｎｄｃｏｎｔｉ ｎｕｅｓｅｘｅｃｕｔｉｏｎｔｏｔｈｅｉｔｅｒａｔｉ ｖｅｃｏｎｖｅｒｇｅｎｃｅｓｔａｔｅ，ｅｎｓｕｒｉ ｎｇｔｈｅｅｆｆｉｃｉｅｎｔａｎｄｓｍｏｏｔｈｅｘｅｃｕｔｉ ｏｎｏｆｔｈｅｉｔｅｒａｔｉ ｖｅｔａｓｋ．Ｂｅｃａｕｓｅｔｈｅｏｐｔｉｍｉ ｓｔｉｃｉ ｔｅｒａｔｉ ｖｅｆａｕｌ ｔｔｏｌ ｅｒａｎｃｅｍｅｃｈａｎｉｓｍｄｏｅｓｎｏｔｇｕａｒａｎｔｅｅｔｈａｔｔｈｅｒｅｓｕｌｔｓｏｂｔａｉ ｎｅｄａｒｅｃｏｍｐｌｅｔｅｌｙｃｏｎｓｉｓｔｅｎｔｗｉｔｈｔｈｅｒｅｓｕｌ ｔｓｏｂｔａｉｎｅｄｂｙｆａｕｌｔ－ｆｒｅｅｅｘｅｃｕｔｉ ｏｎ，ｆｏｒｔｈｅｉｔｅｒａｔｉｏｎｔａｓｋｓｗｉｔｈｈｉｇｈｅｒａｃｃｕｒａｃｙｒｅｑｕｉｒｅｍｅｎｔｓ，ｔｈｉｓｐａｐｅｒｃｏｍｂｉ ｎｅｓｔｈｅｉｔｅｒａｔｉ ｖｅｄａｔａｆｌｏｗｍｏｄｅｌｏｆｔｈｅＦｌｉ ｎｋｓｙｓｔｅｍｔｏｆｕｒｔｈｅｒｐｒｏｐｏｓｅａｈｅａｄ－ｔｏ－ｔａｉｌｃｈｅｃｋｐｏｉ ｎｔ．Ｐｅｓｓｉ ｍｉｓｔｉｃｉｔｅｒａｔｉ ｖｅｆａｕｌｔｔｏｌｅｒａｎｃｅｍｅｃｈａｎｉ ｓｍ．Ｕｎｌ ｉｋｅｔｒａｄｉ ｔｉｏｎａｌｂｌｏｃｋｉｎｇｃｈｅｃｋｐｏｉ ｎｔｓ（ ｂｌｏｃｋｉｎｇｄｏｗｎｓｔｒｅａｍｏｐｅｒａｔｏｒｓ），ｔｈｉｓｆａｕｌ ｔ－ｔｏｌ ｅｒａｎｔｍｅｃｈａｎｉ ｓｍｗｒｉ ｔｅｓｃｈｅｃｋｐｏｉ ｎｔｓｉ ｎａｎｏｎ－ｂｌｏｃｋｉｎｇｍａｎｎｅｒ，ｆｕｌｌｙｃｏｍｂｉ ｎｅｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＦｌｉｎｋｉｔｅｒａｔｉ ｖｅｄａｔａｆｌｏｗ， ａｎｄｉｎｊｅｃｔｓｖａｒｉａｂｌｅｄａｔａｓｅｔｃｈｅｃｋｐｏｉ ｎｔｓｉ ｎｔｏｔｈｅｉ ｔｅｒａｔｉ ｖｅｆｌｏｗｉ ｔｓｅｌ ｆ．Ｂｙｄｅｓｉｇｎｉｎｇｉｔｅｒａｔｉ ｖｅａｗａｒｅｎｅｓｓ，ｔｈｅｓｙｓｔｅｍａｒｃｈｉｔｅｃｔｕｒｅｉｓｓｉ ｍｐｌ ｉｆｉｅｄ，ａｎｄｃｈｅｃｋｐｏｉ ｎｔｃｏｓｔｓａｎｄｆａｉ ｌ ｕｒｅｒｅｃｏｖｅｒｙｔｉ ｍｅｓａｒｅｒｅｄｕｃｅｄ．Ｔｈｉ ｓｐａｐｅｒｉ ｓｂａｓｅｄｏｎｔｈｅＦｌｉ ｎｋｓｙｓｔｅｍ．Ｏｎａｌａｒｇｅｎｕｍｂｅｒｏｆｒｅａｌｄａｔａｓｅｔｓａｎｄｓｉｍｕｌａｔｅｄｄａｔａｓｅｔｓ，ａｃｏｍｐｒｅｈｅｎｓｉ ｖｅｅｘｐｅｒｉ ｍｅｎｔａｌｓｔｕｄｙｏｆｔｈｅｔｗｏｐｒｏｐｏｓｅｄｆａｕｌ ｔｔｏｌｅｒａｎｃｅｍｅｃｈａｎｉｓｍｓｆｒｏｍｔｈｅａｓｐｅｃｔｓｏｆｉ ｎｃｒｅｍｅｎｔａｌｉｔｅｒａｔｉｏｎａｎｄｆｕｌ ｌｉｔｅｒａｔｉ ｏｎｉｓｃｏｎｄｕｃｔｅｄ，ａｎｄｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｐｒｏｐｏｓｅｄｉｔｅｒａｔｉ ｖｅｆａｕｌ ｔｔｏｌｅｒａｎｃｅｏｐｔｉ ｍｉｚａｔｉ ｏｎｔｅｃｈｎｏｌ ｏｇｙｉ ｓｖｅｒｉｆｉ ｅｄ．Ｅｆｆｉ ｃｉｅｎｃｙ．Ｔｈｅｅｘｐｅｒｉ ｍｅｎｔａｌｒｅｓｕｌ ｔｓｃｏｎｆｉｒｍｔｈａｔｔｈｅｏｐｔｉ ｍｉ ｓｔｉ ｃａｎｄｐｅｓｓｉ ｍｉｓｔｉｃｆａｕｌｔ－ｔｏｌｅｒａｎｔｍｅｃｈａｎｉｓｍｓｐｒｏｐｏｓｅｄｉ ｎｔｈｉｓｐａｐｅｒｂａｓｅｄｏｎｔｈｅＦｌｉ ｎｋｓｙｓｔｅｍａｒｅｓｕｐｅｒｉｏｒｔｏｔｈｅｅｘｉｓｔｉｎｇｄｉｓｔｒｉ ｂｕｔｅｄｉｔｅｒａｔｉ ｖｅｆａｕｌ ｔ－ｔｏｌｅｒａｎｔｍｅｃｈａｎｉｓｍｓｉｎｔｅｒｍｓｏｆｃｏｍｐｕｔａｔｉｏｎａｌｅｆｆｉ ｃｉ ｅｎｃｙ．Ｔｈｅｆｏｒｍｅｒｃａｎｉ ｎｃｒｅａｓｅｔｈｅｒｕｎｎｉ ｎｇｔｉｍｅｂｙｕｐｔｏ２２．８％ｉ ｎｆｕｌ ｌｉ ｔｅｒａｔｉ ｖｅｃｏｍｐｕｔｉ ｎｇｔａｓｋｓａｎｄｕｐｔｏ３３．８％ｉ ｎｉ ｎｃｒｅｍｅｎｔａｌ ｉ ｔｅｒａｔｉ ｖｅｃｏｍｐｕｔｉ ｎｇｔａｓｋｓ；ｔｈｅｌａｔｔｅｒｃａｎｓａｖｅｕｐｔｏ１５．３％ｏｆｔｈｅｔｉｍｅｏｖｅｒｈｅａｄｉ ｎｆｕｌ ｌｉｔｅｒａｔｉ ｖｅｔａｓｋｓ？ａｎｄｉ ｎｉｎｃｒｅｍｅｎｔａｌｉｔｅｒａｔｉ ｖｅｔａｓｋｓＳａｖｅｓｕｐｔｏ１８．５％ｏｆｔｉ ｍｅ．Ｋｅｙｗｏｒｄｓｄｉｓｔｒｉ ｂｕｔｅｄｉｔｅｒａｔｉ ｖｅｃａｌ ｃｕｌ ａｔｉ ｏｎ；ＡｐａｃｈｅＦｌｉｎｋ；ｏｐｔｉｍｉｓｔｉｃｆａｕｌ ｔｔｏｌ ｅｒａｎｃｅ；ｐｅｓｓｉ ｍｉｓｔｉｃｆａｕｌ ｔｔｏｌｅｒａｎｃｅ；ｃｈｅｃｋｐｏｉ ｎｔｉ引 言迭代计算通常是数据挖掘和机器学习算法的核心部分， 在各类应用中都普遍存在［１］． 在搜索领域， 由Ｇｏｏｇｌ ｅ 提出的著名的网页排序算法ＰａｇｅＲａｎｋ［２３］，其核心思想就是根据网络之中不同网页之间的链接关系进行迭代计算［１］， 最终的排名即是迭代最终收敛的值或重要性； 在社交网络［５ ７］领域， 很多好友推荐算法都是通过利用现有用户的好友关系网络图通过迭代计算来挖掘用户之间可能存在的潜在链接关系； ＲａｎｄｏｍＷａｌｋ［８９］算法通过迭代计算来求解图中某节点到其它节点的概率； 在影音推荐领域， 常用的推荐算法是按照用户的喜好来对用户进行聚类， 然后向用户推荐同类用户所喜欢的影音资源， 这类方法统称为协同过滤推荐［ｉ Ｍ１］． 其中基于矩阵分解的协同过滤算法， 如交替最小二乘法（ＡＬＳ）和奇异值分解等（ ＳＶＤ） 等都包含迭代计算； 在图论郭文鹏等： 面向Ｆｌｉｎｋ迭代计算的高效容错处理技术 ２１０３１ １ 期中的连通分支算法也是基于迭代实现的． 在数据分析领域中， 常用的Ｋ－Ｍｅａｎｓ［１？聚类算法、 联合聚类、点对聚类等都包含迭代计算， 每次迭代时更新顶点和模型参数的状态， 直到满足收敛或停止标准．随着数据的规模日益增长， 分布式迭代计算成为大数据处理与分析的研究热点之一． 近年来， 流行的大数据处理平台ＨａｄｏｏｐＤ３］、 Ｓｐａｒｋ［１ ４］和ＦｌｉｎｋＤ５］都具备处理迭代任务的能力． 现有的分布式迭代包含全量迭代和增量迭代两种． 全量迭代总是重新计算迭代的中间结果． 然而许多情况下， 迭代任务的中间状态会以不同的速度汇聚． 例如， 在大图的单源最短路径的计算中． 在这种情况下， 系统总是重新计算整个中间状态包括不再变化的部分， 从而导致资源浪费． 增量迭代可以有效地缓解该问题． 该模式使用两个数据迭代状态模拟迭代计算： 解集和工作集． 解集保存当前中间结果， 而工作集保存解集的更新结果． 在增量迭代期间， 系统使用工作集有选择地更新解集的元素， 并根据更新计算下一个工作集．一旦工作集变空， 迭代就会终止． 无论是全量迭代还是增量迭代， 对海量数据而言， 都是极其耗时的， 并且消耗大量的计算资源．由于分布式计算通常涉及大量计算节点的协同工作， 容错性是分布式系统高可用性的必要保证． 主流的分布式大数据平台针对迭代计算任务采取了不同的容错机制． 分布式系统Ｈａｄｏｏｐ 的迭代容错机制主要是通过检查点机制的方式实现， 在每个计算的结束阶段设置检查点， 发生故障时从检查点读取数据重新执行． 反复从底层文件系统中读取数据会造成大量的磁盘１０开销． 分布式系统Ｓｐａｒｋ框架中的ＳｐａｒｋＳｔｒｅａｍｉ ｎｇ采用记录更新的手段实现容错，通过Ｌｉ ｎｅａｇｅ？技术来实现． 对于窄依赖（ 父ＲＤＤ的每个分区只被子ＲＤＤ的一个分区所引用） 的数据因发生故障丢失时， 只需要对丢失的那一部分数据进行恢复并重新计算； 对于宽依赖（ 父ＲＤＤ的每个分区可能被多个子ＲＤＤ引用） 则必须将其祖先ＲＤＤ中的所有数据块全部恢复并重新进行计算． 在宽依赖场景下Ｓｐａｒｋ引人了检查点机制， 在执行过程中选取适当的时机备份， 通过缩短Ｌｉ ｎｅａｇｅ 链长度来减少容错开销． 但在执行过程中， 频繁的数据备份操作也会产生极大的网络和磁盘１〇开销． 分布式系统Ｆｌ ｉｎｋ系统现有的批处理和流处理的容错分别采用了逆向恢复容错技术和前向恢复技术． 批处理容错机制是当Ｊｏｂ失败时通过使用重启策略对整个Ｊｏｂ 重启． 流处理容错机制是基于状态一致的分布式快照实现的， 这些快照保存了执行图中所有算子及传输通道的状态， 这些轻量级快照也可以被视做一种另类的检查点． Ｆｌ ｉｎｋ 的分布式快照采用Ｃｈａｎｄｙ－Ｌａｍｐｏｒｔ［ｌ７］算法实现． 该容错机制虽然高效， 但需要额外的检查点协调者来实现， 管理复杂，且会带来额外的写入开销． Ｆｌ ｉ ｎｋ虽然针对其流处理也可以进行迭代计算， 在实际应用场景下， 大部分的迭代计算任务还是基于批处理执行． 综上， 现有分布式系统的容错机制大多面向通用的计算任务， 在迭代任务上的容错效率较低， 没有结合迭代计算任务的特点， 代价开销较大．传统分布式系统的容错机制大多采用了悲观的检查点容错机制． 通过缓存管理检查点的实现， 与流水线数据流无关． 然而， 这些检查点是以阻塞的方式备份数据， 开销较大， 且忽略了迭代处理的迭代控制， 这使系统设计复杂化， 因为需要额外的组件来管理检査点． 此外， 以分布式方式在海量数据集上执行迭代算法， 算法的中间结果必须在机器之间进行分区存储． 执行失败将导致丢失这些分区的子集， 要继续执行， 系统必须首先恢复丢失的数据． 发生故障时， 系统将暂停执行， 从先前写人的检查点恢复一致状态并继续执行． 这种方法的缺点是， 即使在无故障的情况下， 它也会给执行带来开销． 对于海量数据的迭代算法， 检査点不必要增加了计算的延迟． 现有分布式系统缺少了乐观的容错机制， 悲观的容错机制忽略了分布式迭代数据流的特点， 以阻塞的方式实现容错， 代价开销大， 容错效率低．针对现有分布式系统迭代容错机制的不足， 本文面向大规模分布式迭代计算任务主要贡献有：（１） 提出了基于补偿函数的乐观容错机制． 该容错机制在迭代执行过程中不采用任何额外的容错手段（ 不会引人额外的容错开销）， 在发生故障时， 采用用户自定义的补偿函数收集健康节点上的迭代数据， 并结合初始的迭代数据对丢失的分区数据进行恢复， 保证了迭代任务高效顺利的执行．（２） 提出了一种基于头尾检查点的悲观容错机制． 与传统的阻塞检查点不同， 该容错机制以无阻塞的方式编写检査点， 不会破坏流水线操作任务． 将可变数据集的检査点注人迭代数据流本身， 简化系统架构并有助于在迭代处理期间检查点的创建．（３） 将提出的面向迭代任务的乐观补偿函数容错机制和悲观的头尾检查点机制基于高度创新的开源流处理器Ｆｌｉ ｎｋ进行实现． 乐观的补偿函数机制２１０４ 计 算机 学 报２０２０年的实现设置了收集数据和补偿恢复丢失数据的接口， 可供用户直接使用． 头尾检查点机制的实现， 在Ｍｉ ｎｋ迭代处理框架中新增了头尾检查点选项， 用户可根据迭代任务类型直接选择．（４） 在真实数据集和模拟数据集上从全量迭代和增量迭代方面进行了系统的实验研究， 验证了本文提出的容错技术的高效性．本文第２ 节介绍相关工作； 第３ 节介绍文中涉及的基本概念； 第４节描述基于补偿函数的乐观容错机制； 第５ 节介绍基于头尾检査点的悲观容错机制；第６节为实验分析部分； 第７ 节总结了本文的工作．２相关工作目前， 国内外被各大企业和研究机构所使用的分布式计算系统主要包括批处理系统， 如Ｈａｄｏ叩．流处理系统， 如Ｓｔｏｒｍ和Ｓａｍｚａ． 混合处理系统（ 既支持批处