Method, computer program product, and system for client-side deterministic routing and URL lookup into a distributed cache of URLS

• US 6,311,216 B1
• Filed: 05/29/1998
• Issued: 10/30/2001
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Brian J., Hurvig, Hans
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): TRIM, NKOSI N
• Application Number:
  US09/086,843
• Time in Patent Office: 1,250 Days
• Field of Search: 711/118, 711/122, 711/113, 711/14, 709/217, 709/218, 709/219, 709/226, 709/225, 709/229, 709/203, 709/105
• US Class Current: 709/226
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method, computer program product, and system for directly accessing URL data object requests in a proxy server array. A URL data object request is generated by an enabled client to request a URL data object that resides in the local cache of proxy server in an array of proxy servers configured as a distributed cache. The enabled client 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, or routing the URL data object request through different proxy servers of the array. An array membership list containing array membership information is available at each and every proxy server as well as all enabled clients. This list 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 all enabled clients, the same proxy server will be identified as having the URL data object regardless of which enabled client generated the URL data object request.

Claims

1. In a client system associated with an array of servers configured so as to provide a distributed store of data objects, a method of transmitting a request for a data object to a single server of the array that is assigned to store the data object without sending queries to each server in the array to ascertain the location of the data object, the method comprising the acts of:

providing array membership information at the client system, the array membership information including information identifying each server that is active in the array at a given time;

providing, at the client system, information identifying a data object that is to be accessed by the client system;

determining which single server of the array is assigned to store the data object by performing the acts of;

performing a first deterministic function on the information identifying the data object;

for each server, performing a second deterministic function on the information identifying the server;

combining the results of the first deterministic function with the results of the second deterministic function to generate a value for each server; and

based on the relative values for the servers, deterministically identifying which single server is assigned to store the data object, without sending a query to each server to ascertain the location of the data object; and

transmitting an access request for the data object to the identified single server.

2. The method of claim 1 wherein the data objects are Uniform Resource Locator (“

URL”

) data objects, the servers are proxy servers, the store of data objects is a cache of URL data objects, and the access request is a URL data object access request.

3. The method of claim 1 wherein the first deterministic function and the second deterministic function are deterministic hash functions.

4. The method of claim 3 wherein the act of deterministically identifying which single server is assigned to store the data object comprises the steps of:

ordering the servers based on the values for the servers; and

identifying the server having the highest value as being the server assigned to store the data object.

5. The method of claim 1 wherein the array membership information is contained in an array membership list that is distributed between the servers in the array and accessible to the client system.

6. The method of claim 5 wherein the step of providing array membership information at the client system comprises the acts of:

periodically requesting a new array membership list from a randomly chosen server that is listed in a current array membership list stored at the client system; and

updating the current array membership list with the new array membership list.

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

16. A method as recited in claim 1, wherein the act of combining the results of the first deterministic function with the results of the second deterministic function to generate a value for each server comprises the act of using a third deterministic function selected so as to assign the data objects substantially evenly among the servers in the array.

17. A method as recited in claim 1, wherein the act of combining the results of the first deterministic function with the results of the second deterministic function to generate a value for each server comprises the act of using a third deterministic function selected so as to assign the data objects with relative load factors among the servers in the array.

8. In a client system associated with an array of proxy servers configured so as to provide a cache of uniform resource locator (“

URL”

) data objects distributed across the array of proxy servers, a method of transmitting a request for a URL data object to a single proxy server of the array that is assigned to store the URL data object, the method comprising the acts of;

providing an array membership list at the client system, the list including names of all proxy servers that is active in the array at a given time;

providing, at the client system, a URL identifying a URL data object that is to be accessed by the client system;

determining which single proxy server of the array is assigned to store the URL data object by performing the acts of;

for each of the proxy servers that are active in the array, computing a first deterministic hash value of the name of the proxy server;

computing a second deterministic hash value of the URL;

combining, for each of the proxy servers active in the array, the first deterministic hash value and the second deterministic hash value to generate a deterministic combined hash value associated with each of the proxy servers active in the array; and

based on the relative values of the deterministic combined hash values, deterministically identifying which single proxy server is assigned to store the URL data object; and

transmitting a URL access request for the URL data object to the identified single proxy server.

