Managing execution of programs by multiple computing systems

• US 20070240160A1
• Filed: 03/31/2006
• Published: 10/11/2007
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Paterson-Jones, Roland, Hoole, Quinton, Brown, Christopher, van Biljon, Willem, Smit, Gabriel, Pinkham, Christopher, Tobler, Benjamin
• Granted Patent: US 8,190,682 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 8/60 Software deployment
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine

Abstract

Techniques are described for managing the execution of programs on multiple computing systems, such as computing systems organized into multiple groups. A program execution service manages the program execution on behalf of multiple customers or other users, and selects appropriate computing systems to execute one or more instances of program, such as based in part on locations of one or more previously stored copies of the program from which copies of the program to execute may be acquired. For example, in some situations the selection of an appropriate computing system to execute an instance of a program is based in part on physical or logical proximity to other resources, such as stored copies of the program, executing copies of the program, and/or available computing systems.

Claims

1. A computer-implemented method for managing execution of programs by a program execution service, the program execution service using a plurality of computing systems to execute programs, the plurality of computing systems including multiple groups of computing systems such that the computing systems of each group are physically proximate and share a common group data exchange medium that is specific to that group and such that the multiple groups of computing systems are connected via one or more other data exchange mediums distinct from the group data exchange mediums, the method comprising:

receiving multiple requests that are each to execute an indicated one of multiple programs previously supplied to the program execution service, at least some of the multiple programs each having one or more copies stored locally on one or more of the plurality of computing systems; and

for each received request to execute an indicated program, automatically satisfying the request by,

automatically selecting at least one of the plurality of computing systems to use in executing an instance of the indicated program, the selecting of the at least one computing systems being based at least in part on whether the selected computing systems are in groups with one or more other systems that store local copies of the indicated program; and

for each of the selected computing systems,

if the selected computing system is in a group with one or more other systems that store a local copy of the indicated program, instructing the selected computing system to obtain a copy of the indicated program from at least one of the one or more other systems via the shared common group data exchange medium for the group and to initiate execution of the obtained program copy; and

if the selected computing system is not in a group with another system that stores a local copy of the one program, instructing the selected computing system to obtain a copy of the indicated program from one or more remote systems via at least one of the one or more distinct data exchange mediums and to initiate execution of the obtained program copy.

2. The method of claim 1 wherein the automatic satisfying of each of the received requests is performed by one or more manager computing systems that manage the program execution service, wherein the instructing of a selected computing system in a group to obtain a copy of an indicated program from at least one other system in the group includes providing indications to the selected computing system of the other systems in the group that store a local copy of the indicated program, and wherein the method further comprises, under control of each of multiple selected computing systems:

receiving instructions from a manager computing system to obtain a copy of an indicated program from one or more other indicated systems;

obtaining the copy of the indicated program; and

executing the obtained program copy.

3. The method of claim 1 wherein each group of multiple computing systems is connected to a distinct network switch that provides the common group data exchange medium for the group, wherein the one or more other distinct data exchange mediums include connections between the network switches that have lower data transmission speeds than the high-speed data transmissions between computing systems of a group, and wherein the selecting of the at least one computing systems for an indicated program is performed in such a manner as to give preference to computing systems in groups with one or more other systems that store local copies of the indicated program.

4. The method of claim 1 wherein each of at least some of the plurality of computing systems is associated with a local storage capable of storing copies of multiple programs, wherein the selecting of a computing system includes determining whether any of the at least some computing systems are in a group with that computing system and currently store a local copy of an indicated program, and further comprising, for each of one or more of the selected computing systems and after obtaining a copy of an indicated program to be executed, storing the obtained copy in local storage of the selected computing system.

5. The method of claim 1 wherein at least some of the groups of computing systems each include one or more data storage systems that have local storage capable of storing copies of multiple programs for use by other computing systems of the group, wherein the selecting of a computing system includes determining whether any of the one or more data storage systems are in a group with that computing system and currently store a local copy of an indicated program, and further comprising, for each of one or more of the selected computing systems and after obtaining a copy of an indicated program to be executed, storing the obtained copy in local storage of a data storage system in a group with the computing system.

6. The method of claim 1 further comprising, before the receiving of the multiple requests, receiving a copy of one of the multiple programs and storing copies of the one program on computing systems in multiple groups for later use in satisfying requests to execute the one program.

