System and method for efficiently replicating a file

• US 7,454,424 B2
• Filed: 01/16/2003
• Issued: 11/18/2008
• Est. Priority Date: 01/16/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Cherkasova, Ludmila
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Merilyn P
• Application Number:
  US10/345,719
• Publication Number:
  US 20040143595A1
• Time in Patent Office: 2,133 Days
• Field of Search: 707/10, 707/101, 707/104.1, 707/204, 709/222, 709/226, 709/235, 709/219, 709/236, 711/173
• US Class Current: 1/1
• 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/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method of distributing a file from a first node to a plurality of recipient nodes comprises logically organizing a plurality of recipient nodes to which a file is to be distributed into a plurality of groups of recipient nodes. The file is partitioned into a plurality of subfiles. The file is distributed to a plurality of recipient nodes using a distribution technique comprising (a) an origin node attempting to communicate the plurality of subfiles to recipient nodes of the first group, (b) the plurality of recipient nodes of the first group attempting to exchange their respective subfiles received from the origin node, and (c) attempting to distribute the plurality of subfiles from at least one node of the first group to recipient nodes of a second group. The method further comprises detecting a failed node, and the distribution technique adapting to distribute the file to each non-failed node.

Claims

1. A method of distributing a file F from a first node to a plurality of recipient nodes, the method comprising:

logically organizing a plurality of recipient nodes to which a file F is to be distributed into a plurality of groups of recipient nodes, wherein each group comprises a plurality of said recipient nodes;

partitioning said file F into a plurality of subfiles;

performing distribution of said file F to said plurality of groups of recipient nodes using a distribution technique that comprises

(a) an origin node attempting to establish concurrent communication connections with recipient nodes of a first group and communicate the plurality of subfiles to the recipient nodes of the first group, wherein the origin node attempts to communicate at least one subfile to each recipient node of said first group but not all of said plurality of subfiles to any recipient node of said first group,

(b) said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node, and

(c) attempting to distribute the plurality of subfiles from at least one node of said first group to recipient nodes of a second group;

detecting a failed node; and

said distribution technique adapting to distribute said file F to each non-failed node of said plurality of recipient nodes to which said file F is to be distributed.

2. The method of claim 1 wherein said distribution technique adapting responsive to said detecting a failed node.

3. The method of claim 1 wherein said detecting a failed node comprises said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node.

4. The method of claim 2 wherein said distribution technique adapting comprises:

responsive to said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, said origin node using its established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes.

5. The method of claim 1 wherein said origin node attempting to establish concurrent communication connections with each node of a first group and communicate the plurality of subfiles to the recipient nodes of the first group comprises:

said origin node attempting to communicate a different one of said plurality of subfiles to each of said recipient nodes of said first group.

6. The method of claim 5 wherein said detecting a failed node comprises said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, and wherein said distribution technique adapting comprises:

responsive to said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, said origin node using its established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes.

7. The method of claim 5 wherein said detecting a failed node comprises said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group, and wherein said distribution technique adapting comprises:

responsive to said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group, said origin node establishing concurrent communication connections with non-failed nodes of said first group that have not received the particular subfile from said failed node, and said origin node communicating the particular subfile to said non-failed nodes.

8. The method of claim 1 wherein said detecting a failed node comprises said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group.

9. The method of claim 8 wherein said distribution technique adapting comprises:

responsive to said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular sub file to every other recipient node of said first group, said origin node establishing concurrent communication connections with non-failed nodes of said first group that have not received the particular subfile from said failed node, and said origin node communicating the particular subfile to said non-failed nodes.

10. The method of claim 8 wherein said detecting a failed node comprises:

said recipient nodes of said first group communicating heartbeat messages to said origin node; and

said origin node detecting a failed node from analysis of heartbeat messages received from said first group.

11. The method of claim 10 wherein said origin node detecting a failed node from analysis of heartbeat messages received from said first group comprises:

said origin node identifying a recipient node of said first group from which a heartbeat message was not received by said origin node.

12. The method of claim 1 wherein said detecting a failed node comprises said origin node detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group.

13. The method of claim 12 wherein said distribution technique adapting comprises:

responsive to said origin node detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group, said origin node establishing concurrent communication connections with recipient nodes of said second group, and said origin node communicating the plurality of subfiles to said nodes of said second group.

14. The method of claim 1 wherein said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node further comprises:

said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node such that each recipient node of said first group obtains all of said plurality of subfiles.

15. The method of claim 1 wherein said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node further comprises:

each recipient node of said first group attempting to communicate the subfile that it received from said origin node to every other recipient node of the first group.

16. A system comprising:

means for logically organizing a plurality of recipient nodes to which a file F is to be distributed into a plurality of groups of recipient nodes, wherein each group comprises a plurality of said recipient nodes;

means for partitioning said file F into a plurality of subfiles;

means for performing distribution of said file F to said plurality of groups of recipient nodes using a distribution technique that comprises

(a) an origin node attempting to establish concurrent communication connections with recipient nodes of a first group and communicate the plurality of subfiles to the recipient nodes of the first group, wherein the origin node attempts to communicate at least one subfile to each recipient node of said first group but not all of said plurality of subfiles to any recipient node of said first group,

(b) said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node, and

(c) attempting to distribute the plurality of subfiles from at least one node of said first group to recipient nodes of a second group;

means for detecting a failed node; and

said distribution technique adapting, responsive to said detecting means detecting a failed node, to distribute said file F to each non-failed node of said plurality of recipient nodes to which said file F is to be distributed.

