Gracefully degradable versioned storage systems

• US 7,849,354 B2
• Filed: 06/12/2007
• Issued: 12/07/2010
• Est. Priority Date: 06/12/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Levin, Roy, Prabhakaran, Vijayan, Ramasubramanian, Venugopalan, Thekkath, Chandramohan A., Zhou, Lidong
• Primary Examiner(s): Lohn; Joshua
• Assistant Examiner(s): TRUONG, LOAN
• Application Number:
  US11/811,780
• Publication Number:
  US 20080313496A1
• Time in Patent Office: 1,274 Days
• Field of Search: 714/6, 714/15, 707/695, 717/170
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality

Abstract

Multiple versions of data on different sets of machines allow a system to degrade gracefully even when experiencing excessive failures. When excessive failures cause the latest versions to be unavailable, the system becomes degraded, but still offers an old version if available. A most recent coherent set of the available older versions is found and provided. The degree of degradation increases gradually as the system experiences more and more failures. Graceful degradation is desirably complementary to fault tolerance.

Claims

1. A method for use in a distributed storage system, the method comprising:

maintaining a plurality of versions of a data item including a latest version and an older version, wherein the plurality of versions of the data item include a plurality of older versions of the data item, each older version being associated with a different time based on storage of that older version of the data item;

entering a degraded state on the distributed storage system, wherein the degraded state has a degree of degradation based on the version of the data item that is used during processing in the degraded state; and

if the latest version of the data item is unavailable in the degraded state, then using the older version of the data item during processing in the degraded state.

2. The method of claim 1, wherein entering the degraded state occurs when a number of failures exceeds a threshold.

3. The method of claim 2, further comprising using a fault tolerance mechanism associated with the distributed system to determine when the number of failures exceeds the threshold.

4. The method of claim 1, further comprising storing the versions of the data item prior to entering the degraded state.

5. The method of claim 1, further comprising providing an indication that the processing of the data item in the degraded state is based on the older version of the data item.

6. The method of claim 1, further comprising leaving the degraded state and returning to a normal operating state after the distributed storage system recovers.

7. The method of claim 1, wherein if the latest version of the data item is unavailable in the degraded state, then using the latest available older version of the data item during processing in the degraded state.

8. The method of claim 1, wherein a plurality of consistent degraded views of the distributed storage system is maintained during processing in the degraded state.

9. The method of claim 8, wherein the consistent degraded views are maintained using at least one of a timestamp-based design, a dependency-based design, or a weak-dependency-based design.

10. The method of claim 1, further comprising receiving additional versions of the data item while in the degraded state, branching the additional versions while in the degraded state using a plurality of branches, and merging the branches while in a normal operating state after the distributed storage system recovers.

11. The method of claim 1, wherein maintaining the plurality of versions of the data item comprises storing a timestamp for each version of the data item as metadata.

12. A distributed storage system comprising:

a versioned data store comprising a plurality of data storage devices across which a plurality of versions of a data item are stored, including a latest version and older versions; and

a processor that determines whether to enter a degraded state, and during processing in the degraded state, determines whether to use the latest version of the data item or one of the older versions of the data item, wherein the processor provides data for use by an output device to provide an indication to a user or a client that the processing of the data item in the degraded state is based on one of the older versions of the data item.

13. The system of claim 12, further comprising a fault tolerance mechanism, wherein the degraded state is entered when a number of failures in the system exceeds the capability of the fault tolerance mechanism.

14. The system of claim 12, further comprising an index server that maintains an index that tracks the versions of the data item.

18. The system of claim 13, wherein the fault tolerance mechanism determines when the number of failures exceeds the capability of the fault tolerance mechanism.

19. The system of claim 12, wherein the processor leaves the degraded state and returns to a normal operating state after the distributed storage system recovers.

20. The system of claim 12, wherein the versioned data store maintains a plurality of consistent degraded views of the distributed storage system during processing in the degraded state, wherein the consistent degraded views are maintained using at least one of a timestamp-based design, a dependency-based design, or a weak-dependency-based design.

15. A method for use in a distributed storage system, the method comprising:

receiving an update to a version of a data item that is stored on a storage server;

creating a new version of the data item; and

storing the new version and a plurality of older versions of the data item with metadata on a different storage server, the metadata is used to maintain consistent degraded views of the distributed storage system during processing in a degraded state, wherein the degraded state has a degree of degradation based on the version of the data item that is used during processing in the degraded state.

16. The method of claim 15, wherein the metadata corresponds to at least one of a timestamp-based design, a dependency-based design, or a weak-dependency-based design.

17. The method of claim 15, further comprising determining whether the version of the data item that is stored on the storage server and the new version are coherent.