Collection record location as log tail beginning

• US 10,031,814 B2
• Filed: 04/14/2015
• Issued: 07/24/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, Ramos, Rogerio, Kodandaramaih, Raghavendra Thallam, Damianidis, Christian, Brjazovski, Arkadi, Vasquez Lopez, Daniel
• Primary Examiner(s): Bonzo, Bryce P
• Assistant Examiner(s): Arcos, Jeison C
• Application Number:
  US14/686,480
• Publication Number:
  US 20160306713A1
• Time in Patent Office: 1,197 Days
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

The logging of tasks associated with multiple transactions in the context in which the computing system is capable of having multiple of the transactions active at a given time, and thus in which the order of completion of the transactions is not guaranteed to be the same as the order of initiation of the transactions. A sequence of transaction segment records is added to the log. Each transaction segment record comprises a transaction identifier range that does not overlap with the transaction identifier range in any of the sequence of transaction segment records including the transaction identifier range of any neighboring transaction segment record in the sequence of transaction segment records. Each transaction segment record also includes a log entry identifier range extending from the first task of the first of the transactions to be initiated to the last task of the last transaction to complete.

Claims

1. A computing system comprising:

one or more processors; and

one or more computer-readable media having stored thereon computer-executable instructions that are executable by the one or more processors to recover the computing system using a log comprising multiple collections of events and checkpointed data including a last collection of events, the computer-executable instructions including instructions that are executable to cause the computing system to perform at least the following;

identify a data stream comprising a sequence of events associated with the computing system;

separate the sequence of events into a sequence of a plurality of collections of events within a log, each event collection comprising a plurality of events that have one or more common attributes;

generate a corresponding collection record for each of the plurality of event collections, each given collection record being recorded within the log after completion of the corresponding event collection;

in response to a failure, recover data within the computing system, including at least;

recovering the checkpointed data in the computing system, the checkpointed data comprising a saved subset of the log that includes a subset of the plurality of collection records and a subset of the plurality of event collections;

within the log of a sequence of collection records and event collections, determining that a beginning of a tail of the log is located at or before a location of a next-to-last collection record corresponding to a next-to-last event collection that is located immediately prior to the last event collection, the last event collection comprising a most recent collection of events that is included within the checkpointed data, and the next-to-last event collection comprising a second most recent event collection that is included within the checkpointed data; and

after recovering the checkpointed data, restoring the computing system by performing each event of the log from the identified beginning of the tail of the log onward.

2. The computing system in accordance with claim 1,

the beginning of the tail of the log also being identified as being at a location within the log that is after a location within the log of a collection record for a third to last collection of events included in the checkpointed data.

3. The computing system in accordance with claim 1,

the multiple collections of events being multiple collections of task entries.

4. The computing system in accordance with claim 3,

the multiple collections of task entries each being associated with a set of one or more transaction identifiers.

5. The computing system in accordance with claim 4,

the set of one or more transaction identifiers for any given collection of task entries not overlapping the set of one or more transaction identifiers of any other collection of task entries.

6. The computing system in accordance with claim 4,

the set of one or more transaction identifiers for at least one of the multiple collections of task being a plurality of transaction identifiers.

7. The computing system in accordance with claim 6,

the plurality of transaction identifiers being a transaction identifier range.

8. The computing system in accordance with claim 1,

the checkpointed data including a plurality of events for one or more collections after the last collection of events contained in the checkpointed data.

9. The computing system in accordance with claim 1,

the collection record for each of the multiple collections occurring in the log after a last event of the corresponding collection.

10. The computing system in accordance with claim 9,

the log including a plurality of collection records that are ordered by order of encountering last events of the multiple collections in the log.

11. The computing system in accordance with claim 1,

the log including a plurality of collection records that are ordered by order of encountering last events of the multiple collections in the log.

12. A method, implemented at one or more computer processors, for recovering in a system that has multiple collections of events, each collection having associated therewith a collection record in a log, the method comprising:

identifying a data stream comprising a sequence of events associated with the computing system;

separating the sequence of events into a sequence of a plurality of collections of events within a log, each event collection comprising a plurality of events that have one or more common attributes;

generating a corresponding collection record for each of the plurality of event collections, each given collection record being recorded within the log after completion of the corresponding event collection;

in response to a failure, recovering data within the computing system, including at least;

recovering checkpointed data in the system, the checkpointed data comprising a saved subset of the log that includes a subset of the plurality of collection records and a subset of the plurality of event collections;

within the log of a sequence of collection records and event collections, determining that a beginning of a tail of the log is located at or before a location of a next-to-last collection record corresponding to a next-to-last event collection that is located immediately prior to a last event collection, the last event collection comprising a most recent collection of events that is included within the checkpointed data, and the next-to-last event collection comprising a second most recent event collection that is included within the checkpointed data; and

after recovering the checkpointed data, restoring the computing system by performing each event included within the tail of the log in the system from the identified beginning of the tail of the log.

14. The method in accordance with claim 12,

the multiple collections of events being multiple collections of task entries.

13. The method in accordance with Calm 14,

the beginning of the tail of the log also being identified as at a location within the log that is after a location of a collection record for a third to last collection of events included in the checkpointed data.

15. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are structured such that, when executed by one or more processors of a computing system, the computer-executable instructions cause the computing system to perform a recovery in a system that has multiple collections of events, each collection having associated therewith a collection record in a log, the computer-executable instructions being executable to cause the computing system to perform at least the following:

identify a data stream comprising a sequence of events associated with the computing system;

separate the sequence of events into a sequence of a plurality of collections of events within a log, each event collection comprising a plurality of events that have one or more common attributes;

generate a corresponding collection record for each of the plurality of event collections, each given collection record being recorded within the log after completion of the corresponding event collection;

in response to a failure, recover data within the computing system, including at least;

recovering checkpointed data in the system, the checkpointed data comprising a saved subset of the log that includes a subset of the plurality of collection records and a subset of the plurality of event collections;

within the log of a sequence of collection records and event collections, determining that a beginning of a tail of the log is located at or before a location of a next-to-last collection record corresponding to a next-to-last event collection that is located immediately prior to a last event collection, the last event collection comprising a most recent collection of events that is included within the checkpointed data, and the next-to-last event collection comprising a second most recent event collection that is included within the checkpointed data; and

after recovering the checkpointed data, restoring the computing system by performing each event of the log from the identified beginning of the tail of the log onward.

16. The computer program product in accordance with claim 15,

the beginning of the tail of the log being identified as at a location within the log that is after a location of a collection record for a third to last collection of events included in the checkpointed data.

17. The computer program product in accordance with claim 15,

the multiple collections of events being multiple collections of task entries, the multiple collections of task entries each being associated with a set of one or more transaction identifiers, the set of one or more transaction identifiers for any given collection of task entries not overlapping the set of one or more transaction identifiers of any other collection of task entries.

18. The computer program product in accordance with claim 15,

the collection record for each of the multiple collections occurring in the log after a last event of the corresponding collection, the log including a plurality of collection records that are ordered by order of encountering last events of the multiple collections in the log.