Consistency without ordering dependency

• US 8,433,865 B2
• Filed: 12/11/2009
• Issued: 04/30/2013
• Est. Priority Date: 12/11/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, Thomas J., Cargille, Jonathan M., Tipton, William R., Verma, Surendra
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US12/635,725
• Publication Number:
  US 20110145527A1
• Time in Patent Office: 1,236 Days
• Field of Search: None
• US Class Current: 711/162
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Aspects of the subject matter described herein relate to maintaining consistency in a storage system. In aspects, one or more objects may be updated in the context of a transaction. In conjunction with updating the objects, logical copies of the objects may be obtained and modified. A request to write the updated logical copies is sent to a storage controller. The logical copies do not overwrite the original copies. In conjunction with sending the request, a data structure is provided for the storage controller to store on the disk. The data structure indicates the one or more objects that were supposed to be written to disk and may include verification data to indicate the content that was supposed to be written to disk. During recovery, this data structure may be used to determine whether all of the object(s) were correctly written to disk.

Claims

1. A method implemented at least in part by a computer, the method comprising:

obtaining one or more indications of objects that are involved in a transaction;

locating a first set of storage locations of a store for the objects that are involved in the transaction;

creating logical copies of the objects that are modified in context of the transaction;

determining a second set of storage locations of the store for the logical copies;

creating an association that binds the logical copies of the objects in an atomic unit;

sending one or more requests to write the association and the logical copies to the store while maintaining originals of the objects on the store; and

after a failure occurs, performing a recovery operation comprising;

determining whether a copy of all of the objects as modified in the context of the transaction are in the store, and

discarding modifications for the copy of all of the objects in the store that are modified in the context of the transaction when a copy of an object corresponding to one of the objects as modified in the context of the transaction is determined not to be in the store.

2. The method of claim 1, wherein obtaining one or more indications of objects that are involved in a transaction comprises receiving identifiers of the objects with requests to modify the objects within the context of the transaction.

3. The method of claim 2, wherein locating a first set of storage locations of a store for the objects that are involved in the transaction comprises using the identifiers as keys in a lookup table that associates the keys with locations at which the objects are stored in a store.

4. The method of claim 1, wherein each storage location in the second set of locations is different from each storage location in the first set and wherein creating logical copies of the objects comprises creating copies of portions of the objects that are modified during the transaction.

5. The method of claim 1, wherein creating an association that binds the logical copies of the objects in an atomic unit comprises creating a linked list that references each of the objects.

6. The method of claim 1, wherein creating an association that binds the logical copies of the objects in an atomic unit comprises creating links between pairs of the logical copies, each link including a hash value indicative of correct content of at least one of the logical copies of the pairs.

7. The method of claim 1, wherein sending one or more requests to write the association and the logical copies comprises sending one or more requests to write a data structure that indicates each storage location for the logical copies, one or more requests to write all but one of the logical copies to the store, and waiting to send a request to write the one of the logical copies until a predetermined event occurs.

8. The method of claim 7, wherein waiting to send a request to write the one of the logical copies until a predetermined event occurs comprises waiting for one or more of:

until another transaction has completed, until a predetermined time period has elapsed, and until a checkpoint is reached.

9. The method of claim 8, further comprising sending a request to write the one of the logical copies together with a reference to storage location of a logical copy of an object modified in a context of the another transaction.

10. The method of claim 1, wherein the recovery operation further comprises:

obtaining a first data structure that indicates last known correct storage locations of objects in a non-volatile store;

obtaining another data structure that indicates storage locations of the non-volatile store where the logical copies were planned to be stored, the another data structure also indicating a first set of hashes indicative of correct contents of the logical copies;

reading content located at the storage locations;

computing a second set of hashes of the content;

if corresponding members of the first and second set of hashes are equivalent, updating the first data structure to indicate that the logical copies are stored at the storage locations; and

if any of the corresponding members of the first and second set of hashes are not equivalent, ending the recovery operation.

11. The method of claim 1, further comprising indicating that storage locations associated with the originals of the objects are available for use and indicating the storage locations associated with the logical copies are valid after successfully flushing all logical copies to a non-volatile memory of the store.

