Distributed storage system capable of restoring data in case of a storage failure

• US 7,159,150 B2
• Filed: 12/31/2002
• Issued: 01/02/2007
• Est. Priority Date: 12/31/2002
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James L., Kenchammana-Hosekote, Deepak R., Ponceleon, Dulce B., Zaki, Omer A., Goodson, Garth R., Freitas, Richard F., Roskow, Marc T.
• Primary Examiner(s): Beausoliel; Robert
• Assistant Examiner(s): Ehne; Charles
• Application Number:
  US10/335,284
• Publication Number:
  US 20040128587A1
• Time in Patent Office: 1,463 Days
• Field of Search: 714/4, 714/6, 714/9
• US Class Current: 714/43
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• 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/2053 where persistent mass storage functionality or persistent mass storage control functionality is redundant error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A collective storage system and method for restoring data in the system after a failure in the system. The system includes multiple storage nodes that are interconnected by a network and store data as extents. There are also a set of Data Service (DS) agents for managing the extents, a set of Metadata Service (MDS) agents for managing metadata relating to the nodes and the extents, and a Cluster Manager (CM) agent in each node. After a node failure is detected by one of the CM agents, the agents responsible for coordinating the data restoring are notified of the failure. The agents generate a plan to restore the data extents affected by the failure, and then collectively restoring the affected extents based on the generated plan. The coordinating agents might be the MDS agents or DS agents. The failure might be a node failure or a disk failure.

Claims

1. A collective data storage system comprising:

a plurality of storage nodes connected by a network, each node storing data as extents;

a data service (DS) agent in each node for managing the extents in the node;

a plurality of metadata service (MDS) agents for managing metadata relating to the nodes and the extents, the MDS agents operating in a subset of the nodes;

a cluster manager (CM) agent in each node for detecting a failure in the system and notifying a subset of the DS or MDS agents of the failure,

wherein upon notification of the failure, the subset of DS or MDS agents independently generates a plan to restore the extents affected by the failure and collectively restoring the affected extents based on the plan; and

a persistent map that correlates the data extents with the nodes; and

wherein each MDS agent manages a subset of the map.

2. The storage system as recited in claim 1 further comprising an interface to allow a host application to access data stored in the system.

3. The storage system as in recited in claim 1 further comprising means for determining a subset of the nodes in which the MDS agents operate.

4. The storage system as recited in claim 1, wherein each CM agent maintains an ordered list of the nodes that are currently operating in the system.

5. The storage system as recited in claim 1, wherein each CM agent includes means for detecting a node failure.

6. The storage system as recited in claim 5, wherein said means for detecting a node failure includes means for detecting a missing heart-beat within a predetermined time interval.

7. The storage system as recited in claim 1, wherein each CM agent includes means for detecting a new node in the system.

8. The storage system as recited in claim 7, wherein said means for detecting a new node includes means for monitoring network messages from the new node.

9. The storage system as recited in claim 1, wherein each DS agent propagates updates to the extents in the associated node to other DS agents in the system.

10. The storage system as recited in claim 1, wherein each DS agent manages data caching in the associated node.

11. The storage system as recited in claim 1, wherein:

each node comprises a plurality of data disks; and

each DS agent includes means for detecting a failure of the disks in the associated node.

12. The storage system as recited in claim 11, wherein said means for detecting the disk failure is based on error rates of the disks.

13. The storage system as recited in claim 1, wherein the restore plan includes a list of the extents to be restored to re-establish data redundancy in the system.

14. The storage system as recited in claim 13, wherein the extents to be restored are collectively restored by the DS agents.

15. The storage system as recited in claim 13, wherein space is allocated in the nodes that are still operational to replace the extents affected by the failure.

16. The storage system as recited in claim 15, wherein data in the affected extents is determined and transferred to the allocated space.

17. The storage system as recited in claim 1, wherein:

one of the MDS agents is notified of the failure; and

the notified MDS agent determines those extents affected by the failure based on an Extent_To_Node map.

18. The storage system as recited in claim 1, wherein:

the DS agents are notified of the failure; and

the notified DS agents determine those extents that have data on a failed node based on an Extent To Node map.

19. A method for restoring data in a collective storage system having a plurality of storage nodes interconnected by a network and storing data as extents, Data Service (DS) agents for managing the extents, Metadata Service (MDS) agents for managing metadata relating to the nodes and the extents, and Cluster Manager (CM) agents, the DS agents managing the extents in each node, the method comprising the steps of:

detecting a failure in the system by one of the CM agents;

notifying a subset of the DS or MDS agents of the failure;

generating, by the notified DS or MDS agents independently, a plan to restore the data extents affected by the failure; and

collectively restoring the affected extents based on the generated plan;

wherein each node includes a plurality or disk drives;

the detected failure is a disk failure; and

the disk failure is detected by a DS agent based on error rates of the disks.

20. The method as recited in claim 19, wherein the detected failure is a node failure.

21. The method as recited in claim 20, wherein the node failure is detected based on a missing heart-beat within a predetermined time interval.

22. The method as recited in claim 19, wherein the step of generating the restore plan includes the steps of;

determining the extents affected by the failure; and

allocating space in the nodes that are still operational to replace the affected extents.

23. The method as recited in claim 22, wherein the step of restoring includes the steps of:

determining data in the affected extents; and

transferring the determined data to the allocated space.

24. The method as recited in claim 19, wherein:

each extent comprises a group of data fragments each residing on a different node, the DS agent associated with one of the fragments being a leader of the group;

if the node on which the leader resides fails, then a new leader is chosen for the group as part of the data restoring; and

the leader is notified of the fragments affected by the failure.

25. The method as recited in claim 19, wherein each DS agent includes means for managing data caching and means for propagating updates on the data extents to other nodes.

26. The method as recited in claim 19, wherein each DS agent includes means for propagating updates on the data extents of the DS agent to other nodes.

27. The method as recited in claim 19 further comprising the step of determining a subset of the nodes in which the MDS agents operate.

28. The method as recited in claim 19 further comprising the step of maintaining, by each CM agent, an ordered list of the nodes that are currently operating in the system.

29. The method as recited in claim 19 further comprising the step of detecting a node failure by a CM agent.

30. The method as recited in claim 29, wherein the step of detecting a node failure includes the step of detecting a missing heart-beat within a predetermined time interval.

31. The method as recited in claim 19 further comprising the step of detecting a new node in the system.

32. The method as recited in claim 31, wherein the step of detecting a new node includes the step of monitoring network messages from the new node.

33. The method as recited in claim 19 further comprising the step of propagating updates on the extents, by the DS agent in one of the nodes, to the DS agents in other nodes.

34. The method as recited in claim 19, wherein the agents notified of the failure are the MDS agents.

35. The method as recited in claim 19, wherein the agents notified of the failure are the DS agents.

36. A computer-program product for restoring data in a collective storage system having a plurality of storage nodes interconnected by a network and storing data as extents, Data Service (DS) agents for managing the extents, Metadata Service (MDS) agents for managing metadata relating to the nodes and the extents, and Cluster Manager (CM) agents, the DS agents managing the extents in each node, the computer-program product comprising a computer readable medium comprising program code for:

detecting a failure in the system by one of the CM agents;

notifying a subset of the DS or MDS agents of the failure;

generating, by the notified DS or MDS agents independently, a plan to restore the extents affected by the failure;

collectively restoring the affected extents based on the generated plan;

wherein the generating the restore plan includes the steps of;

determining the extents affected by the failure;

allocating space in the nodes that are still operational to replace the affected extents; and

wherein the restoring includes the steps of;

determining data in the affected extents; and

transferring the determined data to the allocated space.