计算不确定性情况下的恢复和容错

摘要

一种用于提升包括至少一个处理节点的计算系统中容错和恢复的方法，包括：通过在第一处理节点处提升第一处理节点的可用性和恢复，使用被分配第一代指示符的派生器产生第一派生进程，使得其派生进程继承第一代指示符，开始检查点间隔以产生节点恢复信息，使得派生器暂停产生派生进程，向派生器分配与第一代指示符不同的第二代指示符，恢复执行派生器，使得其产生继承第二代指示符的第二派生进程，控制第二派生进程写入存储器的程度；以及在将检查点期间获得的节点恢复信息提交给持久性存储装置之后，释放对第二派生进程可写入存储器的程度的控制。

权利要求

1.一种用于提升包括至少一个处理节点的计算系统中容错和恢复的方法，所述方法包括：提升第一处理节点的可用性和恢复，其中提升可用性和恢复包括：在第一处理节点处，在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符，其中所述第一派生进程继承所述第一代指示符；

开始检查点间隔，在所述检查点间隔结束时，将能够用于恢复所述节点的节点恢复信息提交到持久性存储装置，其中开始所述检查点间隔包括：使得所述派生器暂停产生派生进程，

向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及

在提交所述节点恢复信息之后，释放对所述第二派生进程能够写入存储器的所述程度的控制。

2.根据权利要求1所述的方法，其中控制所述第二派生进程写入存储器的程度包括：阻止所述第二派生进程完成对所述存储器的写入。

3.根据权利要求2所述的方法，还包括：在提交所述恢复信息之后，允许所述第二派生进程将所述写入排队到所述存储器，用于最终完成所述写入。

4.根据权利要求1所述的方法，其中控制所述第二派生进程写入存储器的程度包括：确定所述写入操作是可交换操作，并且允许完成所述可交换操作。

5.根据权利要求4所述的方法，其中确定所述写入操作是可交换操作包括：确定所述写入操作包括增加一变量。

6.根据权利要求4所述的方法，其中确定所述写入操作是可交换操作包括：确定所述写入操作包括在指定位置插入一记录。

7.根据权利要求1所述的方法，还包括：在暂停所述派生器之后设置截止期限，从而为具有所述第一代指示符的任何派生进程提供时间来执行到完成，并且避免不得不保存具有所述第一代指示符的所述派生进程的状态所产生的开销。

8.根据权利要求7所述的方法，还包括：如果所述第一派生进程在所述截止期限之前仍然执行，则暂停所述第一派生进程。

9.根据权利要求7所述的方法，还包括：使得所述第一派生进程能够避免由于在所述截止期限之前未能完成执行而暂停。

10.根据权利要求9所述的方法，其中使得所述第一派生进程能够避免由于在所述截止期限之前未能完成执行而暂停包括：如果所述第一派生进程在所述截止期限前仍在执行，则将所述第一派生进程中的所述第一代指示符改变为所述第二代指示符。

11.根据权利要求1所述的方法，其中所述第一处理节点具有节点代指示符，所述方法还包括使得派生进程成为迁移到第二节点的迁移进程，其中所述第二节点具有节点代指示符。

12.根据权利要求11所述的方法，其中所述第二节点的所述节点代指示符指示所述第二节点处于比所述第一处理节点更年轻的一代中，其中所述方法还包括使得所述迁移进程年轻化。

13.根据权利要求12所述的方法，其中，使得所述迁移进程年轻化包括：所述迁移进程的移入侧年轻化。

14.根据权利要求12所述的方法，其中，使得所述迁移进程年轻化包括：所述迁移进程的移出侧年轻化。

15.根据权利要求1所述的方法，其中所述第一处理节点是多节点系统中的节点，其中每个节点均具有节点代计数，其中所述多节点系统包括至少一个第二节点，其中，在所述第二节点的故障恢复之后，所述第一处理节点向后滚动到对应于所述第二节点的节点代计数的状态。

16.根据权利要求1所述的方法，其中所述第一处理节点是多节点系统中的节点，其中每个节点均具有节点代计数，其中所述多节点系统包括至少一个第二节点，其中，在所述第一处理节点的故障恢复之后，所述第一处理节点通过从检查点恢复提交的工作并从日志恢复未提交的工作，从而向前滚动到与所述第二节点的节点代计数相对应的状态。

17.根据权利要求1所述的方法，其中所述第一处理节点是多节点系统中的节点，其中每个节点均具有节点代计数，所述方法包括：在所述第一处理节点处，从主节点接收指示将要执行检查点的消息，

作为响应，年轻化所述第一处理节点的节点代计数，

使得派生器暂停产生派生进程，

保存用于恢复派生器状态的派生器恢复信息，

继续执行所述派生器，

确定在所述第一处理节点处不再期待有其它较老一代的移入，以及响应于所述确定，向所述持久性存储装置提交所述节点恢复信息。

18.根据权利要求17所述的方法，还包括：设定截止期限，以及在所述截止期限过去之后，暂停仍然在执行的所有较老一代的派生进程，同时较年轻一代的派生进程继续执行。

19.根据权利要求1所述的方法，其中所述第一处理节点是多节点系统中的节点，所述方法包括：在第二节点处保存所述第一处理节点的工作存储器的副本，当所述第一处理节点故障时，暂时地使用所述副本用于本来将由所述第一处理节点执行的处理，以及在所述第一处理节点恢复时，向所述第一处理节点传送更新所述第一处理节点中的存储器所需的信息，使得能够由所述第一处理节点执行后续计算。

20.一种非暂态计算机可读存储介质，存储计算机程序，用于提升包括至少一个处理节点的计算系统中的容错和恢复，所述计算机程序包括用于使得计算系统执行下述步骤的指令：提升第一处理节点的可用性和恢复，其中提升可用性和恢复包括：在第一处理节点处，在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符，其中所述第一派生进程继承所述第一代指示符；

开始检查点间隔，在所述检查点间隔结束时，将能够用于恢复所述节点的节点恢复信息提交到持久性存储装置，其中开始所述检查点间隔包括：使得所述派生器暂停产生派生进程，

向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及

在提交所述节点恢复信息之后，释放对所述第二派生进程能够写入存储器的所述程度的控制。

21.一种计算系统，包括：

数据存储系统，包括持久性存储装置；以及

一个或多个处理节点，包括至少一个处理器，所述至少一个处理器被配置为：提升第一处理节点的可用性和恢复，其中提升可用性和恢复包括：在第一处理节点处，

在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符，其中所述第一派生进程继承所述第一代指示符；

开始检查点间隔，在所述检查点间隔结束时，将能够用于恢复所述节点的节点恢复信息提交到持久性存储装置，其中开始所述检查点间隔包括：使得所述派生器暂停产生派生进程，

向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及

