Redundant data requests with cancellation

• US 9,197,695 B2
• Filed: 10/27/2014
• Issued: 11/24/2015
• Est. Priority Date: 11/02/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Dean, Jeffrey Adgate
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US14/525,072
• Publication Number:
  US 20150046525A1
• Time in Patent Office: 393 Days
• Field of Search: 709/203, 709/223, 709/226
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/5013 Request control
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A method of processing a request, performed by a respective server, is provided in which a request is received from a client. After receiving the request, a determination is made as to whether at least a first predefined number of other servers have a task-processing status for the request indicating that the other servers have undertaken performance of a task-processing operation for the request. When less than the first number of other servers in the set of other servers have the task-processing status for the request, a processing-status message is sent to one or more of the servers in the set of other servers indicating that the respective server is performing the task-processing operation. Upon completion of the task-processing, a result of the processing is sent to the client contingent upon a status of the other servers in the set of other servers.

Claims

1. A method of processing a client-initiated request, performed by a respective server system having one or more processors and memory storing one or more programs that when executed by the one or more processors cause the respective server system to perform the method, the method comprising:

receiving, from a client system, the client-initiated request;

after receiving the client-initiated request, determining whether at least a first predefined number of other server systems have a predefined task-processing status for the client-initiated request indicating that the other server systems have undertaken performance of a corresponding task-processing operation for the client-initiated request

in accordance with a determination that less than the first predefined number of other server systems in the set of other server systems have the predefined task-processing status for the client-initiated request;

sending a processing-status message to one or more of the server systems in the set of other server systems indicating that the respective server system has undertaken performance of the corresponding task-processing operation for the client-initiated request;

performing the corresponding task-processing operation;

upon completing the task-processing of the client-initiated request, sending a result of the task-processing to the client system contingent upon a processing status of other server systems in the set of other server systems for the client-initiated request.

2. The method of claim 1, wherein, upon completing the corresponding task-processing of the-client-initiated request, the method further comprises determining whether a second predefined number of the other server systems in the set of other server systems have undertaken responding to the client-initiated request, the second predefined number being equal to or less than the first predefined number, and forgoing sending the result of the processing to the client system when at least the second predefined number of other server systems have undertaken responding to the client-initiated request.

3. The method of claim 2, wherein the second predefined number and the first predefined number are determined in accordance with a factor selected from the group consisting of:

a redundancy requirement associated with the client-initiated request, a redundancy requirement associated with one or more other client requests, an efficiency requirement associated with the respective server system, and a user-adjustable parameter.

4. The method of claim 1, wherein the client-initiated request is a data retrieval operation or an information processing operation, and wherein the client-initiated request includes a respective request identifier that is used to determine whether another server system in the set of other server systems has undertaken performance of the respective task processing operation for the client-initiated request.

5. The method of claim 1, wherein the determination as to whether at least the first predefined number of the other server systems have a predefined task-processing status for the client-initiated request is based at least in part on whether a processing-status message has been received from another server system indicating that the other server system has undertaken performance of a task processing operation corresponding to the predefined task-processing status for the client-initiated request.

6. A server system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

receiving, from a client system, a request;

after receiving the request, determining whether at least a first predefined number of the other server systems in a set of other server systems have a predefined task-processing status for the request indicating that the other server systems have undertaken performance of the task-processing operation for the request;

in accordance with a determination that less than the first predefined number of the other server systems in the set of other server systems have the predefined task-processing status for the request;

sending a processing-status message to one or more of the other server systems in the set of other server systems indicating that the server system has undertaken performance of the task processing operation for the request; and

performing the task-processing operation;

upon completing the task-processing of the request, sending a result of the processing to the client system contingent upon a processing status of the other server systems in the set of other server systems for the request.

7. The server system of claim 6, wherein, upon completing the task-processing of the request, determining whether a second predefined number of the other server systems in the set of other server systems have undertaken responding to the request, the second predefined number being equal to or less than the first predefined number, and forgoing sending the result of the processing to the client system when at least the second predefined number of other server systems have undertaken responding to the request.

8. The server system of claim 7, wherein the second predefined number and the first predefined number are determined in accordance with a factor selected from the group consisting of:

a redundancy requirement associated with the respective request, a redundancy requirement associated with one or more other client requests, an efficiency requirement associated with the respective server system, and a user-adjustable parameter.

9. The server system of claim 6, wherein the request is a data retrieval operation or an information processing operation, and wherein the request includes a respective request identifier that is used to determine whether another server system has undertaken performance of the respective task processing operation for the request.

10. The server system of claim 6, wherein the determination as to whether at least the first predefined number of the other server systems have a predefined task-processing status for the request is based at least in part on whether a processing-status message has been received from another server system indicating that the other server system has undertaken performance of a task processing operation corresponding to the predefined task-processing status for the request.

11. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a server system with one or more processors, cause the server system to:

receive, from a client system, a request;

after receiving the request, determining whether at least a first predefined number of other server systems in a set of other server systems have a predefined task-processing status for the request indicating that the other server systems have undertaken performance of a corresponding task-processing operation for the request;

in accordance with a determination that less than the first predefined number of other server systems in the set of other server systems have the predefined task-processing status for the request;

send a processing-status message to one or more the other server systems in the set of other server systems indicating that the server system has undertaken performance of the corresponding task-processing operation for the request;

perform the corresponding task-processing operation; and

upon completing the task-processing of the respective request, send a result of the processing to the client system contingent upon a processing status of the other server systems in the set of other server systems for the request.

12. The non-transitory computer readable storage medium of claim 11, wherein, upon completing the corresponding task-processing of the request, performing a determination as to whether a second predefined number of the other server systems in the set of other server systems have undertaken responding to the request, the second predefined number being equal to or less than the first predefined number, and forgoing sending the result of the processing to the client system when at least the second predefined number of other server systems have undertaken responding to the request.

13. The non-transitory computer readable storage medium of claim 12, wherein the second predefined number and the first predefined number are determined in accordance with a factor selected from the group consisting of:

a redundancy requirement associated with the respective request, a redundancy requirement associated with one or more other client requests, an efficiency requirement associated with the respective server system, and a user-adjustable parameter.

14. The non-transitory computer readable storage medium of claim 11, wherein the request is a data retrieval operation or an information processing operation, and wherein the request includes a respective request identifier that is used to determine whether another server system has undertaken performance of the respective task processing operation for the request.

15. The non-transitory computer readable storage medium of claim 11, wherein the determination as to whether at least the first predefined number of the other server systems have a predefined task-processing status for the request is based at least in part on whether a processing-status message has been received from another server system indicating that the other server system has undertaken performance of a task processing operation corresponding to the task-processing status for the request.