Distributed hosting of web content using partial replication

• US 20050283537A1
• Filed: 05/14/2004
• Published: 12/22/2005
• Est. Priority Date: 05/14/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin, Zhang, Cha
• Granted Patent: US 7,546,342 B2
• Time in Patent Office: Days
• US Class Current: 709/240
• 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, the content comprising a plurality of files, the method comprising:

calculating a relative importance for each of the plurality of files;

creating a plurality of subsets of the content, the subsets being determined based on the relative importance of each of the plurality of files; 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 calculating the relative importance comprises calculating a file weight based on a type weight assigned to each of the plurality of files.

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

6. The method of claim 1, wherein calculating the relative importance comprises calculating a file weight based on a site weight assigned to each of the plurality of files.

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

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

9. The method of claim 1, wherein calculating the relative importance comprises calculating a file weight based on a type weight and a site weight assigned to each of the plurality of files.

10. The method of claim 1, 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.

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

12. The method of claim 11, wherein a majority of the plurality of messages are a fixed size.

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

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

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

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

17. A method for retrieving content from a web site, the method comprising:

receiving a uniform resource locator for content of a distributed web site;

determining a plurality of computing devices from which to obtain the content, each computing device storing a subset of the content; and

negotiating with the plurality of computing devices to obtain at least one missing item that allows recreating one of the plurality of files of the web site.

18. The method of claim 17, wherein the subset of content is based on a relative importance of each of a plurality of files of the web site.

19. The method of claim 17, wherein the uniform resource locator includes a tag indicating that the uniform resource locator is associated with the distributed web site.

20. The method of claim 17, wherein determining the plurality of computing devices comprises translating the uniform resource locator into a large integer value to identify the plurality of computing devices.

21. The method of claim 20, wherein the large integer value is a global unifier identifier (GUID).

22. The method of claim 20, wherein determining the plurality of computing devices further comprises using a distributed hash table (DHT) protocol with a key, the key being the large integer value.

23. The method of claim 17, further comprising obtaining a summary file associated with the uniform resource locator, the summary file identifying an index of the messages that comprise the web file and a modification time of the web file.

24. The method of claim 23, wherein the summary file is cached locally.

25. The method of claim 23, wherein the summary file is recreated from items obtained from at least one of the plurality of computing devices.

26. The method of claim 23, further comprising verifying the summary file by comparing the modification time of each summary file received so that the missing item identified by the computing device having an earlier modification time is not retrieved.

27. The method of claim 17, wherein the at least one missing item includes a file associated with the web site.

28. The method of claim 17, wherein the at least one missing item includes a packet containing a portion of a file associated with the web site.

29. The method of claim 17, wherein the at least one missing item includes a coded message encoded using an erasure coding scheme, the coded message containing a portion of at least one file associated with the web site.

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

31. The method of claim 29, wherein negotiating with the plurality of computing devices includes transmitting a packet number and a key associated with the erasure coding scheme for each of the at least one missing items.

32. The method of claim 17, further comprising recreating one of the plurality of files based on the at least one missing item that was obtained.

33. The method of claim 32, further comprising displaying the recreated file in a browser.

34. A computer-readable medium having computer-executable instructions for performing the processing recited in claim 17.

35. 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; and

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

36. The system of claim 35, 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.

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

38. A system comprising:

a processor; and

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

receiving a uniform resource locator for content of a distributed web site;

determining a plurality of computing devices from which to obtain the content, each computing device storing a subset of the content; and

negotiating with the plurality of computing devices to obtain at least one missing item that allows recreating one of the plurality of files of the web site.

39. The system of claim 38, wherein determining the plurality of computing devices comprises translating the uniform resource locator into a large integer number, and applying a distributed hash table (DHT) protocol to locate the computing devices holding the large integer number as a key.

40. The system of claim 38, wherein the at least one missing item includes a coded message encoded using erasure coding scheme, the coded message containing a portion of at least one file associated with the web site.

41. The system of claim 40, wherein negotiating with the plurality of computing devices includes transmitting a packet number and a key associated with the erasure coding scheme for each of the at least one missing items.