用于企业数据中心的虚拟化和整合分析引擎

摘要

一种用于将多个应用整合至一个或多个服务器中的方法和设备。所述方法和设备组织表示与将应用安置于所述一个或多个服务器中有关的偏好的整合约束，并以最大化地满足所述整合约束的方式将所述应用分配至所述一个或多个服务器中。

说明书

相关申请

本申请要求于2010年1月11日提交的美国临时申请号61/293,865的优先权，该美国临时申请的全部公开以参考的方式并入于此。

技术领域

本公开涉及信息技术。更具体地，本公开涉及服务器整合（consolidation）。

背景技术

服务器整合正在变为对许多IT部门来说最高优先级之一，这是由于将一个服务器专用于单个应用的传统方式将使许多服务器在大部分时间内未被充分利用。通过将来自单独机器的工作量聚集至少量服务器中，可以提高资源利用率，因此，这针对企业数据中心节约了功率和空间。随着虚拟化技术最近复苏，现在可以通过在一个物理机器中主控多个虚拟机（VM）来实现服务器整合，每一个虚拟机分别封装一个应用。虚拟化在操作系统与硬件之间提供了抽象层，这使多个VM能够在对系统性能产生最小影响的情况下公平地共享相同物理机。

尽管通过虚拟化而进行的服务器整合带来了许多优势，但是一些优点被由整合引入的所添加的系统管理复杂度抵消。不是管理许多物理机，而是管理员现在面临着在很密集、复杂且共享的环境中集中的大量虚拟机，其中，可以极大地放大硬件故障、人为误差和安全性破坏的影响。例如，需要物理服务器重启的任何情形（例如，硬件故障或系统维护）将影响该物理机中的所有虚拟机而不是单个应用。类似地，多个应用对硬件的增大的共享可以增强对潜在敌对应用揭示敏感信息的可能性，这将危及系统的安全性和保密（privacy）要求。

相应地，需要一种方法和设备来在多种约束下实现服务器整合。

发明内容

公开了一种用于将多个应用整合至一个或多个服务器中的方法。所述方法包括：组织表示与将应用安置（place）于所述一个或多个服务器中有关的偏好的整合约束；以及以最大化地满足所述整合约束的方式将所述应用分配至所述一个或多个服务器中。

还公开了一种用于将多个应用整合至一个或多个服务器中的设备。所述设备包括执行指令的处理器，以便：组织表示与将应用安置于所述一个或多个服务器中有关的偏好的整合约束；以及以最大化地满足所述整合约束的方式将所述应用分配至一个或多个服务器中。

附图说明

图1是用于在多种约束下实现服务器整合的本公开的虚拟化和整合分析引擎或方法的高级流程图。

图2A是根据本公开的示例实施例的方法的约束管理过程的流程图。

图2B是根据本公开的示例实施例的方法的应用安置过程的流程图。

图3是整合约束的图形表示。

图4是用于在“可以是（can be）”亲和矩阵（affinity matrix）中确定每个元（entry）的权重的双权函数（Biweight function）的曲线图。

图5是示出了根据本公开的示例实施例的基于演进（evolution）的安置搜索算法的流程图。

图6A示意了根据本公开的示例实施例的变换算子（mutation operator）的运算。

图6B示意了根据本公开的示例实施例的重组算子（recombination operator）的运算。

图7示意了应用编组过程的示例实施例。

图8示意了将应用编组过程变换为图形切割（graph cut）问题。

图9是利用指令而编程的计算机设备的示例实施例的框图，这些指令使该设备能够执行本公开的虚拟化和整合分析引擎或方法。

具体实施方式

通过虚拟化而进行的服务器整合创造了机会来充分利用系统资源、降低IT成本并节约企业的能量和空间。但是，这还对整合的系统提出了新的挑战和潜在的风险。例如，一个应用的不适当安置可能导致物理机中放在一起的所有其他应用的服务中断。为了避免这些风险，在整合之前需要仔细的计划，这应当考虑系统的各个角度，包括但不限于系统的性能、维护、安全性和商业角度。这些考虑中的每一个被视为必须在服务器整合中管理（即，组织和处理）以实现高质量结果的质量因素或约束。

存储共享约束

