Abstract:
A system and method are provided for determining host assignments for sub-groups of virtual machines (VMs) in a computing environment comprising a plurality of hosts, each host configured for hosting zero or more VMs. The method comprises: determining at least one sub-group of VMs from an overall set of VMs, according to at least one technical or business criterion; and determining, for each sub-group of VMs, a particular set of hosts from the plurality of hosts to be assigned to that sub-group of VMs, based on at least one of: VM-host compatibilities, and existing VM-host placements.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application is a continuation of PCT Application No. PCT/CA2015/050575 filed on Jun. 22, 2015, which claims priority to U.S. Provisional Application No. 62/015,183 filed on Jun. 20, 2014, both incorporated herein by reference 
     
    
     TECHNICAL FIELD 
       [0002]    The following relates to systems and methods for determining optimal placements of virtual machines (VMs) on hypervisor hosts; and for generating corresponding VM/host placement rules, particularly for virtual and cloud computing environments. 
       DESCRIPTION OF THE RELATED ART 
       [0003]    Virtual and cloud computing environments are comprised of one or more physical hypervisor hosts that each run zero or more VMs. These virtual environments are typically managed by a virtual machine manager (VMM) that can organize the hypervisor hosts into one or more groups (often referred to as “clusters”), for performing management functions. Many virtualization technologies allow VMs to be live migrated between hosts with no downtime. Some virtualization technologies leverage the live migration capability by automatically balancing the VM workloads across the hosts comprising a cluster on a periodic basis. Similarly, some virtualization technologies also support the ability to automatically minimize the host footprint of the running VMs to conserve power. These automated load balancing and power saving capabilities typically operate within the scope of a virtual cluster. 
         [0004]    Such VM-to-host placements are normally subject to host level resource constraints (e.g. CPU, memory, etc.) as well as static, user-defined VM-VM affinity, VM-VM anti-affinity, VM-host affinity and VM-host anti-affinity rules. These static placement rules can be used for various purposes such as:
       Running VMs belonging to a load balancing group in separate hosts for better resiliency (VM-VM anti-affinity);   Running VMs comprising an application on the same host for more efficient communication between VMs (VM affinity); and   Running VMs requiring specific software licenses on the corresponding licensed hosts (VM-host affinity).       
 
         [0008]    Determining placement constraints and placement rules for a given computing environment can be time consuming, particularly when done on an ad hoc basis. It is an object of the following to address at least one of the above concerns. 
       SUMMARY 
       [0009]    In one aspect, there is provided a method of determining host assignments for sub-groups of virtual machines (VMs) in a computing environment comprising a plurality of hosts, each host configured for hosting zero or more VMs, the method comprising: determining at least one sub-group of VMs from an overall set of VMs, according to at least one technical or business criterion; and determining, for each sub-group of VMs, a particular set of hosts from the plurality of hosts to be assigned to that sub-group of VMs, based on at least one of: VM-host compatibilities, and existing VM-host placements. 
         [0010]    In other aspects there are provided computer readable media and systems configured for performing the method. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]    Embodiments will now be described by way of example with reference to the appended drawings wherein: 
           [0012]      FIG. 1  is a schematic diagram of an example of a virtual environment architecture; 
           [0013]      FIG. 2  is a schematic diagram of an example of a conventional automated VM placement engine; 
           [0014]      FIG. 3  is a schematic diagram of an example of a cluster having a mix of Windows® and Linux® VMs; 
           [0015]      FIG. 4  is a schematic diagram of an example of a cluster that has optimized VM placements for host-based licensing; 
           [0016]      FIG. 5  is a screen shot of a user interface providing policies for placements of VMs on hosts; 
           [0017]      FIG. 6  is a screen shot of a user interface providing policies for VM sub-groups related to license optimization; 
           [0018]      FIG. 7  is a flow chart illustrating computer executable instructions that can be performed to minimize host resource footprint for a VM sub-group; 
           [0019]      FIG. 8  is a flow chart illustrating computer executable instructions that can be performed to determine optimal hosts for a VM sub-group; 
           [0020]      FIG. 9  is a table illustrating example VM-host compatibility scores based on placement rules; 
           [0021]      FIG. 10  is a table illustrating example VM-group-host compatibility scores based on host placement rules; 
           [0022]      FIG. 11  is a table illustrating example VM-host compatibility scores based on current placements; 
           [0023]      FIG. 12  is a table illustrating example group-host scores based on current placements; 
           [0024]      FIG. 13  is a table illustrating example overall group-host compatibility scores; and 
           [0025]      FIG. 14  is a flow chart illustrating computer executable instructions that can be performed in an ongoing management process flow. 
       
    
    
     DETAILED DESCRIPTION 
       [0026]    It has been found that existing technologies do not support the ability to automatically determine the placement constraints and generate the corresponding placement rules. The following provides a system and method to address this need. Common use cases for such dynamic VM-host placement constraints and rules are to:
       Minimize and constrain the host-based software license usage of VMs by minimizing host resource footprint of the affected VMs. The VM-host placement constraints and rules can be dynamic due to variations in the VM utilization levels, VM resource allocations, and the number of VMs requiring the software license.   Optimize placements for VMs with complementary or conflicting historical utilization patterns by placing them on the same or different hosts. These placement rules can be dynamic as the VM workload patterns change overtime, and VMs are added or removed.       
 
         [0029]    The following systems and methods are also found to be applicable to container technologies (e.g. Docker, Linux Containers) that can run multiple container workloads on container hosts. Containers and container hosts are analogous to the VMs and the hypervisor hosts. Containers also support mobility between container hosts, typically by stopping a container workload on one host, and starting a corresponding container on a different host. This technology is also applicable to routing workloads to the optimal virtual clusters while considering the compatibility and available capacity of the incoming workload and clusters. 
         [0030]    In general, the following provides and exemplifies a model of a virtual computing environment, and provides an example of host-based licensing optimization scenario. Also provided are policies for placing VMs on hosts, and policies for optimizing VM sub-groups of an overall set of VMs in a computing environment. The system is configured to determine optimal number of hosts required per VM sub-group, determine optimal set of hosts for each VM sub-group, and deploy placement rules to enforce VM-host affinity placements. The placement affinity rules can be specified (e.g., by codifying) the relationship between the VM sub-group and the host sub-group in the VMM. 
         [0031]    Turning now to the figures,  FIG. 1  provides a model of a virtual computing environment  10  managed by a VMM  12 . In this example, the environment  10  includes two clusters  14  of hosts  16 . As shown in  FIGS. 1 and 2 , each host  16  can include zero or more VMs  18 . 
         [0032]    Data is collected from the environment  10  to determine the configuration and capacity of existing hosts  16  and of hosts  16  to be added or removed, and to determine the configuration, allocation, and utilization of existing VMs  18  and VMs  18  to be added or removed. The data collected can also be used to determine the existing VM placements, e.g., as shown schematically in  FIG. 1 . 
         [0033]      FIG. 2  illustrates automated load balancing based on recent resource utilization data. This load balancing can be performed by a conventional automated VM placement engine. The placement engine is part of the VMM  12 . The VMM  12  collects data from the hosts  16  regarding the host  16  and VM utilization, analyzes the data, and automatically moves VMs  18  to load balance or save power. As shown in  FIG. 2 , this placement engine supports VM-VM and VM-host affinity and anti-affinity placement rules. In this case, a VM  18  in Host 4  is moved to Host 2  to perform load balancing in Cluster 1 , and the only VM  18  in Host 6  is moved to Host 5  for power saving in Cluster 2 . 
         [0034]    An example of a host-based licensing scenario is shown in  FIGS. 3 and 4 , in which a cluster  14  of six hosts  16  (Host 1  through Host 6 ) are hosting VMs  18  running Windows® (denoted W) and Linux® (denoted L) software. In many virtual clusters  14 , there is a mixture of VMs  18  running different software (e.g., different operating systems, databases, applications, etc.), and licensing costs for some software used by VMs  18  are based on the amount of host resources on which the VMs  19  run. 
         [0035]    As illustrated in  FIGS. 3 and 4 , reducing the host resource footprint of the selected VMs  18  can reduce software license requirements. In this example, the Windows® VMs  18  are licensed based on their host footprint. Therefore, running the Windows® VMs  18  on fewer hosts results in lower software licensing costs. In the initial placements shown in  FIG. 3 , the Windows® VMs  18  are running on five of the six hosts  16  and would need to be licensed for all five hosts  16 . In the optimized placements shown in  FIG. 4 , the Windows® VMs  18  are running on three hosts and thus would only need 60% of the host-based licenses. When comparing  FIGS. 3 and 4 , it can be seen that in this example, the Linux® VMs  18  on Host 1  and Host 4  are migrated to Host 3  and Host 5  with the Windows® VMs  18  on Host 3  and Host 5  migrated to Host 1  and Host 4 . 
         [0036]    The optimized VM placements are determined by the analysis engine  20  and are subject to the VM-host placement policies  22  that constrain the amount of resources that can be consumed by VMs on each host and the VM sub-group optimization policies  24  that dictate how to optimize the VM sub-group placements. 
         [0037]    To determine the membership of the VM sub-groups to run on a minimum host footprint (i.e. an optimal or otherwise minimal set of hosts), VMs  18  requiring a host-based software license can be determined through discovery or imported from a configuration management database (CMDB). Also, VMs  18  in the data model are tagged based on their VM sub-group memberships, and VMs  18  can belong to one VM sub-group at a time. If VMs  18  are using more than one software license (e.g. Windows® and SQL Server®), the VMs can be grouped onto multiple VM sub-groups (e.g. group with Windows® and SQL Server®, and group with Windows® and no SQL Server®). 
         [0038]      FIG. 5  illustrates a policy editing user interface  30  for policies that can be used to determine constraints for placing VMs  18  on hosts  16 . The user interface  30  includes a representative workload model specification, host level resource allocation and utilization constraints (e.g., CPU, memory, disk, network I/O high limits, etc.), high availability (capacity reserved for host failures), and existing VM/host placement rules. The policies can be organized into categories as shown in  FIG. 5 , for example, operational windowing, workload history and trending, representative day selection, handling of unavailable hosts and VMs, reservations and overcommit, and host level utilization (i.e. high limits). The host level utilization policies are illustrated by way of example only in  FIG. 5  and enables settings to be modified. For example the high limit for host CPU utilization can be specified to constrain the maximum CPU that can be used by the VMs on each host. 
         [0039]      FIG. 6  illustrates the user interface  30  to manage policies for minimizing the host footprint of a group of VMs comprising a VM license group. In this scenario, the policy settings include “Software License Control” to enable or disable the license control capability and “VM License Groups” to indicate how the VMs comprising the license groups are to be determined. The settings Host Group Headroom Sizing, Headroom Limit and Headroom Limit as % of Spare Hosts are used to determine the minimum number of hosts  16 . The policies can also include a setting to define the weighting factor used when choosing hosts  16  for a VM sub-group of the overall set of VMs, based the current VM placements vs. VM-host compatibility rules. 
         [0040]      FIG. 7  provides a flow chart illustrating an example process for computing an optimal number of hosts  16  for each VM sub-group. Based on the VMs  18 , hosts  16 , existing placement rules, and VM license groups ( 50 ), the process begins by determining VM affinity groups ( 52 ). Using the VM affinity groups determined at  52 , VM resource allocations, utilization and host resource capacity ( 54 ), policies for placing VMs  18  on hosts  16 , and sizing hosts required for the VM sub-groups ( 56 ), the number of hosts  16  required for each VM sub-group is estimated at  58  based on the primary constraint. 
         [0041]    The primary constraint is determined for each VM sub-group by computing the minimum number of hosts required to run the VMs based on each resource constraint being modeled (e.g. CPU overcommit, memory allocation, CPU utilization, memory utilization, etc.). For each resource constraint, the total resource allocations (e.g. virtual CPUs, memory allocations) or total resource utilization (CPU used, memory used, disk I/O activity, network activity) of the VMs in the VM sub-group is computed and compared against the corresponding useable resource capacity of the hosts. The useable host capacity is based on the actual host capacity and the corresponding resource limit specified through the policies. For example, the total CPU allocation for a VM sub-group is the sum of the virtual CPU allocations of the VMs. The useable CPU allocation capacity for a host is the number of CPUs of the host multiplied by the host CPU allocation limit. Similar calculations are performed for other potential resource constraints, the resource constraint that requires the most number of hosts for the VM sub-group is considered to be the primary constraint. If more than one resource constraint requires the same number of hosts, the primary constraint may be determined by considering the fractional hosts required (e.g. if CPU allocation requires 1.5 hosts and memory allocation requires 1.6 hosts, CPU allocation is considered to be the primary constraint). 
         [0042]    If the total estimated number of hosts  16  required for all the VM sub-groups exceeds the actual number of hosts  16  (determined at  60 ), the fair share rule can be used to allocate the number of hosts  16  per VM sub-group, i.e. by allocating the number of hosts for each VM sub-group by pro-rating the available hosts ( 62 ). 
         [0043]    However, if the estimated number of hosts  16  required is less than the actual number of hosts  16  (as determined at  60 ), the number of hosts for each VM sub-group is allocated via a permutation stacking analysis ( 64 ). The permutation stacking analysis can be performed by first sorting the VM sub-groups from largest to smallest based on the primary constraint. Then, for each group, the permutation analysis is performed by stacking the VMs  18  on the hosts  16  to ensure that the VMs  18  fit. This analysis may find that more hosts  16  are required. 
         [0044]    The hosts are then assigned to the determined groups as required to output minimum number of host allocations for each VM sub-group ( 66 ). 
         [0045]    To illustrate the process flow in  FIG. 7 , consider an example in which:
       a virtual cluster is comprised of 20 VMs and 6 hosts; and   3 VM sub-groups are clustered as: G 1 , G 2 , G 3 .       
 
         [0048]    Based on primary resource constraints (e.g. memory), the estimated number of hosts for G 1 , G 2  and G 3  are 4, 3, 2, and thus the total number of estimated hosts=9. It may be noted that each group can have different primary constraints. 
         [0049]    In this example, the total estimated # hosts=9&gt;actual # hosts=6. 
         [0050]    In applying fair share, the # of hosts are allocated to the groups as follows:
       G(n)=estimated # hosts required for group*actual # hosts/total estimated # hosts required. In this example scenario:       
 
         [0000]        G 1=4*6/9=2.67; 
         [0000]        G 2=3*6/9=2; and 
         [0000]        G 3=2*6/9=1.33. 
         [0052]    To allocate hosts, a floor value for each group is determined as follows:
       G 1 =2;   G 2 =2; and   G 3 =1.       
 
         [0056]    Next, the sum of allocated hosts is computed, and is =5, so one host is available. The available host to group with the largest remainder (i.e. G 1  with 0.67 in this example) is allocated, and the final host allocation is:
       G 1 =3;   G 2 =2;   G 3 =1.       
 
         [0060]    The optimal hosts  16  for the VM sub-groups are also determined. This process chooses the best hosts  16  for each VM sub-group, accounts for existing VM-host affinity and VM-host anti-affinity rules, and can favor current placements to minimize volatility in implementing the placement plan, and assigns hosts  16  to a host group associated with a VM-host affinity placement rule. 
         [0061]      FIG. 8  illustrates a process flow for determining such optimal hosts  16  from the VM sub-groups. 
         [0062]    Using VM-host placement rules for affinity and anti-affinity ( 70 ), a VM-host compatibility score is computed ( 72 ) for each VM-host pair based on the placement rules. A normalized VM-host compatibility score is computed ( 74 ) for each VM-host pair based on the placement rules, and a VM-group-host compatibility score is computed ( 76 ) for each group-host pair based on the placement rules. 
         [0063]    Using the current VM placements on the hosts  16  ( 78 ), a VM-host compatibility score is computed ( 80 ) for each VM-host pair based on the current placements. A normalized VM-host compatibility score is computed ( 82 ) for each VM-host pair based on the current placements, and a group-host compatibility score is computed ( 84 ) for each group-host pair based on the current placements. 
         [0064]    The group-host compatibility scores based on the placement rules and the current placements are then used to compute an overall group-host compatibility score ( 86 ) for each group-host pair, based on a weighting factor ( 88 ) and such scores ( 76 ,  84 ) from the current placements and placement rules. 
         [0065]    From the overall group-host compatibility scores ( 86 ), a VM sub-group is chosen to process ( 90 ). The group-host compatibility metrics and the number of allocated hosts are used to select the optimal host assignments for the group ( 92 ). This is done by comparing group-host scores to choose the most suitable hosts for a group of VMs  18 . For example, the largest group may be chosen first. 
         [0066]    After assigning hosts to a VM sub-group, the process then determines if any group exists with unassigned hosts ( 94 ). In this way, the process re-computes group-host compatibility scores ( 96 ) based on the remaining groups and hosts until there are no additional unassigned hosts and the process is done. The output is a set of one or more VM sub-groups with optimal host assignments ( 98 ). 
         [0067]    An example will now be provided, making reference to the tables shown in  FIGS. 9 through 13 . In  FIG. 9 , VM host compatibility scores based on existing placement rules are shown. In this example, VM-host compatibility scores are between 0 and 100, wherein 100 means fully compatible and 0 means incompatible. 
         [0068]    The VM-host compatibility scores may also be based on the current VM placements on the hosts. For the current placements, the VM-host compatibility of 100 indicates that the VM is currently placed on the given host and 0 indicates VM is not placed on the given host. 
         [0069]    When computing the compatibility scores, as shown by way of example below, when there is not full compatibility (with a score of 100) or complete incompatibility (with a score of zero), any one of a variety of scoring mechanisms can be used to assign a score between zero and 100 for partial compatibility. 
         [0070]    For a given VM-host pair, the normalized score is compute as follows: 
         [0071]    Normalized score for V(n)−Host(n)=compatibility score of V(n)−Host(n)/sum of scores of V(n)−Host(i=1 to h). For example, the normalized score for V 1 −Host 1 =100/(100+0+100)=0.5. 
         [0072]    In the example shown in  FIG. 9 , it can be seen that based on the placement rules, V 1 -V 4  cannot be placed on Host 3 , and V 3  and V 4  cannot be placed on Host 1 . Since V 3  and V 4  can only be placed on Host 2 , the normalized compatibility scores are 1 for both those cases. The normalization of the scores for V 1 , V 2 , V 5  and V 6  are also apparent from  FIG. 9  based on which of the VMs  18  are compatible with which of the hosts  16 . 
         [0073]    Turning now to  FIG. 10 , the group-host compatibility scores for this example are shown. The group-host compatibility score is a relative measure of the compatibility of the group against the target host  16 , wherein the larger the value, the more compatible they are. It may be noted that the group-host compatibility score value can be negative. For a given VM sub-group and host  16 , the group-host compatibility score is based on the following formula: 
         [0074]    SUM(Normalized VM-host scores of current group)−SUM(Normalized VM-host scores of other groups); and 
         [0000]      Compatibility score for  G 1−Host1=( NS ( V 1)+( V 2))−( NS ( V 3)+ NS ( V 4)+ NS ( V 5)+ NS ( V 6)).
 
         [0075]    In this example, the compatibility score for G 1 −Host 1 =(0.5+0.5)−(0+0+0.33+0.33)=0.33. 
         [0076]    These group-host scores provide a relative measure for selecting optimal hosts for VM sub-groups to maximize the overall compatibility for all the groups across the available hosts. That is, the group-host scores consider not only the compatibility of that group with that host, but also how compatible other groups are with that host to optimize assignments across the board. 
         [0077]    In the example shown in  FIG. 10 , VM sub-group G 1  is most compatible with Host 1 , G 2  with Host 2  and G 3  with Host 3 . 
         [0078]      FIG. 11  illustrates the VM host compatibility scores based on the current placements, in this example. For the current placements, 100 is a current VM placement and 0 indicates that the VM  18  is not placed on a host  16 . It can be seen that the 100s simply indicate on which hosts the groups are currently placed (i.e. G 1  on Host 1 , G 2  on Host 2 , and G 3  on Host 3 ). 
         [0079]    The group-host compatibility scores based on the current placements are shown in  FIG. 12 . These group-host compatibility scores based current placements are computed in the same way as the scores based on the existing placement rules ( FIG. 10 ). 
         [0080]    The overall group-host compatibility scores for this example are shown in  FIG. 13 . For each group-host, the compatibility scores from compatibility rules and current placements are blended using the weighting factor, wherein the rules weight is between 0 and 1, and the current placements weight is (1—rules weight). 
         [0081]    The overall score is then computed as: 
         [0000]      Overall score=current placement weight*current placement compatibility score+rules weight*rules compatibility score. 
         [0082]    In the example scores shown in  FIG. 13 , rules and current placement weights of 0.5 are used and, for each group, hosts are selected based on the highest group-host compatibility scores. Based on the analysis, G 1  should be placed on Host 1 , G 2  placed on Host 2 , and G 3  placed on Host 3 . 
         [0083]      FIG. 14  illustrates a process for ongoing management of the dynamic placement rules. Data is collected from the virtual environment  10  ( 100 ), including current VM placements and rules ( 102 ). The virtual environment  10  is analyzed to determine the optimal VM-host placements ( 104 ) and corresponding VM group-host placement rules based on: policies for VM host placements ( 106 ), and policies for optimizing placements ( 108 ). 
         [0084]    New VM placement rules are deployed for VM-host group placement optimization in order to: replace existing dynamic rules, and optionally move VMs  18  to the optimal hosts  16 . The environment  10  can be re-analyzed periodically and placement rules can be replaced as needed ( 110 ). 
         [0085]    For simplicity and clarity of illustration, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. In addition, numerous specific details are set forth in order to provide a thorough understanding of the examples described herein. However, it will be understood by those of ordinary skill in the art that the examples described herein may be practiced without these specific details. In other instances, well-known methods, procedures and components have not been described in detail so as not to obscure the examples described herein. Also, the description is not to be considered as limiting the scope of the examples described herein. 
         [0086]    It will be appreciated that the examples and corresponding diagrams used herein are for illustrative purposes only. Different configurations and terminology can be used without departing from the principles expressed herein. For instance, components and modules can be added, deleted, modified, or arranged with differing connections without departing from these principles. 
         [0087]    It will also be appreciated that any module or component exemplified herein that executes instructions may include or otherwise have access to computer readable media such as storage media, computer storage media, or data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Computer storage media may include volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. Examples of computer storage media include RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by an application, module, or both. Any such computer storage media may be part of the any component described herein or accessible or connectable thereto. Any application or module herein described may be implemented using computer readable/executable instructions that may be stored or otherwise held by such computer readable media. 
         [0088]    The steps or operations in the flow charts and diagrams described herein are just for example. There may be many variations to these steps or operations without departing from the principles discussed above. For instance, the steps may be performed in a differing order, or steps may be added, deleted, or modified. 
         [0089]    Although the above principles have been described with reference to certain specific examples, various modifications thereof will be apparent to those skilled in the art as outlined in the appended claims.