Directing data object access requests in a distributed cache

• US 6,341,311 B1
• Filed: 05/29/1998
• Issued: 01/22/2002
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Valloppillil, Vinod V., Smith, Brian J., Hurvig, Hans
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US09/087,330
• Time in Patent Office: 1,334 Days
• Field of Search: 709/201, 709/203, 709/217, 709/218, 709/219, 709/223, 709/224, 709/225, 709/226, 709/227
• US Class Current: 709/226
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• 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 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method, computer program product, and system for routing URL data object requests in a proxy server array. A URL data object request is received at one proxy server of the array while the desired URL data object resides in the local cache of another proxy server in the array. The receiving proxy server will deterministically identify the residing proxy server based on information residing thereon without resorting to expensive query-response transactions, such as those that occur in proxy server arrays using ICP. An array membership list containing array membership information is available at each and every proxy server and is used in conjunction with the URL as the information for identifying the correct proxy server where the URL data object resides. First, a deterministic hash value is computed for each proxy server name and the URL. Next, a combined hash value is computed that combines the URL hash value with each proxy server hash value. Finally, the proxy server with the highest “score” or combined hash value is identified as the proxy server where the desired URL data object should reside in local cache storage. Since the array membership list, the URL, and the hashing algorithm are the same at each proxy server, the same proxy server will be identified as having the URL data object regardless of which proxy server originally receives the URL data object request.

Claims

1. In a computer network interconnecting a plurality of server systems that store data objects and an array of proxy servers configured to request, receive, and cache data objects from the plurality of server systems on behalf of one or more clients, a method of routing a data object request to a proxy server of the array that is assigned to cache the requested data object, without querying each individual proxy server in the array to determine which proxy server is assigned to cache the requested data object, the method comprising:

providing array membership information at one or more proxy servers, wherein the array membership information identifies one or more proxy servers that are active in the array at a given time;

from at least one client, receiving a request for a data object at a particular proxy server in the array of proxy servers;

performing, by the particular proxy server, a deterministic operation on the array membership information and the data object request in order to identify a proxy server in the array that is assigned to cache the requested data object;

forwarding the data object request to the proxy server identified in the deterministic operation if the identified proxy server is different from the particular server that initially received the request;

examining a local cache of the identified proxy server for the requested data object, and if not found, forwarding the request for the data object to a location external to the array membership so as to obtain the requested data object on behalf of the at least one client and then storing the requested data object in the local cache of the identified proxy server within the array membership; and

sending the requested data object to the at least one client system that requested the data object.

2. The method of claim 1 wherein the data object is a Uniform Resource Locator (“

URL”

) data object and the data object request is a URL request.

3. The method of claim 1 wherein said performing a deterministic operation on the array membership information and data object request comprises:

computing a deterministic hash value for each proxy server identified in the array membership information;

computing a deterministic hash value for the data object based on the data object request;

combining the hash value for the data object and the hash value for each proxy server identified in the array membership information into a deterministic combined hash value for each proxy server identified in the array membership information; and

ordering the proxy servers in the array according to their combined hash values and identifying the proxy server in the array that is assigned to store the data object according to a predetermined criteria.

4. The method of claim 3 wherein the ordering of each array proxy server is from highest to lowest combined hash values and the predetermined criteria is to select the proxy server with the highest combined hash value.

5. The method of claim 1 wherein the array membership information is contained in an array membership list that is distributed to one or more proxy servers in the array.

6. The method of claim 5 wherein distributing the array membership list comprises:

periodically requesting an array membership list from a randomly chosen proxy server of a current array membership list; and

updating the current array membership list with information from the requested array membership list.

7. The method of claim 1 further comprising:

periodically updating the array membership information for proxy server membership changes in the array; and

distributing the updated array membership information to one or more active proxy servers in the array.

8. The method of claim 7 further comprising, when adding a proxy server to the array, distributing to the added proxy server an essentially equal number of cached data objects from one or more other active proxy servers in the array, said distribution not affecting a relocation of any of the cached data objects except for those distributed to the added proxy server, thereby providing a statistically distributed load balancing of the cached data objects across the array of one or more proxy servers, including the added proxy server.

