Confined recovery in a distributed computing system

Patent metadata

Field	Value
Publication number	US-9727425-B1
Application number	US-201514703108-A
Country	US
Kind code	B1
Filing date	May 4, 2015
Priority date	Apr 20, 2011
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

Executing a confined recovery in a distributed system having a plurality of worker systems including a failed worker system at a current superstep. The confined recovery includes determining states of the partitions of the worker systems during the supersteps preceding the current superstep, and determining a recovery initiation superstep preceding the current superstep in which all messages for recovery initiation superstep are available. The recovery initiation superstep is determined responsive to determining the states of the partitions. Additionally, a recovery set of partitions is determined for which messages in supersteps after the recovery initiation superstep are not available. The worker systems having the partitions in the recovery set are instructed to execute the defined function for the partitions in the recovery set starting at the recovery initiation superstep to recover the lost exchanged messages.

First claim

What is claimed is:

1. A computer-implemented method for executing a confined recovery in a distributed computing system having a plurality of worker systems, the worker systems executing a computation in a plurality of supersteps, the worker systems having a plurality of partitions executing a defined function during the supersteps that exchange messages with partitions of other worker systems, the method comprising:
in response to a checkpoint criteria having been met at a particular superstep, transmitting a message to the worker systems to instruct them to save a current state of their assigned partitions to a persistent storage;
detecting a failed worker system, and in response:
determining, based on information stored in persistent storage, a previous superstep from which a recovery can be conducted and a recovery set of partitions that need to execute the defined function to recover from the failure;
assigning the recovery set of partitions to a recovery worker system and instructing the recovery worker system to execute the defined function;
instructing messaging worker systems with partitions not included in the recovery set to retrieve their outgoing messages sent to the failed worker system from the persistent storage and transmit them to the recovery worker system,
creating a group status message indicating whether each of the messaging worker systems succeeded in transmitting its outgoing messages, and
transmitting the group status message to each of the plurality of worker systems.

2. The method of claim 1 , further comprising:
receiving a plurality of status messages from the messaging worker systems, each status message indicating whether a messaging worker system succeeded in transmitting its outgoing messages.

3. The method of claim 1 , wherein the recovery worker system includes a proper subset of the plurality of worker systems.

4. The method of claim 1 , wherein the messaging worker systems include a proper subset of the plurality of worker systems.

5. The method of claim 1 , wherein determining previous superstep from which a recovery can be conducted includes identifying that messages for the previous superstep are available in persistent storage.

6. The method of claim 1 , wherein the recovery worker system includes at least one of the plurality of worker systems that has not failed.

7. The method of claim 1 , wherein instructing the messaging worker systems to transmit outgoing message to the recovery worker system includes instructing the messaging worker systems to transmit messages that are not available to the recovery worker system.

8. A non-transitory, computer-readable medium storing instructions operable when executed to cause at least one processor to perform operations for executing a confined recovery in a distributed computing system having a plurality of worker systems, the worker systems executing a computation in a plurality of supersteps, the worker systems having a plurality of partitions executing a defined function during the supersteps that exchange messages with partitions of other worker systems, the operations comprising:
in response to a checkpoint criteria having been met at a particular superstep, transmitting a message to the worker systems to instruct them to save a current state of their assigned partitions to a persistent storage;
detecting a failed worker system, and in response:
determining, based on information stored in persistent storage, a previous superstep from which a recovery can be conducted and a recovery set of partitions that need to execute the defined function to recover from the failure;
assigning the recovery set of partitions to a recovery worker system and instructing the recovery worker system to execute the defined function;
instructing messaging worker systems with partitions not included in the recovery set to retrieve their outgoing messages sent to the failed worker system from the persistent storage and transmit them to the recovery worker system;
creating a group status message indicating whether each of the messaging worker systems succeeded in transmitting its outgoing messages; and
transmitting the group status message to each of the plurality of worker systems.

9. The computer-readable medium of claim 8 , the operations further comprising:
receiving a plurality of status messages from the messaging worker systems, each status message indicating whether a messaging worker system succeeded in transmitting its outgoing messages.

10. The computer-readable medium of claim 8 , wherein the recovery worker system includes a proper subset of the plurality of worker systems.

11. The computer-readable medium of claim 8 , wherein the messaging worker systems include a proper subset of the plurality of worker systems.

12. The computer-readable medium of claim 8 , wherein determining previous superstep from which a recovery can be conducted includes identifying that messages for the previous superstep are available in persistent storage.

13. The computer-readable medium of claim 8 , wherein the recovery worker system includes at least one of the plurality of worker systems that has not failed.

14. The computer-readable medium of claim 8 , wherein instructing the messaging worker systems to transmit outgoing message to the recovery worker system includes instructing the messaging worker systems to transmit messages that are not available to the recovery worker system.

15. A system for executing a confined recovery in a distributed computing system having a plurality of worker systems, the worker systems executing a computation in a plurality of supersteps, the worker systems having a plurality of partitions executing a defined function during the supersteps that exchange messages with partitions of other worker systems, the system comprising:
memory for storing data; and
one or more processors operable to perform operations comprising:
in response to a checkpoint criteria having been met at a particular superstep, transmitting a message to the worker systems to instruct them to save a current state of their assigned partitions to a persistent storage;
detecting a failed worker system, and in response:
determining, based on information stored in persistent storage, a previous superstep from which a recovery can be conducted and a recovery set of partitions that need to execute the defined function to recover from the failure;
assigning the recovery set of partitions to a recovery worker system and instructing the recovery worker system to execute the defined function;
instructing messaging worker systems with partitions not included in the recovery set to retrieve their outgoing messages sent to the failed worker system from the persistent storage and transmit them to the recovery worker system;
creating a group status message indicating whether each of the messaging worker systems succeeded in transmitting its outgoing messages; and
transmitting the group status message to each of the plurality of worker systems.

16. The system of claim 15 , the operations further comprising:
receiving a plurality of status messages from the messaging worker systems, each status message indicating whether a messaging worker system succeeded in transmitting its outgoing messages.

17. The system of claim 15 , wherein the recovery worker system includes a proper subset of the plurality of worker systems.

18. The system of claim 15 , wherein the messaging worker systems include a proper subset of the plurality of worker systems.

19. The system of claim 15

Assignees

• Google Inc

Inventors

• Malewicz Grzegorz
• Austern Matthew H
• Dehnert James C
• Bik Aart J C
• Czajkowski Grzegorz

Classifications

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F11/1464

  for networked environments · CPC title