Data distribution techniques for load-balanced fault-tolerant web access

• US 6,070,191 A
• Filed: 10/17/1997
• Issued: 05/30/2000
• Est. Priority Date: 10/17/1997
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Narendran, Balakrishnan, Yajnik, Shalini, Rangarajan, Sampath
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US08/953,577
• Time in Patent Office: 956 Days
• Field of Search: 709/201, 709/203, 709/217, 709/218, 709/219-227, 707/1, 707/10, 707/100, 707/200, 707/202
• US Class Current: 709/226
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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/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

A server system for processing client requests received over a communication network includes a cluster of N document servers and at least one redirection server. The redirection server receives a client request from the network and redirects it to one of the document servers, based on a set of pre-computed redirection probabilities. Each of the document servers may be an HTTP server that manages a set of documents locally and can service client requests only for the locally-available documents. A set of documents are distributed across the document servers in accordance with a load distribution algorithm which may utilize the access rates of the documents as a metric for distributing the documents across the servers and determining the redirection probabilities. The load distribution algorithm attempts to equalize the sum of the access rates of all the documents stored at a given document server across all of the document servers. In the event of a server failure, the redirection probabilities may be recomputed such that the load of client requests is approximately balanced among the remaining document servers. The redirection probabilities may also be recomputed periodically in order to take into account changes in document access rates and changes in server capacity. The recomputation may be based on a maximum-flow minimum-cost solution of a network flow problem.

Claims

1. A method of processing client requests received in a server system over a communication network, the method comprising the steps of:

determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents;

computing a set of redirection probabilities based on the distribution;

routing a client request to a redirection server; and

redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.

2. The method of claim 1 wherein at least one of the document servers is an HTTP server.

3. The method of claim 1 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.

4. The method of claim 3 wherein the subset of documents for a given document server are available locally on that document server.

5. The method of claim 3 wherein the subset of documents for a given document server are available to that server over a local area network.

6. The method of claim 3 wherein the redirection server redirects a request for a given document to one of the document servers only if a copy of the given document is available to that document server.

7. The method of claim 1 wherein the documents are permitted to be replicated, such that more than one document server may be a candidate for servicing a given client request.

8. The method of claim 1 further including the step of determining the redirection probabilities and an initial distribution of the set of documents across the plurality of document servers using a load distribution algorithm.

9. The method of claim 8 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after the initial document distribution is complete.

10. The method of claim 8 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.

11. The method of claim 8 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.

12. The method of claim 11 wherein the load balancing metric is the access rates of the documents.

13. The method of claim 12 wherein the load distribution algorithm attempts to equalize the sum of the access rates of all the documents accessible to a given document server across all of the document servers.

14. The method of claim 11 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.

15. The method of claim 12 wherein if λ

is the rate at which client requests are received in the redirection server, the load distribution algorithm distributes the documents across N document servers such that the rate of requests redirected to each server is approximately λ

/N.

16. The method of claim 8 wherein the load distribution algorithm includes the steps of:

randomly selecting a document and one of the document servers;

mapping an access rate of the selected document to the selected server; and

if the selected server has additional capacity, randomly selecting another document and mapping it to the selected server.

17. The method of claim 16 wherein the load distribution algorithm includes the steps of:

mapping a portion of an access rate of a randomly-selected document to the selected server; and

if the selected server has insufficient capacity to accommodate the entire access rate of the randomly-selected document, selecting another document server at random, and mapping a remaining portion of the access rate of the randomly-selected document to the other randomly-selected document server.

18. The method of claim 17 wherein the selecting and mapping steps are repeated until the entire access rates of all of the documents have been mapped to document servers.

19. The method of claim 8 wherein the load distribution algorithm is a two-phase algorithm including a first phase and a second phase, and the first phase includes the step of distributing documents to the document servers in accordance with a round robin technique, and further wherein the first phase ends when any server exceeds its access rate capacity.

20. The method of claim 19 wherein the second phase of the two-phase algorithm distributes document copies to a document server until a cumulative maximum access rate is reached for that server, and then distributes document copies to another document server, and wherein replication of a given document copy takes place when a given document server exceeds its capacity when the given document copy is distributed to the given server.

21. The method of claim 1 further including the step of recomputing the set of redirection probabilities after a change in conditions associated with the server system.

22. The method of claim 21 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.

23. The method of claim 22 wherein the recomputing step is based on a maximum-flow minimum-cost solution of a network flow problem.

24. The method of claim 1 further including the step of utilizing a binning algorithm to redistribute documents from a failed one of the document servers to the remaining document servers.

25. A server system for processing client requests received over a communication network, the system comprising:

