分布式系统中的服务组合修复与自主规范

### 分布式系统中的服务组合修复与自主规范 #### 1. 引言与动机 面向服务的计算（SOC）推动了松散耦合和分布式实体（即服务）的重用，并将它们自动组合成增值应用程序。在SOC中，一个关键问题是开发支持自动组合的模型和算法，从可用服务和组合需求中生成业务流程，这在Web服务的背景下被称为Web服务组合（WSC）问题。 AI规划越来越多地应用于WSC，因为它支持从不完整指定的需求进行自动组合。然而，在现实开放的世界中，变化频繁发生。服务可能随时不可预测地出现或消失，用户需求或业务目标也可能随时间改变。这就需要对原有的组合计划进行调整。 解决计划适应变化的方法主要有两种：一是从当前执行状态进行全面重新规划；二是尝试修复计划，尽可能重用原计划。计划修复是应对变化世界中WSC的有价值解决方案，原因如下： - 可以保留部分执行计划的效果，避免回滚。 - 实践中，计划修复通常比重新规划更高效，因为大部分计划在变化后仍然有效。 - 尽可能保持对未执行服务的承诺，这在业务或安全方面可能是必要的。 - 最终用户可能更喜欢修复后的相似计划，而非重新规划的差异较大的计划。 本文基于规划图提出解决方案。规划图能紧凑表示服务间的关系，即使有变化，部分规划图仍然有效。通过识别新的组合问题，移除消失的服务，添加新目标，得到部分规划图，然后使用修复算法“重新生长”该图，快速搜索可行解决方案，同时最大程度重用部分图中的内容。 #### 2. 形式化建模 ##### 2.1 语义模型 为了实现从用户需求自动发现和组合服务，需要为服务关联某种形式的语义。基于共享本体的语义可用于提供全自动组合，服务可以传达两种语义信息： - 与消息一起传输的数据相关的语义信息。例如，提供酒店房间的服务，其输入可能包括旅行城市、日期和用户名等语义信息，输出为酒店登记信息。 - 与服务实现的功能或能力相关的语义信息。可以将服务的能力视为特定输出。 本文使用数据语义结构（DSS）来支持语义信息，定义如下： - **定义1**：数据语义结构（DSS）D是一个二元组 (D, RD)，其中D是表示某些数据语义的概念集，RD = {RD_i : 2^D → 2^D} 是概念之间的关系集。当存在RD_i ∈ RD，使得RD_i(D1) = D2时，我们说D2可以从D1得到，记为D1 ;RD_i D2 或 简单记为D1 ; D2。 ##### 2.2 服务和服务组合模型 - **定义2**：给定一个DSS (D, RD)，Web服务w是一个元组 (in, out)，其中in ⊆ D 表示w的输入参数，out ⊆ D 表示w的输出参数。in^- ⊆ in 表示被服务消耗的输入参数集。 - **数据适应服务**：对于每个RD_i ∈ RD，当D1 ;RD_i D2 时，定义一个数据适应服务w_Ri = (D1, D2)，它可以自动实现为服务或可重用的独立代码。 - **定义3**：假设参数集DW = {d1, d2, ..., dk} 中的每个参数都是一组Web服务W = {w1, w2, ..., wm} 中某个服务的输出参数。如果 {d1, d2, ..., dk} ; {dn}，且dn ∈ in(wn)，则W中的每个服务都可以连接到wn，记为wi ▷ wn。 - **定义4**：给定一个DSS (D, RD)，组合需求是一个二元组 (D_in^U, D_out^U)，其中D_in^U ⊆ D 是提供的（或输入）参数集，D_out^U ⊆ D 是所需的（或输出）参数集。 - **定义5**：一个组合需求 (D_in^U, D_out^U) 由一组连接的Web服务W = {w1, ..., wn} 满足，当且仅当对于所有i ∈ {1, ..., n}： - 对于所有d ∈ in(wi)，D_in^U ∪ out(w1) ∪ ... ∪ out(wi - 1) ; d。 - 对于所有d ∈ D_out^U，D_in^U ∪ out(w1) ∪ ... ∪ out(wn) ; d。 ##### 2.3 模型与语言 Web服务的接口在WSDL文件中描述，DSS是可以用OWL描述内容的子类。WSDL可以扩展以引用OWL语义注释，SAWSDL标准也可用于此。 一些服务输入参数是信息性的，可以无限制使用；而其他输入参数是可消耗的，只能使用一次。可以扩展OWL的rdf:property来描述参数的可消耗性属性。 本文假设服务是无状态的，每个服务只有一个操作。如果服务有多个操作，可以使用索引进行处理。 ##### 2.4 作为规划的Web服务组合 AI规划已成功应用于解决WSC问题，通过将其编码为规划问题： - **定义6**：规划问题是一个三元组P = ((S, A, γ), s0, g)，其中： - S是状态集，状态s是有限命题符号集L = {p1, ..., pn} 的子集。 - A是动作集，动作a是一个三元组 (precond, effects^-, effects⁺)，其中precond(a) 表示a的前提条件，effects^-(a) 和 effects⁺(a) 分别表示a的负效应和正效应，且effects^-(a) ∩ effects⁺(a) = ∅。 - γ是状态转换函数，对于任何状态s，如果precond(a) ⊆ s，则γ(s, a) = (s - effects^-(a)) ∪ effects⁺(a)。 - s0 ∈ S 是初始状态。 - g ⊆ L 是一组命题，称为目标命题（或简称为目标）。 WSC问题可以映射到规划问题： - 每个服务w映射到同名的动作，服务的输入参数映射到动作的前提条件，输出参数映射到动作的正效应，可消耗参数映射到负效应。 - 组合需求的输入参数映射到初始状态s0。 - 组合需求的输出参数映射到目标g。 本文使用基于规划图的算法，相关定义如下： - **定义7**：在规划图中，分层计划是一组动作集的序列 ⟨π1, π2, ..., πn⟩，其中每个πi (i = 1, ..., n) 是独立的。π1适用于s0，当i = 2, ..., n时，πi适用于γ(si - 2, πi - 1)，且g ⊆ γ(...(γ(γ(s0, π1), π2)...πn)。 - **定义8**：在规划图中，两个动作a和b独立，当且仅当满足effects^-(a) ∩ [precond(b) ∪ effects⁺(b)] = ∅，且effects^-(b) ∩ [precond(a) ∪ effects⁺(a)] = ∅。一组动作独立当且仅当其中的动作两两独立。 ##### 2.5 示例 为了演示模型和规划算法，给出一个简单的旅行示例。示例中使用的DSS概念包括： - 用户信息uinfo（由用户名uname和用户城市ucity组成） - 出发和返回日期fromdate和todate - 出发和返回城市（或国家）depcity和depcountry（或destcity和destcountry） - 旅行警报travelalert - 航班请求flightreq - 飞机和酒店的登记信息planereg和hotelreg 下面是一个简单的mermaid流程图，展示服务组合的基本流程： ```mermaid graph LR A[输入参数] --> B[服务1] B --> C[服务2] C --> D[输出参数] ``` 表格：服务与规划问题的映射关系 | 服务相关元素 | 规划问题对应元素 | | ---- | ---- | | 服务w | 动作w | | 服务输入参数in(w) | 动作前提条件precond(w) | | 服务输出参数out(w) | 动作正效应effects⁺(w) | | 服务可消耗参数in^-(w) | 动作负效应effects^-(w) | | 组合需求输入参数D_in^U | 初始状态s0 | | 组合需求输出参数D_out^U | 目标g | #### 3. 服务组合中的变化模型 在现实世界中，服务组合面临着多种变化，这些变化会影响原有的组合计划。服务可能会因为各种原因（如故障、用户移动导致服务超出范围等）不可预测地出现或消失，同时，用户需求或业务目标也可能随时间发生改变。 服务消失时，原计划需要进行调整，因为某些服务的缺失可能导致部分目标无法实现。而用户需求或业务目标的变化，例如在旅行到达目的地后想要增加观光功能，也要求对服务组合进行相应的修改。 #### 4. 重新规划与修复的评估标准 为了衡量重新规划和修复服务组合计划的效果，需要建立相应的评估标准。 重新规划是从当前执行状态开始进行全面的规划，它会生成一个全新的计划来满足变化后的需求。而计划修复则是尝试在原计划的基础上进行修改，尽可能重用原计划中的部分内容。 评估标准主要考虑以下几个方面： - **效率**：在实践中，计划修复通常比重新规划更高效，因为大部分计划在变化后仍然有效，只需对受影响的部分进行调整。但在最坏情况下，修改现有计划和全面重新规划的效率可能相同。 - **保留效果**：计划修复可以保留部分执行计划的效果，避免将其丢弃并回滚效果，这在某些情况下是非常重要的。 - **服务承诺**：修复计划可以尽可能保持对未执行服务的承诺，这对于业务或安全原因可能是必需的。 - **用户偏好**：最终用户可能更喜欢使用与原计划相似的修复后的计划，而不是差异较大的重新规划后的计划。 #### 5. 修复算法 本文提出的修复算法基于规划图。规划图能够紧凑地表示服务之间的关系，即使发生一些变化，部分规划图仍然有效。 修复算法的步骤如下： 1. **识别新问题**：根据新的可用服务集合和新的目标，确定新的服务组合问题。 2. **构建部分规划图**：从原规划图中移除消失的服务，并在目标层添加新的目标，得到一个部分规划图。 ```mermaid graph LR A[原规划图] --> B[移除消失服务] B --> C[添加新目标] C --> D[部分规划图] ``` 3. **“重新生长”部分规划图**：根据启发式函数，在部分规划图中搜索未实现的目标和不满足的前提条件，并在这些地方“重新生长”规划图，直到找到可行的解决方案。该算法的目标不是构建完整的规划图，而是快速搜索可行解，同时最大程度地重用部分图中的内容。 与重新规划相比，修复算法只构建完整规划图的一部分，直到找到解决方案。当服务组合问题变化不大，原规划图的大部分仍然有效时，修复算法通常比重新规划更快。 #### 6. 实验评估 通过实验对修复算法进行了评估，实验结果表明： - **效率方面**：在服务组合问题变化不大的情况下，修复算法比重新规划更快，因为它可以重用原规划图的大部分内容。 - **解决方案质量**：修复算法得到的解决方案与重新规划得到的解决方案具有相同的质量。 - **局限性**：在某些情况下，修复算法可能无法找到存在的解决方案，而重新规划可以找到。这是修复算法为了提高速度所做出的权衡。 #### 总结 本文围绕分布式系统中的服务组合修复与自主规范展开了深入探讨。首先介绍了面向服务的计算（SOC）和Web服务组合（WSC）问题，指出在现实开放世界中服务和需求的变化对服务组合计划的影响。 为了解决这些问题，提出了基于规划图的计划修复方法。详细阐述了相关的形式化模型，包括语义模型、服务和服务组合模型、模型与语言的关系以及将WSC问题映射为规划问题的方法。 通过实验评估，验证了修复算法在效率和解决方案质量方面的优势，但也指出了其存在的局限性。计划修复在保留部分执行计划效果、保持服务承诺和满足用户偏好等方面具有明显的优势，是应对变化世界中WSC问题的一种有价值的解决方案。 以下是一个总结表格，对比重新规划和修复算法的特点： | 评估指标 | 重新规划 | 修复算法 | | ---- | ---- | ---- | | 效率 | 全面规划，最坏情况下与修复算法效率可能相同，通常效率较低 | 实践中通常更高效，尤其在变化不大时 | | 保留效果 | 丢弃原计划，需重新规划 | 保留部分执行计划效果 | | 服务承诺 | 可能改变对未执行服务的承诺 | 尽可能保持对未执行服务的承诺 | | 用户偏好 | 生成全新计划，可能与原计划差异大 | 生成与原计划相似的计划 | 未来，随着分布式系统和服务组合技术的不断发展，可以进一步研究如何优化修复算法，减少其局限性，提高在各种变化情况下的适应性和性能。同时，可以探索将更多的语义信息和上下文信息融入服务组合中，以更好地满足用户的多样化需求。