在提交所述节点恢复信息之后，释放对所述第二派生进程能够写入存储器的所述程度的控制。

说明书

计算不确定性情况下的恢复和容错

[0001] 相关申请的交叉引用

[0002] 本申请要求序列号为第62/065,941号美国申请的2014年10月20日优先权日期的权益，该申请的内容通过引用合并于此。

背景技术

[0003] 本说明书涉及在存在计算不确定性情况下的恢复和容错。

[0004] 由于各种原因，计算系统有时会故障。当这样的系统故障时，数据可能会丢失。最好采取措施来防止或至少最小化这种数据丢失。

[0005] 这些措施的示例包括数据库中的ACID(原子性、一致性、直到提交的隔离性、提交时的持久性)事务。这些已知的措施是非常有鲁棒性的。它们可以满足非常高的正确性标准，同时也是容错的。

[0006] 然而，所有的这种鲁棒性都是有代价的。用于防止故障的已知方法具有高延迟时间，并且有时会导致很长时间装置不可用。因此，对于大容量的事务来说，这些方法不太适合。

[0007] 另外，一些已知方法需要确定性计算。在确定性计算中，执行任务的顺序是固定的，并且计算的结果在每次执行时保持不变。不清楚这些已知方法如何适应于有效处理非确定性计算环境。

[0008] 当计算装置包括彼此协作的多个处理节点时，产生额外的复杂性。在这种装置中，装置的一个节点可能故障，而其它节点可以继续工作。当故障的节点恢复时，这不能保证该故障节点本身已经恢复到其它节点期望其所处状态的状态。

发明内容

[0009] 在一个方案中，本发明特征在于一种用于提升包括至少一个处理节点的计算系统中容错和恢复的方法。这种方法包括：提升第一处理节点的可用性和恢复，其中提升可用性和恢复包括，在第一处理节点处，在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符(generation indicator)，其中所述第一派生进程继承所述第一代指示符；开始检查点间隔，在该检查点间隔结束时，可用于恢复所述节点的节点恢复信息被提交到持久性存储装置，其中开始所述检查点间隔包括使得所述派生器暂停产生派生进程，向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及在提交所述节点恢复信息之后，释放对所述第二派生进程可写入存储器的所述程度的控制。

[0010] 在一些实践中，控制所述第二派生进程写入存储器的程度包括阻止所述第二派生进程完成对所述存储器的写入。在这些实践中，还包括在提交恢复信息之后，允许第二个派生进程将写入排队到存储器，用于其最终完成。

[0011] 在其它实践中，控制第二派生进程写入存储器的程度包括确定所述写入操作是可交换操作，并且允许完成所述可交换操作。在这些实践中，确定所述写入操作是可交换操作包括确定所述写入操作包括增加变量，并且确定所述写入操作是可交换操作包括确定所述写入操作包括在指定位置插入记录。

[0012] 在本发明的实践中，还包括在暂停所述派生器之后设置截止期限，从而为具有所述第一任务代指示符的任何派生进程提供时间来执行完成，并且避免与不得不保存具有所述第一代指示符的所述派生进程的状态相关联的开销。在这些实践中，还包括如果所述第一派生进程在所述截止期限之前仍然执行，则暂停所述第一派生进程，还包括使所述第一派生进程能够避免由于在所述截止期限之前未能完成执行而暂停，例如如果所述第一派生进程在所述截止期限前仍在执行，则在所述第一派生进程中将所述第一任务代指示符改变为所述第二任务代指示符。

[0013] 在第一节点具有节点代指示符，本发明的额外实践包括使得派生进程成为迁移到第二节点的迁移进程，其中所述第二节点具有节点代指示符。在这些实践中，所述第二节点的所述节点代计数指示所述第二节点处于比所述第一节点更年轻的一代中，在这种情况下，所述方法还包括使所述迁移进程年轻化，要么移入侧年轻化所述迁移进程，要么移出侧年轻化所述迁移进程。

[0014] 在一些情形下，所述第一节点是多节点系统中的节点，其中每个节点均具有节点代计数，并且所述多节点系统包括至少一个第二节点。这些情形下，本发明中具有一些实践，在所述第二节点的故障恢复之后，所述第一节点向后滚动到对应于所述第二节点的节点代计数的状态。

[0015] 在其它情形下，其中所述第一节点是多节点系统中的节点，其中每个节点均具有节点代计数，并且所述多节点系统包括至少一个第二节点。这些情形下，本发明中具有一些实践，在所述第一节点的故障恢复之后，所述第一节点通过从检查点恢复提交的工作并从日志恢复未提交的工作，向前滚动到与所述第二节点的节点代计数相对应的状态。

[0016] 在这些情形下，所述第一节点是多节点系统中的节点，其中每个节点均具有节点代计数，本发明的实践包括第一节点实施一些动作的实践。这些包括从主节点接收指示将要执行检查点的消息，作为响应，年轻化所述第一节点的节点代计数，使得派生器暂停产生派生进程，保存派生器恢复信息，以恢复派生器状态，继续执行所述派生器，确定在所述第一节点处不再期待有其它较老一代的移入，并且响应于所述确定，向所述持久性存储装置提交所述节点恢复信息。在这些实践中，还包括设定截止期限，并且在所述截止期限过去之后，暂停仍然在执行的所有较老一代的派生进程，同时较年轻一代的派生进程继续执行。

[0017] 在一些情形下，所述第一节点是多节点系统中的节点。在这种情形下，本发明的替代实践包括在所述第二节点处保存所述第一节点的工作存储器的副本，当所述第一节点故障时，暂时地使用所述副本用于本来将由所述第一节点执行的处理，并且在所述第一节点恢复时，向所述第一节点传送更新所述第一节点中的存储器所需的信息，以便可以由所述第一节点执行后续计算。

[0018] 在另一个方案中，本发明特征是一种以非暂态形式存储在计算机可读存储介质上的软件，当执行时，提升包括至少一个处理节点的计算系统中的容错和恢复。所述软件包括用于使计算系统执行下述步骤的指令：提升第一处理节点的可用性和恢复，其中提升可用性和恢复包括，在第一处理节点处，在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符，其中所述第一派生进程继承所述第一代指示符；开始检查点间隔，在该检查点间隔结束时，可用于恢复所述节点的节点恢复信息被提交到持久性存储装置，其中开始所述检查点间隔包括使得所述派生器暂停产生派生进程，向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及在提交所述节点恢复信息之后，释放对所述第二派生进程可写入存储器的所述程度的控制。