许多虚拟机监视器具有基于内容的存储共享特征，以在驻留于相同物理机中的虚拟机（VM）之间共享存储页的复制拷贝。为了在整合的系统中提高存储利用，更好的是将具有许多复制存储页的应用（其中每一个由VM封装）分配至相同机器中。

网络约束

存在多种网络相关约束，这是由于重要的是具有整合的环境，其中，尽可能少地中断应用之间的网络通信。例如，由于以下两个原因，可以避免将两个网络密集型应用分配至相同机器中：1）两个网络密集型VM在一个物理机中共存将导致VM之间的性能干扰；2）通过在系统中均匀分布网络密集型应用，可以平衡网络业务，并且降低网络瓶颈的可能性。

相关性认知约束（Correlation Awareness Constraints ）

整合的一个优点在于以下事实：其允许物理机中共同主控的应用之间的资源复用。由此，可以优化每个机器中的资源使用率。然而，如果具有相关资源利用的两个应用一起位于相同机器中，则无法充分利用资源复用的优点。在整合过程中，必须将这些应用分离至不同机器中。

同步峰值负载避免约束

在共享的整合环境中，每个应用的资源超额预订可以最大化所利用的资源方面的平台收益。即，不是使用每个应用的最大资源使用作为其资源需求，而是可以使一些超额预订容限（overbooking tolerance）（例如，使用99%利用率作为资源需求）引导应用安置。然而，为了取得这种优势，需要将具有同步峰值负载的应用分离至不同机器。否则，由于对其超额预订容限的频繁违反，这些应用可能表现出性能问题。

安全性和保密约束

尽管当前虚拟化产品在内部提供了强大的安全性机制，但是仍存在危及管理程序（hypervisor）的可能性，这从而向恶意内部人士（malicious insider）暴露所有用户域。这些可能性导致对应用隔离和软件完整性的严格要求。例如，管理规定可能需要投资银行维持其市场分析和证券承销部门（包括其相应的信息处理设施）之间的严格分离。类似地，一些保密要求需要确保应当将包含冲突信息的两个应用分离至不同物理机中。

维护约束

在整合环境中，需要物理服务器重启的任何情形将影响该机器中的所有VM。因此，必须将具有重叠维护窗口的应用组合成一个物理主机，使得可以减轻整合的系统中的硬件维护的影响。

商业约束

还存在对整合的IT环境的运营进行管理的大量非技术考虑。例如，可以将一些应用（例如，那些金融处理软件）分配在一起，以便于管理。另一方面，由于合约义务，需要分离服务于不同客户的一些应用。

存在将影响服务器整合的结果的许多其他约束，包括但不限于故障容限和电力线冗余。在本公开中，在服务器整合中有效地利用大量约束。即，发现了在最大化地满足指定约束的同时需要尽可能少的机器的整合解决方案。

图1是用于在多种约束下实现服务器整合的本公开的虚拟化和整合分析引擎或方法的高级流程图。该方法一般执行两个过程：约束管理10和应用安置20。约束管理过程集中于对各种整合约束的有效处理。应用安置过程以最优的方式在约束下分配应用。由此，可以获得不仅需要最小量资源来主控应用而且最大化地满足现有约束的整合解决方案。

约束管理过程发现、表示、检验和组合服务器整合中的所有约束。其不仅接受人指定的约束，而且从系统资源日志和配置文件自动发现约束。例如，约束管理过程可以分析应用的历史资源使用，以标识频繁示出其资源利用的同时存在的峰值的应用对。需要在整合期间分离这些应用对。类似地，还可以通过应用之间的关系（即，在物理机中这些应用优选是放在一起的还是分离的）来描述许多其他约束。因此，使用亲和矩阵来表示每个约束，其中，每个元反映了将相关应用对一起置于相同物理服务器中的偏好。基于矩阵元的值，进一步将亲和矩阵分类为多种类型：例如“必须是（must be）”、“不应当是（should not be）”和“可以是”矩阵。尽管“必须是”和“不应当是”矩阵指定了两个应用必须或不应当位于相同机器中，但是“可以是”矩阵提供了应用安置的软偏好（soft preference）。在整合过程中，必须遵循“必须是”和“不应当是”约束，而需要基于亲和矩阵中描述的偏好程度来尽力满足“可以是”约束。

