Stream data processing on multiple application timelines

Patent metadata

Field	Value
Publication number	US-10949427-B2
Application number	US-201715588299-A
Country	US
Kind code	B2
Filing date	May 5, 2017
Priority date	Jan 31, 2017
Publication date	Mar 16, 2021
Grant date	Mar 16, 2021

Abstract

Accommodating a particular kind of out-of-order data; namely, when data arrives out-of-order because the data is generated in systems that may have different application timelines. As data arrives, it arrives with a particular partition key. For instance, the partition key might identify the source of the data. The data from each partition key is kept in-order with respect to all other data from that same partition key. That said, data from one key is permitted to have a different timeline as compared to data from any other key. Thus, the data may not be in-order when viewed globally across keys. Rather, data is tolerated to be out-of-order globally so long as the lag in the arrived data is within some tolerated lag. If the data arrives having a time that exceeds the maximum tolerated lag, then the system applies some policy to determine what to do with the delayed data.

First claim

What is claimed is:

1. A computing system comprising:
one or more processors;
one or more computer-readable media having thereon computer-executable instructions that are structured such that, when executed by the one or more processors, cause the computing system to perform steps for performing query processing on streaming data, the steps comprising:
receiving a data stream of a plurality of data items for each of a plurality of keys;
producing a processable data stream that includes all of the received plurality of items, wherein producing the processable data stream comprises:
for each of the data items from the data stream for each of the plurality of keys, ensuring that the data items for each key of the plurality of keys are temporally in order; and
for each of the data items in the processable data stream, ensuring that the data items temporally lag no more than a given tolerance in the processable data stream.

2. The computing system in accordance with claim 1 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
dropping the corresponding data item such that the corresponding data item is not included within the processable data stream.

3. The computing system in accordance with claim 1 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
fast forwarding a time stamp of the corresponding data item.

4. The computing system in accordance with claim 1 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
placing the corresponding time stamp in-order in the processable data stream.

5. The computing system in accordance with claim 4 , the steps further comprising:
performing one or more query operations on the processable data stream.

6. The computing system in accordance with claim 5 , the query operations comprising per-key query operations.

7. The computing system in accordance with claim 5 , the query operations comprising per-key aggregation operations.

8. The computing system in accordance with claim 5 , the query operations comprising across key-operations.

9. The computing system in accordance with claim 5 , the plurality of keys being a first plurality of keys, the processable data stream being a first processable data stream, the one or more query operations being first one or more query operations, the steps further comprising:
for data items from the first processable data stream, ensuring that the data items for the corresponding key of a second plurality of keys are temporally in order when producing a second processable data stream; and
performing one or more query operations on the second processable data stream.

10. The computing system in accordance with claim 5 , the plurality of keys being a first plurality of keys, the processable data stream being a first processable data stream, the one or more query operations being first one or more query operations, the steps further comprising:
for data items from the first processable data stream, temporally ordering the first processable data stream to generate a second processable data stream; and
performing one or more query operations on the second processable data stream.

11. A method for performing query processing on streaming data, the method comprising:
receiving a data stream of a plurality of data items for each of a plurality of keys;
producing a processable data stream that includes all of the received plurality of items, wherein producing the processable data stream comprises:
for each of the data items from the data stream for each of the plurality of keys, ensuring that the data items for each key of the plurality of keys are temporally in order; and
for each of the data items in the processable data stream, ensuring that the data items temporally lag no more than a given tolerance in the processable data stream.

12. The method in accordance with claim 11 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
dropping the corresponding data item such that the corresponding data item is not included within the processable data stream.

13. The method in accordance with claim 11 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
fast forwarding a time stamp of the corresponding data item.

14. The method in accordance with claim 11 , wherein ensuring that the data items temporally lag no more than a given tolerance comprises the following for each of at least one data item in the received data stream that is determined to temporally lag greater than the given tolerance:
placing the corresponding time stamp in-order in the processable data stream.

15. The computing system in accordance with claim 14 , further comprising:
performing one or more query operations on the processable data stream.

16. The method in accordance with claim 15 , the query operations comprising per-key query operations.

17. The method in accordance with claim 15 , the query operations comprising per-key aggregation operations.

18. The method in accordance with claim 15 , the query operations comprising across key-operations.

19. The method in accordance with claim 15 , the plurality of keys being a first plurality of keys, the processable data stream being a first processable data stream, the one or more query operations being first one or more query operations, the method further comprising:
for data items from the first processable data stream, ensuring that the data items for the corresponding key of a second plurality of keys are temporally in order when producing a second processable data stream; and
performing one or more query operations on the second processable data stream.

20. A computer program product comprising one or more computer-readable storage media that have thereon computer-executable instructions that are structured such that, when executed by one or more processors of a computing system, cause the computing system to perform steps for performing query processing on streaming data, the steps comprising:
receiving a data stream of a plurality of data items for each of a plurality of keys;
producing a processable data stream that includes all of the received plurality of items, wherein producing the processable data stream comprises:
for each of the data items from the data stream for each of the plurality of keys, ensuring that the data items for each key of the plurality of keys are temporally in order; and
for each of the data items in the processable data stream, ensuring that the data items temporally lag no more than a given tolerance in the processable data stream. processable data stream.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Chandramouli Badrish
• Goldstein Jonathan
• Barnett Michael
• Terwilliger James Felger

Classifications

• G06F16/24568 Primary

  Data stream processing; Continuous queries · CPC title

• G06F7/08

  Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) · CPC title