迁移工作流容错执行模型及其实现方法研究

摘要

迁移工作流是一类基于移动agent计算模式的工作流管理技术，它以移动agent为范型构建一个或多个任务执行主体（称作迁移实例），以工作位置映射工作流参与者的网络节点和服务，其中，网络节点表示迁移实例的工作场所，位置服务包括运行时服务和工作流服务两部分。迁移实例可以在某个工作位置上利用本地资源和服务执行一项或多项任务，并在必要时携带任务说明书和当前执行结果迁移到另一个能满足其要求的新工作位置上继续工作。为同一个工作流创建的多个迁移实例可以协同工作，以满足并行业务过程管理的需要。 因为迁移实例运行在一个跨机构的异构网络环境中，所以其任务执行过程容易受不确定性因素的影响，例如主机故障、链路故障、通信故障、服务程序和服务资源故障等。上述不确定因素不仅会干扰迁移工作流的正常执行，而且可能导致迁移实例夭折，甚至迁移工作流失败，因此，迁移实例容错是保证迁移工作流可达性、正确性和可靠性不可或缺的必要机制。迁移实例容错主要包括三个方面：执行容错、通信容错和状态容错。 ·执行容错；执行容错是指工作流任务能够在所有工作位置上都被迁移实例可靠执行。在迁移工作流模型中，工作流任务通过迁移实例在工作位置之间的连续迁移和就地利用服务完成，工作位置不仅要为迁移实例提供运行场所，而且要为迁移实例提供可靠的工作流服务，任何主机物理故障或服务逻辑故障都会干扰迁移实例任务的正常完成。特别是对于某些要求可靠性较高的长事务任务（如订票、付款）来说，因为涉及到对重要数据库的访问，需要保证操作的事务属性，对迁移实例的执行过程，需要提供必要的容错保障机制。 ·通信容错：通信容错是指迁移实例之间的通信信件能够被可靠地发送和递交。在迁移工作流模型中，通信是迁移实例之间实现协作的基础，只有保证通信信件能够被可靠地发送和递交，才能保证迁移实例协作的成功。存在两方面的原因会导致迁移实例间的通信失败：（1）通信链路物理故障，导致信件不能发出；（2）迁移实例移动，导致信件不能可靠递交，即当信件到达目标主机时，接收方迁移实例已经离开。对于通信链路物理故障，可以通过备份链路重传信件。对于因迁移实例移动而导致的信件递交失败，可以通过设计合理的迁移实例位置追踪和信件转发机制实现容错。 ·状态容错：状态容错是指迁移实例的异常状态能够被及时捕获和恢复。迁移实例的状态包括正常执行状态和异常状态，异常状态主要是指迁移实例因某些物理故障或受到安全攻击而变得不可追踪或不可用。因为并行的多个业务子过程之间通常具有数据和时间关联关系，所以，执行同一工作流的多个迁移实例之间也具有特定的行为依赖关系。如果某个迁移实例的状态出现异常，则可能会引发其它迁移实例的状态异常或执行阻塞。因此，状态容错机制不仅要能够及时地捕获单个迁移实例的异常状态并使其恢复，而且要能够分析状态异常的波及范围，有效限制异常状态的蔓延。 本文在国家自然科学基金项目的资助下，以迁移工作流系统模型为基础，吸收其他领域的研究成果，重点研究了迁移工作流的容错执行模型及其实现方法，包括迁移实例的容错执行方法、迁移实例间可靠通信方法、多迁移实例的协同监控和失败协调恢复方法等，并通过具体的应用案例对上述研究成果进行了分析和验证。本文的主要工作包括： 1.迁移工作流容错执行模型研究 为了实现迁移工作流的可靠执行，本文建立了系统级容错执行模型。模型从服务层、实例层、协作层三个层次描述了系统存在的故障，及相应的容错实现机制。文中给出了容错执行模型的框架结构，设计了迁移工作流实验用例，建立了迁移工作流容错执行环境。 2.迁移实例容错执行模型及其实现方法研究。 为了实现迁移实例的容错执行，本文将工作流任务区分两种不同的类型：时间关键任务和业务关键任务。时间关键任务特指那些对响应时间要求较高的短事务任务，如实时数据处理、在线软件更新等。业务关键任务特指对执行可靠性要求较高的长事务任务，如订票、购物、转帐等。由于业务关键任务通常涉及数据库的修改，因此需要保证执行的“只一次”性和事务属性。本文针对执行业务关键任务的迁移实例，重点研究了一类基于空间复制的容错执行阶段构建模型，文中给出了动态阶段的概念，定义了动态优先级，设计实现了阶段工作位置选取策略和动态阶段构建算法。性能和效率分析表明，该模型能够减少阶段提交的时间和通信开销，提高容错执行的效率。 3.迁移实例容错通信模型及其实现方法研究。 为了实现迁移实例间的通信容错，本文针对通信过程中因迁移实例移动而导致的信件不能可靠递交故障，重点研究了一类基于服务域划分和“邮局-邮箱”原理的迁移实例可靠通信模型，文中给出了通信模型的定义及体系结构，设计了迁移实例的命名和寻址方式，给出了主要的通信算法，并对模型特性和通信效率进行了分析。实验表明，该通信模型模拟现实世界中的信件投递过程，简单易实施，具有较好的可靠性和效率。 4.迁移实例状态监控模型及其协调恢复方法研究。 为了实现迁移实例状态容错，本文针对因某个迁移实例状态异常而导致的其它迁移实例状态不一致或执行阻塞故障，重点研究了一类针对多主体协同并发过程的协同监控模型及其相应的检查点算法，文中给出了协同监控模型定义，设计了监控者管理算法，包括监控者创建、移动与退出，并描述了监控信息的获取与处理过程以及基于监控的检查点过程。性能和效率分析表明，监控模型能够实施对迁移实例有效的监控，通过监控者的协调，实现故障恢复后全局一致性状态。 本文工作的创新点主要体现在： 1.针对工作位置故障导致的迁移实例执行过程受阻问题，提出了一种基于空间复制的容错执行阶段构建模型。该模型有效降低了空间复制法的时间和通信开销，提高了迁移实例执行容错方法的可用性。 该模型通过合理规划迁移实例的任务执行阶段，避免了迁移实例执行过程中对工作位置的不必要重访，降低了总体运行时间；通过工作位置动态服务优先级的设定和计算，使得工作位置在不同时刻相对于不同的迁移实例具有不同的服务优先级，因而能够更加准确地反映工作位置作为迁移实例运行时环境的适合程度；通过尽可能选取上一阶段使用过的工作位置的策略设定，使得迁移实例既能够选取到执行环境中最优的工作位置，又减少了阶段提交的通信开销。 2.针对通信链路故障和迁移实例移动性导致的通信失败问题，提出了一种基于服务域划分的迁移实例容错通信模型。该模型具有简单易用、高可靠性和高效率的特点，并且对系统规模扩大具有良好的适应性。 该模型借助业务关联度的概念把工作位置划分成不同的服务域，在服务域上设置邮局，在邮局中为本域创建和外域迁来的迁移实例设置信箱，并通过熟人地址簿建立地址缓存机制，以便地址查询。每个迁移实例都有两个信箱：源信箱和活动信箱。活动信箱由迁移实例随身携带，以方便信件的直接投递和提取；源信箱固定存放在迁移实例的创建地邮局，用以支持信件直接投递失败时的信件转发。该模型具有以下优点：（1）双信箱机制。双信箱机制可以有效避免迁移过程中发生的信件丢失，并保证信件的“仅一次（exactly-once）”提交；（2）熟人地址簿机制。熟人地址簿机制支持高效透明的迁移实例寻址，不仅可以有效降低通信地址查询时间，而且可以减轻迁移实例通信对创建地的依赖，降低系统在迁移实例注册、注销等方面的开销，增强系统健壮性和提高工作效率。 3.针对迁移实例异常状态捕获与恢复问题，提出了一种层次型协同监控模型（HCM3）。该模型可以有效捕获和处理迁移实例的状态信息，避免迁移实例夭折造成的工作流执行失败。 该模型将迁移实例状态监控看作一个多监控者的协同工作过程，多个监控者协同监控执行同一工作流的所有迁移实例，并通过监控者之间的协调实现不同层次异常状态的捕获、处理和恢复。该模型具有以下特点：（1）监控层次性。监控者之间具有层次关系，并与迁移实例之间的层次关系相对应，不但可以针对不同的迁移实例定制监控内容和监控手段，而且能够诊断并处理在迁移实例层和过程层发生的异常情况，协调不同层次间的监控者行为；（2）监控并发性。监控可以在不同层次上同时进行，通过监控者之间的协调达到状态的一致，在一定程度上解决了集中式监控的单点瓶颈问题，提高了监控效率；（3）监控可靠性与监控效率。模型在多个监控者之间分散监控失败风险，同集中式监控相比具有较高的可靠性，同时对每个迁移实例仅分配一个监控者，避免了过多冗余监控者带来的额外开销。 由于迁移工作流的特殊性，也由于迁移工作流管理尚是一个刚刚开始的研究新领域，因此，无论是理论研究还是应用方面都还远未成熟。本文进一步的研究工作包括： 1.协同监控模型的进一步完善。本文关于迁移工作流的协同监控模型还处于概念验证阶段，一方面系统对许多参数做了假定，如仅设定有限种类的故障类型，而且不考虑监控者的失败情况等；另一方面实验案例较单一，没有结合系统做大量深入的定量分析。下一步的工作将进一步考虑环境的复杂性和动态性，完善算法，并在已有的定性分析的基础上，对整个系统的各方面性能做深入的定量分析，以获得客观的评判标准。 2.面向目标的任务分解和迁移实例执行机制。本文的研究内容基于面向过程的迁移工作流方法进行，因为业务过程分解和迁移实例执行阶段的划分需要事先对业务流程进行明确的定义，所以要求系统设计者掌握完备的工作流知识。对于跨机构、大规模协同业务过程，要求设计者掌握完备的工作流知识是十分困难的。下一步将研究目标驱动的迁移工作流机制，以减少系统性能对设计者先验知识的依赖，提高系统的易用性。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究的背景和意义

