Collection record for overlapping data stream collections

• US 10,592,494 B2
• Filed: 04/14/2015
• Issued: 03/17/2020
• Est. Priority Date: 04/14/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Diaconu, Cristian, Damianidis, Christian, Brjazovski, Arkadi, Ramos, Rogerio, Kodandaramaih, Raghavendra Thallam
• Primary Examiner(s): Mackes, Kris E
• Assistant Examiner(s): Davanlou, Soheila (Gina)
• Application Number:
  US14/686,560
• Publication Number:
  US 20160306841A1
• Time in Patent Office: 1,799 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

The insertion into a data stream of collection records associated with multiple collections of data items in the data stream, for purposes of aiding in subsequent processing of the data stream by collections. Each collection record comprises a collection definition that does not overlap with the collection definition in any of the sequence of collection records including the collection definition of any neighboring collection record in the sequence of collection records. Each collection record also includes a data stream address range extending from the first data item to the last data item in the collection.

Claims

1. A computing system comprising:

one or more processors; and

a computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computing system to insert collection records associated with a plurality of collections of transaction segment records into a data stream that contains a plurality of transaction segment records, each of the plurality of transaction segment records corresponding to a transaction identifier and a data stream address, each transaction identifier being assigned sequentially when the corresponding transaction is started, each of the plurality of transaction segment records being entered into the data stream after the transaction segment is completed, at least two different transactions being performed in parallel, and a plurality of data stream addresses corresponding to the at least two different transactions that are performed in parallel overlapping, the computer-executable instructions including instructions that are executable to cause the computing system to perform at least the following;

for a non-overlapping range of transaction identifiers,

identify a collection of transaction segment records within the data stream, the collection of transaction segment records comprising a plurality of transaction segment records, each of which corresponds to a transaction identifier that is within the corresponding non-overlapping range of transaction identifiers;

establish a reference count that represents the identified collection of transactions within the range of transaction identifiers that have not yet completed;

each time a transaction that has a transaction identifier within the range of transaction identifiers is detected as completed, alter the reference count so as to represent a decrementing of the identified collection of transactions within the range that have not yet completed;

when the reference count represents that there are no further transactions having transaction identifiers within the range that have not completed, create a corresponding collection record comprising,

the corresponding range of the transaction identifiers that is not overlapping with a range of sequential identifiers of another collection of transaction segment records, and

a data stream address range at least extending from a first transaction segment record of the collection to a last transaction segment record of the collection; and

insert the created collection record into the data stream at any place after the last transaction segment record of the corresponding collection of transaction segment records, wherein a data stream address range of at least one collection of transaction segment record overlaps a data stream address range of at least another collection of transaction segment, the overlapping address range being caused by the at least two different transactions being performed in parallel.

2. The computing system in accordance with claim 1, the data stream being a log.

3. The computing system in accordance with claim 2, the collection records being transaction segment records, the collection comprising a transaction identifier range.

4. The computing system in accordance with claim 3, wherein for each collection of transaction segment records, the transaction segment records are created by performing the following:

determining that any prior transaction segment records, if any, in the collection of transaction segment records have been written to the log;

in response to determining that any prior transaction segment records have been written to the log, identifying a latest transaction identifier of the transaction segment record, thereby identifying the transaction identifier range of the transaction segment record;

determining if there are any transactions having a transaction identifier within the transaction identifier range that have not yet completed;

if there are any transactions having a transaction identifier that is within the transaction identifier range that has not yet completed, awaiting completion of the uncompleted transactions that are within the transaction identifier range;

upon determining that all of the transactions within the transaction identifier range have completed, creating the transaction segment record; and

placing the transaction segment record into the log.

5. The computing system in accordance with claim 4, wherein for each of at least one collection of transaction segment records, determining if there are any transactions having a transaction identifier within the transaction identifier range that have not yet completed comprises:

evaluating a transaction map that shows active transactions according to transaction identifier.

6. The computing system in accordance with claim 4, wherein for each of at least one collection of transaction segment records, determining if there are any transactions having a transaction identifier within the transaction identifier range that have not yet completed comprises:

identifying a number of transactions within the transaction identifier range that have not yet completed.

7. The computing system in accordance with claim 1, a range of data stream address of a given collection record overlapping a range of data stream address of at least one of a neighboring prior collection of transaction segment records and a neighboring subsequent collection of transaction segment records in the plurality of collections of transaction segment records.

8. The computing system in accordance with claim 1, a range of data stream address of a given collection record overlapping a range of data stream address of both of a neighboring prior collection of transaction segment records and a neighboring subsequent collection of transaction segment records in the plurality of collections of transaction segment records.

9. A method, implemented at a computing system that includes one or more processors, for inserting collection records associated with a plurality of collections of transaction segment records into a data stream that contains a plurality of transaction segment records, each of the plurality of transaction segment records corresponding to a transaction identifier and a data stream address, each transaction identifier being assigned sequentially when the corresponding transaction is started, each of the plurality of transaction segment records being entered into the data stream after the transaction segment is completed, at least two different transactions being performed in parallel, and a plurality of data stream addresses corresponding to the at least two different transactions that are performed in parallel overlapping, the method comprising:

for a non-overlapping range of transaction identifiers,

identifying collection of transaction segment records within the data stream, the collection of transaction segment records comprising a plurality of transaction segment records, each of which corresponds to a transaction identifier that is within the corresponding non-overlapping range of transaction identifiers;

establishing a reference count that represents the identified collection of transactions within the range of transaction identifiers that have not yet completed;

each time a transaction that has a transaction identifier within the range of transaction identifiers is detected as completed, altering the reference count so as to represent a decrementing of the identified collection of transactions within the range that have not yet completed;

when the reference count represents that there are no further transactions having transaction identifiers within the range that have not completed, creating a corresponding collection record comprising,