12. A computer storage medium having computer-executable instructions, which when executed perform actions, comprising:

obtaining an indication of an object involved in an update of one or more transactions;

locating the object in a first storage location of a store;

creating a logical copy of the object that includes changes made to the object in context of the one or more transactions;

determining a second storage location of the store for storing the logical copy;

sending a request to write the logical copy as changed to the second storage location;

in conjunction with sending the request, providing data that indicates a next location at which a logical copy pertaining to another transaction, if any, is to be written;

updating a volatile data structure to indicate that the logical copy is stored in the second storage location; and

sending a request to write changes to the volatile data structure to the store and in conjunction with sending the request to write changes, sending a flush command to the store, the flush command instructing a controller of the store to write cache associated with the store to non-volatile memory of the store.

13. The computer storage medium of claim 12, wherein locating the object in a first storage location of a store comprises receiving an identifier of the object and using the identifier to look up an association in a data structure that associates identifiers with storage locations.

14. The computer storage medium of claim 12, further comprising updating the volatile data structure to indicate a storage location of the store of changes made in context of another transaction after sending the request to write changes to the volatile data structure to the store.

15. The computer storage medium of claim 12, further comprising performing recovery actions, comprising:

locating a head of a linked list, each member of the linked list associated with a logical copy that was to be written to a location of the store specified by the linked list;

iterating over the linked list until a member of the linked list is associated with a logical copy that was not written to the location associated with the member; and

in conjunction with iterating over the linked list, for each member for which a logical copy was written to the location specified by the member, updating a data structure to indicate a new location for an object associated with the logical copy.

16. The computer storage medium of claim 12, wherein the actions further comprise:

performing recovery actions comprising;

determining whether changes to the logical copy of the object and changes to the logical copy of each of at least one other object atomically bound with the object were written to the store, and

discarding changes written to the store, corresponding to the logical copy of the object and the logical copy of the at least one other object when changes corresponding to at least one of the logical copy of the object and the logical copy of each of the at least one other object are determined not to be written to the store.

17. In a computing environment, a system, comprising:

an interface operable to receive a request to modify an object involved in a transaction;

a store having a non-volatile memory and a volatile memory thereon;

a storage controller that potentially allows writes to the non-volatile memory to proceed in an order other than an order in which requests for the writes were received; and

an I/O manager operable to perform actions, comprising;

locating the object in a first storage location of the store,

creating a logical copy of the object that includes changes made to the object in context of the transaction,

determining a second storage location of the store for storing the logical copy,

sending a request to write the logical copy as changed to the second storage location, and

updating a volatile data structure to indicate that the logical copy is stored in the second storage location; and

a recovery manager operable to perform actions comprising;

determining whether the logical copy of the object as changed and a logical copy, as changed, of each of at least one other object atomically bound with the object were written to the second storage location, and

discarding changes written to the second storage location, corresponding to the logical copy of the object and the logical copy of the at least one other object when changes corresponding to at least one of the logical copy of the object and the logical copy of each of the at least one other object are determined not to be written to the second storage location.

18. The system of claim 17, wherein the interface is further operable to receive a request to modify one of the at least one other object involved in the transaction and wherein the I/O manager is further operable to perform additional actions, comprising:

creating an association that binds the one of the at least one other object and the object together; and

in conjunction with sending a request to write the logical copy as changed to the second storage location sending a request to write the association to the storage controller.

19. The system of claim 17, further comprising a checkpoint manager operable to send a request to write the volatile data structure to the storage controller and to send a flush request to the storage controller, the flush request instructing the storage controller to flush data from the volatile memory of the store to the non-volatile memory of the store.

20. The system of claim 17, wherein the recovery manager is further operable to determine whether the logical copy of the object as changed was written to the second storage location based on comparing a stored hash of the logical copy of the object as changed with a hash computed from content read from the second storage location, the recovery manager being further operable to update another data structure to indicate that the logical copy of the object is stored in the second storage location if the hashes are equivalent.