[0019] 在又一种方案中，本发明特征是一种数据存储系统，包括持久性存储装置；以及一个或多个处理节点，包括被配置为提升第一处理节点的容错和恢复，其中提升可用性和恢复包括，在第一处理节点处，在所述节点处执行派生器，其中所述派生器在执行过程中产生第一派生进程，其中执行所述派生器包括向所述派生器分配第一代指示符，其中所述第一派生进程继承所述第一代指示符；开始检查点间隔，在该检查点间隔结束时，可用于恢复所述节点的节点恢复信息被提交到持久性存储装置，其中开始所述检查点间隔包括使得所述派生器暂停产生派生进程，向所述派生器分配与所述第一代指示符不同的第二代指示符，继续执行所述派生器，从而使得所述派生器产生第二派生进程，其中所述第二派生进程继承所述第二代指示符，以及控制所述第二派生进程写入存储器的程度；以及在提交所述节点恢复信息之后，释放对所述第二派生进程可写入存储器的所述程度的控制。

[0020] 方案可以具有以下一个或多个优点。

[0021] 本文描述的用于提升容错和恢复的技术使得计算系统能够保持高可用性。通过战略性地放松某些ACID约束，计算系统仍然可以提供可恢复性，但是无需更多极端措施的高开销。因此，有更多的计算资源可用于有用的工作。此外，通过控制派生进程(例如，操作系统进程或线程)写入存储器的程度，仍然可以在检查点间隔期间实现有用的工作，同时确保保持容错机制的完整性。因此，这些技术在发生故障的情况下和正常的无故障运行期间都能增强计算系统的内部功能。

附图说明

[0022] 图1示出在存在计算不确定性的情况下用于实施我们的容错和恢复的单节点计算装置；

[0023] 图2示出在图1的节点操作期间遇到的检查点间隔和工作间隔；

[0024] 图3示出在图2的检查点间隔期间允许将派生运行到完成的方法；

[0025] 图4示出派生器进程可以在图2的检查点间隔期间继续产生派生进程的方法；

[0026] 图5示出一种方法，其中在检查点间隔期间派生进程可以通过将写入排队到存储器来继续工作；

[0027] 图6示出了多节点计算装置；

[0028] 图7示出了来自图7的装置的节点中共存的两代；

[0029] 图8示出了响应于检查点消息由从属节点执行的方法步骤；

[0030] 图9示出了涉及增加迁移代计数的方法步骤；

[0031] 图10示出了故障后用于恢复的方法步骤；

[0032] 图11示出了在另一个节点处维护的副本，以使得能够更快速地恢复；

[0033] 图12示出了使用图11所示的副本，用于快速恢复的过程；以及

[0034] 图13示出了关于图9所示的多节点，执行图5所示方法的示例。

具体实施方式

[0035] 图1示出一种数据处理系统的示例，其中可以在存在计算不确定性情形下使用用于容错和恢复的技术。数据处理系统包括单节点计算装置8，其具有包括工作存储器12的节点10。在该节点10上运行的进程14使用该工作存储器12，来保存它们相应的进程状态并且存储它们相应计算的中间结果。在不同的实施例中，进程14可以被实现为在节点10上运行的操作系统内的多种计算资源中的任何一个。例如，进程14可以被实现为具有它们自己的地址空间的操作系统“进程”，或者实现为具有它们自己的执行上下文(例如，阶段、寄存器等)的操作系统“线程”，或者实现为一些其它类型的“任务”，该“任务”包括要执行的一系列操作、但不一定具有专用于它的特定操作系统进程或线程。

[0036] 由于工作存储器12通常是易失性的，所以将其状态周期性地保存在存储在持久性存储装置16中的检查点文件18中是明智的。在节点10的操作中断的情况下，这些检查点文件18可以用于恢复状态信息。

[0037] 在节点上运行的进程14中的有些进程是派生器(spawner)20。“派生器”是一种类型的进程，其属性之一为具有产生一个或多个其它进程的能力。由派生器产生的进程在本文中被称为“派生进程(spawn)”(以单数和复数形式)。由动词“派生(to spawn)”的适当变形来指称产生这种派生进程的动作。图1示出已经产生派生进程22A、22B的派生器20。派生器20通常是一个长生存期的进程，而派生进程22A、22B虽然有很多，但生存期往往要短得多。在某些情况下，派生器是一个比该派生器派生的派生进程生存期更长的进程。派生进程22A、22B也相互独立和异步，使得派生进程22A、22B已经完成其计算的程度与派生器20起初产生派生进程22A、22B的时间无关。结果是，派生进程22A、22B执行计算的顺序是不确定的。
由于执行计算的顺序通常会影响结果，所以这使计算整体不确定。

[0038] 计算装置8在其操作过程中与外界通信。例如，计算装置8可以接收一个或多个传入消息流24并且产生一个或多个传出消息流28。如下面将更详细描述的，这些消息24、28由装置8临时存储在持久性存储装置16内。这些消息24、28可以临时存储在物理和/或逻辑上分开的相应区域内，由其托管(escrow)。传入消息24可以存储在持久性存储装置16中的传入消息托管区域26中，并且传出消息28可以存储在持久性存储装置16中的传出消息托管区域30中。

[0039] 参考图2，由检查点间隔32和工作间隔34来标记节点的操作。在工作间隔34期间，节点执行有用的工作，同时进程向完成推进。在检查点间隔32期间，节点10暂停所有进程，对它们进行序列化，并且将结果保存到持久性存储装置16中。然后，节点10将工作存储器中的任何其它内容保存到持久性存储装置16中。此时，检查点被认为是已经被“提交”了，进程14被认为是已经“经过检查点”了。

[0040] 优选地，检查点间隔32比工作间隔34短得多。本文所述的装置和方法旨在通过减小检查点间隔32的长度来增加可在工作间隔34中执行的处理量。

[0041] 一旦提交了检查点，则节点10就允许进程14继续并且释放传出消息托管区域30中的传出消息28。

[0042] 将传出消息28存储在传出消息托管区域30中而不是立即发送它们是有用的，用于防止可能由于节点10的故障而导致的不一致。例如，进程14很可能发送传出消息28，来通知一些计算结果。如果在该消息28已被发送之后但是在计算结果被提交给持久性存储装置16之前，节点10故障，则节点10将重新启动并且重新执行未提交的计算。一旦完成，将发送另一消息28，来通知该第二次计算的结果。如果两个结果不同(在非确定性计算的情况下是可能的)，则其中一个消息将是无效的。

[0043] 作为具体的示例，考虑进程14基于随机数发生器的结果向客户授予奖励的情况。如果不存在传出消息托管区域30，则进程14将向第一个客户发送消息28，宣布奖励即将到来。然后，节点10崩溃并重新启动。由于进程14的状态从未被保存，所以没有该客户被授予任何奖励的记录，或者没有进程14已成功完成执行的记录。然后节点10可以重新执行进程
14，进而进程14将产生不同的随机数，从而导致第二消息28被发送给另一个客户，宣布奖励即将到来。这将需要要么颁发两个奖励而其中只有一个是本打算颁发的，要么应对至少一个失望的客户。

