Arrangement for recovery of data by network nodes based on retrieval of encoded data distributed among the network nodes

• US 20050283645A1
• Filed: 02/07/2005
• Published: 12/22/2005
• Est. Priority Date: 06/03/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Toebes, John, Walker, Douglas Jay, Turner, Bryan C.
• Granted Patent: US 7,818,607 B2
• Time in Patent Office: Days
• US Class Current: 714/4.11
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/14 Multichannel or multilink protocols
• 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: H04Q 2213/13034 A/D conversion, code compression/expansion
• CPC Class Codes: H04Q 2213/13174 Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13215 Code checking, CRC

Abstract

Distributed data, having been stored in a distributed storage system as a collection of distributed data elements, is recovered based on connection of multiple user nodes, each user node having stored selected distributed data elements as a corresponding portion of the distributed data during replication of the distributed data elements throughout the distributed storage system. Each distributed data element is identifiable by a corresponding unique object identifier (OID). Each user node includes a discovery resource for discovering reachable user nodes, a local cache configured for identifying at least the corresponding portion of the distributed data based on the respective OIDs, and an identification service module configured for resolving a data object to a corresponding OID, via the corresponding local cache, or based on sending a query to the reachable user nodes. Hence, user nodes can recover distributed data based on exchanging resolution information and OID information.

Claims

1. A method in a user node configured for connection to a network, the method comprising:

connecting to a data link configured for providing connectivity with a connected user node;

establishing a recovered data storage system based on stored data elements having been replicated throughout a distributed storage system, each of the stored data elements having a corresponding unique object identifier that is independent of any storage address on a storage medium, the establishing including;

(1) storing, in a table for each locally-stored data element having been stored in the user node based on the replication throughout the distributed storage system, the corresponding unique object identifier and a corresponding stored location of the corresponding locally-stored data element,

(2) detecting whether the connected user node is reachable via the data link,

(3) selectively sending to the connected user node at least one of the unique object identifiers stored in the table in response to a query from the connected user node that specifies an attribute of the stored data element associated with the least one unique object identifier,

(4) selectively sending to the connected user node a second query that specifies an attribute of a data element determined to be absent from the user node, and

(5) selectively storing, in response to reception thereof from the connected user node, any received unique object identifiers that are distinct from the unique object identifiers stored in the table, the unique object identifiers and said any received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said any received unique object identifiers including the unique object identifier for the data element determined to be absent from the user node.

2. The method of claim 1, wherein one of the locally-stored data elements corresponds to a directory entry configured for identifying a structure of a prescribed directory utilized by the user node, the selectively sending of the second query comprising:

detecting within the directory entry an absence of subdirectory information for a subdirectory; and

sending a query to the connected user node for the subdirectory information based on at least one of a name of the subdirectory and the corresponding unique object identifier of the subdirectory;

the selectively storing including storing in the table, upon receipt from the connected user node, the subdirectory information as the data element determined to be absent from the user node.

3. The method of claim 2, wherein the selectively sending of the second query includes sending the at least one unique object identifier and a corresponding name for the corresponding locally-stored data element.

4. The method of claim 3, wherein the selectively sending at least one of the unique object identifiers includes:

receiving from the connected user node a query specifying a name for one of the locally-stored data elements as the attribute;

resolving the name by supplying to the connected user node the at least one unique object identifier and selectively supplying the locally-stored data element.

5. The method of claim 1, wherein the selectively sending of the second query includes:

receiving from a locally-executed application instance a request specifying a corresponding name of one of the stored data elements;

determining whether the name and the corresponding unique object identifier of the corresponding one stored data element are stored locally;

forwarding the request to the connected user node based on a determined absence of any one of the name and the corresponding unique object identifier of the corresponding one stored data element locally within the user node, the attribute in the second query including the name;

the selectively storing including caching a response from the user node that specifies at least one of the unique object identifier, the corresponding stored location, and the corresponding data element identified by the name specified in the request.

6. The method of claim 1, further comprising:

detecting a second connected user node reachable via the data link;

wherein the establishing further includes;

(6) selectively sending to the second connected user node at least one of the unique object identifiers stored in the table based on a third query from the second connected user node,

(7) selectively sending to the second connected user node a fourth query that specifies an attribute of a second data element determined to be absent from the user node, and

(8) selectively storing in the table, in response to reception thereof from the second connected user node, any second received unique object identifiers that are distinct from the unique object identifiers and received unique object identifiers stored in the table, the unique object identifiers, said any received unique object identifiers, and said any second received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said second received unique object identifiers including the unique object identifier for the second data element determined to be absent from the user node.

