Network architecture with load balancing, fault tolerance and distributed querying

• US 20060274761A1
• Filed: 12/20/2005
• Published: 12/07/2006
• Est. Priority Date: 06/06/2005
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Bailey, Michael Paul, Error, Christopher Reid
• Granted Patent: US 8,239,535 B2
• Time in Patent Office: Days
• US Class Current: 370/396
• 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 first front-end server having an input and output for receiving a request for data from the client device, the first front-end server dividing the request into a plurality of sub-requests;

a plurality of back-end servers each having an input and an output for communication for retrieving data from storage and capable of receiving and responding to a sub-request, the plurality of back-end servers coupled for communication with the first front-end server; and

a database having an input and output for storing information, the database coupled for communication with each of the plurality of back-end servers.

2. The system of claim 1, wherein the system further comprises a second front-end server having an input and output for receiving a request for data from the client device, the second front-end server dividing the request into a plurality of sub-requests, the second front-end server coupled for communication with 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 database stores website visitation data stored in a binary format.

5. The system of claim 1, wherein the 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 a slice of a data sets, each slice being a complete uncompromised segment of the data set that can be used to provide a statistically valid response to a query

7. The system of claim 1, wherein sub-request are distributed to one 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 the front-end server is capable of generating a response to the request so long as at least one of the plurality of back-end servers provides data in response to a sub-request.

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

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

retrieving a data set for the visitor from a database to a plurality of back-end servers;

notify the front-end server that the data set is loaded to the plurality of back-end servers;

running a query on the dataset;

receiving data from the back-end servers;

combining the data from the back-end severs; and

sending the combined data as the response to the query.

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

11. The method of claim 9, further comprising the steps of:

accessing the system by a visitor;

assigning the visitor a visitor identification number; and

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

12. The method of claim 11, 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.

13. The method of claim 9, wherein the step of retrieving the data set for the visitor includes:

dividing the request into slices;

retrieving the slices from the database; and

loading the slices to the plurality of back-end servers.

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 the data set corresponding to the visitor;

dividing the data set into a plurality of slices;

selecting a slice and sending a request for a back-end sever;

reporting load and availability for the plurality of back-end servers;

selecting the back-end sever with the lowest load; and

loads the selected slice from the database to the selected back-end server.

15. The method of claim 14 where in each slice is a complete uncompromised segment of the data set that can be used to provide a statistically valid response to a query.

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

17. The method of claim 14 wherein reporting 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.

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

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

20. The method of claim 14 wherein the confirmation message indicates the visitor identification number for the slice and percentage of the data set that the slice represents.

21. The method of claim 14 wherein some of steps are performed by a front-end server and wherein the process for loading data slices masterless and done in an anarchistic way.

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

receiving a query from a visitor received at a front-end server;

generating by front-end server a broadcast request to a plurality of back-end servers;

receiving the broadcast request at a first back-end server and determining whether the first back-end server holds data for the visitor;

perform the query on the portion of the data for the visitor held by the first back-end server; and

sending result data, the visitor identification number to the front-end server

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

24. The method of claim 22 wherein the step of sending result data includes sending a percentage of the entire data set that the result data represents.

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

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

if 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.

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

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

if 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.

27. The method of claim 24 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.