[0044] 为了在故障之后进行恢复，节点10从持久性存储装置16检索所有进程14的状态和工作存储器12的状态。然后，它重传存储在传出消息托管区域30中的任何传出消息28，检索传入消息托管区域16中的传入消息用于处理，然后继续对实时数据的正常操作。

[0045] 传出消息托管区域30中所有消息28的重传可能导致接收者接收相同重复的消息。在一个实施例中，接收者被配置为忽略重复消息28。在另一实施例中，当恢复时，接收者和恢复的节点10通信，以识别已经接收到的消息28。这允许节点10避免发送相同重复的消息
28。

[0046] 上述过程结果导致了冗长的检查点间隔32，其进而可以导致在接收到传入消息与产生对应传出消息之间的低吞吐量或增加的延迟时间。可以使用各种方法来减少此延迟时间、和/或增加吞吐量。

[0047] 第一种优化方法的特征是在后台维护日志(journal)36。每当工作存储器12中的项目被改变时，对应的条目将被写入日志36，使得日志条目可以用于在恢复时间再现所述改变。日志36可以被异步地转移到持久性存储装置16。在检查点间隔32期间，节点10将确保所有日志条目确实已经变得持久。然后可以通过使用包含工作存储器12的快照的旧检查点文件18并且应用如日志36所示的更改来实现恢复。

[0048] 该优化减少了检查点间隔32的长度，但是其以增加恢复时间为代价。特别地，从获得工作存储器12的上一张完整图像经过的时间越长，日志36中的条目数将越多。这将增加恢复时间。

[0049] 第二优化方法依赖于以下事实：节点10仅具有几个派生器进程20，每个派生器进程20产生(或“派生”)多个短生存期进程，本文以单数和复数形式表示为“派生进程22A、22B”。

[0050] 派生进程22A、22B的生存期是随机的，但其预期值远远短于派生器20生存期的预期值。因此，在检查点期间花费时间来对派生进程22A、22B进行序列化几乎没有意义。事实上，在一些情况下，序列化派生进程22A、22B所需的时间是派生进程预期生存期的很大一部分。因此，通常有利的是暂停派生器20，从而防止产生新的派生进程，并且然后允许现有派生进程22A、22B自然地终止。

[0051] 为了节省时间，如图3所示，检查点产生方法包括暂停派生器20(步骤38)并将其序列化(步骤40)。然而，现有派生进程22A继续执行(步骤42)。然后，在落后者的截止期限(落后者的截止期限被选择为限定足够长的空闲时间间隔，其足够长以允许大多数派生进程22A完成执行但是不会太长来明显地影响延迟时间)之后(步骤46)，暂停(步骤48)并序列化(步骤50)仍然在执行的派生进程(被称为“落后派生进程”)。

[0052] 因此，前述方法通过减少需要序列化的进程14的数量，来减小检查点间隔32的长度。它通过允许被期望快速终止的进程22快速终止来实现上述目的，从而消除了序列化这些进程22作为创建有效检查点的一部分的需要。

[0053] 由于认识到所要避免的缺陷实际上是在检查点间隔32期间对工作存储器12的改变，因此出现了第三优化过程。因此，如果进程14实际上不必写入工作存储器12，而是只需要读取工作存储器12，那么暂停它就没有意义了。

[0054] 为了实现该第三优化过程，节点10依赖于与每个进程相关联的代计数(generation count)。由于派生器20是一种进程，所以它具有代计数。由于派生器的派生进程22A、22B也是进程，所以它们也具有代计数。派生进程22A和派生该派生进程22A的派生器20的代计数是相关的。特别地，派生进程22A、22B的代计数等于派生它的派生器20的代计数。由动词“继承(to inherit)”的适当形式来描述引起派生进程22A、22B的代计数与派生它的派生器的代计数相关联(或由其导出)的动作。当具有特定代计数的派生器20产生派生进程22A、22B时，可以说派生进程22A、22B已经继承了派生器的代计数。

[0055] 在操作中，在检查点间隔32开始之前，派生器20已经产生较老一代的派生进程22A。在检查点间隔32开始时，派生器20被“年轻化”。

[0056] 动词“年轻化(to youthen)”及其变形和同义词描述了可以在整数上执行的特定计算操作。如本文所使用的，对其进行年轻化运算的特定整数是代计数。描述了可以在代计数上执行的操作。

[0057] 在本文所描述的特定示例中，使派生器20年轻化的动作指增加其代计数的动作。在年轻化之后，派生器20则继续在检查点间隔32期间产生派生进程，仅仅现在，它产生较年轻一代的派生进程22B。这样做的结果是在节点10内共存两种派生进程22：在派生器20年轻化之前产生的较老一代的派生进程22A、以及在派生器20年轻化之后产生的较年轻一代的派生进程22B。

[0058] 参考图4，在检查点间隔开始时，派生器20被暂停(步骤52)，使得它在暂停时不产生任何新的派生进程，并且其处理状态被保存(步骤54)。然后派生器20使得其代计数增加(步骤56)，此后，派生器20继续(即，不暂停)。在继续之后，派生器20能够再次产生派生进程22，不过这一次，它的所有派生进程22B都将在较年轻一代的派生进程中。

[0059] 尝试写入工作存储器12的任何较年轻一代的派生进程22B被阻止，直到检查点间隔32完成。因此，较年轻一代的派生进程22不能运行到完成。它们只能运行直到第一次实际写入工作存储器12的时刻。然而，较年轻一代的派生进程22可以至少在中途完成。这允许甚至在检查点间隔32期间发生一些处理。

[0060] 通常，在检查点间隔32期间，存储装置12中的所有进程14将被序列化。然而，在图4的优化方法中，仅序列化较老一代的派生进程22A是有利的。

[0061] 代计数使得节点10能够识别哪个派生进程是较年轻一代的派生进程22B，并且因此避免保存其状态。

[0062] 遗憾的是，不得不等待较老一代派生进程22A完成处理，这往往会增加延迟时间，因为年轻一代的派生进程22B不能进行全通径，直到所有的较老一代派生进程22A都完成，或者直到较老一代派生进程22A的落后者暂停所触发落后者截止期限。

[0063] 在第二优化方法的变型中，代替阻止尝试修改工作存储器12的较年轻一代派生进程22B，并且因此失去继续进行有用工作的机会，节点10可以用世代号(generation number)来标记工作存储器12中的每个数据项。如果较年轻一代的派生进程22B修改了一个存储器位置，而不是阻止直到检查点之后，则节点10将通过更新其世代号来年轻化存储器位置。那么，如果较老一代的派生进程22A试图读或写这种年轻化的存储器位置，那么较老一代的派生进程22A会通过暂停自己、将其状态写到检查点、更新它的世代号、继续执行年轻化状态，从而来自发地年轻化它自身。节点10还使用世代号来标记写入日志的条目，使得其可以将对应于较老一代派生进程的日志条目与对应于较年轻一代派生进程的日志条目区分开。

