| 面向Flink迭代计算的高效容错处理技术_郭文鹏 |
| 来源：一起赢论文网 日期：2021-02-01 浏览数：1954 【 字体： 大 中 小 大 中 小 大 中 小 】 |
|
第４ ３ 卷第１ １ 期２ ０２ ０ 年１ １ 月计算机学报ＣＨ Ｉ Ｎ ＥＳＥＪ Ｏ ＵＲ Ｎ Ａ ＬＯ ＦＣ ＯＭＰ ＵＴ ＥＲＳＶｏｌ ． ４ ３Ｎ ｏ ． １ １Ｎｏ ｖ． ２ ０２ ０面向Ｆｌ ｉ ｎｋ 迭代计算的高效容错处理技术郭文鹏ｎ赵宇海＂王国仁２ ）韦刘国ｎ东北大学计算机科学与工程学院沈阳１ １ ０ １ ６９ ）２ ）（ 北京理工大学计算机学院北京１ ０ ０ ０ ８ １ ）摘要迭代计算是相同逻辑的重复执行， 在各种机器学习和数据挖掘方法中被广泛使用． 在大数据的处理与分析领域中， 分布式迭代计算更是当前的热点研究问题之一． 容错机制是分布式系统高可用性的必要保证． 现有分布式系统的容错机制虽然在髙可用性上表现良好， 但忽略了面向迭代计算的容错效率问题． 本文针对批流混合大数据计算系统Ａ ｐａｃ ｈ ｅ Ｆ ｌ ｉ ｎｋ 的迭代容错效率问题， 进行了系统的研究． 执行流处理任务时， Ｆ ｌ ｉ ｎ ｋ 采用“ 分布式快照”的检查点机制来完成容错． 对于海量数据的迭代分析， 检查点增加了不必要的延迟． 执行批处理任务时， Ｆ ｌ ｉｎ ｋ 采用从头执行任务的方式来实现容错， 该方式虽然实现简单， 但带来了很大的时间开销． 针对以上问题， 本文首先提出了一种基于补偿函数的乐观迭代容错机制． 该容错机制在迭代任务发生故障时采用乐观补偿的思想恢复任务， 在迭代执行过程中不采用任何额外的容错手段（ 不会引人额外的容错开销） ， 采用用户自定义的补偿函数收集健康节点上的迭代数据， 并结合初始的迭代数据对故障节点上丢失的分区数据进行恢复， 继续执行至迭代收敛状态， 保证了迭代任务的高效顺利执行． 由于乐观迭代容错机制并不保证得到的结果与无故障执行得到的结果完全一致， 因此针对精度要求较高的迭代任务， 本文结合Ｆｌ ｉ ｎ ｋ 系统的迭代数据流模型， 进一步提出一种基于头尾检査点悲观迭代容错机制． 与传统的阻塞检査点（ 阻塞下游操作符） 的工作方式不同， 该容错机制以非阻塞的方式编写检査点， 充分结合Ｆ Ｕ ｎｋ 迭代数据流的特点， 将可变数据集的检查点注人迭代流本身． 通过设计迭代感知， 简化了系统架构， 降低了检査点成本和故障恢复时间． 本文基于Ｆｌ ｉ ｎ ｋ 系统， 在大量的真实数据集和模拟数据集上， 从增量迭代和全量迭代两方面对提出的两种容错机制进行了全面的实验研究， 验证了本文提出的迭代容错优化技术的高效性． 实验结果证实， 本文基于Ｆｌ ｉ ｎｋ 系统提出的乐观容错机制和悲观容错机制在计算效率上均优于现有的分布式迭代容错机制． 前者在全量迭代计算任务中运行时间最髙可提升２ ２ ． ８ ％ ， 在增量迭代计算任务中最髙可提升３ ３． ８ ％ ； 后者在全量迭代任务中最高可节省１ ５ ．３ ％ 的时间开销， 在增量迭代任务中最高可节省１ ８ ． ５ ％ 的时间开销．关键词分布式迭代计算； Ａｐａ ｃ ｈ ｅ Ｆｌ ｉ ｎ ｋ ； 乐观容错； 悲观容错； 检查点中图法分类号ＴＰ １ ８ＤＯＩ号１ ０ ． １ １ ８ ９ ７／ＳＰ ． Ｊ ． １ ０ １ ６． ２ ０ ２ ０ ． ０ ２ １ ０ １Ｅ ｆｆｉ ｃ ｉｅｎ ｔ Ｆ ａｕｌ ｔ－Ｔｏｌｅｒａ ｎｔ Ｐｒｏｃ ｅｓｓ ｉｎ ｇＴｅ ｃｈ ｎｏｌ ｏｇｙｆｏｒＦｌ ｉｎ ｋＩ ｔ ｅｒａ ｔ ｉｖｅＣｏｍｐｕｔ ｉｎｇＧＵ ＯＷｅ ｎ－ Ｐ ｅｎ ｇｎＺ Ｈ ＡＯ Ｙ ｕ－Ｈ ａｉ１）ＷＡＮ ＧＧｕ ｏ－ Ｒｅ ｎ２ ）ＷＥＩ Ｌｉ ｕ－Ｇｕ ｏｎｌ） （．Ｓ ｃｈ ｏ ｏ ｌｏ ｆＣｏ ｍｐ ｕ ｔ ｅｒ Ｓｃ ｉｅ ｎｃ ｅ ａ ｎ ｄＥｎｇ ｉ ｎ ｅｅｒ ｉｎ ｇ ＾Ｎｏ ｒｔｈ ｅａ ｓ ｔｅ ｒｎ Ｕｎ ｉｖｅ ｒｓ ｉ ｔｙ ＊ Ｓｈ ｅｎ ｙａ ｎｇ１ １ ０ １ ６ ９ ）２ ＞ （ Ｓ ｃ ｈｏ ｏｌ ｏ ｆＣｏ ｍ ｐｕ ｔｅ ｒ Ｓｃ ｉｅｎ ｃｅ ａ ｎｄ Ｔｅｃ ｈ ｎ ｏ ｌｏ ｇ ｙ？ Ｂｅｉｊｉ ｎｇ Ｉ ｎ ｓ ｔ ｉ ｔ ｕ ｔ ｅ ｏｆ Ｔｅｃｈ ｎ ｏｌ ｏ ｇｙ Ｕｎ ｉ ｖｅｒｓ ｉ ｔｙ ， Ｂ ｅｉｊｉ ｎｇ１ ０ ００ ８ １ ）Ａｂ ｓ ｔ ｒａｃ ｔＩ ｔ ｅ ｒ ａ ｔｉ ｖｅ ｃ ａ ｌ ｃ ｕｌ ａ ｔ ｉ ｏ ｎ ｉｓ ｔｈ ｅ ｒ ｅ ｐｅ ａ ｔ ｅｄ ｅ ｘｅ ｃ ｕｔ ｉｏ ｎｏ ｆ ｔｈ ｅ ｓａｍｅ ｌ ｏｇ ｉ ｃａ ｎｄ ｉ ｓｗ ｉ ｄ ｅｌ ｙ ｕ ｓ ｅ ｄ ｉ ｎｖａ ｒ ｉｏ ｕｓ ｍａ ｃｈｉ ｎ ｅｌｅ ａｒｎ ｉｎ ｇａｎ ｄｄａ ｔ ａｍ ｉ ｎｉ ｎｇｍ ｅｔ ｈｏｄｓ ．Ｉ ｎ ｔ ｈｅ ｆ ｉｅ ｌ ｄｏｆｂ ｉｇｄａｔａｐｒｏｃ ｅｓｓ ｉｎ ｇａ ｎｄａ ｎａ ｌ ｙｓｉ ｓ ，ｄ ｉ ｓ ｔ ｒｉ ｂ ｕｔ ｅ ｄｉ ｔｅ ｒ ａ ｔ ｉ ｖｅｃｏｍ ｐ ｕｔ ｉ ｎｇ ｉ ｓ ｏ ｎｅ ｏｆ ｔ ｈｅ ｃ ｕｒ ｒ ｅ ｎｔｈ ｏｔ ｒｅ ｓ ｅ ａ ｒ ｃｈ ｉ ｓ ｓ ｕ ｅｓ ．Ｆ ａｕ ｌ ｔ ｔｏ ｌ ｅｒ ａ ｎ ｃｅ ｉ ｓ ａｎ ｅ ｃ ｅ ｓ ｓ ａ ｒｙｇ ｕａ ｒ ａ ｎ ｔｅ ｅ ｆ ｏｒｈ ｉ ｇｈ ａ ｖａ ｉｌａ ｂｉｌｉ ｔ ｙｏ ｆｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕｔ ｅ ｄｓ ｙ ｓｔ ｅｍ ｓ ．Ａｌ ｔ ｈｏ ｕｇ ｈ ｔ ｈｅ ｆ ａ ｕ ｌ ｔｔｏ ｌ ｅ ｒ ａ ｎｃ ｅｍ ｅｃ ｈａｎ ｉ ｓｍｏｆ ｅ ｘ ｉ ｓ ｔ ｉ ｎｇ ｄｉ ｓ ｔ ｒ ｉ ｂｕｔ ｅｄ ｓｙ ｓ ｔ ｅｍ ｓｐ ｅｒ ｆｏｒｍ ｓｗ ｅｌ ｌ ｉ ｎｈｉ ｇｈ ａ ｖａｉ ｌ ａｂｉ ｌ ｉｔ ｙ ，ｉ ｔ ｉｇ ｎｏ ｒ ｅｓ ｔｈ ｅｐｒ ｏｂ ｌｅ ｍｏｆ ｆａｕ ｌ ｔ ｔｏ ｌ ｅ ｒａｎ ｃ ｅｅ ｆｆ ｉ ｃ ｉ ｅ ｎ ｃｙｆ ｏｒ ｉ ｔ ｅｒ ａ ｔｉ ｖｅ ｃｏ ｍｐ ｕｔ ｉ ｎ ｇ．Ｔ ｈ ｉ ｓ ｐａ ｐ ｅｒ ｓｙｓ ｔ ｅｍａ ｔｉ ｃａ ｌ ｌｙ ｓｔ ｕ ｄ ｉｅ ｓ ｔ ｈ ｅ ｉ ｔｅ ｒａ ｔｉ ｖ ｅ收稿日期： ２ ０ １ ９－ ０ ９ － ０ ２； 在线发布日期： ２ ０ ２ ０－０ ２ －１ ３ ． 本课题得到科技部重点研发项目“ 云计算和大数据” 重点专项项目（ ２ ０ １ ８ ＹＦＢ１ ０ ０ ４ ４ ０ ２ ）和国家自然科学基金（ ６ １ ７ ７ ２ １ ２ ４ ） 资助． 郭文鹏， 硕士研究生， 主要研究方向为大数据． Ｅ－ｍａ ｉ ｌ ： １ ７ ６ ２ ８ ８ ２ ２ ３ ２ ４ ＠ ｑ ｑ ． ｃ ｏｍ． 赵宇海（ 通信作者） ， 博士， 教授， 中国计算机学会（ 〇＾ ） 高级会员， 主要研究领域为数据挖掘． ￡－１ １＾丨： ２１ １３ 〇７ １ １１＾ ＠１ １＾１ ．１１扣． ６（１１ １． 〇１ ． 王国仁， 博士， 教授，中国计算机学会（ ＣＣＦ ） 高级会员， 主要研究领域为数据库． 韦刘国， 硕士研究生， 主要研究方向为大数据．２ １ ０ ２ 计算机学报 ２ ０ ２ ０ 年ｆ ａ ｕｌ ｔ－ｔ ｏ ｌｅ ｒ ａ ｎ ｔｅ ｆ ｆｉ ｃ ｉ ｅ ｎｃ ｙｏｆ ｂａ ｔｃ ｈ－ｆ ｌｏ ｗ ｈ ｙｂｒ ｉｄ ｂｉ ｇ ｄａ ｔａ ｃ ｏｍｐ ｕｔ ｉ ｎｇ ｓｙ ｓ ｔ ｅ ｍＡｐ ａｃ ｈｅ Ｆ ｌｉ ｎｋ ．Ｗｈ ｅｎｐｅ ｒ ｆ ｏｒｍ ｉ ｎｇｓ ｔ ｒ ｅ ａｍ ｐｒ ｏ ｃｅ ｓ ｓ ｉ ｎｇｔ ａ ｓ ｋｓ ， Ｆ ｌｉｎ ｋ ｕｓ ｅｓ ａ “ｄ ｉ ｓ ｔ ｒ ｉ ｂｕ ｔ ｅｄ ｓｎ ａｐ ｓｈ ｏｔ” ｃｈ ｅｃ ｋｐ ｏｉ ｎｔ ｍ ｅｃ ｈａ ｎ ｉｓ ｍｔ ｏｃｏｍ ｐ ｌ ｅｔ ｅ ｆａ ｕ ｌ ｔｔｏ ｌ ｅｒ ａ ｎ ｃｅ．Ｆ ｏｒ ｉｔ ｅ ｒ ａ ｔ ｉｖ ｅ ａ ｎａ ｌ ｙｓ ｉｓ ｏｆ ｍａ ｓ ｓ ｉ ｖ ｅｄａ ｔ ａ ，ｃｈ ｅ ｃｋ ｐｏ ｉｎ ｔ ｓ ａ ｄ ｄｕｎ ｎｅ ｃｅ ｓｓ ａ ｒｙｄｅ ｌ ａ ｙ．Ｗｈ ｅ ｎｐ ｅｒ ｆ ｏｒｍ ｉｎ ｇｂ ａ ｔｃ ｈｐ ｒｏｃ ｅｓ ｓ ｉｎ ｇｔ ａ ｓｋ ｓ ，Ｆ ｌ ｉｎ ｋ ｕｓ ｅｓ ｔ ｈ ｅｔ ａ ｓｋ ｅ ｘｅ ｃｕ ｔｉ ｏ ｎｍｅ ｔ ｈｏ ｄｆｒ ｏｍ ｔ ｈｅｂｅ ｇｉ ｎ ｎ ｉ ｎｇｔ ｏａ ｃｈ ｉ ｅｖｅ ｆ ａ ｕ ｌ ｔ ｔ ｏｌ ｅ ｒａ ｎ ｃｅ ．Ａ ｌ ｔ ｈ ｏｕ ｇｈ ｔ ｈｉ ｓｍｅ ｔ ｈｏｄ ｉ ｓ ｓ ｉｍ ｐｌ ｅ ｔ ｏｉ ｍｐ ｌ ｅｍ ｅｎ ｔ ，ｉ ｔｂ ｒ ｉ ｎｇ ｓ ａ ｌ ｏｔｏｆ ｔ ｉ ｍｅｏ ｖｅｒ ｈｅ ａ ｄ．Ｉ ｎｖ ｉ ｅ ｗｏｆ ｔ ｈ ｅ ａ ｂｏ ｖｅｐ ｒ ｏｂ ｌ ｅｍｓ ？ ｔｈ ｉ ｓ ｐａ ｐ ｅｒ ｆｉ ｒ ｓ ｔｐｒｏ ｐｏ ｓ ｅ ｓ ａ ｎ ｏｐ ｔｉ ｍ ｉ ｓ ｔ ｉ ｃ ｉ ｔ ｅ ｒ ａ ｔｉ ｖｅｆａ ｕ ｌ ｔｔ ｏｌ ｅ ｒ ａ ｎ ｃ ｅｍｅ ｃｈ ａ ｎ ｉ ｓｍｂａ ｓ ｅｄｏ ｎｃ ｏｍ ｐｅ ｎｓ ａｔ ｉ ｏ ｎ ｆ ｕ ｎｃ ｔ ｉｏ ｎ ｓ ．Ｔｈ ｉ ｓｆ ａ ｕ ｌ ｔ－ｔ ｏｌ ｅ ｒａｎ ｔｍｅ ｃｈ ａ ｎｉ ｓｍ ｕｓ ｅ ｓｏｐｔ ｉ ｍｉ ｓ ｔ ｉ ｃｃ ｏｍｐ ｅｎ ｓ ａ ｔ ｉ ｏｎｔ ｏｒ ｅｃ ｏｖｅ ｒ ｔ ａｓ ｋ ｓ ｗ ｈ ｅ ｎｉ ｔ ｅ ｒａ ｔ ｉ ｖ ｅｔ ａ ｓｋ ｓｆａ ｉｌ ．Ｉ ｔｄ ｏｅ ｓ ｎ ｏｔ ｕｓｅ ａ ｎｙａ ｄｄ ｉ ｔｉ ｏｎ ａ ｌｆ ａ ｕ ｌ ｔ－ｔ ｏ ｌ ｅ ｒ ａ ｎ ｔｍｅ ｔｈ ｏｄ ｓ （ ｉ ｔｄ ｏｅ ｓｎ ｏｔｉ ｎｔ ｒ ｏ ｄｕ ｃ ｅ ａ ｄ ｄｉ ｔ ｉ ｏｎａ ｌｆａ ｕ ｌｔ－ｔ ｏｌ ｅｒ ａｎ ｔ ｏｖ ｅ ｒｈ ｅ ａｄ ） ｄ ｕｒ ｉ ｎ ｇｉ ｔ ｅ ｒａ ｔ ｉ ｖ ｅｅ ｘｅｃ ｕ ｔ ｉ ｏ ｎ ， ａ ｎｄ ｕ ｓ ｅ ｓ ｕ ｓ ｅｒ － ｄ ｅｆ ｉ ｎｅ ｄ ｃｏｍ ｐｅ ｎ ｓ ａ ｔ ｉ ｏｎ ｆｕ ｎ ｃ ｔ ｉｏ ｎｓ ｔ ｏ ｃｏｌ ｌｅ ｃ ｔ ｈｅ ａ ｌ ｔ ｈ ｙｎ ｏｄ ｅ ｓ．Ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖｅ ｄａ ｔ ａ ＊ｃ ｏｍ ｂｉ ｎ ｅｄｗ ｉ ｔ ｈｔ ｈｅ ｉ ｎｉ ｔ ｉ ａ ｌｉｔ ｅ ｒ ａ ｔ ｉｖ ｅｄ ａ ｔ ａ ， ｒ ｅｃ ｏｖｅ ｒ ｓｔｈ ｅｌ ｏｓ ｔｐａ ｒ ｔ ｉ ｔ ｉｏｎ ｄ ａ ｔａ ｏ ｎｔ ｈｅ ｆ ａ ｉ ｌ ｅｄｎｏ ｄｅ ，ａ ｎｄｃ ｏｎｔ ｉ ｎｕ ｅ ｓｅｘ ｅｃ ｕ ｔ ｉｏｎｔｏｔ ｈｅｉ ｔｅ ｒ ａ ｔｉ ｖｅｃｏｎ ｖｅｒ ｇｅ ｎｃ ｅｓ ｔ ａ ｔ ｅ ，ｅ ｎ ｓ ｕ ｒ ｉ ｎｇｔ ｈ ｅｅ ｆｆ ｉ ｃ ｉ ｅ ｎｔ ａｎ ｄｓ ｍｏｏｔ ｈｅ ｘ ｅｃ ｕｔ ｉ ｏｎｏ ｆ ｔ ｈ ｅ ｉｔ ｅ ｒ ａ ｔｉ ｖ ｅｔ ａ ｓｋ ． Ｂｅ ｃ ａ ｕ ｓｅ ｔ ｈｅ ｏｐ ｔ ｉｍ ｉ ｓ ｔ ｉｃ ｉ ｔ ｅｒ ａ ｔ ｉ ｖｅｆ ａ ｕｌ ｔ ｔ ｏｌ ｅ ｒ ａ ｎｃ ｅｍ ｅｃ ｈ ａｎ ｉ ｓｍｄ ｏｅ ｓ ｎｏ ｔｇ ｕａ ｒ ａ ｎ ｔ ｅｅｔ ｈ ａｔ ｔ ｈｅ ｒ ｅ ｓｕ ｌｔ ｓ ｏ ｂｔａ ｉ ｎｅｄ ａ ｒ ｅ ｃｏｍｐ ｌｅ ｔｅ ｌ ｙｃｏｎｓ ｉｓ ｔ ｅ ｎｔ ｗ ｉ ｔｈｔ ｈ ｅｒｅ ｓ ｕｌ ｔ ｓ ｏｂ ｔａ ｉｎ ｅｄｂ ｙｆａ ｕｌ ｔ－ｆｒ ｅ ｅ ｅ ｘｅｃｕ ｔｉ ｏｎ ，ｆ ｏｒ ｔ ｈ ｅｉ ｔ ｅ ｒ ａ ｔ ｉｏ ｎ ｔａ ｓ ｋｓ ｗｉ ｔ ｈ ｈｉ ｇ ｈｅ ｒａ ｃｃ ｕ ｒａ ｃ ｙｒ ｅ ｑｕ ｉｒ ｅ ｍｅ ｎ ｔ ｓ ，ｔ ｈ ｉｓ ｐａ ｐ ｅｒ ｃ ｏｍｂ ｉ ｎ ｅｓ ｔ ｈ ｅ ｉｔ ｅ ｒ ａ ｔｉ ｖｅ ｄａ ｔ ａｆ ｌ ｏｗ ｍｏ ｄ ｅ ｌｏ ｆ ｔ ｈ ｅＦｌｉ ｎ ｋ ｓ ｙｓ ｔ ｅ ｍｔ ｏ ｆ ｕｒ ｔｈ ｅ ｒｐｒｏｐ ｏ ｓ ｅ ａ ｈｅ ａ ｄ－ｔｏ－ｔ ａ ｉｌ ｃｈ ｅ ｃｋ ｐｏ ｉ ｎｔ ．Ｐ ｅ ｓ ｓｉ ｍｉ ｓ ｔ ｉｃ ｉ ｔ ｅｒ ａ ｔ ｉ ｖｅｆ ａ ｕｌｔ ｔｏ ｌｅ ｒ ａｎ ｃｅｍｅｃｈ ａ ｎｉ ｓｍ．Ｕ ｎｌ ｉｋ ｅ ｔ ｒａ ｄｉ ｔ ｉｏｎａ ｌｂ ｌ ｏｃ ｋｉ ｎｇｃｈ ｅｃ ｋｐｏｉ ｎ ｔｓ （ ｂｌ ｏｃｋｉ ｎｇ ｄｏｗｎｓｔｒｅａｍｏｐｅ ｒａ ｔｏｒ ｓ ） ，ｔ ｈ ｉ ｓ ｆａ ｕ ｌ ｔ－ｔ ｏｌ ｅ ｒ ａ ｎｔｍ ｅｃ ｈａ ｎ ｉ ｓｍｗ ｒ ｉ ｔ ｅｓｃ ｈｅ ｃ ｋｐ ｏｉ ｎ ｔ ｓｉ ｎａ ｎｏｎ－ ｂ ｌ ｏｃ ｋ ｉｎ ｇｍａ ｎ ｎｅ ｒ ，ｆｕ ｌ ｌｙ ｃｏ ｍｂｉ ｎ ｅ ｓ ｔｈ ｅｃ ｈａ ｒ ａ ｃ ｔ ｅｒ ｉｓ ｔｉ ｃ ｓ ｏｆ Ｆ ｌ ｉｎ ｋｉ ｔ ｅ ｒａ ｔ ｉ ｖｅｄ ａｔ ａ ｆ ｌ ｏｗ ， ａ ｎｄｉｎｊ ｅ ｃ ｔ ｓ ｖａ ｒ ｉ ａｂ ｌ ｅｄａ ｔ ａｓ ｅｔｃ ｈ ｅｃｋ ｐｏ ｉ ｎｔ ｓｉ ｎｔ ｏｔｈ ｅｉ ｔ ｅ ｒａ ｔｉ ｖｅ ｆｌ ｏ ｗｉ ｔ ｓ ｅｌ ｆ．Ｂｙｄ ｅｓ ｉｇ ｎ ｉｎ ｇｉ ｔ ｅｒ ａ ｔｉ ｖｅ ａｗａ ｒ ｅ ｎ ｅｓ ｓ ，ｔ ｈ ｅｓｙ ｓ ｔ ｅ ｍａｒ ｃｈ ｉ ｔ ｅｃ ｔｕ ｒ ｅｉ ｓ ｓ ｉ ｍｐ ｌ ｉｆ ｉ ｅ ｄ ，ａ ｎｄｃ ｈｅ ｃ ｋｐ ｏｉ ｎ ｔ ｃｏ ｓ ｔ ｓ ａｎ ｄ ｆａ ｉ ｌ ｕ ｒ ｅ ｒ ｅｃ ｏ ｖｅ ｒｙ ｔｉ ｍ ｅｓ ａ ｒ ｅ ｒｅ ｄ ｕｃ ｅｄ ．Ｔ ｈｉ ｓｐａ ｐｅ ｒ ｉ ｓ ｂａ ｓ ｅｄ ｏｎ ｔｈ ｅ Ｆｌ ｉ ｎ ｋ ｓｙｓ ｔ ｅｍ ．Ｏ ｎａ ｌａ ｒｇ ｅｎ ｕｍ ｂ ｅ ｒ ｏ ｆ ｒ ｅ ａｌ ｄａ ｔ ａ ｓ ｅｔ ｓ ａｎ ｄｓ ｉｍ ｕｌ ａｔ ｅ ｄｄ ａｔ ａｓ ｅｔ ｓ ，ａ ｃｏｍｐ ｒ ｅ ｈ ｅｎ ｓ ｉ ｖｅ ｅ ｘｐ ｅ ｒ ｉ ｍｅ ｎｔ ａ ｌｓ ｔ ｕｄｙｏ ｆ ｔｈ ｅ ｔ ｗ ｏｐｒ ｏ ｐｏ ｓ ｅｄｆａ ｕｌ ｔｔ ｏｌ ｅ ｒ ａ ｎ ｃ ｅｍ ｅｃ ｈａ ｎ ｉ ｓｍ ｓ ｆ ｒｏｍ ｔ ｈｅ ａ ｓ ｐｅ ｃｔ ｓ ｏｆ ｉ ｎｃ ｒ ｅ ｍｅ ｎｔ ａ ｌ ｉ ｔ ｅｒ ａｔ ｉ ｏｎ ａ ｎ ｄ ｆ ｕ ｌ ｌｉ ｔ ｅｒ ａ ｔ ｉ ｏｎ ｉｓ ｃ ｏｎ ｄｕ ｃ ｔ ｅｄ ， ａｎ ｄｔ ｈｅ ｅｆ ｆｅ ｃｔ ｉ ｖｅ ｎ ｅｓ ｓ ｏｆ ｔ ｈｅｐｒ ｏ ｐｏｓ ｅｄｉ ｔ ｅｒ ａｔ ｉ ｖｅ ｆ ａ ｕｌ ｔｔ ｏｌ ｅ ｒ ａｎ ｃｅ ｏｐ ｔｉ ｍ ｉｚ ａｔ ｉ ｏｎｔ ｅ ｃｈ ｎｏ ｌ ｏｇ ｙ ｉ ｓｖｅ ｒ ｉｆ ｉ ｅｄ ．Ｅｆ ｆｉ ｃ ｉ ｅ ｎ ｃｙ．Ｔ ｈ ｅｅ ｘ ｐｅ ｒ ｉ ｍｅ ｎ ｔａ ｌｒ ｅ ｓｕ ｌ ｔ ｓｃｏ ｎｆ ｉ ｒｍｔ ｈ ａ ｔｔ ｈ ｅｏｐ ｔ ｉ ｍｉ ｓ ｔ ｉ ｃａ ｎｄｐ ｅｓ ｓ ｉ ｍｉ ｓ ｔ ｉ ｃｆａ ｕ ｌ ｔ－ｔｏ ｌ ｅｒ ａ ｎｔ ｍｅ ｃｈ ａ ｎｉ ｓｍ ｓｐ ｒｏｐ ｏｓ ｅｄｉ ｎｔ ｈｉ ｓｐａ ｐ ｅ ｒｂａ ｓ ｅ ｄｏ ｎｔ ｈ ｅＦｌｉ ｎ ｋｓ ｙｓ ｔｅ ｍａ ｒ ｅｓ ｕｐ ｅｒ ｉ ｏ ｒ ｔｏｔ ｈｅ ｅｘ ｉｓ ｔ ｉｎ ｇｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕｔ ｅｄ ｉｔ ｅ ｒａ ｔ ｉ ｖｅｆ ａ ｕｌ ｔ－ｔ ｏｌ ｅ ｒａ ｎ ｔｍ ｅｃ ｈａ ｎ ｉ ｓｍｓ ｉｎ ｔ ｅｒｍ ｓ ｏｆ ｃｏｍ ｐｕ ｔ ａｔ ｉ ｏｎ ａ ｌｅ ｆｆ ｉ ｃｉ ｅ ｎｃ ｙ．Ｔ ｈｅ ｆ ｏｒｍ ｅｒ ｃａ ｎ ｉ ｎ ｃｒ ｅ ａ ｓｅ ｔ ｈ ｅｒ ｕｎ ｎｉ ｎ ｇ ｔ ｉｍ ｅｂ ｙｕ ｐ ｔ ｏ ２ ２ ． ８ ％ ｉ ｎｆ ｕ ｌ ｌｉ ｔ ｅ ｒａ ｔｉ ｖｅ ｃｏｍ ｐ ｕｔ ｉ ｎｇｔ ａ ｓｋ ｓ ａ ｎｄｕ ｐ ｔｏ ３ ３ ． ８ ％ｉ ｎ ｉ ｎ ｃ ｒ ｅ ｍｅ ｎｔ ａ ｌ ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ ｃ ｏｍｐ ｕ ｔｉ ｎ ｇｔ ａ ｓｋ ｓ ；ｔ ｈｅ ｌ ａｔ ｔ ｅ ｒ ｃ ａｎ ｓ ａｖ ｅ ｕｐ ｔ ｏ １ ５ ． ３ ％ｏ ｆｔ ｈ ｅｔ ｉｍ ｅｏ ｖ ｅｒ ｈ ｅａ ｄｉ ｎ ｆ ｕ ｌ ｌｉ ｔ ｅｒ ａ ｔ ｉ ｖｅｔ ａ ｓｋ ｓ ？ａ ｎ ｄ ｉ ｎ ｉｎ ｃ ｒ ｅｍｅ ｎ ｔ ａ ｌ ｉ ｔ ｅｒａ ｔ ｉ ｖｅ ｔ ａｓ ｋ ｓ Ｓ ａ ｖｅ ｓ ｕｐ ｔｏ １ ８ ． ５ ％ｏｆ ｔ ｉ ｍｅ．Ｋ ｅｙｗｏｒｄｓｄｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ ｉ ｔ ｅｒ ａ ｔ ｉ ｖｅ ｃ ａ ｌ ｃ ｕｌ ａ ｔ ｉ ｏｎ ；Ａ ｐａ ｃｈ ｅ Ｆｌｉｎ ｋ ；ｏｐ ｔ ｉｍ ｉｓ ｔｉ ｃ ｆａ ｕ ｌ ｔ ｔｏ ｌ ｅ ｒａ ｎ ｃｅ ；ｐ ｅｓ ｓ ｉ ｍｉ ｓ ｔｉ ｃｆ ａ ｕｌ ｔ ｔ ｏ ｌ ｅｒａ ｎ ｃｅ ； ｃ ｈ ｅｃ ｋ ｐｏｉ ｎ ｔｉ 引言迭代计算通常是数据挖掘和机器学习算法的核心部分， 在各类应用中都普遍存在［ １ ］． 在搜索领域， 由Ｇｏ ｏｇ ｌ ｅ 提出的著名的网页排序算法Ｐ ａｇ ｅ Ｒａ ｎｋ ［ ２ ３］，其核心思想就是根据网络之中不同网页之间的链接关系进行迭代计算［ １ ］， 最终的排名即是迭代最终收敛的值或重要性； 在社交网络［５ ７］ 领域， 很多好友推荐算法都是通过利用现有用户的好友关系网络图通过迭代计算来挖掘用户之间可能存在的潜在链接关系； Ｒａ ｎ ｄｏｍ Ｗａ ｌ ｋ［８ ９］ 算法通过迭代计算来求解图中某节点到其它节点的概率； 在影音推荐领域， 常用的推荐算法是按照用户的喜好来对用户进行聚类， 然后向用户推荐同类用户所喜欢的影音资源， 这类方法统称为协同过滤推荐［ｉ Ｍ １］． 其中基于矩阵分解的协同过滤算法， 如交替最小二乘法（ ＡＬＳ ）和奇异值分解等（ ＳＶＤ） 等都包含迭代计算； 在图论郭文鹏等： 面向Ｆｌ ｉ ｎｋ 迭１ １ 代计算 的 高效 容错 处理技术 ２１ ０ ３ 期中的连通分支算法也是基于迭代实现的． 在数据分析领域中， 常用的Ｋ－Ｍ ｅ ａｎ ｓ［１？ 聚类算法、联合聚类、点对聚类等都包含迭代计算， 每次迭代时更新顶点和模型参数的状态， 直到满足收敛或停止标准．随着数据的规模日益增长， 分布式迭代计算成为大数据处理与分析的研究热点之一． 近年来， 流行的大数据处理平台Ｈ ａ ｄｏｏｐＤ ３ ］、Ｓｐ ａｒｋ ［ １ ４ ］ 和Ｆｌ ｉ ｎ ｋＤ ５ ］都具备处理迭代任务的能力． 现有的分布式迭代包含全量迭代和增量迭代两种． 全量迭代总是重新计算迭代的中间结果． 然而许多情况下， 迭代任务的中间状态会以不同的速度汇聚． 例如， 在大图的单源最短路径的计算中． 在这种情况下， 系统总是重新计算整个中间状态包括不再变化的部分， 从而导致资源浪费． 增量迭代可以有效地缓解该问题． 该模式使用两个数据迭代状态模拟迭代计算： 解集和工作集． 解集保存当前中间结果， 而工作集保存解集的更新结果． 在增量迭代期间， 系统使用工作集有选择地更新解集的元素， 并根据更新计算下一个工作集．一旦工作集变空， 迭代就会终止． 无论是全量迭代还是增量迭代， 对海量数据而言， 都是极其耗时的， 并且消耗大量的计算资源．由于分布式计算通常涉及大量计算节点的协同工作， 容错性是分布式系统高可用性的必要保证． 主流的分布式大数据平台针对迭代计算任务采取了不同的容错机制． 分布式系统Ｈａ ｄ ｏｏ ｐ 的迭代容错机制主要是通过检查点机制的方式实现， 在每个计算的结束阶段设置检查点， 发生故障时从检查点读取数据重新执行． 反复从底层文件系统中读取数据会造成大量的磁盘１ ０ 开销． 分布式系统Ｓ ｐａ ｒｋ 框架中的Ｓｐ ａｒ ｋＳｔ ｒｅ ａｍ ｉ ｎｇ 采用记录更新的手段实现容错，通过Ｌｉ ｎ ｅａ ｇｅ？ 技术来实现． 对于窄依赖（ 父ＲＤ Ｄ的每个分区只被子ＲＤＤ 的一个分区所引用） 的数据因发生故障丢失时， 只需要对丢失的那一部分数据进行恢复并重新计算； 对于宽依赖（ 父ＲＤＤ 的每个分区可能被多个子Ｒ ＤＤ 引用） 则必须将其祖先ＲＤ Ｄ 中的所有数据块全部恢复并重新进行计算． 在宽依赖场景下Ｓ ｐａ ｒｋ 引人了检查点机制， 在执行过程中选取适当的时机备份， 通过缩短Ｌ ｉ ｎ ｅａ ｇｅ 链长度来减少容错开销． 但在执行过程中， 频繁的数据备份操作也会产生极大的网络和磁盘１ 〇开销． 分布式系统Ｆ ｌ ｉｎ ｋ 系统现有的批处理和流处理的容错分别采用了逆向恢复容错技术和前向恢复技术． 批处理容错机制是当Ｊ ｏ ｂ 失败时通过使用重启策略对整个Ｊ ｏｂ 重启． 流处理容错机制是基于状态一致的分布式快照实现的， 这些快照保存了执行图中所有算子及传输通道的状态， 这些轻量级快照也可以被视做一种另类的检查点． Ｆｌ ｉｎ ｋ 的分布式快照采用Ｃｈ ａ ｎｄ ｙ－Ｌａｍｐ ｏｒ ｔ［ ｌ ７］ 算法实现． 该容错机制虽然高效， 但需要额外的检查点协调者来实现， 管理复杂，且会带来额外的写入开销． Ｆｌ ｉ ｎ ｋ 虽然针对其流处理也可以进行迭代计算， 在实际应用场景下， 大部分的迭代计算任务还是基于批处理执行． 综上， 现有分布式系统的容错机制大多面向通用的计算任务， 在迭代任务上的容错效率较低， 没有结合迭代计算任务的特点， 代价开销较大．传统分布式系统的容错机制大多采用了悲观的检查点容错机制． 通过缓存管理检查点的实现， 与流水线数据流无关． 然而， 这些检查点是以阻塞的方式备份数据， 开销较大， 且忽略了迭代处理的迭代控制， 这使系统设计复杂化， 因为需要额外的组件来管理检査点． 此外， 以分布式方式在海量数据集上执行迭代算法， 算法的中间结果必须在机器之间进行分区存储． 执行失败将导致丢失这些分区的子集， 要继续执行， 系统必须首先恢复丢失的数据． 发生故障时， 系统将暂停执行， 从先前写人的检查点恢复一致状态并继续执行． 这种方法的缺点是， 即使在无故障的情况下， 它也会给执行带来开销． 对于海量数据的迭代算法， 检査点不必要增加了计算的延迟． 现有分布式系统缺少了乐观的容错机制， 悲观的容错机制忽略了分布式迭代数据流的特点， 以阻塞的方式实现容错， 代价开销大， 容错效率低．针对现有分布式系统迭代容错机制的不足， 本文面向大规模分布式迭代计算任务主要贡献有：（ １ ） 提出了基于补偿函数的乐观容错机制． 该容错机制在迭代执行过程中不采用任何额外的容错手段（ 不会引人额外的容错开销） ， 在发生故障时， 采用用户自定义的补偿函数收集健康节点上的迭代数据，并结合初始的迭代数据对丢失的分区数据进行恢复， 保证了迭代任务高效顺利的执行．（ ２ ） 提出了一种基于头尾检查点的悲观容错机制． 与传统的阻塞检查点不同， 该容错机制以无阻塞的方式编写检査点， 不会破坏流水线操作任务． 将可变数据集的检査点注人迭代数据流本身， 简化系统架构并有助于在迭代处理期间检查点的创建．（ ３ ） 将提出的面向迭代任务的乐观补偿函数容错机制和悲观的头尾检查点机制基于高度创新的开源流处理器Ｆ ｌ ｉ ｎｋ 进行实现． 乐观的补偿函数机制２ １ ０ ４ 计算机学报 ２ ０ ２ ０年的实现设置了收集数据和补偿恢复丢失数据的接口， 可供用户直接使用． 头尾检查点机制的实现， 在Ｍｉ ｎｋ 迭代处理框架中新增了头尾检查点选项， 用户可根据迭代任务类型直接选择．（ ４ ） 在真实数据集和模拟数据集上从全量迭代和增量迭代方面进行了系统的实验研究， 验证了本文提出的容错技术的高效性．本文第２ 节介绍相关工作； 第３ 节介绍文中涉及的基本概念； 第４ 节描述基于补偿函数的乐观容错机制； 第５ 节介绍基于头尾检査点的悲观容错机制；第６ 节为实验分析部分； 第７ 节总结了本文的工作．２ 相关工作目前， 国内外被各大企业和研究机构所使用的分布式计算系统主要包括批处理系统， 如Ｈ ａ ｄｏ叩．流处理系统， 如Ｓｔ ｏｒｍ 和Ｓａ ｍｚａ ． 混合处理系统（ 既支持批处理又支持流处理的框架） ， 如Ｓｐ ａ ｒｋ 和Ｆｌｉ ｎ ｋ ． 各个计算系统都具有自己独特的容错机制，但总体上可以将这些容错机制分为两类，一类是基于检查点的容错机制，一类是基于记录更新的容错机制．分布式系统环境下， 假如某个计算节点出现故障， 集群和任务将进人故障， 容错恢复的目标是采取相应的措施， 将任务和系统转换到正确执行的状态． 分布式容错恢复技术整体上包括了前向恢复技术（ Ｆｏｒｗａ ｒｄＲｅ ｃｏｖ ｅｒｙ ）［ １８ ］ 和逆向恢复（ Ｂａ ｃｋｗ ａｒ ｄＲ ｅ ｃｏｖ ｅｒｙ ） 技术［ １ ９ ］． 文献［ ２ ０ ］ 中提出了一种分布式曰志恢复系统的数据恢复方法． 三阶段提交协议比两阶段提交协议能更好地实现分布式事务执行的无阻塞， 在分布式数据库发生故障时可以有效地恢复分布式数据库中的数据， 保证了分布式日志恢复系统的高可用性和高可靠性． 文献［２ １ ］ 中研究了分布式系统下基于检査点的容错服务， 利用系统失效关联性特征来建立模型， 得到减小分布式任务的完成时间的检查点放置策略， 从而在保证系统可靠性的前提下， 降低容错服务的实现代价， 提高分布式系统的运行效率． Ｄｕ ｄｏ ｌ ａ ｄｏｖ 等人在文献［２ ２］ 中提出了一种使用算法补救的容错机制， 该机制利用了数据挖掘和机器学习中使用大量虚拟算法的鲁棒性、自校正性， 这些算法从各种中间一致状态收敛到正确的解． 该函数在算法上创建这样的一致状态， 而不是回滚到先前的检査点状态． 该优化机制不会检查任何状态， 并且在保证容错所需的开销方面具有最佳的无故障性能．在过去几年中， 出现了许多优化的迭代计算系统．像Ｔ ｗｉ ｓ ｔ ｅ ｒ［２ ３］ 或Ｈ ａＬｏｏｐ［２ ４］ 这样的Ｍ ａ ｐＲ ｅｄ ｕｃ ｅ［ １ ３］扩展， 以及像Ｓｐ ａ ｒ ｋ 这样的系统能够有效地执行某类迭代算法， Ｆ ｌｉｎ ｋ 系统在全量迭代的基础上， 新增了增量迭代功能． 增量迭代是通过部分计算取代全量计算， 在计算过程中会将数据分为热点数据和非热点数据， 每次迭代计算会针对热点数据展开， 这种模式适合用于数据量比较大的计算场景， 不需要对全部的输人数据集进行计算， 所以在性能和速度上都会有很大的提升． 而这些分布式计算系统的容错机制大多以悲观的方式实现， 且面向的通用的计算任务． 对于迭代任务而言， 容错开销大， 计算效率低．缺乏了对乐观容错机制的设计， 且采用的悲观容错机制多数以阻塞的方式实现． 没有结合迭代数据流的特点， 引人了不必要的额外开销． 此外， 现有的分布式系统的检查点机制基于阻塞的方式来实现， 即通过阻塞下游操作符等待完整数据的到来． 以阻塞方式实现检查点产生了较大的时间开销． 针对这些问题， 本文提出了面向大规模迭代计算处理的高效容错技术． 由于Ｆ ｌ ｉ ｎ ｋ 作为高效的开源批处理器， 在批处理和流处理的计算效率上均优于Ｈ ａ ｄｏｏｐ 、Ｓｔ ｏｒｍ 和Ｓｐａ ｒｋ ［２ ３］． 本文基于Ｆ ｌ ｉ ｎｋ 系统实现了基于补偿函数的乐观容错机制和基于头尾检查点的悲观容错机制， 并在大量数据集上从全量迭代和增量迭代方面进行了实验研究与分析．３ 基本概念本节给出文中涉及到的一些基本概念并对要解决的问题给出形式化描述．定义１ （ 步函数） ． 在迭代计算中， 对每一轮迭代输入的数据集进行转换操作的函数称为步函数（ Ｓｔ ｅ ｐＦｕ ｎｃ ｔ ｉｏ ｎ） ．例如， Ｐ ａｇ ｅＲ ａｎ ｋ 全量迭代算法在执行时， 每一轮迭代都要对顶点的ｒ ａ ｎ ｋ 值进行更新． 更新ｒ ａ ｎｋ值的操作有Ｊｏ ｉｉｕ Ｆ ｉ ｌ ｔｅ ｒ 等操作符， 这些操作符构成的数据流图即为该算法的步函数．定义２ （ 超级步） ． 在迭代计算中， 从迭代输人开始， 经过步函数的转换， 到更新为下一轮迭代输入的整个流程称为超级步．如图１ 为Ｆ ｌ ｉ ｎｋ 官方文档展示的迭代超级步的粒度即同步的粒度． 步函数是超级步的组成部分， 从第一个超级步迭代输人开始， 经过步函数的转换并郭文鹏等： 面向Ｆｌ ｉｎ ｋ 迭１ １ 期 代计算的 高效容错处理技术 ２ １ ０ ５更新为第二个超级步的输入． 该流程即为一个超级步．１ ｓｔ Ｓｕｐ ｅｒ Ｓｔ ｅｐ２ｎ ｄ Ｓｕ ｐ ｅｒ Ｓｔｅｐ３ ｒｄ Ｓｕｐ ｅｒ Ｓｔ ｅｐ？Ｓｔｅｐ Ｆｕ ｎ ｃｔｉ ｏ ｎ；Ｓｔｅｐ Ｆｕ ｎｃｔ ｉ ｏ ｎ ｉＳｔｅｐ Ｆｕ ｎｃｔｉｏ ｎ图３ 全量迭代计算示意图Ｂａｒｒｉｅｒ Ｓｙ ｎｃｈ ｒ ｏｎ ｉｚａｔｉ ｏｎ图ｉ 迭代超级步示意图定义３ （ 乐观容错机制） ． 在分布式系统环境下， 如果某个计算节点出现故障， 则采取相应的容错机制来把系统恢复到无错误状态． 乐观容错机制采用乐观的态度， 即假定所有的故障及其恢复策略都事先已知． 当系统发现错误后， 试图把系统带入一个新状态． 该机制要求系统事先掌握可能出现的故障．例如， 本文提出的乐观补偿恢复机制， 在迭代任务执行之前， 需要对分布式系统可能出现故障丢失数据的情况进行采取补偿恢复措施． 如果任务没有出现故障， 则顺利完成执行． 如果出现故障则采用预先定义的补偿措施对故障进行恢复， 使用恢复后的数据继续迭代的执行．定义４ （ 悲观容错机制）． 悲观容错机制与定义３ 的乐观容错机制相反， 该机制采用的是悲观的思想， 假定故障的产生是未知的， 在系统执行任务的过程中定期保存一些结果和历史记录信息．一旦发生故障， 则可恢复到最新记录的状态．例如， Ｆ ｌｉ ｎｋ 系统采用的分布式快照机制就是一种悲观的容错机制， 如图２ 所示， 以固定的时间间隔将ｂ ａ ｒ ｒ ｉ ｅ ｒ 注人数据流， 进行Ｃｈ ｅ ｃｋ ｐ ｏ ｉ ｎｔ 备份． 当出现故障时， 恢复到最近的Ｃ ｈｅ ｃｋ ｐｏ ｉｎ ｔ 时的状态．ｄａ ｔａ ｓ ｔｒｅａｍ＿ ｎ ｅｚｕ ｒ ｅｃ ｏ ｒｄｓｏｌｄ ｅｒ ｒｅｃｏｒｄｓ —＾ｃｈ ｅｃｋｐ ｏｉ ｎ ｔｃ ｈ ｅｃｋｐｏ ｉ ｎ ｔｓｔｒ ｅａｍｒｅｃｏｒ ｄｂａ ｒｒｉ ｅｒ ｎｂ ａｒ ｒｉ ｅｒ ｔ ｉ—１｛ ｅｖｅｎｔ）１， 输出迭代ｉ 〇次后的结果． 在迭代过程中， 每一轮迭代都要对所有的数据进行加１ 操作． 这种对全量数据进行转换的迭代过程即为全量迭代．定义６ （ 增量迭代） ． 增量迭代计算过程如图４所示， 通过部分计算取代全量计算， 在计算过程中会将数据集分为热点数据和非热点数据， 每次迭代计算会针对热点数据展开， 不需要对全部的输人数据集进行计算．图４ 增量迭代计算示意图例如， 图论中的连通分支算法， 该算法用于求解图的连通性问题． 迭代过程为： 首先， 初始化每个顶点所属的分类值（ 即所属的连通分量组）， 每个顶点初始值等于该顶点值的Ｉｄ ． 其次， 每个顶点搜索其相邻的顶点， 如果顶点的分类值小于该顶点的分类值， 则更新该顶点的分类值， 并在连通图中传播． 最后， 当没有顶点需要更新时， 所有连通图包含的顶点具有相同的分类值， 算法结束． 这种只需对部分数据进行转换的操作即为增量迭代．４ 基于补偿函数的乐观容错机制ｐ ａｒ ｔ ｏ ｆｐａ ｒｔ ｏ ｆｐａ ｒｔ ｏｆｃｈ ｅｃｋ ｐ ｏｉ ｎ ｔ ｎ ＋ １ｃｈｅｃｋｐｏ ｉ ｎ ｔ ｎｃ ｈ ｅｃｋ ｐｏ ｉ ｎ ｔｎ — １图２Ｆｌｉ ｎ ｋ 系统分布式快照示意图定义ｓ （ 全量迭代） ． 全量迭代计算过程如图３所示． 在数据流接人迭代算子的过程中， 步函数每次都会处理全量的数据， 然后计算下一次迭代的输入，即图中的Ｎ ｅ ｘ ｔＰ ａ ｒ ｔｉ ａ ｌ Ｓ ｏｌ ｕ ｔ ｉ ｏ ｎ ， 最后根据触发条件输出迭代计算的结果．例如， 给定一组数据， 迭代步函数为迭代数据加本节针对现有分布式计算系统悲观容错的迭代容错机制额外开销大， 需要额外的组件控制检查点协同者， 实现复杂等特点． 提出了一种面向迭代任务的乐观补偿函数容错机制． 该容错机制在迭代执行过程中， 不会引人任何额外的开销． 如果出现故障，则采用用户自定义的补偿函数收集健康节点上的数据， 并结合初始迭代数据对丢失的分区数据进行恢复． 现有的分布式系统未引人乐观恢复机制的原因之一在于， 补偿函数完全由用户编写， 实现难度大．２ １ ０ ６ 计算机学报 ２ ０２ ０年本节的乐观补偿函数机制在实现时为用户提供了收集数据和恢复数据的接口， 可供用户直接使用． 该机制保证了迭代任务高效顺利的执行， 得到的结果可以收敛到无故障执行时的近似状态．本节首先分析了分布式迭代的收敛性， 证明了补偿函数的乐观容错机制的正确性． 然后从全量迭代和增量迭代的角度实现了补偿函数容错机制．４． １ 分布式迭代计算的收敛性在计算机科学中， 迭代是对一段程序的反复执行． 迭代可以表示一种状态， 该状态以可变重复的形式存在． 迭代计算是数学领域中的常见的计算方式，常见的应用有矩阵求解特征值问题以及方程组求解等问题． 迭代的求解思路是不断趋近， 选择一个粗略的初始值， 采用迭代公式不断地更新该值， 如果该值满足收敛条件即精度满足或者迭代次数满足则终止． 否则， 将继续更新和计算该值． 大数据系统的分ｎ ｏｄ ｅ ｌｎ ｏｄ ｅ ２ｎｏｄｅ ３ｎｏｄ ｅ４图５Ｆｌｉ ｎｋ 系统中的分布式迭代数据流其中， 分布式迭代计算可以表示为ｘ＊ ＝／（ 工以－１ ）） ， 々＝１ ， ２ ，…， ”（ １ ）其中变量ｉ 表示的迭代过程中不断更新计算的数值， 即迭代变量． 公式左边的Ｖ 表示迭代计算到第办次时的值， 公式右边／ 是第々次迭代结果计算的通用表达式， 即迭代函数． 分布式迭代算法执行过程中， 每一轮迭代所需的数据可以表示为Ｐ ， 记为迭代变量． 可以使用向量／Ｔ＝（ ｘ Ｐ ， ｘ ｆ ，…， ：＾） 来表示迭代变量， 其中每个ｘ ｆ 都是一个迭代元素． ／为ＪＴ 的映射， ／ 是需要反复执行的一系列操作集合（ ／， ， ／２ ，…， ／，，） ， 每个／， 函数只负责计算向量Ｐ 的第／ 个元素， 因此式（ １ ） 等价于方程组（ ２ ） 的形式：＝／，（ ：＾卜１ ）， ｘ广ｄ，…， 工广＂） ，ｉ ＝ １ ， ２ ，…， ｎ（ ２ ）分布式迭代计算的初始向量可以表示为ｕｒ ， ：＾ ，…， ：＾ ） ， 利用式（ ２ ） 可逐次计算迭代向量文⑴＝（ ｘ ｊ＊ ＞， 工ｐ ，…， 工， ） ， 是＝１ ， ２ ，…， ” ？ 若向量序列Ｗ ｝ 无限趋近于向量；ｒ ＝（ｘｒ，…，〇， 即， ＝ ／ （ ， ） ． 则向量为迭代计算的解． 在某些特殊形况下求得最佳， 并非容易， 可能需要大量的迭代过程． 但根据迭代求解的特点可知， 满足迭代算法精度的近似值ｙ 可以充当算法的解．迭代计算的构建比较简单， 但许多迭代模型的计算过程都并非趋近于特定解． 也即不会收敛． 现实生活中只有收敛的迭代模型对用户有真实的意义，故迭代的收敛标准和条件对于迭代计算而言， 尤为关键．为了便于理解， 可以将式（ ２ ） 转化为ｊｃｕ ， ＝ Ｍｘａ ￣ｎ＋ ｐ ．ｋ ＝ ｌ ， ２ ，－， ｗ（ ３ ）其中Ｍ 称为迭代矩阵，／｝ 为一向量． 当式（ ３ ） 收敛时， 则有：ｊｃ＊ ＝ Ｍｘ＋ ｐ（ ４ ）记误差向量那么ｊｃ？当且仅当＃ — ０ ． 由式（ ３ ） 和（ ４ ） 可得误差向量的递推公式：ｅ＊＝ Ｍｅ＇ ＊ — ＂， 々＝ １ ， ２ ，…， ｗ（ ５ ）对式（ ５ ） 递推得到：ｙ ＝ Ｍｅ？丨＞， ６ ＝ １ ， ２ ，…， ？（ ６ ）因此， 当时， Ｖ —０ 的充分必要条件是： ０ ．推论１． 迭代计算是否逼近某个值与迭代构成的矩阵Ｍ 相关， 即迭代是否收敛与迭代计算的函数密不可分． 因此， 迭代计算过程具有很好的健壮性，在迭代循环的迭代过程中迭代变量产生一些误差，模型的最终收敛也不受影响． 现实迭代算法中的迭代矩阵ｉＷ 通常由概率组成， 因此可以得到在海量数据的迭代处理过程中， ￥— ０ ．由上述迭代计算的收敛性分析可知， 基于补偿函数的乐观的容错机制具有一致性的收敛状态． 乐观容错恢复的原理图如图６ 所示． 在第二次迭代过程中ｎ ｏｄ ｅ ３ 上发生故障， 通过补偿函数对健康节点ｎ ｏ ｄｅ ｌ 和ｎ 〇ｄ ｅ２ 上的数据进行收集， 并结合初始的ｎ ｏｄ ｅ ｌｎ ｏ ｄｅ ２ｎ ｏｄ ｅ３ ｎ ｏｄ ｅ４图６ 乐观容错恢复原理图郭文鹏等： 面向Ｆ ｌｉ ｎ ｋ 迭１ １ 期 代计算 的高效容错处理技 术 ２ １ ０ ７完整数据对丢失的数据进行补偿恢复得到新的迭代数据， 继续执行迭代计算． 迭代计算的收敛性特点确保了结果总是朝着正确的方向无限逼近， 乐观容错机制使用该特点， 在发生故障时， 通过补偿丢失数据的近似值作为新的变量继续迭代， 保证了大规模分布式迭代计算结果的正确性．４． ２ 基于乐观容错机制的全量迭代算法本节主要基于分布式全量迭代算法实现基于补偿函数的乐观容错机制， 以典型的Ｐ ａ ｇｅ Ｒａ ｎ ｋ 算法为例， Ｐａ ｇ ｅＲａ ｎ ｋ 算法的介绍详见文献［２ － ３］ ． 本节进一步基于Ｍ ｉ ｎｋ 系统设计和实现了具有乐观容错机制的Ｐ ａｇ ｅＲ ａ ｎｋ 算法．本节以图７ 所示的网页链接为例， 介绍基于补偿函数乐观容错机制的Ｐ ａ ｇｅ Ｒａ ｎ ｋ 算法的设计与实现． 当前网络中共有Ａ ， Ｂ ， Ｃ ， Ｄ ， ￡， Ｆ 共５ 个网页，使用有向图Ｇ ＝（ Ｖ ， ￡） 表示该网络． 若网页Ａ 包含一个到Ｂ 网页的链接， 则会有一条边（ Ａ ， Ｂ ） ． 网页中顶点集合＾ ＝｛八， ５ ， （：， ０ ， ￡：｝ ， 网页中边集合￡：＝｛ （ Ａ ， Ｂ ） ， （Ａ ， Ｃ） ， （ Ａ ， Ｄ ） ， （ Ａ ， Ｅ ） ， （ Ｂ ， Ａ ） ， （ Ｂ， Ｄ ） ，（ Ｂ ， Ｆ ） ， （ Ｃ ， Ａ ） ， （ Ｃ ， Ｆ ） Ａ Ｄ ， Ｂ ） Ａ Ｄ ， Ｃ ） Ａ Ｄ ， Ｅ ） ，（ Ｄ ， Ｆ ） ， （ ￡， Ｃ ） ， （ Ｆ ， Ｅ ）｝ ．图７ 网页链接示例图如果一个网页有ｘ 个链出网页， 则该从网页跳转这： Ｔ 个网页的概率都为１ ／ Ｘ ， 该网页贡献给其跳转网页心吨／ ｘ，． 例如网页Ａ 包含４ 个跳转链接，则从Ａ 网页跳转到网页Ｂ、Ｃ、Ｄ、￡的概率为均为１ ／ ４ ， 由此可以推出一个网络内网页互相跳转的概率矩阵表示从网页ｆ 跳转到网页ｊ 的概率．ｆｌ ／ ｘｉ，（．ｊ ， ｉ ） ６ＥＭｕ ｊ＝（ ７ ）ｌ Ｏ ，〇， ０￥Ｅ使用概率矩阵Ｍ 表示图７ 中网络中各网页之间的跳转概率可以表示为Ｍ＝０ １ ／ ３ １ ／ ２ ０ ０ ０１ ／ ４ ０ ０ １ ／４ ０ ０１ ／４ ０ ０ １ ／ ４ １ ０１ ／ ４ １ ／ ３ ０ ０ ０ ０１ ／ ４ ０ ０ １ ／ ４ ０ １０ １ ／ ３ １ ／ ２ １ ／ ４ ０ ０ ，由于网络中可能会出现这样一些网页， 它们除了本身之外没有其它的出链， 或者几个网页构成的循环圈， 这样会导致这个或这些网页的Ｒａ ｎ ｋ 值只增不减， 为了规避这种情况， Ｐａ ｇ ｅＲ ａ ｎｋ 算法引人了一个阻尼因子ａ ， 假定用户会有ａ 的概率通过网页之间的链接去访问网络中的其它网页， 有（ １一ａ ） 的概率通过直接输人浏览器地址访问． Ｐ ａｇ ｅ Ｒａ ｎｋ 值的计算公式为叫）＝ １＾ ＋ ？ ２ 微（ ８ ）其中Ｐｉ？ （ ／＞，） 表示网页Ｚ＇的Ｒａ ｎ ｋ 值， Ｌ（ 九） 表示网页＿ ；＿的链出网页数． 在实际应用中， 阻尼因子ａ — 般取为０ ． ８ ５． 而在多次迭代过程中一般很难达到精确结果， 所以一般取两轮迭代的无穷范数作为收敛精度， 当相邻两轮迭代变量Ｒａ ｎ ｋ 之间的绝对值之差小于给定的阈值或满足最大迭代次数时， 迭代终止．记每第ｉ 轮迭代的Ｒａ ｎ ｋ 值为记＇ 以图７ 网络拓扑为例， 每个网页初始的Ｒａ ｎ ｋ 值可以表示为１ ？（ ０ ＞＝｛ １ ／ ６ ， １ ／６ ， １／ ６ ， １ ／ ６ ， １ ／ ６ ， １ ／６ ｝Ｔ， 经历１ ０次迭代网页Ｒａ ｎ ｋ 值变化如图８ 所示．ｒ Ｏ． １ ６ ６ ６ ６ ７＇］ 〔０ ． １ ４ ３ ０ ５ ６］ｒ Ｏ ． １ ５ ３ ０ ９ ０ ＇ｊ０ ．１ ６ ６ ６ ６ ７ ０． ０ ９ ５ ８ ３ ３ ０ ． ０ ７ ８ ２ ７ ３０ ．１ ６ ６ ６６ ７＞ ＝＞ ＜０． ２ ３ ７ ５０ ０ ０ ？ １ ５ ９ ７ ３ １０ ．１ ６ ６ ６６ ７ ０ ． １ ０ ７ ６ ３ ９ ０ ． ２ ８ ２ ５ ５ ２０ ． １ ６６ ６ ６ ７ ０ ． ０ ９５ ８ ３３ ０ ． ２ ２ ９ ９ ７ ４０ ． １ ６６ ６ ６ ７ ． ． ０ ． １ ７８ ４ ７ ２ ． ． ０ ． １ ７ ５ ９ ６ ４ ．（ ０ ） （ １ ） （ ２ ）ｒ ０ ． １ １ ５ ０ ６ ３＇ｊｒ Ｏ ． １ ６ １ ２ ５ ６＾ｒ Ｏ ． １ ５ ３ １ ７ ８ ＇｜０ ． ０ ７５ ０ ７ ４ ０ ． ０ ６ ６ ３ ８ ９ ０ ． ０ ７ ４ ２ ９ ５０ ．２ ７０ ５ ５ ２＞＝＞ ＜０ ． ２ ５ ７ ３ ３ ６ ０ ． ２ ２ ６ ５ ３ ３０ ．０ ７ ９７０ ９ ０ ． ０ ７０７ ２ ２ ０ ． ０ ７ ８ ０ ７ ７０ ． ２ ２４ ６４ ３ ０ ． １ ７ ９ １ ０ ３ ０ ？ ２ ２ ５７ ６ ０． ０ ． １ ３ ２ ６０ ５ ， ． ０ ． １ ７８ １ ９４ ．． ０ ． １ ６ ８ ２ ０ ６＞（ ３ ） （ ４ ） （ ５ ）（０ ． １ ４ ２ ３２ ７］ｒ Ｏ． １ ５ ９ ０ ７ ３ ｒ Ｏ ． １ ５ ４ ３ ９ ６＇ｊ０ ．０ ７４ １ ４ ２ ０． ０ ７ １ ９４ ７ ０ ． ０ ７ ５ ０ ０ ６０ ． ２ ６ ６０ ３ ７＞ ＝＞ ＜０ ． ２ ５ ６４ ９ ６ ０ ． ２ ５ ０９ ８ ００ ． ０ ７８ ６０ １ ０． ０ ７ ６ ２ ５ １ ０ ． ０ ７ ９ １ ８ ８０ ． ２ １ ７ １ １ ７ ０． ２０ ７ ０ ２８ ０ ． ２ ２ ４ ４ １ ５－ ０ ． １ ５８ ９ １ ８ ． ． ０． １ ７ ５ ７ ７ ５ ． ． ０ ． １ ７ ０ ５ ９ ９ ．〔０ ？ １ ５ ２ ９ １ ８〕（ ７ ）ｒ Ｏ ． １ ５ ８ ９ ３ ８＇）０ ． ０ ７ ４ ６ ３ ７ ０ ． ０ ７ ４ ２ ９ ６０ ． ２ ６ ５ ３ ９ ０ ０ ． ２ ６ ０ ９ ９ ５０ ． ０ ７ ９ ０ ６ １ ０ ． ０ ７ ８ ６ ４ ２０ ． ２ １ ９ ６ ４ ６ ０． ２ １ ８ ５ ７ ９． ０ ． １ ６ ９ ７ ４ ６ － ， ０ ． １ ７ ５ ７ ３ ８ ．（ ９ ） （ １ ０ ）图８Ｐ ａｇ ｅ Ｒａ ｎ ｋ 迭代Ｒａ ｎ ｋ 值变化图由图８ 可得， 在第１ ０ 次迭代后， Ｒａ ｎ ｋ 值变为＜ ０ ．１ ５ ８ ９３ ８ ， ０ ． ０ ７ ４２ ９ ６ ， ０ ．２ ６ ０ ９ ９５ ， ０ ． ０ ７８ ６ ４ ２ ， ０ ． ２ １ ８５ ７ ９ ，２ １ ０ ８ 计算机学报 ２ ０ ２ ０年０ ．１ ７ ５ ７ ３ ８ ｝Ｔ． 经计算可得， 在第１ ６ 次迭代时， 其Ｒａ ｎ ｋ值的收敛精度达到了１ 〇＿ ３， Ｒａｎ ｋ 值收敛为｛ ０ ． １ ６０ ３ ２ ９ ，０ ． ０ ７ ５９ ５ ８， ０ ． ２ ６ ７ ５０ ９ ， ０ ． ０ ８ ０３ ８ ６ ， ０ ． ２２ ６ ０５ ６ ， ０ ．１ ７ ７ ３ ８ ７｝Ｔ．假设在某次迭代过程中， 导致分区数据丢失， 可以设计补偿函数统计当前丢失的数据Ｒａ ｎ ｋ 值个数为《以及丢失的总概率为为丢失的网页补偿一个相同的Ｒａ ｎ ｋ 值／？ ／ ？ ， 然后和未丢失的数据一起继续执行迭代任务．以图７ 中的网络拓扑为例， 假设在第４ 迭代， 集群中的计算节点ｎ ｏｄｅ ｌ 发生故障， 并且ｎｏ ｄｅ ｌ 上保存的是顶点Ｓ 和Ｃ 的数据． 在发生故障后， 对丢失的数据进行补偿恢复， 得到新一轮迭代的输入． 迭代过程中网页的Ｒａ ｎ ｋ 值变化如图９ 所示．ｒ０ ． １ ６ ６ ６ ６ ７＇０ ． １ ４ ３ ０ ５ ６ ０ ． １ ５ ３ ０ ９ ０＇０ ． １ ６ ６ ６ ６ ７ ０ ． ０ ９ ５ ８ ３ ３ ０． ０ ７ ８ ２ ７ ３０ ． １ ６ ６ ６ ６ ７ ０ ． ２ ３ ７ ５ ０ ０ ０－ １ ５ ９ ７３ １０ ． １ ６ ６ ６ ６ ７＞—＾＊０． １ ０ ７ ６ ３ ９＞＝ ＞０． ２ ８ ２ ５ ５ ２０ ． １ ６ ６ ６ ６ ７ ０ ．０ ９ ５ ８ ３ ３ ０． ２ ２ ９ ９ ７ ４．０． １ ６ ６ ６ ６ ７ ． ，０ ． １ ７ ８ ４ ７ ２ ， ，０． １ ７ ５ ９ ６ ４，（ ０ ） （ １ ） （ ２ ）＾０ ． １ １ ５ ０ ６ ３＇０ ． １ ６ １ ２ ５ ６ ０ ．１ ６ １ ２ ５ ６＇０ ． ０ ７ ５ ０ ７ ４ ０．０ ６ ６ ３ ８ ９ ０ ． ０ ６ ６ ３ ８ ９０ ． ２ ７０ ５ ５ ２０ ． ０ ７ ９７ ０ ９＞ ■＝＞＊ ＞＝ ＞＾０ ．１ ６ ４ ０ ２ ９０ ． １ ６ ４ ０ ２ ９０ ． ２ ２ ４ ６ ４ ３ ０ ． １ ７ ９ １ ０ ３ ０ ．１ ７ ９ １ ０ ３． ０ ． １ ３ ２ ６ ０ ５．．０ ． １ ７ ８ １ ９ ４， ．０ ．１ ７ ８ １ ９ ４」（ ３ ） （ ４ ） （ ４，）＇０ ． １ １ ３ ５ ２ ３ ０ ． １ ５ ６ ３ ７ １＇０ ．１ ６ ０ ２ ６ ７＇０ ． ０ ９ ４ １ ２ ３ ０ ． ０ ６ ５ ７１ ５ ０ ． ０ ７ ４ ３ ３ ５０ ． ２ ４ ６ ３ ６ １ ０ ． ２ ７ ４ ４ ６ ５ ０ ． ２ ３ ７ ３ ９ ６０ ． ０ ７ ８ ０ ７ ７＞＝＞？ ＜０ ． ０ ７ ５ ７ ９ ２＞－ ＜０ ． ０ ７ ６ ８ ４ ８０ ． ２ ４ ５ ５ ８ ８ ０ ． １ ９ １ ８ ３ ７ ０ ． ２ ２ １ ３ ５ ３． ０ ． １ ４ ８ ３ ７ ９ ． ． ０ ． １ ７ ２ ９ ６ ３ ， ． ０ ．１ ７ ６ ３ ７ ２ ．（ ５ ） （ ６ ） （ ７ ）？０ ． １ ４ ６ ９ ５ ５＇０ ． １ ５ ８ ３ ６ ３ Ｕ１ ５ ８ ２ ７ ８，０．０ ７ ５ ３ ８ ７ ０ ． ０ ７ ３ ２ ５ ３ ０． ０ ７ ５ １ ３ ９０ ＿ ２６ ３ ５ ３ ７ ０ ． ２ ６ ４ ７ ６ １ ０ ． ２ ５ ５ ３ ７ ８０ ． ０ ８ ０ １ １ ８ ０ ． ０ ７ ７ ５ ８ ８＞？ ＜０ ． ０ ７ ９ ４ ０ ７０ ． ２ ２ ５ ３ ０ ４ ０ ． ２ １ ２ ０ ４ ５ ０ ． ２ ２ ４ ２ １ ９． ０ ． １ ６３ ２ ８ ５ ． ． ０ ． １ ７ ５ ３ ８ ８， ． ０ ．１ ７ ４ ７ ６ ６ ，（ ８ ） （ ９ ） （ １ ０ ）图９Ｐａｇｅ Ｒａｎ ｋ 补偿后Ｒ ａ ｎｋ 值变化图由图９ 可以看出第４ 次迭代， 节点ｎ ｏｄ ｅ ｌ 出现故障后对节点Ｂ 、Ｃ 的Ｒａ ｎ ｋ 值补偿为０ ． １ ６ ４０ ２ ９ ， 再次经过６ 次迭代后得到的Ｒａ ｎ ｋ 值与图８ 的正确Ｒａ ｎ ｋ 值比较接近， 且在补偿后迭代执行在第１ ４ 次时， 其Ｒａ ｎ ｋ 值收敛精度达到１ （Ｔ ３， Ｒａ ｎ ｋ 值收敛为｛ ０． １ ６ ０ ８ ３７ ， ０ ． ０ ７ ６１ ４４ ， ０ ． ２ ６８ ７ ４９ ， ０ ． ０８ ０ ５ ８９ ， ０． ２ ２ ６ ７８ ５ ，０ ？ １ ７ ７ ９ ５ ６ ｝丁．采用本文提出的乐观补偿函数对丢失的网页恢复并继续迭代得到的网页排名与无故障迭代计算得到的结果一致． Ｐａ ｇｅ Ｒａ ｎｋ 算法对应的补偿函数具体执行过程如算法１ 所示．算法１ ．Ｐａ ｇ ｅＲ ａ ｎｋ 全量迭代算法补偿函数．输人： 顶点集合Ｖ ， 当前迭代变量输出： 对故障节点丢失数据补偿后的新迭代变量１．Ｓｕ ｍＲａｎｋ—ｓ ｕｎＫ ｉ＾ ｎ） ／ ／统计健康节点 Ｒａｎ ｋ值２．Ｌ ｏｓ ｔ Ｎ ｕ ｍ—ｃ ｏｕ ｎｔ Ｃ ＶＯ— ｃ ｏｕ ｎｔ Ｃ ｉ？１ ＊ １） ／ ／计算丢失的顶点数量３．Ｃ ｏｍｐ ｅｎ ｓａ ｔ ｉ ｏｎ Ｒａ ｎ ｋ ＜－（ １ —Ｓｕ ｍＲ ａｎ ｋ ） ／ Ｌｏ ｓｔ Ｎｕ ｍ４ ．／ ／对丢失顶点的Ｒａ ｎ ｋ 值进行补偿５ ．Ｆ ＯＲｅ ａ ｃ ｈ 认ｉ ｎＶ ７／ 遍历节点上的顶点６．如果未丢失７ ．ａ ｄ ｄ广ｔ ｏ ｉｄ ／ ／直接加人到８ ．ｅ ｌ ｓｅ ／ ／ 如果丢失９．ａ ｄ ｄＣ ｏ ｍｐｅ ｎ ｓ ａ ｔ ｉ ｏ ｎＲ ａｎｋｔ ｏ１ ０ ． ／ ／ 将丢失补偿后的Ｒ ａｎｋ 加入到Ｊ ？ ：二４． ３ 基于乐观容错机制的増量迭代算法本节主要基于分布式增量迭代算法实现基于补偿函数的乐观迭代容错机制， 使用典型的Ｃｏ ｎｎ ｅｃ ｔｅ ｄ－Ｃｏｍｐｏ ｎｅ ｎｔ ｓ增量迭代算法为例展开介绍． Ｃｏｎ ｎ ｅｃ ｔ ｅｄ －Ｃｏｍ ｐｏｎ ｅ ｎｔ ｓ 算法第３部分已经介绍；本节进一步基于Ｆｌｉ ｎ ｋ 系统实现了基于乐观容错机制的Ｃｏｎｎ ｅ ｃ ｔｅ ｄ－Ｃｏｍ ｐｏ ｎｅｎ ｔ ｓ 算法？本节以图１ ０ 所示的连通图为例， 以具体实例介绍了基于乐观容错机制的Ｃｏ ｎｎ ｅ ｃｔ ｅｄ Ｃｏｍｐ ｏｎ ｅ ｎｔ ｓ算法的设计与实现．图１ ０Ｃ ｏｎ ｎｅ ｃ ｔ ｅｄ Ｃｏ ｍｐ ｏｎ ｅｎｔ ｓ算法示例图假设当前共有Ｉ ｄ 为１ ？ １ ５ 的１ ５ 个顶点组成的图． 如图７ 所示为顶点之间的连通关系． 记顶点的分类值为Ｃｌ ｄ ， 初始时所有顶点的Ｃｉ ｄ ＝ Ｉ Ｄ．使用Ｃｏ ｎｎ ｅ ｃｔ ｅ ｄＣｏｍｐ ｏ ｎｅ ｎ ｔｓ 算法对图１ ０ 中的顶点数据进行迭代， 则每个顶点在迭代过程中对应的Ｃｉ ｄ 值变化如图１ １ 所示． 在经历第５ 次迭代后，每个顶点的Ｃｉ ｄ 值不再更新， 迭代结束． Ｃｏｎ ｎｅ ｃ ｔ ｅｄ－Ｃｏｍｐ ｏ ｎ ｅｎ ｔ ｓ算法属于增量迭代， 当某个顶点在本轮迭代过程中， 其Ｃｉ ｄ 值没有发生变化， 代表该顶点的Ｃｉｄ 值已经是其所在的连通子图中所有顶点中的最小Ｉ ｄ 值． 故在下次迭代时可以忽略该顶点． 在迭代过程中， 若集群中某节点生故障而导致部分数据郭文鹏等： 面向Ｆ ｌ ｉ ｎ ｋ 迭１ １ 期 代计算 的 高效容错处理技 术 ２ １ ０９丢失时， 使用补偿函数将丢失的顶点补偿顶点的初始值， 该节点周围的节点可能已收敛到最终的结果．故对于丢失的节点只需要经历较少的收敛次数即可再次得到最终收敛的结果．图１ １Ｃ ｏ ｎｎ ｅ ｃ ｔ ｅｄ Ｃ ｏｍｐｏｎ ｅ ｎ ｔ ｓ迭代Ｃ ｉ ｄ值变化图以图１ １ 为例， 假如在第３ 次迭代时， 某台节点ｎｏ ｄ ｅ２ 发生故障， ｎｏｄ ｅ２ 上存放的顶点有３ ， ６ ， ９？ 在发生故障后， 对丢失的数据进行补偿恢复， 得到新一轮迭代的输人． 继续执行迭代的过程如图１ ２ 所示．经过补偿后的顶点同在第５ 次迭代收敛， 且结果一致．图１ ２Ｃ ｏ ｎｎ ｅ ｃ ｔ ｅｄ Ｃ ｏｍｐｏｎ ｅ ｎｔ ｓ 补偿后Ｃ ｉ ｄ 值变化图基于Ｃｏ ｎｎ ｅ ｃ ｔ ｅ ｄ Ｃ ｏｍｐ ｏ ｎ ｅ ｎｔ ｓ 的补偿函数的具体执行过程如算法２ 所示．算法２ ．Ｃ ｏ ｎ ｎｅ ｃ ｔ ｅ ｄＣｏ ｍｐｏ ｎｅ ｎ ｔ ｓ 增量迭代算法补偿函数．输人： 顶点集合Ｖ ， 当前迭代变量Ｃ Ｗ＜ ４ ＞输出： 对故障节点丢失数据补偿后的新迭代变量ｃｗ ＝１ ．Ｆ ＯＲ ｅａ ｃ ｈ Ｗ，ｉ ｎＶ／ ／遍历节点上的顶点２ ．ｉ ｆ ｔ；，ｉ ｎ ＣＷｕＶ ／如果未丢失３ ． ａ ｄ ｄＣＷ ：４ ＞ｔ ｏＣ Ｗ＝ ／／ 直接加人到４．ｅｌ ｓｅ／ ／如果未丢失５． ａ ｄ ｄｔ ｏＣ Ｗ＝ ／ ／ 直接加人到６．／ ／将丢失的顶点的Ｉ ｄ 作为补偿值， 并加人本文基于Ｆ ｌ ｉ ｎｋ 系统实现了全量迭代算法的乐观补偿容错机制， 现有的分布式系统没有新增乐观容错机制的原因之一在于补偿函数需要完全由用户定义和实现． 本文实现的乐观补偿函数容错机制为用户提供了补偿函数接口， 该接口中定义了抽象的收集数据方法并将初始数据集作为参数传人该方法， 便于用户直接使用． 执行过程中发生故障时， 主节点Ｊ ｏ ｂ Ｍａ ｎａ ｇｅ ｒ 会通过心跳信息监测到具体发生故障的Ｔ ａ ｓｋ Ｍａ ｎ ａ ｇｅ ｒ． 此时会判断用户是否编写了补偿函数， 如果有， 则会触发收集数据的操作， 在Ｅ ｘ ｅｃ ｕ ｔ ｉ ｏ ｎ Ｇ ｒａ ｐｈ 中向分配了任务的健康节点发出收集数据的消息． Ｔａ ｓｋ Ｍ ａ ｎ ａ ｇｅ ｒ 收到消息后， 会根据迭代任务的类型来收集数据， 如果是全量迭代则会在Ｉ ｔ ｅ ｒａ ｔ ｉ ｏ ｎ ｌ ｎ ｔ ｅ ｒ ｍｅ ｄ ｉ ａ ｔ ｅＴ ａ ｓｋ 中收集数据？ 如果是增量迭代， 则会在其Ｉ ｔ ｅ ｒ ａ ｔ ｉｏ ｎ Ｈ ｅ ａ ｄＴ ａ ｓｋ 中收集数据．数据收集完成后， 调用用户编写的补偿函数， 对丢失的数据进行恢复． 将恢复得到的数据作为新的迭代输人继续执行．５ 基于头尾检查点的悲观容错机制如前所述， 现有分布式计算系统迭代容错效率低， 采用的悲观检查点机制时以阻塞的方式写人外部存储？ 额外开销大， 没有针对迭代计算的特点制定特定的容错机制． 本节提出了一种基于头尾检查点的悲观容错机制， 该机制以一种不受阻塞的方式编写检查点， 将可变的数据集输人迭代数据流， 降低了检查点成本和故障恢复开销． 进一步基于Ｆ ｌｉ ｎ ｋ 系统实现了头尾检查点机制． 本节首先介绍了Ｆ ｌ ｉ ｎ ｋ系统中的迭代模型． 其次介绍并分析了阻塞检查点和非阻塞检查点的代价开销． 最后提出了尾部检查点和头部检查点机制并进行了代价开销分析．５ ． １Ｆ ｌ ｉ ｎｋ 系统中的迭代模型本节以Ｆ ｌ ｉ ｎｋ 系统迭代处理图算法为例． 介绍了Ｆ ｌｉ ｎｋ 系统的迭代模型． 对于顶点数据集，使用表示顶点Ｗ ， 表示顶点的迭代变量值． 对于边数据集使用表示源顶点，表示目标顶点． 表示边的权重（ 该值是可选的） ． 通常对于图迭代计算问题，一般表示为顶２ １ １ ０计算机学报２ ０ ２ ０ 年点为其它顶点生成消息， 并在每个超级步中接收消息更新其值． 使用关系运算符． 这类迭代计算表示为ｙ（ ｍ ）ｙ （ Ｖ＜ － ＞） ｍ Ｅ ）（ ９ ）其中， 是当前顶点的值， Ｅ 是边． 首先顶点为其他顶点产生消息， 即Ｍ Ｅ ． 然后， 顶点收集消息以及当前值Ｕ（ Ｗ ｌ ｘ ｆ：． 最后， 使用步函数／ 来更新顶点的值．图１ ３ 显示了数据流系统中图迭代的通用编程框架． 要在数据流系统中执行图算法， 输人数据常从外部存储（ Ｈ ＤＦ Ｓ ） 加载以构建狀数据集， 而数据集由用户指定的初始值根据应用程序构建． 迭代运算符用于将新生成的顶点集Ｖａｆ ｅ， 替换上一次迭代的顶点集这里将和Ｖｅ ＂ｅ ＿ｒ＇ 称为迭代数据集． 在ｊ ｏ ｉｎ 阶段期间， ￡＃ｅ 和Ｖｅ ｒｋ ｉ 数据集彼此连接以生成中间数据集， 即在顶点之间交换的信息． 这里连接运算符伴随用户自定义的函数以产生有效的值． 例如， 指定用户定义的连接函数， 使其与Ｆ ｌ ｉ ｎ ｋ 中的ｊ ｏ ｉ ｎ 运算符相关联， 而通过在Ｓ ｐａ ｒ ｋ 中的ｊｏｉ ｎ 之后应用ｍａ ｐ 函数来实现． 在ｇｒｏ ｕｐ Ｂ ｙ 阶段， 中间数据集由ｇｒ ｏ ｕ ｐＢ ｙ 运算符应用，该运算符按目标顶点对数据进行分组以构造每个顶点的邻域． 在聚合阶段， 用户定义的聚合函数应用于Ｖｅ ｄｅ ｘ 数据集和其邻居数据集的并集， 以便计算正在处理的顶点的新值． 但是ｕ ｎｉ ｏｎ 运算符是可选的，因为在某些应用程序中， 顶点的值仅依赖于它的邻居． 其中Ｊ ｏ ｉ ｎ 阶段对应了式（ １ ） 中的Ｖ＾ ； ＞Ｍ ￡， Ｇｒｏ ｕ ｐ阶段对应了Ｕ（ Ｖ（ ＂） Ｍ Ｅ ， Ａｇｇ ｒ ｅｇ ａ ｔ ｉ ｏ ｎ阶段对应了Ｕ （ Ｖ（； ＞） ｔｘ ｆ：） ．＜ｗ＞／Ｖｅｒｔｅｘ／＿ ／Ｖｅ ｒｔｅｘ＇／／Ｊｏ ｉ ｎ阶律Ｇ ｒ ｏ ｕｐＢｙ阶學＼Ａｇ ｇ ｒｅ ｇａ ｔｉｏ ｎ阶 段、＇（ Ｊｏ ｉｊ）－？／ 消息／ 邻居邻居＋／？＾ｒ ｅｇａ ｔｉｏｉｊｊ图１ ３ 图迭代处理通用编程框架通常， 迭代输人经过每个超级步的转换后， 得到的输出在迭代算法的执行过程期间作为下一个超级步的输人． 因此， 在下一轮迭代过程中， Ｖ〃＾ｒ＇ 数据集将替换原有的Ｖｅ ｒｔ ｅｘ ， 替换过程通过反向通道来完成． 其中， 系统的迭代数据流的执行过程如图１ ４ 所示．反向通道操作符？｛ 操作符｝迭代头迭代尾图１ ４ 迭代数据流５ ． ２阻塞检查点与非阻塞检查点在阻塞运算符模型［２ ６］ 中， 每个运算符在任何下游运算符开始使用结果之前生成其完整结果．该模型简化了检查点策略的实施， 并被Ｄｒ ｙ ａ ｃＰ＇Ｍａ ｈ ｏ ｍ 和Ｐ ｒｅ ｇ ｅｌ ｉ ｘ 等系统广泛采用． 遵循此原则，为了编写检查点， 在开始下一个超级步之前保存迭代数据集． 在迭代数据流中， 检查点可以通过反向通道写入， 如图１ ４ 所示． 我们假设该集群中所有的节点工作均匀， 并且工作负载在所有节点之间完美平衡． 然后， 阻塞检查点的开销Ｑ， 如下：Ｄ ＇〇ｉ， ＝—（ １ ０ ）ｎ ｖ其中Ｄ ＇是在超级步ｉ 结束之后且在超级步； ＋１ 之前的检查点的数据大小ｍ 是集群中节点的数量〇是每个节点使用的外部存储系统的写人速率．阻塞运算符模型极大简化了容错任务， 因为它可以防止下游任务消耗其上游输出的一部分数据而导致其余部分发生故障变得不可用的情况［ ２ ° ］． 但是此阻塞模型通常会增加执行延迟， 如例１ 所示． 这种高延迟的原因是只有当迭代数据集完全可用时才会与入检查点， 并且在完成检查点后， 后续的超级步才可以启动计算．例１ ． 假设图迭代处理算法在由１ 〇个节点上组成的集群上运行． 另外， 迭代数据集的数据量即检查点的大小为１ ０ Ｇ Ｂ ， 并且每个节点上的Ｈ ＤＦ Ｓ 的写人速率是５ ０ Ｍ Ｂ／ Ｓ． 根据式（ １ ２ ） 可知，在阻塞运算符模型中写入检查点的额外开销是２ ０ ． ４ ８ ｓ ． 如果一次迭代任务没有任何检查点的超级步的执行时间为２ ｍｉ ｎ ， 那么检查点额外开销所花费的占比为１ ４ ．６ ％ ．Ｆ ｌ ｉ ｎｋ 系统实现的检查点容错机制， 虽然不会以无阻塞的方式破坏迭代管道． 但它忽略了迭代控制，并使系统设计复杂化， 需要额外的组件来协调故障恢复的检查点， 特别是对于迭代图算法． 此外， 节点上的磁盘故障是本地实现策略的灾难， 因为故障磁盘上的数据将完全丢失， 并且后向重新计算可能是耗时的．郭文鹏等： 面向Ｆｌｉ ｎｋ 迭１ １ 期 代计 算的 高 效容错处理技术 ２ １ １ １５ ． ３ 尾部检查点与头部塞检查点本节提出的检查点机制， 通过在数据流执行过程中将检查点写人到外部存储， 与迭代无关的阻塞检查点不同， 该机制在数据流中， 可以感知迭代． 编写检查点将可变迭代数据集保存到外部存储是一项特俗任务， 该检查点的写入隐含地包含在流水线执行中． 它不仅在不破坏流水线任务的情况下继承了低延迟的优势， 而且只有在当前迭代中的检查点完成后， 迭代协调器才能启动下一次迭代， 此外，Ｈ Ｄ ＦＳ 等外部存储为容错提供了高可用和可靠性．对于尾部检查点， 如图１ ５ （ ａ ） 所示， 检查点的写人与数据集的生成同步进行， 在超级步的尾部写人外部存储． 即超级步尾部数据流速为因为是以流水线的方式生成的． 如果产生的流速大于写人外部存储器的最高速率Ｖ ，即ｗ＞ 切． 则可以在没有任何运行时间开销的情况下写人检查点． 否则， 数据被累积， 进程等待写人外部存储完全写入需要的开销为在此期ｎｖ ，Ｄ ＇７）间， 已写人的数据量为因此， 待写人的数据量ｎ ｖ ，为丄「Ｄ。。— 将剩余数据写人磁盘所ｎＬ」需的时间是额外的开销． 给定写人速率％ 尾部检查点的开销ＯＵ 为Ｏ ｕ ｂ ＝＼Ｄ ， ：、｛ ｖ ｔ—ｖ ）ｎｖｖ ，Ｖ ＜，Ｖｔ（ １ １ ）ｖ ＞ ｖ，例２ ？ 在例１ 的基础上， 如果用于生成Ｖｅ ｒｔ ｅｘ＇数据集的流水线速率是６ ０Ｍ Ｂ／ ｓ ． 则根据式（ １ １ ） 可以计算得， 尾部检查点的开销是３ ． ４ １ ｓ．对于头部检查点， 如图１ ５ （ ｂ ） 所示， 检查点的写入与Ｖｅ ｒｔｅｏ？ 数据集的完成同步进行． 由于Ｖｅ ｒ ｆ ｅｘ数据集由管道中的下游节点使用． 如果检查点的写人速率ｕ 大于超级步头部的流水线速率％ ． 即则可以在没有任何运行时开销的情况下完成检查点的写人． 如果＾＜ 叫， 则在消耗完整个Ｖｅ７＾：ｒ数据集之后还存在剩余数据， 剩余的数据量为Ｄ ＇， 写人该数据的开销为但是如果此时间小于超级步ｉ 的正常执行时间〖，， 即， 则仍然没有运行时开销， 因为将数ｎｖｖ ｈ据写人外部存储和下游操作符的处理是并行完成的． 否则， 迭代协调器需要等待写人外部存储才能完成， 以便继续执行下一个超级步． 在这种情况下， 时间导致运行时开销． 然而， 需要考虑头部检查点的干扰次ａ ＜ａ，） ， 这可能会延迟作业的运行时间， 因为它仍然占用计算或存储资源． 头部检查点的开销〇Ｌ 近似为ｎｖ ｖｈｎ ｖ ｖｈｌ〇， 其他（ １ ２ ）反向通道操作符Ｙ… 操作符下迭代头迭代尾（ ｂ ） 头部检查点图１ ５ 尾部检查点和头部检査点例３ 显示了头部检查点将检查点写人操作和每个超级步骤的图形计算并行化， 以便显着减少检查点的运行时开销．例３ ． 在例１ 的基础上， 如果使用Ｖｅ ｄａ 数据集的流水线流的速率是６ ０ ＭＢ ／ Ｓ ， 则根据等式（ １ ２ ） ，尾部检查点的开销是〇．根据前面对阻塞检查点和头尾检查点的代价分析， 我们可以推理出以下定理．定理１ ． 无阻塞检查点的开销不高于阻塞检查点的开销．证明． 分别对比尾部检查点和阻塞检查点， 头部检查点和阻塞检查点的开销． 尾部检查点与阻塞检查点开销对比： 如果” ＜ ％ ， 那么＾＾＜ １ ， 因此Ｖ ，（Ｘ，＝Ｄ：’二（ 巧―并且 〇，， 〉〇． 因此〇ｕ ＜ｎｖｖｔｎ ｖ当时， ？ 头部检查点与阻塞检查ｎ （ ， ）点对比： 如果Ｋ＂＞ ？，＿ 次， 那么，＝ｎ ｖ ｖ／，Ｄ （ ， ） ｉ ｖｈ ＿ ｖ ）ｎ ｖｖ ｈ－Ｚｉ ＋ｄｉ ＜＾ ＵＬ＾）＜Ｄ＾＝ａ ＿此外ｎ ｖ ｖ／，ｎｖ〇＇：？＝ 〇并且〇？ ＞〇， 因此２ １ １ ２ 计算机学报 ２ ０ ２ ０ 年综上所述， 由和０ ＾ ＜ Ｑ， 可知， 阻塞检查点模型开销高于非阻塞检查点．定理２ ． 若超级步简化为恒定速率的管道， 即叫＝％ ， 则头部检查点开销不高于尾部检查点．ｎ （ ／ ） （ ７ １ ＿７ ， ＾证明． 如果１； ＜叫且一ｖＡ那么〇丨： ？＝ｎｖ ｖｈＤ ｕ＼ ｖｈ—ｙ ）＾＋ 汐＾． Ｄ（ ， ＞ （ ｖ，—ｙ ）ｎ ｖｖｈ＇＇ｎｖ ｖ，〇Ｌ ？ ． 否则， ｄ＝〇并且 〇ｕ ＞ 〇． 因此 〇Ｋ〇：，？ ．定理１ 表明流水线数据流系统应采用无阻塞模型来保存迭代数据集以进行图形处理． 定理２ 表明，在超级步的头部检查用于图处理的迭代数据集可能导致低开销． 在某些情况下， 头部检查点没有开销（ 如例２ 和例３ ） ， 而尾部检查点会产生显着的成本．６ 实验分析对于本文提出的两种容错机制， 在Ｆｌｉ ｎ ｋ 系统上进行了实现， 通过修改Ｍ ｉｎ ｋ 底层源码， 提供了用户可以直接使用的补偿函数接口和可设置的头尾检查点参数． 通过在源码中增加一些ｋ ｉ ｌ ｌ 计算节点的方法， 模拟了计算节点出现故障． 使用优化的容错机制与Ｆｌｉ ｎ ｋ 系统原有的容错机制在故障发生后任务恢复耗费的的迭代次数和时间进行了对比与分析， 分别采用全量迭代Ｐ ａｇ ｅ Ｒａ ｎｋ 算法和增量迭代Ｃ ｏｎ ｎ ｅｃ ｔｅ ｄＣｏ ｍｐ ｏｎ ｅｎ ｔ ｓ 算法在不同规模的数据集上进行了实验．６ ． １ 数据集本文针对Ｐａ ｇ ｅＲａ ｎ ｋ 算法和Ｃｏｍｐ ｏｎ ｅ ｎｔ ｓ 算法采用了两类数据集． 分别是真实数据集和模拟数据集， 真实数据集ｇ ｅ ｍｓ ｅｃ－ Ｆ ａ ｃ ｅ ｂｏｏ ｋ 是斯坦福大学２ ０ １ ７ 年１ １ 月收集的有关Ｆａ ｃ ｅＢｏ ｏｋ 页面的数据；ｗｉ ｋ ｉ－ｔ ｏ ｐｃ ａ ｔ ｓ 是斯坦福大学２ ０ １ １ 年９ 月收集的维基百科的超链接网络图； Ｈｏ ｌ ｌ ｉ ｎ ｓ 数据集是霍林斯大学教育网的网页链接关系数据； ａ ｓ－ Ｓｋ ｉ ｔ ｔ ｅｒ 数据集为Ｉｎ ｔ ｅｒ ｎｅ ｔ 拓扑， 包含ｈ ｔ ｔｐ ： ／ ／ ｗ ｗｗ ． ｃ ａｉ ｄ ａ ． ｏ ｒｇ ／ ｔ ｏｏｌ ｓ ／ｍ ｅａ ｓ ｕｒ ｅｍ ｅｎ ｔ ／ ｓｋ ｉ ｔ ｔ ｅ ｒ 网站２ ０ ０ ５ 年每天运行的网页链接关系． ｃｉ ｔ－Ｐ ａ ｔ ｅｍ ｓ 数据集为国家经济研究局维护的美国专利数据集， 涵盖了１ ９ ６ ３ 年至１ ９ ９ ９ 年的专利及引用数据． ｗｅ ｂ－ Ｇｏｏｇｌ ｅ 数据集为谷歌网页数据．真实数据集主要用于全量迭代Ｐ ａｇ ｅ Ｒａ ｎ ｋ 算法实验分析． 模拟数据集ｄ ａ ｔ ａ ｓ ｅｔ ｌ－ ３ 是在实验时随机生成的具有较多连通分量的图数据集． 其主要用于Ｃｏ ｎ ｎｅ ｃ ｔｅ ｄＣｏｍ ｐｏ ｎｅ ｎ ｔ ｓ 算法， 因为在执行该算法时，收敛较快， 故随机生成了规模较大的连通图数据集．详细信息如表１ 所示．表１ 实验环境配置配置 参数机器节点数量 １ 主节点， ６ 从节点内存 ３２ Ｇ Ｂ Ｘ ６操作系统 Ｃｅｎ ｔＯｓ ７ＪＤ Ｋ 版本 １． ８ ． ０＿ １ ９ １开发环境 Ｉ ｎ ｔｅ ｌ ｌｉ Ｊ Ｉ ＤＥＡＦｌｉ ｎ ｋ 版本 １ ． ４ ． ２Ｈ ａ ｄ ｏｏ ｐ 版本 ２ ． ７ ． ３６． ２ 实验环境设置本文采用的全量迭代算法Ｐａ ｇ ｅＲａ ｎ ｋ 和增量迭代算法Ｃｏ ｍｐ ｏｎ ｅ ｎｔ ｓ 基于Ｆ ｌｉ ｎｋ ｌ． ４ ．２ 实现， 本文对底层源码进行了修改， 新增了迭代任务的乐观恢复容错功能． 并采用ｊａｖ ａ 语言编写具有乐观恢复容错机制的Ｐａ ｇｅ Ｒａ ｎｋ 算法和Ｃｏ ｍｐｏ ｎｅ ｎ ｔ ｓ 算法的案例与未优化的Ｈ ｉｎ ｋ 进行了实验对比． 实验分析的环境设置和使用的数据集如表１ 和表２ 所示．表２ 数据集数据集 Ｎ ｏ ｄ ｅｓ Ｅｄ ｇｅ ｓｇ ｅｍ ｓｅｃ－Ｆａ ｃｅ ｂ ｏ ｏ ｋ－２ ８－ ５ ０ ５ １ ５ ８ １ ９ ３０ ６ｗ ｉｋｉ－ｔ ｏ ｐ ｃａ ｔ ｓ１２９－１ ７ ９ １ ４ ８ ９ ２８ ５ １ １ ８０ ７Ｈｏ ｌ ｌ ｉ ｎ ｓ：３ ０］ ６ ０ １ ２ ２ ３ ８ ７ ５ａ ｓ－ Ｓｋｉ ｔ ｔｅ ｒ －３ １ －１ ６ ９ ６ ４ １ ５ １ １ ０ ９ ５ ２ ９ ８ｃｉ ｔ－ Ｐ ａ ｔ ｅｎ ｔｓ－］ ２ 」３７ ７４ ７ ６８ １ ６ ５ １ ８ ９ ４ ８ｗ ｅｂ － Ｇｏ ｏｇ ｌ ｅＬ Ｓ ３］ ８７ ５ ７ １ ３ ５ １ ０ ５ ０ ３ ９ｄ ａｔ ａｓｅ ｔ－１ ２ ０２ ０ ４ ０ ０ ０ ０ｄ ａｔ ａｓｅ ｔ－２ ５ ０ ０ １ ２ ２ ５ ０ ０ ０ １ ２ １ｄ ａｔ ａ ｓ ｅ ｔ－ ３ １ ０ ０ ０ ０ ０ ０ ０ １ ２ ０ ０ ０ ０ ０ ０６ ． ３ 实验结果与分析本文通过修改Ｆ ｌ ｉｎ ｋ ｌ ． ４ ． ２ 的源码， 新增了补偿函数接口． 新增参数来设置在指定的迭代次数ｋ ｉ ｌ ｌ节点， 模拟故障的发生． 乐观容错机制与Ｆ ｌ ｉ ｎｋ ｌ ． ４ ． ２原有的重启恢复容错机制在正确性、运行时间、故障发生后恢复所用的迭代次数上进行了分析． 在不同规模的数据集上展示的实验效果表明， 网络中顶点之间的边数越多， 对于全量迭代算法来说， 收敛速度越慢． 对于全量迭代算法来说， 收敛速度越快．（ １ ） 正确性评估基于乐观容错机制全量迭代算法Ｐａ ｇｅ Ｒａ ｎ ｋ 通过使用表１ 中的小数据集（ Ｈ ｏｌ ｌ ｉ ｎ ｓ ） 和大数据集（ ｗ ｉ ｋｉ－ｔ ｏｐ ｃ ａ ｔ ｓ ） 在分布式集群上运行？ Ｐａ ｇｅ Ｒａ ｎ ｋ 算法迭代收敛的阈值？ 取Ｖ （ １ 〇〇Ｘ Ａ〇的小数单位， Ｊ Ｖ为网页总数． 在所有实验中， 模拟故障发生时丢失的节点上的数据量为１ ／ ２ ０ ． 为了充分验证算法的正确１ １ 期 郭文鹏等： 面向Ｆ ｌｉ ｎ ｋ 迭代计笕的高效容错处理技术 ２ １ １ ３５１ ０２ ０３ ０４ ０发生故障时的迭代进度（ ｃ ） ｗｉｋｉ－ｔｏｐ ｃａ ｔｓ （ 总迭代次数６ ４ ）图１ ７Ｐａ ｇｅ Ｒａ ｎ ｋ 算法恢复迭代次数比较１ ０２ ０３ ０４ ０发生故障时的迭代进度（ ｂ ） ｆａｃ ｅｂ ｏｏ ｋ ａｒ ｔ ｉｓｔ（ 总迭代次数５ ０ ）９ ３９ ２１ ０ ２ ０３ ０４ ０迭代乐观恢复机制的正确性５０（ ｂ ） ｗｉ ｋｉ－ ｔｏ ｐ ｃａｔ ｓ图１ ６ 迭代乐观复制机制的正确性图１ ６ （ ａ ） 为小型数据集Ｈ ｏ ｌ ｌ ｉｎ ｓ 的实验效果，图１ ６ （ ｂ ） 为大型数据集ｗ ｉ ｋｉ－ ｔ ｏ ｐｃ ａ ｔ ｓ 的实验效果． 基于乐观容错机制的Ｃ ｏ ｎ ｎｅ ｃｔ ｅ ｄＣ ｏｍ ｐ ｏｎ ｅ ｎｔ ｓ 增量迭代算法的乐观恢复在发生故障时， 补偿恢复得到的结果和正常迭代得到的最终结果完全一致． 由图１ ６可以得出， 由于Ｐ ａｇ ｅＲ ａ ｎ ｋ 算法得到的最终结果是近似值， 故对于Ｐ ａｇ ｅ Ｒａ ｎ ｋ 算法实验的结果和原执行结果在同一收敛度且结果相差不超过５ ％ ， 可以认为两种结果均正确． 连通分量算法则完全保证了一致性结果即正确率为１ ０ ０ ％ ． 因此， 补偿函数得到的最终结果是正确的． 此外， 通过使用不同规模的数据集进行实验， 发现对于网络顶点数量较多的顶点，性（ 和正常迭代结果的重复率）， 对不同数据集的总迭代次数（ Ｈｏ ｌ ｌ ｉ ｎｓ ：１ ４２次， ｗ ｉ ｋｉ－ｔｏ ｐｃａ ｔ ｓ ： ６ ４次） 按不同的迭代间隔触发节点ｓ ｉ 发生故障， 并采用乐观的容错机制进行恢复． 将得到的最终结果与正常迭代的结果进行对比， 由于Ｐａ ｇｅ Ｒａ ｎ ｋ 算法结果本身就是近似值， 故两次迭代排名误差小于１ ０ 的网页认为排名正确． 小数据集结果的正确性和大数据集的正确性分别如图１ ６ 所示．９２１ ０２ ０４ ０８ ０迭代乐观恢复机制的正确性（ ａ ） Ｈｏ ｌ ｌ ｉ ｎ ｓ１ ２０收敛速度越快．（ ２ ） 恢复性能评估基于乐观容错机制全量迭代算法Ｐａ ｇｅ Ｒ ａ ｎｋ 和增量迭代算法Ｃｏ ｎｎ ｅｃ ｔ ｅｄ Ｃｏ ｍｐ ｏｎ ｅ ｎｔ ｓ 算法在模拟故障发生时， 恢复任务需要继续迭代至收敛． 依然采用正确性评估中的实验条件， 使用表２ 的真实数据数据集和模拟数据集进行实验， 针对不同规模数据集的迭代次数可以观察出优化后的Ｆ ｌ ｉ ｎ ｋ 恢复后执行的迭代次数均少于Ｆ ｌｉ ｎｋ 原有的迭代次数． 基于补偿函数的乐观容错机制在Ｐａ ｇ ｅＲ ａ ｎｋ 算法和Ｃ ｏ ｎ ｎｅ ｃ ｔ ｅ ｄＣ ｏｍ ｐ ｏ ｎｅ ｎ ｔ ｓ 算法上的迭代次数提升效果分别如图１ ７ 和图１ ８ 所示． 实验结果表明， 在迭代次数上， 乐观容错机制故障恢复后比原有的Ｆ ｌ ｉ ｎ ｋ 容Ｌ ０ ０９ ９９ ８ｉ１ ０２ ０３ ０发生故障时的迭代进度（ ａＨａ ｃｅｂ ｏｏ ｋ ａｔ ｈ ｌｅ ｔｅｓ （ 总迭代次数４ ６ ）４０｜ Ｂ 优化后的Ｆｌｉｎ ｋ Ｓ 未优化的｜Ｈ 优化后的Ｆｌｉ ｎ ｋ Ｓ 未优化的Ｆ ｌｉ ｎ ｋ｜０ Ｐ ａｇ ｅＲａｎ ｋ 算法结果正确＿ＮＣｏｎ ｎ ｅ ｃｔｅｄ Ｃｏ ｍｐｏ ｎ ｅｎ ｔ ｓ算法正确率０Ｐａ ｇ ｅＲａｎ ｋ 结果正确率ＳＣｏ ｎ ｎ ｅｃ ｔｅｄ ｃｏ ｍｐｏ ｎ ｅｎ ｔ ｓ结果正确率ＩＫ ＩＫ ＩＩ１ＩＩｏｏｏｏｏ５４３２１＾名＾ ３劫『＞１５１２鉍＾１％／齋蓉３１０８６０９９％／＃蓉ＨＩ＞型Ｓ２？ｗ＾ｌ＜／／／／／／？／／／？§§§§§§８８８ｓｓｓｓｓｓｓｓｓ８０８ｓ§§§§§§§§§§§§§§§００§§§§１ ０３ ０５ ０７０９ ０１ ０ ０发生故障时的迭代进度（ ａ ） ｄ ａ ｔａｓｅｔ １ （ 总迭代次数１ ０ １ ）表３ 和表４ 分别列举了乐观迭代容错优机制和悲观迭代容错优化机制的具体实验条件以及提升的百分比． 基于头尾检查点的容错机制在故障发生的不同阶段时间开销不同． 此外， 不同的硬件环境下，〇１ ０２ ０３ ０４０发生故障时的迭代进度（ ｃ ） ｗｉ ｋ卜ｔｏ ｐｃ ａｔｓ（ 总迭代次数６ ４ ）图１ ９Ｐ ａ ｇｅ Ｒａ ｎｋ 算法运行时间比较５１ ０２ ０３ ０４ ０发生故障时的迭代进度（ ｂ ）ｆ ａｃｅ ｂ ｏｏ ｋ＿ａｒｔ ｉｓｔ （ 总迭代次数５０ ）７ ００１ ０ ３ ０５０７ ０９ ０发生故障时的迭代进度１ ０ ０（ ｃ ）ｄ ａｔａ ｓｅｔ ３ 总迭代次数（１ ９ ３ ）图１ ８Ｐａ ｇ ｅ Ｒ ａ ｎ ｋ 算法恢复迭代次数比较（ ３ ） 迭代恢复时间评估分布式迭代计算的运行时间是影响计算效率的关键． 现实世界中的分布式集群出现的故障时间是无法精确预估的． 为了保证实验的完整性， 实验假定故障在总的迭代次数执行一半时发生故障． 使用Ｐ ａ ｇ ｅＲ ａ ｎｋ算法和Ｃ ｏ ｎ ｎｅ ｃ ｔ ｅ ｄＣ ｏｍ ｐｏ ｎｅ ｎ ｔ ｓ算法对大规模数据集进行了实验分析， 如图１ ９ 和图２ ０ 分别°５１ ０２ ０３ ０４０发生故障时的迭代进度（ ａ ） ｆ ａｃｅｂ ｏ ｏ ｋ＿ａ ｔｈ ｌ ｅｔ ｅｓ（ 总迭代次数４ ６ ）６０ ００１ ０３ ０５ ０７ ０９ ０１ ０ ０发生故障时的迭代进度（ ｂ ） ｄａ ｔａ ２ （ 总迭代次数１ ２ １ ）为不同数据集下的实验效果． 图２ １ 和图２ ２ 综合对比了不同数据集下的全量迭代和增量迭代使用乐观容错机制提升的效率． 实验效果表明， 在运行时间上， 基于乐观的容错机制比Ｆ ｌｉ ｎｋ 原有的容错机制在全量迭代上平均提升了１ ６ ． ８ １ ％ ， 在增量迭代平均提升了２ ４ ． ２ ％ ．６ ０ ０错机制在全量迭代上平均节省了３ ５ ． ８ ７ ％ ， 在增量迭代上随迭代进度呈线性提升． 在不同规模的数据集上验证了乐观容错恢复机制补偿后的快速的收敛恢复速度．１ ０ ０｜Ｂ 优化后的Ｆｌｉ ｎ ｋＳ 未优化的Ｆｌｉｎｋ ｜ｍｉ ｌ ｉ ｉ丨Ｈ 优化后的Ｆｌｉ ｎｋ Ｓ 未优化的Ｆｌｉ ｎ ｋ ｜１优化后的Ｆ ｌ ｉ ｎ ｋ Ｓ 未优化的Ｆ ｌ ｉ ｎ ｋ ｜２ １ １ ４ 计算机学 报 ２ ０ ２ ０ 年ｏｏｏｏ８６４２Ｏ Ｉ＆Ｏ Ｉ６５４０ ００ ００ ０ｏｏｏｏｏｏ８５２９６３ｗ＾＾ ｌ细Ｓ１ １５㈣峯ｏｏｏＩｏｏｏｏ５４３２ｏｏｏｏｏｏ２０８６４２ｏｏｏｏｏｏｏｏｏｏ５４３２１Ｓ／ＲＩ忘妇胡／／／／／／／／／／ｆｆｆ／ｆ／／／／／／？．ｆ／／／／／／／／／ＡＸＮＶＳＸＮＸＷＣＳＮＸＶＷＮＮＸＮＷＶＮＸＶ＾ｓｓｓｓｓｓｓｓｓｓｓ＼＼ｓｓｓｓ＞郭文鹏等： 面向Ｆｌ ｉ ｎ ｋ 迭代汁算的高效容错处理技术 ２ １ １ ５１ ０３ ０５ ０７０９ ０１ ０ ０迭代故障进度丨冬１ ２ ２ 增Ｗ 迭代不Ｎ 数据集下提升的效率１ ０ ０ａ ｓ－ Ｓ ｋ ｉｔ ｔｅ ｒｗ ｉ ｋｉ－ｔｏ ｐ ｃａ ｔｓ数据集（ ａ ） Ｐａｇ ｅＲａｎ ｋ 检查点时间对比１ ０２ ０３０迭代故障进度４ ０图２ １ 全Ｍ 迭代不同数据集下提升的效率３ ５５０１ ０３ ０５０７ ０９０１ ０ ０发生故障时的迭代进度（ ｃ ） ｄ ａｔ ａｓ ｅｔ３ （ 总迭代次数３ ７５ ）图２ ０Ｃ ｏｒｍｅ ｃ ｔ ｅ ｄ Ｃｏ ｍｐｏ ｎ ｅｎ ｔ 算法运行时间比较检查点的写人速率和效率也会有影响． 为了尽量避免该影响， 实验以迭代次数Ｖ＾＂（ 其中《为总迭代次数） 为间隔使用Ｃｏ ｎｎ ｅｃ ｔ ｅｄ Ｃｏ ｍｐ ｏ ｎ ｅｎ ｔ ｓ 算法和Ｐ ａｇ ｅ Ｒａ ｎ ｋ算法在数据ｉ－ｔｏｐ ｃａ ｔ ｓ 和ａ ｓ－ Ｓ ｋ ｉ ｔ ｔ ｅｒ 上进行实验． 其中运行时间分别如图２ ３ 所示． 实验效果表明， 尾部检查点的平均时间开销在全量和迭代和增量迭代上均优于现有的阻塞检查点， 平均节省开销分别为１ ３ ． ８ ２ ％ 和１ ０ ． ８ ７ ％ ． 面向迭代任务的尾部检查点的容错效率高于头部检查点．（ ａ ） ｄ ａ ｔａｓ ｅｔｌ （ 总迭代次数１ ０ １ ）１ ０３０５ ０７ ０９０１ ０ ０发生故障时的迭代进度（ ｂ ） ｄ ａ ｔ ａｓｅ ｔ２ （ 总迭代次数３４ ３ ）３ ５ ０３ ０ ０ｒ） （）３ ５ ０３ ０ ０数据集（ ｂ ） Ｃｏ ｎ ｎｅｃｔ ｅｄＣｏｍｐｏ ｎ ｅ ｎ ｔｓ检查点时间对比图２ ３ 不同检查点容错机制运行时间对比—？－ 优化后的Ｆｌ ｉ ｎｋ？ 未优化的Ｆｌ ｉ ｎ ｋ？ ｄａ ｔａ ｓ ｅｔ １ｄ ａ ｔａ ｓｅ ｔ２ｄ ａ ｔａ ｓ ｅｔ ３？？？ ＼ ｗ，１ １ 期ｏ ｌｏ ｌｏ ｌｏ ｌ７６５４０ ００５０３２２％／嫌較电蜞叵宏５ ０２ ０ １５ ００ ０ｖｔａｌｆｅｆｃｌ ｓｏｏｏｏｏ５０５０５２２１．—－ｏｏｏｏｏ０５０５０３２２１１ｖＲｌｆｅ＾ｌＦ２ ２９６次／ｔ ｌ较２ １ １ ６ 计算机学报 ２ ０ ２ ０ 年表３ 乐观容错机制实验条件及性能优化对比（ ａ ） Ｐａ ｇｅ Ｒａ ｎ ｋ 算法执行时间对比ｗｅ ｂ－ Ｇ ｏ ｏ ｇｌ ｅ ｓｏ ｃ－ＬＪ总迭代次数 ６ ４ ５ ８ＥＰＳ Ｉ Ｌ ＯＮ ０ ． ０ ０ ０ ０ ０ ０ ０ １ ０ ． ００ ０ ０ ０ ０ ０ ０ １Ｐａ ｇ ｅ ｓ ８ ７ ５ ７ １ ３ ４ ８ ４ ７ ５ ７ １Ｌｉ ｎ ｋ ｓ ５１ ０ ５ ０ ３ ９ ６ ８ ９ ９ ３ ７ ７ ３模拟故障 第３ ２ 次 第２ ９ 次未优化时间 ３ ６ ５ ｓ １ ８ ６ ７ ｓ优化后时间 ３ ４ ３ ｓ １ ７ ６ ４ ｓ提升百分比 ５ ． ７ ５ ％ ５ ． ５ ２ ％（ ｂ ）Ｃｏ ｎ ｎ ｅ ｃｔ ｅｄ Ｃｏ ｍ ｐｏ ｎ ｅｎ ｔ ｓ 算法执行时间对比ｄ ａ ｔ ａｓ ｅ ｔ ｌ ｄ ａ ｔａ ｓ ｅ ｔ ２ ｓｏ ｃ－ ＬＪ总迭代次数 １ ０ １ １ ２ １ １ ２Ｖｅ ｒ ｔｅ ｘ ２ ０ ２ ０ ５０ ０ １ ２ ２ ４ ８ ４ ７ ５ ７ １Ｅｄ ｇｅ ４ ０ ０ ０ ０ ５ ０ ０ ０ １ ２ １ ６８ ９ ９ ３ ７７ ３模拟故障 第５ ０ 次 第６ ０ 次 第６ 次未优化时间 Ｉ ｌ ｌ ｓ １ ６ ４ ｓ ３ ０ １ ｓ优化后时间 １ ３ ６ ｓ １ ３ ８ ｓ ２ ６ ６ ｓ提升百分比 ２ ２ ． ５ ２ ％ １ ５ ． ８ ５ ％ １ １ ． ６３ ％表４ 悲观容错机制实验条件及开销对比（ ａ ＞Ｐａ ｇｅＲ ａ ｎ ｋ 算法检查点所占开销ｓｃ－ Ｓ ｋ ｉ ｔｔ ｅ ｒ ｗ ｉ ｋ ｉ－ｔ ｏ ｐ ｃａ ｔｓ正常时间 ２ ９ ２ ｓ ４ ３ ４ ｓ头检查点 ３ ４ ０ ｓ ５ ２ ６ ｓ尾检查点 ３ ２ ７ ｓ ５ ０ ３ ｓ阻塞检查点 ３ ９ ３ｓ ６ ９ ７ ｓ头检查点开销 １ ６． ４ ％ ２ １ ． ２ ％尾检查点开销 １ １ ． ９ ％ １ ５ ． ８ ％阻塞检查点 ３ ４． ６ ％ ３ ７ ． ７ ＾头尾平均容错 １ ４． ２ ％ １ ８ ． ５ ％（ ｂ ） Ｃｏ ｎｎｅｃ ｔ ｅｄ Ｃｏｍ ｐ ｏ ｎ ｅ ｎ ｔｓ 算法检査点所占开销ｄ ａ ｔａ ｌ ｄ ａ ｔ ａ ２正常时间 １ １ ２ ｓ １ ３ ８ ｓ头检查点 １ ２ ４ ｓ １ ５ ３ ｓ尾检査点 １ １ ５ ｓ １ ４ ０ ｓ阻塞检査 １ ３ ３ ｓ １ ６ ５ ｓ头检査点开销 ９ ． ６ ％ １ ０． ９ ％尾检査点开销 ２ ． ７ ％ １ ． ４ ％阻塞检査点 １ ８ ． ８ ％ １ ９． ６ ％７ 总结本文提出了面向大规模迭代计算的乐观容错机制和悲观容错机制． 与现有的大数据计算平台的容错机制不同， 乐观容错机制只在故障发生时进行补偿恢复， 减少了不必要的容错代价和开销， 在故障率较低的情况下， 提拱了高效的处理性能． 悲观容错机制主要采用迭代数据流任务的特点， 将检查点注入迭代数据流中， 无需阻塞操作， 以较低的开销保证了迭代任务的正确执行． 大量的实验表明， 在处理大规模的迭代计算时， 乐观恢复的容错机制随迭代规模的增大和迭代进度的推移节省的迭代次数越多， 全量迭代运行时间平均提升３ ５ ． ８ ７ ％ ． 增量迭代随迭代进度呈线性提升． 在迭代中期出现故障时， 全量迭代运行时间平均提升１ ６ ． ８ １ ％ ． 增量迭代平均运行时间提升２ ４ ． ２ ％ ． 头尾检查点容错机制虽然与不同的硬件环境和网络带宽有关， 但其总体代价开销在不同情况下均小于阻塞检査点． 尾部检査点面向增量迭代任务平均节省的时间代价开销为１ ３ ． ８ ２ ％ ，面向全量迭代任务平均提升１ ０ ． ８ ７ ％ ． 由于受网络带宽和外部设备的影响， 悲观的容错机制误差较较大， 但尾部检査点和头部检査点的代价开销均小于阻塞检査点． 后期将会采取某种技术手段， 调整网络带宽并结合磁盘是否空闲来减少外界条件不同引人的误差． 目前的补偿函数迭代次数优化的比例通常高于迭代时间优化的比例， 可能的原因是补偿函数数据收集完成之后没有释放中间数据的内存， 导致之后的迭代时间优化效率偏低． 下一步将针对现有的内存消耗型补偿算法进行优化．参考文献［ １ ］Ｚ ｈａ ｎ ｇＹ ？ Ｇａ ｏＱ ？ Ｇａｏ Ｌ ？ ｅｔ ａｌ． ｉＭａ ｐ Ｒｅ ｄ ｕ ｃｅ ： Ａ ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅｄｃｏｍ ｐ ｕ ｔｉ ｎ ｇ ｆ ｒａｍｅ ｗｏ ｒ ｋ ｆｏ ｒ ｉｔ ｅ ｒ ａｔｉｖ ｅｃｏｍｐ ｕ ｔ ａ ｔｉｏｎ ．Ｊｏ ｕ ｒ ｎａ ｌ ｏ ｆＧ ｒ ｉｄ Ｃｏｍ ｐ ｕ ｔｉ ｎ ｇ ， ２０ １ ２ ， １ ０ （ １ ） ： ４ ７－６ ８［ ２ ］ Ｍａｓｓ ｕ ｃｃｉ ＦＡ ？Ｄｏｃａ ｍｐｏ Ｄ ．Ｍｅａ ｓ ｕ ｒｉ ｎｇｔ ｈｅａ ｃａ ｄｅ ｍｉｃ ｒ ｅｐ ｕｔ ａｔ ｉ ｏｎｔｈｒ ｏｕ ｇ ｈ ｃｉ ｔａ ｔｉｏ ｎ ｎｅｔ ｗｏ ｒ ｋｓ ｖｉ ａ ＰａｇｅＲ ａｎｋ ． Ｊｏ ｕ ｒｎａｌｏ ｆ Ｉ ｎｆｏ ｒｍｅｔ ｒｉ ｃｓ，２ ０ １ ９ ， １ ３ （ １ ） ： １ ８ ５ － ２ ０ １［３ ］ Ｈａｖｅ ｌ ｉｗ ａｌ ａ Ｔ Ｈ． Ｔｏ ｐ ｉ ｃ － ｓｅｎ ｓｉｔｉｖｅ ＰａｇｅＲａｎｋ： Ａ ｃｏｎ ｔ ｅｘｔ－ｓｅｎ ｓｉｔｉｖｅｒａ ｎ ｋｉ ｎ ｇ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ ｆｏ ｒ ｗｅ ｂｓ ｅａ ｒ ｃ ｈ．Ｉ ＥＥＥＴ ｒａ ｎｓａ ｃ ｔ ｉ ｏ ｎｓ ｏ ｎＫ ｎ ｏ ｗ ｌ ｅｄ ｇ ｅ ａ ｎ ｄ Ｄａ ｔ ａＥｎｇ ｉ ｎｅ ｅｒ ｉ ｎｇ ＊ ２ ０ ０ ３ ？ １ ５ （ ４ ） ： ７ ８ ４ － ７ ９６［４］Ｇｏ ｎ ｚ ａ ｌ ｅｚ Ｓａ ｎｃｈ ｅ ｚＲ ．Ｍｅａ ｓｕ ｒ ｅ ｍｅ ｎ ｔ ｓａｎ ｄ ａ ｎａ ｌ ｙ ｓｉ ｓ ｏ ｆ ｏ ｎ ｌ ｉ ｎ ｅｓ ｏ ｃ ｉ ａｌ ｎ ｅ ｔ ｗｏ ｒ ｋ ｓ ． Ｍａｔ ｅ ｒ ｉ ａｌ ｓ Ｔ ｒ ａ ｎ ｓ ａ ｃｔｉ ｏ ｎ ｓ Ｊ ＩＭ ， ２ ０ １ ４， ２ １ （ ３ ） ：１ ５ ９ －１ ６８［ ５ ］ Ｌｉ Ｊ Ｒ ？ Ｃｈ ｅ ｎＬ， Ｗ ａｎ ｇＳ Ｐ ， ｅ ｔ ａｌ ． Ａｃｏ ｍｐ ｕ ｔａ ｔｉｏ ｎａ ｌ ｍｅｔ ｈｏ ｄｕ ｓ ｉ ｎ ｇｔ ｈ ｅ ｒ ａｎ ｄ ｏｍｗ ａｌ ｋｗ ｉｔ ｈｒ ｅｓ ｔ ａｒ ｔ ａ ｌｇ ｏ ｒ ｉｔ ｈｍ ｆ ｏ ｒ ｉ ｄ ｅ ｎ ｔｉ ｆ ｙ ｉ ｎ ｇｎ ｏ ｖ ｅ ｌ ｅ ｐ ｉ ｇ ｅｎ ｅ ｔ ｉ ｃ ｆ ａｃ ｔｏ ｒｓ ．Ｍｏ ｌ ｅ ｃｕ ｌ ａ ｒ Ｇ ｅｎ ｅ ｔｉ ｃｓａ ｎ ｄ Ｇｅｎ ｏｍ ｉ ｃｓ ？２ ０ １ ８，２ ９ ３ （ １ ） ：２ ９ ３ － ３ ０ １［６ ］Ａｄ ｅ ｗｏ ｌ ｅＫＳ ？ Ａｎ ｕ ａ ｒＮ Ｂ ， Ｋ ａｍ ｓｉ ｎ Ａ ． Ｍａ ｌ ｉ ｃｉ ｏ ｕ ｓ ａｃ ｃ ｏ ｕ ｎｔ ｓ：Ｄａｒ ｋ ｏ ｆ ｔｈ ｅ ｓｏ ｃｉａ ｌ ｎ ｅｔ ｗｏ ｒ ｋｓ．Ｊ ｏ ｕ ｒｎ ａ ｌ ｏ ｆ Ｎ ｅｔ ｗ ｏ ｒｋＣｏｍｐ ｕ ｔｅ ｒＡｐ ｐ ｌ ｉ ｃａｔ ｉ ｏ ｎ ｓ ， ２ ０ １ ７ ， ７ ９ （ １ ）： ４ １－ ６ ７［７ ］Ｓ ｈｕ Ｋａ ｉ ， Ｗ ａｎ ｇ Ｓｕ － Ｈａ ｎｇ ， Ｔａ ｎ ｇ Ｊ ｉ－Ｌｉａ ｎ ｇ ， ｅ ｔ ａｌ ． Ｕｓ ｅｒ ｉ ｄ ｅｎ ｔ ｉ ｔ ｙｌ ｉｎｋａｇ ｅ ａｃｒ ｏ ｓｓ ｏ ｎ ｌ ｉ ｎｅ ｓｏ ｃｉ ａｌ ｎｅｔ ｗｏ ｒｋｓ： Ａ ｒｅ ｖｉ ｅｗ． ＡＣＭＳ ＩＧ ＫＤＤＥｘｐ ｌ ｏ ｒ ａ ｔ ｉ ｏ ｎ ｓ Ｎｅ ｗｓｌ ｅ ｔ ｔｅ ｒ ， ２０ １ ７ ， １ ８ （ ２ ）： ５ －１ ７［８ ］Ｘｕ Ｃ ， Ｈｏ ｌ ｚ ｅ ｍｅ ｒＭ ， Ｋ ａ ｕ ｌ Ｍ ， ａ ｎｄ Ｍａｒ ｋ ｌ Ｖ．Ｅｆ ｆ ｉ ｃｉｅ ｎ ｔｆ ａ ｕ ｌ ｔ－ｔｏ ｌ ｅｒ ａｎ ｃｅ ｆｏ ｒ ｉ ｔ ｅｒ ａ ｔ ｉ ｖ ｅｇｒ ａ ｐ ｈ ｐ ｒ ｏｃ ｅｓ ｓ ｉｎ ｇ ｏ ｎ ｄ ｉ ｓｔｒｉ ｂ ｕ ｔ ｅｄ ｄ ａｔ ａ ｆｌｏ ｗｓｙ ｓｔ ｅｍｓ／ ／ Ｐｒ ｏ ｃｅｅｄｉ ｎｇ ｓ ｏｆ ｔ ｈｅ ＩＥＥＥ３ ２ ｎ ｄ Ｉｎ ｔ ｅｒ ｎａ ｔｉｏ ｎ ａｌ Ｃｏ ｎｆ ｅｒ ｅ ｎｃｅＤａ ｔａ Ｅ ｎ ｇ ｉ ｎ ｅｅ ｒ ｉ ｎ ｇ ． Ｈｅ ｌ ｓ ｉ ｎ ｋｉ， Ｆｉ ｎ ｌ ａｎ ｄ ， ２ ０ １ ６ ：６ １ ３－６ ２ ４［ ９ ］Ｐｅ ｎｇＷ ， Ｌ ｉＭ， Ｃ ｈ ｅｎ Ｌ ， ｅｔ ａ ｌ ． Ｐ ｒ ｅｄｉｃ ｔｉｎ ｇ ｐ ｒ ｏ ｔｅｉｎｆ ｕ ｎ ｃｔｉｏ ｎｓｂ ｙ ｕ ｓ ｉ ｎ ｇｕ ｎ ｂ ａｌ ａ ｎ ｃｅｄ ｒ ａｎｄ ｏ ｍ ｗａ ｌ ｋ ａｌ ｇ ｏ ｒ ｉｔ ｈｍ ｏｎ ｔｈ ｒｅ ｅ ｂ ｉ ｏｌ ｏ ｇｉ ｃａ ｌｎｅｔ ｗｏ ｒ ｋｓ ． ＩＥ ＥＥ ／ ＡＣ Ｍ Ｔｒ ａ ｎｓ ａ ｃｔｉｏ ｎ ｓｏ ｎ Ｃｏｍｐ ｕ ｔａ ｔｉ ｏ ｎａｌ Ｂｉ ｏ ｌ ｏ ｇ ｙａｎｄ Ｂｉｏｉ ｎ ｆｏ ｒｍ ａｔｉ ｃｓ ， ２ ０ １ ７ ＊ １ ４ （ ２ ） ： ３ ６ ０ －３６ ９郭文鹏等： 面向Ｆｌ ｉ ｎ ｋ 迭１ １ 期 代计 算的 高 效 容错处 理技术 ２ １ １ ７［ １ ０］ Ｙｕ Ｊ ｉ ｅ － Ｇ ｅ ｎ ｇ ． Ｙｉ ｎ ｇ Ｌｉ ｎ ， Ｙ ａｎＭａ ， ｅ ｔ ａｌ． Ｉ ｎ ｔ ｅｒ ａｃ ｔ ｉ ｖｅ ｖ ｉｓ ｕ ａ ｌ ｉ ｚ ａ ｔ ｉ ｏｎｏ ｆ ＤＧ Ａ ｄ ａ ｔ ａ ｂ ａ ｓｅｄ ｏ ｎ ｍｕ ｌ ｔ ｉ ｐ ｌ ｅ ｖｉ ｅｗ ｓ． Ｊ ｏｕ ｒ ｎ ａ ｌ ｏ ｆ Ｐ ｈ ｙ ｓｉ ｃ ｓＣｏ ｎ ｆｅ ｒ ｅ ｎ ｃｅ ＊ ２ ０ １ ７， ７ ８ ７ （ １ ） ： ０ １ ２ ０ ０ １［ １ １ ］Ｗ ａ ｎ ｇＱｉ ａ ｎ ， Ｗａ ｎ ｇＪ ｕ ｎ－ Ｂｏ ． Ｉ ｍｐ ｒ ｏｖ ｅｄ ｃｏ ｌ ｌ ａ ｂｏ ｒａ ｔ ｉｖ ｅ ｆ ｉ ｌ ｔ ｅ ｒ ｉ ｎ ｇｒ ｅ ｃｏｍ ｍｅｎ ｄ ａｔｉｏ ｎ ａｌ ｇ ｏ ｒ ｉｔ ｈ ｍ． Ｃｏ ｍｐ ｕ ｔ ｅ ｒ Ｓｃ ｉ ｅｎ ｃ ｅ ， ２ ０ １ ０ ， ３ ７ （ ６ ） ：２ ２ ６ － ２ ２ ８ （ ｉ ｎＣｈ ｉ ｎｅｓ ｅ ）（ 王茜， 王均波．一种改进的协同过滤推荐算法． 计算机科学， ２ ０ １ ０， ３ ７ （ ６ ） ： ２ ２ ６－ ２ ２ ８ ）［１ ２］Ｊ ｅ ｏｎｇ Ｙ Ｊ ， Ｌ ｅ ｅＪ ， Ｍ ｏｏ ｎ Ｊ ， ｅ ｔ ａ ｌ ． Ｋ－ Ｍｅａ ｎ ｓｄ ａ ｔ ａ ｃｌ ｕｓ ｔ ｅｒｉｎ ｇｗ ｉｔ ｈ ｍ ｅｍｒ ｉ ｓ ｔｏ ｒｎ ｅ ｔ ｗ ｏ ｒ ｋ ｓ ．Ｎａ ｎ ｏＬ ｅ ｔ ｔ ｅ ｒ ｓ ＊２０ １ ８ ，１ ８ （ ７ ） ：４ ４ ４ ７ － ４４ ５ ３［ １ ３ ］Ｄｉｔ ｔ ｒｉｃ ｈＪ？ Ｑｕ ｉａ ｎｅ－ Ｒ ｕ ｉ ｚ Ｊ Ａ． Ｅ ｆｆｉｃｉ ｅ ｎ ｔ ｂｉ ｇ ｄａ ｔ ａｐ ｒｏ ｃｅ ｓ ｓｉ ｎ ｇｉ ｎＨ ａ ｄ ｏ ｏ ｐ Ｍａ ｐ Ｒ ｅｄ ｕ ｃｅ． Ｐ ｒ ｏ ｃｅ ｅｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅＶ ＬＤ ＢＥ ｎ ｄ ｏｗ ｍｅ ｎ ｔ，２ ０ １ ２ ，５ （ １ ２ ） ： ２ ０ １ ４－ ２ ０ １ ５［ １ ４］Ｚａ ｈ ａ ｒ ｉ ａ Ｍ ， Ｘｉ ｎ ＲＳ ． Ｗｅ ｎ ｄ ｅ ｌ ｌ Ｐ ．ｅ ｔ ａｌ． Ａ ｐａ ｃｈ ｅｓ ｐ ａｒ ｋ ：Ａｕ ｎｉ ｆ ｉ ｅｄ ｅ ｎ ｇ ｉ ｎ ｅ ｆ ｏｒ ｂ ｉ ｇ ｄａ ｔ ａ ｐ ｒ ｏ ｃ ｅｓ ｓ ｉ ｎｇ ． Ｃｏｍ ｍｕ ｎ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓｏ ｆ ｔ ｈ ｅＡＣ Ｍ ， ２ ０ １ ６ ， ５ ９ （ １ １ ） ： ５ ６－６ ５［ １ ５ ］ Ｃａ ｒ ｂ ｏ ｎ ｅ Ｐ ， Ｋ ａ ｔｓ ｉ ｆ ｏ ｄ ｉ ｍｏ ｓＡ ，Ｅ ｗｅ ｎ Ｓ ，ｅ ｔ ａ ｌ ．Ａｐ ａ ｃ ｈ ｅ ｆｌ ｉ ｎｋ ：Ｓ ｔ ｒｅａ ｍａ ｎ ｄ ｂ ａ ｔ ｃ ｈ ｐ ｒ ｏ ｃｅ ｓｓ ｉｎ ｇ ｉ ｎ ａｓ ｉ ｎ ｇ ｌ ｅｅ ｎ ｇｉ ｎ ｅ ． Ｂ ｕ ｌ ｌ ｅ ｔｉ ｎ ｏ ｆｔ ｈ ｅ Ｉ Ｅ ＥＥ Ｃｏ ｍｐ ｕ ｔ ｅ ｒＳｏ ｃ ｉ ｅｔ ｙ Ｔ ｅ ｃｈ ｎ ｉ ｃ ａ ｌＣｏ ｍ ｍｉｔ ｔ ｅｅ ｏ ｎ Ｄａ ｔ ａＥ ｎ ｇ ｉ ｎ ｅｅ ｒｉｎｇ ， ２ ０ １ ５ ， ３ ６ （ ４ ） ： ２ ８－３ ８［ １ ６ ］Ｓｃ ｈｅ ｒ ｂ ａ ｕ ｍ Ｊ， Ｎ ｏ ｖ ｏ ｔ ｎｙ Ｍ ， Ｖａ ｙ ｄａ Ｏ ．Ｓ ｐ ｌ ｉ ｎ ｅ ： Ｓｐ ａ ｒ ｋ ｌ ｉ ｎ ｅａ ｇ ｅ ，ｎ ｏ ｔ ｏ ｎ ｌ ｙ ｆ ｏ ｒ ｔ ｈ ｅ ｂ ａｎ ｋｉ ｎｇ ｉ ｎ ｄ ｕ ｓ ｔ ｒ ｙ ／ ／ Ｐ ｒｏ ｃｅ ｅｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ ＩＥ ＥＥＩ ｎ ｔ ｅ ｒ ｎ ａ ｔｉｏ ｎ ａ ｌＣｏ ｎ ｆ ｅｒ ｅ ｎ ｃｅ ｏ ｎ Ｂｉ ｇ Ｄａ ｔ ａ ａｎ ｄＳ ｍａ ｒ ｔＣ ｏｍ ｐ ｕ ｔｉ ｎ ｇ（ Ｂｉ ｇＣｏ ｍ ｐ ） ． Ｓｈ ａ ｎ ｇ ｈ ａ ｉ ． Ｃｈ ｉ ｎａ ＊ ２ ０ １ ８ ： ４ ９ ５－ ４ ９ ８［ １ ７ ］Ｋ ｉｅ ｈ ｎ Ａ ， Ａｇ ｇ ａｒ ｗａ ｌ Ｄ．Ａ ｓｔ ｕ ｄ ｙ ｏ ｆｍ ｕ ｔ ａ ｂ ｌ ｅｃ ｈ ｅ ｃ ｋ ｐ ｏｉｎ ｉｉｎ ｇａ ｎｄｒ ｅ ｌａ ｔｅ ｄａ ｌ ｇ ｏ ｒ ｉｔ ｈｍ ｓ． Ｓ ｃｉ ｅ ｎ ｃ ｅｏ ｆ Ｃｏｍ ｐ ｕ ｔ ｅ ｒ Ｐ ｒｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ．２ ０ １ ８ ， １ ６ ０ （ １ ）：７ ８ － ９ ２［ １ ８ ］Ｗｅ ｎ Ｍ ｅｉ．Ｌ ｉ Ｈｏ ｎ ｇ－ Ｌ ｉ ａ ｎ ｇ ．Ｒｅ ｓｅ ａ ｒ ｃｈ ａ ｎ ｄ ｐ ｒ ａ ｃｔ ｉ ｃｅ ｏ ｆ ｔ ｈ ｅｒ ｏ ｌ ｌ－ｆ ｏ ｒ ｗ ａ ｒｄ ｒ ｅ ｃｏｖ ｅ ｒ ｙ ｔｅ ｃｈ ｎ ｉ ｑ ｕ ｅ ｉ ｎ ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔｅ ｄ ａ ｎ ｄ ｒ ｅａ ｌ－ｔ ｉ ｍｅｓ ｙ ｓ ｔｅ ｍｓ ．Ｃｏ ｍ ｐ ｕ ｔｅ ｒ Ｅｎ ｇ ｉ ｎ ｅｅ ｒｉ ｎ ｇ ８＾ － Ｓｃ ｉ ｅｎ ｃ ｅ ？ １ ９ ９９ ，２ １ （ ５ ） ：２ ８－ ３ １ （ ｉ ｎＣ ｈ ｉ ｎ ｅｓｅ ）（ 文梅， 李宏亮． 分布式实时系统中前向恢复技术的研究与实践． 计算机工程与科学， １ ９ ９ ９ ， ２ １ （ ５ ） ： ２ ８ － ３ １ ）［ １ ９ ］Ｄｅ ａｎ Ｊ？ Ｇ ｈ ｅ ｍａｗａ ｔ Ｓ． Ｍ ａ ｐ Ｒ ｅｄ ｕ ｃｅ ： Ｓｉ ｍｐ ｌｉｆ ｉ ｅ ｄ ｄ ａ ｔ ａ ｐ ｒ ｏｃ ｅｓ ｓｉ ｎ ｇｏ ｎｌ ａ ｒｇ ｅ ｃｌ ｕ ｓｔ ｅ ｒ ｓ． Ｉ ｎ ＯＳ ＤＩ ， ２０ ０ ４： １ ３ ７－１ ５ ０［ ２ ０］Ｚｈｏｕ Ｊ ｉ ａ ｎ ｇ ． Ｗａｎ ｇＷｅｉ－ Ｐｉ ｎ ｇ ． Ｍｅｎ ｇ Ｄａｎ， ｅｔ ａｌ ．Ｋ ｅｙ Ｔｅｃ ｈ ｎ ｏｌ ｏ ｇｙｉ ｎｄｉ ｓ ｔ ｒ ｉｂ ｕ ｔ ｅ ｄ ｆｉｌ ｅ ｓｙ ｓ ｔ ｅ ｍ ｔ ｏｗ ａ ｒ ｄ ｓ ｂｉｇｄ ａ ｔａ ａ ｎ ａ ｌ ｙ ｓｉ ｓ． Ｊ ｏ ｕ ｒ ｎ ａ ｌｏｆ Ｃｏｍｐ ｕ ｔｅ ｒ Ｒｅ ｓ ｅａ ｒ ｃｈ ａ ｎ ｄ Ｄｅ ｖ ｅｌ ｏｐ ｍｅｎ ｔ， ２ ０ １ ４， ５ １ （ ２ ） ： ３ ８ ２ －３ ９４ （ ｉ ｎ Ｃ ｈ ｉ ｎ ｅｓ ｅ）（ 周江， 王伟平． 孟丹等． 面向大数据分析的分布式文件系统关键技术． 计箅机研究与发展， ２ ０ １ ４ ， ５ １（ ２ ） ： ３８ ２ －３ ９ ４ ）［ ２ １ ］ Ｅｗｅｎ Ｓ ， Ｔｚｏ ｕ ｍａ ｓＫ ． Ｋａ ｕ ｆｍａｎ ｎ Ｍ， ｅ ｔ ａ ｌ． Ｓｐ ｉｎ ｎ ｉｎ ｇｆ ａｓ ｔ ｉｔ ｅ ｒａ ｔｉｖｅｄ ａ ｔ ａ ｆ ｌ ｏｗ ｓ． Ｐ ｒｏ ｃ ｅｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ ＶＬＤ ＢＥｎ ｄ ｏｗ ｍｅ ｎ ｔ ，２ ０ １ ２ ，５ （ １ １ ） ：１ ２ ６ ８ －１ ２ ７ ９ＧＵ ＯＷｅ ｎ －Ｐ ｅｎｇ ， Ｍ． Ｓ．ｃ ａ ｎ ｄ ｉ ｄａ ｔ ｅ ．Ｈｉ ｓ ｍａｊｏ ｒ ｒｅ ｓ ｅ ａ ｒｃｈｉｎｔ ｅ ｒ ｅ ｓ ｔ ｉｓ ｂ ｉ ｇ ｄａ ｔ ａ ．［２ ２ ］Ｄ ｕ ｄ ｏ ｌ ａｄ ｏ ｖ Ｓ ， Ｘ ｕＣ ， Ｓｃ ｈ ｅｌ ｔｅ ｒ Ｓ ，ｅｔａ ｌ． Ｏｐ ｔｉ ｍｉ ｓ ｔｉ ｃｒ ｅｃ ｏ ｖ ｅｒ ｙｆｏ ｒ ｉｔ ｅ ｒａ ｔｉ ｖ ｅ ｄ ａ ｔ ａ ｆ ｌ ｏｗ ｓｉ ｎ ａｃ ｔｉ ｏ ｎ／ ／ Ｐ ｒ ｏ ｃ ｅｅｄｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅＡ ＣＭＳＩ ＧＭＯ ＤＩ ｎ ｔ ｅ ｒｎａ ｔ ｉ ｏ ｎ ａｌ Ｃ ｏ ｎ ｆ ｅｒ ｅ ｎ ｃ ｅｏ ｎＭａ ｎ ａｇ ｅｍ ｅｎｔ ｏ ｆ Ｄａ ｔ ａ．Ｍｅ ｌ ｂ ｏｕ ｒ ｎ ｅ ， Ｖｉ ｃｔ ｏ ｒ ｉ ａ ， Ａｕ ｓ ｔ ｒ ａ ｌ ｉ ａ ， ２ ０ １ ５ ： １ ４ ３ ９ －１ ４ ４ ３［ ２ ３ ］Ｅｋ ａ ｎ ａ ｙ ａ ｋ ｅ Ｊ ． ＬｉＨ ． Ｚ ｈ ａ ｎ ｇ Ｂ ． ｅｔ ａ ｌ ．Ｔ ｗ ｉ ｓ ｔ ｅｒ ： Ａ ｒ ｕ ｎ ｔ ｉ ｍ ｅ ｆｏｒｉ ｔ ｅｒ ａ ｔ ｉ ｖ ｅＭａ ｐ Ｒ ｅｄ ｕｃ ｅ／ ／ Ｐ ｒ ｏｃ ｅｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ Ａ ＣＭＩ ｎ ｔｅ ｒ ｎ ａ ｔ ｉ ｏ ｎａ ｌＳ ｙｍｐ ｏ ｓ ｉ ｕ ｍ ｏｎ Ｈ ｉ ｇ ｈ Ｐｅ ｒｆｏ ｒｍａ ｎｃｅ Ｄｉｓ ｔ ｒ ｉｂ ｕ ｔ ｅ ｄＣｏｍ ｐ ｕ ｔｉ ｎ ｇ．Ｃ ｈ ｉ ｃａ ｇｏ ． Ｉ ｌ ｌ ｉ ｎ ｏｉ ｓ，２ ０ １ ０ ： ８ １ ０ － ８ １ ８［ ２ ４ ］ ＢｕＹ ， Ｈ ｏ ｗｅ Ｂ ， Ｂａ ｌ ａ ｚｉ ｎ ｓ ｋ ａＭ ， ｅ ｔａ ｌ ．Ｈ ａ Ｌｏ ｏ ｐ ：Ｅ ｆｆ ｉ ｃｉ ｅ ｎ ｔｉｔ ｅ ｒ ａ ｔｉ ｖｅ ｄ ａ ｔ ａ ｐ ｒ ｏ ｃｅ ｓｓ ｉ ｎ ｇ ｏ ｎ ｌ ａ ｒｇ ｅ ｃｌ ｕ ｓ ｔ ｅ ｒ ｓ． Ｐ ｒｏ ｃ ｅｅ ｄｉｎ ｇ ｓ ｏ ｆｔ ｈｅＶ Ｌ ＤＢＥ ｎ ｄ ｏｗ ｍ ｅｎ ｔ ， ２０ １ ０ ， ３ （ １－ ２ ） ：２ ８ ５ － ２ ９ ６［ ２ ５ ］Ｕ ｐ ａｄ ｈｙ ａ ｙａ Ｐ ． Ｋ ｗ ｏ ｎ ＹＣ ， Ｂａ ｌ ａ ｚ ｉ ｎ ｓ ｋ ａＭ ．Ａ ｌ ａｔ ｅ ｎ ｃｙ ａ ｎ ｄｆ ａ ｕ ｌ ｔ－ｔｏ ｌ ｅｒ ａ ｎ ｃ ｅｏ ｐ ｔ ｉ ｍｉ ｚｅ ｒｆｏ ｒｏ ｎ ｌ ｉ ｎ ｅ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｑｕ ｅ ｒ ｙｐ ｌ ａ ｎ ｓ／ ／Ｐ ｒ ｏ ｃｅ ｅ ｄ ｉ ｎ ｇｓ ｏ ｆ ｔ ｈ ｅ ＡＣ ＭＳ ＩＧ ＭＯＤ Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔｉｏ ｎａ ｌＣｏ ｎ ｆｅ ｒ ｅ ｎｃｅｏｎ Ｍａ ｎ ａ ｇ ｅｍ ｅｎ ｔ ｏ ｆ Ｄａ ｔａ ． ２０ １ １ ：２ ４ １－２ ５ ２［ ２ ６ ］Ａｌ ｅ ｘ ａ ｎ ｄ ｒ ｏ ｖ Ａ ， Ｂｅ ｒ ｇ ｍａ ｎ ｎ Ｒ ， Ｅｗ ｅｎ Ｓ ， ｅ ｔ ａ ｌ ．Ｔ ｈｅ ｓ ｔ ｒ ａ ｔ ｏ ？ｓ ｐ ｈ ｅ ｒ ｅｐ ｌａ ｔ ｆ ｏ ｒｍｆｏ ｒｂ ｉｇ ｄ ａ ｔａ ａｎ ａｌ ｙ ｔｉ ｃｓ．Ｔ ｈ ｅＩ ｎｔ ｅ ｒ ｎ ａ ｔｉ ｏ ｎ ａ ｌＪ ｏ ｕ ｒ ｎ ａ ｌｏ ｎ Ｖｅ ｒｙ Ｌ ａ ｒ ｇ ｅＤ ａｔ ａ Ｂａ ｓ ｅ ｓ ， ２ ０ １ ４ ， ２ ３ （ ６ ） ： ９ ３ ９－９ ６４［ ２ ７ ］Ｂｅｎｊａｍ ｉ ｎ ＡＳ ＊Ｄｉ ａ ｚＭＭ ， Ｌａ ｕ ｒ ａ Ｅ ， ｅ ｔ ａｌ ．Ｔｅ ｓ ｔ ｓｏｆ ｔ ｈ ｅＤＲ ＹＡＤ ｔ ｈ ｅｏ ｒｙ ｏ ｆｔ ｈ ｅ ａｇ ｅ－ｒ ｅ ｌａ ｔ ｅｄ ｄｅ ｆｉｃ ｉｔ ｉ ｎｍｅ ｍｏｒｙ ｆｏｒ ｃｏ ｎ ｌ ｅｘ ｔ：Ｎ ｏ ｔ ａ ｂｏ ｕ ｔｃ ｏ ｎｔ ｅ ｘ ｔ ？ａ ｎ ｄ ｎ ｏ ｔａ ｂ ｏｕ ｔ ａ ｇ ｉ ｎ ｇ ． Ｐｓ ｙ ｃｈ ｏ ｌ ｏｇ ｙ＆－Ａ ｇ ｉ ｎ ｇ ， ２ ０ １ ２ ， ２ ７ （ ２ ） ： ４ １ ８－ ４ ２ ８［２ ８ ］Ｌｉ Ｚ ， Ｎ ｉ ｅＦ ， Ｃ ｈ ａ ｎｇＸ ， ｅ ｔａ ｌ ．Ｒ ａｎ ｋ －ｃ ｏｎ ｓ ｔ ｒ ａ ｉ ｎ ｅｄｓ ｐｅ ｃ ｔｒ ａ ｌｃｌ ｕ ｓ ｔ ｅｒ ｉ ｎ ｇｗ ｉｔ ｈｆｌ ｅ ｘ ｉ ｂ ｌ ｅ ｅｍｂ ｅｄ ｄ ｉ ｎｇ ．Ｉ ＥＥ ＥＴ ｒ ａ ｎｓａ ｃ ｔ ｉ ｏ ｎ ｓｏ ｎＮ ｅ ｕ ｒ ａ ｌＮ ｅ ｔ ｗｏ ｒ ｋ ｓａ ｎ ｄ Ｌ ｅａ ｒ ｎ ｉ ｎ ｇ Ｓｙ ｓ ｔ ｅｍ ｓ ？２ ０ １ ８ ，２ ９ （ １ ２ ） ：６０ ７ ３－６ ０ ８ ２［ ２ ９ ］Ｙ ｉ ｎＨ ， Ｂ ｅ ｎ ｓ ｏ ｎ Ａ Ｒ ， Ｌｅｓ ｋ ｏ ｖ ｅｃ Ｊ ， ｅｔ ａ ｌ ． Ｌｏ ｃ ａ ｌｈ ｉ ｇ ｈ ｅ ｒ－ ｏ ｒ ｄ ｅｒｇ ｒ ａ ｐｈ ｃ ｌ ｕｓ ｔ ｅ ｒ ｉ ｎ ｇ／ ／ Ｐ ｒ ｏ ｃｅ ｅｄｉ ｎ ｇｓ ｏ ｆ ｔ ｈ ｅＡＣＭ ＳＩ ＧＫ Ｄ Ｄ Ｉｎ ｔ ｅｒ ｎ ａ？ｔ ｉ ｏ ｎ ａｌ Ｃｏ ｎ ｆｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ Ｋｎ ｏ ｗｌ ｅ ｄ ｇ ｅＤ ｉ ｓ ｃ ｏｖ ｅ ｒｙ ａ ｎ ｄ Ｄａ ｔ ａＭｉ ｎ ｉ ｎ ｇ．Ｈａ ｌ ｉ ｆａ ｘ ，Ｃ ａｎ ａ ｄ ａ ， ２ ０ １ ７ ：５ ５ ５ － ５ ６ ４［ ３ ０ ］Ｄｉ ｅ ｆｅ ｎ ｄ ｅ ｒ ｆｅ ｒ ＣＬ ？ Ｄｏ ａ ｎ ＲＡ ， Ｓａ ｌ ｏ ｗ ｅ ｙ Ｃ．Ｔ ｈ ｅ ｑ ｕ ａ ｎ ｔ ｉ ｔ ａ ｔ ｉ ｖｅｒｅ ａ ｓ ｏ ｎ ｉ ｎｇｐ ｒ ｏ ｇｒ ａ ｍａｔＨ ｏ ｌ ｌ ｉ ｎ ｓ Ｕｎ ｉ ｖ ｅ ｒ ｓｉ ｔｙ ．Ｐｅ ｅｒ Ｒｅｖ ｉ ｅｗ，２ ０ ０ ４ ， ６ （ ４ ） ： １ ３［ ３ １ ］ Ｌｅｓ ｋ ｏ ｖ ｅｃ Ｊ ． Ｋ ｌ ｅ ｉ ｎ ｂ ｅ ｒ ｇ Ｊ ， Ｆａ ｌ ｏ ｕ ｔ ｓ ｏ ｓ Ｃ．Ｇｒ ａ ｐ ｈｓｏ ｖ ｅｒ ｔ ｉ ｍｅ ：Ｄ ｅｎ ｓ ｉ ｆ ｉ ｃａ ｔｉｏ ｎｌ ａ ｗ ｓ ，ｓ ｈ ｒ ｉ ｎ ｋ ｉ ｎ ｇｄ ｉ ａ ｍｅｔ ｅ ｒ ｓａ ｎ ｄｐ ｏ ｓ ｓｉ ｂ ｌ ｅｅ ｘｐ ｌ ａｎａ ｔｉ ｏ ｎｓ ／ ／ Ｐｒ ｏｃ ｅｅ ｄ ｉ ｎｇ ｓｏｆ ｔ ｈ ｅＥｌ ｅ ｖ ｅｎ ｔ ｈＡＣＭＳＩ Ｇ Ｋ Ｄ ＤＩ ｎ ｔｅ ｒ ｎ ａ ｔｉ ｏ ｎａ ｌ Ｃｏ ｎ ｆ ｅ ｒ ｅｎ ｃ ｅｏ ｎＫ ｎ ｏｗｌ ｅ ｄ ｇ ｅＤ ｉ ｓｃ ｏｖ ｅｒ ｙｉ ｎ Ｄａ ｔａＭｉ ｎ ｉ ｎ ｇ． Ｃｈ ｉ ｃａｇｏ ， ＵＳ Ａ ， ２ ０ ０ ５ ： １ ７ ７ －１ ８ ７［ ３ ２ ］Ｌｅ ｓ ｋｏ ｖ ｅｃ Ｊ ，Ｌａｎ ｇ ＫＪ ，Ｄａ ｓｇ ｕ ｐ ｔａ Ａ ， ｅ ｔ ａｌ ．Ｃ ｏｍｍ ｕ ｎ ｉ ｔ ｙｓ ｔ ｒ ｕ ｃｔ ｕ ｒｅ ｉ ｎ ｌ ａ ｒ ｇ ｅ ｎｅ ｔｗ ｏ ｒ ｋ ｓ： Ｎ ａ ｔ ｕ ｒａ ｌ ｃｌ ｕ ｓｔ ｅ ｒｓｉ ｚ ｅｓ ａ ｎ ｄｔ ｈ ｅａ ｂ ｓ ｅｎ ｃ ｅｏ ｆ ｌ ａ ｒｇ ｅ ｗｅ ｌ ｌ－ｄ ｅ ｆｉ ｎ ｅｄ ｃｌ ｕ ｓｔ ｅ ｒ ｓ ． Ｉ ｎ ｔ ｅ ｒ ｎ ｅ ｔＭａ ｔ ｈ ｅｍａ ｔｉ ｃｓ ，２ ０ ０ ９ ， ６ （ １） ： ２ ９－１ ２ ３［ ３ ３ ］Ｃｅ ｎ ｔ ｏ ｌ ａＤ ．Ｔ ｈ ｅ ｓ ｏ ｃ ｉ ａ ｌｏ ｒ ｉ ｇ ｉ ｎ ｓｏ ｆ ｎ ｅ ｔ ｗｏ ｒｋ ｓ ａ ｎｄ ｄ ｉｆｆ ｕ ｓ ｉｏ ｎ．Ａ ｍ ｅｒ ｉ ｃ ａｎ Ｊｏ ｕ ｒ ｎａ ｌ ｏ ｆ Ｓｏ ｃ ｉｏ ｌ ｏ ｇｙ ， ２ ０ １ ５ ， １ ２ ０ （ ５ ） ： １ ２ ９ ５－１ ３ ３ ８Ｚ ＨＡ Ｏ Ｙ ｕ － Ｈａ ｉ ． Ｐ ｈ ． Ｄ．， ｐ ｒｏ ｆｅ ｓ ｓ ｏ ｒ．Ｈｉ ｓｍａｊ ｏ ｒｒ ｅ ｓ ｅ ａ ｒｃ ｈｉ ｎ ｔ ｅ ｒｅ ｓ ｔ ｉ ｓ ｄａ ｔ ａ ｍ ｉ ｎ ｉ ｎｇ．ＷＡ Ｎ Ｇ Ｇｕ ｏ － Ｒｅ ｎ ． Ｐｈ． Ｄ． ，ｐ ｒｏ ｆｅ ｓｓ ｏｒ ．Ｈ ｉ ｓｍ ａｊ ｏｒ ｒｅ ｓ ｅａ ｒ ｃ ｈｉ ｎ ｔ ｅ ｒｅ ｓ ｔ ｉｓ ｄａ ｔ ａ ｂａ ｓ ｅ．ＷＥＩ Ｌ ｉｕ － Ｇ ｕｏ ，Ｍ． Ｓ． ｃ ａｎｄｉ ｄ ａ ｔ ｅ． Ｈ ｉｓｍａｉ ｎ ｒｅ ｓｅ ａ ｒｃ ｈ ｉ ｎ ｔ ｅ ｒｅ ｓｔｉ ｓ ｂ ｉ ｇｄ ａ ｔａ．２ １ １ ８ 计算机学报 ２ ０ ２ ０ 年Ｂａｃｋｇｒｏ ｕｎｄＤｉ ｓ ｔ ｒｉ ｂｕ ｔ ｅ ｄ ｉ ｔ ｅ ｒａ ｔ ｉ ｖｅ ｃ ｏｍｐｕ ｔ ｉ ｎ ｇｉｓｏ ｎｅ ｏ ｆ ｔ ｈ ｅ ｍａ ｉｎ ｓ ｔ ｒｅ ａｍｔ ｅ ｃ ｈｎｏ ｌ ｏ ｇｉ ｅ ｓｉ ｎ ｔ ｈ ｅ ｆｉ ｅ ｌ ｄ ｏ ｆ ｂ ｉ ｇ ｄ ａ ｔ ａ ｐ ｒｏ ｃ ｅ ｓｓ ｉｎ ｇ ａ ｎ ｄ ａｎ ａｌｙ ｓ ｉ ｓ．Ｔｈ ｅ ｆ ａｕ ｌ ｔ ｔ ｏ ｌｅ ｒａ ｎ ｃ ｅ ｍｅ ｃｈ ａ ｎ ｉｓ ｍｉｓａ ｎｅ ｃ ｅ ｓ ｓａ ｒ ｙｇ ｕ ａ ｒａ ｎｔ ｅ ｅ ｆ ｏ ｒｈ ｉｇ ｈ ａｖａ ｉｌ ａ ｂ ｉｌｉ ｔ ｙ ｏｆ ｄｉ ｓｔ ｒ ｉ ｂ ｕｔ ｅ ｄ ｓ ｙ ｓｔ ｅｍｓ ．Ａｌｔ ｈ ｏｕ ｇ ｈ ｔｈ ｅ ｆ ａ ｕ ｌ ｔｔ ｏｌ ｅ ｒａｎｃ ｅ ｍｅ ｃ ｈａ ｎｉ ｓｍ ｏｆ ｅ ｘ ｉ ｓ ｔ ｉ ｎ ｇｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕｔ ｅ ｄ ｓｙ ｓ ｔ ｅｍｓ ｐ ｅ ｒ ｆｏ ｒｍｓｗｅ ｌ ｌｉ ｎ ｈｉ ｇ ｈａ ｖ ａｉｌ ａ ｂ ｉ ｌｉｔ ｙ ，ｉｔｉ ｇｎ ｏ ｒｅ ｓｔ ｈ ｅ ｐｒ ｏｂ ｌ ｅｍｏｆｆ ａ ｕ ｌｔｔｏ ｌｅ ｒａｎｃ ｅｅ ｆｆ ｉ ｃｉ ｅｎｃ ｙ ｆｏ ｒｉ ｔ ｅｒ ａ ｔ ｉ ｖ ｅ ｃｏｍｐｕ ｔｉ ｎ ｇ． Ｔｈｅ ｎｅｗｇ ｅ ｎｅ ｒａ ｔｉ ｏ ｎｏｆ ｂ ｉ ｇ ｄ ａ ｔ ａ ｃｏ ｍｐ ｕ ｔ ｉ ｎｇ ｓｙ ｓ ｔ ｅｍＡ ｐａ ｃ ｈｅ Ｆ ｌｉ ｎ ｋ ｍａ ｉ ｎ ｌ ｙ ｕｓ ｅ ｓｔ ｈ ｅ“ｄ ｉ ｓ ｔ ｒｉ ｂ ｕｔ ｅ ｄｓ ｎａ ｐ ｓ ｈｏ ｔ” ｃ ｈ ｅ ｃ ｋｐ ｏ ｉ ｎ ｔｍｅ ｃ ｈ ａ ｎ ｉ ｓｍｔｏ ｐ ｅ ｒ ｆｏｒ ｍｆ ａ ｕ ｌｔ ｔ ｏ ｌ ｅ ｒａ ｎｃ ｅ ｗｈ ｅ ｎｐ ｅ ｒｆ ｏｒ ｍｉ ｎ ｇｓ ｔ ｒｅ ａｍｐ ｒｏｃ ｅ ｓ ｓ ｉ ｎ ｇｔ ａ ｓ ｋ ｓ． Ｆｏ ｒｉ ｔ ｅ ｒａ ｔ ｉ ｖｅ ａ ｎ ａ ｌ ｙｓ ｉ ｓ ｏｆ ｍａ ｓ ｓｉ ｖｅ ｄａ ｔ ａ ？ ｃ ｈｅ ｃ ｋｐｏｉ ｎ ｔ ｓ ａ ｄｄ ｕｎ ｎ ｅｃ ｅ ｓｓ ａ ｒ ｙｄｅ ｌ ａ ｙ．Ｗ ｈ ｅ ｎｅ ｘｅ ｃ ｕ ｔ ｉ ｎ ｇａ ｂａ ｔ ｃ ｈ ｐｒｏ ｃ ｅ ｓｓ ｉ ｎｇ ｔ ａ ｓｋ ，ｗｈ ｅ ｎｔ ｈ ｅｃｏ ｍｐ ｕｔ ｉ ｎｇ ｎ ｏｄ ｅ ｆ ａ ｉ ｌ ｓ ａ ｎｄｔ ｈ ｅ ｔ ａ ｓｋ ｆａ ｉ ｌｓ，ｔ ｈ ｅ ｔ ａ ｓｋ ｉ ｓ ｅ ｘｅ ｃ ｕ ｔ ｅ ｄｆ ｒｏｍｔ ｈｅ ｂ ｅ ｇｉｎｎ ｉ ｎｇｔ ｏ ｃ ｏｍｐｌｅｔ ｅ ｔｈ ｅ ｆ ａ ｕｌｔ ｔｏ ｌ ｅ ｒａｎ ｃ ｅ． Ｔｈ ｉｓ ｆａ ｕｌｔｔ ｏ ｌｅ ｒａｎ ｃ ｅ ｍｅ ｔ ｈｏ ｄ ｂｒ ｉ ｎ ｇｓ ａ ｌ ｏｔ ｏ ｆ ｏｖ ｅ ｒｈｅ ａ ｄ ．Ｂａｓ ｅｄ ｏｎ ｔ ｈｅ ｃ ｈａ ｒ ａｃ ｔ ｅ ｒｉ ｓ ｔｉ ｃ ｓ ｏ ｆ Ｆ ｌ ｉｎ ｋ，ｓ ａ ｒ ｃｈ ｉ ｔｅ ｃｔ ｕｒ ｅ ａｎ ｄｉｔ ｅ ｒａ ｔ ｉｖ ｅ ｐｒｏ ｃｅ ｓ ｓｉｎｇ ，ｔｈｉ ｓ ｐａ ｐ ｅ ｒｐ ｒｏｐｏｓ ｅ ｓａｎ ｏ ｐ ｔｉｍｉｓ ｔｉｃｉｔｅ ｒａ ｔｉ ｖ ｅｆ ａ ｕ ｌｔ ｔ ｏｌ ｅ ｒａｎ ｃ ｅ ｍｅ ｃ ｈａｎ ｉ ｓｍ ｂａ ｓ ｅ ｄ ｏｎ ｃ ｏｍｐ ｅ ｎｓ ａ ｔ ｉ ｏ ｎｆ ｕ ｎｃ ｔ ｉ ｏ ｎ ｓａｎｄａ ｐ ｅｓ ｓｉ ｍｉ ｓ ｔ ｉ ｃ ｉ ｔ ｅ ｒａ ｔ ｉ ｖｅ ｆ ａｕ ｌｔ ｔ ｏｌ ｅ ｒａｎｃ ｅｍｅ ｃ ｈａ ｎ ｉ ｓ ｍｂ ａｓ ｅ ｄ ｏ ｎｈ ｅａ ｄ－ｔ ｏ－ ｅ ｎｄ ｃ ｈ ｅ ｃ ｋ ｐｏｉ ｎｔ ｓ， ｗｈ ｉ ｃ ｈ ｒｅ ｄ ｕｃ ｅ ｓ ｆａ ｕｌ ｔ ｒｅ ｃ ｏ ｖｅ ｒｙ ｔｉ ｍｅａ ｎｄ ｆ ａ ｕｌｔ ｔ ｏｌｅ ｒａ ｎ ｃ ｅ ｏｖｅ ｒ ｈｅ ａ ｄ ａｎｄ ｉｍｐ ｒｏｖｅ ｓ ｉ ｔ ｅ ｒａ ｔ ｉ ｖｅ ｃ ａ ｌｃ ｕ ｌａ ｔｉ ｏ ｎｅ ｆ ｆ ｅ ｃ ｔ ｉ ｖｅ ｎｅ ｓ ｓ ．Ｔ ｈ ｅｅ ｘ ｐ ｅ ｒｉ ｍｅ ｎｔ ａ ｌｒ ｅｓ ｕ ｌｔ ｓ ｐｒｏ ｖｅ ｔ ｈ ｅｅ ｆ ｆ ｉ ｃ ｉ ｅｎ ｃ ｙｏｆ ｔ ｈ ｅ ｉ ｔ ｅ ｒａ ｔ ｉ ｖ ｅ ｆ ａ ｕ ｌ ｔ－ｔ ｏ ｌ ｅ ｒ ａ ｎ ｔ ｏ ｐ ｔｉｍｉｚ ａ ｔｉ ｏｎ ｔ ｅ ｃ ｈ ｎｉ ｑｕ ｅ ｐｒ ｏｐ ｏｓ ｅ ｄｉ ｎ ｔ ｈ ｉ ｓ ｐ ａ ｐｅ ｒ．Ｔｈ ｉ ｓｗ ｏｒ ｋ ｗａ ｓ ｓ ｕｐ ｐｏ ｒ ｔ ｅｄ ｂｙ ｔ ｈｅ Ｎａ ｔ ｉ ｏ ｎａ ｌ Ｋ ｅｙ Ｒｅ ｓｅ ａ ｒ ｃ ｈａ ｎｄ Ｄｅ ｖｅ ｌ ｏｐｍｅ ｎ ｔＰｒ ｏｇ ｒａｍ ｏｆ Ｃ ｈｉ ｎａ （ ２ ０ １ ８ Ｙ ＦＢ １ ０ ０ ４ ４ ０２ ）ａｎ ｄｔ ｈ ｅＧｅｎｅ ｒａ ｌＰ ｒｏｇ ｒａｍｏｆｔ ｈ ｅＮａ ｔｉ ｏｎ ａ ｌＮ ａ ｔ ｕｒ ａｌＳｃ ｉ ｅ ｎ ｃ ｅＦｏ ｕｎ ｄａ ｔｉｏｎ ｏｆ Ｃｈ ｉ ｎａ （ ６ １ ７ ７ ２ １ ２ ４ ） ． |
| [返回] |
下一篇：理性公平的秘密共享方案_刘海