Data caching for distributed execution computing

• US 8,229,968 B2
• Filed: 03/26/2008
• Issued: 07/24/2012
• Est. Priority Date: 03/26/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Taifeng, Liu, Tie-Yan, Liu, Minghao, Chen, Zhi
• Primary Examiner(s): Lee, Wilson
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US12/055,777
• Publication Number:
  US 20090249004A1
• Time in Patent Office: 1,581 Days
• Field of Search: 707/748, 707/798
• US Class Current: 707/798
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Embodiments for caching and accessing Directed Acyclic Graph (DAG) data to and from a computing device of a DAG distributed execution engine during the processing of an iterative algorithm. In accordance with one embodiment, a method includes processing a first subgraph of the plurality of subgraphs from the distributed storage system in the computing device. The first subgraph being processed with associated input values in the computing device to generate first output values in an iteration. The method further includes storing a second subgraph in a cache of the device. The second subgraph being a duplicate of the first subgraph. Moreover, the method also includes processing the second subgraph with the first output values to generate second output values if the device is to process the first subgraph in each of one or more subsequent iterations.

Claims

1. A method, comprising:

storing a plurality of subgraphs of a directed acyclic graph (DAG) in a remote global data storage of a distributed storage system;

processing multiple subgraphs of the plurality of subgraphs in multiple computing devices of a DAG distributed execution engine, each of the multiple computing devices produces a vertex based on a corresponding subgraph and corresponding input values;

processing a first subgraph of the plurality of subgraphs from the remote global data storage with associated input values in a computing device of the DAG distributed execution engine in a first iteration by at least producing a vertex using the first subgraph and the associated input values, and aggregating the vertex with vertices produced by the multiple computing devices to generate first output values;

storing a second subgraph that is a copy of the first subgraph into a local cache of the computing device via a network that connects the local cache to the remote global data storage; and

processing the second subgraph with the first output values to generate a second output values in response to determining that the computing device is to process the first subgraph in a second iteration,

wherein the DAG represents a sparse matrix of linkage information between web pages, each of the associated input values represents a rank value of a source web page to associated destination web pages, and each output value represents a rank value of the source web page to other source web pages.

2. The method of claim 1, further comprising processing a third subgraph stored in the remote global data storage of the distributed storage system with the second output values to generate second output values in response to determining that the computing device is to process the third subgraph in the second iteration.

3. The method of claim 1, wherein the second iteration occurs consecutively or non-consecutively after the first iteration.

4. The method of claim 1, wherein the storing the second subgraph into the local cache includes storing the second subgraph into at least one of a memory cache or a disk cache of the computing device.

5. The method of claim 1, wherein storing the second subgraph into the local cache includes creating a memory map file for the second subgraph.

6. The method of claim 5, wherein processing the second subgraph includes accessing the second subgraph using the memory map file.

7. The method of claim 1, wherein the plurality of subgraphs are read-only data files.

8. The method of claim 1, wherein the associated input values are initial input values or output values from another iteration.

9. A computer readable memory having computer-executable instructions that, when executed, perform acts comprising:

storing a plurality of subgraphs of a directed acyclic graph (DAG) in a remote global data storage of a distributed storage system;

processing multiple subgraphs of the plurality of subgraphs in multiple computing devices of a DAG distributed execution engine, each of the multiple computing devices producing a vertex based on a corresponding subgraph and corresponding input values;

processing a first subgraph of the plurality of subgraphs from the remote global data storage with associated input values in a computing device of the DAG distributed execution engine in an iteration by at least producing a vertex using the first subgraph and the associated input values, and aggregating the vertex with vertices produced by the multiple computing devices to generate first output values;

storing a second subgraph that is a copy of the first subgraph into a local cache of the computing device via a network that connects the local cache to the remote global data storage; and

processing the second subgraph with the first output values to generate second output values in a subsequent iteration,

wherein the DAG represents a sparse matrix of linkage information between web pages, each of the associated input values represents a rank value of a source web page to associated destination web pages, and each output value represents a rank value of the source web page to other source web pages.

10. The computer readable memory of claim 9, wherein the storing the second subgraph into the local cache includes creating a file identifier for the second subgraph.

11. The computer readable memory of claim 10 wherein processing the second subgraph includes using the file identifier as a handle to access the second subgraph.

12. The computer readable memory of claim 9, wherein the storing the second subgraph into the local cache includes storing the subgraph in at least one of a memory cache or a disk cache.

13. The computer readable memory of claim 9, wherein each of the associated input values is an initial input value or an output value from another iteration.

14. A Directed Acyclic Graph (DAG) distributed execution engine, the engine comprising:

a network;

a plurality of computing devices connected by the network, each computing device including;

one or more processors; and

memory to store a plurality of computer-executable instructions for execution by the one or more processors, the computer-executable instructions comprising;

storing a plurality of subgraphs of a DAG in a remote global data storage of a distributed storage system;

processing multiple subgraphs of the plurality of subgraphs in multiple computing devices of the DAG distributed execution engine, wherein each of the multiple computing devices produces a vertex based on a corresponding subgraph and corresponding input values;

processing a first subgraph of the plurality of subgraphs from the remote global data storage with associated input values in a computing device in a first iteration by at least producing a vertex using the first subgraph and the associated input values, and aggregating the vertex with vertices produced by the multiple computing devices to generate first output values;

storing a second subgraph that is a copy of the first subgraph in a local cache of the computing device in response to determining that a number of times that the first subgraph has been processed by the computing device exceeds a predetermined threshold; and

processing the second subgraph with the first output values to generate second output values in a second iteration that occurs after the first iteration,

wherein the DAG represents a sparse matrix of linkage information between web pages, each of the associated input values represents a rank value of a source web page to associated destination web pages, and each output value represents a rank value of the source web page to other source web pages.

15. The engine of claim 14, wherein the processing the second subgraph includes for propagating a vertex using the second subgraph and the first output values.

16. The engine of claim 14, wherein the second iteration occurs consecutively or non-consecutively after the first iteration.

17. The engine of claim 14, wherein each of the associated input values is and initial input value or an output value from another iteration.