Reliably storing information across multiple computers such as in a hive of computers

• US 20070011302A1
• Filed: 09/30/2005
• Published: 01/11/2007
• Est. Priority Date: 09/07/2002
• Status: Active Grant

• Current Assignee: Appistry Incorporated
• Original Assignee: Appistry Incorporated
• Inventors: Lozano, Roberto, Groner, Michael
• Granted Patent: US 7,363,346 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• 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: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• 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 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

Disclosed are mechanisms for reliably storing information across multiple computers networked together, where each of these computers may or may not be a hive node of a hive. This information includes multiple information units. At least one protection unit is generated based on the information units such that the information can be recreated using less than all of these information units and at least one protection unit. A data unit is defined as one or more information units, one or more protection units, or a combination of information and protection units, with each information unit being included in at least one of the data units and each protection unit being included in at least one of the data units. A operation is initiated to store on each of the computers at least one data unit, such that each data unit is stored in at least one of the computers.

Claims

1. A method for reliably storing information across a plurality of computers networked together, each of the plurality of computers including a storage mechanism, said information including a plurality of information units, the method comprising:

generating at least one protection unit based on the plurality of information units such that said information can be recreated using less than all of said information units and at least one of said at least one protection unit, wherein a data unit of a plurality of data units is defined as one or more information units of the plurality of information units, one or more protection units of said at least one protection unit, or a combination of one or more information units of the plurality of information units and one or more protection units of said at least one protection unit; and

wherein each of said information units are included in at least one of the plurality of data units and each of said at least one protection unit are included in at least one of the plurality of data units; and

initiating storage on each of the plurality of computers of at least one data unit of the plurality of data units such that each data unit in the plurality of data units is stored in at least one of the plurality of computers.

2. The method of claim 1, wherein said information includes a computer file, and each of the plurality of information units include an approximate same sized portion of the computer file.

3. The method of claim 1, wherein said information includes a plurality of computer files, and each of the plurality of information units includes a different one of the plurality of computer files.

4. The method of claim 1, comprising:

retrieving less than all of the data units in the plurality of data units from computers of the plurality of computers, wherein said retrieved less than all data units include at least one of said at least one protection unit; and

recreating said information from said retrieved less than all of the data units.

5. The method of claim 4, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein a minimum of k of the plurality of data units are required to recreate said information.

6. The method of claim 5, wherein n is three and k is two, and each of said k data units consists of one of said information units or one of said at least one protection unit.

7. The method of claim 5, wherein n is four and k is two, and each of said k data units consists of one of said information units and one of said at least one protection unit.

8. The method of claim 4, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein said retrieved less than all data units consists of more than k data units.

9. The method of claim 1, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein a minimum of k of the plurality of data units are required to recreate said information; and

wherein said method includes selecting the plurality of computers based on their respective locations such that k computers are located on each of at least two physically different subnetworks.

10. The method of claim 9, comprising:

retrieving k data units from computers of the plurality of computers, wherein said retrieved k data units include at least one of said at least one protection unit; and

recreating said information from said retrieved less than all of the data units.

11. The method of claim 1, wherein each of the plurality of computers is a hive node.

12. The method of claim 11, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein a minimum of k of the plurality of data units are required to recreate said information; and

wherein said method includes selecting the plurality of computers based on their respective locations such that k computers are located on each of at least two different hive territories.

13. The method of claim 12, comprising:

retrieving k data units from computers of the plurality of computers, wherein said retrieved k data units include at least one of said at least one protection unit; and

recreating said information from said retrieved less than all of the data units.

14. The method of claim 1, wherein the plurality of computers includes at least three computers.

15. The method of claim 1, wherein the plurality of computers includes at least four computers.

16. The method of claim 1, wherein the plurality of computers includes a first computer and a second computer;

and the method includes the first computer updating said information, and subsequently, the second computer updating said information, wherein said updating said information includes said generating operation and said initiating storage on each of the plurality of computers operation.

17. The method of claim 1, wherein said generating and said initiating storage are performed by a particular computer of the plurality of computers;

and wherein the method includes;

the particular computer receiving an instruction to store said information from a different device, said instruction including said information and an identifier for use in storing said information.

18. The method of claim 1, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein a minimum of k of the plurality of data units are required to recreate said information;

wherein said generating and said initiating storage are performed by a particular computer of the plurality of computers; and