7. A method in a network having a data link configured for providing connectivity, the method comprising:

connecting by a first user node to the data link, the first user node having a first group of stored data elements having been stored in the first user node based on the first user node having been in communication with a distributed storage system having replicated the stored data elements, each of the stored data elements having a corresponding unique object identifier that is independent of any storage address on a storage medium, the first user node further including a table having a corresponding first group of the unique object identifiers for identifying the respective first group of data elements;

connecting by a second user node to the data link, the second user node having a second group of the stored data elements having been stored in the second user node based on the second user node having been in communication with the distributed storage system having replicated the stored data elements, the second user node further including a corresponding table having a corresponding second group of the unique object identifiers for identifying the respective second group of data elements;

selectively supplying by at least one of the first and second user nodes at least a corresponding distinct one of the unique object identifiers from among the first and second groups, respectively, based on discovery of the second and first user nodes and in response to a query received by the at least one of the first and second user nodes, the first and second user nodes establishing a recovered data storage system based on a union of the first and second groups of unique object identifiers based on mutual discovery of the first and second user nodes via the data link, each unique object identifier being independent of any storage address on any storage medium.

8. The method of claim 7, wherein each table for each corresponding user node is configured for identifying, for each corresponding group of stored data elements, the corresponding group of respective unique object identifiers and respective stored locations of the stored data elements.

9. The method of claim 8, wherein one of the data elements in the first group corresponds to a directory entry configured for identifying a structure of a prescribed directory utilized by the first user node, the method further comprising:

detecting by the first user node an absence within the directory entry of subdirectory information for a subdirectory;

sending the query by the first user node to the second user node for the subdirectory information based on query data that includes at least one of a name of the subdirectory and the corresponding unique object identifier of the subdirectory;

retrieving, by the second user node, the subdirectory information from the corresponding table using the query data, the selectively supplying including sending a reply to the first user node including the query data and the subdirectory information; and

storing by the first user node, upon receipt of the reply from the second user node, the subdirectory information into the corresponding table.

10. The method of claim 9, wherein the selectively supplying includes sending said at least a corresponding distinct one of the unique object identifiers and a corresponding name for the corresponding stored data element.

11. The method of claim 7, further comprising:

in the first user node;

(1) receiving from a locally-executed application instance a request specifying a corresponding name of one of the stored data elements;

(2) determining whether the name and the corresponding unique object identifier of the corresponding one stored data element are stored locally;

(3) forwarding the request to the second user node based on a determined absence of any one of the name and the corresponding unique object identifier of the corresponding one stored data element locally within the user node; and

(4) caching a response from the second user node that specifies at least one of the unique object identifier, the corresponding stored location, and the corresponding data element identified by the name specified in the request.

12. The method of claim 7, further comprising:

connecting by a third user node to the data link, the third user node having a third group of the stored data elements having been stored in the third user node based on the third user node having been in communication with the distributed storage system having replicated the stored data elements, the third user node further including a corresponding table having a corresponding third group of the unique object identifiers for identifying the respective third group of data elements;

the selectively supplying further including supplying between the first, second, and third user nodes at least a corresponding distinct second one of the unique object identifiers from among the first, second and third groups based on discovery of the third user node and in response to a query from the third user node, the first, second, and third user nodes establishing the recovered data storage system based on the union of the first, second, and third group of unique object identifiers.

13. A network node comprising:

a data storage medium configured for storing locally-stored data elements, the locally stored data elements having been stored on the data storage medium based on the network node having been in communication with a distributed storage system having replicated stored data elements that include the locally-stored data elements, each of the stored data elements having a corresponding unique object identifier that is independent of any storage address on a storage medium, the data storage medium including a table configured for storing, for each said locally-stored data element, a corresponding unique object identifier and a corresponding stored location of the corresponding locally-stored data element;

a network connection resource configured for connecting to a data link that is configured for providing connectivity with a connected user node;

a discovery resource configured for detecting a presence of the connected user node based on whether the connected user node is reachable via the data link, the discovery resource configured for communicating with the connected user node for establishment of a recovered data storage system based on a prescribed authentication with the connected user node;

an identification module configured for identifying a stored data element in response to a query from any one of an executable application in the user node and the connected user node, the identification module configured for selectively sending to the connected user node at least one of the unique object identifiers stored in the table based on the corresponding locally-stored data element having been specified in the query and having been received from the connected user node, the identification module configured for selectively storing, in response to reception thereof from the connected user node, any received unique object identifiers that are distinct from the unique object identifiers stored in the table, the unique object identifiers and said any received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system.