[0064] 第四种优化方法依赖于允许较年轻一代派生进程22B即使在第一次尝试写入工作存储器12之后也继续处理的想法。该方法依赖于以下事实：有时，将计算结果写入工作存储器12的顺序不重要。如果是这种情况，则可以稍后对工作存储器12的写入简单地排队。此方法也允许即使在第一次尝试写入工作存储器12之后，较年轻一代的派生进程22B在检查点间隔32期间也继续工作。

[0065] 通常，每当执行一系列操作时，出现的问题是序列中的操作顺序是否会使序列的结果有差异。如果操作在序列内的位置不影响结果，则该序列内的操作被称为“可交换的”。否则，操作是“不可交换的”。可交换操作的示例是增加或减少一值的指令、将记录插入到列表中某个限定位置的指令、以及通常地不需要读取待执行的值的任何操作。第四优化方法利用这些可交换的操作。

[0066] 现在参考图5，在第四优化方法中，在通常不允许较年轻一代的派生进程22B写入存储器12时，节点10从较年轻一代的派生进程22B接收写入请求(步骤60)。然而，在该方法中，节点10区分可交换操作和不可交换操作(步骤62)。如果所提出的写入是可交换的，则节点10将其排队(步骤64)。然后较年轻一代的派生进程22B继续执行(步骤66)。这允许较年轻一代的派生进程22B在其第一次尝试写入工作存储器12之后继续处理。其结果是，只要较年轻一代的派生进程22B实施的任何写入操作是可交换的，则该较年轻一代的派生进程22B在检查点间隔32期间继续执行。另一方面，如果提出的写入是不可交换的写入，则节点10暂停执行较年轻一代的派生进程22B(步骤68)。

[0067] 除了不可交换的写入，还有其它条件可以允许派生进程22B在本来通常不能写入的条件下写入。另一个示例出现在较年轻一代派生进程22B检查存储器12之后认识到较老一代派生进程22A不可能进行进一步的存储器访问时。

[0068] 第五优化方法是减少延迟时间，该延迟时间的出现原因是由于传出消息托管区域30直到检查点间隔32完成并且与产生传出消息28相关联的所有计算已被提交到持久性存储装置16才释放传出消息28。在发送错误消息的后果严重的情况下，在从传出消息托管区域30释放消息28之前，等待直到检查点间隔32结束的想法是有用的。然而，有时发送错误消息的影响是最小的，但是发送延迟消息的后果是严重的。

[0069] 作为示例，考虑传出消息28是特定零售商店中商品优惠券的情况。假设装置已经检测到用户在特定时刻处于该特定零售店附近。显然，在用户有机会离开零售商店之前，期望立即传送消息28。如果这个消息28在等待发送的传出消息托管区域30上滞留，那么就会丢失优惠券有用的机会。另一方面，如果该优惠券是由于节点10的故障而随后丢失的计算的结果，那么任何人都不可能抱怨。毕竟，要不商店可能会进行它本不该进行的销售，而且用户可能已经获得了商品的一些折扣。

[0070] 第五优化方法，其在不等待将底层数据提交到持久性存储装置16的情况下释放传出消息28，预先假定传送传出消息28的时间是重要的，并且与其延迟传送的不良后果相比，错误的或不一致的传出消息28的成本是最小的。在第五优化方法中，在检查点间隔32结束之前从传出消息托管区域30释放传出消息28或者完全地绕开传出消息托管区域30。

[0071] 图6示出多节点装置70，其中结合图1-图6描述的类型的多个节点72、74、76、78彼此通信并且彼此协作进行数据处理。在这种情况下，任务可以将消息从第一节点72发送到第二节点74。

[0072] 在某些情况下，消息可以具有将任务从第一节点72迁移到第二节点74的效果。从一个节点迁移到另一个节点的任务被称为“迁移(migrant)”任务。取决于不同视角，迁移任务是“移入(immigrant)”任务或“移出(emigrant)”任务。从第一节点72的视角来看，因为任务将要离开第一个节点，所以迁移任务是“移出”任务。相反地，从第二节点74的视角来看，因为任务将要到达第二节点74，所以迁移任务是“移入”任务。

[0073] 在其它情况下，消息可能是远程过程调用或远程数据访问请求，使得请求任务在接收到返回消息之前不能继续。在其它情况下，任务可以使用该消息简单地将信息从第一节点72异步地发送到第二节点74。例如，可以使用本文描述的用于提升容错和恢复的技术来配置诸如在2015年9月2日提交的、发明名称为“EXECUTING GRAPH-BASED PROGRAM SPECIFICATIONS(执行基于图形的程序规范)”的序列号为14/842,956的美国专利申请中描述的计算系统，该申请通过引用合并于此。

[0074] 在这种情况下，上述方法的应用将不太理想，部分是因为直到在下一个检查点间隔32结束时将消息80从托管中释放时，才能将消息80从第一节点72发送到第二节点76。这导致了相当长的延迟时间。虽然可以通过对于多节点装置70中的节点到节点发送的消息免除托管来潜在地减少这种延迟时间，但是由于不确定性，这样的免除是不够的。

[0075] 例如，当存在多个节点72、74、76、78时，因为许多计算是非确定性的，所以会出现这样和那样的困难。这种不确定性计算的示例包括：结果取决于发生读取和写入的顺序的示例，依赖于实时时钟的示例，以及依赖于随机数发生器的结果的示例，这些示例已经在上文中结合传出消息托管区域30的有利性进行了描述。

[0076] 如果第一节点72与第二节点74通信，然后在下一个检查点间隔32之前失去联系(例如由于故障)，则装置70可能由于这种不确定性而以不一致性告终，如下所述。在故障之后，装置70将从最近的检查点恢复第一节点72并且重新开始计算。在将消息从第一节点72传输到第二节点74之前，可以从计算的点重新开始计算。由于计算的非确定性特性，在从检查点恢复之后，第一节点72很大程度上可能发送完全不同的消息到第二节点74。但是，该第二节点74可能已经接收到原始消息，这潜在地将两个节点72和74置于不一致的状态中。例如，节点72处于已经向节点74发送“新”版本消息的状态，但是节点74处于已经对“旧”版本消息进行动作的状态。此外，节点74还可能基于从节点72接收到的原始消息，已向另一节点76发送消息，因此节点72和节点76也可能处于不一致的状态。因此，不一致性可以像病毒一样传播到装置70中的所有节点。

[0077] 避免上述困难的一种方法是确保所有节点72、74、76、78对它们的检查点同步，例如使用“屏障同步”操作，如下所述。“检查点领导者”向所有节点发送消息，命令它们开始检查点间隔。然后，在每个检查点完成之后，每个节点回复检查点领导者，确认检查点完成。当检查点领导者已经从所有节点接收到确认时，它将命令所有节点提交检查点，然后继续处理。