wherein the method includes the particular computer receiving an instruction to store said information from a different device, the instruction including said information and a value of k to use in said generating operation.

19. The method of claim 18, wherein the instruction also defines the value of n.

20. A method for use with a hive distributed storage system for storing information among a plurality of hive nodes in a reliability group of a hive, each of the plurality of hive nodes including a storage mechanism, said information including a plurality of information units, the method comprising:

generating at least one protection unit based on the plurality of information units such that said information can be recreated using less than all of said information units and at least one of said at least one protection unit, wherein a data unit of a plurality of data units is defined as one or more information units of the plurality of information units, one or more protection units of said at least one protection unit, or a combination of one or more information units of the plurality of information units and one or more protection units of said at least one protection unit; and

wherein each of said information units are included in at least one of the plurality of data units and each of said at least one protection unit are included in at least one of the plurality of data units; and

storing on each of said hive nodes at least one data unit of the plurality of data units such that each data unit in the plurality of data units is stored in at least one of said hive nodes.

21. The method of claim 20, wherein said information includes a computer file, and each of the plurality of information units include an approximate same sized portion of the computer file.

22. The method of claim 20, wherein said information includes a plurality of computer files, and each of the plurality of information units includes a different one of the plurality of computer files.

23. The method of claim 20, wherein each of said hive nodes of the reliability group includes a mechanism for replacing a failed hive node of said hive nodes of the reliability group.

24. The method of claim 23, comprising a particular hive node of said hive nodes recognizing that the failed hive node has failed, and in response, said particular hive node initiating replacement of said failed hive node in the reliability group with a replacement hive node;

wherein said replacement of said failed hive node includes recreating and storing on the replacement hive node said at least one data unit stored on said failed hive node.

25. The method of claim 24, wherein said replacement of said failed hive node includes sending a multicast hive volunteer request message and receiving one or more responses, and selecting the replacement hive node from said one or more responses.

26. The method of claim 23, comprising a first particular hive node and a second particular hive node of said hive nodes each recognizing that the failed hive node has failed, and in response, the first particular hive node identifying that it should replace said failed node and the second particular hive node identifying that it not should replace said failed node, said first particular hive node initiating replacement of said failed hive node in the reliability group with a replacement hive node;

wherein said replacement of said failed hive node includes recreating and storing on the replacement hive node said at least one data unit stored on said failed hive node.

27. The method of claim 26, wherein said identification by the first particular hive node that it should replace said failed node includes the first particular hive node identifying that it is in communication with a quorum of the plurality of nodes.

28. The method of claim 27, wherein said identification by the second particular hive node that it should not replace said failed node includes the second particular hive node identifying that it is not in communication with a quorum of the plurality of nodes.

29. The method of claim 20, comprising creating the reliability group, said creating the reliability group including requesting hive volunteers and receiving responses, and selecting the plurality of hive nodes from said responses.

30. The method of claim 29, wherein said responses include responses from hive nodes other than the plurality of hive nodes.

31. The method of claim 29, wherein said requesting hive volunteers includes sending a multicast hive volunteer request message.

32. The method of claim 29, wherein said selecting the plurality of hive nodes from responses includes intelligently selecting the plurality of hive nodes to diversify the hive node composition of the reliability group in comparison with the composition of one or more other reliability groups;

wherein said intelligently selecting includes referencing a data structure identifying membership information of other reliability groups.

33. The method of claim 20, comprising:

retrieving less than all of the data units in the plurality of data units from said hive nodes, wherein said retrieved less than all data units include at least one of said at least one protection unit; and

recreating and said information from said retrieved less than all of the data units.

34. The method of claim 33, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein said retrieved less than all data units consists of k data units.

35. The method of claim 20, including receiving a meta file defining said information and an identifier for said information.

36. The method of claim 20, wherein said generating operation is performed by a particular hive node of the reliability group;

and wherein the method includes;

the particular hive node receiving an instruction to store said information from a remote device, said instruction including said information and an identifier for use in storing said information.

37. The method of claim 20, wherein said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein said less than all data units consists of k data units;

wherein said generating operation is performed by a particular hive node of the reliability group; and

wherein the method includes;

the particular hive node receiving an instruction to store said information, the instruction including said information and a value of k to use in said generating operation.

38. The method of claim 20, including:

