Deterministic data processing

• US 8,910,188 B1
• Filed: 03/23/2012
• Issued: 12/09/2014
• Est. Priority Date: 07/14/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yuewei, Rudys, Algis P., Yang, Stewart
• Primary Examiner(s): Ho, Andy
• Assistant Examiner(s): Mudrick, Timothy A
• Application Number:
  US13/428,249
• Time in Patent Office: 991 Days
• Field of Search: 719/318
• US Class Current: 719/318
• CPC Class Codes: G06F 13/00 Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units interface circuits for specific input/output devices G06F3/00 ; multiprogram control therefor G06F9/46; multiprocessor systems G06F15/16
• CPC Class Codes: G06F 3/00 Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for processing event data. In one aspect, a method includes assigning events to event bundles based on timestamps associated with the events. Each event bundle contains events having timestamps that are within a pre-specified period of time. Event batches are created, where each event batch includes a pre-specified number of event bundles. A first event batch is provided to a first computing group and a second computing group. The first computing group is configured to perform a first processing stage, and the second computing group is configured to perform a second processing stage. A determination is made that a threshold number of the event bundles in the first event batch have been processed by the first computing group. In response to the determination, a second event batch is provided to each of the computing groups.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving event data specifying a set of events that have occurred, the set of events including advertising impressions and user interactions with advertisements, the event data for each event including a timestamp indicative of a time at which the event occurred;

assigning the events to event bundles based on the timestamps, each event bundle containing events having timestamps that are within a pre-specified period of time;

creating event batches, each event batch including a pre-specified number of event bundles;

providing, during a first processing cycle in which one or more processing stages are performed, a first event batch to each of a first computing group and a second computing group, each computing group including one or more data processing apparatus, the first computing group being a computing group that is configured to perform operations of a first processing stage, the second computing group being a computing group that is configured to perform operations of a second processing stage;

determining that a threshold number of the event bundles in the first event batch have been processed by the first computing group;

in response to the determination, providing, during a second processing cycle in which one or more processing stages are performed, a second event batch to each of the first computing group and the second computing group;

determining that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle; and

providing, during a third processing cycle in which one or more processing stages are performed, a third event batch to each of the first computing group and the second computing group based on the determination that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle.

2. The method of claim 1, wherein:

operations of the second processing stage comprise operations that are performed on first result data from the first processing stage, the first result data being data that are output as a result of the first processing stage; and

operations of a third processing stage comprise operations that are performed on second result data from the second processing stage, the second result data being data that are output as a result of the second processing stage.

3. The method of claim 1, wherein determining that a threshold number of event bundles in the first event batch have been processed by the first computing group comprises:

determining that all of the event bundles in the first event batch have been processed by the first computing group; and

determining that a first result from the first processing stage is available to be processed by the second computing group.

4. The method of claim 1, wherein assigning the events to event bundles comprises:

identifying a first set of events having timestamps specifying times that are in a first pre-specified period;

grouping the first set of events to a first event bundle, the first event bundle having a first event bundle identifier;

identifying a second set of events having timestamps specifying times that are in a second pre-specified period; and

grouping the second set of events to a second event bundle, the second event bundle having a second event bundle identifier having at least one different character than the first event bundle identifier.

5. The method of claim 4, wherein the first pre-specified period and the second pre-specified period are temporally adjacent periods and have a matching duration.

6. The method of claim 1, wherein creating event batches comprises creating event batches in which two or more of the event batches include a same number of event bundles.

7. The method of claim 1, further comprising:

receiving, by the first computing group that performs operations of a first processing stage, the first event batch;

processing event data for the events that belong to first event batch;

determining that processing of the first event batch has been completed; and

logging first results of the first processing stage to a data store.

8. The method of claim 7, wherein determining that processing of the first batch has been completed comprises determining that a threshold number of event bundles from the first batch has been processed.

9. The method of claim 7, further comprising:

receiving, by a second computing group that performs operations of a second processing stage, the first event batch;

preventing the first event batch from being processed by the second computing group until the first results have been logged;

determining that the first results have been logged; and

processing the first results and event data for the events that belong to the first event batch, the processing including performing the operations of the second processing stage; and

logging second results of the second processing stage.

10. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving event data specifying a set of events that have occurred, the set of events including advertising impressions and user interactions with advertisements, the event data for each event including a timestamp indicative of a time at which the event occurred;

assigning the events to event bundles based on the timestamps, each event bundle containing events having timestamps that are within a pre-specified period of time;

creating event batches, each event batch including a pre-specified number of event bundles;

providing, during a first processing cycle, a first event batch to each of a first computing group and a second computing group, each computing group including one or more data processing apparatus, the first computing group being a computing group that is configured to perform operations of the first processing stage, the second computing group being a computing group that is configured to perform operations of a second processing stage;

determining that a threshold number of the event bundles in the first event batch have been processed by the first computing group;

in response to the determination, during a second processing cycle, a second event batch to each of the first computing group and the second computing group;

determining that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle; and

providing, during a third processing cycle, a third event batch to each of the first computing group and the second computing group based on the determination that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle.

11. A system comprising:

a data store storing event data for a plurality of events specifying a set of events that have occurred, the set of events including advertising impressions and user interactions with advertisements, the event data for each event including a timestamp indicative of a time at which the event occurred; and

an event processing apparatus configured to interact with the data store and to perform operations comprising;

receiving event data;

assigning the events to event bundles based on the timestamps, each event bundle containing events having timestamps that are within a pre-specified period of time;

creating event batches, each event batch including a pre-specified number of event bundles;

providing, during processing cycle in which one or processing stages are performed, a first event batch to each of a first computing group and a second computing group, each computing group including one or more data processing apparatus, the first computing group being a computing group that is configured to perform operations of a first processing stage, the second computing group being a computing group that is configured to perform operations of a second processing stage;

determining that a threshold number of the event bundles in the first event batch have been processed by the first computing group;

in response to the determination, during a second processing cycle in which one or more processing stages are performed, a second event batch to each of the first computing group and the second computing group;

determining that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle; and

providing, during a third processing cycle in which one or more processing stages are performed, a third event batch to each of the first computing group and the second computing group based on the determination that the threshold number of the event bundles in the first event batch and results from the first processing stage have been processed by the second computing group during the second processing cycle.

12. The system of claim 11, wherein:

operations of the second processing stage comprise operations that are performed on first result data from the first processing stage, the first result data being data that are output as a result of the first processing stage; and

operations of a third processing stage comprise operations that are performed on second result data from the second processing stage, the second result data being data that are output as a result of the second processing stage.

13. The system of claim 11, wherein determining that a threshold number of event bundles in the first event batch have been processed by the first computing group comprises:

determining that all of the event bundles in the first event batch have been processed by the first computing group; and

determining that a first result from the first processing stage is available to be processed by the second computing group.

14. The system of claim 11, wherein assigning the events to event bundles comprises:

identifying a first set of events having timestamps specifying times that are in a first pre-specified period;

grouping the first set of events to a first event bundle, the first event bundle having a first event bundle identifier;

identifying a second set of events having timestamps specifying times that are in a second pre-specified period; and

grouping the second set of events to a second event bundle, the second event bundle having a second event bundle identifier having at least one different character than the first event bundle identifier.

15. The system of claim 14, wherein the first pre-specified period and the second pre-specified period are temporally adjacent periods and have a matching duration.

16. The system of claim 11, wherein creating event batches comprises creating event batches in which two or more of the event batches include a same number of event bundles.

17. The system of claim 11, wherein the event processing apparatus is further configured to perform operations including:

receiving, by the first computing group that performs operations of a first processing stage, the first event batch;

processing event data for the events that belong to first event batch;

determining that processing of the first event batch has been completed; and

logging first results of the first processing stage to a data store.

18. The system of claim 17, wherein determining that processing of the first batch has been completed comprises determining that a threshold number of event bundles from the first batch has been processed.

19. The system of claim 17, wherein the event processing apparatus is further configured to perform operations including:

receiving, by a second computing group that performs operations of a second processing stage, the first event batch;

preventing the first event batch from being processed by the second computing group until the first results have been logged;

determining that the first results have been logged; and

processing the first results and event data for the events that belong to the first event batch, the processing including performing the operations of the second processing stage; and

logging second results of the second processing stage.