HASH PARTITIONING STREAMED DATA

• US 20110154359A1
• Filed: 12/18/2009
• Published: 06/23/2011
• Est. Priority Date: 12/18/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ostrovsky, Igor, Toub, Stephen H.
• Granted Patent: US 8,276,154 B2
• Time in Patent Office: Days
• US Class Current: 718/106
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

The present invention extends to methods, systems, and computer program products for partitioning streaming data. Embodiments of the invention can be used to hash partition a stream of data and thus avoids unnecessary memory usage (e.g., associated with buffering). Hash partitioning can be used to split an input sequence (e.g., a data stream) into multiple partitions that can be processed independently. Other embodiments of the invention can be used to hash repartition a plurality of streams of data. Hash repartitioning converts a set of partitions into another set of partitions with the hash partitioned property. Partitioning and repartitioning can be done in a streaming manner at runtime by exchanging values between worker threads responsible for different partitions.

Claims

1. At a computer system including one or more processors and system memory, the computer system also including an input data stream, a plurality of worker threads, and a corresponding plurality of output data streams, each worker thread in the plurality of worker threads directly corresponding to an output data stream in the plurality of output data streams, each worker thread in the plurality of worker threads configured to determine the equivalence of data elements from the input data stream in accordance with an equivalence function and to assign data elements determined to be equivalent to the same worker thread for output on the worker'"'"'s corresponding output data stream such that equivalent data elements are output on the same output data stream, a method for distributing data elements from the input data stream across the plurality of output data streams, the method comprising:

an act of a first worker thread, from among the plurality of worker threads, acquiring a lock on the input data stream, the lock shared among the plurality of worker threads;

an act of the first worker thread accessing one or more data elements from the input data stream subsequent to locking the input data stream;

an act of the first worker thread releasing the lock on the input data stream;

for each data element in the one or more data elements;

an act of the first worker thread using the equivalence function to identify the appropriate output data stream, from among the plurality of output data streams, for outputting the data element; and

an act of the first worker thread assigning the data element to a worker thread corresponding to the identified appropriate output data stream such that data elements determined to be equivalent by the equivalence function are assigned to the same worker thread; and

an act of the first worker thread determining if other worker threads assigned any data elements from the input data stream to the first worker thread for output on the first worker thread'"'"'s corresponding output data stream.

2. The method as recited in claim 1, wherein the act of the first worker thread using the equivalence function to identify the appropriate output data stream comprises an act of the first worker thread using a hash function to identify the appropriate output data stream.

3. The method as recited in claim 1, wherein the act of the first worker thread using the equivalence function to identify the appropriate output data stream comprises an act of the first worker thread using the equivalence function to identify an output data stream corresponding to first worker thread.

4. The method as recited in claim 3, wherein the act of the first worker thread assigning the data element to a worker thread corresponding to the identified appropriate output data stream comprises an act of the first worker thread assigning the data element to the first worker thread.

5. The method as recited in claim 4, wherein the an act of the first worker thread assigning the data element to the first worker thread comprises an act of the first worker thread outputting the data element on its corresponding output data stream.

6. The method as recited in claim 1, wherein the act of the first worker thread using the equivalence function to identify the appropriate output data stream comprises an act of the first worker thread using the equivalence function to identify an output data stream corresponding to a second different worker thread.

7. The method as recited in claim 6, wherein the act of the first worker thread assigning the data element to a worker thread corresponding to the identified appropriate output data stream comprises an act of the first worker thread assigning the data element to the second different worker thread.

8. The method as recited in claim 7, wherein the act of the first worker thread assigning the data element to the second different worker thread comprises an act of the first worker thread storing the data element in a storage buffer for the second different worker thread.

9. The method as recite din claim 1, wherein the act of the first worker thread determining if other worker threads assigned any data elements from the input data stream to the first worker thread comprises an act of the first worker thread checking a storage buffer for the first worker thread.

10. The method as recited in claim 9, further comprising an act of the first worker thread outputting any data elements stored in the storage buffer to the first worker thread'"'"'s output data stream.

12. The method as recited in claim 10, wherein the act of accessing one or more data elements from an input data stream comprises an act of accessing one or more data elements from an input data stream specifically directed to the worker thread.

