Systems and methods for assigning code lines to clusters with storage and other constraints

• US 9,280,387 B2
• Filed: 08/23/2012
• Issued: 03/08/2016
• Est. Priority Date: 08/25/2011
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Falko, Andrey
• Primary Examiner(s): Mitchell, Jason
• Assistant Examiner(s): GOORAY, MARK A
• Application Number:
  US13/593,095
• Publication Number:
  US 20130219364A1
• Time in Patent Office: 1,293 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

In accordance with disclosed embodiments, there are provided methods, systems, and apparatuses for assigning code lines to clusters with storage and other constraints in an on-demand service environment including, for example, receiving as input, a plurality of code lines for test within a host organization; determining available resource capacity for each of a plurality of clusters within the host organization; determining required resource capacity for each of the plurality of code lines for test within the host organization; sorting the plurality of clusters according to the determined available resource capacity for each; sorting the plurality of code lines according to the determined required resource capacity for each; and allocating the plurality of code lines amongst the plurality of clusters based on the sorting of the plurality of clusters and based further on the sorting of the plurality of code lines. Other related embodiments are disclosed.

Claims

1. A method in a host organization, the method comprising:

receiving as input, a plurality of code lines for test within the host organization;

determining available resource capacity for each of a plurality of clusters within the host organization;

determining required resource capacity for each of the plurality of code lines for test within the host organization;

sorting the plurality of clusters according to the determined available resource capacity for each, wherein the plurality of clusters are ranked from the lowest available resource capacity to the greatest available resource capacity;

sorting the plurality of code lines on a per-code line basis according to the determined required resource capacity for each of the plurality of code lines, wherein the plurality of code lines are ranked from the least resource intensive to the most resource intensive; and

allocating the plurality of code lines amongst the plurality of clusters based on the sorting of the plurality of clusters and based further on the sorting of the plurality of code lines, wherein the plurality of code lines are allocated to available clusters by allocating first, code lines from among the plurality of code lines, having a least or lowest requisite capacity to a cluster having the lowest available resource capacity.

2. The method of claim 1, wherein sorting the plurality of clusters according to the determined available resource capacity for each comprises:

updating an allocation map with the sorting of the plurality of clusters.

3. The method of claim 2, wherein sorting the plurality of code lines according to the determined required resource capacity for each comprises:

sorting the plurality of code lines according to the code line having the lowest required resource capacity to the code line having the greatest required resource capacity; and

updating the allocation map with the sorting of the plurality of code lines.

4. The method of claim 1, wherein the code line having a lowest required resource capacity according to the sorting of the plurality of code lines is allocated first to the cluster having the lowest available resource capacity according to the sorting.

5. The method of claim 4, wherein if the cluster having the lowest available resource capacity according to the sorting is insufficient to fully allocate the code line having the lowest required resource capacity according to the sorting, then the code line having the lowest required resource capacity is partially allocated to each of:

(i) the cluster having the lowest available resource capacity, and

(ii) the cluster having the next to lowest available resource capacity according to the sorting.

6. The method of claim 5, wherein the code line having the greatest required resource capacity according to the sorting is allocated last.

7. The method of claim 1, further comprising:

mapping within an allocation map, each of the plurality of code lines to one or more of the plurality of clusters based on the sorting of the sorting of the plurality of clusters and the sorting of the plurality of code lines;

wherein each of the plurality of code lines is assigned to the one or more clusters based on a pre-defined allowed number of code lines for one or more of the plurality of clusters and based further on available resource capacity for the one or more clusters and required resource capacity for each of the plurality of code lines; and

wherein allocating the plurality of code lines amongst the plurality of clusters comprises allocating according to the allocation map.

8. The method of claim 7, wherein the available resource capacity for each of the plurality of clusters comprises:

a limited storage resource capacity; and

limited capacity for hosting virtual machines (VMs) corresponding to the pre-defined allowed number of code lines for each of the plurality of clusters.

9. The method of claim 1, wherein the method further comprises:

determining a base image required for each of the plurality of code lines; and

for each of the plurality of code lines allocated;

(i) allocating the code line and the base image required for the code line to one or more Virtual Machines executing at the clusters of the host organization, and

(ii) provisioning the allocated code line and the base image required for the code line to the one or more Virtual Machines executing at the clusters of the host organization.

10. The method of claim 1, wherein determining available resource capacity for each of a plurality of clusters within the host organization comprises:

receiving an allocation map as an input, wherein the allocation map defines the available resource capacity for each of a plurality of clusters within the host organization.

