Determinism for distributed applications

• US 9,804,945 B1
• Filed: 01/03/2013
• Issued: 10/31/2017
• Est. Priority Date: 01/03/2013
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Allen, Nicholas Alexander
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US13/733,763
• Time in Patent Office: 1,762 Days
• Field of Search: 714 381
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06

Abstract

Systems and methods are described for analyzing and verifying distributed application programs. In one embodiment, an application program is divided into as one or more independently executable components. During execution of the independently executable components, non-deterministic events are modified in order to effectuate deterministic results. The non-deterministic events may be modified in accordance with a predetermined set of constraints.

Claims

1. A computing system comprising one or more computing nodes and one or more data stores in communication with the one or more computing nodes, the one or more data stores having stored thereon:

policy information comprising one or more determinism policies indicative of non-deterministic program conditions, responses to determinism violations, and criteria for dividing program code; and

computer instructions that, upon execution by the one or more computing nodes, at least cause the computing system to;

receive an application program operable for execution in a distributed computing environment comprising one or more computing devices;

divide the application program into executable components in accordance with the criteria for dividing program code, the executable components being separately executable as independent processes;

execute the executable components in a plurality of containers configured to instantiate an execution space for executing the executable components, wherein the containers are configured to independently execute the executable components using one or more shared states and wherein relationships between the executable components are defined by the one or more determinism policies; and

in response to a determination that a non-deterministic event has occurred between at least two of the plurality of containers in accordance with the one or more determinism policies, applying one or more responses to the non-deterministic event in accordance with the one or more determinism policies in order to effectuate a deterministic result, wherein the one or more responses comprise terminating one of the plurality of containers.

2. The computing system according to claim 1, wherein the one or more data stores further store thereon one or more launch configurations describing a program environment.

3. The computing system according to claim 1, wherein the determination that a non-deterministic event has occurred is performed in part by trapping operations between the containers and synchronizing the shared states, and wherein the non-deterministic event is modified by delaying or reordering.

4. The computing system according to claim 1, wherein the determination that a non-deterministic event has occurred is performed in part by trapping file system requests or network requests.

5. The computing system according to claim 1, wherein the one or more determinism policies indicate deterministic boundaries between threads, processes, or applications.

6. A computer-implemented method for executing distributed application programs, the method comprising:

dividing an application program into a plurality of components that are independently executable in accordance with determinism boundaries for which determinism is enforced, the application program being operable to execute in a distributed computing environment;

independently executing the plurality of components in a plurality of containers configured to instantiate an execution space for executing the plurality of components to enforce the determinism boundaries, and

replacing non-deterministic events between two or more of the plurality of containers with deterministic events in accordance with a predetermined set of responses to the non-deterministic events, wherein one of the plurality of containers is terminated in association with the predetermined set of responses.

7. The method of claim 6 wherein the application program is divided in accordance with criteria for dividing program code during executing of the application program.

8. The method of claim 6, wherein the plurality of containers are implemented in a plurality of virtual machines, wherein the plurality of virtual machines are configured to independently execute the plurality of components and wherein relationships between the plurality of components are defined by one or more determinism policies.

9. The method of claim 6, wherein said replacing is in response to a determination that a non-deterministic event has occurred in accordance with one or more determinism policies.

10. The method of claim 6, wherein the plurality of components are arranged as an acyclic directed graph of executable component relationships.

11. The method of claim 6, wherein said replacing is performed by one or more mediation functions configured to enforce the predetermined set of responses.

12. The method of claim 6, wherein the replacing comprises applying a fixed ordering.

13. The method of claim 12, wherein the fixed ordering comprises a repeatable order for performing memory reads and writes.

14. The method of claim 6, wherein the responses include groupings of identifiable execution units that override deterministic boundaries.

15. The method of claim 6, wherein the responses include access permissions for nondeterministic input sources.

16. The method of claim 6, further comprising invoking a debugger in response to a non-deterministic event.

17. The method of claim 6, wherein said dividing is performed based on configuration information describing the distributed computing environment.

18. The method of claim 17, wherein the configuration information is indicative of resources for executing a thread, process, application, or other unit of execution identified as having a determinism boundary.

19. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to:

cause separate execution of a plurality of independently executable components in a plurality of containers in accordance with determinism boundaries for which determinism is enforced, wherein the plurality of independently executable components are derived from an application program operable to execute in a distributed computing environment, and wherein the plurality of containers are configured to instantiate an execution space for executing the independently executable components; and

in response to a determination that a non-deterministic event has occurred between at least two of the plurality of containers in accordance with non-deterministic program conditions defined by one or more determinism policies, replace the non-deterministic event with a deterministic event in accordance with the one or more determinism policies, wherein one of the plurality of containers is terminated in association with the one or more determinism policies.

20. The one or more non-transitory computer-readable storage media of claim 19, wherein the plurality of independently executable components are arranged as an acyclic directed graph indicative of relationships between the plurality of independently executable components.

21. The one or more non-transitory computer-readable storage media of claim 19 wherein the plurality of independently executable components comprise a mediation function to enforce the one or more determinism policies.

22. The one or more non-transitory computer-readable storage media of claim 19 wherein the determination is based on trapping operations between the plurality of containers.

23. The one or more non-transitory computer-readable storage media of claim 22 wherein the trapped operations are completed in a designated container.

24. A computing system comprising one or more computing nodes and one or more data stores in communication with the one or more computing nodes, the one or more data stores having stored thereon computer instructions that, upon execution by the one or more computing nodes, at least cause the computing system to:

divide an application program into a plurality of components that are independently executable in accordance with determinism boundaries for which determinism is enforced, the application program being operable to execute in a distributed computing environment;

independently execute the plurality of components in a plurality of containers configured to instantiate an execution space for executing the plurality of components; and

replace non-deterministic events between the plurality of containers with deterministic events in accordance with a predetermined set of responses to the non-deterministic events, wherein one of the plurality of containers is terminated in association with the predetermined set of responses.

25. The computing system of claim 24, wherein the application program is divided in accordance with criteria for dividing program code during executing of the application program.

26. The computing system of claim 24, wherein the plurality of components are arranged as an acyclic directed graph of executable component relationships.

27. The computing system of claim 24, wherein the non-deterministic events are replaced at least in part by applying a fixed ordering.