17. The system of claim 16 wherein said detecting means comprises:

means for said origin node detecting a failed node in said first group.

18. The system of claim 17 wherein said means for said origin node detecting a failed node in said first group comprises:

means for said origin node detecting that said origin node is unable to communicate a particular subfile to a node of said first group.

19. The system of claim 17 wherein said distribution technique adapting comprises:

responsive to said detecting means detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, said origin node using its established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes.

20. The system of claim 16 wherein said detecting means comprises means for said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group.

21. The system of claim 20 wherein said distribution technique adapting comprises:

responsive to said detecting means detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group, said origin node establishing concurrent communication connections with non-failed nodes of said first group that have not received the particular subfile from said failed node, and said origin node communicating the particular subfile to said non-failed nodes.

22. The system of claim 20 wherein said means for said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group comprises:

each of said recipient nodes of said first group comprising means for communicating heartbeat messages to said origin node; and

said origin node comprising means for analyzing heartbeat messages received from said first group to detect a failed node in said first group.

23. The system of claim 16 wherein said detecting means comprises means for said origin node detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group.

24. The system of claim 23 wherein said distribution technique adapting comprises:

responsive to said detecting means detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group, said origin node establishing concurrent communication connections with recipient nodes of said second group, and said origin node communicating the plurality of subfiles to said nodes of said second group.

25. The system of claim 23 wherein said means for said origin node detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group comprises:

said at least one node of said first group comprising means for communicating Heartbeat messages to said origin node; and

said origin node comprising means for analyzing heartbeat messages received from said at least one node of said first group.

26. A system comprising:

an origin node that comprises a file F;

a plurality of recipient nodes to which said file F is to be distributed;

said origin node operable to logically organize said plurality of recipient nodes into a plurality of groups of recipient nodes, wherein each group comprises a plurality of said recipient nodes;

said origin node operable to partition said file F into a plurality of subfiles;

said origin node operable to attempt to establish concurrent communication connections with recipient nodes of a first group and communicate the plurality of subfiles to the recipient nodes of the first group, wherein the origin node attempts to communicate at least one subfile to each recipient node of said first group but not all of said plurality of subfiles to any recipient node of said first group;

said plurality of recipient nodes of said first group operable to attempt to exchange their respective subfiles received from said origin node;

at least one node of said first group operable to act as an origin node to attempt to distribute the plurality of subfiles to recipient nodes of a second group;

said origin node operable to detect a failed node in said first group; and

said origin node operable to manage distribution of said file F upon detecting a failed node in said first group in a manner such that every non-failed node of said first group receives said file F.

27. The system of claim 26 wherein said origin node is operable to detect a failed node in said first group by detecting that said origin node is unable to communicate a particular subfile to such failed node of said first group.

28. The system of claim 26 further comprising:

said origin node operable, responsive to said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, to use its established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes.

29. The system of claim 26 wherein said origin node is operable to attempt to communicate a different one of said plurality of subfiles to each recipient node of the first group.

30. The system of claim 29 further comprising:

said origin node operable, responsive to said origin node detecting a failed node in said first group such that said origin node is unable to communicate a particular subfile to such failed node, to use its established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes.

31. The system of claim 26 further comprising:

said origin node operable, responsive to said origin node detecting a failed node in said first group after said origin node has communicated a particular subfile to such failed node but before such failed node has communicated said particular subfile to every other recipient node of said first group, to establish concurrent communication connections with non-failed nodes of said first group that have not received the particular subfile from said failed node and communicate the particular subfile to said non-failed nodes.

32. The system of claim 31 wherein each of said recipient nodes of said first group is operable to communicate heartbeat messages to said origin node, and said origin node is operable to analyze heartbeat messages received from said first group to detect a failed node in said first group.

33. The system of claim 26 further comprising:

said origin node operable, responsive to said origin node detecting said at least one node of said first group as failed when said at least one node is attempting to distribute the plurality of subfiles to recipient nodes of a second group, to establish concurrent communication connections with recipient nodes of said second group and communicate the plurality of subfiles to said nodes of said second group.

34. A method of distributing a file F from a first node to a plurality of recipient nodes, the method comprising:

logically organizing a plurality of recipient nodes to which a file F is to be distributed into a plurality of groups of recipient nodes, wherein each group comprises a plurality of said recipient nodes;

partitioning said file F into a plurality of subfiles;

an origin node attempting to establish concurrent communication connections with recipient nodes of a first group and communicate the plurality of subfiles to the recipient nodes of the first group, wherein the origin node attempts to communicate at least one subfile to each recipient node of said first group but not all of said plurality of subfiles to any recipient node of said first group;

wherein if said origin node detects a failed node in said first group such that it is unable to communicate a particular subfile to such failed node, then said origin node using the established concurrent communication connections with non-failed nodes of said first group to communicate the particular subfile to said non-failed nodes;

said plurality of recipient nodes of said first group attempting to exchange their respective subfiles received from said origin node;

wherein if a node in said first group is detected as failed before communicating its respective subfile received from said origin node to all of the other nodes of said first group, then said origin node establishing concurrent communication connections with the non-failed nodes of said first group and communicating the respective subfile of the failed node to each of the non-failed nodes of the first group;

attempting to distribute the plurality of subfiles from at least one node of said first group to recipient nodes of a second group;

wherein if said origin node detects said at least one node as failed when attempting to distribute the plurality of subfiles to said recipient nodes of said second group, then said origin node establishing concurrent communication connections with the nodes of said second group and communicating the plurality of subfiles to each of the nodes of said second group.