Incremental parallel processing of data

Patent metadata

Field	Value
Publication number	US-10025620-B2
Application number	US-201614989867-A
Country	US
Kind code	B2
Filing date	Jan 7, 2016
Priority date	Apr 1, 2014
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

One example method includes identifying synchronous code including instructions specifying a computing operation to be performed on a set of data; transforming the synchronous code into a pipeline application including one or more pipeline objects; identifying a first input data set on which to execute the pipeline application; executing the pipeline application on a first input data set to produce a first output data set; after executing the pipeline application on the first input data set, identifying a second input data set on which to execute the pipeline application; determining a set of differences between the first input data set and second input data set; and executing the pipeline application on the set of differences to produce a second output data set.

First claim

What is claimed is:

1. A computer-implemented method executed by one or more processors, the method comprising:
identifying a first input data set on which to execute a pipeline application that includes pipeline objects, the pipeline application configured to be executed in parallel across a plurality of computing devices, each of the pipeline objects configured to receive an input data set and produce an output data set;
executing the pipeline application on a first input data set to produce a first output data set, the executing the pipeline application including executing each of the pipeline objects in order such that a first pipeline object of the pipeline objects provides output data as input data to a second pipeline object of the pipeline objects and including:
determining a pipeline object state for each of the pipeline objects in response to executing the pipeline application on the first input data set, each of the pipeline object states including a representation of a respective input data set and a respective output data set for the respective pipeline object;

identifying a second input data set on which to execute the pipeline application;
determining a set of differences between the first input data set and the second input data set, where the set of difference indicates that the second input data set adds a first item to items in the first data set and removes a second item from the items in the first data set; and
executing the pipeline application on the set of differences that indicates that the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set to produce a second output data set that is the same as an output data set that the pipeline application would produce from execution on the second data set, the executing the pipeline application on the set of differences that indicates that the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set including executing each of the pipeline objects in order such that the first pipeline object of the pipeline objects provides second output data as second input data to the second pipeline object of the pipeline objects and including:
updating the pipeline object states in response to executing the pipeline application on the set of differences between the first input data set and the second input data set to generate an updated pipeline object state for each of the pipeline objects, each of the updated pipeline object states including differences from the respective input data set and the respective output data set for the respective pipeline object.

2. The method of claim 1 , further comprising determining a pipeline state in response to executing the pipeline application on the first input data set, the pipeline state including a representation of the first input data set and the first output data set.

3. The method of claim 2 , further comprising updating the pipeline state in response to executing the pipeline application on the set of differences from the first input data set to generate an updated pipeline state, the updated pipeline state including a representation of the second input data set and the second output data set.

4. The method of claim 1 , wherein identifying the first input data set on which to execute the pipeline application comprises:
transforming the first input data set into a first set of key value pairs; and
storing the first set of key value pairs in a key value store.

5. The method of claim 4 , wherein determining the set of differences between the first input data set and the second input data set comprises:
transforming the second input data set into a second set of key value pairs;
comparing the second set of key value pairs to the first set of key value pairs; and
identifying key value pairs that have been added or deleted from the second set of key value pairs relative to the first set of key value pairs.

6. The method of claim 1 , wherein determining the set of differences between the first input data set and the second input data set comprises:
determining a last execution timestamp for the pipeline application representing a time at which the pipeline application was executed on the first input data set; and
identifying a set of items in the second input data set including timestamps after the last execution timestamp.

7. The method of claim 1 , wherein executing the pipeline application on the set of differences that indicates the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set to produce a second output data set that is the same as an output data set that the pipeline application would produce from execution on the second data set comprises:
producing a third output set from executing the pipeline application on the set of differences that indicates the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set; and
applying the third output set to the first output data set to produce the second output set.

8. A system comprising:
memory for storing data; and
one or more processors operable to access the memory and perform operations comprising:
identifying a first input data set on which to execute a pipeline application that includes pipeline objects, the pipeline application configured to be executed in parallel across a plurality of computing devices, each of the pipeline objects configured to receive an input data set and produce an output data set;
executing the pipeline application on a first input data set to produce a first output data set, the executing the pipeline application including executing each of the pipeline objects in order such that a first pipeline object of the pipeline objects provides output data as input data to a second pipeline object of the pipeline objects and including:
determining a pipeline object state for each of the pipeline objects in response to executing the pipeline application on the first input data set, each of the pipeline object states including a representation of a respective input data set and a respective output data set for the respective pipeline object;

identifying a second input data set on which to execute the pipeline application;
determining a set of differences between the first input data set and the second input data set, where the set of difference indicates that the second input data set adds a first item to items in the first data set and removes a second item from the items in the first data set; and
executing the pipeline application on the set of differences that indicates that the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set to produce a second output data set that is the same as an output data set that the pipeline application would produce from execution on the second data set, the executing the pipeline application on the set of differences that indicates that the second input data set adds the first item to items in the first data set and removes the second item from the items in the first data set including executing each of the pipeline objects in order such that the first pipeline object of the pipeline objects provides second output data as second input data to the second pipeline object of the pipeline objects and including:
updating the pipeline object states in response to executing the pipeline application on the set of differences between the first input data set and the second input data set to generate an updated pipeline object state

Assignees

• Google Llc

Inventors

• Bradshaw Robert
• Chambers Craig D
• Cooper Ezra
• Raniwala Ashish
• Perry Frances J

Classifications

• G06F16/24534

  Query rewriting; Transformation · CPC title

• G06F16/51

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/235

  Update request formulation · CPC title

• G06F16/258

  Data format conversion from or to a database · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title