Reliable, efficient peer-to-peer storage

• US 20070208748A1
• Filed: 02/22/2006
• Published: 09/06/2007
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin
• Granted Patent: US 9,047,310 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104

Abstract

An adaptive coding storage system that uses adaptive erasure resilient code (ERC) which changes the number of fragments used for encoding according to the size of the file distributed. Adaptive ERC may greatly improve the efficiency and reliability of P2P storage. A number of procedures for P2P storage applications may also be implemented. In one embodiment small, dynamic data files are diverted to the more reliable peers or even a server, while large and static files are stored utilizing the storage capacity of the unreliable peers. Also, for balanced contribution and benefit, a peer should host the same amount of content as it stored in the P2P network. As a result, unreliable peers are allowed to distribute less data, and more reliable peers are allowed to distribute more. Also, smaller files are assigned a higher distribution cost, and the larger files are assigned a lower distribution cost.

Claims

1. A computer-implemented process for encoding files to be stored in a distributed network, comprising the process actions of:

calculating optimal file size ranges corresponding to different erasure resilient coding (ERC) number of fragments, wherein each number of fragments is the optimal number of fragments for a corresponding range of file sizes;

inputting a file of a given file size;

if the file size is smaller than the range of the file sizes for the smallest ERC number of fragments of two, encoding the file without using erasure resilient coding;

if the file size of the input file corresponds to a range of file sizes, encoding the file using erasure resilient coding and the optimal number of fragments corresponding to the file size range of the input file.

2. The computer-implemented process of claim 1 further comprising the process action of sending the encoded file to one or more peers in a distributed network.

3. The computer-implemented process of claim 1 further comprising computing the number of peers that the encoded file will be stored to according to peer reliability and desired reliability of file content.

4. The computer-implemented process of claim 1 wherein calculating optimal file size ranges corresponding to different erasure resilient coding (ERC) number of fragments, comprises the process actions of:

determining a boundary between different numbers of fragments as the optimal file size suited for a particular ERC number of fragments.

5. The computer-implemented process of claim 1, further comprising the process actions of:

obtaining a set of file fragments of the encoded file equal to or greater than a number of fragments that the file is split into for encoding; and

decoding the encoded file fragments with erasure resilient decoding if the file was erasure resilient coded to obtain a decoded version of the encoded file; and

decoding the encoded fragments without erasure resilient decoding if the file was not erasure resilient coded to obtain a decoded version of the encoded file.

6. The computer-implemented process of claim 1 wherein the erasure resilient coding used in encoding the file is Reed Solomon coding.

7. The computer-implemented process of claim 6 wherein:

if the file size less than approximately 10 KB, erasure resilient coding is not used;

if the file size is approximately 10 KB to 33 KB, the optimum number of fragments is two;

if the file size is approximately 33 KB to 100 KB, the optimum number of fragments is four;

if the file size is approximately 100 KB to 310 KB, the optimum number of fragments is eight;

if the file size is approximately 310 KB to 950 KB, the optimum number of fragments is sixteen;

if the file size is approximately 950 KB to 2.9 MB, the optimum number of fragments is thirty two;

if the file size is approximately 2.9 MB to 8.9 MB, the optimum number of fragments is sixty four;

if the file size is approximately 8.9 MB to 26 MB, the optimum number of fragments is one hundred and twenty eight; and

if the file size is greater than approximately 26 MB, the optimum number of fragments is two hundred and fifty six.

8. A computer-readable medium having computer-executable instructions for performing the process recited in claim 1.

9. A system for improving the storage reliability and efficiency of a peer-to-peer network, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,

determine the optimum number of fragments to encode a file of given size with erasure resilient coding;

if the optimum number of fragments to encode the file with erasure resilient encoding is one, do not encode the file with erasure resilient coding; and

if the optimum number of fragments is larger than one, encode the file by breaking the file into the optimum number of fragments and encoding the file with erasure resilient coding.

10. The system of claim 9 further comprising a program module to compute the number of peers that the encoded file fragments will be stored to according to peer reliability and desired reliability of file content.

11. The system of claim 10 further comprising a program module to distribute the file encoded with erasure resilient coding to one or more peers on a network.

12. The system of claim 11 wherein the program module to distribute the file comprises sub-modules to:

determine the reliability of each peer in the distributed network;

determine the size of the file;

and use one or more peers with proper reliability as determined by file size to distribute the file.

13. The system of claim 12 wherein the program module to distribute the file comprises sub-modules to:

if the file is large, use peers whose reliability is below a given threshold to distribute the large file; and

if the file is not large, use peers whose reliability is above a given threshold to distribute the file.

14. The system of claim 11 wherein the program module to distribute the file comprises sub-modules to:

determine the reliability of each peer in the distributed network;

determine if the file is static;

if the file is static, use peers whose reliability is below a given threshold to distribute the file; and

if the file is not static, use peers whose reliability is above a given threshold to distribute the file.

15. The system of claim 11 wherein the program module to distribute the file comprises sub-modules to:

determine the reliability of each peer in the distributed network;

monitor changes of the file;

first distribute the file to more reliable peers;

if the file is observed not to change, redistribute the file to less reliable peers.

16. The system of claim 9 further comprising a program module to improve efficiency of the distributed network using a server, further comprising sub-modules to:

back up all dynamic files in the distributed network to the server;

periodically have peers and the server in the distributed network check to see if the dynamic files backed up to the server have changed;

if the dynamic files have not changed, designate these files as static and bundle them together into a large file; and

distribute the large file with erasure resilient coding to the distributed network.

17. The system of claim 9 wherein the program module to determine the optimum number of fragments to encode a file of a given size with erasure resilient coding comprises sub-modules to:

determine an optimum file size range for each possible erasure resilient coding number of fragments, wherein each number of fragments is the optimum number of fragments for the corresponding range;

determine into which file size range the size of an input file falls;

use as the optimum number of fragments corresponding to the optimum file size range into which the size of the input file falls.

18. A computer-implemented process for decoding an encoded file stored in a distributed network, comprising the process actions of:

retrieving a set of fragments of an encoded file equal to or greater than the number of fragments that were used to encode the file, wherein the file was erasure resilient encoded with an optimum number of fragments for a given file size; and

decoding the encoded fragments with erasure resilient decoding to obtain a decoded version of the encoded file.

19. The computer-implemented process of claim 18 wherein at least some of the encoded fragments are retrieved from a storage medium of one or more peers in the distributed network.

20. The computer-implemented process of claim 18 wherein at least some of the encoded fragments are retrieved from a storage medium of a server on the distributed network.