7. The method of claim 1 wherein the plurality of computing systems are part of a distributed network of computing systems for executing programs of customers of the program execution service, wherein the multiple programs previously supplied to the program execution service are programs supplied by the customers, and wherein at least some of the plurality of computing systems each host multiple virtual machine nodes that each is capable of executing at least one of the multiple programs.

8. The method of claim 1 wherein at least some of the multiple requests to execute indicated programs each include an indication of at least one of a number of instances of an indicated program to execute, of a time to initiate execution of the instances of the indicated program, of one or more hardware resources for use in executing the instances of the indicated program, and of geographic information related to executing the instances of the indicated program, and wherein the automatic satisfying of each of the at least some requests is performed in such a manner as to accommodate the at least one indications for the request.

9. The method of claim 8 wherein at least some of the indicated programs each have associated hardware resource criteria for execution, and wherein the automatic selecting of the at least one computing systems for use in executing each of the at least some indicated programs is further performed such that each of the selected computing systems provides hardware resources that satisfy the associated hardware resource criteria for the indicated program.

10. The method of claim 9 wherein the associated hardware resource criteria include at least one of an indicated amount of memory, an indicated amount of processor usage, an indicated amount of network bandwidth, an indicated amount of disk space, and an indicated amount of swap space.

11. The method of claim 9 wherein the automatic selecting of the at least one computing systems for use in executing each of the at least some indicated programs is further based in part on whether one or more other machines in a group with a selected computing system is currently executing a copy of the indicated program.

12. A computer-implemented method for managing execution of programs by a program execution service, the method comprising:

receiving an indication of a program to be executed on at least one of multiple computing systems of a predefined group, the multiple computing systems being provided for execution of programs for a program execution service and sharing a common data exchange medium;

determining whether one or more of the computing systems of the predefined group stores a copy of the indicated program; and

automatically obtaining a local copy of the indicated program for execution by,

if it is determined that one or more of the computing systems of the predefined group store a copy of the indicated program, obtaining the local copy from at least one of the one or more computing systems via the common data exchange medium; and

if it is not determined that one or more of the computing systems of the predefined group store a copy of the indicated program, obtaining the local copy from one or more computing systems external to the predefined group via one or more data exchange mediums distinct from the common data exchange medium.

13. The method of claim 12 further comprising initiating execution of the obtained local copy of the indicated program on one of the multiple computing systems of the predefined group.

14. The method of claim 13 wherein the method is performed by the one computing system.

15. The method of claim 13 wherein the method is performed by a manager module for the predefined group.

16. The method of claim 12 further comprising initiating execution of multiple instances of the obtained local copy of the indicated program on multiple of the computing systems of the predefined group.

17. The method of claim 12 further comprising sending status information regarding one or more of the multiple computing systems of the predefined group to a remote system manager for use in managing the program execution service.

18. The method of claim 17 wherein the status information includes at least one of an indication of one or more program copies stored on the one or more computing systems, an indication that execution of the indicated program has been initiated, an indication of one or more programs currently executing on the one or more computing systems, and an indication of resource utilization of one or more programs executing on the one or more computing systems.

19. The method of claim 12 wherein the multiple computing systems of the predefined group are all located in a single physical location, the physical location being one of a single hardware rack, a single data center, an area served by a single local area network, and an area served by a single network switch.

20. The method of claim 19 wherein the program execution service further uses multiple other groups to execute programs, each of the other groups having multiple other computing systems in other physical locations.

21. The method of claim 20 wherein the one or more computing systems external to the predefined group from which a local copy is obtained are in one or more of the other groups.

22. The method of claim 20 wherein the one or more computing systems external to the predefined group from which a local copy is obtained are part of a remote storage system that is distinct from the multiple groups used by the program execution service to execute programs.

23. The method of claim 19 wherein the common data exchange medium is a physical data connection between the computing systems in the single physical location, the physical data connection not being shared with computing systems external to the predefined group.

24. The method of claim 12 wherein the common data exchange medium provides higher data exchange bandwidth than the one or more distinct data exchange mediums.

25. The method of claim 12 wherein the multiple computing systems of the predefined group are physically proximate to each other.

26. The method of claim 12 wherein the multiple computing systems of the predefined group are logically proximate to each other.

