Managing workflow communication in a distributed storage system

• US 8,090,683 B2
• Filed: 03/11/2009
• Issued: 01/03/2012
• Est. Priority Date: 02/23/2009
• Status: Expired due to Fees

• Current Assignee: Autonomy Incorporated (HP Inc.)
• Original Assignee: Iron Mountain Incorporated
• Inventors: Beaman, Peter D., Tran, Tuyen M., Newson, Robert S.
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US12/402,469
• Publication Number:
  US 20100217931A1
• Time in Patent Office: 1,028 Days
• Field of Search: 707/610, 707/626, 707/651, 707/652, 707/656, 707/658, 707/687, 707/692
• US Class Current: 707/610
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence

Abstract

In a data storage system having a plurality of storage nodes storing replicas of stripes, one storage node serves as a primary stripe node for a stripe. Client applications using the data storage system request operations affecting metadata stored in the stripe, and the data storage system creates workflow objects to implement the requested operation. Once the operation is completed, the workflow is acknowledged. A method for establishing a new primary stripe node comprises performing, by a selected storage node, a feasibility determination to determine the feasibility of the selected storage node becoming the new primary stripe node. It is feasible to become a new primary stripe node when doing so does not cause workflows that have been acknowledged, or that will be acknowledged, to result in strays.

Claims

1. A computer-implemented method for determining feasibility of a selected stripe node becoming a new primary stripe node for a stripe in a data storage system, the data storage system comprising a plurality of nodes storing replicas of the stripe, the method comprising:

computing a test generation for a journal associated with the selected stripe node and corresponding to the stripe,

wherein the journal comprises entries that are assigned generations greater than previous entries; and

comparing, by a feasibility module, a greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe with the test generation, and

when the greatest generation for each of the plurality of nodes storing replicas of the stripe is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node.

2. The method of claim 1, wherein the test generation comprises the generation that would be assigned to an entry that would be next recorded in the journal.

3. The method of claim 1, wherein the test generation comprises the greatest generation assigned to entries in the journal associated with the selected stripe node.

4. The method of claim 1, further comprising:

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

5. The method of claim 1, wherein the greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe is stored in an endorsement repository at the selected stripe node.

6. The method of claim 1,

wherein the plurality of nodes storing replicas of the stripe comprises a subset of the plurality of nodes storing replicas of the stripe, the subset having equivalent greatest generations corresponding to the replicas of the stripe,

wherein the subset has a minimum number of replicas of the stripe, and

wherein the minimum number is chosen to achieve a desired level of durability.

7. The method of claim 6, wherein

when the greatest generation for the nodes in the subset is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node;

and

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

8. The method of claim 1, wherein, prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node.

9. The method of claim 8, wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node comprises a message containing an epoch of a new stripe map.

10. The method of claim 1, wherein becoming the new primary stripe node comprises writing a first entry in the journal associated with the selected stripe node, the first entry being assigned the test generation.

11. The method of claim 1,

wherein each of the plurality of nodes storing replicas of the stripe stores a stripe map, the stripe map comprising an indication of which of the plurality of nodes storing replicas of the stripe is a primary stripe node, and

wherein the computing is triggered by receiving a new stripe map at the selected stripe node, wherein the new stripe map indicates that the selected stripe node is intended to become the new primary stripe node.

12. The method of claim 11,

wherein prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe,

wherein the new stripe map is associated with an epoch that is greater than any epoch for previous stripe maps, and

wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe comprises a message containing the epoch of the new stripe map.

13. A data storage system comprising:

a plurality of nodes storing replicas of a stripe;

a selected stripe node having a journal corresponding to a stripe,

wherein the journal comprises entries that are assigned generations greater than previous entries;

a feasibility module comprising computer readable instructions for determining feasibility of the selected stripe node becoming a new primary stripe node for the stripe, wherein the determining feasibility comprises;

computing a test generation for the journal corresponding to the stripe; and

comparing, by the feasibility module, a greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe with the test generation, and

when the greatest generation for each of the plurality of nodes storing replicas of the stripe is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node.

14. The data storage system of claim 13, wherein the selected stripe node is one of a plurality of nodes storing replicas of a stripe.

15. The data storage system of claim 13, wherein the test generation comprises the generation that would be assigned to an entry that would be next recorded in the journal.

16. The data storage system of claim 13, wherein the test generation comprises the greatest generation assigned to entries in the journal associated with the selected stripe node.

