Lockless open collection data structure

• US 10,102,251 B2
• Filed: 04/14/2015
• Issued: 10/16/2018
• 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
• Primary Examiner(s): Le, Miranda
• Application Number:
  US14/686,544
• Publication Number:
  US 20160306856A1
• Time in Patent Office: 1,281 Days
• Field of Search: 707703
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A lockless open collection data structure used to create a sequence of collection records. The sequence of collection records may be inserted into a data stream for purposes of assisting in subsequent processing of the data stream in a parallel manner, by collection. The open collection data structure is re-usable for multiple collections of data items within the data stream. The use of the open collection data structure may occur while a data stream that includes multiple different types of data items is being evaluated. The open collection data structure is used to track an expandable collection definition of a currently open collection. Upon detecting that the collection definition is no longer expandable, the collection record is created based on state within the open collection data structure. Once the collection record for a collection has been created, the open collection data structure becomes available for the next collection record.

Claims

1. A computing system comprising:

one or more processors;

a hardware storage device having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computing system to use an open collection data structure to create a sequence of collection records, the computer-executable instructions including instructions to perform at least the following;

access an open collection data structure that is lockless and re-usable for creating a corresponding collection record for each of a plurality of collections of data items within a data stream of a plurality of different types of data items, each collection of data items comprising a plurality of data items that include one or more common attributes, each given collection record including a collection definition that defines the collection of data items to which the given collection record corresponds; and

evaluate the data stream that includes the plurality of different types of data items;

use the lockless data structure to create a sequence of collection records by performing the following for at least one of the sequence of collection records;

identify an expandable collection definition associated with an open collection for which a collection record is to be created, wherein the expandable collection definition is expandable to include data items of a particular data item type if the last data item of that particular data item type is encountered in the data stream;

represent the expandable collection definition within the open collection data structure;

represent a data stream address range associated with the open collection within the open collection data structure;

upon detecting an event, determine that the expandable collection definition is no longer expandable;

upon determining that the expandable collection definition for the collection is no longer expandable, create a collection record based on state within the open collection data structure; and

once the collection record for a collection has been created, make the open collection data structure available for a next collection record in the sequence of collection records.

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 definition comprising a transaction identifier range.

4. The computing system in accordance with claim 1, the detected event being that the prior collection record in the sequence of collection records has been created.

5. The computing system in accordance with claim 1, the open collection data structure also including a field representing whether the prior collection records has been completed.

6. The computing system in accordance with claim 1, the detected event occurring after the prior collection record in the sequence of collection records has been created.

7. The computing system in accordance with claim 6, the detected event being that the collection has reached a predetermined size.

8. The computing system in accordance with claim 1, the collection record being created when inserted into the data stream.

9. The computing system in accordance with claim 1, each of the collection records being inserted into the data stream after a location of a last data item of the collection represented by the associated collection record.

10. A method, implemented at a computing system that includes one or more processors, for using an open collection data structure to create a sequence of collection records, the method comprising:

accessing an open collection data structure that is lockless and re-usable for creating a corresponding collection record for each of a plurality of collections of data items within a data stream of a plurality of different types of data items, each collection of data items comprising a plurality of data items that include one or more common attributes, each given collection record including a collection definition that defines the collection of data items to which the given collection record corresponds;

evaluating the data stream that includes the plurality of different types of data items; and

using the lockless data structure to create a sequence of collection records by performing the following for at least one of the sequence of collection records;

identifying an expandable collection definition associated with an open collection for which a collection record is to be created, wherein the expandable collection definition is expandable to include data items of a particular data item type if the last data item of that particular data item type is encountered in the data stream;

representing the expandable collection definition within the open collection data structure;

representing a data stream address range associated with the open collection within the open collection data structure;

upon detecting an event, determining that the expandable collection definition is no longer expandable;

upon determining that the expandable collection definition for the collection is no longer expandable, creating a collection record based on state within the open collection data structure; and

once the collection record for a collection has been created, making the open collection data structure available for a next collection record in the sequence of collection records.

11. The method in accordance with claim 10, each of the collection records being inserted in the data stream in the same order as the last data item of each associated collection is encountered in the data stream.

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

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

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

15. The method in accordance with claim 12, the size of the open collection data structure being 64 bits or less.

16. The method in accordance with claim 10, wherein only one open collection data structure is used in the creation of the sequence of collection records.

17. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a computing system to cause the computing system to use an open collection data structure to create a sequence of collection records, the computer-executable instructions including instructions to perform at least the following:

access an open collection data structure that is lockless and re-usable for creating a corresponding collection record for each of a plurality of collections of data items within the data stream of a plurality of different types of data items, each collection of data items comprising a plurality of data items that include one or more common attributes, each given collection record including a collection definition that defines the collection of data items to which the given collection record corresponds;

evaluate the data stream that includes the plurality of different types of data items; and

use the lockless data structure to create a sequence of collection records by performing the following for at least one of the sequence of collection records;

identify an expandable collection definition associated with an open collection for which a collection record is to be created, wherein the expandable collection definition is expandable to include data items of a particular data item type if the last data item of that particular data item type is encountered in the data stream;

maintain the expandable collection definition within the open collection data structure;

represent a data stream address range associated with the open collection within the open collection data structure;

upon detecting an event, determine that the expandable collection definition is no longer expandable;

upon determining that the expandable collection definition for the collection is no longer expandable, create a collection record based on state within the open collection data structure; and

once the collection record for a collection has been created, make the open collection data structure available for a next collection record in the sequence of collection records.

18. The computer program product in accordance with claim 17, the data stream being a log.

19. The computer program product in accordance with claim 18, the collection records being transaction segment records, the collection definition comprising a transaction identifier range.