27. The method of claim 12 wherein the received indication of the program to be executed includes an indication of one or more computing systems of the predefined group that each store a copy of the indicated program, and wherein the determining of whether one or more of the computing systems of the predefined group stores a copy of the indicated program is based at least in part on the received indication of the one or more computing systems.

28. The method of claim 12 wherein the determining of whether one or more of the computing systems of the predefined group stores a copy of the indicated program includes sending a request to one or more computing systems of the predefined group for information related to stored copies of the indicated program.

29. The method of claim 12 wherein the automatic obtaining of the local copy of the indicated program includes storing the obtained local copy in a local program repository of one of the computing systems of the predefined group that contains one or more stored copies of other programs.

30. The method of claim 29 wherein the storing of the obtained local copy of the indicated program in the local program repository includes removing at least one stored copy of another program in order to provide storage space for the obtained local copy.

31. The method of claim 30 wherein the at least one removed copies of the another programs are selected for removal based at least in part on how recently those copies were used for execution of the another programs.

32. The method of claim 12 wherein obtaining the local copy of the indicated program includes obtaining a portion of the local copy from each of multiple computing systems that have access to a stored copy of the indicated program.

33. The method of claim 32 wherein the obtaining of the portion of the local copy from each of the multiple computing systems includes requesting a portion of the local copy from each of the multiple computing systems and requesting additional portions of the local copy from a subset of the multiple computing systems based on responses received to one or more prior requests.

34. The method of claim 12 wherein the receiving of the indication of the program to be executed on at least one of the multiple computing systems of the predefined group includes selecting the predefined group from multiple groups of computing systems used by the program execution service, the selecting being based on current conditions of the selected group.

35. The method of claim 34 wherein the current conditions of the selected group include at least one of whether one or more computing systems of the selected group are available to execute the indicated program, whether one or more computing systems of the selected group are currently executing a copy of the indicated program, and whether one or more computing systems of the selected group have a stored copy of the indicated program.

36. The method of claim 12 further comprising determining that multiple computing systems of the predefined group need a local copy of the indicated program for execution.

37. The method of claim 36 further comprising obtaining a single copy of the indicated program on behalf of all of the multiple computing systems via a data exchange medium distinct from the common data exchange medium, and distributing local copies of the obtained single copy to each of the multiple computing systems via the common data exchange medium.

38. The method of claim 12 further comprising, after the obtaining of the local copy of the indicated program:

executing an instance of the indicated program;

storing the local copy of the indicated program for later use;

after the storing of the local copy, receiving an indication to execute a new version of the indicated program;

automatically obtaining a new local copy of the new version of the indicated program for execution; and

storing the new local copy of the new version of the indicated program for later use in lieu of the stored local copy.

39. The method of claim 12 wherein at least some of the multiple computing systems of the predefined group each host multiple virtual machines that are each able to execute at least one program, and wherein the indicated program is a virtual machine image to be executed by at least one of the virtual machines.

40. A computer-readable medium whose contents enable a computing system to manage execution of programs, by performing a method comprising:

determining to execute at least one instance of an indicated program;

automatically selecting one or more computing machines for use in executing one or more instances of the indicated program, the selected computing machines each being one of a plurality of computing machines that each belong to one of multiple groups, the selecting of the one or more computing machines being based at least in part on each of the selected computing machines being a member of a group that contains at least one machine with a stored copy of the indicated program and at least one computing machine that is available to execute the indicated program; and

providing an indication to initiate execution of the indicated program on at least one of the selected computing machines.

41. The computer-readable medium of claim 40 wherein the automatic selecting of the one or more computing machines includes selecting one of the groups that includes multiple computing machines, the selected one or more computing machines each being one of the multiple computing machines of the selected group.

42. The computer-readable medium of claim 41 wherein the selecting of the one group is based at least in part on the selected group containing at least one machine that has a stored copy of the indicated program and at least one computing machine that is available to execute the indicated program.

43. The computer-readable medium of claim 40 wherein each selecting of the one or more computing machines includes selecting a particular computing machine of a particular group that is available to execute the indicated program.

44. The computer-readable medium of claim 43 wherein the selecting of each of the particular computing machines is based at least in part on the selected computing machine having a previously stored local copy of the indicated program.

45. The computer-readable medium of claim 40 wherein the indicated program uses an indicated amount of memory when executing, wherein at least some of the computing machines are each configured to simultaneously execute multiple programs that use varying amounts of memory when executing, and wherein the selecting of the one or more computing machines based on the at least one computing machine being available to execute the indicated program includes selecting a computing machine that currently has an amount of memory available to execute a program that meets or exceeds the indicated amount of memory.

