System and method for efficiently replicating a file among a plurality of recipients having improved scalability

• US 20040143576A1
• Filed: 01/16/2003
• Published: 07/22/2004
• Est. Priority Date: 01/16/2003
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Co. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Co. (HP Inc.)
• Inventors: Cherkasova, Ludmila
• Granted Patent: US 7,200,598 B2
• Time in Patent Office: Days
• US Class Current: 707/10
• CPC Class Codes: G06F 16/10 File systems; File servers
• 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 distributed to the plurality of groups, wherein the distributing includes (a) partitioning the file into a plurality of subfiles, (b) distributing the plurality of subfiles from a first node to a first group, wherein at least one subfile is distributed from the first node to each recipient node of the first group but not all of the plurality of subfiles are distributed from the first node to any of the recipient nodes of the first group, and (c) the plurality of recipient nodes of the first group exchanging their respective subfiles such that each recipient node of the first group obtains all of the plurality of subfiles.

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; and

distributing said file F to the recipient nodes of said plurality of groups, wherein said distributing includes

(a) partitioning said file F into a plurality of subfiles,

(b) distributing the plurality of subfiles from a first node to a first group of recipient nodes, wherein at least one subfile is distributed from the first node to each recipient node of said first group but not all of said plurality of subfiles are distributed from the first node to any of the recipient nodes of said first group, and

(c) said plurality of recipient nodes of said first group exchanging their respective subfiles such that each recipient node of said first group obtains all of said plurality of subfiles.

2. The method of claim 1 wherein said logically organizing said plurality of recipient nodes into a plurality of groups of recipient nodes comprises:

determining a number of recipient nodes to include in each of said plurality of groups.

3. The method of claim 2 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

determining a number k of concurrent communication connections that can be supported by any one of the nodes for concurrent communication with a plurality of the other nodes.

4. The method of claim 3 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

determining the number of recipient nodes to include in each of said plurality of groups as a function of the determined number k.

5. The method of claim 3 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

determining a number m of groups each having k recipient nodes, wherein

$m=\frac{n}{k}$

with n being the total number of said plurality of recipient nodes to which said file F is to be distributed.

6. The method of claim 3 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

computing

$\frac{n}{k}$

 

where n is the total number of said plurality of recipient nodes to which said file F is to be distributed, wherein if

$\frac{n}{k}=m+r$

where r<

k then logically arranging said n recipient nodes into m groups each comprising k recipient nodes and one group comprising r nodes.

7. The method of claim 6 wherein for each of said m groups distributing said file F thereto as follows:

distributing the plurality of subfiles to the recipient nodes of the group, wherein at least one subfile is distributed to each recipient node of the group but not all of said plurality of subfiles are distributed to any of the recipient nodes of the group; and

said recipient nodes of the group exchanging their respective subfiles such that each recipient node of the group obtains all of said plurality of subfiles.

8. The method of claim 6 wherein for said group comprising r nodes distributing said file F thereto as follows:

communicating a subfile from each node of one of the m groups to every recipient node the group comprising r nodes such that said r recipient nodes each receive all of said plurality of subfiles.

9. The method of claim 3 wherein said partitioning said file F comprises:

partitioning said file F into k subfiles.

10. The method of claim 1 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing a different subfile to each of said recipient nodes of said first group.

11. The method of claim 1 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing the plurality of subfiles to said plurality of recipient nodes of said first group concurrently.

12. The method of claim 1 wherein said plurality of recipient nodes of said first group exchanging their respective subfiles further comprises:

each of said plurality of recipient nodes establishing concurrent communication connections to every other recipient node of said first group.

13. The method of claim 1 wherein said distributing said file F to said recipient nodes of a plurality of groups further comprises:

distributing the plurality of sub files from at least one node of said first group to the recipient nodes of a second group, wherein at least one subfile is distributed from the at least one node to each recipient node of said second group but not all of said plurality of subfiles are distributed from the at least one node to any of the recipient nodes of said second group; and

said recipient nodes of said second group exchanging their respective subfiles such that each recipient node of said second group obtains all of said plurality of subfiles.

14. The method of claim 13 wherein said distributing the plurality of subfiles from said at least one node of said first group to the recipient nodes of a second group comprises:

distributing the plurality of subfiles to said plurality of recipient nodes of said second group concurrently.

15. The method of claim 13 wherein said recipient nodes of said second group exchanging their respective subfiles further comprises:

each of said recipient nodes of said second group establishing concurrent communication connections to every other recipient node of said second group.

16. The method of claim 1 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing the plurality of subfiles via a communication network to which said first node and said plurality of recipient nodes of said first group are communicatively coupled.

17. The method of claim 16 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing the plurality of subfiles to said plurality of recipient nodes of said first group via concurrent communication connections of said first node to said communication network.

18. The method of claim 1 wherein said first node and said plurality of recipient nodes of said first group each comprise a server computer.

19. A system comprising:

means for logically organizing a plurality (n) 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 determining a number k of concurrent communication connections that can be supported by any one of the nodes for concurrent communication with a plurality of the other nodes;

means for distributing said file F to the recipient nodes; and

means for computing

$\frac{n}{k},$

 

wherein if

$\frac{n}{k}=m$

 

then

(a) said organizing means logically organizes said n recipient nodes into m groups each comprising k recipient nodes, and

(b) said means for distributing said file F comprises means to distribute said file F to each of said m groups as follows;