9. The method of claim 8 wherein the act of deterministically identifying which single proxy server is assigned to store the URL data object comprises the acts of:

ordering the proxy servers based on the values for the servers; and

identifying the proxy server having the highest deterministic combined hash value as being the single proxy server assigned to store the data object.

10. The method of claim 8 wherein each proxy server contains an array membership list and wherein the act of providing an array membership list at the client comprises the acts of:

periodically requesting a new array membership list from a randomly chosen proxy server that is listed in a current array membership list stored at the client system; and

updating the current array membership list with the new array membership list.

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

12. In a client system associated with an array of proxy servers configured so as to provide a cache of uniform resource locator (“

URL”

) data objects distributed across the array of proxy servers, a method of transmitting a request for a URL data object to a single proxy server of the array that is assigned to store the URL data object, the method comprising the acts of;

providing an array membership list at the client system, the list including information identifying all proxy servers that are active in the array at a given time, the list being located on each proxy server of the array, said act of providing an array membership list comprising the acts of;

periodically requesting the array membership list located at a proxy server of the array; and

updating the array membership list at the client system using the requested array membership list;

in response to a URL request generated at the client system, determining which single proxy server is assigned to store a URL data object associated with the URL request without making a query to any of the proxy servers of the array, by performing the acts of;

for each of the proxy servers that are active in the array, computing a first deterministic hash value based on the information identifying the proxy server;

computing a second deterministic hash value of a URL associated with the URL request;

combining, for each of the proxy servers active in the array, the first deterministic hash value and the second deterministic hash value to generate a deterministic combined hash value for each of the proxy servers; and

based on the relative values of the deterministic combined hash values, deterministically identifying which single proxy server is assigned to store the URL data object; and

forwarding the URL request to the identified single proxy server.

13. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 12.

14. A computer-readable medium having computer-executable components for routing a uniform resource locator (“

URL”

) generated at a client system to a single proxy server that is assigned to store a URL data object associated with the URL request, the single proxy server being part an array of proxy servers configured so as to provide a distributed cache of URL data objects, the components comprising;

a request generating component for originating or forwarding a URL request that includes a URL associated with a URL data object that is to be accessed by the client system;

a proxy server identification component for deterministically identifying which single proxy server in the array is assigned to store the URL data object associated with the URL without sending queries to the all of the proxy servers in the array, including performing the acts of;

for each of the proxy servers that are active in the array, computing a first deterministic hash value of a name of the proxy server;

computing a second deterministic hash value of the URL;

combining, for each of the proxy servers active in the array, the first deterministic hash value and the second deterministic hash value to generate a deterministic combined hash value associated with each of the proxy servers active in the array; and

based on the relative values of the deterministic combined hash values, deterministically identifying which single proxy server is assigned to store the URL data object; and

a routing component to route the generated URL request to the identified single proxy server.

15. A system of server computers configured into a distributed cache for holding Uniform Resource Locator (“

URL”

) data objects and client computers that access the distributed cache, wherein a URL request generated at a client computer can be routed directly to the server computer that is assigned to store the requested URL data object without queries being made to any other server computer, the system comprising;

at least two server computers, each server computer comprising;

a CPU;

storage means, electronically coupled and responsive to said CPU, said storage means containing membership information including information identifying all server computers included in the distributed cache;

means, electronically coupled and responsive to said CPU, for receiving URL requests from clients of the distributed cache; and

at least one client computer being a client of the distributed cache, said client computer comprising;

a CPU;

storage means, electronically coupled and responsive to said CPU, said storage means containing membership information including information identifying all server computers included in the distributed cache;

means, electronically coupled and responsive to said CPU, for generating a URL request;

means, electronically coupled and responsive to said CPU, for deterministically identifying which single server computer in the distributed cache is assigned to store a URL data object associated with the URL request by performing the acts of;

for each of the servers computers in the array, computing a first deterministic hash value of the information identifying the server computer;

computing a second deterministic hash value of a URL that is associated with the URL request;

combining, for each of the server computers, the first deterministic hash value and the second deterministic hash value to generate a deterministic combined hash value associated with each of the server computers; and

based on the relative values of the deterministic combined hash values, deterministically identifying which single server computer is assigned to store the URL data object; and

means, electronically coupled and responsive to said CPU, for routing the URL request to the identified single server computer.