46. The computer-readable medium of claim 40 wherein the indicated program has one or more associated resource criteria for execution, and wherein a computing machine that is available to execute the indicated program has available resources sufficient to satisfy each of the one or more associated resource criteria.

47. The computer-readable medium of claim 46 wherein the one or more associated resource criteria includes at least one of an amount of memory, an amount of processor usage, an amount of network bandwidth, an amount of disk space, and an amount of swap space.

48. The computer-readable medium of claim 40 wherein the automatic selecting of the one or more computing machines is further based in part on the one or more selected computing machines being members of one or more groups that each contain at least one computing machine that is currently executing a copy of the indicated program.

49. The computer-readable medium of claim 40 wherein the indication to initiate execution of the indicated program is provided to each of at least one of the selected computing machines.

50. The computer-readable medium of claim 49 wherein the indication provided to a selected computing machine to initiate execution of the indicated program includes an indication of one or more computing machines in the group of the selected computing machine that have a stored copy of the indicated program.

51. The computer-readable medium of claim 40 wherein the computing system operates on behalf of a program execution service, wherein the indicated program is one of multiple programs associated with the program execution service by customers of the program execution service, and wherein the plurality of computing machines are used by the program execution service to execute the multiple programs on behalf of the customers.

52. The computer-readable medium of claim 51 wherein each of the multiple groups is a predefined group that includes multiple computing machines that are physically proximate and that share being located on a single hardware rack, located on a single local area network, connected to a single network switch, and/or located in a single data center.

53. The computer-readable medium of claim 40 wherein each of the multiple groups include a distinct data exchange medium that is shared by the computing machines that belong to that group but that is not shared by computing machines that belong to other groups.

54. The computer-readable medium of claim 40 wherein at least some of the plurality of computing machines each have associated local program repositories for storing copies of one or more programs, and wherein the method further comprises selecting at least one stored copy of a program to each be removed from one or more of the associated local program repositories and replaced with a copy of the indicated program.

55. The computer readable medium of claim 54 wherein the at least one stored program copies selected for removal are less recently used than other stored copies of programs.

56. The computer-readable medium of claim 40 wherein the method further comprises, in response to a received indication of another program for later execution, sending to one or more computing machines an indication to store a local copy of the another program for later use.

57. The computer-readable medium of claim 40 wherein the method further comprises repeatedly receiving status information regarding at least some of the plurality of computing machines, and wherein the automatic selecting of the one or more computing machines is based at least in part on received status information.

58. The computer-readable medium of claim 57 wherein the status information includes at least one of an indication of copies of programs that are stored, an indication of instances of programs that are being executed, and an indication of resource utilization of programs that are being executed.

59. The computer-readable medium of claim 40 wherein the method further comprises determining to migrate at least one currently executing program from a first of the plurality of computing machines to a second of the plurality of computing machines, and initiating migration of the at least one executing programs to the second computing machine.

60. The computer-readable medium of claim 40 wherein at least some of the plurality of computing machines are each configured to execute multiple programs concurrently.

61. The computer-readable medium of claim 60 wherein the at least some computing machines each host multiple virtual machines that are each able to execute at least one program, and wherein the indicated program is a virtual machine image to be executed by at least one of the virtual machines.

62. The computer-readable medium of claim 40 wherein the determining to execute the at least one instance of the indicated program is based on a request received from a user that indicates a number of instances desired to be executed.

63. The computer-readable medium of claim 62 wherein the received request further includes one or more indications related to one or more computing machines for use in executing the at least one instance of the indicated program, and wherein the automatic selecting of the one or more computing machines is further based on the one or more received indications.

64. The computer-readable medium of claim 62 wherein the method further comprises receiving multiple requests from multiple users to execute instances of multiple programs, and automatically selecting one or more computing machines for use with each of the requests.

65. The computer-readable medium of claim 64 wherein the multiple programs each have associated resource criteria such that at least some of the associated resource criteria will be used during execution of each instance of the program, and wherein the automatic selecting of the computing machines for use with the multiple requests includes associating multiple program instances to be executed on one or more computing machines such that the associated resource criteria of the multiple program instances exceeds available resources of the one or more computing machines.

