【摘 要】
:
以图结构表示的数据广泛存在于各类应用场景,大规模图分析挖掘需要利用分布式图处理系统。图处理算法一般都是迭代的,且执行时间长。在此过程中,系统中节点出现故障是常见的现象。通常,分布式图处理系统利用检查点来处理故障。在正常执行期间,系统需要周期性地写入检查点。特别地,在写入检查点时,一些系统会暂停计算过程,即阻塞式写检查点。显然,这种阻塞式写检查点方法带来了额外的运行时开销。与此不同,非阻塞式写检查点
论文部分内容阅读
以图结构表示的数据广泛存在于各类应用场景,大规模图分析挖掘需要利用分布式图处理系统。图处理算法一般都是迭代的,且执行时间长。在此过程中,系统中节点出现故障是常见的现象。通常,分布式图处理系统利用检查点来处理故障。在正常执行期间,系统需要周期性地写入检查点。特别地,在写入检查点时,一些系统会暂停计算过程,即阻塞式写检查点。显然,这种阻塞式写检查点方法带来了额外的运行时开销。与此不同,非阻塞式写检查点方法容许检查点的写入和计算过程同时进行,有利于降低额外开销。无论是采用阻塞式写检查点方法还是非阻塞式写检查点方法,一旦发生故障,系统读取最新的检查点处并进行回滚,以实现故障恢复。这种恢复方式要求系统在故障发生前周期性地写入检查点,因而被称为悲观恢复。与悲观恢复不同,乐观恢复并不要求系统写入任何检查点,一旦故障发生,该方式会重新载入输入数据,并通过顶点副本或用户定义的补偿函数来恢复丢失顶点的值。一般来说,上述容错技术都能有效地处理故障,然而这些技术也存在局限性。对于非阻塞式写检查点方法而言,其降低了写检查点带来的运行时开销,但可能导致资源竞争,因为检查点的写入和计算是并行的。进一步地,资源竞争会延长执行时间以及检查点的写入时间。而对于乐观恢复而言,其恢复时需重载输入数据并通过重分区来重新构建丢失的顶点和边,这会带来显著的恢复开销。为实现更为高效的容错技术,本文针对上述容错技术存在的局限性进行了研究。首先,本文关注了非阻塞式写检查点方法带来的资源竞争,说明了可通过限制系统最大并发写入的检查点数量来缓解资源竞争,并重点考虑了限制检查点写入数量后存在的积压检查点的选择问题。然后,本文研究了如何利用悲观恢复的检查点来降低乐观恢复的恢复开销,并重点关注了如何降低检查点的运行时开销以及如何选择检查点的写入时机等问题。最后,本文研发了一个原型系统,用于验证研究过程中提出的容错技术的有效性。围绕上述研究内容,本文的主要贡献如下:·提出了采用优先权的非阻塞式写检查点方法,缓解了并发写入多个非阻塞检查点导致的资源竞争。采用优先权的非阻塞式写检查点方法包括排队策略和跳跃机制两项技术。其中,排队策略用于缓解资源竞争,该策略通过用户设定的k值以及一个队列来限制系统最大并发写入的检查点数量。一旦系统并发写入的检查点数量达到k,后续的检查点便会被插入到队列中。进一步地,跳跃机制用于解决队列中积压检查点的选择问题,该机制利用了队列中检查点存在的两个特性:(i)队列中越靠后的检查点保存的状态更新,因而对系统更有益(陈旧度);(ii)队列中写入时间越短的检查点对系统越有益(迟缓度)。在挑选检查点时,该机制优先从队列中挑选出迟缓度最小的检查点,然后再从中挑选出陈旧度最低的检查点。本文的实验表明采用优先权的非阻塞式写检查方法相比于原生的非阻塞式写检查点方法减少了 41.5%的执行时间。·设计了基于混合策略的故障恢复方式,降低了无检查点的乐观恢复方式引起的恢复开销。在乐观恢复的基础上,混合策略要求系统在载入数据后像悲观恢复一样写入一个检查点用以保存各个节点上的顶点和边。特别地,为了避免多次写入检查点带来的高昂开销,混合策略仅会写入一次检查点。此外,为了使检查点尽快可用,该策略要求系统在初始迭代处进行检查点的写入。一旦故障发生,该策略从检查点中而不是输入数据中恢复故节点上丢失的顶点和边,由此达到减少恢复开销的目的。本文的实验表明,基于混合策略的恢复方式相比于悲观恢复和乐观恢复分别减少了 5 0%和39%的执行时间。·实现了采取上述写检查点方法和故障恢复方式的分布式图处理原型系统,并针对典型图处理应用进行了容错技术演示。本文在开源的分布式图处理系统Giraph中完成了上述写检查点方法和故障恢复方式的具体技术实现,并阐述了对应原型系统的设计思路。最终,本文基于连通分量这一典型的图处理应用对本文所提出的容错技术进行了展示。综上所述,本文重点研究了现有容错技术中非阻塞式写检查点方法和乐观恢复中分别存在的资源竞争和高昂恢复开销问题。针对这两个问题,本文分别设计了采用优先权的非阻塞式写检查点方法以及基于混合策略的故障恢复方式,并最终构建了一个原型系统用于对上述写检查点方法和故障恢复方式进行展示。理论分析和实验结果表明本文的研究工作有效地缓解了非阻塞式写检查点方法带来的资源竞争,并降低了乐观恢复方式的恢复开销。
其他文献
超材料是一种新型人造材料,它的主要特点是尺寸远远小于工作波长。超材料的物理性质不依赖于材料的参数,而是取决于人工设计的结构,超材料与电磁波作用时可以产生一些天然材料无法产生的奇特物理现象。超表面是超材料的二维形式,电磁特性和超材料一致。与三维块状的超材料相比超表面是超薄材料,弥补了超材料体积大、不利于集成的缺点,目前被广泛的研究。随着集成系统的飞速发展,对超表面的研究不仅停留在实现单一的频率和功能
多目标跟踪作为无人驾驶领域的一项核心技术,伴随着无人驾驶技术逐渐走进人们的视野,越来越多的研究人员也投身到了多目标跟踪领域进行更深层次的探索。经过长时间的技术积淀,多目标跟踪在交通安全、虚拟现实和无人驾驶等领域已经开始了应用,同时也展现出了巨大的潜力。如今目标跟踪的相关技术已经应用到了实际的生产生活中,为人们的生活带来了便利,提高了人们的生活质量。作为计算机视觉领域的一项基础工作,随着深度学习与卷
随着时间推移和5G技术普及,互联网技术在各行各业中得到推广,这也使得电梯制造商在市场营销过程中逐步引入智能网络的理念。在新社会环境下,商业电梯制造商所面临的业内竞争十分激烈。随着社会经济的不断发展,市场改革的不断深入,也推进了企业市场营销的改进和完善,在竞争激烈的市场环境下,如何提升市场营销的水平已是每个企业发展中重点关注的问题。本次研究结合以上背景内容,梳理国内外学术界现有对于电梯制造商相关的营
随着我国全社会用电量持续不断地增长,输电线路的数量以及覆盖范围也在逐年攀升扩增,绝缘子在输电线路中担任着机械固定、支撑线路以及实现电气绝缘等多种功能,拥有着至关重要的地位,若不及时检测更换故障绝缘子,会导致电力系统短暂奔溃并且造成一定的经济损失。由于输电线路大多处于山大岭等远离城市的地方,若采用巡检人员实地勘察的巡检方式,不仅安全系数低成本还高。目前部分省市已逐步采用无人机拍摄获取巡检图像,但由于
区块链利用拜占庭容错协议以及密码学技术保证节点间数据一致性和不可篡改,在互不信任的多方间实现安全的数据共享,避免了数据伪造、丢失等问题。近年来,区块链广泛应用于各种存证场景并发挥重要作用,如司法鉴证、防伪溯源等。基于区块链的存证应用种类丰富,其过程可概括为证据上传、证据共享以及证据查询三阶段。然而,交易数据信息简单、语义表达能力弱,系统提供的接口单一且系统吞吐低,如何从功能与性能两个维度改进当前基
随着循环神经网络(Recurrent Neural Network,RNN)的应用更加广泛,对抗序列的存在给这类安全攸关应用构成了极大的威胁,其中包含自动驾驶行为预测模型。RNN对抗序列生成是一种提升RNN鲁棒性的方法,然而目前现有的RNN对抗序列生成方法普遍存在着低效的问题。因此,针对上述问题,围绕自动驾驶行为预测模型,提出了一种基于权重自动机(Weighted Finite Automaton
气象条件是人民日常生活和农业生产的重要影响因素,随着各类气象灾害的频繁出现,人民群众的生命财产安全受到了严重威胁。因此,气象监测和预测变得越来越重要。随着传感器技术和通信技术的进一步发展,气象监测从人工记录数据逐步转为自动化记录和管理数据。气象数据的准确监测是开展气象工作的基础,也是准确预测各种突发性灾害天气的依据。目前市场上的气象监测系统,往往存在网络化能力不高、自动化能力欠缺以及设备部署复杂等
序列推荐(Sequential Recommendation)根据用户的历史交互序列预测用户的下一次交互物品,由于序列中复杂的物品依赖以及用户的多方面兴趣,想要准确预测用户的下一次交互的物品十分困难。现有的工作将序列中的每一个交互物品视作一个兴趣单元,并应用了最新的深度学习技术来学习到用户兴趣的统一表示。虽然这些方法在实验中取得了较好的效果,但它们仍存在一些缺陷:1)一个向量不足以表示用户多方面的
呼吸状态可以反映一个人的生理和心理状况,有助于相关疾病的筛查诊断和预后评估。本文对非接触式呼吸状态评估方法展开研究。具体来说,利用视觉传感器进行呼吸信号提取,结合多种信号处理技术对原始信号进行处理,借助机器学习技术对呼吸状态进行分类,并以此为研究框架,搭建了两套非接触式呼吸监控设备,深度研究人体向前走动时识别深呼吸的方法。主要研究内容及创新如下:(1)搭建基于彩色相机和标志物追踪的呼吸监控系统,结
在大数据时代,数据已成为比肩石油的基础性关键战略资源,正在颠覆全球社会的发展模式。数据流通是释放数据价值的关键环节,数据交易系统的建立是促进数据流通的重要举措。数据交易系统帮助卖方数据流入买方,增加数据的流动性,帮助释放数据价值。随着《数据安全法》等相关文件的发布,全社会对于数据安全和数据隐私的需求越来越高,对传统的数据交易系统提出了保护数据隐私等新要求。目前的数据交易系统存在三个问题:1.二次转