IP Library Granted Patent US 8,473,783
Granted Patent B2
US 8,473,783 · App. 12/942,326 · Granted Jun 25, 2013

Fault tolerance in distributed systems

Inventors: Henrique Andrade (Croton-on-Hudson, NY); Kirsten W. Hildrum (Hawthorne, NY); Michael J. E. Spicer (Lafayette, CA); Chitra Venkatramani (Roslyn Heights, NY); Rohit S. Wagle (Elmsford, NY)
Assignee: International Business Machines Corporation
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,473,783
App. No.
12/942,326
Granted
Jun 25, 2013
Kind
B2
Abstract

Fault tolerance is provided in a distributed system. The complexity of replicas and rollback requests are avoided; instead, a local failure in a component of a distributed system is tolerated. The local failure is tolerated by storing state related to a requested operation on the component, persisting that stored state in a data store, such as a relational database, asynchronously processing the operation request, and if a failure occurs, restarting the component using the stored state from the data store.

Claims (77)

1. A method of managing execution of operation requests to facilitate fault tolerance in a distributed system having a plurality of components, said method comprising:

receiving at one component of the distributed system an operation request to be processed, the one component executing on a processor;

processing, by the one component, the operation request, the processing including initiating one or more sub-operation requests to be performed by at least one other component of the distributed system;

storing at least an indication of the one or more sub-operation requests in an asynchronous work queue to be asynchronously processed by the at least one other component, the asynchronous work queue including one or more sub-operation requests for which processing is incomplete;

storing state related to the operation request in a persistent data store, said state including at least an indication of the one or more sub-operation requests on the asynchronous work queue; and

responsive to storing the state in the persistent data store and completing the operation request, asynchronously initiating execution of a sub-operation request of the one or more sub-operation requests on the asynchronous work queue.

2. The method of claim 1 , further comprising:

determining, by the one component, that it is being restarted;

performing recovery, by the one component, responsive to being restarted, said performing recovery comprising:

obtaining from the persistent data store the state including the at least an indication of the one or more sub-operation requests included on the asynchronous work queue; and

restoring the asynchronous work queue placing the one or more sub-operation requests back on the asynchronous work queue; and

resuming processing of the one component, said resuming processing comprising servicing one or more remote operation requests.

3. The method of claim 2 , further comprising:

determining by a remote component that the one component has failed; and

automatically retrying a requested operation to be performed by the one component one or more times.

4. The method of claim 1 , further comprising determining whether the operation request is a non-idempotent operation or an idempotent operation, and wherein based on the operation request being a non-idempotent operation, a transaction identifier associated with the operation request is to be used in determining whether the operation request has been previously processed to completion.

5. The method of claim 4 , wherein the non-idempotent operation is tied to a database transaction boundary in that data is persisted for the non-idempotent operation responsive to performing a transaction commit operation.

6. The method of claim 4 , further comprising:

determining whether the non-idempotent operation has previously been processed to completion, said determining checking a repository of complete transaction identifiers for the transaction identifier associated with the non-idempotent operation; and

processing the non-idempotent operation responsive to determining the non-idempotent operation has not been previously processed to completion.

7. The method of claim 1 , wherein the sub-operation request has a transaction identifier associated therewith, and said method further comprises storing results from the execution of the sub-operation request and the transaction identifier in a repository, responsive to executing the sub-operation request.

8. The method of claim 7 , further comprising deleting the sub-operation request from the asynchronous work queue responsive to completing execution of the sub-operation request.

9. The method of claim 1 , further comprising:

responsive to receiving the operation request, determining whether the operation request is a non-idempotent operation or an idempotent operation;

responsive to determining the operation request is a non-idempotent operation, using a transaction identifier associated with the non-idempotent operation to determine whether the non-idempotent operation has been previously processed to completion;

executing the non-idempotent operation, responsive to determining that the non-idempotent operation has not been previously processed to completion; and

retrieving results from a repository, responsive to determining that the non-idempotent operation has been previously processed to completion, wherein execution is not repeated.

10. The method of claim 9 , further comprising processing the idempotent operation, responsive to determining that the operation request is an idempotent operation, the processing being independent of transaction identifier use.

11. A computer system for managing execution of operation requests to facilitate fault tolerance in a distributed system having a plurality of components, said computer system comprising:

a memory; and

a processor in communications with the memory, wherein the computer system is configured to perform a method, the method comprising:

receiving at one component of the distributed system an operation request to be processed;

processing, by the one component, the operation request, the processing including initiating one or more sub-operation requests to be performed by at least one other component of the distributed system;

