Network architecture with load balancing, fault tolerance and distributed querying

• US 8,239,535 B2
• Filed: 12/20/2005
• Issued: 08/07/2012
• Est. Priority Date: 06/06/2005
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Error, Christopher Reid, Bailey, Michael Paul
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US11/313,589
• Publication Number:
  US 20060274761A1
• Time in Patent Office: 2,422 Days
• Field of Search: 709/224, 709/226
• US Class Current: 709/226
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0817 by checking functioning
• 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/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer

Abstract

A network architecture with load balancing, fault tolerance and distributed querying comprises a plurality of front-end servers, a plurality of back-end servers, and a database. The front-end servers are coupled to a network to receive data requests from client devices. The front-end servers are each coupled to the plurality of back-end servers. The front-end servers handle data requests at a macro level and divide the request into sub-requests that are sent to the plurality of back-end servers. The back-end servers are coupled to the database to retrieve data. Each data request is distributed across the plurality of back-end servers according to workload. The front-end servers are fault tolerant in that they can respond to a request for data without all of the back-end servers being responsive or providing data. The present invention also includes a plurality of methods including: a method for distributed querying, a method for loading data sets from a database, and a method for responding to a query that provides fault tolerance.

Claims

1. A system for responding to requests for data from a client device, the system comprising:

a front-end server configured to;

receive a request for data from a client;

identify a data set to be retrieved, wherein the identified data set comprises stored data that corresponds to the requested data;

identify a plurality of slices of data to be retrieved, wherein each identified slice of data to be retrieved comprises a complete uncompromised segment of the identified data set that can be used to provide a statistically valid response to the request for data such that the front-end server is capable of generating a statistically valid response to the request upon receiving data corresponding to less than all of the plurality of slices of data identified;

generate a plurality of sub-requests, wherein each of the plurality of sub-requests corresponds to an identified slice of data to be retrieved;

communicate the plurality of sub-requests to one or more of a plurality of back-end servers;

receive data corresponding to less than all of the plurality of slices of data identified; and

generate, in response to receiving data corresponding to less than all of the plurality of slices of data identified, a statistically valid response to the request for data, wherein to generate the statistically valid response, the front-end server is further configured to scale the data received to account for data that is not received;

wherein each respective back-end server is configured to;

receive one or more of the plurality of sub-requests from the first front-end server;

load, from a database, a portion of the stored data corresponding to the identified slice of data to be retrieved that corresponds to the one or more sub-requests received at the respective back-end server; and

transmit, to the front-end server, data corresponding to the identified slice of data loaded from the database; and

wherein the database comprises the stored data, wherein the database is configured to communicate, to each respective back-end server, a portion of the stored data corresponding to the identified slice of data to be retrieved that corresponds to the one or more sub-requests received at the respective back-end server.

2. The system of claim 1, wherein the system further comprises a second front-end server configured to:

receive a request for data from a client;

identify a data set to be retrieved, wherein the identified data set comprises stored data that corresponds to the requested data;

identify a plurality of slices of data to be retrieved, wherein each identified slice of data to be retrieved is a complete uncompromised segment of the identified data set to be retrieved;

generate a plurality of sub-requests, wherein each of the plurality of sub-requests corresponds to an identified slice of data to be retrieved; and

communicate the plurality of sub-requests to one or more of the plurality of back-end servers.

3. The system of claim 1, wherein the back-end servers filter the data in response to a filter request and based on criterion provided by the front-end servers.

4. The system of claim 1, wherein the stored data comprises website visitation data stored in a binary format.

5. The system of claim 4, wherein a binary format used to send the data to the client is encoded according to a hash algorithm so as to minimize bandwidth usage, the binary format is identical to the format used in database so that no file format translation need be performed when back-end servers extract data from the database.

6. The system of claim 1, wherein the back-end servers store and process the portion of the stored data received from the database.

7. The system of claim 1, wherein sub-request are distributed to one or more of the plurality of the back-end servers according to the load and availability of each of the plurality of the back-end servers.

8. The system of claim 1, wherein to generate the statistically valid response, the front-end server is further configured to determine statistical validity for the response depending on a size of the data set request for data comprises scaling the data received to account for data that is not received.

9. The system of claim 1, wherein to communicate the plurality of sub-requests to one or more of a plurality of back-end servers, the front-end server is further configured to:

communicate, to a first of the back-end servers, a first of the plurality of sub-requests corresponding to a first identified slice of data to be retrieved; and

communicate, to a second of the back-end servers, a second of the plurality of sub-requests corresponding to a second identified slice of data to be retrieved, wherein to receive the data corresponding to less than all of the plurality of slices of data identified, the front-end server is further configured to;

receive, from at least the first back-end server, a response comprising data corresponding to the first sub-request and the first identified slice of data to be retrieved; and

fail to receive, from at least the second back-end server, a response comprising data corresponding to the second sub-request and the second identified slice of data to be retrieved, and wherein to generate the statistically valid response to, the front-end server is further configured to;

scale the data of responses received to generate a statistically valid response based at least on the received response comprising data corresponding to the first sub-request and the first identified slice of data to be retrieved.

10. A method for accessing a web analytics system and responding to a query, the method comprising the steps of:

assigning a visitor to one of a plurality of front-end servers;

receiving a query for data from the visitor;

identifying a data set to be retrieved, wherein the identified data set comprises stored data that corresponds to the queried data;

identifying a plurality of slices of data to be retrieved, wherein each identified slice of data to be retrieved is a complete uncompromised segment of the identified data set that can be used to provide a statistically valid response to the query for data such that the front-end server is capable of generating a statistically valid response to the query upon receiving data corresponding to less than all of the plurality of slices of data identified;