11. The method of claim 1, wherein determining available resource capacity for each of a plurality of clusters within the host organization comprises determining one or more of the following attributes for each of the plurality of clusters:

processing power capacity of the cluster derived from one or more Central Processing Unit(s) of the cluster;

capacity for simultaneously hosted Virtual Machines of the cluster based on a pre-defined allowed number of code lines for the cluster; and

storage capacity accessible to the cluster.

12. The method of claim 1, further comprising:

determining a cluster has sufficient available resource capacity for simultaneously hosting two or more Virtual Machines based on a pre-defined allowed number of code lines for the cluster; and

determining on a per Virtual Machine basis for each of the two or more Virtual Machines;

(i) processing power capacity available to the Virtual Machine, and

(ii) storage capacity accessible to the Virtual Machine.

13. The method of claim 1:

wherein determining available resource capacity for each of a plurality of clusters within the host organization comprises determining a quantity of Storage Area Network (SAN) storage, or a quantity of Network Attached Storage (NAS) storage, or a quantity of local storage, accessible to each of the plurality of clusters;

wherein determining required resource capacity for each of the plurality of code lines for test within the host organization comprises determining a quantity of SAN storage required to store each of the plurality of code lines and to store a corresponding base image required by each of the plurality of code lines; and

wherein the required resource capacity for each of the plurality of code lines and the corresponding base image required by each of the plurality of code lines is non-uniform.

14. The method of claim 13, wherein determining available resource capacity for each of the plurality of clusters within the host organization further comprises:

determining minimal processing power requirements for each of the plurality of code lines, wherein the minimal processing power requirements differ among the plurality of code lines.

15. The method of claim 1, wherein receiving as input, a plurality of code lines for test within the host organization comprises:

receiving, as the input, a set of known and pre-configured code lines for test within the host organization.

16. The method of claim 15, wherein the set of known and pre-configured code lines for test within the host organization defines one or more of the following attributes for each of the plurality of code lines for test within the host organization:

required minimal processing power for performing test on the code line;

required storage capacity for storing the code line and for storing a corresponding base image required by code line.

17. The method of claim 1, wherein each of the plurality of clusters within the host organization comprises:

operational memory for the cluster;

one or more Central Processing Units (CPUs) constituting a quantity of processing power for the cluster;

a limited quantity of storage capacity accessible to the cluster;

a network interface;

one or more simultaneously executing Virtual Machines on the cluster capable to support a corresponding pre-defined number of allowable code lines on the cluster; and

wherein each of the Virtual Machines are allocated thereto;

(i) at least a portion of the operational memory for the cluster;

(ii) at least a portion of the quantity of processing power for the cluster,

(iii) at least a portion of the limited quantity of storage capacity accessible to the cluster; and

(iv) at least a portion of network capacity available to the cluster through the network interface.

18. The method of claim 17, wherein allocating the plurality of code lines amongst the plurality of clusters further comprises:

comparing the determined required resource capacity for each of the plurality of code lines for test within the host organization against the Virtual Machine allocations to determine adequacy for allocating any one of the plurality of code lines to a Virtual Machine at the cluster.

19. The method of claim 17 further comprising generating an allocation map representing:

(i) all Virtual Machines within the plurality of clusters within the host organization;

(ii) assignment of every one of the plurality of code lines to a corresponding one of the Virtual Machines within the plurality of clusters;

wherein no more than one of the plurality of code lines is assigned to any single Virtual Machine and where any single code line is assigned to one or more Virtual Machines as needed based on the required resource capacity of the code line.

20. Non-transitory computer readable storage medium having instructions stored thereon that, when executed by a processor in a host organization, the instructions cause the host organization to perform operations comprising:

receiving as input, a plurality of code lines for test within the host organization;

determining available resource capacity for each of a plurality of clusters within the host organization;

determining required resource capacity for each of the plurality of code lines for test within the host organization;

sorting the plurality of clusters according to the determined available resource capacity for each, wherein the plurality of clusters are ranked from the lowest available resource capacity to the greatest available resource capacity;

sorting the plurality of code lines on a per-code line basis according to the determined required resource capacity for each of the plurality of code lines, wherein the plurality of code lines are ranked from the least resource intensive to the most resource intensive; and

according to the determined required resource capacity for each; and

allocating the plurality of code lines amongst the plurality of clusters based on the sorting of the plurality of clusters and based further on the sorting of the plurality of code lines, wherein the plurality of code lines are allocated to available clusters by allocating first, code lines from among the plurality of code lines, having a least or lowest requisite capacity to a cluster having the lowest available resource capacity.

21. The non-transitory computer readable storage medium of claim 20, wherein sorting the plurality of clusters according to the determined available resource capacity for each comprises:

updating an allocation map with the sorting of the plurality of clusters.

22. The non-transitory computer readable storage medium of claim 21, wherein sorting the plurality of code lines according to the determined required resource capacity for each comprises:

sorting the plurality of code lines according to the code line having the lowest required resource capacity to the code line having the greatest required resource capacity; and

updating the allocation map with the sorting of the plurality of code lines.

23. The non-transitory computer readable storage medium of claim 22, wherein allocating the plurality of code lines amongst the plurality of clusters comprises allocating in accordance with the following allocation rules:

(i) select the code line having the lowest required resource capacity;

(ii) if the selected code line having the lowest required resource capacity has a required resource capacity of zero, then select the code line having the next lowest and non-zero required resource capacity as the selected code line;

(iii) select the cluster having the lowest available resource capacity;

(iv) if the selected the cluster having the lowest available resource capacity has an available resource capacity of zero, then select the cluster having the next lowest and non-zero available resource capacity as the selected cluster;

(v) if the available resource capacity of the selected cluster is less than or equal to the required resource capacity of the selected code line then;

(a) update the required resource capacity of the selected code line in the allocation map by subtracting the available resource capacity for the selected cluster from the required resource capacity for the selected code line,

(b) set to zero in the allocation map, the available resource capacity for the selected cluster, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vi) if the available resource capacity of the selected cluster is greater than or equal to the required resource capacity of the selected code line then;

(a) update the available resource capacity of the selected cluster in the allocation map by subtracting the required resource capacity of the selected code line from the available resource capacity of the selected cluster,

(b) set to zero in the allocation map, the required resource capacity of the selected code line, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vii) if a number of code lines assigned to the selected cluster is equal to greater than a pre-defined allowed number of code lines for the selected cluster, then;

(a) set to zero in the allocation map, the available resource capacity for the selected cluster;

(viii) if the required resource capacity of the selected code line is greater than zero, then;

(a) trigger an indication that the plurality of clusters is insufficient to allocate all of the plurality of code lines for test, and

(b) exit;

(ix) repeat allocating according to the rules (i) through (viii) if the required resource capacity for any of the plurality of code lines is greater than zero in the allocation map.

24. The non-transitory computer readable storage medium of claim 20:

wherein the code line having a lowest required resource capacity according to the sorting of the plurality of code lines is allocated first to the cluster having the lowest available resource capacity according to the sorting; and

wherein the cluster having the lowest available resource capacity according to the sorting is insufficient to fully allocate the code line having the lowest required resource capacity according to the sorting, the code line having the lowest required resource capacity is allocated to;

(i) the cluster having the lowest available resource capacity, and

(ii) the cluster having the next to lowest available resource capacity according to the sorting.

25. A system to operate within a host organization, the system comprising:

a processor to execute instructions;

an input interface to receive a plurality of code lines for test within the host organization;

a test analyzer to;

(i) determine available resource capacity for each of a plurality of clusters within the host organization, and

(ii) determine required resource capacity for each of the plurality of code lines for test within the host organization;

a mapping engine to;

(i) sort the plurality of clusters according to the determined available resource capacity for each wherein the plurality of clusters are ranked from the lowest available resource capacity to the greatest available resource capacity,

(ii) sort the plurality of code lines on a per-code line basis according to the requisite capacity for each of the plurality of code lines, wherein the plurality of code lines are ranked from the least resource intensive to the most resource intensive; and

(iii) update an allocation map according to the sort of the plurality of clusters and further according to the sort of the plurality of code lines; and

an allocation engine to allocate the plurality of code lines amongst the plurality of clusters based on the sorting of the plurality of clusters and based further on the sorting of the plurality of code lines, wherein the plurality of code lines are allocated to available clusters by allocating first, code lines from among the plurality of code lines, having a least or lowest requisite capacity to a cluster having the lowest available resource capacity.

26. The system of claim 25:

wherein the mapping engine to sort the plurality of code lines according to the determined required resource capacity for each comprises sorting the plurality of code lines according to the code line having the lowest required resource capacity to the code line having the greatest required resource capacity.

27. The system of claim 26, wherein the allocation engine to allocate the plurality of code lines comprises allocating in accordance with the following allocation rules:

(i) select the code line having the lowest required resource capacity;

(ii) if the selected code line having the lowest required resource capacity has a required resource capacity of zero, then select the code line having the next lowest and non-zero required resource capacity as the selected code line;

(iii) select the cluster having the lowest available resource capacity;

