PARALLEL PROCESSING OF DATA

• US 20110276962A1
• Filed: 12/02/2010
• Published: 11/10/2011
• Est. Priority Date: 05/04/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tigani, Jordan, Perry, Frances J., Chambers, Craig D., Raniwala, Ashish, Henry, Robert R.
• Granted Patent: US 8,887,156 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

An untrusted application is received at a data center including one or more processing modules and providing a native processing environment. The untrusted application includes a data parallel pipeline. Secured processing environments are used to execute the untrusted application.

Claims

1. A method comprising:

receiving, at a data center including one or more processing modules and providing a native processing environment, an untrusted application that includes a data parallel pipeline, wherein the data parallel pipeline specifies multiple parallel data objects that contain multiple elements and multiple parallel operations that are associated with untrusted functions that operate on the elements;

instantiating a first secured processing environment in the native processing environment and on one or more of the processing modules;

executing the untrusted application in the first secured processing environment, wherein executing the application generates a dataflow graph of deferred parallel data objects and deferred parallel operations corresponding to the data parallel pipeline;

communicating information representing the data flow graph outside of the first secured processing environment;

applying, outside of the first secured processing environment and in the native processing environment, one or more graph transformations to the information representing the dataflow graph to generate a revised dataflow graph that includes one or more of the deferred parallel data objects and deferred, combined parallel data operations that are associated with one or more of the untrusted functions; and

executing the deferred, combined parallel operations to produce materialized parallel data objects corresponding to the deferred parallel data objects, wherein executing the deferred, combined parallel operations comprises;

instantiating one or more second secured processing environments in the native processing environment and on one or more of the processing modules;

executing the untrusted functions associated with the deferred, combined parallel operations in the one or more second secured processing environments.

2. The method of claim 1 wherein the first secured processing environment comprises a first virtual machine and the one or more second secured processing environments comprises a second virtual machine.

3. The method of claim 2 wherein the first virtual machine and the one or more second virtual machines are hardware virtual machines.

4. The method of claim 1 wherein executing the untrusted functions associated with the deferred, combined parallel operations in the one or more second secured processing environments comprises:

communicating an input batch of records into the second secured processing environment from outside of the second secured processing environment, the input batch of records including multiple, individual input records; and

executing at least one of the untrusted functions associated with the deferred, combined parallel operations on each of the individual records in the input batch to generate output records;

collecting the output records into an output batch; and

communicating the output batch outside of the second secured processing environment.

5. The method of claim 1 further comprising sending an output of the untrusted application to a client system that sent the untrusted application to the data center.

6. The method of claim 1 wherein communicating the information representing the data flow graph outside of the first secured processing environment comprises communicating the information representing the data flow graph to an execute graph service outside of the first secured processing environment.

7. The method of claim 1 wherein:

the deferred, combined parallel data operations includes at least one generalized mapreduce operation, the generalized mapreduce operation including multiple, parallel map operations and multiple, parallel reduce operations and being translatable to a single mapreduce operation that includes a single map function to implement the multiple, parallel map operations and a single reduce function to implement the multiple, parallel reduce operations, the single map function and the single reduce function including one or more of the untrusted functions.

8. The method of claim 7 wherein:

executing the deferred, combined parallel operations comprises translating the combined mapreduce operation to the single mapreduce operation; and

executing the untrusted functions associated with the deferred, combined parallel operations in the one or more second secured processing environments comprises executing the single map function and the single reduce function in the one or more second secured processing environments.

9. The method of claim 1 wherein:

executing the untrusted application in the secured processing environment comprises executing the untrusted application within a virtual machine in the first secured processing environment; and

executing the untrusted functions associated with the deferred, combined parallel operations in the one or more secured processing environments comprises executing the untrusted functions associated with the deferred, combined parallel operations in a virtual machine within the one or more second secured processing environments.

10. The method of claim 1 wherein communicating information representing the data flow graph outside of the first secured processing environment comprises communicating information representing the data flow graph outside of the first secured processing environment using a remote procedure call.

11. The method of claim 10 further comprising auditing the remote procedure call.

12. A system comprising:

one or more processing modules configured to provide native processing environment and to implement the following;

a first secured processing environment in the native processing environment, the first secured processing environment configured to;

execute an untrusted application that includes a data parallel pipeline, the data parallel pipeline specifying multiple parallel data objects that contain multiple elements and multiple parallel operations that are associated with untrusted functions that operate on the elements;

