Method, computer program product, and system for migrating URLs within a dynamically changing distributed cache of URLs

• US 6,377,991 B1
• Filed: 05/29/1998
• Issued: 04/23/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: Smith, Brian J., Hurvig, Hans
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US09/087,687
• Time in Patent Office: 1,425 Days
• Field of Search: 709/221, 709/219, 709/214, 709/222, 709/223, 709/220, 709/203, 709/224, 709/226, 700/79, 707/202
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level

Abstract

A method, computer program product, and system for migrating URL data objects in a proxy server array when an array member is removed, added, or temporarily unavailable. An array membership list containing array membership information is available at each proxy server in the array and at all enabled client that 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 is the same at each proxy server or enabled client, the same proxy server will be identified as having the URL data object regardless of which proxy server originally receives or enabled client generates the URL data object request. The hashing algorithm is designed to automatically compensate for changes in the array membership list so that only the fewest amount of URL data objects will migrate from the local cache of one proxy server to another proxy server as a result of array membership changes.

Claims

1. In a system including one or more clients that request one or more data objects over a network comprised of an array of servers, and wherein each server has a local cache for storing data objects that have been assigned to that server, with the result that i) the array of servers is thereby able to provide a distributed cache for the data objects requested by the one or more clients, and so that ii) requests for data objects will be directed to a particular server at which the data object should be stored, a method of maintaining an essentially balanced distribution of the data objects across the array of servers even in the event that a server of the array is removed, or in the event that a server is added to the array, while still preserving the ability to more efficiently determine and direct a particular request for a data object to the server in the array where the data object should be stored, the method comprising:

a step for assigning to each requested object a particular server at which the object is to be cached so that when a client makes a request to a particular server for an object, either the client or the server, as appropriate, will be able to determine where the object should be in the array of servers and will then be able to direct the request accordingly;

in the event that the array of servers is changed by either adding a new server to the array of servers, or removing a server from the array of servers, then in either case performing

a step for reassigning some of the objects from one or more servers now included in the array of servers so as to more equally distribute the data objects across the current array of servers;

thereafter, when a client makes a request to a particular server of the current array of servers for a data object, a step for determining at one or the other of either the client or the server to which the request was made, where the object should be stored in the current array of servers;

a step for directing the client'"'"'s request to the particular server in the current array of servers where the requested object should be stored; and

if the particular server in the current array of servers where the requested object should be stored does not have the object cached, then retrieving the object and storing it in the local cache of the particular server to which the requested object is assigned for caching.

2. A method as recited in claim 1 wherein the data objects are Uniform Resource Locator (“

URL”

) data objects, and the servers are proxy servers.

3. A method as recited in claim 1 wherein the removed server is a proxy server that is temporarily unavailable.

4. A method as recited in claim 1 wherein there are N servers in the array of servers before adding a server and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers is comprised of an act of reassigning by directing requests for 1/(N+1) data objects from each of the N servers to the newly added server.

5. A method as recited in claim 1 wherein there are N servers in the array of servers before removing a server and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers is comprised of an act of reassigning by directing requests for 1/N data objects from the removed server.

6. A method as recited in claim 1, further comprising a step for providing array membership information at each server in the array of servers, and a step for enabling at least some clients by providing the array membership information to such clients, and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers comprises an act deterministically processing both a particular data object request and the array membership information to identify a particular server where the particular data object should be stored without making a query to any of the other servers in the current array of servers.

7. The method of claim 6 wherein the array membership information is contained in an array membership list that further contains a load factor for each server, wherein the data objects are balanced across the distributed store according to the load factor for each server in the array of servers.

8. The method of claim 6 wherein said processing of the array membership information and the particular data object request to identify the server where the particular data object should be stored comprises steps for:

computing a deterministic hash value for each server in the current array of servers;

computing a deterministic hash value for the particular data object;

combining the hash value for the particular data object and each hash value for each server in the current array of servers into a deterministic combined hash value for each server in the array of servers; and

ordering the servers according to the combined hash values and selecting a server according to a predetermined criteria.

9. The method of claim 8 wherein the ordering of servers in the array of servers is from highest to lowest combined hash values and the predetermined criteria is to select the server with the highest combined hash value.

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

