Data distribution techniques for load-balanced fault-tolerant web access
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
57 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
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. - View Dependent Claims (45, 46, 47, 48, 49, 50, 51, 52, 53)
-
-
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.
-
Specification