Versioned records management using restart era

• US 9,952,931 B2
• Filed: 01/19/2016
• Issued: 04/24/2018
• Est. Priority Date: 01/19/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Larson, Per-Ake, Fitzgerald, Robert Patrick, Diaconu, Cristian
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US15/001,088
• Publication Number:
  US 20170206137A1
• Time in Patent Office: 826 Days
• Field of Search: 707686, 707661, 707674, 707999202, 707999203
• CPC Class Codes: G06F 11/1417 Boot up procedures
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A versioned records management computing system that uses a restart era in order to promote rapid recovery. A persistent store includes a multi-versioned record collection. The records are also associated with a restart era that corresponds to the era of operation of the computing system after a restart. Upon a recovery, the current restart era changes. An object collection media has an object collection that conforms to an object model such that the object model is used to operate upon the records. The object collection media is operable such that the object collection is durable so as to survive restarts of the system to thereby allow for accelerated recovery.

Claims

1. A versioned records management computing system having a restart era that changes when the versioned records management computing system recovers from a crash, the computing system comprising:

a processor;

a persistent store that includes a plurality of items that are each marked with a restart era, wherein any item that was created in the current restart era is marked with the current restart era, the persistent store comprising a multi-versioned record collection comprising some of the plurality of items in the form of a plurality of records collectively corresponding to multiple versions, the persistent store also having thereon an object collection of objects that represent others of the plurality of items and that conforms to an object model such that the object model is used to operate upon the plurality of records via the object collection;

a versioned records management component configured to manage visibility of the plurality of records based on the version of each record, the persistent store also having thereon an object collection that conforms to an object model such that the object model is used to operate upon the plurality of records; and

a recovery component that is configured to recover from a crash by marking and sweeping the plurality of items while normal operations are occurring on the record collection via the use of the object model on the object collection, the marking involving promoting the item to the current restart era if the item is reachable via the object collection.

2. The versioned records management computing system in accordance with claim 1, the recovery component operating during normal operation by performing the following:

an act of evaluating each of at least some of the plurality of items;

as a result of the act of evaluating, an act of marking the evaluated items by performing an act of promoting at least some of the evaluated items to the current restart era by changing the restart era of the promoted items to the current restart era, and an act of refraining from changing the restart era of at least some of the evaluated items.

3. The versioned records management computing system in accordance with claim 2, further comprising the following after the act of marking:

an act of scanning the persistent store and deleting the items from a prior restart era from the persistent store.

4. The versioned records management computing system in accordance with claim 2, the act of evaluating for a particular item of the plurality of records comprising:

an act of determining that the particular item is not reachable via the object collection; and

as a result of the act of determining that the particular item is not reachable via the object collection, an act of refraining from changing the restart era of the particular item.

5. The versioned records management computing system in accordance with claim 2, the particular item being a particular record of the record collection, the act of evaluating for a particular item of the plurality of records comprising:

an act of determining that the particular record is reachable via the object collection;

the act of determining that the particular record is not visible via the versioned records management component; and

the act of refraining from changing the restart era of the particular record as a result of the act of determining that the particular record is not visible via the versed records management component.

6. The versioned records management computing system in accordance with claim 5, the act of determining that the particular record is not visible comprising:

an act of determining that the particular record was created as part of a transaction that did not commit.

7. The versioned records management computing system in accordance with claim 5, the act of determining that the particular record is not visible comprising:

an act of determining that the particular record was deleted as part of a transaction that did commit.

8. The versioned records management computing system in accordance with claim 2, the act of evaluating for a particular item of the plurality of records comprising:

an act of determining that the particular item is reachable via the object collection; and

as a result of at least the act of determining that the particular item is reachable via the object collection, an act of changing the restart era of the particular item to the current restart era.

9. The versioned records management computing system in accordance with claim 2, the particular item being a particular record of the record collection, the act of evaluating for a particular item of the plurality of records comprising:

an act of determining that the particular record is reachable via the object collection;

the act of determining that the particular record is visible via the versioned records management component; and

as a result of the acts of determining, an act of changing the restart era of the particular item to the current restart era.

10. The versioned records management computing system in accordance with claim 1, at least some of the promoted items being records of the records collection.

11. The versioned records management computing system in accordance with claim 10, at least some of the promoted items being objects of the object collection.

12. The versioned records management computing system in accordance with claim 1, at least some of the plurality of records each comprising a row or column.

13. The versioned records management computing system in accordance with claim 1, the object collection including at least one index for the plurality of records.

14. The versioned records management computing system in accordance with claim 1, the object collection including all of the indices associated with the plurality of records.

15. The versioned records management computing system in accordance with claim 1, the plurality of items being lock-free data structures.

16. The versioned records management computing system in accordance with claim 1, the version of a record of the plurality of records being defined by a begin timestamp and an end timestamp, wherein the version of the record is visible at a particular time if the particular time is between the begin timestamp and the end timestamp.

17. The versioned records management computing system in accordance with claim 1, the persistent store comprising persistent main memory.

18. The versioned records management computing system in accordance with claim 17, the object collection media also comprising the persistent main memory.

19. A method for recovering a versioned records management computing system having a restart era that changes when the versioned records management computing system recovers from a crash, the method comprising:

an act of the computing system using a persistent store to recover consistent records such that each record that was valid and visible at any given time prior to the crash remains valid and visible at the time after the crash, wherein the computing system includes the persistent store having a plurality of items that are each marked with a restart era, wherein any item that was created in the current restart era is marked with the current restart era, the persistent store comprising a multi-versioned record collection comprising some of the plurality of items in the form of a plurality of records collectively corresponding to multiple versions, the persistent store also having thereon an object collection of objects that represent others of the plurality of items and that conforms to an object model such that the object model is used to operate upon the plurality of records via the object collection;

after the recovering of the consistent records, an act of the computing system performing normal operation by using the object model to operate upon the plurality of records; and

in parallel with the normal operation, an act of the computing system promoting at least some of the plurality of items in the persistent store to the current restart era, and thereafter sweeping any of the plurality of items that are not marked as having the current restart era.

20. A computer program product comprising one or more computer-readable storage device having thereon computing executable instructions that structured such that, when executed by one or more processors of the computing system, configure the computing system to implement a method for recovering a versioned records management computing system having a restart era that changes when the versioned records management computing system recovers from a crash, wherein the method includes:

an act of the computing system using a persistent store to recover consistent records such that each record that was valid and visible at any given time prior to the crash remains valid and visible at the time after the crash, wherein the computing system includes a persistent store having a plurality of items that are each marked with a restart era, wherein any item that was created in the current restart era is marked with the current restart era, the persistent store comprising a multi-versioned record collection comprising some of the plurality of items in the form of a plurality of records collectively corresponding to multiple versions, the persistent store also having thereon an object collection of objects that represents others of the plurality of items and that conforms to an object model such that the object model is used to operate upon the plurality of records via the object collection;

after the recovering of the consistent records, an act of the computing system performing normal operation by using the object model to operate upon the plurality of records; and

in parallel with the normal operation, an act of the computing system promoting at least some of the plurality of items in the persistent store to the current restart era, and thereafter sweeping any of the plurality of items that are not marked as having the current restart era.