[0078] 这种方法形成了多节点检查点问题的解决方案的基础，但并没有完全解决问题，原因有两个。首先，在多节点装置中，某些节点可能在故障中幸存，在这种情况下，幸存的节点必须从它们的当前状态向后滚动到检查点状态(而不是向前滚动到检查点状态)。其次，当执行检查点时，可能有在传输中的消息，这可能允许非确定性从旧处理间隔、经过检查点、并且泄漏到新的处理间隔。

[0079] 在单节点装置中，如果节点10发生故障，则它只需要向前滚动以恢复未提交的工作。但是在多节点装置70中，在节点78故障时，未发生故障的其它节点72、74、76可能需要向后滚动。分布式装置70通过使一些节点78向前滚动并且其它节点72、74、76向后滚动来恢复的这种机制意味着，实际上可以使所有节点72、74、76、78在相同检查点处重新开始。因此，所得到的装置70实现了所有节点的同时检查点的效果。然而，它并不是通过尝试在所有节点上实际地同步操作来实现的，如上所述这是困难的。相反，它通过操纵节点72、74、76、78的状态来获得同步检查点的优点，而不必实际地提供这样的检查点。

[0080] 为了实现上述恢复方法，节点72、74、76、78执行分布式检查点方法，如下详细描述的。参考图7，当实现分布式检查点方法时，每个进程和每个消息获取代计数82。另外，维护与每个检查点相关联的任务的运行计数84。每个节点还维护其派生器20的派生器-注册表86。另外，每个节点72维护节点代计数88。

[0081] 节点代计数88使得节点76能够执行代间隙(generation gap)，在代间隙中由较年轻一代派生进程22A执行的工作与由较老一代派生进程22B执行的工作彼此不会相互干扰。作为代间隙的结果，较老一代和较年轻一代可能或多或少地忽视彼此。实际上，节点76变成两个虚拟机，一个被较老一代的派生进程22A看到，另一个被较年轻一代的派生进程22B看到。这两个虚拟机共存在相同的物理平台上，但是彼此正交。

[0082] 此外，每个节点76还实现双向日志90，其使得节点76根据需要向前或向后滚动到特定状态。双向日志90包括对工作存储装置92的更改、检查点任务状态的列表94和检查点消息96。这些元素提供了一种及时向前滚动的方式。此外，双向日志90以存储器12中的撤销日志98为特征，以使得节点76能够及时地向后滚动。一般来说，及时向前滚动是故障节点恢复的方式。及时向后滚动是当装置70中的一个节点发生故障时另一个节点所做的动作。

[0083] 在操作中，如图6所示，主节点72向所有其它节点74、76、78(即“从属节点”)发送检查点消息100，指示检查点的到来。然而，不要求该检查点在所有节点72、74、76、78中同时发生。

[0084] 图8示出了在存在计算不确定性的情况下示例性容错和恢复过程的流程图。响应于接收到检查点消息(步骤102)，从属节点76将不会立即开始检查点间隔。如上所述，这是不切实际的。相反，从属节点76增加其节点代计数88(步骤104)，并创建日志条目，指示其节点代计数88增加(步骤106)。

[0085] 然后，从属节点76暂停其所有的派生器20(步骤108)，并将它们的状态写入双向日志90(步骤110)。然后，对于其每个派生器20，从属节点76增加该派生器的代计数82(步骤112)。随着其代计数82增加，允许派生器20继续操作(步骤114)。然而，由于派生器的代计数
82已经增加，所以任何得到的派生进程22B将处于较年轻的一代。

[0086] 在这一点上，两代将共存于从属节点76中。较老一代的派生进程22A，即代计数比该节点的代计数少一代的那些派生进程，可以继续处理至完成，必要时向存储器12写入。较年轻一代的派生进程22B，即代计数符合节点代计数88的那些派生进程，可能会处理到写入存储器12为止。此时，较年轻一代的派生进程22B被阻止。

[0087] 应该指出的是，在至此的描述中，只涉及两代派生进程：较老一代的派生进程22A(其代计数82比节点代计数88少一代)，以及较年轻一代的派生进程22B(其代计数82匹配节点代计数88)。然而，原则上没有理由在同一平台上不能共存多于两代。

[0088] 参考图9，在多节点装置70中，任务79可以从发送节点78移出并移入到接收节点76。如结合图6所示，这样的任务79被称为“迁移任务”或“迁移”。

[0089] 在下面的讨论中，有必要引用与特定对象相关联的值。为了避免附图中的附图标记发生歧义，并且以与标准数学符号一致的方式，括号将用于表示“的”。因此，由于“88”已被分配给“节点代计数”以及“76”是节点，所以节点76的节点代计数88将被写为88(76)。

[0090] 当迁移的代计数82(79)与接收节点76的节点代计数88(76)不同时，可能会出现困难。通过在节点之间实现消息托管区域，可以避免这些困难。但是，这将再次导致延迟时间，而分布式检查点方法首先要避免的就是延迟时间。

[0091] 根据分布式检查点方法，有三种可能性：发送节点的节点计数88(78)与接收节点的节点计数88(76)相同；发送节点78具有比接收节点的节点计数88(76)低的节点代计数88(78)；并且发送节点78具有比接收节点的88(76)更高的节点代计数88(78)。

[0092] 在第一种可能性中，迁移将具有与发送节点78的节点计数88(78)相同的代计数82(79)。因此，发送节点78、接收节点76和迁移79都具有相同的代计数。在这种情况下，没有什么特别需要做的。

[0093] 当在迁移79传送的同时接收节点76增加其代计数88(76)时，可能会出现第二种可能性。这意味着，在移入接收节点76时，迁移79将其自身呈现为此时已经成为接收节点76的较老一代的成员。在这种情况下，接收节点76将通过增加迁移的代计数82(79)来年轻化该迁移79。其结果是，迁移任务79将能够继续处理，但是如同其它较年轻一代的派生进程22B一样，它将被阻止写入存储器12。然后，在接收节点76处对迁移79的年轻化进行日志记录。由于年轻化的动作发生在接收节点76处，所以其被称为“移入侧年轻化”。

[0094] 当在迁移79移出之前发送节点78增加其代计数88(78)时，可能出现第三种可能性。在这种情况下，发送节点78通过在发送之前增加迁移的代计数82(79)来年轻化迁移79，并且在发送节点处对年轻化事件进行日志记录。由于年轻化的动作发生在发送节点78处，所以其称为“移出侧年轻化”。