11. In a system including one or more clients that request one or more data objects over a network comprised of an array of proxy servers, and wherein each proxy server has a local cache for storing data objects that have been assigned to that proxy server, with the result that i) the array of proxy servers is thereby able to provide a distributed cache for the data objects requested by the one or more clients, and so that ii) requests for data objects will be directed to a particular proxy server at which the data object should be stored, a method of maintaining an essentially balanced distribution of the data objects across the array of proxy servers even in the event that a server of the array is removed, or in the event that a server is added to the array, while still preserving the ability to more efficiently determine and direct a particular request for a data object to the server in the array where the data object should be stored, the method comprising:

a step for assigning to each requested object a particular server at which the object is to be cached so that when a client makes a request to a particular server an object, either the client or the server, as appropriate, will be able to determine where the object should be in the array of servers and will then be able to direct the request accordingly;

in the event that a proxy server is added to the array of proxy servers, then performing a step for reassigning some of the data objects to the added proxy server from each of the other active proxy servers in the array of proxy servers by directing requests for an essentially equal number of cached data objects that were assigned to be stored on each of the other proxy servers to the added proxy server, said reassignment not effecting a relocation of any of the cached data objects in the current array of proxy servers;

in the event that a proxy server is removed from the array of proxy servers, then performing a step for reassigning to the remaining active proxy servers in the array of proxy servers an essentially equal number of cached data objects that were previously assigned to the removed proxy server by directing requests for the essentially equal number of cached data objects to each of the remaining active proxy servers, said reassignment not effecting a relocation of any of the cached data objects stored on the removed server so as to more equally distribute the data objects across a current array of proxy servers; and

whenever a proxy server is added to the array or removed from the array, altering array membership information of each active proxy server in the current array of proxy servers such that the reassignment of the data objects for the event of a proxy server being either added or removed from the array of proxy servers can be deterministically determined based on the array membership information and a data object access request.

12. A method as recited in claim 11 wherein the removed proxy server is a proxy server that is temporarily unavailable.

13. A method as recited in claim 11 wherein there are N proxy servers in the array of proxy servers before adding a proxy server to the array of proxy servers and wherein said step for reassigning some of the data objects in the event that a proxy server is added to the array of proxy server is comprised of an act of reassigning by directing requests for 1/(N+1) data objects to the newly added proxy server.

14. A method as recited in claim 11 wherein there are N proxy servers in the array of proxy servers before removing a proxy server from the array and wherein said step of reassigning dome of the data objects in the event that a proxy server is removed from the array of proxy servers is comprised of an act of reassigning by directing requests for 1/N data objects to each of the remaining proxy servers in the array of proxy servers.

15. A method as recited in claim 11 further comprising a step for providing an array membership list at each proxy server and a step for enabling at least some clients by providing the array membership list to such clients the array membership list identifying all proxy servers that are active in the current array of proxy servers at a given time, and wherein the distribution of data object requests due to adding or removing a proxy server from the array of proxy servers comprises deterministically processing both a particular data object request and the array membership list to identify the proxy server assigned to store the particular data object without making a query to any of the other proxy servers in the current array of proxy servers.

16. The method of claim 15 wherein a load factor is associated with each proxy server in the array membership list and the data objects are assigned to the proxy servers according to the load factor for each individual proxy server.

17. The method of claim 15 wherein said processing of the array membership list and data object request to identify the proxy server assigned to store the particular data object comprises steps for:

computing a deterministic hash value for each proxy server contained in the array membership list;

computing a deterministic hash value for the particular data object;

combining the hash values for the particular data object and for each proxy server in the array membership list into a deterministic combined hash value for each proxy server in the array membership list; and

ordering the proxy servers in the array of proxy servers according to the combined hash values and selecting a proxy server according to a predetermined criteria.

18. The method of claim 17 wherein the ordering of the proxy servers is from highest to lowest combined hash values and the predetermined criteria is to select the proxy server with the highest combined hash value.

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

20. In a system including one or more clients that request one or more data objects over a network comprised of an array of servers, and wherein each server has a local cache for storing data objects that have been assigned to that server, with the result that i) the array of servers is thereby able to provide a distributed cache for the data objects requested by the one or more clients, and so that ii) requests for data objects will be directed to a particular server at which the data object should be stored, a method of maintaining an essentially balanced distribution of the data objects across the array of servers when requesting a data object from the array of servers even in the event that a server of the array is removed, or in the event that a server is added to the array, while still preserving the ability to more efficiently determine and direct a particular request for a data object to the server in the array where the data object should be stored, the method comprising:

a step for providing an array membership list at each proxy server, the array membership list identifying all proxy servers that are active in the array at a given time;

a step for enabling at least some of the clients, wherein the array membership list is provided to such clients;