the corresponding range of the transaction identifiers that is not overlapping with a range of sequential identifiers of another collection of transaction segment records, and

a data stream address range at least extending from a first transaction segment record of the collection to a last transaction segment record of the collection; and

inserting the created collection record into the data stream at any place after the last transaction segment record of the corresponding collection of transaction segment records,

wherein a data stream address range of at least one collection of transaction segment record overlaps a data stream address range of at least another collection of transaction segment, the overlapping address range being caused by the at least two different transactions being performed in parallel.

10. The method in accordance with claim 9, wherein for each of a sequence of collection records, the collection records are created by performing the following:

determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream;

in response to determining that any prior collection records have been inserted into the data stream, identifying a current collection definition of the collection;

determining if there are any transaction segment record in that data stream that satisfy the current collection definition that have not yet been encounter in the data stream;

if there are any transaction segment record in the data stream that satisfy the current collection definition that have not yet been encountered in the data stream, awaiting encountering of the last transaction segment record that satisfies the current collection definition in the data stream;

upon determining that all of the transaction segment records within the current collection definition have been encountered in the data stream, creating the collection record; and

inserting the collection record into the data stream.

11. The method in accordance with claim 10, the collection record of each of the sequence of collections records having a data stream address that is later than a latest data stream address in the data stream address range of the collection corresponding to the collection record.

12. The method in accordance with claim 10, wherein at least until determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream, the current collection definition may change to encompass a particular data item type if a last transaction segment record of a particular data item type is encountered in the data stream.

13. The method in accordance with claim 12, wherein until a particular condition is encountered after determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream, the current collection definition may change to encompass a particular data item type if a last transaction segment record of a particular data item type is encountered in the data stream.

14. The method in accordance with claim 13, the particular condition being that the collection associated with the collection record has reached a predetermined size.

15. The method in accordance with claim 12, wherein a collection of transition segment records changes from an open state in which the current collection of transaction segment records may expand, to a closing state in which the current collection of transaction segment records may not expand, the collection when in the open state being represented by an open collection data structure that is lockless.

16. The method in accordance with claim 15, the open collection data structure being lockless because it can be entirely refreshed in a single processor cycle.

17. The method in accordance with claim 16, a size of the open collection data structure being 256 bits or less.

18. The method in accordance with claim 16, a size of the open collection data structure being 128 bits or less.

19. The method in accordance with claim 10, wherein for each of at least one of the sequence of collection records, the collection records are created by performing the following:

determining that a collection size has reached a target size, wherein at least until determining that the collection size has reached a target size, the current collection of transaction segment record may change to encompass a particular data item type if a last data item of a particular data item type is encountered.

20. A computer program product comprising one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by one or more processors of a computing system to cause the computing system to insert collection records associated with a plurality of collections of transaction segment records into a data stream that contains a plurality transaction segment records, each of the plurality of transaction segment records corresponding to a transaction identifier and a data stream address, each transaction identifier being assigned sequentially when the corresponding transaction is started, each of the plurality of transaction segment records being entered into the data stream after the transaction segment is completed, at least two different transactions being performed in parallel, and a plurality of data stream addresses corresponding to the at least two different transactions that are performed in parallel overlapping, the computer-executable instructions including instructions that are executable to cause the computing system to perform at least the following:

for a non-overlapping range of transaction identifiers,

identify a collection of transaction segment records within the data stream, the collection of transaction segment records comprising a plurality of transaction segments records, each of which corresponds to a transaction identifier that is within the corresponding non-overlapping range of transaction identifiers;

establish a reference count that represents the identified collection of transactions within the range of transaction identifiers that have not yet completed;

each time a transaction that has a transaction identifier within the range of transaction identifiers is detected as completed, alter the reference count so as to represent a decrementing of the identified collection of transactions within the range that have not yet completed;

when the reference count represents that there are no further transactions having transaction identifiers within the range that have not completed, create a corresponding collection record comprising,

the corresponding range of the transaction identifier that is not overlapping with a range of sequential identifiers of another collection of transaction segment records,

a data stream address range at least extending from a first transaction segment record of the collection to a last transaction segment record of the collection; and

insert the created collection record into the data stream at any place after the last transaction segment record of the corresponding collection of transaction segment records,

wherein a data stream address range of at least one collection of transaction segment record overlaps a data stream address range of at least another collection of transaction segment, the overlapping address range being caused by the at least two different transactions being performed in parallel.

21. The computer program product in accordance with claim 20, wherein for each of a sequence of collection records, the collection records are created by performing the following:

determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream;

in response to determining that any prior collection records have been inserted into the data stream, identifying a current collection definition of the collection;

determining if there are any transaction segment records in that data stream that satisfy the current collection definition that have not yet been encounter in the data stream;

if there are any transaction segment records in the data stream that satisfy the current collection definition that have not yet been encountered in the data stream, awaiting encountering of the last transaction segment record that satisfies the current collection definition in the data stream;

upon determining that all of the transaction segment records within the current collection definition have been encountered in the data stream, creating the collection record; and

inserting the collection record into the data stream.

22. The computer program product in accordance with claim 21, the collection record of each of the sequence of collections records having a data stream address that is later than a latest data stream address in the data stream address range of the collection corresponding to the collection record.

23. The computer program product in accordance with claim 21, wherein at least until determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream, the current collection definition may change to encompass a particular data item type if a last transaction segment record of a particular data item type is encountered in the data stream.

24. The computer program product in accordance with claim 23, wherein until a particular condition is encountered after determining that any prior collection records, if any, in the sequence of collection records have been inserted into the data stream, the current collection definition may change to encompass a particular data item type if a last transaction segment record of a particular data item type is encountered in the data stream.