(i) distributing the plurality of subfiles to the recipient nodes of the group, wherein at least one subfile is distributed to each recipient node of the group but not all of said plurality of subfiles are distributed to any of the recipient nodes of the group, and

(ii) said recipient nodes of the group exchanging their respective subfiles such that each recipient node of the group obtains all of said plurality of subfiles.

20. The system of claim 19 wherein if

21. The system of claim 20 wherein for said group comprising r nodes, said means for distributing said file F to said plurality of recipient nodes comprises means for distributing said file F to said group comprising r nodes as follows:

communicating a subfile from each node of one of the m groups to every recipient node the group comprising r nodes such that said r recipient nodes each receive all of said plurality of sub files.

22. The system of claim 19 wherein said means for distributing said file F to each of said m groups comprises means for distributing a different one of said plurality of subfiles to each of the recipient nodes of a group.

23. The system of claim 19 wherein said means for distributing said file F to each of said m groups comprises means for communicating said plurality of subfiles to all of the recipient nodes of a group concurrently.

24. The system of claim 19 wherein said recipient nodes of the group exchanging their respective subfiles comprises said recipient nodes of the group exchanging their respective subfiles concurrently.

25. The system of claim 19 wherein said recipient nodes of the group exchanging their respective subfiles comprises a recipient node of the group communicating its respective subfile to all other recipient nodes of the group concurrently.

26. A system comprising:

an origin node comprising a file F;

a plurality of recipient nodes to which said file F is to be distributed, wherein the plurality of recipient nodes are logically organized into a plurality of groups, each group comprising a plurality of said recipient nodes;

said origin node operable to partition said file F into a plurality of subfiles, and said origin node operable to distribute all of said plurality of subfiles to recipient nodes of a first group, wherein at least one subfile is distributed from the origin node to each recipient node of said first group but not all of said plurality of subfiles are distributed from the origin node to any of the recipient nodes of said first group;

said recipient nodes of said first group operable 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;

at least one of said recipient nodes of said first group operable to distribute all of said plurality of subfiles to recipient nodes of a second group, wherein at least one subfile is distributed from the at least one node to each recipient node of said second group but not all of said plurality of subfiles are distributed from the at least one node to any of the recipient nodes of said second group; and

said recipient nodes of said second group operable to exchange their respective subfiles received from said at least one node such that each recipient node of said second group obtains all of said plurality of subfiles.

27. The system of claim 26 wherein said origin node is operable to distribute a different one of said plurality of subfiles to each of the recipient nodes of said first group.

28. The system of claim 27 wherein said origin node is operable to communicate said plurality of subfiles to all of the recipient nodes of said first group concurrently.

29. The system of claim 28 wherein each of said recipient nodes of said first group is operable to communicate its respective subfile received from said origin node to all other recipient nodes of the first group concurrently.

30. 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;

distributing said file F to the recipient nodes of said plurality of groups, wherein said distributing includes

(a) partitioning said file F into a plurality of subfiles,

(b) distributing the plurality of subfiles from a first node to a first group of recipient nodes, wherein at least one subfile is distributed from the first node to each recipient node of said first group but not all of said plurality of subfiles are distributed from the first node to any of the recipient nodes of said first group,

(c) said plurality of recipient nodes of said first group exchanging their respective subfiles such that each recipient node of said first group obtains all of said plurality of sub files, and

(d) distributing said file F from said first group to at least one other group of recipient nodes.

31. The method of claim 30 wherein said logically organizing said plurality of recipient nodes into a plurality of groups of recipient nodes comprises:

determining a number of recipient nodes to include in each of said plurality of groups.

32. The method of claim 31 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

determining a number k of concurrent communication connections that can be supported by any one of the nodes for concurrent communication with a plurality of the other nodes.

33. The method of claim 32 wherein said determining a number of recipient nodes to include in each of said plurality of groups comprises:

determining the number of recipient nodes to include in each of said plurality of groups as a function of the determined number k.

34. The method of claim 32 wherein said partitioning said file F comprises:

partitioning said file F into k subfiles.

35. The method of claim 30 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing a different subfile to each of said recipient nodes of said first group.

36. The method of claim 35 wherein said distributing the plurality of subfiles from said first node to said first group of recipient nodes comprises:

distributing the plurality of subfiles to said plurality of recipient nodes of said first group concurrently.

37. The method of claim 30 wherein said plurality of recipient nodes of said first group exchanging their respective subfiles further comprises:

each of said plurality of recipient nodes establishing concurrent communication connections to every other recipient node of said first group.

38. The method of claim 30 wherein said distributing said file F from said first group to at least one other group of recipient nodes comprises:

distributing the plurality of subfiles from a first node of said first group to a second group of recipient nodes, wherein at least one subfile is distributed from the first node of said first group to each recipient node of said second group but not all of said plurality of subfiles are distributed from the first node of said first group to any of the recipient nodes of said second group; and

said plurality of recipient nodes of said second group exchanging their respective subfiles such that each recipient node of said second group obtains all of said plurality of subfiles.

39. The method of claim 38 wherein said distributing the plurality of subfiles from said at least one node of said first group to the recipient nodes of said second group comprises:

distributing the plurality of subfiles to said plurality of recipient nodes of said second group concurrently.

40. The method of claim 38 wherein said recipient nodes of said second group exchanging their respective subfiles further comprises:

each of said recipient nodes of said second group establishing concurrent communication connections to every other recipient node of said second group.