in the event that the array of servers is changed by either adding a new server to the array of servers, or by removing a server from the array of servers, then in either case performing

a step for altering each array membership list to reflect that a server has been added or removed from the array;

a step for reassigning some of the objects from one or more servers now included in the array of servers so as to more equally distribute the data objects across the current array of servers;

a step for directing each data object request to the server that is assigned to store that data object by processing a particular data object and the altered array membership list in order to identify the proxy server that is assigned to store the particular data object; and

if the server in the current array of servers that is assigned to store the requested data object does not have the data object cached, then retrieving the data object and storing it in the local cache of the server to which the requested data object is assigned for caching.

21. The method of claim 20 wherein said step for directing each data object request to the server that is assigned to store that data object by processing a particular data object and the altered array membership list to identify the proxy server that is assigned to store the particular data object further comprises:

a step for computing a deterministic hash value for each server contained in the current array membership list;

a step for computing a deterministic hash value for the particular data object;

a step for combining the hash values of the particular data object and each server in the current array membership list into a deterministic combined hash value for each in the current array; and

a step for ordering the servers in the array according to the combined hash values; and

selecting a server according to a predetermined criteria, the selected server being assigned to store the particular data object.

22. The method of claim 21 wherein the step for ordering the proxy servers comprises an act of ordering the servers from highest to lowest combined hash values and wherein the predetermined criteria is to select the server with the highest combined hash value.

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

24. In a system including one or more clients that request one or more data objects over a network comprised of an array of servers, and wherein each server has a local cache for storing data objects that have been assigned to that server, with the result that i) the array of servers is thereby able to provide a distributed cache for the data objects requested by the one or more clients, and so that ii) requests for data objects will be directed to a particular server at which the data object should be stored, a computer program product for implementing a method of maintaining an essentially balanced distribution of the data objects across the array of servers even in the event that a server of the array is removed, or in the event that a server is added to the array, while still preserving the ability to more efficiently determine and direct a particular request for a data object to the server in the array where the data object should be stored, the computer program product comprising:

a computer readable medium having computer readable instructions for performing the method, the method comprising;

a step for assigning to each requested object a particular server at which the object is to be cached so that when a client makes a request to a particular server for an object, either the client or the server, as appropriate, will be able to determine where the object should be in the array of servers and will then be able to direct the request accordingly;

in the event that the array of servers is changed by either adding a new server to the array of servers, or removing a server from the array of servers, then in either case performing

a step for reassigning some of the objects from one or more servers now included in the array of servers so as to more equally distribute the data objects across the current array of servers;

thereafter, when a client makes a request to a particular server of the current array of servers for a data object, a step for determining at one or the other of either the client or the server to which the request was made, where the object should be stored in the current array of servers;

a step for directing the client'"'"'s request to the particular server in the current array of servers where the requested object should be stored; and

if the particular server in the current array of servers where the requested object should be stored does not have the object cached, then retrieving the object and storing it in the local cache of the particular server to which the requested object is assigned for caching.

25. A computer program product as in claim 24, wherein the data objects are Uniform Resource Locator (“

URL”

) data objects, and the servers are proxy servers.

26. A computer program product as in claim 24, wherein the removed server is a proxy server that is temporarily unavailable.

27. A computer program product as in claim 24, wherein there are N servers in the array of servers before adding a server and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers is comprised of an act of reassigning by directing requests for 1/(N+1) data objects from each of the N servers to the newly added server.

28. A computer program product as in claim 24, wherein there are N servers in the array of servers before removing a server and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers is comprised of an act of reassigning by directing requests for 1/N data objects from the removed server.

29. A computer program product as in claim 24, further comprising a step for providing array membership information at each server in the array of servers, and a step for enabling at least some clients by providing the array membership information to such clients, and wherein said step for reassigning some of the objects from one or more servers now included in the array of servers comprises an act deterministically processing both a particular data object request and the array membership information to identify a particular server where the particular data object should be stored without making a query to any of the other servers in the current array of servers.

30. A computer program product as in claim 29, wherein the array membership information is contained in an array membership list that further contains a load factor for each server, wherein the data objects are balanced across the distributed store according to the load factor for each server in the array of servers.

31. A computer program product as in claim 29, wherein said processing of the array membership information and the particular data object request to identify the server where the particular data object should be stored comprises steps for:

computing a deterministic hash value for each server in the current array of servers;

computing a deterministic hash value for the particular data object;