a plurality of document servers, wherein a distribution of a set of documents over the plurality of document servers is determined based at least in part on access rates of at least a subset of the documents; and

at least one redirection server for receiving a client request and for redirecting the client request to one of the plurality of document servers based on a set of redirection probabilities computed from the distribution.

26. The apparatus of claim 25 wherein at least one of the document servers is an HTTP server.

27. The apparatus of claim 25 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.

28. The apparatus of claim 27 wherein the subset of documents for a given document server are available locally on that document server.

29. The apparatus of claim 27 wherein the subset of documents for a given document server are available to that server over a local area network.

30. The apparatus of claim 27 wherein the redirection server redirects a request for a given document to one of the document servers only if a copy of the given document is available to that document server.

31. The apparatus of claim 25 wherein the documents are permitted to be replicated, such that more than one document server may be a candidate for servicing a given client request.

32. The apparatus of claim 25 wherein the redirection probabilities are determined and the set of documents are distributed across the plurality of document servers in accordance with a load distribution algorithm.

33. The apparatus of claim 32 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after an initial document distribution is complete.

34. The apparatus of claim 32 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.

35. The apparatus of claim 32 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.

36. The apparatus of claim 35 wherein the load balancing metric is the access rates of the documents.

37. The apparatus of claim 35 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.

38. The apparatus of claim 36 wherein the load distribution algorithm attempts to equalize the sum of the access rates of all the documents accessible to a given document server across all of the document servers.

39. The apparatus of claim 32 wherein if λ

is the rate at which client requests are received in the redirection server, the load distribution algorithm distributes the documents across N document servers such that the rate of requests redirected to each server is approximately λ

/N.

40. The apparatus of claim 32 wherein the load distribution algorithm is a two-phase algorithm including a first phase and a second phase, and the first phase distributes documents to the document servers in accordance with a round robin technique, and further wherein the first phase ends when any server exceeds its access rate capacity.

41. The apparatus of claim 40 wherein the second phase of the two-phase algorithm distributes document copies to a document server until a cumulative maximum access rate is reached for that server, and then distributes document copies to another document server, and wherein replication of a given document copy takes place when a given document server exceeds its capacity when the given document copy is distributed to the given server.

42. The apparatus of claim 25 wherein the redirection probabilities are recomputed after a change in conditions associated with the server system.

43. The apparatus of claim 42 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.

44. An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising:

means for determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents;

means for computing a set of redirection probabilities based on the distribution;

means for routing a client request to a redirection server; and

means for redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.

45. The apparatus of claim 44 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.

46. The apparatus of claim 44 wherein the redirection probabilities and an initial distribution of the set of documents across the plurality of document servers are determined using a load distribution algorithm.

47. The apparatus of claim 46 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after the initial document distribution is complete.

48. The apparatus of claim 46 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.

49. The apparatus of claim 46 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.

50. The apparatus of claim 49 wherein the load balancing metric is the access rates of the documents.

51. The apparatus of claim 49 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.

52. The apparatus of claim 44 wherein the set of redirection probabilities arc recomputed after a change in conditions associated with the server system.

53. The apparatus of claim 52 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.

54. An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising:

a memory for storing a set of redirection probabilities; and

a processor operative to determine a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents;

to compute the set of redirection probabilities based on the distribution;

to receive a client request; and

to redirect the client request to one of the plurality of document servers based on the set of redirection probabilities.

55. A method of processing client requests received in a server system over a communication network, the method comprising the steps of:

determining a distribution of a set of documents over a plurality of servers of the server system based at least in part on access rates of at least a subset of the documents;

computing a set of redirection probabilities based on the distribution;

storing the set of redirection probabilities in a memory of the system;

receiving a client request; and

routing the client request to one of the plurality of document servers based on the set of redirection probabilities.

56. A method of processing client requests received in a server system over a communication network, the method comprising the steps of:

determining a distribution of a set of documents over a plurality of document servers based at least in part on access rates of at least a subset of the documents;

computing a set of redirection probabilities based on the distribution;

utilizing the distribution to compute a set of redirection probabilities; and

routing a client request to one of the plurality of document servers based on the set of redirection probabilities.

57. A method of processing client requests received in a server system over a communication network, the method comprising the steps of:

determining a distribution of a set of documents over a plurality of document servers of the server system based at least in part on access rates of at least a subset of the documents;

computing a set of redirection probabilities based on the distribution;

routing a client request from a redirection server of the server system to one of the plurality of document servers in the system based on the set of redirection probabilities; and

recomputing the redirection probabilities after a change in conditions associated with the server system.