Distributed data storage

• US 8,688,630 B2
• Filed: 10/21/2009
• Issued: 04/01/2014
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Compuverde AB (Pure Storage, Inc.)
• Original Assignee: Compuverde AB (Pure Storage, Inc.)
• Inventors: Bernbo, Stefan, Melander, Christian, Persson, Roger, Petersson, Gustav
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US13/125,524
• Publication Number:
  US 20110295807A1
• Time in Patent Office: 1,623 Days
• Field of Search: None
• US Class Current: 707/610
• 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
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• 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/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

Abstract

The present invention relates to a distributed data storage system comprising a plurality of storage nodes. Using unicast and multicast transmission, a server application may read and write data in the storage system. Each storage node may monitor reading and writing operations on the system as well as the status of other storage nodes. In this way, the storage nodes may detect a need for replication of files on the system, and may carry out a replication process that serves to maintain a storage of a sufficient number of copies of files with correct versions at geographically diverse locations.

Claims

1. A method for maintaining data in a data storage system that includes a plurality of data storage nodes, the method being employed in a first data storage node in the data storage system, the method comprising:

the first data storage node monitoring two or more other storage nodes, wherein a node list stored at the first data storage node indicates that the two or more other storage nodes are members of a storage group, the first data storage node is also a member of the storage group, and each member of the storage group is configured to monitor the other members of the storage group in order to determine whether locally stored data needs to be replicated among the members of the storage group;

the first data storage node detecting, based on the monitoring, conditions in the data storage system that indicate that at least one storage node included on the node list is malfunctioning;

the first data storage node performing a local search of host lists stored on the first data storage node, and the first storage node determining that a data entity that is stored on the first data storage node is to be replicated based on a host list for the data entity indicating that the data entity was stored on the at least one malfunctioning storage node, wherein the host list for the data entity comprises an associated list identifying a subset of storage nodes within the storage group that store the data entity, and each of a plurality of data entities that are stored on the data storage node are associated with a corresponding host list that indicates which storage nodes store a corresponding data entity; and

the first data storage node initiating a replication process for the data entity based on detecting that the at least one storage node is malfunctioning and the host list for the data entity indicating that the data entity was stored on the at least one malfunctioning storage node.

2. A method according to claim 1, wherein monitoring the two or more other storage nodes comprises the first data storage node listening for heartbeat signals from the two or more other storage nodes.

3. A method according to claim 1, wherein a subsequent data replication procedure is performed based on the first data storage node detecting a data inconsistency with in the data storage system for a file stored at the first data storage node.

4. A method according to claim 1, further comprising maintaining replication list, wherein the replication list includes files that are to be replicated.

5. A method according to claim 4, wherein the replication list includes priorities.

6. A method according to claim 1, wherein the replication process comprises:

the first data storage node sending a multicast message enquiring whether recipients of the multicast message store the data entity;

the first data storage node determining whether the data entity is stored on a sufficient number of storage nodes; and

on condition it is determined that said data entity is not stored on a sufficient number of storage nodes, the first data storage node selecting at least one additional storage node and transmitting the data entity to the at least one additional storage node.

7. A method according to claim 6, further comprising the first data storage node updating said data entity on storage nodes containing obsolete versions of said data entity.

8. A method according to claim 1, further comprising the first data storage node sending a message to one or more storage nodes indicated on the host list, the message including a request to be a master node for the data entity.

9. A method according to claim 1, further comprising the first data storage node monitoring of reading operations carried out in the data storage system.

10. The method according to claim 1, further comprising:

the first data storage node sending a multicast message to two or more other storage nodes requesting whether the two or more other storage nodes can store the data entity;

the first data storage node receiving a response from a subset of the two or more other storage nodes;

the first data storage node selecting at least one storage node from the subset of responding nodes to store the data entity; and

the first data storage node updating the host list for the data entity to indicate that the at least one storage node from the subset stores the data entity.

11. The method according to claim 1, wherein the node list comprises a list of Internet Protocol (IP) addresses for other storage nodes in the storage group.

12. The method according to claim 11, wherein the node list is associated with a node list version number, the first data storage node monitoring the status of the two or more other storage nodes comprises the first data storage node monitoring for heartbeat signals sent from the two or more other storage nodes.

13. The method according to claim 12, wherein the heartbeat signals comprise a version number for a copy of the node list.

14. The method according to claim 1, wherein the replication process comprises the first data storage node sending one or more of a copy of the data entity or a copy of the host list for the data entity to another storage node for storage.

15. A data storage node for maintaining data in a data storage system that includes a plurality of data storage nodes, the data storage node comprising a processor configured to:

monitor two or more other storage nodes, wherein a node list stored at the data storage node indicates that the two or more other storage nodes are members of a storage group, the data storage node is also a member of the storage group, and each member of the storage group is configured to monitor the other members of the storage group in order to determine whether locally stored data needs to be replicated among the members of the storage group;

detect, based on the monitoring, conditions in the data storage system that indicate that at least one storage node included on the node list is malfunctioning;

perform a local search of host lists stored on the data storage node;

determine that a data entity that is stored on the data storage node is to be replicated based on a host list for the data entity indicating that the data entity was stored on the at least one malfunctioning storage node, wherein the host list for the data entity comprises an associated list identifying a subset of storage nodes within the storage group that store the data entity, and each of a plurality of data entities that are stored on the data storage node are associated with a corresponding host list that indicates which storage nodes store a corresponding data entity; and

initiate a replication process for the data entity based on detecting that the at least one storage node is malfunctioning and the host list for the data entity indicating that the data entity was stored on the at least on malfunctioning storage node.

16. The data storage node according to claim 15, wherein the data storage node is further configured to become a master for the data entity during the replication process.

17. The data storage node according to claim 16, wherein the data storage node is configured to create a master host list for the data entity during the replication process.

18. The data storage node according to claim 17, wherein the master host list comprises an indication of which version of the data entity is stored by each storage node included in the master host list.

19. The data storage node according to claim 15, wherein the data storage node is configured to send a copy of the data entity and to send a copy of the host list for the data entity to another storage node.

20. A data storage system comprising at least three data storage nodes organized as a storage group, wherein each data storage node in the storage group comprises a processor configured to:

monitor two or more other storage nodes, wherein a node list stored at the data storage node indicates that the two or more other storage nodes are members of the storage group, the data storage node is also a member of the storage group, and each member of the storage group is configured to monitor the other members of the storage group in order to determine whether locally stored data needs to be replicated among the members of the storage group;

detect, based on the monitoring, conditions in the data storage system that indicate that at least one storage node included on the node list is malfunctioning;

perform a local search of host lists stored on the data storage node;

determine that a data entity that is stored on the data storage node is to be replicated based on a host list for the data entity indicating that the data entity was stored on the at least one malfunctioning storage node, wherein the host list for the data entity comprises an associated list identifying a subset of storage nodes within the storage group that store the data entity, and each of a plurality of data entities that are stored on the data storage node are associated with a corresponding host list that indicates which storage nodes store a corresponding data entity; and

initiate a replication process for the data entity based on detecting that the at least one storage node is malfunctioning and the host list for the data entity indicating that the data entity was stored on the at least on malfunctioning storage node.