1.2国内外研究现状

1.2.1工作流领域研究进展

1.2.2移动agent概念及其在工作流中的应用

1.2.3可靠性与容错问题研究

1.2.4迁移工作流研究

1.3课题的来源及主要研究内容

1.3.1课题的来源

1.3.2本文的工作与创新

1.4本文的组织

第2章迁移工作流容错执行模型

2.1概述

2.2迁移工作流模型

2.3迁移工作流管理系统框架

2.3.1工作位置

2.3.2迁移工作流管理引擎

2.3.3迁移实例

2.3.4迁移工作流执行过程

2.4迁移工作流容错执行模型

2.4.1故障分析

2.4.2迁移工作流容错执行模型

2.5迁移工作流实验用例设计

2.5.1流程设计

2.5.2容错运行环境

2.6本章小结

第3章迁移实例容错通信模型及其实现方法

3.1概述

3.2基于服务域划分的迁移实例通信模型

3.2.1模型描述

3.2.2迁移实例的命名与寻址

3.3通信算法

3.3.1信件发送算法

3.3.2信件转发算法

3.3.3信件接收算法

3.3.4熟人地址薄管理算法

3.3.5信件投递过程描述

3.4模型特性及效率分析

3.4.1模型特性分析

3.4.2通信效率分析

3.4.3实验结果分析

3.5本章小结

第4章迁移实例容错执行模型及其实现方法

4.1概述

4.2迁移实例容错执行过程

4.3动态阶段构建模型

4.3.1动态阶段定义

4.3.2工作位置在迁移实例一跳内能够完成的任务

4.3.3工作位置的动态优先级

4.3.4阶段wp的选取

4.3.5动态阶段构建算法

4.4性能分析

4.4.1特性分析

4.4.2实验结果

4.5本章小结

第5章多迁移实例状态监控模型及其协调恢复方法

5.1概述

5.2研究基础

5.2.1迁移实例执行约束

5.2.2相关研究

5.3迁移工作流协同监控模型HCM3

5.3.1模型定义

5.3.2协同监控任务的分配

5.3.3监控者的管理

5.3.4监控信息的获取与处理

5.4基于层次监控模型的协调检查点过程

5.4.1阶段1

5.4.2阶段2

5.4.3阶段3

5.4.4 CPN的结构

5.4.5协调恢复过程

5.5模型特性分析

5.6性能评价

5.7本章小结

第6章总结与展望

6.1本文总结

6.2研究展望

参考文献

致谢

攻读学位期间发表的学术论文目录

外文论文(一)

外文论文(二)

在读期间参与科研项目情况