Adaptive liveness management for robust and efficient peer-to-peer storage

• US 7,886,034 B1
• Filed: 09/27/2006
• Issued: 02/08/2011
• Est. Priority Date: 09/27/2006
• Status: Expired due to Fees

• Current Assignee: NortonLifeLock Inc.
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Kritov, Slava, Hartmann, Alfred, Witten, Brian
• Primary Examiner(s): Nguyen; Dustin
• Application Number:
  US11/535,939
• Time in Patent Office: 1,595 Days
• Field of Search: 709/203, 709/213, 709/232, 707/200, 375/240.24, 370/352, 711/118
• US Class Current: 709/223
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network

Abstract

A peer-to-peer storage manager measures availability (liveness) of the various nodes in a peer-to-peer storage pool, and adjusts the storage of data within the pool to meet performance expectations based on this liveness information. Based on node liveness statistics, the peer-to-peer storage manager fine tunes storage up or down to efficiently allocate storage while maintaining service level objectives for retrieval time probabilities. Responsive to node liveness information, the peer-to-peer storage manager can dynamically adjust redundancy and/or determine which nodes on which to store data. The peer-to-peer storage manager can execute these storage modifications using rateless erasure codes that allow highly robust storage with only weakly synchronized directory update protocols.

Claims

1. A computer implemented method for robustly managing peer-to-peer storage, the method comprising the steps of:

storing an item in a peer-to-peer storage pool as data blocks, at least some of the data blocks being redundant, the redundant data blocks being stored on different nodes of the peer-to-peer storage pool;

tracking liveness of nodes in the peer-to-peer storage pool to determine a retrieval probability of the item as a whole; and

modifying storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information comprising changing a number of redundant data blocks to adjust the retrieval probability in accordance with a predetermined threshold.

2. The method of claim 1 wherein tracking liveness of nodes in the peer-to-peer storage pool further comprises:

transmitting a request to at least one node in the peer-to-peer storage pool; and

receiving a response from the at least one node.

3. The method of claim 1 wherein adjusting redundancy of storage of blocks of data in the peer-to-peer storage pool further comprises:

using a rateless code to adjust redundancy of storage of blocks of data in the peer-to-peer storage pool; and

permitting asynchronous updating of distributed hash table directory information in the peer-to-peer storage pool, to reflect the adjusted redundancy.

4. The method of claim 3 further comprising:

subsequently synchronizing the distributed hash table directory information.

5. The method of claim 1 wherein modifying storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information further comprises:

moving stored blocks of data to nodes with different liveness profiles in the peer-to-peer storage pool, responsive to tracked liveness information.

6. The method of claim 5 wherein moving stored blocks of data to nodes with different liveness profiles in the peer-to-peer storage pool further comprises:

using a rateless code to store blocks of data on new nodes with different liveness profiles from the old nodes on which the blocks where originally stored;

adding the new nodes as additional block holders in a distributed hash table;

removing directory entries in the distributed hash table concerning storage of the blocks on the old nodes; and

deleting the blocks from the old nodes.

7. At least one non-transitory computer readable medium containing a computer program product for robustly managing peer-to-peer storage, the computer program product comprising:

program code for storing an item in a peer-to-peer storage pool as data blocks, at least some of the data blocks being redundant, the redundant data blocks being stored on different nodes of the peer-to-peer storage pool;

program code for tracking liveness of nodes in the peer-to-peer storage pool to determine a retrieval probability of the item as a whole; and

program code for modifying storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information comprising changing a number of redundant data blocks to adjust the retrieval probability in accordance with a predetermined threshold.

8. The computer program product of claim 7 wherein the program code for tracking liveness of nodes in the peer-to-peer storage pool further comprises:

program code for transmitting a request to at least one node in the peer-to-peer storage pool; and

program code for receiving a response from the at least one node.

9. The computer program product of claim 7 wherein the program code for adjusting redundancy of storage of blocks of data in the peer-to-peer storage pool further comprises:

program code for using a rateless code to adjust redundancy of storage of blocks of data in the peer-to-peer storage pool; and

program code for permitting asynchronous updating of distributed hash table directory information in the peer-to-peer storage pool, to reflect the adjusted redundancy.

10. The computer program product of claim 9 further comprising:

program code for subsequently synchronizing the distributed hash table directory information.

11. The computer program product of claim 7 wherein the program code for modifying storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information further comprises:

program code for moving stored blocks of data to nodes with different liveness profiles in the peer-to-peer storage pool, responsive to tracked liveness information.

12. The computer program product of claim 11 wherein the program code for moving stored blocks of data to nodes with different liveness profiles in the peer-to-peer storage pool further comprises:

program code for using a rateless code to store blocks of data on new nodes with different liveness profiles from the old nodes on which the blocks where originally stored;

program code for adding the new nodes as additional block holders in a distributed hash table;

program code for removing directory entries in the distributed hash table concerning storage of the blocks on the old nodes; and

program code for deleting the blocks from the old nodes.

13. A computer system comprising non-transitory storage memory for robustly managing peer-to-peer storage, the computer system comprising:

a peer-to-peer storage manager configured to store an item in a peer-to-peer storage pool as data blocks, at least some of the data blocks being redundant, the redundant data blocks being stored on different nodes of the peer-to-peer storage pool, the peer-to-peer manager configured to track liveness of nodes in a peer-to-peer storage pool to determine a retrieval probability of the item as a whole, and;

the peer-to-peer storage manager configured to modify storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information comprising changing a number of redundant data blocks to adjust the retrieval probability in accordance with a predetermined threshold.

14. The computer system of claim 13 wherein the peer-to-peer storage manager configured to adjust redundancy of storage of blocks of data in the peer-to-peer storage pool is further configured to:

use a rateless code to adjust redundancy of storage of blocks of data in the peer-to-peer storage pool; and

permit asynchronous updating of distributed hash table directory information in the peer-to-peer storage pool, to reflect the adjusted redundancy.

15. The computer system of claim 13 wherein the peer-to-peer storage manager configured to modify storage of data blocks within the peer-to-peer storage pool responsive to tracked liveness information is further configured to:

move stored blocks of data to nodes with different liveness profiles in the peer-to-peer storage pool, responsive to tracked liveness information.