14. The node of claim 13, wherein:

the data storage medium is configured for storing in one of the locally-stored data elements a directory entry configured for identifying a structure of a prescribed directory utilized by the user node,

the identification module, in response to detecting within the directory entry an absence of subdirectory information for a subdirectory, is configured for sending a query to the connected user node for the subdirectory information based on at least one of a fully qualified name of the subdirectory and the corresponding unique object identifier of the subdirectory;

the identification module configured for storing in the table, upon receipt from the connected user node, the subdirectory information.

15. The node of claim 14, wherein the identification module is configured for sending the at least one unique object identifier and a corresponding name for the corresponding locally-stored data element.

16. The node of claim 13, wherein:

the query is from the connected user node and specifies a name for one of the locally-stored data elements;

the identification module configured for resolving the name by supplying to the connected user node the corresponding unique object identifier and selectively supplying the locally-stored data element.

17. The node of claim 13, wherein the identification module includes:

an object identifier lookup module configured for determining from the table the corresponding stored location relative to the corresponding unique object identifier; and

a identification service module configured for resolving a name of a file relative to a corresponding one of the unique object identifiers for a corresponding stored data element having information associated with the file, the identification service module configured for selectively sending the query, having been received from the executable application, to the connected user node in response to a determined absence of the name specified in the query within the network node, the identification service module configured for supplying a request to the object identifier lookup module, specifying the corresponding unique object identifier for the name specified in the query, for the corresponding file in response to detecting the name specified in the query and the corresponding unique object identifier in the table.

18. The node of claim 17, wherein the object identifier lookup module is configured for sending to the connected user node a second request, specifying an unlocatable unique object identifier, based on a determined absence in the local table of the corresponding stored location for the corresponding data element identified by the unlocatable unique object identifier, the object identifier lookup module configured for caching a response from the user node that specifies at least one of the unique object identifier, the corresponding stored location, and the corresponding data element identified by the name specified in the request.

19. The node of claim 13, wherein:

the discovery resource is configured for detecting a second connected user node reachable via the data link;

the identification module configured for selectively sending to the second connected user node at least one of the unique object identifiers stored in the table based on detecting that the second connected user node is reachable via the data link and in response to a query from the second connected user node, and selectively storing in the table, in response to reception thereof from the second connected user node, any second received unique object identifiers that are distinct from the unique object identifiers and received unique object identifiers stored in the table, the unique object identifiers, said any received unique object identifiers, and said any second received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system.

20. A computer readable medium having stored thereon sequences of instructions for connection to a network, the sequences of instructions including instructions for:

connecting to a data link configured for providing connectivity with a connected user node;

establishing a recovered data storage system based on stored data elements having been replicated throughout a distributed storage system, each of the stored data elements having a corresponding unique object identifier that is independent of any storage address on a storage medium, the establishing including;

(1) storing, in a table for each locally-stored data element having been stored in the user node based on the replication throughout the distributed storage system, the corresponding unique object identifier and a corresponding stored location of the corresponding locally-stored data element,

(2) detecting whether the connected user node is reachable via the data link,

(3) selectively sending to the connected user node at least one of the unique object identifiers stored in the table in response to a query from the connected user node that specifies an attribute of the stored data element associated with the at least one unique object identifier,

(4) selectively sending to the connected user node a second query that specifies an attribute of a data element determined to be absent from the user node, and

(5) selectively storing, in response to reception thereof from the connected user node, any received unique object identifiers that are distinct from the unique object identifiers stored in the table, the unique object identifiers and said any received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said any received unique object identifiers including the unique object identifier for the data element determined to be absent from the user node.

21. The medium of claim 20, wherein one of the locally-stored data elements corresponds to a directory entry configured for identifying a structure of a prescribed directory utilized by the user node, the selectively sending of a second query including:

detecting within the directory entry an absence of subdirectory information for a subdirectory;

sending a query to the connected user node for the subdirectory information based on at least one of a name of the subdirectory and the corresponding unique object identifier of the subdirectory;

the selectively storing including storing in the table, upon receipt from the connected user node, the subdirectory information as the data element determined to be absent from the user node.

22. The medium of claim 21, wherein the selectively sending of the second query includes sending the at least one unique object identifier and a corresponding name for the corresponding locally-stored data element.

23. The medium of claim 22, wherein the selectively sending at least one of the unique object identifiers includes:

receiving from the connected user node a query specifying a name for one of the locally-stored data elements;