generating a plurality of sub-requests, wherein each of the plurality of sub-requests corresponds to an identified slice of data to be retrieved;

communicating the plurality of sub-requests to one or more of a plurality of back-end servers;

wherein each respective back-end server is configured to;

receive one or more of the plurality of sub-requests from the first front-end server;

retrieve, from a database, a portion of the stored data corresponding to the identified slice of data to be retrieved that corresponds to the one or more sub-requests received at the respective back-end server; and

notify the front-end server that the portion of the stored data is loaded into the respective back-end server;

receiving, from the plurality of back-end servers, data corresponding to less than all of the plurality of slices of data identified;

generating, in response to receiving data corresponding to less than all of the plurality of slices of data identified, a statistically valid response to the request for data, wherein said generating the statistically valid response comprises scaling the data received to account for data that is not received; and

sending the statistically valid response as the response to the query.

11. The method of claim 10, wherein the step of assigning the visitor to one of the plurality of front-end servers is performed to load balance a plurality of visitors among the plurality of front-end servers.

12. The method of claim 10, wherein assigning the visitor to one of the plurality of front-end servers comprises the steps of:

receiving the query from the visitor;

assigning the visitor a visitor identification number; and

assigning the visitor to one of a plurality of front-end servers based on the visitor identification number assigned to the visitor.

13. The method of claim 12, wherein the step of assigning the visitor to one of a plurality of front-end servers assigns the visitor to a first front-end server if the visitor identification number is in a first group, and assigns the visitor to a second front-end server if the visitor identification number is from a second group.

14. A method for loading a data set from a database to a plurality of back-end servers, the method comprising the steps of:

identifying a data set to be retrieved corresponding to a visitor;

identifying a plurality of slices of data to be retrieved, wherein each identified slice of data to be retrieved is a complete uncompromised segment of the identified data set that can be used to provide a statistically valid response to a request for data such that a front-end server receiving data is capable of generating a statistically valid response to the request upon receiving data corresponding to less than all of the plurality of slices of data identified, and wherein a determination of statistical validity for the response depends on a size of the data set;

generating a request for a selected slice of the plurality of slices of data to be retrieved;

determining which of the plurality of back-end servers has the lowest load based on the load and availability for the plurality of back-end servers;

selecting a back-end sever determined to have the lowest load; and

sending the request to the selected back-end server.

15. The method of claim 14, wherein the step of sending the request to the selected back-end sever is performed by broadcasting a UDP broadcast message to available backend servers.

16. The method of claim 14, wherein determining which of the plurality of back-end servers has the lowest load based on the load and availability of the back-end server is a based on a factor from the group of:

a number of slices already being processed, a processing power/speed of the back-end server, a communication/connection speed available to the back-end server, and other processing characteristics.

17. The method of claim 14 wherein the step of selecting the back-end server selects the back-end server with the best availability.

18. The method of claim 14 further comprises the steps of sending a confirmation message indicating the data slice has been loaded into the back end server.

19. The method of claim 14, further comprising:

transmitting a confirmation message from the selected back-end server, the confirmation message indicating a visitor identification, number for the slice and percentage of the data set that the slice represents.

20. The method of claim 14 wherein some of steps are performed by a frontend server and wherein the process for loading data slices is masterless and is done in an anarchistic way.

21. A method for responding to a query for data from a client, the method comprising the steps of:

receiving at a front-end server a query from a visitor, the visitor corresponding to a data set;

identifying a data set to be retrieved, wherein the identified data set comprises stored data that corresponds to the data set corresponding to the visitor;

identifying a plurality of slices of data to be retrieved, wherein each identified slice of data to be retrieved is a complete uncompromised segment of the identified data set to be retrieved that can be used to provide a statistically valid response to the request for data such that the front-end server is capable of generating a statistically valid response to the request upon receiving data corresponding to less than all of the plurality of slices of data identified, and wherein a determination of statistical validity for the response depends on a size of the data set;

generating by the front-end server a broadcast request for at least one of the plurality of slices of data to be retrieved, the broadcast request being sent to a plurality of back-end servers including at least a first back-end server, the broadcast request including a visitor identification number assigned to the visitor;

where at least one of the back-end severs is configured to;

receive the broadcast request;

determine whether the back-end server holds at least one of the plurality of slices of data to be retrieved;

perform, responsive to determining that the back-end server holds a slice of data to be retrieved, at least a portion of the query on the back-end server to generate result data including the data to be retrieved held by the back-end server; and

send the result data in association with the visitor identification number to the front-end server.

22. The method of claim 21 wherein the broadcast request is sent to as many as possible of plurality of the back-end servers.

23. The method of claim 21 wherein the step of sending result data includes sending a percentage of the data set that the result data represents.

24. The method of claim 23 further comprising the steps of:

determining that the entire data set has been received by the front-end server;

upon determining that the entire data set has been received by the front end server;

combining responses from the plurality of back-end servers; and

sending the combined response to the client.

25. The method of claim 23 further comprising the steps of:

determining that less than the entire data set has been received by the front-end server;

upon determining that less than the entire data set has been received by the front end server;

combining responses from the plurality of back-end servers;

determining the percentage of the data set received, multiplying the data from the request by the inverse of the determined percentage; and

sending the multiplied data to the client.

26. The method of claim 23 further comprising the steps of comparing the determined percentage of the data set received to a threshold, and sending a message indicating there is not enough data for a statistically valid response to the visitor if the determined percentage is less than the threshold.