为了高效利用大量约束，约束管理过程针对每种类型的亲和矩阵提供了约束融合（fusion）过程。“必须是”或“不应当是”矩阵的融合是直截了当的，这是由于在组合的输出中必须全部满足这些硬约束。对于“可以是”约束，该方法使用加权平均来组合这些矩阵。在该方法中仔细选择组合的权重，以在原始约束中强调这些强偏好以及在融合中区分各种约束。由此，组合的“可以是”矩阵可以保存来自初始矩阵的所有重要信息。

该方法的应用安置过程将应用安置到由整合约束引导的物理机中。已知，应用安置是NP硬（NP-hard）问题并通常依赖于启发法方法来找到近似最优解。然而，主要为了最小化主机而设计应用安置中使用的当前启发法，这未考虑在整合期间对约束的满足。为了自动化更有效启发法的设计，应用安置过程的一个实施例使用基于演进的算法来在约束下标识最优应用安置。该算法开发出多个演进算子（例如，变换、重组和选择），以更新每个群体（population）的安置解。由此，群体的质量始终得以改进，而演进过程将最终收敛为最优安置解。

应用安置的搜索空间随应用的数目而以指数方式增大。为了使安置搜索与应用的数目适应性缩放，应用安置过程的一个实施例在应用安置之前提供了应用编组机制。在该实施例中，应用安置过程将应用群集为多个组，并在每个应用组中分别执行安置搜索。由此，可以显著改进基于演进的安置算法的效率。当整合中涉及的应用的数目较大时，这种优势尤其有价值。

约束管理

图2A是该方法的约束管理过程的流程图。在约束管理过程的框200中，发现服务器整合中利用的约束。以上讨论的约束是服务器整合中利用的常见约束中的一些，尽管实际上存在更多的约束。这些约束从不同角度表示对服务器整合的各个期望，这些角度包括系统性能、可靠性、安全性、能量、维护、商业等。尽管一些约束可以由系统运营商直接指定，但是可以从系统日志和配置文件发现多种约束。

给定多种约束，则需要表示这些约束的一致方式，使得可在整合过程中良好地利用这些约束。已经观察到，可以将大多数约束转换为整合的应用之间的依赖性集合。例如，可以将“存储共享约束”表达为基于其存储图像的相似性将应用对分配至相同机器中的偏好。类似地，“安全性约束”通常指定不应当安置到相同机器中的应用对的列表。因此在约束管理过程的框210中，使用应用亲和矩阵                                               来描述或表示约束，以描述每个约束c，其中，n是要整合的应用的数目，其中，第(i,j)个元A_ij表示根据约束c将应用a_i和a_j安置到相同物理机中的偏好。值A_ij从-1至1的范围内变化，其中，正值表示将两个应用安置到相同机器中的偏好或协定，而负值表示与一起放置两个应用相反。

在约束管理过程的框220中，基于约束的严格度（strictness）将亲和矩阵分类为多种不同类型。已经观察到，尽管必须在整合期间实行一些约束（例如安全性和保密约束），但是一些约束仅提供了与安置应用有关的特定偏好程度。为了区分软和硬约束，该方法将亲和矩阵划分为多种类型。

一种类型的亲和矩阵是“必须是”亲和矩阵。“必须是”矩阵元的值是1或0。1值的元表示必须将两个相关应用安置在一起，而0值的元不包含任何期望。

另一种类型的亲和矩阵是“不应当是”亲和矩阵。“不应当是”矩阵具有-1或0值的元。尽管-1值的元指示了不应当将两个相关应用安置在一起，0值的元不包含任何期望。

其他类型的亲和矩阵是“可以是”亲和矩阵。“可以是”亲和矩阵表示分配应用的软偏好，其中，每个元的值处于-1与1之间。

每个约束可以由属于以上或其他类型之一的具体亲和矩阵表征。如图3所示，给定多种约束c₁, c₂ …, c_k，则可以获得亲和矩阵的多个集合，分别表示例如“必须是”、“不应当是”和“可以是”约束。执行了矩阵分类，这是由于每种类型的矩阵将以其自身的方式在整合过程中起作用。在该方法必须遵守整合中的硬约束的同时，软“可以是”约束仅可以被尽力满足。