9. The method of claim 7 further comprising, when removing a proxy server from the array, distributing to one or more remaining active proxy servers in the array an essentially equal number of cached data objects from the removed proxy server, said distribution not affecting a relocation of any of the cached data objects except for those distributed from the removed proxy server, thereby providing a statistically distributed load balancing of the cached data objects across the array of proxy servers.

10. The method as recited in claim 1 wherein the deterministic operation includes a relative load factor for at least one proxy server of the array.

11. The method as recited in claim 1 wherein the at least one client is one or more proxy servers that are external to the array.

12. The method as recited in claim 1 wherein the identified proxy server is the particular proxy server that initially received the request.

13. In a computer network interconnecting a plurality of server systems that store data objects and an array of proxy servers configured to request, receive, and cache data objects from the plurality of server systems on behalf of one or more clients, a computer program product comprising:

a computer readable medium storing computer executable instructions for implementing a method of routing a data object request to a proxy server of the array that is assigned to cache the requested data object, without querying each individual proxy server in the array to determine which proxy server is assigned to cache the requested data object;

and wherein the method performed by said executable instructions comprises;

providing array membership information at one or more proxy servers, wherein the array membership information identifies one or more proxy servers that are active in the array at a given time;

from at least one client, receiving a request for a data object at a particular proxy server in the array of proxy servers;

performing, by the particular proxy server, a deterministic operation on the array membership information and the data object request in order to identify a proxy server in the array that is assigned to cache the requested data object;

forwarding the data object request to the proxy server identified in the deterministic operation if the identified proxy server is different from the particular server that initially received the request;

examining a local cache of the identified proxy server for the requested data object, and if not found, forwarding the request for the data object to a location external to the array membership so as to obtain the requested data object on behalf of the at least one client and then storing the requested data object in the local cache of the identified proxy server within the array membership; and

sending the requested data object to the at least one client system that requested the data object.

14. The computer program product of claim 13 wherein the data object is a Uniform Resource Locator (“

URL”

) data object and the data object request is a URL request.

15. The computer program product of claim 13 wherein said performing a deterministic operation on the array membership information and data object request comprises:

computing a deterministic hash value for each proxy server identified in the array membership information;

computing a deterministic hash value for the data object based on the data object request;

combining the hash value for the data object and the hash value for each proxy server identified in the array membership information into a deterministic combined hash value for each proxy server identified in the array membership information; and

ordering the proxy servers in the array according to their combined hash values and identifying the proxy SERVER in the array that is assigned to store the data object according to a predetermined criteria.

16. The computer program product of claim 15 wherein the ordering of each array proxy server is from highest to lowest combined hash values and the predetermined criteria is to select the proxy server with the highest combined hash value.

17. The computer program product of claim 13 wherein the array membership information is contained in an array membership list, and wherein the method further comprises distributing the array membership list to one or more proxy servers in the array.

18. The computer program product of claim 17 wherein distributing the array membership list comprises:

periodically requesting an array membership list from a randomly chosen proxy server of a current array membership list; and

updating the current array membership list with information from the requested array membership list.

19. The computer program product of claim 13 wherein the method further comprises:

periodically updating the array membership information for proxy server membership changes in the array; and

distributing the updated array membership information to one or more active proxy servers in the array.

20. The computer program product of claim 19 wherein the method further comprises, when adding a proxy server to the array, distributing to the added proxy server an essentially equal number of cached data objects from one or more other active proxy servers in the array, said distribution not effecting a relocation of any of the cached data objects except for those distributed to the added proxy server, thereby providing a statistically distributed load balancing of the cached data objects across the array of proxy servers, including the added proxy server.

21. The computer program product of claim 19 wherein the method further comprises, when removing a proxy server from the array, distributing to one or more remaining active proxy servers in the array an essentially equal number of cached data objects from the removed proxy server, said distribution not effecting a relocation of any of the cached data objects except for those distributed from the removed proxy server, thereby providing a statistically distributed load balancing of the cached data objects across the array of one or more proxy servers.

22. The computer program product as recited in claim 13 wherein the deterministic operation includes a relative load factor for at least one proxy server of the array.

23. The computer program product as recited in claim 13 wherein the at least one client is one or more proxy servers that are external to the array.

24. The computer program product as recited in claim 13 wherein the identified proxy server is the particular proxy server that initially received the request.