17. The data storage system of claim 13, further comprising:

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

18. The data storage system of claim 13, wherein the greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe is stored in an endorsement repository at the selected stripe node.

19. The data storage system of claim 13,

wherein the plurality of nodes storing replicas of the stripe comprises a subset of the plurality of nodes storing replicas of the stripe, the subset having equivalent greatest generations corresponding to the replicas of the stripe,

wherein the subset has a minimum number of replicas of the stripe, and

wherein the minimum number is chosen to achieve a desired level of durability.

20. The data storage system of claim 19, wherein

when the greatest generation for the nodes in the subset is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node;

and

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

21. The data storage system of claim 13, wherein, prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node.

22. The data storage system of claim 21, wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node comprises a message containing an epoch of a new stripe map.

23. The data storage system of claim 13, wherein becoming the new primary stripe node comprises writing a first entry in the journal associated with the selected stripe node, the first entry being assigned the test generation.

24. The data storage system of claim 13,

wherein each of the plurality of nodes storing replicas of the stripe stores a stripe map, the stripe map comprising an indication of which of the plurality of nodes storing replicas of the stripe is a primary stripe node, and

wherein the computing is triggered by receiving a new stripe map at the selected stripe node, wherein the new stripe map indicates that the selected stripe node is intended to become the new primary stripe node.

25. The data storage system of claim 24,

wherein prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe,

wherein the new stripe map is associated with an epoch that is greater than any epoch for previous stripe maps, and

wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe comprises a message containing the epoch of the new stripe map.

26. A computer program product comprising a non-transitory computer usable medium having a computer readable program code stored therein, the computer readable program code configured to be executed to implement a method for determining feasibility of a selected stripe node becoming a new primary stripe node for a stripe in a data storage system, the data storage system comprising a plurality of nodes storing replicas of the stripe, the method comprising:

computing a test generation for a journal associated with the selected stripe node and corresponding to the stripe,

wherein the journal comprises entries that are assigned generations greater than previous entries; and

comparing, by a feasibility module, a greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe with the test generation, and

when the greatest generation for each of the plurality of nodes storing replicas of the stripe is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node.

27. The computer program product of claim 26, wherein the test generation comprises the generation that would be assigned to an entry that would be next recorded in the journal.

28. The computer program product of claim 26, wherein the test generation comprises the greatest generation assigned to entries in the journal associated with the selected stripe node.

29. The computer program product of claim 26, further comprising:

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

30. The computer program product of claim 26, wherein the greatest generation corresponding to the stripe for each of the plurality of nodes storing replicas of the stripe is stored in an endorsement repository at the selected stripe node.

31. The computer program product of claim 26,

wherein the plurality of nodes storing replicas of the stripe comprises a subset of the plurality of nodes storing replicas of the stripe, the subset having equivalent greatest generations corresponding to the replicas of the stripe,

wherein the subset has a minimum number of replicas of the stripe, and

wherein the minimum number is chosen to achieve a desired level of durability.

32. The computer program product of claim 31, wherein

when the greatest generation for the nodes in the subset is less than the test generation, determining that it is feasible for the selected stripe node to become the new primary stripe node;

and

when the greatest generation for any of the plurality of nodes storing replicas of the stripe is greater than or equal to the test generation, determining that it is not feasible for the selected stripe node to become the new primary stripe node.

33. The computer program product of claim 26, wherein, prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node.

34. The computer program product of claim 33, wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node comprises a message containing an epoch of a new stripe map.

35. The computer program product of claim 26, wherein becoming the new primary stripe node comprises writing a first entry in the journal associated with the selected stripe node, the first entry being assigned the test generation.

36. The computer program product of claim 26,

wherein each of the plurality of nodes storing replicas of the stripe stores a stripe map, the stripe map comprising an indication of which of the plurality of nodes storing replicas of the stripe is a primary stripe node, and

wherein the computing is triggered by receiving a new stripe map at the selected stripe node, wherein the new stripe map indicates that the selected stripe node is intended to become the new primary stripe node.

37. The computer program product of claim 36,

wherein prior to determining that it is feasible to become the new primary stripe node, each of the plurality of nodes storing replicas of the stripe communicates, to the selected stripe node, a commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe,

wherein the new stripe map is associated with an epoch that is greater than any epoch for previous stripe maps, and

wherein the commitment not to endorse generations greater than the test generation for the journal associated with the selected stripe node and corresponding to the stripe comprises a message containing the epoch of the new stripe map.