Cooperative fault tolerance and load balancing

• US 10,241,876 B1
• Filed: 10/27/2017
• Issued: 03/26/2019
• Est. Priority Date: 09/23/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Tong, Darick, Anderson, Ryan D.
• Primary Examiner(s): Chea, Philip J
• Assistant Examiner(s): Chen, Wuji
• Application Number:
  US15/796,444
• Time in Patent Office: 515 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 server device, comprising:

accessing, at the server, a homing cache specifying entities for which the server is a current home server;

identifying an entity specified in the homing cache for which the server is the current home sever but not a primary home server;

determining whether the primary home server is available;

in response to determining the primary home server is available;

sending, to the primary home server, a gravitation request that causes the primary home server, in response to receiving and processing the gravitation request, to assign itself as the current home server of the entity so that the entity will send subsequent requests to the primary home server; and

updating the homing cache to indicate the primary home server is the current home server of the entity; and

in response to determining the primary home server is not available, again determining whether the primary home server for the entity is available after a delay period;

wherein sending, to the primary home server, the gravitation request comprises;

determining a current load of the server;

determining a current load of the primary home server;

sending the gravitation request to the primary home sever only if the current load of the server is greater than the current load of the primary home server.

2. The method of claim 1, further comprising:

for each determination that the primary home server is not available, increasing the delay period from a current delay period value to a new delay period.

3. The method of claim 2, wherein increasing the delay period from to current delay period value to the new delay period comprises exponentially increasing the delay period.

4. A server 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;

accessing, at the server, a homing cache specifying entities for which the server is a current home server;

identifying an entity specified in the homing cache for which the server is the current home sever but not a primary home server;

determining whether the primary home server is available;

in response to determining the primary home server is available;

sending, to the primary home server, a gravitation request that causes the primary home server, in response to receiving and processing the gravitation request, to assign itself as the current home server of the entity so that the entity will send subsequent requests to the primary home server; and

updating the homing cache to indicate the primary home server is the current home server of the entity; and

in response to determining the primary home server is not available, again determining whether the primary home server for the entity is available after a delay period;

wherein sending, to the primary home server, the gravitation request comprises;

determining a current load of the server;

determining a current load of the primary home server;

sending the gravitation request to the primary home sever only if the current load of the server is greater than the current load of the primary home server.

5. The system of claim 4, the operations further comprising:

for each determination that the primary home server is not available, increasing the delay period from a current delay period value to a new delay period.

6. The system of claim 5, wherein increasing the delay period from to current delay period value to the new delay period comprises exponentially increasing the delay period.

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

accessing, at the server, a homing cache specifying entities for which the server is a current home server;

identifying an entity specified in the homing cache for which the server is the current home sever but not a primary home server;

determining whether the primary home server is available;

in response to determining the primary home server is available;

sending, to the primary home server, a gravitation request that causes the primary home server, in response to receiving and processing the gravitation request, to assign itself as the current home server of the entity so that the entity will send subsequent requests to the primary home server; and

updating the homing cache to indicate the primary home server is the current home server of the entity; and

in response to determining the primary home server is not available, again determining whether the primary home server for the entity is available after a delay period;

wherein sending, to the primary home server, the gravitation request comprises;

determining a current load of the server;

determining a current load of the primary home server;

sending the gravitation request to the primary home sever only if the current load of the server is greater than the current load of the primary home server.

8. The non-transitory computer-readable medium of claim 7, the operations further comprising:

for each determination that the primary home server is not available, increasing the delay period from a current delay period value to a new delay period.

9. The non-transitory computer-readable medium of claim 8, wherein increasing the delay period from to current delay period value to the new delay period comprises exponentially increasing the delay period.