实际上，在整合约束中可以存在一些冲突。例如，可以在“必须是”和“不应当是”矩阵中均指定一些应用对。该方法可以通过在整合之前在框225中检验所有约束来识别这些冲突。约束检验过程确定在硬约束之间是否存在冲突。即，如果应用对被标签为“不应当是”和“必须是”越是，则将生成警告。约束检验过程确定以下条件：“必须是”安置在一起的应用的资源需求之和应当小于物理机的容量。否则，没有机器可以主控该组应用。例如，如果基于约束而必须安置在一起的应用集合的总计资源需求超过任何物理机的资源容量，则该方法可以辨别该情形并在整合过程之前输出警告。然而，该方法并不在整合期间解决这些冲突。取而代之，该方法发现或识别所有这些违反，且然后要求系统运营商处理它们。

实际上，可能遇到表示服务器整合的各种约束的大量亲和矩阵。如果直接使用原始约束来执行应用安置，则安置算法必须频繁地逐一检验这些亲和矩阵，以生成可行的解。因此，在约束管理过程的框230中，使用约束融合过程来组合亲和矩阵。由此，可以获得少量亲和矩阵，以表示原始约束。通过使用紧凑的约束表示来引导应用安置，安置算法可以更高效。

分别对每种类型的亲和矩阵执行约束融合。对于硬约束（例如，“必须是”和“不应当是”亲和矩阵），其组合相对简单，这是由于在组合的输出中必须全部满足原始约束。例如，仅当原始“必须是”矩阵中的至少一个在该元中具有非零值时，组合的“必须是”矩阵的元值才为1。类似地，只要原始“不应当是”矩阵之一在一个元中具有非零值，就在组合的“不应当是”矩阵中设置该元的值-1。

“可以是”约束的组合不是直截了当的，这是由于这些约束被表示为反映整合的各种偏好程度的实值矩阵。此外，亲和矩阵通常源自不同源，每个源具有其自身的准则以指定偏好。因此，在一个实施例中，使用加权平均来组合“可以是”矩阵。将权重α_i指派给每个“可以是”亲和矩阵，以区分这些软约束的重要性，其中，，而K是“可以是”亲和矩阵的总数。以下等式（2）示出了：较大值α_i反映了其相关亲和矩阵在整合期间的较高重要性。权重值可以由系统运营商基于其对各种约束的源的了解来指定。

除了辨别各个亲和矩阵以外，还在约束融合期间考虑亲和矩阵中的每个元的值。这是由于“可以是”矩阵中的这些软偏好通常包含歧义，且歧义的级别基于矩阵中的每个元的值而变化。接近于-1或1的元值包含极小的歧义，原因是由这些值表达的强偏好。另一方面，接近于0的元值可能包含较高歧义。如果在服务器整合中以相同方式对待元值，则可以在许多有歧义的建议中掩埋强偏好。例如，假设应用α_i与α_j之间的亲和关系被指定为：

10个原始“可以是”矩阵中的，其中，仅一个约束强烈建议应当分离这种应用对（利用值-0.9），而其他约束呈现弱值0.1。在该示例中，如果对这些值求平均，则将针对应用α_i和α_j获得最终元值0，这是不期望的，原因在于这种结果忽视了组合中对-0.9的第一强烈建议。为了强调这些强烈建议，将权重w_ij应用于每个“可以是”矩阵中的每一个元C_ij。可以使用以下双权函数，利用元值C_ij来确定w_ij的值：

。（1）

图4图示了双权函数的曲线，该函数用于确定“可以是”亲和矩阵中的每个元的权重。可以看出，对于具有高绝对值的矩阵元，权重值较高，而对于具有低绝对值的那些元，权重值较低。

基于以上考虑，给定K个“可以是”亲和矩阵C⁽¹⁾、C⁽²⁾、……、C^(K)，则组合的输出矩阵C将在其第(i, j)元中具有以下值：

。（2）

其中，α-₁、……、α-_K表示用于区分亲和矩阵的权重，而w_ij^(k), k =1、……、K表示亲和矩阵C^(K)中的第(i, j)元的权重。在约束融合之后，可以重新归一化输出矩阵C，以确保所有元值的值处于-1与1之间的范围内。

应用安置