storing at least an indication of the one or more sub-operation requests in an asynchronous work queue to be asynchronously processed by the at least one other component, the asynchronous work queue including one or more sub-operation requests for which processing is incomplete;

storing state related to the operation request in a persistent data store, said state including at least an indication of the one or more sub-operation requests on the asynchronous work queue; and

responsive to storing the state in the persistent data store and completing the operation request, asynchronously initiating execution of a sub-operation request of the one or more sub-operation requests on the asynchronous work queue.

12. The computer system of claim 11 , wherein the method further comprises:

determining, by the one component, that it is being restarted;

performing recovery, by the one component, responsive to being restarted, said performing recovery comprising:

obtaining from the persistent data store the state including the at least an indication of the one or more sub-operation requests included on the asynchronous work queue; and

restoring the asynchronous work queue placing the one or more sub-operation requests back on the asynchronous work queue; and

resuming processing of the one component, said resuming processing comprising servicing one or more remote operation requests.

13. The computer system of claim 12 , wherein the method further comprises:

determining by a remote component that the one component has failed; and

automatically retrying a requested operation to be performed by the one component one or more times.

14. The computer system of claim 11 , wherein the sub-operation request has a transaction identifier associated therewith, and said method further comprises:

storing results from the execution of the sub-operation request and the transaction identifier in a repository, responsive to executing the sub-operation request; and

deleting the sub-operation request from the asynchronous work queue responsive to completing execution of the sub-operation request.

15. The computer system of claim 11 , wherein the method further comprises:

responsive to receiving the operation request, determining whether the operation request is a non-idempotent operation or an idempotent operation;

responsive to determining the operation request is a non-idempotent operation, using a transaction identifier associated with the non-idempotent operation to determine whether the non-idempotent operation has been previously processed to completion;

executing the non-idempotent operation, responsive to determining that the non-idempotent operation has not been previously processed to completion; and

retrieving results from a repository, responsive to determining that the non-idempotent operation has been previously processed to completion, wherein execution is not repeated.

16. A computer program product for managing execution of operation requests to facilitate fault tolerance in a distributed system having a plurality of components, the computer program product comprising:

a non-transitory computer readable storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:

receiving at one component of the distributed system an operation request to be processed;

processing, by the one component, the operation request, the processing including initiating one or more sub-operation requests to be performed by at least one other component of the distributed system;

storing at least an indication of the one or more sub-operation requests in an asynchronous work queue to be asynchronously processed by the at least one other component, the asynchronous work queue including one or more sub-operation requests for which processing is incomplete;

storing state related to the operation request in a persistent data store, said state including at least an indication of the one or more sub-operation requests on the asynchronous work queue; and

responsive to storing the state in the persistent data store and completing the operation request, asynchronously initiating execution of a sub-operation request of the one or more sub-operation requests on the asynchronous work queue.

17. The computer program product of claim 16 , wherein the method further comprises:

determining, by the one component, that it is being restarted;

performing recovery, by the one component, responsive to being restarted, said performing recovery comprising:

obtaining from the persistent data store the state including the at least an indication of the one or more sub-operation requests included on the asynchronous work queue; and

restoring the asynchronous work queue placing the one or more sub-operation requests back on the asynchronous work queue; and

resuming processing of the one component, said resuming processing comprising servicing one or more remote operation requests.

18. The computer program product of claim 17 , wherein the method further comprises:

determining by a remote component that the one component has failed; and

automatically retrying a requested operation to be performed by the one component one or more times.

19. The computer program product of claim 16 , wherein the sub-operation request has a transaction identifier associated therewith, and said method further comprises:

storing results from the execution of the sub-operation request and the transaction identifier in a repository, responsive to executing the sub-operation request; and

deleting the sub-operation request from the asynchronous work queue responsive to completing execution of the sub-operation request.

20. The computer program product of claim 16 , wherein the method further comprises:

responsive to receiving the operation request, determining whether the operation request is a non-idempotent operation or an idempotent operation;

responsive to determining the operation request is a non-idempotent operation, using a transaction identifier associated with the non-idempotent operation to determine whether the non-idempotent operation has been previously processed to completion;

executing the non-idempotent operation, responsive to determining that the non-idempotent operation has not been previously processed to completion; and

retrieving results from a repository, responsive to determining that the non-idempotent operation has been previously processed to completion, wherein execution is not repeated.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 9, 2010
From: ANDRADE, HENRIQUE; HILDRUM, KIRSTEN W.; SPICER, MICHAEL J.E.; VENKATRAMANI, CHITRA; WAGLE, ROHIT S.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 025416/0910 →
Continuity (1)
Related Publication 20120117423A1 · May 10, 2012