System and method for analyzing data records

• US 9,830,357 B2
• Filed: 08/02/2016
• Issued: 11/28/2017
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pike, Robert C., Quinlan, Sean, Dorward, Sean M., Dean, Jeffrey, Ghemawat, Sanjay
• Primary Examiner(s): Park, Grace
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US15/226,795
• Publication Number:
  US 20160342657A1
• Time in Patent Office: 483 Days
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method processes data records. The method partitions the data records into groups and assigns each group to a respective process of a first plurality of processes, which execute in parallel. For each group, the assigned process extracts information from the data records, applies a script with information processing commands applied sequentially to produce intermediate values, stores the intermediate values in a respective intermediate data structure, and updates the status of the group to indicate completion. When the predefined threshold percentage of the data records are completed, the process assigns each group to a respective second process as a backup. When each of the groups has been completed by at least one process (either the original or the backup), the method executes a second plurality of processes to aggregate intermediate values from the intermediate data structures to produce output data. The aggregation includes intermediate values only once for each group.

Claims

1. A computer-implemented method of processing a plurality of data records, performed on a system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the computer-implemented method, comprising:

partitioning the plurality of data records into groups and assigning each group of data records to a respective process of a first plurality of processes;

executing the first plurality of processes in parallel, wherein for each group the assigned process;

extracts information from the data records in the group;

applies a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more intermediate values;

stores the one or more intermediate values in a respective intermediate data structure in a plurality of intermediate data structures; and

updates a status of the group to indicate completion;

determining whether at least a predefined threshold percentage of the plurality of data records are completed based on the status updates provided by the first plurality of processes, wherein the predefined threshold percentage is a predetermined value that is less than all the first plurality of data records;

when it is determined that the predefined threshold percentage of the plurality of data records are completed, assigning each group of data records that is not completed to a respective second process of the first plurality of processes;

when it is determined that each of the groups in the plurality of groups has been completed by at least one process, executing a second plurality of processes to aggregate intermediate values from the intermediate data structures to produce output data, wherein the aggregation includes intermediate values only once for each group in the plurality of groups.

2. The computer-implemented method of claim 1, wherein the predetermined value is 90 percent of the first plurality of data records.

3. The computer-implemented method of claim 1, wherein the predetermined value is 95 percent of the first plurality of data records.

4. The computer-implemented method of claim 1, wherein the predetermined value is 99 percent of the first plurality of data records.

5. The computer-implemented method of claim 1, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

6. The computer-implemented method of claim 1, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

7. The computer-implemented method of claim 1, wherein a respective intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the respective intermediate data structure.

8. The computer-implemented method of claim 1, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the computer-implemented method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

9. The computer-implemented method of claim 1, wherein

a first process in the first plurality of processes generates a first intermediate data structure in the plurality of intermediate data structures, the first intermediate data structure having a first key,

a second process in the first plurality of processes generates a second intermediate data structure in the plurality of intermediate data structures, the second intermediate data structure having a second key, wherein the first key and the second key are the same, and

a process in the second plurality of processes aggregates (i) values from the first intermediate data structure indexed to the first key and (ii) values from the second intermediate data structure indexed to the second key to produce all or a portion of the output data.

10. A system for processing a plurality of data records, comprising:

one or more processors; and

memory storing one or more programs to be executed by the one or more processors;

the one or more programs comprising instructions for;

partitioning the plurality of data records into groups and assigning each group of data records to a respective process of a first plurality of processes;

executing the first plurality of processes in parallel, wherein for each group the assigned process;

extracts information from the data records in the group;

applies a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more intermediate values;

stores the one or more intermediate values in a respective intermediate data structure in a plurality of intermediate data structures; and

updates a status of the group to indicate completion;

determining whether at least a predefined threshold percentage of the plurality of data records are completed based on the status updates provided by the first plurality of processes, wherein the predefined threshold percentage is a predetermined value that is less than all the first plurality of data records;

when it is determined that the predefined threshold percentage of the plurality of data records are completed, assigning each group of data records that is not completed to a respective second process of the first plurality of processes;

when it is determined that each of the groups in the plurality of groups has been completed by at least one process, executing a second plurality of processes to aggregate intermediate values from the intermediate data structures to produce output data, wherein the aggregation includes intermediate values only once for each group in the plurality of groups.

11. The system of claim 10, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

12. The system of claim 10, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

13. The system of claim 10, wherein a respective intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the respective intermediate data structure.

14. The system of claim 10, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the computer-implemented method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.

15. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:

partitioning a plurality of data records into groups and assigning each group of data records to a respective process of a first plurality of processes;

executing the first plurality of processes in parallel, wherein for each group the assigned process;

extracts information from the data records in the group;

applies a multi-step script comprising a plurality of information processing commands applied sequentially to the extracted information to produce one or more intermediate values;

stores the one or more intermediate values in a respective intermediate data structure in a plurality of intermediate data structures; and

updates a status of the group to indicate completion;

determining whether at least a predefined threshold percentage of the plurality of data records are completed based on the status updates provided by the first plurality of processes, wherein the predefined threshold percentage is a predetermined value that is less than all the first plurality of data records;

when it is determined that the predefined threshold percentage of the plurality of data records are completed, assigning each group of data records that is not completed to a respective second process of the first plurality of processes;

when it is determined that each of the groups in the plurality of groups has been completed by at least one process, executing a second plurality of processes to aggregate intermediate values from the intermediate data structures to produce output data, wherein the aggregation includes intermediate values only once for each group in the plurality of groups.

16. The non-transitory computer readable storage medium of claim 15, wherein an intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices.

17. The non-transitory computer readable storage medium of claim 15, wherein a data record in the plurality of data records comprises a log file, a transaction record or a document.

18. The non-transitory computer readable storage medium of claim 15, wherein a respective intermediate data structure in the plurality of intermediate data structures is a table having a plurality of indices, wherein at least a subset of the plurality of indices is dynamically generated when one or more values are stored in the respective intermediate data structure.

19. The non-transitory computer readable storage medium of claim 15, wherein an intermediate data structure in the plurality of intermediate data structures is a table, the computer-implemented method further comprising initializing the table, wherein the table comprises a plurality of indices that are statically generated when the table is initialized.