resolving the name by supplying to the connected user node the at least one unique object identifier and selectively supplying the locally-stored data element.

24. The medium of claim 20, wherein the selectively sending of the second query includes:

receiving from a locally-executed application instance a request specifying a corresponding name of one of the stored data elements;

determining whether the name and the corresponding unique object identifier of the corresponding one stored data element are stored locally;

forwarding the request to the connected user node based on a determined absence of any one of the name and the corresponding unique object identifier of the corresponding one stored data element locally within the user node;

the selectively storing including caching a response from the user node that specifies at least one of the unique object identifier, the corresponding stored location, and the corresponding data element identified by the name specified in the request.

25. The medium of claim 20, further comprising instructions for:

detecting a second connected user node reachable via the data link;

wherein the establishing further includes;

(6) selectively sending to the second connected user node at least one of the unique object identifiers stored in the table based on a third query from the second connected user node,

(7) selectively sending to the second connected user node a fourthe query that specifies an attribute of a second data element determined to be absent from the user node, and

(8) selectively storing in the table, in response to reception thereof from the second connected user node, any second received unique object identifiers that are distinct from the unique object identifiers and received unique object identifiers stored in the table, the unique object identifiers, said any received unique object identifiers, and said any second received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said second received unique object identifiers including the unique object identifier for the second data element determined to be absent from the user node.

26. A network node comprising:

means for connecting to a data link configured for providing connectivity with a connected user node; and

means for establishing a recovered data storage system based on stored data elements having been replicated throughout a distributed storage system, each of the stored data elements having a corresponding unique object identifier that is independent of any storage address on a storage medium, the means for establishing configured for;

(1) storing, in a table for each locally-stored data element having been stored in the user node based on the replication throughout the distributed storage system, the corresponding unique object identifier and a corresponding stored location of the corresponding locally-stored data element,

(2) detecting whether the connected user node is reachable via the data link,

(3) selectively sending to the connected user node at least one of the unique object identifiers stored in the table in response to a query from the connected user node that specifies an attribute of the stored data element associated with the at least one unique object identifier,

(4) selectively sending to the connected user node a second query that specifies an attribute of a data element determined to be absent from the user node, and

(5) selectively storing, in response to reception thereof from the connected user node, any received unique object identifiers that are distinct from the unique object identifiers stored in the table, the unique object identifiers and said any received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said any received unique object identifiers including the unique object identifier for the data element determined to be absent from the user node.

27. The node of claim 26, wherein one of the locally-stored data elements corresponds to a directory entry configured for identifying a structure of a prescribed directory utilized by the user node, the means for establishing configured for:

detecting within the directory entry an absence of subdirectory information for a subdirectory;

sending a query to the connected user node for the subdirectory information based on at least one of a name of the subdirectory and the corresponding unique object identifier of the subdirectory; and

storing in the table, upon receipt from the connected user node, the subdirectory information as the data element determined to be absent from the user node.

28. The node of claim 27, wherein the means for establishing is configured for sending the at least one unique object identifier and a corresponding name for the corresponding locally-stored data element.

29. The node of claim 28, wherein the means for establishing is configured for:

receiving from the connected user node a query specifying a name for one of the locally-stored data elements; and

resolving the name by supplying to the connected user node the corresponding unique object identifier and selectively supplying the locally-stored data element.

30. The node of claim 26, wherein the means for establishing is configured for:

receiving from a locally-executed application instance a request specifying a corresponding name of one of the stored data elements;

determining whether the name and the corresponding unique object identifier of the corresponding one stored data element are stored locally;

forwarding the request to the connected user node based on a determined absence of any one of the name and the corresponding unique object identifier of the corresponding one stored data element locally within the user node, the attribute in the second query including the name;

caching a response from the user node that specifies at least one of the unique object identifier, the corresponding stored location, and the corresponding data element identified by the name specified in the request.

31. The node of claim 26, wherein the means for establishing is configured for:

detecting a second connected user node reachable via the data link;

selectively sending to the second connected user node at least one of the unique object identifiers stored in the table based on a third query from the second connected user node,

selectively sending to the second connected user node a fourth query that specifies an attribute of a second data element determined to be absent from the user node, and

selectively storing in the table, in response to reception thereof from the second connected user node, any second received unique object identifiers that are distinct from the unique object identifiers and received unique object identifiers stored in the table, the unique object identifiers, said any received unique object identifiers, and said any second received unique object identifiers identifying the stored data elements having been recovered in the recovered data storage system, said second received unique object identifiers including the unique object identifier for the second data element determined to be absent from the user node.