图2B是该方法的应用安置过程的流程图。该应用安置过程包括框240中的可选应用编组过程和框250中的应用安置过程。可选应用编组过程240用于在存在大量应用时加速应用过程250。

在应用安置过程250中存在两个单独的目的。第一目的来自资源节约的角度。基于每个应用的资源需求和机器的容量将应用分配至最小数目的机器。通过这样做，可以实现最大能量耗费节约（以及硬件成本节约）。应用安置的第二个目的来自以上讨论的各种约束。整合解决方案应当符合这些约束，以使系统更可靠、稳定且易于管理。

基于以上目的，使用目标（objective）函数来引导最优应用安置的搜索。给定n个应用，则将每个应用α_i的资源需求表示为，其中对应于R种类型的资源（例如CPU、存储器、盘、网络带宽等）之一。类似地，m个物理服务器中的每一个的资源容量被表示为。使用n x m二进制矩阵X来描述应用安置解，其中，第(i, k)元x-_ik描述了是（x_ik=1）否（x_ik=0）应当将应用α_i置于第k个机器中。由于每个应用可以置于仅一个物理机中，因此结果是，其中。还使用m维二进制向量y来描述每个物理服务器的状态，其中，第k个元素y-_k=1表示开启第k个服务器，而y_k=0表示该机器的“关断（off）”状态。基于以上标记法，通过找到需要最小数目的机器在服务器容量满足所有应用的资源需求的条件下主控应用的矩阵X来实现应用安置的第一目的

（3）

，其中。

如上所述，应用安置的第二目的涉及对各种约束的符合。这里，使用不同的策略来处理各种类型的约束。在应用安置过程期间检查“不应当是”约束。即，当将一个应用分配给机器时，首先基于“不应当是”亲和矩阵中的规范来确定是否有任何冲突应用已驻留于该机器中。如果在该机器中发现冲突应用，则跳过该冲突应用，并评估其他机器以安置该应用。

在应用安置之前处理“必须是”亲和矩阵或约束。根据“必须是”矩阵，将必须置于相同机器中的那些应用进行组合，并使用新应用来在安置过程中表示它们。该新应用的资源需求等于所有组合的应用的需求之和，且与其他应用的其亲和值（affinity value）等于其源应用与其他应用的平均亲和。具体地，将遵守“必须是”约束的应用组合成虚拟应用。实际应用具有两个特征：1）资源需求；以及2）与其他应用的亲和。虚拟应用需要在整合中以相同的方式对待与实际应用相同的两个特征。为了实现该结果，该方法：1）将虚拟应用的资源需求定义为等于所有组合的应用的需求之和；以及2）将虚拟应用与其他应用之间的亲和值定义为等于其源应用与其他应用的平均亲和。

在安置过程中，仅考虑新生成的应用，而不单独考虑原始应用。

不同于“必须是”和“不应当是”约束，“可以是”约束或亲和矩阵C表示用于分配应用的软偏好。应当将具有高亲和的应用分配至相同机器中，并将具有高亲和的应用与具有低亲和分数的应用分离。可以将这种安置目标描述为最大化一起置于每个机器中的所有应用的总计（组合）亲和分数

（4）

高总计亲和分数反映了与“可以是”约束的更好符合。然而，由于在最小化框架中描述了在等式（3）中表达的第一安置目的，因此将等式（4）重写为以下等式

（5）

其中，使用(1-C_ij)来描述在相同机器中分配两个应用时这两个应用之间的不合。总结一起置于机器k中的每个应用对α_i和α_j之间的不合或冲突级别，即，x_ik=x_jk=1，且该方法试图在应用安置期间最小化这种函数。通过这样做，促进具有高亲和值的那些应用置于相同机器中，并分离具有低亲和值的那些应用。

将在等式（3）和（5）中描述的两个目标进行组合，针对应用安置在等式（6）中获得最终目标函数

（6）

参数λ确定每个目标在安置解中的重要性。在一个实施例中，将参数λ设置为1。在其他实施例中，可以将参数λ设置为其他值，以平衡每个目标的重要性。