a requesting hive node multicasting a request to identify one of said hive nodes in the reliability group;

the requesting hive node receiving a response to the request from a particular hive node of said hive nodes in the reliability group;

the requesting hive node requesting said information from the particular hive node; and

the particular hive node sending the information to the requesting hive node.

39. The method of claim 38, including:

the particular hive node requesting said data units from other hive nodes of the reliability group, and in response, the particular hive node receiving at least k information units and recreating said information using at least k information units of said received at least k information units.

40. A method for reliably storing information across different groups of computers, each of said different groups including a plurality of computers networked together, each of said computers including a storage mechanism, the method comprising:

reliability storing first information across a first group of said different groups of computers; and

reliability storing second information across a second group of said different groups of computers, wherein the first group of computers includes at least one computer different that the second groups of computers;

wherein said reliably storing said respective information, with said respective information including a plurality of information units, includes;

generating at least one protection unit based on the plurality of information units such that said respective information can be recreated using less than all of said information units and at least one of said at least one protection unit, wherein a data unit of a plurality of data units is defined as one or more information units of the plurality of information units, one or more protection units of said at least one protection unit, or a combination of one or more information units of the plurality of information units and one or more protection units of said at least one protection unit; and

wherein each of said information units are included in at least one of the plurality of data units and each of said at least one protection unit are included in at least one of the plurality of data units; and

initiating storage on each of the plurality of computers of said respective group of computers of at least one data unit of the plurality of data units such that each data unit in the plurality of data units is stored in at least one of the plurality of computers of said respective group of computers.

41. The method of claim 40, wherein the first and second groups of computers each consist of a different number of computers, and said generating at least one protection unit includes using an (n, k) threshold scheme, wherein the plurality of data units consists of n data units;

and wherein a minimum of k of the plurality of data units are required to recreate said information; and

wherein said k used for storing said first information across the first group of computers is different than k used for storing said second information across the second group of computers.

42. The method of claim 40, wherein each of the plurality of computers of the first and second groups is a hive node.

43. A method for use with a hive distributed storage system for storing information units among a plurality of hive nodes in a reliability group of a hive, each of the plurality of hive nodes including a storage mechanism, said information including an information unit, the method comprising:

generating one protection unit based on the information unit such that said information can be recreated from the information unit or the protection unit, wherein a data unit of a plurality of data units is defined as the information unit or the protection unit; and

wherein the information unit is included in one of the plurality of data units and the protection unit is included in one of the plurality of data units; and

storing on each of said hive nodes at least one data unit of the plurality of data units such that each data unit in the plurality of data units is stored in at least one of said hive nodes.

44. The method of claim 43, wherein each of said hive nodes of the reliability group includes a mechanism for replacing a failed hive node of said hive nodes of the reliability group.

45. The method of claim 44, comprising one of said hive nodes recognizing that the failed hive node has failed, and in response, said hive node initiating replacement of said failed hive node in the reliability group with a replacement hive node;

wherein said replacement of said failed hive node includes recreating and storing on the replacement hive node said at least one data unit stored on said failed hive node.

46. The method of claim 44, comprising a first particular hive node and a second particular hive node of said hive nodes each recognizing that the failed hive node has failed, and in response, the first particular hive node identifying that it should replace said failed node and the second particular hive node identifying that it not should replace said failed node, said first particular hive node initiating replacement of said failed hive node in the reliability group with a replacement hive node;

wherein said replacement of said failed hive node includes recreating and storing on the replacement hive node said at least one data unit stored on said failed hive node.

47. The method of claim 46, wherein said identification by the first particular hive node that it should replace said failed node includes the first particular hive node identifying that it is in communication with a quorum of the plurality of nodes.

48. The method of claim 47, wherein said identification by the second particular hive node that it should not replace said failed node includes the second particular hive node identifying that it is not in communication with a quorum of the plurality of nodes.

49. The method of claim 43, comprising creating the reliability group, said creating the reliability group including requesting hive volunteers and receiving responses, and selecting the plurality of hive nodes from said responses.

50. The method of claim 43, including:

a requesting hive node multicasting a request to identify one of said hive nodes in the reliability group;

the requesting hive node receiving a response to the request from a particular hive node of said hive nodes in the reliability group;

the requesting hive node requesting said information from the particular hive node; and

the particular hive node sending the information to the requesting hive node.