DETERMINISTIC PROGRESSIVE BIG DATA ANALYTICS

• US 20140372438A1
• Filed: 06/12/2013
• Published: 12/18/2014
• Est. Priority Date: 06/12/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandramouli, Badrish, Goldstein, Jonathan, Quamar, Abdul Hussain
• Granted Patent: US 9,514,214 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A plurality of data items that are annotated with progress markers may be obtained. The progress markers may indicate progress points associated with atemporal processing progress of the respective data items. Deterministic, massively parallel, progressive processing may be initiated on the plurality of data items on a plurality of devices, the progress markers indicating which of the plurality of data items are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data items into the results.

Claims

1. A system comprising:

a device that includes at least one processor, the device including a distributed progressive analytics engine comprising instructions tangibly embodied on a computer readable storage medium for execution by the at least one processor, the distributed progressive analytics engine including;

a data item acquisition component configured to obtain a plurality of data items that are annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data items; and

a progressive distributed processing manager configured to initiate deterministic, massively parallel, progressive processing of the plurality of data items on a plurality of devices, the progress markers indicating which of the plurality of data items are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data items into the results.

2. The system of claim 1, further comprising:

a map component configured to initiate progress-aware batching of sets of the plurality of data items, and progress-aware data flow of the plurality of data items, as part of progress-aware map-reduce operations that are included in the progressive processing.

3. The system of claim 2, further comprising:

a progressive data shuffle component configured to initiate sort-free progressive data shuffling, using grouping of sets of the plurality of data items, the grouping based on progress markers of respective data items included in the sets.

4. The system of claim 2, further comprising:

a progress-aware merging component configured to initiate progress-aware merging of portions of the plurality of data items.

5. The system of claim 4, further comprising:

a progress-aware reducer component configured to initiate the progress-aware merging of portions of the plurality of data items of the progress-aware merging component, at a reducer stage, as part of progress-aware map-reduce operations that are included in the progressive processing.

6. The system of claim 5, wherein:

the map component is configured to pipeline progress-batches from the map component to the progress-aware reducer component based on a signaling mechanism for indicating an availability for pipelining of respective ones of the progress-batches to a job tracker.

7. The system of claim 5, wherein:

the progress-aware reducer component includes a blocking concurrent queue (BCQ) configured to perform lock-free in-memory concurrent enqueue and dequeue operations.

8. The system of claim 5, wherein:

the progress-aware reducer component is implemented by a user.

9. The system of claim 5, wherein:

the reducer stage includes a streaming temporal engine that processes the progress markers substantially equivalently as processing of temporal fields.

10. The system of claim 1, wherein:

obtaining the plurality of data items that are annotated with progress markers includes receiving the plurality of data items that include data tuples that are user-augmented with respective progress intervals that indicate logical points where the data tuples enter and exit portions of computation included in the progressive processing.

11. The system of claim 10, wherein:

the respective progress intervals that indicate logical points where the data tuples enter and exit portions of computation included in the progressive processing are used to assign the respective data tuples to progressive samples.

12. The system of claim 1, wherein:

the progressive distributed processing manager is configured to initiate the deterministic, massively parallel, progressive processing that includes concurrent scheduling of multi-stage map and reduce jobs with a scheduling policy and flow control scheme.

13. A computer-readable storage medium storing executable instructions that are configured to cause one or more processors to:

obtain a plurality of data items that are annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data items; and

initiate deterministic, massively parallel, progressive processing of the plurality of data items on a plurality of devices, the progress markers indicating which of the plurality of data items are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data items into the results.

14. The computer-readable storage medium of claim 13, wherein:

initiating the deterministic, massively parallel, progressive processing includes initiating distributed progressive processing of the plurality of data items using progress-aware batching of sets of the plurality of data items, and progress-aware data flow of the plurality of data items.

15. The computer-readable storage medium of claim 14, wherein:

the progress-aware batching of sets of the plurality of data items includes progress-aware batching of the sets of the plurality of data items at a map stage of the distributed progressive processing, as part of progress-aware map-reduce operations that are included in the progressive processing.

16. The computer-readable storage medium of claim 13, wherein:

initiating the deterministic, massively parallel, progressive processing includes initiating distributed progressive processing of the plurality of data items using sort-free progressive data shuffling, using grouping of sets of the plurality of data items, the grouping based on progress markers of respective data items included in the sets.

17. The computer-readable storage medium of claim 13, wherein:

initiating the deterministic, massively parallel, progressive processing includes initiating distributed progressive processing of the plurality of data items using progress-aware merging of portions of the plurality of data items, wherein

the progress-aware merging of portions of the plurality of data items includes progress-aware merging of the portions of the plurality of data items at a reducer stage of the distributed progressive processing, as part of progress-aware map-reduce operations that are included in the progressive processing.

18. The computer-readable storage medium of claim 17, wherein:

the reducer stage includes a streaming temporal engine that processes the progress markers substantially equivalently as processing of temporal fields.

19. The computer-readable storage medium of claim 13, wherein:

obtaining the plurality of data items that are annotated with progress markers includes receiving the plurality of data items that include data tuples that are user-augmented with respective progress intervals that indicate logical points where the data tuples enter and exit portions of computation included in the progressive processing.

20. A method comprising:

obtaining a plurality of data items that are annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data items; and

initiating, via a device processor, deterministic, massively parallel, progressive processing of the plurality of data items on a plurality of devices, the progress markers indicating which of the plurality of data items are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data items into the results.