Distributed hosting of web content using partial replication

• US 7,546,342 B2
• Filed: 05/14/2004
• Issued: 06/09/2009
• Est. Priority Date: 05/14/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Cha, Li, Jin
• Primary Examiner(s): BOUTAH, ALINA A
• Application Number:
  US10/845,625
• Publication Number:
  US 20050283537A1
• Time in Patent Office: 1,852 Days
• Field of Search: 709/240, 709/203, 709/219, 709/241, 707/100
• US Class Current: 709/203
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

The mechanisms described herein are directed at hosting content of a web site on multiple computing devices. A relative importance for each file associated with the web site is calculated. This relative importance is used to calculate several subsets of the content which are distributed to several devices within a computer cluster, such as a server array, peer-to-peer network, and the like. The subsets may include coded messages created using an erasure coding scheme on packets containing portions of one or more files. Upon retrieving a file, a fixed number of distinct coded messages are retrieved from the devices based on the erasure coding scheme. The file is re-created with these distinct messages. Because multiple devices hold the content, the web site may be retrieved significantly faster and the reliability is increased without consuming a large amount of storage space or bandwidth of any one computing device.

Claims

1. A method for distributing content of a web site among multiple computing devices within a computer cluster comprising a host computing device and one or more peer computing devices, the content comprising a plurality of files, the method comprising:

calculating a relative importance for each of the plurality of files, wherein calculating the relative importance comprises calculating a file weight (FW) based on a type weight (T) and a site weight (S) assigned to each of the plurality of files such that

FW=S×

T;

creating a plurality of subsets of the content, the subsets being determined based on the relative importance of each of the plurality of files, wherein creating the plurality of subsets is further based on an individual replication amount specified for each computing device, the individual replication amount being based upon a storage amount on the computing device for holding one of the subsets and is determined by;

$D<br><br>\left(\mathrm{\lambda <br><br>}<br><br><br><br>i\right)=\underset{m}{\sum <br><br>}<br><br><br><br>P<br><br><br><br>m<br><br><br><br>\max <br><br>\left(1,F<br><br><br><br>W<br><br><br><br>m\times <br><br>\mathrm{\lambda <br><br>}<br><br><br><br>i\right),$

 

where D(λ

_i) represents a total amount to be replicated to a peer computing device i, λ

_i represents the file weight for an mth file of the web site and Pm represents a file size of the mth file of the web site; and

distributing one of the plurality of subsets to each of the multiple computing devices.

2. The method of claim 1, wherein the computer cluster comprises a server array.

3. The method of claim 1, wherein the computer cluster comprises a peer-to-peer network.

4. The method of claim 1, wherein the type weight is based on a file extension.

5. The method of claim 1, wherein the site weight is assigned to a directory with each file within the directory having the site weight of the directory.

6. The method of claim 5, wherein a sub-directory of the directory inherits the site weight assigned to the directory.

7. The method of claim 1, wherein the plurality of files is divided into a plurality of messages, and each subset includes at least one message.

8. The method of claim 7, wherein a majority of the plurality of messages are a fixed size.

9. The method of claim 1, further comprising dividing the plurality of files into a plurality of original messages, applying an erasure coding scheme to derive a plurality of coded messages, and adding one or more of the coded messages into each subset.

10. The method of claim 9, wherein the erasure coding scheme comprises a Reed-Solomon codec.

11. The method of claim 9, wherein distributing one of the plurality of subsets comprises distributing the subset based on a key associated with the erasure coding scheme.

12. A computer-readable storage medium having computer-executable instructions stored thereon for performing the processing recited in claim 1.

13. A system comprising:

a processor; and

a memory into which a plurality of instructions are loaded, the plurality of instructions performing a method comprising;

assigning a type weight to a file associated with a web site;

assigning a site weight to the file;

calculating a file weight for the file based on the type weight and the site weight;

calculating a replication ratio for the file, wherein the replication ratio is determined by;

wm,i=max{1,FWm×

λ

i},

where w_mi represents a peer replication ratio for a mth file for a peer i, λ

_i represents a peer replication factor calculated for the peer i and FW_m represents the file weight for the mth file in the web site; and

sending the file to one of a plurality of computing devices based on the replication ratio.

14. The system of claim 13, further comprising splitting the file into a plurality of messages, and wherein sending the file comprises sending at least one of the plurality of messages associated with the file to the one computing device.

15. The system of claim 14, further comprising applying an erasure coding scheme to derive a plurality of coded messages, the coded messages being the messages.