combining the hash value for the particular data object and each hash value for each server in the current array of servers into a deterministic combined hash value for each server in the array of servers; and

ordering the servers according to the combined hash values and selecting a server according to a predetermined criteria.

32. A computer program product as in claim 31, wherein the ordering of servers in the array of servers is from highest to lowest combined hash values and the predetermined criteria is to select the server with the highest combined hash value.

33. In a system including one or more clients that request one or more data objects over a network comprised of an array of proxy servers, and wherein each proxy server has a local cache for storing data objects that have been assigned to that proxy server, with the result that i) the array of proxy servers is thereby able to provide a distributed cache for the data objects requested by the one or more clients, and so that ii) requests for data objects will be directed to a particular proxy server at which the data object should be stored, a computer program product for implementing a method of maintaining an essentially balanced distribution of the data objects across the array of proxy servers even in the event that a server of the array is removed, or in the event that a server is added to the array, while still preserving the ability to more efficiently determine and direct a particular request for a data object to the server in the array where the data object should be stored, the computer program product comprising:

a computer readable medium having computer executable instructions for performing the method, the method comprising;

a step for assigning to each requested object a particular server at which the object is to be cached so that when a client makes a request to a particular server an object, either the client or the server, as appropriate, will be able to determine where the object should be in the array of servers and will then be able to direct the request accordingly;

in the event that a proxy server is added to the array of proxy servers, then performing a step for reassigning some of the data objects to the added proxy server from each of the other active proxy servers in the array of proxy servers by directing requests for an essentially equal number of cached data objects that were assigned to be stored on each of the other proxy servers to the added proxy server, said reassignment not effecting a relocation of any of the cached data objects in the current array of proxy servers;

in the event that a proxy server is removed from the array of proxy servers, then performing a step for reassigning to the remaining active proxy servers in the array of proxy servers an essentially equal number of cached data objects that were previously assigned to the removed proxy server by directing requests for the essentially equal number of cached data objects to each of the remaining active proxy servers, said reassignment not effecting a relocation of any of the cached data objects stored on the removed server so as to more equally distribute the data objects across a current array of proxy servers; and

whenever a proxy server is added to the array or removed from the array, altering array membership information of each active proxy server in the current array of proxy servers such that the reassignment of the data objects for the event of a proxy server being either added or removed from the array of proxy servers can be deterministically determined based on the array membership information and a data object access request.

34. A computer program product as defined in claim 33, wherein the removed proxy server is a proxy server that is temporarily unavailable.

35. A computer program product as defined in claim 33, wherein there are N proxy servers in the array of proxy servers before adding a proxy server to the array of proxy servers and wherein said step for reassigning some of the data objects in the event that a proxy server is added to the array of proxy server is comprised of an act of reassigning by directing requests for 1/(N+1) data objects to the newly added proxy server.

36. A computer program product as defined in claim 33, wherein there are N proxy servers in the array of proxy servers before removing a proxy server from the array and wherein said step of reassigning dome of the data objects in the event that a proxy server is removed from the array of proxy servers is comprised of an act of reassigning by directing requests for 1/N data objects to each of the remaining proxy servers in the array of proxy servers.

37. A computer program product as defined in claim 33, further comprising a step for providing an array membership list at each proxy server and a step for enabling at least some clients by providing the array membership list to such clients the array membership list identifying all proxy servers that are active in the current array of proxy servers at a given time, and wherein the distribution of data object requests due to adding or removing a proxy server from the array of proxy servers comprises deterministically processing both a particular data object request and the array membership list to identify the proxy server assigned to store the particular data object without making a query to any of the other proxy servers in the current array of proxy servers.

38. A computer program product as defined in claim 37, wherein a load factor is associated with each proxy server in the array membership list and the data objects are assigned to the proxy servers according to the load factor for each individual proxy server.

39. A computer program product as defined in claim 37, wherein said processing of the array membership list and data object request to identify the proxy server assigned to store the particular data object comprises steps for:

computing a deterministic hash value for each proxy server contained in the array membership list;

computing a deterministic hash value for the particular data object;

combining the hash values for the particular data object and for each proxy server in the array membership list into a deterministic combined hash value for each proxy server in the array membership list; and

ordering the proxy servers in the array of proxy servers according to the combined hash values and selecting a proxy server according to a predetermined criteria.

40. A computer program product as defined in claim 39, wherein the ordering of the proxy servers is from highest to lowest combined hash values and the predetermined criteria is to select the proxy server with the highest combined hash value.