Consistency without ordering dependency

• US 8,996,829 B2
• Filed: 04/29/2013
• Issued: 03/31/2015
• Est. Priority Date: 12/11/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Miller, Thomas J., Cargille, Jonathan M., Tipton, William R., Verma, Surendra
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US13/872,896
• Publication Number:
  US 20130311733A1
• Time in Patent Office: 701 Days
• Field of Search: 711/141, 711/162
• 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 modified in context of a transaction;

creating, by the computer, logical copies of the objects that are modified in the context of the transaction while maintaining originals of the objects on a store;

indicating that storage locations associated with the originals of the objects are available for use;

indicating that storage locations associated with the logical copies are valid after successfully flushing all logical copies to a non-volatile memory of the store;

creating a write plan that indicates an intention of where on the store the logical copies are to be written, the write plan including a value indicative of correct content of one or more of the logical copies; and

sending a request to write the write plan to the store.

2. The method of claim 1, wherein creating logical copies of the objects comprises creating copies of portions of the objects that are modified during the transaction.

3. The method of claim 2, where the creating logical copies of the objects further comprises creating a first set of pointers that refer to the portions of the objects that are modified during the transaction and creating a second set of pointers that refer to non-changed portions of the objects that are modified during the transaction, the first set of pointers and the second set of pointers usable to reference the portions that are modified and the non-changed portions to construct the objects as modified.

4. The method of claim 1, further comprising locating a first set of storage locations of the store for the objects that are involved in the transaction by using identifiers of the objects as keys in a lookup table that associates the keys with locations at which the objects are stored in the store.

5. The method of claim 1, where creating the write plan comprises creating a linked list that references each of the objects.

6. The method of claim 5, where the creating the linked list 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, further comprising sending 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, where the waiting to send the 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 a storage location of a logical copy of an object modified in a context of the another transaction.

10. The method of claim 1, further comprising performing recovery actions, comprising:

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 write plan indicates that the logical copies were to be written, 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 actions.

11. At least one computer storage device storing 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 a write plan to the store, the write plan indicating an intention of writing the logical copy as changed to the second storage location, the write plan including a value indicative of correct content of the logical copy as changed;

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;

sending a request to write changes to the updated volatile data structure to the store; and

sending, to the store in conjunction with the sending the request to write the changes, a flush command that instructs a controller of the store to write cache associated with the store to non-volatile memory of the store.

12. The at least one computer storage device of claim 11, where the 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.

13. The at least one computer storage device of claim 11, 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.

14. The at least one computer storage device of claim 11, 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.

15. 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 allows writes to the non-volatile memory to proceed in an order other than an order in which requests for the writes were received;

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 a write plan to the store, the write plan indicating an intention of writing the logical copy as changed to the second storage location, the write plan including a value indicative of correct content of the logical copy as changed,

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 as changed is stored in the second storage location; and

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.

16. The system of claim 15, wherein the interface is further operable to receive a request to modify another 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 another 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.

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