Deterministic progressive big data analytics

• US 9,514,214 B2
• Filed: 06/12/2013
• Issued: 12/06/2016
• Est. Priority Date: 06/12/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chandramouli, Badrish, Goldstein, Jonathan, Quamar, Abdul Hussain
• Primary Examiner(s): PHAM, KHANH B
• Application Number:
  US13/915,632
• Publication Number:
  US 20140372438A1
• Time in Patent Office: 1,273 Days
• US Class Current: 1/1
• 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, and a computer readable storage medium storing instructions for execution by the at least one processor, for implementing a distributed progressive analytics engine that comprises;

a data item acquisition component that obtains a plurality of data items, the respective data items comprising respective data tuples that are each respectively annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data tuples, each respective progress marker including a respective progress interval associated with each respective one of the plurality of data tuples; and

a progressive distributed processing manager that initiates 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 tuples are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data tuples into the results, each respective progress interval comprising a respective progress-start attribute value indicating a first logical point where the respective data tuple enters a portion of computation included in the progressive processing, and a respective progress-end attribute value indicating a second logical point where the respective data tuple exits the portion of computation.

2. The system of claim 1, further comprising:

a map component that initiates 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 that initiates sort-free progressive data shuffling, using grouping of sets of the plurality of data items, the grouping based on the progress markers of respective data items included in the sets.

4. The system of claim 2, further comprising:

a progress-aware merging component that initiates progress-aware merging of portions of the plurality of data items.

5. The system of claim 4, further comprising:

a progress-aware reducer component that initiates 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 pipelines 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) that performs 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 includes receiving the plurality of respective data tuples that are user-augmented with the respective progress intervals.

11. The system of claim 10, wherein:

the respective progress intervals are used to assign the respective data tuples to progressive samples.

12. The system of claim 1, wherein:

the progressive distributed processing manager initiates 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, when executed, cause one or more processors to:

obtain a plurality of data items, the respective data items comprising respective data tuples that are each annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data tuples, each respective progress marker including a respective progress interval associated with each respective one of the plurality of data tuples; 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 tuples are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data tuples into the results, each respective progress interval comprising a respective progress-start attribute value indicating a first logical point where the respective data tuple enters a portion of computation included in the progressive processing, and a respective progress-end attribute value indicating a second logical point where the respective data tuple exits the portion of computation.

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 the 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 includes receiving the plurality of respective data tuples that are user-augmented with the respective progress intervals.

20. A method comprising:

obtaining a plurality of data items, the respective data items comprising respective data tuples that each are annotated with progress markers indicating progress points associated with atemporal processing progress of the respective data tuples, each respective progress marker including a respective progress interval associated with each respective one of the plurality of data tuples; 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 tuples are to be incorporated into results of the progressive processing, the progress markers further indicating an ordering for incorporation of the respective data tuples into the results, each respective progress interval comprising a respective progress-start attribute value indicating a first logical point where the respective data tuple enters a portion of computation included in the progressive processing, and a respective progress-end attribute value indicating a second logical point where the respective data tuple exits the portion of computation.