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

• US 7,363,346 B2
• Filed: 09/30/2005
• Issued: 04/22/2008
• Est. Priority Date: 09/07/2002
• Status: Expired due to Fees

• Current Assignee: Appistry Incorporated
• Original Assignee: Appistry Incorporated
• Inventors: Groner, Michael Scott, Lozano, Roberto Raul
• Primary Examiner(s): Vu; Viet D.
• Application Number:
  US11/241,152
• Publication Number:
  US 20070011302A1
• Time in Patent Office: 935 Days
• Field of Search: 709/213, 709/214, 709/215, 709/217, 709/223, 709/225, 709/226, 713/193, 714/6
• US Class Current: 709/214
• 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;

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.

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;

and the method includes identifying the plurality of computers using a volunteer procedure including;

requesting hive volunteers, receiving responses to said request from each of the plurality of computers plus one or more additional hive nodes, and selecting the plurality of computers from said received responses.

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

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

47. The method of claim 1, wherein a hive includes each of the plurality of computers, with the hive including a plurality of territories, with each of the plurality of computers belonging to one of the plurality of territories;

and wherein the instruction includes an indication of the reliability level determining whether to store the plurality of data units across multiple different territories of the plurality of territories; and

wherein the particular computer is responsive to said indication of reliability in determining on which of the plurality of computers to store data units of the plurality of data units.

19. 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:

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;

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.

20. The method of claim 19, 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.

21. The method of claim 19, 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.

22. The method of claim 19, 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.

23. The method of claim 22, 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.

24. The method of claim 23, 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.

25. The method of claim 22, 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.

26. The method of claim 25, 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.

27. The method of claim 26, 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.

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

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

30. The method of claim 19, 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.

31. The method of claim 19, 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.

32. The method of claim 31, 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.

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

34. The method of claim 19, 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.

35. The method of claim 19, 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.

36. The method of claim 19, 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.

37. The method of claim 36, 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.

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

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.

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

48. The method of claim 38, wherein said generating and said initiating storage for storing the first information is performed by a first particular computer of the first group, and said generating and said initiating storage for storing the second information is performed by a second particular computer of the second group;

and

wherein the method includes;

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

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

40. 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:

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;

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.

41. The method of claim 40, 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.

42. The method of claim 41, 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.

43. The method of claim 41, 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.

44. The method of claim 43, 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.

45. The method of claim 44, 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.

46. The method of claim 40, 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.