如果每个应用被视为项目并且每个机器被视为箱（bin），则应用安置的任务与传统装箱问题相对应，针对该问题，可能导致最优解的简洁或智能算法是不可能的。代替使用一些穷举分析来找到最优解，频繁采用一些人为设计的启发法（例如，首次适配递减（FFD）和最佳适配递减（BFD）算法）来找到装箱的近似最优解。然而，这些启发法仅集中于最小化机器的数目，而未考虑应用安置中的各种约束。如果依赖于传统启发法来搜索等式（6）的目标函数的最优解，则最终结果可能远离期望最优值，这是由于其并不反映等式（5）的第二目标。因此，多目标优化需要新的启发法设计。然而，难以手动发现这些新的启发法，这是由于该问题的解空间比传统装箱问题的解空间复杂得多。因此，在一个实施例中，可以使用搜索最优安置解的基于演进的算法来执行框250的应用安置过程。演进算法允许经由演进来自动化有效启发法的设计。由此，演进算法可以比基于传统启发法的方法实现更好的安置结果。

图5是示出了基于演进的安置搜索算法的流程图。每个安置解被视为一个样本，使用P(g)来表示在生成g时μ个安置解的群体。对于每个安置解，该方法计算等式（6）的目标函数的值。对群体的评估是计算该群体中的每个候选安置解的目标函数值。因此，在图5的流程图的框600中，生成安置解P(g)的初始群体（群体P(g)），并在框610中，评估群体P(g)。在框620中，确定是否终止该过程。在以下情况下，在框622中终止该过程：1）由多个连续群体生成的等式（6）中的目标函数示出了非常接近的值（收敛）；或者2）已经达到特定量的时间预算。在以下情况下，该过程继续至框630：1）连续群体未示出目标函数（6）的收敛行为；以及2）仍存在可用于继续的时间预算。通过对群体P(g)使用变异算子，在框630中生成群体P(g)的大小λ的后代（offspring）P’(g+1)。后代P’(g+1)包含需要评估的新安置解。在框640中评估后代P’(g+1)中的每个后代样本的目标函数（安置解）。在评估了后代P’(g+1)中的每个个体后代样本的目标函数之后，演进算法通过从后代P’(g+1)和先前群体P(g)的联合（union）中选择最佳样本，在框650中生成安置解的新群体，即，群体P(g+1)中的第(g+1)个。在安置过程中，良好的样本对应于可带来在等式（6）的函数中指定的低目标值的安置解。通过设计适当的“变异（variation）”和“选择（selection）”算子，图5的演进算法的迭代过程将收敛至最优安置解。

在基于演进的安置搜索中，每个安置解被表示为：

（7）

等式（6）包含多个应用集合，其中每一个描述了一起置于相同机器中的应用的列表。注意，每个应用出现在一个且仅一个应用集合中，且对相同集合中的那些应用的总计资源需求不应当超过物理机的容量。表示P中的应用集合的总数等于主控这些应用所需的物理机的数目。

仍参照图5，基于这种表示，可以通过从未分配的应用的给定池中随机选择应用α₁、且然后将其分配至空机器中来生成框600的每个初始安置解。以概率性方式选择应用α₁，以确保具有较大资源需求的那些应用更可能被首先选择。从未分配的应用的给定池中选择其他应用，并将其定位到α_i的机器中。概率性应用选择用于选择其他应用，也使得具有与α_i的较高亲和以及较高资源需求的应用变得更有机会被选择为α_i的邻居。将所选择的应用分配至α_i的机器中，直到在该机器中没有空余容量以主控更多应用为止。重复该过程，直到未分配的应用的给定池为空为止。在将应用分配至机器中期间，检验“不应当是”约束矩阵，以查看是否有冲突应用已存在于该机器中。如果是，则撤回当前安置动作，即，将应用安置回到未分配的应用的给定池中以供未来选择。执行安置生成μ次，而该μ个安置解用作初始群体。注意，不是利用均匀随机采样，而是利用大量信息（例如，应用的资源需求以及应用之间的亲和）来引导初始安置解的生成。通过这样做，可以与安置空间中的潜在最优值接近地定位所生成的初始样本，且因此，演进过程可以有较高机会快速收敛至最优解。