66. The computer-readable medium of claim 40 wherein multiple instances of the indicated program are to be simultaneously executed on multiple computing machines, and wherein the automatic selecting of the one or more computing machines includes selecting multiple computing machines from multiple groups to execute the multiple instances in order to balance use of resources by the multiple instances.

67. The computer-readable medium of claim 40 wherein the computer-readable medium is a memory of a computing system.

68. The computer-readable medium of claim 40 wherein the computer-readable medium is a data transmission medium transmitting a generated data signal containing the contents.

69. The computer-readable medium of claim 40 wherein the contents are instructions that when executed cause the computing system to perform the method.

70. A system configured to manage execution of programs, comprising:

a memory; and

a system manager module configured to, in response to a determination to execute at least one instance of an indicated program, automatically select one or more computing machines for executing one or more instances of the indicated program, the selected computing machines being from one or more of multiple groups, the selecting of a computing system being based at least in part on the selected computing machine being a member of a group that includes one or more machines that have a stored copy of the indicated program.

71. The system of claim 70 further comprising multiple groups of computing machines such that each group includes multiple computing machines that share a common physical data connection not shared by computing machines external to the group, each computing machine being configured to execute at least one program, at least one machine of each group being configured to store copies of multiple programs.

72. The system of claim 71 wherein the common physical data connections shared by the multiple computing machines of the multiple groups are each provided by a distinct network switch.

73. The system of claim 71 further comprising multiple machine manager modules each associated with one of the multiple groups and each configured to, in response to a determination to execute at least one instance of an indicated program of which at least one of the machines of the associated group has a stored copy, facilitate obtaining a copy of the indicated program for execution from one or more of the at least one machines via the common physical data connection shared by the multiple computing machines of the associated group.

74. The system of claim 73 wherein the system is operated by a program execution service and further comprises a remote storage module that is accessible to the multiple machines of the multiple groups and that is configured to store copies of multiple programs from customers of the program execution service and to provide a copy of one of the multiple programs in response to a received request.

75. The system of claim 74 wherein the multiple machine manager modules are each further configured to, in response to an indication of a program of which none of the machines of the associated group for the machine manager module has a stored copy, facilitate obtaining a copy of the indicated program from the remote storage module.

76. The system of claim 75 wherein the multiple machine manager modules are each further configured to, after an indication of a program of which none of the machines of the associated group for the machine manager module has a stored copy and in response to a determination to execute at least one instance of the indicated program, determine whether any of the multiple groups of computing machines have at least one machine that stores a copy of the indicated program and facilitate obtaining a copy of the indicated program from one or more machines of one or more of the multiple groups if any are determined to store a copy of the indicated program.

77. The system of claim 76 wherein the facilitating of the obtaining of a copy of an indicated program from the remote storage module is performed only if none of the multiple groups of computing machines are determined to have at least one machine that stores a copy of the indicated program.

78. The system of claim 73 wherein the multiple machine manager modules are each further configured to initiate execution of an obtained copy of a program on at least one of the computing machines of the associated group for the machine manager module.

79. The system of claim 78 wherein the system manager module is further configured to, after selecting a computing machine of one of the multiple groups for executing an instance of an indicated program, send instructions to a machine manager module associated with the one group to provide a determination to execute at least one instance of the indicated program and to provide information to facilitate determining whether at least one of the machines of the one group has a stored copy of the indicated program.

80. The system of claim 73 wherein each of the computing machines executes one of the multiple machine manager modules, wherein the facilitating of the obtaining of a copy of an indicated program by a machine manager module includes obtaining the indicated program copy, and wherein each machine manager module is further configured to initiate execution of an obtained program copy on the computing machine executing the machine manager module.

81. The system of claim 73 wherein the system manager module and the multiple machine manager modules each include software instructions for execution in memory of one or more computing machines of the system.

82. The system of claim 70 wherein the system manager module consists of a means for, in response to a determination to execute at least one instance of an indicated program, automatically selecting one or more computing machines for executing one or more instances of the indicated program, the selected computing machines being from one or more of multiple groups, the selecting of a computing system being based at least in part on the selected computing machine being a member of a group that includes one or more machines that have a stored copy of the indicated program.

83. The system of claim 70 wherein at least some of the selected computing machines each host multiple virtual machines that are each able to execute at least one program, and wherein the indicated program is a virtual machine image to be executed by at least one of the virtual machines.