Cooperative fault tolerance and load balancing

• US 9,830,235 B1
• Filed: 09/16/2016
• Issued: 11/28/2017
• Est. Priority Date: 09/23/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tong, Darick, Anderson, Ryan D.
• Primary Examiner(s): Chea, Philip
• Assistant Examiner(s): Chen, Wuji
• Application Number:
  US15/267,435
• Time in Patent Office: 438 Days
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for cooperative fault tolerance and load balancing. In one aspect, a method includes receiving a request from an entity wherein the request includes metadata specifying a plurality of non-responsive servers to which the entity sent the request but that could not process the request; determining that the data processing apparatus is not a current home server for the entity based on information cached in the data processing apparatus, wherein the current home server is a server within a plurality of preferred servers that processes requests for the entity and, in response thereto: assigning the data processing apparatus as the current home server so that the entity will send subsequent requests to the data processing apparatus for processing; and sending a response to the entity.

Claims

1. A method implemented at a client device, comprising:

creating, at a client, requests on behalf of an entity;

for each request;

accessing, at the client, a homing cache storing an assignment list for the entity that specifies one or more servers for the entity;

determining, from the assignment list, the entity'"'"'s current home server;

sending the request to the current home server; and

determining whether there is failure of the current home server for the request;

for each request for which there is a determined failure of the current home server;

selecting, from the assignment list, a next listed server as the current home server for the entity;

attaching, to the request, metadata describing the prior current home server as a failed server; and

sending the request with the attached metadata to the current home server.

2. The method of claim 1, further comprising updating metadata stored at the user device that describes a list of failed server to include the prior current home server.

3. The method of claim 2, further comprising, for each request for which there is not a determined failure of the current home server:

receiving a response from the current home server;

if the response is not a redirect, updating a homing cache in the user device; and

if the response is a redirect, adding, at the user device, the current home server to a list of re-directing servers.

4. The method of claim 3, further comprising, if the response is a redirect, sending the request to the server specified by the redirect.

5. A client device, comprising:

a hardware processor; and

a non-transitory computer-readable medium coupled to the processor and having instructions stored thereon, which, when executed by the processor, cause the processor to perform operations comprising;

creating, at a client, requests on behalf of an entity;

for each request;

accessing, at the client, a homing cache storing an assignment list for the entity that specifies one or more servers for the entity;

determining, from the assignment list, the entity'"'"'s current home server;

sending the request to the current home server; and

determining whether there is failure of the current home server for the request;

for each request for which there is a determined failure of the current home server;

selecting, from the assignment list, a next listed server as the current home server for the entity;

attaching, to the request, metadata describing the prior current home server as a failed server; and

sending the request with the attached metadata to the current home server.

6. The client device of claim 5, the operations further comprising updating metadata stored at the user device that describes a list of failed server to include the prior current home server.

7. The client device of claim 6, the operations further comprising, for each request for which there is not a determined failure of the current home server:

receiving a response from the current home server;

if the response is not a redirect, updating a homing cache in the user device; and

if the response is a redirect, adding, at the user device, the current home server to a list of re-directing servers.

8. The client device of claim 7, the operations further comprising, if the response is a redirect, sending the request to the server specified by the redirect.

9. A non-transitory computer-readable medium having instructions stored thereon, which, when executed by a processor in a server, cause the processor to perform operations comprising:

creating, at a client, requests on behalf of an entity;

for each request;

accessing, at the client, a homing cache storing an assignment list for the entity that specifies one or more servers for the entity;

determining, from the assignment list, the entity'"'"'s current home server;

sending the request to the current home server; and

determining whether there is failure of the current home server for the request;

for each request for which there is a determined failure of the current home server;

selecting, from the assignment list, a next listed server as the current home server for the entity;

attaching, to the request, metadata describing the prior current home server as a failed server; and

sending the request with the attached metadata to the current home server.

10. The non-transitory computer-readable medium of claim 9, the operations further comprising updating metadata stored at the user device that describes a list of failed server to include the prior current home server.

11. The non-transitory computer-readable medium of claim 10, the operations further comprising, for each request for which there is not a determined failure of the current home server:

receiving a response from the current home server;

if the response is not a redirect, updating a homing cache in the user device; and

if the response is a redirect, adding, at the user device, the current home server to a list of re-directing servers.

12. The non-transitory computer-readable medium of claim 11, the operations further comprising, if the response is a redirect, sending the request to the server specified by the redirect.