[0095] 在任一种情况下，已经从主节点接收到检查点消息的节点76将设置截止期限，以允许较老一代派生进程22A完成执行，从而确保较老一代接近灭绝，并避免需要记录它们的状态(步骤116)。尽管如此，可能会存在终止很慢的较老一代的派生进程22A。一旦达到截止期限，则节点76再等待延长的时间是不切实际的，仍在运行的任何较老一代派生进程22将被暂停、序列化、记录日志和年轻化，之后允许其继续执行，受到的约束是它不能写入工作存储器12，直到将工作存储器12提交到持久性存储装置16之后。

[0096] 从属节点76直到它知道不再期待有较老一代的移入到达才会开始实际检查点。为了实现这一点，每当节点72识别出所有的较老一代的移出已成功移出时，它向所有其它节点74、76、78广播刷新消息。一旦从属节点76已经从所有节点72、74、78接收到刷新消息，它就知道较老一代移入的流动已经结束(步骤118)。较年轻一代的移入仍然可以到达从属节点76，正如较年轻一代的移出仍然可以从从属节点76离开。然而，这些较年轻一代的移出与检查点过程无关。

[0097] 此时，从属节点76现在准备将其工作存储器12提交到持久性存储装置16(步骤120)。这以与上述单节点情况相同的方式进行。

[0098] 节点故障后重新启动的过程如图10所示，这取决于涉及的节点是否示故障节点。在接收到重新启动的指令(步骤122)之后，节点确定它是否是故障节点，或者确定装置70中的另一节点是否故障(步骤124)。如果节点是故障节点，则它检索日志并且从其最后的有效检查点向前滚动(步骤126)。如果节点不是故障节点，则它向后滚动到其上一个检查点(步骤128)。

[0099] “向后滚动”操作的示例包括以下步骤：(1)终止当前正在运行的所有任务(包括派生器和派生进程)；(2)使用双向日志条目来撤消对存储器的任何更改。

[0100] 在已经向前滚动了任何故障节点并且已经向后滚动了任何幸存节点之后，装置70还可以执行其它操作，作为重新启动任务的一部分。例如，装置70可以执行以下操作：(1)刷新通信网络，以确保早于故障的所有消息已经被丢弃，(2)通过从日志恢复它们的保存状态并且重新启动它们，来重新启动作为检查点一部分的所有任务，(3)重新发送在检查点之前未发送的任何消息，以及(4)处理从检查点接收但尚未被处理的任何消息。

[0101] 从故障节点上的最后一个有效检查点向前滚动的任务是可能耗时的。参考图11，在一些实践中，在第二节点134上维护来自第一节点132的存储器130的副本128是有用的。优选地，第二节点134不具有与第一节点132相同的故障模式。在正常操作中，在每个检查点处，副本128与第一节点132处的存储器130同步。副本128还具有关联的撤销日志136，以使其能够向后滚动到其最近检查点处的状态。

[0102] 现在参考图12，在第一节点132故障时，将第二节点124处的副本128指定为主节点(步骤138)。第二节点124上的所有进程被关闭(步骤140)，之后重新启动第二节点134(步骤142)。此时用作原本的前一副本128借助于撤销日志136向后滚动到上一个检查点(步骤
144)。然后，多节点装置70的操作可以继续，等待向后滚动时间的顺序上的恢复。这通常比向前滚动时间短得多。同时，恢复的第一节点132可以继续向前滚动到正确的状态，而不会减缓多节点装置70的整体恢复。一旦第一节点132准备就绪，它再次接管为原本，并且前一副本128再次成为副本。

[0103] 尽管图11示出仅一个第二节点134，但应当理解，可以存在多于一个的第二节点，每个节点具有副本128和撤销日志136。在这种情况下，在第一节点132故障时，多个第二节点中的一个必须被选择作为第一节点存储器的新原本的所有者。

[0104] 在某些情况下，可能会有许多幂等(idempotent)的操作。在这种情况下，代替向前滚动，简单地重复执行幂等运算的计算是合理的，因为这些计算不会造成任何伤害。

[0105] 恢复的最终结果是所有点都处于与从一代到下一代的过渡一致的状态。其结果是，较老一代进程的任何工作都不会丢失，但是由较年轻一代进程完成的所有的工作都丢失了。这确保了所有节点之间一致的状态。在这种背景下，在没有任何故障的情况下本来可以到达的状态是“一致的”。相比之下，如果只能通过一个或多个故障的发生来解释该状态，则该状态是“不一致的”。

[0106] 图13示出了结合图6和图9所示的多节点装置70中的发送节点78和接收节点76中的几个派生进程的状态。在图13中，时间沿垂直轴向下增加。时间轴示出第一间隔146、跟随第一间隔146的第二间隔148、以及跟随第二间隔148的第三间隔150。

[0107] 图13示出了几个派生进程22A-22H，其每个具有相关联的代计数。具有N个代计数的派生进程在本文中将被称为“第一代派生进程”。具有N+1个代计数的派生进程在本文中将被称为“第二代派生进程”。形容词“第一代”和“第二代”也将用于指利用代计数标记的其它实体，包括节点、迁移任务和派生进程。

[0108] 在第一间隔146期间，发送节点78是第一代节点。在第二间隔和第三间隔150期间，发送节点78是第二代节点。应当注意，节点的这种行进是循环的，使得第三间隔150之后将是对于第二代起到与第二间隔148对于第一代所起作用相同作用的间隔。尽管不一定与在发送节点78处发生的过程同步，但是在接收节点76上发生相同的过程。为了方便起见，使用相同的附图标记来表示发送节点78和接收节点76中的间隔。然而，这并不意味着它们是同步的。

[0109] 在第一间隔146期间，派生器进程20派生各种第一代派生进程22A-22E。在整个第一间隔146期间，任何第一代派生进程22A-22E可以自由地写入发送节点存储器12A。

[0110] 在第二间隔148期间，发送节点78成为第二代节点。因此，派生器进程20现在只派生第二代派生进程。在第二间隔148期间，任何第一代派生进程22A-22E保持自由地写入发送节点存储器12A。第二代派生进程22F-22G可以自由地执行，但是禁止写入发送节点存储器12A。因此，此第二间隔148的目的是为任何残留的第一代派生进程22、22D、22E提供一些时间，以在检查点间隔32出现之前完成执行。

[0111] 在第三间隔150期间，派生器进程20派生另一个第二代派生进程22H。在第三间隔150期间，不再保持有第一代派生进程，并且所有的第二代派生进程22F-22H都可以自由地写入发送节点存储器12A。

[0112] 在发送节点78处，第一个第一代派生进程22A、第二个第一代派生进程22B、第三个第一代派生进程22C、第四个第一代派生进程22D和第五个第一代派生进程22E全部在第一间隔146期间开始执行。然而，其中仅有第一个第一代派生进程22A和第二个第一代派生进程22B设法在第一个间隔146期间结束执行。第三个第一代派生进程22C设法在第二间隔148期间结束。第四个第一代派生进程22D需要很长时间，直到第三间隔150开始才能结束。第五代第一代派生进程22E从未实际在发送节点78处结束。代替地，它在第二间隔148中途迁移到接收节点76。迁移的同时接收节点76仍然处于其自己的第二间隔148中。

