Parallel processing of an ordered data stream

• US 8,996,556 B2
• Filed: 06/05/2009
• Issued: 03/31/2015
• Est. Priority Date: 06/05/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ostrovsky, Igor, Duffy, John, Liddell, Mike
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): PARK, GRACE A
• Application Number:
  US12/479,242
• Publication Number:
  US 20100312801A1
• Time in Patent Office: 2,125 Days
• Field of Search: 707/764, 707/796
• US Class Current: 707/764
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, with each order key associated with one of the input data elements, includes processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements. The plurality of sets of output data elements is stored in a plurality of buffers, with each buffer associated with one of the worker units. An ordered output data stream is output while the input data stream is being processed by outputting selected output data elements from the buffers in an order that is based on the order keys.

Claims

1. A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:

storing the ordered input data stream, including storing as part of the input data stream an order key for each of the input data elements, wherein the order keys indicate a total order of all of the input data elements in the ordered input data stream;

processing the stored ordered input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements;

storing the plurality of sets of output data elements in a plurality of buffers along with an associated order key for each output data element, each buffer associated with one of the worker units;

outputting an ordered output data stream while the input data stream is being processed in a parallel manner with the plurality of worker units by outputting selected output data elements from the plurality of buffers in an order that is based on the order keys stored in the plurality of buffers;

generating a data structure that includes a plurality of entries, each entry associated with one of the buffers and identifying a next output data element to be output from its associated buffer based on the order keys stored in the buffers; and

selecting output data elements to be output from the buffers based on output data elements identified by the data structure.

2. The method of claim 1, wherein the data structure is a heap data structure.

3. The method of claim 1, wherein each entry includes a value identifying one of the order keys stored in the plurality of buffers.

4. The method of claim 3, and further comprising:

identifying one of the entries in the data structure that has a smallest order key;

identifying one of the output data elements in the buffer associated with the identified entry based on the smallest order key; and

outputting the identified output data element into the ordered output data stream.

5. The method of claim 4, and further comprising:

updating the identified entry to identify a next output data element to be output from its associated buffer.

6. The method of claim 1, and further comprising:

waiting to output data elements from all of the buffers when any of the buffers becomes empty.

7. The method of claim 6, wherein the outputting of an ordered output data stream is performed by a merge unit, and wherein the method further comprises:

causing the merge unit to enter a sleep state when any of the buffers becomes empty.

8. The method of claim 1, wherein input data elements from the input data stream are provided to the worker units in a gradual manner and not all at one time.

9. The method of claim 1, wherein the order keys are non-consecutive integers.

10. The method of claim 1, wherein outputting selected output data elements from the buffers comprises outputting selected chunks of output data elements from the buffers, wherein each chunk includes a plurality of data elements.

11. The method of claim 1, and further comprising:

determining whether a total number of data elements in a first one of the buffers exceeds a predetermined threshold; and

privatizing the first buffer and allocating a new buffer to replace the first buffer when it is determined that the total number of data elements in the first buffer exceeds the predetermined threshold.

12. The method of claim 1, and further comprising:

determining whether a total number of data elements in a first one of the buffers exceeds a predetermined threshold; and

waiting to process additional input data elements from the input data stream by the worker unit associated with the first buffer when it is determined that the total number of data elements in the first buffer exceeds the predetermined threshold.

13. The method of claim 12, and further comprising:

resuming processing of input data elements from the input data stream by the worker unit associated with the first buffer when the total number of data elements in the first buffer falls below the predetermined threshold.

14. The method of claim 12, and further comprising:

causing the worker unit associated with the first buffer to enter a sleep state when it is determined that the total number of data elements in the first buffer exceeds the predetermined threshold.

15. The method of claim 1, and further comprising:

obtaining a lock on the input data stream with a first one of the worker units;

pulling at least one input data element from the input data stream while the lock is held by the first worker unit; and

releasing the lock on the input data stream after pulling the at least one input data element from the input data stream.

16. A computer-readable storage medium storing computer-executable instructions for performing a method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:

storing the ordered input data stream, including storing as part of the input data stream an order key for each of the input data elements, wherein the order keys indicate a total order of all of the input data elements in the ordered input data stream;

processing the stored ordered input data stream in a parallel manner with a plurality of worker units, thereby generating a corresponding plurality of sets of output data elements;

storing the plurality of sets of output data elements in a corresponding plurality of buffers along with an associated order key for each output data element, each buffer associated with one of the worker units;

outputting an ordered output data stream while the input data stream is being processed in a parallel manner with the plurality of worker units by outputting selected output data elements from the plurality of buffers in an order that is based on the order keys stored in the plurality of buffers;

generating a data structure that includes a plurality of entries, each entry associated with one of the buffers and identifying a next output data element to be output from its associated buffer based on the order keys stored in the buffers; and

selecting output data elements to be output from the buffers based on output data elements identified by the data structure.

17. The computer-readable storage medium of claim 16, wherein the method further comprises:

waiting to output data elements from all of the buffers when any of the buffers becomes empty.