Redundant Data Requests with Cancellation

• US 20130110909A1
• Filed: 06/15/2012
• Published: 05/02/2013
• Est. Priority Date: 11/02/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Jeffrey A. Dean
• Inventors: Dean, Jeffrey A.
• Granted Patent: US 8,874,643 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• 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 for processing a client-initiated request by: receiving from a client a request including server identifiers for one or more other servers; determining whether at least a first predefined number of the other servers have a predefined task-processing status for the request; in accordance with a determination that less than the first predefined number of the other servers have the predefined task-processing status for the request: sending a processing-status message to one or more the other servers indicating that the respective server has undertaken performance of the respective task-processing operation for the request; performing the respective task-processing operation; upon completing processing of the request: determining whether a second predefined number of the other servers have undertaken responding to the request; in accordance with a determination that at least the second predefined number of the other servers have undertaken responding to the request, foregoing sending a result to the client.

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, a respective request including server identifiers for one or more other server systems distinct from the respective server system;

after receiving the respective request, determining whether at least a first predefined number of the other server systems have a predefined task-processing status for the respective request;

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

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

performing the respective task-processing operation;

upon completing processing of the respective request;

determining whether a second predefined number of the other server systems have undertaken responding to the respective request; and

in accordance with a determination that at least the second predefined number of the other server systems have undertaken responding to the respective request,

foregoing sending a result of the processing to the client system.

2. The method of claim 1, wherein the second predefined number is equal to or less than the first predefined number.

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

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

4. The method of claim 1, wherein the respective request includes a request selected from the group consisting of:

a data retrieval request, and an information processing request; and

wherein the respective 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 respective 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 respective request is based at least in part on

whether a processing-status message has been received from another server systems indicating that the other server system has undertaken performance of a task-processing operation corresponding to the predefined task-processing status for the respective request.

6. The method of claim 1, further comprising:

storing a queue of requests to be processed at the respective server system, wherein;

the task-scheduling action includes a queue-management action related to placing the respective request in the queue or processing the respective request after it has been placed in the queue; and

the task-scheduling policy includes a queue-management policy.

7. The method of claim 6, wherein the determination as to whether at least the first predefined number of other server systems have a predefined task-processing status for the respective request is performed:

before or after placing the respective request in the queue, or both.

8. The method of claim 6, wherein the queue-management action includes an action selected from the group consisting of:

foregoing placing the respective request in the queue;

lowering a respective priority of the respective request in the queue; and

removing the respective request from the queue.

9. 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 respective request including server identifiers for one or more other server systems distinct from the server system;

after receiving the respective request, determining whether at least a first predefined number of the other server systems have a predefined task-processing status for the respective request;

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

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

performing the respective task-processing operation;

upon completing processing of the respective request;

determining whether a second predefined number of the other server systems have undertaken responding to the respective request; and

in accordance with a determination that at least the second predefined number of the other server systems have undertaken responding to the respective request, foregoing sending a result of the processing to the client system.

10. The system of claim 9, wherein the second predefined number is equal to or less than the first predefined number.

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

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

12. The system of claim 9, wherein the respective request includes a request selected from the group consisting of:

a data retrieval request, and an information processing request; and

wherein the respective 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 respective request.

13. The system of claim 9, 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 respective request is based at least in part on whether a processing-status message has been received from another server systems indicating that the other server system has undertaken performance of a task-processing operation corresponding to the predefined task-processing status for the respective request.

14. The system of claim 9, wherein the one or more programs further comprising instructions for:

storing a queue of requests to be processed at the server system, wherein;

the task-scheduling action includes a queue-management action related to placing the respective request in the queue or processing the respective request after it has been placed in the queue; and

the task-scheduling policy includes a queue-management policy.

15. The system of claim 13, wherein the determination as to whether at least the first predefined number of other server systems have a predefined task-processing status for the respective request is performed:

before or after placing the respective request in the queue, or both.

16. The system of claim 13, wherein the queue-management action includes an action selected from the group consisting of:

foregoing placing the respective request in the queue;

lowering a respective priority of the respective request in the queue; and

removing the respective request from the queue.

17. 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 respective request including server identifiers for one or more other server systems distinct from the respective server system;

after receiving the respective request, determining whether at least a first predefined number of the other server systems have a predefined task-processing status for the respective request;

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

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

perform the respective task-processing operation;

upon completing processing of the respective request;

determine whether a second predefined number of the other server systems have undertaken responding to the respective request; and

in accordance with a determination that at least the second predefined number of the other server systems have undertaken responding to the respective request, forego sending a result of the processing to the client system.

18. The non-transitory computer readable storage medium of claim 17, wherein the second predefined number is equal to or less than the first predefined number.

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

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

20. The non-transitory computer readable storage medium of claim 17, wherein the respective request includes a request selected from the group consisting of:

a data retrieval request, and an information processing request; and

wherein the respective 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 respective request.

21. The non-transitory computer readable storage medium of claim 17, 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 respective request is based at least in part on whether a processing-status message has been received from another server systems indicating that the other server system has undertaken performance of a task-processing operation corresponding to the predefined task-processing status for the respective request.

22. The non-transitory computer readable storage medium of claim 17, wherein the one or more programs further comprising instructions for:

storing a queue of requests to be processed at the server system, wherein;

the task-scheduling action includes a queue-management action related to placing the respective request in the queue or processing the respective request after it has been placed in the queue; and

the task-scheduling policy includes a queue-management policy.

23. The non-transitory computer readable storage medium of claim 22, wherein the determination as to whether at least the first predefined number of other server systems have a predefined task-processing status for the respective request is performed:

before or after placing the respective request in the queue, or both.

24. The non-transitory computer readable storage medium of claim 22, wherein the queue-management action includes an action selected from the group consisting of:

foregoing placing the respective request in the queue;

lowering a respective priority of the respective request in the queue; and

removing the respective request from the queue.