[0113] 在执行期间，第一个第一代派生进程22A在第一间隔146期间写入发送节点存储器12A，并且第三个第一代派生进程22C在第二间隔148期间写入发送节点存储器12A。第二个第一派生进程22B在执行期间根本不写入发送节点存储器12A。第五个第一代派生进程22E最终(但仅仅在接收节点76处)写入发送节点存储器12A。

[0114] 在第二间隔148期间，第一个第二代派生进程22F和第二个第二代派生进程22G都开始执行。有时，在第二间隔148期间，第一个第二代派生进程22F达到它必须向发送节点存储器12A写入的点。然而，由于仍然是第二间隔148，所以禁止写入发送节点存储器12A。因此，如虚线所示，它被暂停。一旦第三间隔150开始，则第一个第二代派生进程22F向发送节点存储器12A写入并完成执行。

[0115] 同时，第二个第二代派生进程22G在第二间隔148期间已经开始的足够晚，使得截止到实际上其必须向发送节点存储器12A写入的时刻，第三间隔150已经开始。因此，第二个第二代派生进程22G不间断地执行。

[0116] 第三个第二代派生进程22H在第三间隔150期间开始。这实质上是第一个第一代派生进程22A的镜像。

[0117] 在执行过程中，第一个第一代派生进程22A导致第一任务152迁移到接收节点76。第一任务152继承第一个第一代派生进程22A的世代号。因此，它开始作为第一代任务存在。
此第一任务152到达接收节点76，同时接收节点76仍然在第一间隔146中操作。因此，接收节点76充当第一代节点。因此，第一任务152自由执行并写入接收节点存储器12B，只要在第三间隔150在接收节点76上开始之前即可。

[0118] 同样，在执行过程中，第二个第一代派生进程22B使得第二任务154迁移到接收节点76。第二任务154继承第一个第一代派生进程22A的世代号。因此，它开始作为第一代任务存在。然而，此第二任务154到达接收节点76，同时接收节点76已经在其第二间隔148中操作。因此，第二任务154从第一代任务改变为第二代任务。这包括在接收节点日志文件156中日志记录第二任务154的伴随步骤。

[0119] 在发送节点78处对于第五个第一代派生进程22E发生类似的事件。第五个第一代派生进程22E在执行中途迁移到接收节点76。然而，当其到达接收节点76时，接收节点76已经开始了它自己的第二间隔148。因此，第二节点已经变成第二代节点。因此，第五个第一代派生进程22E被改变为第二代派生进程。这种变化伴随着在发送节点日志文件158中对第五个第一代派生过程22E进行日志记录。然后，第五个第一代派生进程22E继续在接收节点76上执行，但是作为第二代派生进程。

[0120] 同时，返回发送节点78处，第四个第一代派生进程22D在第二间隔148结束之前还没有结束执行。此时，第四个第一代派生进程22D在发送节点日志文件158处进行日志记录，并且其代计数增加，使得它现在变成第二代派生进程。然后，第四个第一代派生进程22D在第三间隔150期间继续执行。

[0121] 应当注意的是，第四个第一代派生进程22D在其迁移到接收节点76期间持续由第五个第一代派生进程22E持续的相同的两个步骤，即记录步骤和派生变化。因此，可以合理的说，第四个第一代派生过程22D在某种意义也被迁移了。主要区别在于，第五个第一代派生进程22E进行了节点间迁移，而第四个第一代派生进程22D进行了节点内迁移。

[0122] 因此，这里描述的检查点和恢复方法基于这样的认知：多个节点之间同时执行检查点的有利性不是源于时间同步性，而是源于时间同步的副作用。因此，该方法再现了多个节点之间检查点的时间同步性的副作用，而不需要实际地实现时间同步性。

[0123] 例如，可以使用执行合适的软件指令的可编程计算系统来实现上述容错和恢复方法，或者可以在诸如现场可编程门阵列(FPGA)或某些混杂形式的合适硬件中实现上述容错和恢复方法。例如，在编程方法中，软件可以包括在一个或多个编程或可编程计算系统(其可以是诸如分布式、客户端/服务器或网格的各种架构)上执行的一个或多个计算机程序中的过程，每个计算系统包括至少一个处理器，至少一个数据存储系统(包括易失性和/或非易失性存储器和/或存储元件)，至少一个用户界面(用于使用至少一个输入设备或端口接收输入，并且用于使用至少一个输出设备或端口提供输出)。软件可以包括例如提供与数据流图的设计、配置和执行相关的服务的更大程序的一个或多个模块。程序的模块(例如，数据流图的元素)可以被实现为符合存储在数据仓库中的数据模型的数据结构或其他有组织的数据。

[0124] 软件可以使用持续一段时间(例如，动态存储器装置(例如动态RAM)的刷新周期之间的时间)的介质的物理特性(例如，表面凹坑和平台、磁畴或电荷等)以非暂时性形式存储，例如被实施在易失性或非易失性存储介质或任何其它非暂时性介质中。在准备加载指令时，软件可以提供在有形、非暂时性介质上，例如CD-ROM或其他计算机可读介质(例如，可由通用或专用计算系统或设备读取)，或者可以通过网络的通信介质被递送(例如，被编码成传播信号)到其被执行的计算系统的有形、非暂时性介质。可以在专用计算机上或使用诸如协处理器或现场可编程门阵列(FPGA)或特定的专用集成电路(ASIC)的专用硬件来执行处理中的一些或全部。处理可以以分布式方式实现，其中由软件指定的计算的不同部分由不同的计算元件执行。每个这样的计算机程序优选地存储在或下载到可由通用或专用可编程计算机访问的存储设备的计算机可读存储介质(例如，固态存储器或介质，或磁介质或光介质)上，用于当计算机读取存储设备介质以执行本文所述的处理时，配置和操作计算机。本发明的系统还可以被认为可实现为配置有计算机程序的有形的、非暂时性介质，其中如此配置的介质使得计算机以特定和预定义的方式操作以执行本文描述的一个或多个处理步骤。

[0125] 已经描述了本发明的多个实施例。然而，应当理解，前述描述旨在说明而不是限制本发明的范围，本发明的范围由所附权利要求的范围限定。因此，其他实施例也在所附权利要求的范围内。例如，在不脱离本发明的范围的情况下可以进行各种修改。另外，上述的一些步骤可以是与顺序无关的，并且因此可以以与所描述的顺序不同的顺序来执行。

[0126] 已经描述了我们所声称的新的发明，并且该发明通过专利证书来获得保护。