13. The method as recited in claim 10, wherein the act of accessing one or more data elements from an input data stream comprises an act of the worker thread acquiring a lock on the input data stream.

14. The method as recited in claim 10, wherein the act of using the equivalence function to identify the appropriate output data stream comprises an act of the worker thread identifying the output data stream corresponding to the worker thread.

15. The method as recited in claim 10, wherein the act of using the equivalence function to identify the appropriate output data stream comprises an act of the worker thread identifying the output data stream corresponding to a different worker thread.

16. The method as recited in claim 10, wherein the act of assigning the data element to a worker thread corresponding to the identified appropriate output data stream comprise an act of the worker thread assigning the data element to the worker thread.

17. The method as recited in claim 10, wherein the act of assigning the data element to a worker thread corresponding to the identified appropriate output data stream comprise an act of the worker thread assigning the data element to a different worker thread.

18. The method as recited in claim 1, wherein the act of checking a storage buffer for data elements assigned to the worker thread by other worker threads comprises an act of the determining that data elements are contained in the storage buffer.

19. The method as recited in claim 1, wherein the act of checking a storage buffer for data elements assigned to the worker thread by other worker threads comprises an act of determining that the storage buffer is empty, and in response, further comprising an act of accessing one or more additional data elements from the input data stream

11. At a computer system including one or more processors and system memory, the computer system also including a plurality of input data streams, a plurality of worker threads, and a plurality of output data streams, each of the plurality of input data streams streaming a previously partitioned subset of data to one or more of the plurality of worker threads, data streamed on each input data stream determined to be equivalent by a prior equivalence function, each worker thread in the plurality of worker threads directly corresponding to an output data stream in the plurality of output data streams, each worker thread in the plurality of worker threads configured to determine the equivalence of data elements from the plurality of input data streams in accordance with an equivalence function and to assign data elements determined to be equivalent by the equivalence function to the same worker thread for output on the worker'"'"'s corresponding output data stream such that data elements determined to be equivalent by the equivalence function are output on the same output data stream, a method for repartitioning the plurality of input data streams, the method comprising:

at each worker thread in the plurality of worker threads;

an act of the worker thread accessing one or more data elements from an input data stream, the data elements determined to be equivalent by the prior equivalence function;

for each of the one or more data elements;

an act of using the equivalence function to identify the appropriate output data stream, from among the plurality of output data streams, for outputting the data element;

an act of assigning the data element to a worker thread corresponding to the identified appropriate output data stream such that data elements determined to be equivalent by the equivalence function are assigned to the same worker thread;

an act of checking a storage buffer for data elements assigned to the worker thread by other worker threads, data elements in the storage buffer determined to be equivalent by the equivalence function; and

an act of outputting any data elements in the storage buffer on the worker thread'"'"'s corresponding output data stream.

20. A computer program product for use at a computer system, the computer system including an input data stream, a plurality of worker threads, and a corresponding plurality of output data streams, each worker thread in the plurality of worker threads directly corresponding to an output data stream in the plurality of output data streams, each worker thread in the plurality of worker threads configured to determine the equivalence of data elements from the input data stream in accordance with an equivalence function and to assign data elements determined to be equivalent to the same worker thread for output on the worker'"'"'s corresponding output data stream, the computer program product for implementing a method for distributing data elements from the input data stream across the plurality of output data streams, the computer program product comprising one or more computer storage media having stored thereon computer-executable instructions that, when execution at a processor, cause the computer system to perform the method, including the following at a worker thread from among the plurality of worker threads:

acquire a lock on the input data stream, the lock shared among the plurality of worker threads;

access one or more data elements from the input data stream subsequent to locking the input data stream;

release the lock on the input data stream;

for each data element in the one or more data elements;

use the equivalence function to compute a hash code for the data element;

map the data element to the appropriate output data stream, from among the plurality of output data streams, based on the hash code; and

assign the data element to a worker thread corresponding to the appropriate output data stream such that data elements determined to be equivalent by the equivalence function are mapped to the same worker thread; and

check a lock-free stack corresponding to the worker thread to determining if other worker threads assigned any data elements from the input data stream to the worker thread for output on the worker thread'"'"'s corresponding output data stream.