在框610中评估了群体P(g)之后，在框630中将变异算子应用于群体P(g)以得到其后代P’(g+1)。在一个实施例中，变异算子包括变换算子和重组算子。尽管重组的目的是共享来自先前群体的信息以使得可以保存对搜索空间的结构的在先了解，但是变换是为了将一些随机性添加至新群体中，使得搜索过程可以更有机会探查搜索空间中的新结构。

图6A示意了变换算子。给定安置解P₁，则在步骤1中随机选择需要变换的一些应用集合。图6A所示的箭头表示所选择的应用集合。从安置解P₁中移除所选择的集合，并将移除的集合中的应用安置到队列中。在步骤2中，将排队的应用分配至修改后的安置解P₁’中。通过按应用的资源需求在队列中对应用进行排序并从高至低需求逐一选择应用来执行分配。对于每个所选择的应用α_i，执行搜索以找到该应用的理想机器（即，对P₁’中的适当应用集合的搜索），以便主控所选择的应用。计算所选择的应用α_i与P₁’中的每个机器中的所有应用之间的总计亲和，且然后从高亲和至低值扫描每个机器。如果存在具有足以主控所选择的应用α_i的空余资源的机器，则将所选择的应用α_i安置到该应用集合中。否则，开启空机器，即，在P₁’中添加新应用集合以主控α_i。一旦已经安置了队列中的所有应用，就获得来自原始解P₁的变换安置。

图6B示意了重组算子。与变换算子同时执行重组算子。然而，不同于对单个安置解执行的变换算子，对两个安置解P₁和P₂进行重组算子。在重组的第一步骤中，随机选择两个安置解P₁和P₂之一。在图6B所示的示例中，选择安置解P₁。然后，对于安置解P₁中的每个应用集合，针对该集合中的所有应用对计算总计亲和。然后，选择具有最高总计亲和的一些应用集合，由步骤1中的箭头表示。所选择的应用集合表示安置解P₁中的最佳集合，其是要在重组中保存的。在步骤2中，将所选择的应用集合插入到安置解P₂中，以生成增大的解P₂’。在这种情况下，可以在增大的安置解P₂’中遇到复制的应用。在原始安置解P₂中选择包含与所插入的集合重叠的应用的那些应用集合，且然后从增大的安置解P₂’中移除由“*”表示的那些集合。在移除了那些集合之后，存在修改后的安置解P₂’’的未指派的应用。在步骤3中将这些应用安置到队列中，并以与变换算子中相同的方式使用这些应用，将排队的应用指派至修改后的安置解P₂’’中。在已经指派所有排队的应用之后，最终安置被视为安置解P₁与P₂之间的重组的输出。

在上述两个变异算子中，利用需要变换或重组的应用集合的数目（即，图7和8所示的箭头的数目）来确定变换和重组的强度。在一个实施例中，在具有最小值1的条件下，根据相关安置解中的应用集合的总数的5％和10％之间的值的范围，随机生成该数目。

在演进搜索中，选择群体大小p=30和后代大小μ=30。在后代样本当中，其一半由变换算子生成，而另一半由重组算子产生。尽管变换和重组算子在新样本生成中结合了大量变异，但是关于目标函数（6），演进中的解的第(g+1)个群体始终比先前群体具有更好的性能评估。由此，向解空间中的更好区域引导搜索过程，且该搜索过程将最终收敛至使（6）最小的最优安置。

应用安置过程的搜索空间随着应用的数目以指数方式增长。当存在在整合中涉及的大量应用时，可以实现基于演进的搜索的效率。通过在执行安置过程（图2B的框250）之前执行前述应用编组过程（图2B的框240），可以解决该缩放性问题。

图7示意了应用编组过程的一个实施例。如其中所示，将应用划分为多个组，并在每个应用组中分别执行基于演进的搜索。由于每个子任务的搜索空间比原始解空间小得多，因此可以显著地提高安置搜索的效率。此外，应用编组过程还提供了并行执行安置搜索的可能性。如图7所示，使用多核架构（多核CPU）的并行处理特征来在每个组中同时进行安置搜索。