(iv) if the selected the cluster having the lowest available resource capacity has an available resource capacity of zero, then select the cluster having the next lowest and non-zero available resource capacity as the selected cluster;

(v) if the available resource capacity of the selected cluster is less than or equal to the required resource capacity of the selected code line then;

(a) update the required resource capacity of the selected code line in the allocation map by subtracting the available resource capacity for the selected cluster from the required resource capacity for the selected code line,

(b) set to zero in the allocation map, the available resource capacity for the selected cluster, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vi) if the available resource capacity of the selected cluster is greater than or equal to the required resource capacity of the selected code line then;

(a) update the available resource capacity of the selected cluster in the allocation map by subtracting the required resource capacity of the selected code line from the available resource capacity of the selected cluster,

(b) set to zero in the allocation map, the required resource capacity of the selected code line, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vii) if a number of code lines assigned to the selected cluster is equal to greater than a pre-defined allowed number of code lines for the selected cluster, then;

(a) set to zero in the allocation map, the available resource capacity for the selected cluster;

(viii) if the required resource capacity of the selected code line is greater than zero, then;

(a) trigger an indication that the plurality of clusters is insufficient to allocate all of the plurality of code lines for test, and

(b) exit;

(ix) repeat allocating according to the rules (i) through (viii) if the required resource capacity for any of the plurality of code lines is greater than zero in the allocation map.

28. The system of claim 25:

wherein the code line having a lowest required resource capacity according to the sorting of the plurality of code lines is allocated first to the cluster having the lowest available resource capacity according to the sorting; and

wherein the cluster having the lowest available resource capacity according to the sorting is insufficient to fully allocate the code line having the lowest required resource capacity according to the sorting, the code line having the lowest required resource capacity is allocated to;

(i) the cluster having the lowest available resource capacity, and

(ii) the cluster having the next to lowest available resource capacity according to the sorting.

29. A method in a host organization, the method comprising:

receiving as input, a plurality of code lines for test within the host organization;

determining available resource capacity for each of a plurality of clusters within the host organization;

determining required resource capacity for each of the plurality of code lines for test within the host organization;

sorting the plurality of clusters according to the determined available resource capacity for each, wherein sorting the plurality of clusters according to the determined available resource capacity for each comprises sorting the plurality of clusters according to the cluster having the lowest available resource capacity to the cluster having the greatest available resource capacity and updating an allocation map with the sorting of the plurality of clusters;

sorting the plurality of code lines according to the determined required resource capacity for each, wherein sorting the plurality of code lines according to the determined required resource capacity for each comprises sorting the plurality of code lines according to the code line having the lowest required resource capacity to the code line having the greatest required resource capacity and updating the allocation map with the sorting of the plurality of code lines; and

allocating the plurality of code lines amongst the plurality of clusters based on the sorting of the plurality of clusters and based further on the sorting of the plurality of code lines, wherein allocating the plurality of code lines amongst the plurality of clusters comprises allocating in accordance with the following allocation rules;

(i) select the code line having the lowest required resource capacity;

(ii) if the selected code line having the lowest required resource capacity has a required resource capacity of zero, then select the code line having the next lowest and non-zero required resource capacity as the selected code line;

(iii) select the cluster having the lowest available resource capacity;

(iv) if the selected the cluster having the lowest available resource capacity has an available resource capacity of zero, then select the cluster having the next lowest and non-zero available resource capacity as the selected cluster;

(v) if the available resource capacity of the selected cluster is less than or equal to the required resource capacity of the selected code line then;

(a) update the required resource capacity of the selected code line in the allocation map by subtracting the available resource capacity for the selected cluster from the required resource capacity for the selected code line,

(b) set to zero in the allocation map, the available resource capacity for the selected cluster, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vi) if the available resource capacity of the selected cluster is greater than or equal to the required resource capacity of the selected code line then;

(a) update the available resource capacity of the selected cluster in the allocation map by subtracting the required resource capacity of the selected code line from the available resource capacity of the selected cluster,

(b) set to zero in the allocation map, the required resource capacity of the selected code line, and

(c) assign the selected code line to the selected cluster in the allocation map;

(vii) if a number of code lines assigned to the selected cluster is equal to greater than a pre-defined allowed number of code lines for the selected cluster, then;

(a) set to zero in the allocation map, the available resource capacity for the selected cluster;

(viii) if the required resource capacity of the selected code line is greater than zero, then;

(a) trigger an indication that the plurality of clusters is insufficient to allocate all of the plurality of code lines for test, and

(b) exit;

(ix) repeat allocating according to the rules (i) through (viii) if the required resource capacity for any of the plurality of code lines is greater than zero in the allocation map.