Distributed system with asynchronous execution systems and methods

• US 20060101062A1
• Filed: 10/28/2005
• Published: 05/11/2006
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Schack, Darren P., Godman, Peter J.
• Granted Patent: US 8,051,425 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Systems and methods are provided for reducing latency in distributed systems by executing commands as sufficient information and system resources become available. In one embodiment, commands in a transaction include dependency information and an execution engine is configured to execute the commands as the dependencies become satisfied. In some embodiments, the commands also include priority information. If sufficient resources are not available to execute two or more commands with satisfied dependencies, the execution engine determines an order for executing the commands based at least in part on the priority information. In one embodiment, time-intensive commands are assigned a higher priority than commands that are expected to take less time to execute.

Claims

1. A method of performing a transaction in a distributed system, the method comprising:

providing a first command and a second command that define functions to be performed in the transaction, wherein the first command further defines a dependency;

holding the first command in a waiting state until the dependency is satisfied;

prioritizing the first command and second command; and

executing the first command and the second command in an order based at least in part on the prioritization.

2. The method of claim 1, wherein the dependency is such that the first command depends on data made available by the second command.

3. The method of claim 1, wherein prioritizing the first command and the second command comprises setting a priority flag in the first commands.

4. The method of claim 1, wherein executing the first command comprises performing the function defined by the first command on a local node.

5. The method of claim 4, wherein executing the second command comprises:

transmitting the second command to a remote node; and

performing the functions defined by the second command on the remote node, wherein the remote node determines when to perform the functions thereon.

6. The method of claim 5, further comprising:

storing data returned by the remote node in a remote cache; and

transferring the data from the remote cache to a local cache corresponding to the local node.

7. A distributed system comprising:

a plurality of nodes configured to participate in a transaction through a computer network, wherein the transaction comprises commands with dependencies;

a layout manager module configured to determine in which one of the plurality of nodes to write blocks of data; and

an execution manager module configured to process the commands based at least in part on the dependencies.

8. The distributed system of claim 7, wherein the nodes comprise smart storage units.

9. The distributed system of claim 8, wherein the transaction is selected from a group comprising one or more of:

a write transaction;

a mirror transaction;

a mirror recovery transaction;

a parity write transaction; and

a restripe transaction.

10. The distributed system of claim 7, wherein the dependencies define relationships among the commands.

11. The distributed system of claim 7, wherein execution manager module processes the commands in one or more states comprising:

a waiting state, wherein the execution manager module holds the commands until their respective dependencies are satisfied;

a runnable state, wherein the execution manager determines resources available to execute the commands; and

a running state wherein one or more of the plurality of nodes execute the commands.

12. The distributed system of claim 11, wherein the commands comprise priority information and the execution manager module holds the commands in the runnable state until their respective priorities are satisfied.

13. The distributed system of claim 11, further comprising a done state wherein the commands are no longer executed.

14. The distributed system of claim 13, wherein the execution manager module sets the commands to the done state upon detecting a failure.

15. The distributed system of claim 7, wherein the blocks of data comprise error correction information.

16. A method of processing commands in a distributed system, the method comprising:

defining dependencies for a plurality of commands;

setting the plurality of commands in a waiting state;

as dependencies are satisfied for particular commands, setting the particular commands in a runnable state; and

executing the particular commands in the runnable state as system resources become available.

17. The method of claim 16, further comprising:

defining priorities for the commands; and

holding the particular commands in the runnable state until the respective priorities are satisfied.

18. A network comprising a plurality of nodes configured to participate in a transaction over the network, wherein the transaction comprises a plurality of commands, wherein at least one of the commands comprises dependency information, and wherein the network executes the at least one command when the dependency information is satisfied.

19. The network of claim 18, wherein the dependency information indicates that the at least one command is not dependent on other commands.

20. The network of claim 18, wherein the at least one command further comprises priority information, and wherein the network executes the at least one command when the dependency information is satisfied and based on the priority information.