在应用编组之后，通过合计所有组中的安置结果来获得最终安置解。这种解可能不等效于通过搜索全局解空间而获得的原始最优解。然而，如果由应用的每个组表示的分段子空间彼此正交，则可以最小化这些差异。为了实现这一点，应当以确保应用的不同组尽可能彼此分离的方式划分应用。例如，给定了表示应用之间的亲和的“可以是”矩阵，则应当将具有高亲和值的应用编组在一起，并将其与具有低亲和值的应用分离。注意，在编组过程中不涉及硬约束。不考虑“不应当是”亲和矩阵，这是由于其仅指定了不应当将两个应用置于相同机器中，但仍允许这两个应用处于相同组中。对于“必须是”约束，如上所述生成新应用，以表示“必须是”定位在一起的原始应用，并在编组过程中使用该新应用而不是原始应用。

更具体地，给定n个应用，则编组过程将应用划分为N个组，其中，以及，其中。例如，编组的输入可以是从约束融合过程生成的“可以是”亲和矩阵。可以将“可以是”矩阵构制为如图8所示的图结构。可以使用公知的图分区算法，基于“可以是”矩阵中的值，对应用进行编组，其中，图中的每个节点表示一个应用，而每个链路表示关联的应用之间的亲和。给定这种图，则目的是基于节点对中关联的强度（即，亲和）将其切割成多个子图，如图8所示。存在多种可使用的公知图分区算法，包括但不限于最小值切割算法和归一化切割算法。如果使用归一化切割算法来执行图分区，则该算法试图最小化每个组与其互补之间的平均链路比。

（8）

其中，目标函数中的分子测量多少个链路从出发

（9）

而分母中的degree（）表示从中的节点至该组中的所有节点的总连接

（10）

为了找到使等式（8）最小的应用编组解，对输入“可以是”亲和矩阵C进行归一化，且然后确定归一化矩阵的N个最大特征向量。这些特征向量可以用于表示原始数据。即，可以将每个应用α_i表示为与特征向量中的第i个元相对应的N维向量。在新表示的数据上使用公知的群集（clustering）方法，以将n个应用划分为N个组。这种已知的群集方法可以包括但不限于k-means群集方法。

本公开的方法的直接应用之一是用于云计算的成本估计模型。随着云计算的出现，越来越多的组织现在正在考虑将其内部IT结构移动至公共或私有云，以便节约功率和管理成本。然而，组织可能对于将其IT基础设施移动至云而犹豫不定，这是由于难以准确地估计移动的成本。具体地，这种成本由多种因素确定，这些因素包括应用实例的大小、入站和出站网络业务等等。本公开的方法可以用作供系统管理员获得准确成本估计的整合工具。

本公开的方法可以由适当编程的计算机设备执行，该计算机设备的配置是本领域公知的。例如，可以使用公知的计算机处理器、存储单元、存储设备、计算机软件和其他模块来实现适当的计算机设备。计算机的非限制性实施例的框图在图9中示出并由参考标记900表示。计算机设备900包括但不限于处理器904，处理器904通过执行与本公开的虚拟化和整合分析引擎或方法相对应的计算机程序指令来控制计算机设备900的总体操作。当期望执行计算机程序指令时，可以将计算机程序指令存储在存储设备908（例如，磁盘）中并加载至存储器912中。计算机设备900还包括用于与其他设备进行通信（例如，本地或经由网络）的一个或多个接口916。计算机设备900还进一步包括输入/输出920，输入/输出920表示允许与计算机设备900进行用户交互的设备（例如，显示器、键盘、鼠标、扬声器、按钮等）。

本领域技术人员将认识到，执行与本公开的虚拟化和整合分析引擎或方法相对应的计算机程序指令的计算机设备的实际实施方式还可以包括其他元件，且该图9是出于示意目的而对计算机设备的一些元件的高级表示。此外，执行与本公开的虚拟化和整合分析引擎或方法相对应的计算机程序指令的计算机设备可以是更大设备或系统的组件。此外，本领域技术人员将认识到，这里描述的方法还可以是使用专用硬件来实现的，该专用硬件的电路被具体配置为实现该方法。可替换地，该方法可以是使用硬件和软件的各种组合来实现的。

尽管这里描述并示意了示例性附图和具体实施例，但是应当理解，本公开的范围不限于所讨论的具体实施例。因此，实施例应被视为示意性的而非限制性的，并且应当理解，在不脱离所附权利要求及其结构和功能等同物中阐述的本发明的范围的情况下，本领域技术人员可以在这些实施例中作出变化。