Peer-to-peer method and system for performing and managing backups in a network of nodes

• US 20040153458A1
• Filed: 10/30/2003
• Published: 08/05/2004
• Est. Priority Date: 11/08/2002
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: Cox, Landon P., Noble, Brian D.
• Granted Patent: US 7,424,514 B2
• Time in Patent Office: Days
• US Class Current: 707/10
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A peer-to-peer method and system for performing and managing backups in a network of nodes exploit excess disk capacity to perform peer-to-peer backup with no administrative costs. Each node minimizes storage overhead by selecting peer nodes that share substantial amounts of data. Common installations find suitable peer nodes and peer nodes with high overlap are identified. The method and system also provide mechanisms for confidentiality, integrity, and detection of failed or malicious peer nodes.

Claims

1. A peer-to-peer method for performing and managing backups in a network of nodes which form a cooperative collection of machines having excess storage capacity, the method comprising:

(a) determining a plurality of peer nodes from the network of nodes for a first node of the network based on an amount of stored data common to both the first node and each of the plurality of peer nodes; and

(b) storing a backup copy of data unique to the first node on each of the plurality of peer nodes so that each of the plurality of peer nodes stores a substantially complete backup of the first node.

2. The method as claimed in claim 1, further comprising repeating steps (a) and (b) for each of the other nodes of the network so that a plurality of substantially complete backups are stored on a plurality of peer nodes for each of the nodes of the network.

3. The method as claimed in claim 1, wherein the step of determining is also based on network distance that each of the plurality of peer nodes is from the first node.

4. The method as claimed in claim 1, wherein at least one of the plurality of peer nodes is the local peer node to reduce network load and improve restore performance.

5. The method as claimed in claim 1, wherein at least one of the plurality of peer nodes is a remote peer node to provide geographic diversity.

6. The method as claimed in claim 1, wherein data is stored in the first and peer nodes as chunks of data.

7. The method as claimed in claim 1, further comprising monitoring the plurality of peer nodes to determine if a peer node is no longer capable of providing a backup to the first node and repeating steps (a) and (b) to determine a replacement peer node from the network of nodes and to store a backup copy of data unique to the first node on the replacement peer node.

8. The method as claimed in claim 7, wherein the step of monitoring is performed statistically.

9. The method as claimed in claim 1, further comprising preventing a forged request to drop a backup copy from one of the peer nodes.

10. The method as claimed in claim 6, wherein the data is stored in the peer nodes as encrypted chunks.

11. The method as claimed in claim 10, wherein the data is encrypted by a key derived from the data stored in the peer nodes.

12. The method as claimed in claim 11, wherein the key is encrypted.

13. The method as claimed in claim 12, wherein the key is encrypted by a key-encrypting key stored with the data.

14. The method as claimed in claim 2, wherein data is stored in the peer nodes as chunks of encrypted data and wherein each of the encrypted chunks includes data which represents a set of nodes having an interest in the encrypted chunk.

15. The method as claimed in claim 1, further comprising determining when the first node is decommissioned and reclaiming storage space on the peer nodes associated with the decommissioned node.

16. The method as claimed in claim 1, further comprising determining whether a node of the network claiming to be a peer node is a peer node.

17. A peer-to-peer system for performing and managing backups in a network of nodes which form a cooperative collection of machines having excess storage capacity, the system comprising:

means for determining a plurality of peer nodes from the network of nodes for a first node of the network based on an amount of stored data common to both the first node and each of the plurality of peer nodes; and

means for storing a backup copy of data unique to the first node on each of the plurality of peer nodes so that each of the plurality of peer nodes stores a substantially complete backup of the first node.

18. The system as claimed in claim 17, wherein the means for determining determines a plurality of peer nodes from the network for each of the nodes of the network and wherein the means for storing stores a backup copy of data unique to each of the nodes of the network on each of its plurality of peer nodes so that a plurality of substantially complete backups are stored on a plurality of peer nodes for each of the nodes of the network.

19. The system as claimed in claim 17, wherein the means for determining determines the plurality of peer nodes based on network distance that each of the plurality of peer nodes is from the first node.

20. The system as claimed in claim 17, wherein at least one of the plurality of peer nodes is the local peer node to reduce network load and improve restore performance.

21. The system as claimed in claim 17, wherein at least one of the plurality of peer nodes is a remote peer node to provide geographic diversity.

22. The system as claimed in claim 17, wherein data is stored in the first and peer nodes as chunks of data.

23. The method as claimed in claim 17, further comprising means for monitoring the plurality of peer nodes to determine if a peer node is no longer capable of providing a backup to the first node, wherein the means for determining determines a replacement peer node from the network of nodes and wherein the means for storing stores a backup copy of data unique to the first node on the replacement peer node.

24. The system as claimed in claim 23, wherein the means for monitoring monitors the plurality of peer nodes statistically.

25. The system as claimed in claim 17, further comprising means for preventing a forged request to drop a backup copy from one of the peer nodes.

26. The system as claimed in claim 22, wherein the data is stored in the peer nodes as encrypted chunks.

27. The system as claimed in claim 26, wherein the data is encrypted by a key derived from the data stored in the peer nodes.

28. The system as claimed in claim 27, wherein the key is encrypted.

29. The system as claimed in claim 28, wherein the key is encrypted by a key-encrypting key stored with the data.

30. The system as claimed in claim 18, wherein data is stored in the peer nodes as chunks of encrypted data and wherein each of the encrypted chunks includes data which represents a set of nodes having an interest in the encrypted chunk.

31. The system as claimed in claim 17, further comprising means for determining when the first node is decommissioned and means for reclaiming storage space on the peer nodes associated with the decommissioned node.

32. The system as claimed in claim 17, further comprising means for determining whether a node of the network claiming to be a peer node is a peer node.