wherein executing the application generates a dataflow graph of deferred parallel data objects and deferred parallel operations corresponding to the data parallel pipeline;

communicate information representing the data flow graph outside of the first secured processing environment;

a service located outside of the first secured processing environment and in the native processing environment, the service configured to;

receive the information representing the data flow graph from the first secured processing environment;

apply one or more graph transformations to the information representing the dataflow graph to generate a revised dataflow graph that includes one or more of the deferred parallel data objects and deferred, combined parallel data operations that are associated with one or more of the untrusted functions;

cause execution of the deferred, combined parallel operations to produce materialized parallel data objects corresponding to the deferred parallel data objects; and

one or more second secured processing environments in the native processing environment, the one or more second secured processing environments configured to execute the untrusted functions associated with the deferred, combined parallel operations to result in execution of the deferred, combined parallel operations.

13. The system of claim 12 wherein the first secured processing environment comprises a first virtual machine and the one or more second secured processing environments comprises a second virtual machine.

14. The system of claim 13 wherein the first virtual machine and the one or more second virtual machines are hardware virtual machines.

15. The system of claim 12 wherein:

the one or more processing devices are configured to implement a worker configured to communicate an input batch of records into the second secured processing environment from outside of the second secured processing environment, the input batch of records including multiple, individual input records; and

to execute the untrusted functions associated with the deferred, combined parallel operations, the one or more second secured processing environments are configured to;

execute at least one of the untrusted functions associated with the deferred, combined parallel operations on each of the individual records in the input batch to generate output records;

collect the output records into an output batch; and

communicate the output batch to the worker.

16. The system of claim 12 further comprising a client system configured to receive an output of the untrusted application.

17. The system of claim 12 wherein:

the deferred, combined parallel data operations includes at least one generalized mapreduce operation, the generalized mapreduce operation including multiple, parallel map operations and multiple, parallel reduce operations and being translatable to a single mapreduce operation that includes a single map function to implement the multiple, parallel map operations and a single reduce function to implement the multiple, parallel reduce operations, the single map function and the single reduce function including one or more of the untrusted functions.

18. The system of claim 17 wherein:

the service is configured to translate the combined mapreduce operation to the single mapreduce operation; and

the one or more second secured processing environments are configured to execute the single map function and the single reduce function in the one or more second secured processing environments.

19. The system of claim 12 wherein:

the first secured processing environment is configured to execute the untrusted application within a virtual machine in the first secured processing environment; and

the one or more second secured processing environments are configured to execute the untrusted functions associated with the deferred, combined parallel operations in a virtual machine within the one or more second secured processing environments.

20. A computer readable medium storing instructions that, when executed by one to or more processing devices, cause the one or more processing devices to:

access information representing a dataflow graph of deferred parallel data objects and deferred parallel operations, the deferred parallel data objects and deferred parallel operations corresponding to parallel data objects and parallel operations specified by a data parallel pipeline included in an untrusted application, wherein the parallel data objects contain multiple elements and the parallel operations are associated with untrusted functions that operate on the elements;

apply one or more graph transformations to the information representing the dataflow graph to generate a revised dataflow graph that includes one or more of the deferred parallel data objects and deferred, combined parallel data operations that are associated with one or more of the untrusted functions; and

execute the deferred, combined parallel operations to produce materialized parallel data objects corresponding to the deferred parallel data objects, wherein, to execute the deferred, combined parallel operations, the instructions comprise instructions that cause the one or more processing devices to;

instantiate one or more secured processing environments;

execute the untrusted functions associated with the deferred, combined parallel operations in the one or more secured processing environments.

21. The medium of 22 wherein, to access information representing the dataflow graph of deferred parallel data objects and deferred parallel operations, the instructions include instructions that, when executed by the one or more processing devices, cause the one or more processing devices to:

receive the untrusted application that includes the data parallel pipeline;

instantiate an initial secured processing environment;

execute the untrusted application in the initial secured processing environment, wherein executing the application generates the dataflow graph of deferred parallel data objects and deferred parallel operations; and

communicate the information representing the data flow graph outside of the initial secured processing environment such that the graph transformations are applied to the information representing the dataflow graph outside of the initial secured processing environment.

22. The medium of claim 21 wherein the one or more secured processing environments includes a virtual machine.